Capacitated Vehicle Routing with Non-Uniform Speeds
Capacitated Vehicle Routing with Non-Uniform Speeds
复制标题
DOI：
10.1007/978-3-642-20807-2_19
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
Inge Li Gørtz;M. Molinaro;V. Nagarajan;R. Ravi
中科院分区：
文献类型：
--
作者：
Inge Li Gørtz;M. Molinaro;V. Nagarajan;R. Ravi
Thecapacitated vehicle routing problem(CVRP) [21] involves distributing (identical) items from a depot to a set of demand locations in the shortest possible time, using a single capacitated vehicle. We study a generalization of this problem to the setting of multiple vehicles having non-uniform speeds (that we callHeterogenous CVRP), and present a constant-factor approximation algorithm.The technical heart of our result lies in achieving a constant approximation to the following TSP variant (calledHeterogenous TSP). Given a metric denoting distances between vertices, a depotrcontainingkvehicles having speeds {λi}i= 1k, the goal is to find a tour for each vehicle (starting and ending atr), so that every vertex is covered in some tour and the maximum completion time is minimized. This problem is precisely Heterogenous CVRP when vehicles are uncapacitated.The presence of non-uniform speeds introduces difficulties for employing standard tour-splitting techniques. In order to get a better understanding of this technique in our context, we appeal to ideas from the 2-approximation for minimum makespan scheduling in unrelated parallel machines of Lenstra et al. [19]. This motivates the introduction of a new approximate MST construction calledLevel-Prim, which is related toLight Approximate Shortest-path Trees[18]. The last component of our algorithm involves partitioning the Level-Prim tree and matching the resulting parts to vehicles. This decomposition is more subtle than usual since now we need to enforce correlation between the lengths of the parts and their distances to the depot.
