TY - GEN

T1 - Approximation Algorithms for Car-Sharing Problems

AU - Luo, Kelin

AU - Spieksma, Frits C.R.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Car-sharing

KW - Matching

UR - http://www.scopus.com/inward/record.url?scp=85091088959&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-58150-3_21

DO - 10.1007/978-3-030-58150-3_21

M3 - Conference contribution

AN - SCOPUS:85091088959

SN - 9783030581497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 262

EP - 273

BT - Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings

A2 - Kim, Donghyun

A2 - Uma, R.N.

A2 - Cai, Zhipeng

A2 - Lee, Dong Hoon

PB - Springer

T2 - 26th International Conference on Computing and Combinatorics, COCOON 2020

Y2 - 29 August 2020 through 31 August 2020

ER -