Approximation Algorithms for Car-Sharing Problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequality. Each request needs to be served by a car, which means that a car must first visit the pick-up location of the request, and then visit the drop-off location of the request. Each car can serve two requests. One problem is to serve all requests with the minimum total travel time (called), and the other problem is to serve all requests with the minimum total latency (called). We also study the special case where the pick-up and drop-off location of a request coincide. We propose two basic algorithms, called the match and assign algorithm and the transportation algorithm. We show that the best of the resulting two solutions is a 2-approximation for (and a 7/5-approximation for its special case), and a 5/3-approximation for (and a 3/2-approximation for its special case); these ratios are better than the ratios of the individual algorithms. Finally, we indicate how our algorithms can be applied to more general settings where each car can serve more than two requests, or where cars have distinct speeds.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
EditorsDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
PublisherSpringer
Pages262-273
Number of pages12
ISBN (Print)9783030581497
DOIs
Publication statusPublished - 2020
Event26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, United States
Duration: 29 Aug 202031 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12273 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Computing and Combinatorics, COCOON 2020
CountryUnited States
CityAtlanta
Period29/08/2031/08/20

Keywords

  • Approximation algorithms
  • Car-sharing
  • Matching

Fingerprint Dive into the research topics of 'Approximation Algorithms for Car-Sharing Problems'. Together they form a unique fingerprint.

  • Cite this

    Luo, K., & Spieksma, F. C. R. (2020). Approximation Algorithms for Car-Sharing Problems. In D. Kim, R. N. Uma, Z. Cai, & D. H. Lee (Eds.), Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings (pp. 262-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12273 LNCS). Springer. https://doi.org/10.1007/978-3-030-58150-3_21