{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T14:40:01Z","timestamp":1734273601449,"version":"3.30.2"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2003,12]]},"abstract":"<jats:p>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<jats:sup>3<\/jats:sup>n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM.<\/jats:p><jats:p>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 [Formula: see text] -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<jats:sup>2<\/jats:sup>) 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<jats:sup>3<\/jats:sup>n) time parallel algorithm on a CREW PRAM.<\/jats:p>","DOI":"10.1142\/s0129626403001598","type":"journal-article","created":{"date-parts":[[2004,3,5]],"date-time":"2004-03-05T11:52:36Z","timestamp":1078487556000},"page":"673-687","source":"Crossref","is-referenced-by-count":0,"title":["PARALLEL ALGORITHMS FOR VEHICLE ROUTING PROBLEMS"],"prefix":"10.1142","volume":"13","author":[{"given":"ARVIND","family":"GUPTA","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAMESH","family":"KRISHNAMURTI","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1425"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"rf3","unstructured":"M.\u00a0Desrochers, Vehicle Routing: Methods and Studies (North-Holland, Amsterdam, 1988)\u00a0pp. 242\u2013254."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90034-3"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140406"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"rf8","unstructured":"S.\u00a0Fortune and J.\u00a0Wyllie, Proceedings of the Tenth Annual ACM Symposium on the Theory of Computing (1978)\u00a0pp. 114\u2013118."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/0221066"},{"key":"rf10","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Karuno, H.\u00a0Nagamochi and T.\u00a0Ibaraki, Proceedings of the Fourth International Symposium on Algorithm and Computation (Springer-Verlag, 1993)\u00a0pp. 486\u2013495.","DOI":"10.1007\/3-540-57568-5_280"},{"key":"rf11","doi-asserted-by":"crossref","unstructured":"R.\u00a0Karp and V.\u00a0Ramachandran, Handbook of Theoretical Computer Science (Volume A), ed. J.\u00a0van Leeuwen (MIT Press\/Elsevier, Cambridge, 1990)\u00a0pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"rf12","first-page":"119","volume":"12","author":"Ma J.","journal-title":"J. Information Processing"},{"key":"rf13","doi-asserted-by":"crossref","unstructured":"G.\u00a0Miller and J.\u00a0Reif, Proceedings of the 26th Symposium on Foundations of Computer Science (IEEE, 1985)\u00a0pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.36.2.212"},{"volume-title":"Synthesis of Parallel Algorithms","year":"1993","author":"Reif J. H.","key":"rf15"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1994.1324"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.2.254"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.22.1.1"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220305"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626403001598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,15]],"date-time":"2024-12-15T13:59:20Z","timestamp":1734271160000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626403001598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":20,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2003,12]]}},"alternative-id":["10.1142\/S0129626403001598"],"URL":"https:\/\/doi.org\/10.1142\/s0129626403001598","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"type":"print","value":"0129-6264"},{"type":"electronic","value":"1793-642X"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}