No Access

PARALLEL ALGORITHMS FOR VEHICLE ROUTING PROBLEMS

School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6, Canada

Research supported by the Natural Sciences and Engineering Research Council of Canada and the Advanced Systems Institute.

Search for more papers by this author

and

RAMESH KRISHNAMURTI

School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6, Canada

Research supported by the Natural Sciences and Engineering Research Council of Canada.

Search for more papers by this author

https://doi.org/10.1142/S0129626403001598Cited by:0 (Source: Crossref)

Abstract

Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log³ n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM.

We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n²) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log³ n) time parallel algorithm on a CREW PRAM.

Keywords:

References

G. Brodal, J. Traff and C. Zaroliagis, Journal of Parallel and Distributed Computing 49(1), 4 (1998). Crossref, Web of Science, Google Scholar
S. A. Cook, Information and Control 64, 2 (1985). Crossref, Google Scholar
M. Desrocherset al., Vehicle Routing: Methods and Studies (North-Holland, Amsterdam, 1988) pp. 242–254. Google Scholar
M. Desrochers and F. Soumis, European Journal of Operational Research 35, 242 (1988). Crossref, Web of Science, Google Scholar
J. Desrosiers, F. Soumis and M. Desrochers, Networks 14, 545 (1984). Crossref, Web of Science, Google Scholar
E. Dijkstra, Numerische Mathematik 1, 269 (1959). Crossref, Google Scholar
R. Floyd, Communications of the ACM 5(6), 345 (1962). Crossref, Web of Science, Google Scholar
S. Fortune and J. Wyllie, Proceedings of the Tenth Annual ACM Symposium on the Theory of Computing (1978) pp. 114–118. Google Scholar
G. Frederickson and D. Guan, Siam J. of Computing 21(6), 1130 (1992). Crossref, Web of Science, Google Scholar
Y. Karuno, H. Nagamochi and T. Ibaraki, Proceedings of the Fourth International Symposium on Algorithm and Computation (Springer-Verlag, 1993) pp. 486–495. Google Scholar
R. Karp and V. Ramachandran, Handbook of Theoretical Computer Science (Volume A), ed. J. van Leeuwen (MIT Press/Elsevier, Cambridge, 1990) pp. 869–941. Google Scholar
J. Ma and T. Takaoka, J. Information Processing 12(2), 119 (1989). Google Scholar
G. Miller and J. Reif, Proceedings of the 26th Symposium on Foundations of Computer Science (IEEE, 1985) pp. 478–489. Google Scholar
H. Psaraftiset al., Management Science 36(2), 212 (1990). Crossref, Web of Science, Google Scholar
J. H. Reif (ed.) , Synthesis of Parallel Algorithms ( Morgan Kaufmann , San Mateo, California , 1993 ) . Google Scholar
N. G. F. Sancho, Journal of Mathematical Analysis and Applications 186, 643 (1994). Crossref, Web of Science, Google Scholar
M. Solomon, Operations Research 35(2), 254 (1987). Crossref, Web of Science, Google Scholar
M. Solomon and J. Desrosiers, Transportation Science 22, 1 (1988). Crossref, Web of Science, Google Scholar
J. N. Tsitsiklis, Networks 22, 263 (1992). Crossref, Web of Science, Google Scholar
S. Warshall, Journal of the ACM 9(1), 11 (1962). Crossref, Web of Science, Google Scholar