论文标题
用于汽车共享问题的近似算法
Approximation algorithms for car-sharing problems
论文作者
论文摘要
我们考虑了出现汽车共享问题的几种变体。给定的是许多请求，每个请求包括一个拾取位置和下车位置，许多汽车以及不满意的对称旅行时间，可满足三角形不平等。每个请求都需要用汽车服务，这意味着汽车必须首先访问请求的接送位置，然后访问请求的下车位置。每辆车都可以提出两个请求。一个问题是在最短的总旅行时间（称为$ \ cs_ {sum} $）的情况下服务所有请求，而另一个问题是以最小总延迟（称为$ \ cs_ {lat} $）服务所有请求。我们还研究了请求的取货和下车位置一致的特殊情况。我们提出了两种基本算法，称为匹配并分配算法和传输算法。我们表明，由此产生的两个解决方案中最好的是$ 2 $ -Approximation，$ \ cs_ {sum} $（对于特殊情况而言，$ 7/5 $ -Approximation），以及$ 5/3 $ -AppRoximation for $ \ cs_ {lat} $（和3/2 $ -Approxoximation）的$ 5/3 $ -AppRoximation;这些比率优于单个算法的比率。最后，我们指出了如何将我们的算法应用于更通用的设置，在此设置中，每辆汽车都可以提供两个以上的请求，或者汽车具有不同速度。
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 $\CS_{sum}$), and the other problem is to serve all requests with the minimum total latency (called $\CS_{lat}$). 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 $\CS_{sum}$ (and a $7/5$-approximation for its special case), and a $5/3 $-approximation for $\CS_{lat}$ (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.
