Capacitated Vehicle Routing with Nonuniform Speeds

• 成果类型: Article
• 署名作者: Gortz, Inge Li; Molinaro, Marco; Nagarajan, Viswanath; Ravi, R.
• 署名单位: Technical University of Denmark; University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan; Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0729
• 发表日期: 2016
• 页码: 318-331
• 关键词: approximation algorithms; delivery problems; heuristics; minimum; bounds

摘要

The capacitated vehicle routing problem (CVRP) involves distributing identical items from a depot to a set of demand locations using a single capacitated vehicle. We introduce the heterogeneous capacitated vehicle routing problem, a generalization of CVRP to the setting of multiple vehicles having nonuniform speeds, and present for it a constant-factor approximation algorithm. Our main contribution is an approximation algorithm for the heterogeneous traveling salesman problem, which is the special case of heterogeneous CVRP with uncapacitated vehicles. Given a metric denoting distances between vertices, a depot r containing k vehicles having respective speeds {lambda(i)}(i=1)(k), the objective in heterogeneous TSP is to find a tour for each vehicle (starting and ending at r) so that every vertex is covered in some tour and the maximum completion time is minimized; the completion time of a vehicle is the distance traveled divided by its speed. Our algorithm relies on a new approximate minimum spanning tree construction called Level-Prim, which is related to but different from Light Approximate Shortest-path Trees. We also extend the widely used tour-splitting technique to nonuniform speeds, using ideas from the 2-approximation algorithm for scheduling in unrelated machines.