{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:40:52Z","timestamp":1767339652014,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Danish Council for Independent Research | Natural Sciences","award":["DFF-1323-00178"],"award-info":[{"award-number":["DFF-1323-00178"]}]},{"name":"NSF","award":["CCF-0728841"],"award-info":[{"award-number":["CCF-0728841"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"<jats:p>Dial-a-Ride problems consist of a set<jats:italic>V<\/jats:italic>of<jats:italic>n<\/jats:italic>vertices in a metric space (denoting travel time between vertices) and a set of<jats:italic>m<\/jats:italic>objects represented as source-destination pairs {(<jats:italic>s<jats:sub>i<\/jats:sub>,t<jats:sub>i<\/jats:sub><\/jats:italic>)}<jats:sup><jats:italic>m<\/jats:italic><\/jats:sup><jats:sub><jats:italic>i<\/jats:italic>=1<\/jats:sub>, where each object requires to be moved from its source to destination vertex. In the<jats:italic>multi-vehicle Dial-a-Ride<\/jats:italic>problem, there are<jats:italic>q<\/jats:italic>vehicles, each having capacity<jats:italic>k<\/jats:italic>and where each vehicle<jats:italic>j<\/jats:italic>\u2208 [<jats:italic>q<\/jats:italic>] has its own depot-vertex<jats:italic>r<jats:sub>j<\/jats:sub>\u2208 V<\/jats:italic>. A feasible schedule consists of a capacitated route for each vehicle (where vehicle<jats:italic>j<\/jats:italic>originates and ends at its depot<jats:italic>r<jats:sub>j<\/jats:sub><\/jats:italic>) that together move all objects from their sources to destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e.,<jats:italic>makespan<\/jats:italic>) of vehicles, where the completion time of vehicle<jats:italic>j<\/jats:italic>is the time when it returns to its depot<jats:italic>r<jats:sub>j<\/jats:sub><\/jats:italic>at the end of its route. We study the<jats:italic>preemptive<\/jats:italic>version of multi-vehicle Dial-a-Ride, in which an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Our main results are an<jats:italic>O<\/jats:italic>(log<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>)-approximation algorithm for<jats:italic>preemptive multi-vehicle Dial-a-Ride<\/jats:italic>, and an improved<jats:italic>O<\/jats:italic>(log<jats:italic>t<\/jats:italic>)-approximation for its special case when there is no capacity constraint (here<jats:italic>t<\/jats:italic>\u2264<jats:italic>n<\/jats:italic>is the number of distinct depot-vertices). There is an \u03a9 (log<jats:sup>1\/4-\u03f5<\/jats:sup><jats:italic>n<\/jats:italic>) hardness of approximation known even for single vehicle capacitated Dial-a-Ride [G\u00f8rtz 2006]. For uncapacitated multi-vehicle Dial-a-Ride, we show that there are instances when natural lower bounds (used in our algorithm) are \u02dc\u03a9(log<jats:italic>t<\/jats:italic>) factor away from the optimum.<\/jats:p><jats:p>We also consider the special class of metrics induced by graphs excluding any fixed minor (e.g., planar metrics). In this case, we obtain improved guarantees of<jats:italic>O<\/jats:italic>(log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) for capacitated multi-vehicle Dial-a-Ride, and<jats:italic>O<\/jats:italic>(1) for the uncapacitated problem.<\/jats:p>","DOI":"10.1145\/2629653","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Minimum Makespan Multi-Vehicle Dial-a-Ride"],"prefix":"10.1145","volume":"11","author":[{"given":"Inge Li","family":"G\u00f8rtz","sequence":"first","affiliation":[{"name":"Technical University of Denmark, Kongens Lyngby Denmark"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9283-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0484"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch and Yossi Azar. 1997. Buy-at-bulk network design. In FOCS. 542--547. Baruch Awerbuch and Yossi Azar. 1997. Buy-at-bulk network design. In FOCS. 542--547.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93417"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281112"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(00)00056-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060617"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701392056"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796446"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750317"},{"key":"e_1_2_1_14_1","first-page":"2","article-title":"The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 4OR","volume":"1","author":"Cordeau Jean-Francois","year":"2003","unstructured":"Jean-Francois Cordeau and Gilbert Laporte . 2003 . The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 4OR : A Quarterly Journal of Operations Research 1 , 2 . Jean-Francois Cordeau and Gilbert Laporte. 2003. The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 4OR: A Quarterly Journal of Operations Research 1, 2.","journal-title":"A Quarterly Journal of Operations Research"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1030.0052"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.11.010"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_20"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0490"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721857"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.527"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 142--151","author":"Hall Leslie A.","year":"1996","unstructured":"Leslie A. Hall , David B. Shmoys , and Joel Wein . 1996 . Scheduling to minimize average completion time: Off-line and on-line algorithms . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 142--151 . Leslie A. Hall, David B. Shmoys, and Joel Wein. 1996. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 142--151."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294129"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00569-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.2006.11732749"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPAN.2005.88"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e91-a.9.2328"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.29.1.17"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.08.002"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629653","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:30Z","timestamp":1750227210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2629653"],"URL":"https:\/\/doi.org\/10.1145\/2629653","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}