{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:47:01Z","timestamp":1760150821089,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T00:00:00Z","timestamp":1642464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union's Horizon 2020","award":["754462"],"award-info":[{"award-number":["754462"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are given, each of which consists of a pick-up location and a drop-off location. Serving a request means that a car must first visit the pick-up location of the request and then visit the drop-off location. Each car can only serve at most c requests. Each assignment can yield multiple different serving routes and corresponding serving times, and our goal was to serve the maximum number of requests with the minimum travel time (called CSsum) and to serve the maximum number of requests with the minimum total latency (called CSlat). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems CSsum and CSlat are APX-hard when c\u22652. We propose an algorithm, called the transportation algorithm (TA), which is a (2c\u22121)-approximation (resp. c-approximation) algorithm for CSsum (resp. CSlat); these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e., c=2. In addition to the TA, we investigated another algorithm, called the match-and-assign algorithm (MA). Moreover, we call the algorithm that outputs the best of the two solutions found by the TA and MA the CA. We show that the CA is a two-approximation (resp. 5\/3) for CSsum (resp. CSlat), and these ratios are better than the ratios of the individual algorithms, the TA and MA.<\/jats:p>","DOI":"10.3390\/a15020030","type":"journal-article","created":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T22:46:32Z","timestamp":1642545992000},"page":"30","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2006-0601","authenticated-orcid":false,"given":"Kelin","family":"Luo","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2547-3782","authenticated-orcid":false,"given":"Frits C. R.","family":"Spieksma","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,18]]},"reference":[{"key":"ref_1","unstructured":"(2021, December 01). Uber. Available online: https:\/\/www.uber.com\/nl\/en\/ride\/uberpool\/."},{"key":"ref_2","unstructured":"(2021, December 01). TransVision. Available online: https:\/\/www.transvision.nl\/."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1287\/serv.2020.0258","article-title":"Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions","volume":"12","author":"Tafreshian","year":"2020","journal-title":"Serv. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1016\/j.sbspro.2011.04.530","article-title":"Dynamic ride-sharing: A simulation study in metro Atlanta","volume":"17","author":"Agatz","year":"2011","journal-title":"Procedia-Soc. Behav. Sci."},{"key":"ref_5","unstructured":"Luo, K., Erlebach, T., and Xu, Y. (2018, January 27\u201331). Car-Sharing between Two Locations: Online Scheduling with Two Servers. Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Luo, K., Erlebach, T., and Xu, Y. (2019, January 13\u201316). Car-Sharing on a Star Network: On-Line Scheduling with k Servers. Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany.","DOI":"10.1016\/j.tcs.2018.09.004"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Liu, H., Luo, K., Xu, Y., and Zhang, H. (2019, January 13\u201315). Car-Sharing Problem: Online Scheduling with Flexible Advance Bookings. Proceedings of the Combinatorial Optimization and Applications\u201413th International Conference (COCOA 2019), Xiamen, China.","DOI":"10.1007\/978-3-030-36412-0_27"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1287\/opre.1030.0106","article-title":"An exact method for the car pooling problem based on lagrangean column generation","volume":"52","author":"Baldacci","year":"2004","journal-title":"Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bei, X., and Zhang, S. (2018, January 2\u20137). Algorithms for trip-vehicle assignment in ride-sharing. Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, LA, USA.","DOI":"10.1609\/aaai.v32i1.11298"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.trb.2017.01.004","article-title":"A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem","volume":"99","author":"Masoud","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.trb.2017.10.006","article-title":"A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ride-sharing system","volume":"106","author":"Masoud","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1073\/pnas.1611675114","article-title":"On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment","volume":"114","author":"Samaranayake","year":"2017","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1177\/0278364912444766","article-title":"Robotic load balancing for mobility-on-demand systems","volume":"31","author":"Pavone","year":"2012","journal-title":"Int. J. Robot. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1287\/trsc.1100.0346","article-title":"Time slot management in attended home delivery","volume":"45","author":"Agatz","year":"2011","journal-title":"Transp. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/j.tre.2016.04.010","article-title":"Making dynamic ride-sharing work: The impact of driver and rider flexibility","volume":"91","author":"Stiglic","year":"2016","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1287\/trsc.2017.0768","article-title":"Stable matching for dynamic ride-sharing systems","volume":"52","author":"Wang","year":"2018","journal-title":"Transp. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ashlagi, I., Burq, M., Dutta, C., Jaillet, P., Saberi, A., and Sholley, C. (2019, January 24\u201328). Edge weighted online windowed matching. Proceedings of the 2019 ACM Conference on Economics and Computation, Phoenix, AZ, USA.","DOI":"10.1145\/3328526.3329573"},{"key":"ref_18","unstructured":"Lowalekar, M., Varakantham, P., and Jaillet, P. (2020, January 9\u201313). Competitive Ratios for Online Multi-capacity Ridesharing. Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS \u201920), Auckland, New Zealand."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Guo, X., and Luo, K. (2022, January 10\u201312). Algorithms for online car-sharing problem. Proceedings of the CALDAM 2022: The 8th Annual International Conference on Algorithms and Discrete Applied Mathematics, Puducherry, India.","DOI":"10.1007\/978-3-030-95018-7_18"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Mori, J.C.M., and Samaranayake, S. (2021, January 19\u201321). On the Request-Trip-Vehicle Assignment Problem. Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), Virtual Conference.","DOI":"10.1137\/1.9781611976830.21"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Burkard, R., Dell\u2019Amico, M., and Martello, S. (2012). Assignment Problems: Revised Reprint, SIAM.","DOI":"10.1137\/1.9781611972238"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Luo, K., and Spieksma, F.C.R. (2020, January 29\u201331). Approximation Algorithms for Car-Sharing Problems. Proceedings of the Computing and Combinatorics\u201426th International Conference (COCOON 2020), Atlanta, GA, USA.","DOI":"10.1007\/978-3-030-58150-3_21"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s00186-012-0397-2","article-title":"Between a rock and a hard place: The two-to-one assignment problem","volume":"76","author":"Goossens","year":"2012","journal-title":"Math. Methods Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(94)90199-6","article-title":"Approximation algorithms for multidimensional assignment problems with decomposable costs","volume":"49","author":"Bandelt","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0166-218X(96)00128-X","article-title":"Approximation algorithms for multi-index transportation problems with decomposable costs","volume":"76","author":"Queyranne","year":"1997","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., and Shmoys, D.B. (2011). The Design of Approximation Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/30\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:03:27Z","timestamp":1760133807000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,18]]},"references-count":26,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020030"],"URL":"https:\/\/doi.org\/10.3390\/a15020030","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,1,18]]}}}