Improved Approximations for a CVRP with Unsplittable Demands

• 成果类型: Article; Early Access
• 署名作者: Friggstad, Zachary; Mousavi, Ramin; Rahgoshay, Mirmahdi; Salavatipour, Mohammad R.
• 署名单位: University of Alberta
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2022.0097
• 发表日期: 2025-10-17
• 关键词: capacitated vehicle routing; Combinatorial Optimization; approximation algorithm; TRAVELING SALESMAN; heuristics; bounds; PTAS

摘要

In this paper, we present improved approximation algorithms for the (unsplitta-ble) capacitated vehicle routing problem (CVRP) in general metrics. In the CVRP, we are given a set of points (clients) V together with a depot r in a metric space, with each v is an element of V having a demand d(v) > 0 and a vehicle of bounded capacity Q. The goal is to find a mini-mum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once and the total demands of the clients in each tour are at most Q. In the unsplittable variant we study, the demand of a node must be served entirely by one tour. We present two approximation algorithms for the unsplittable CVRP: a combinatorial (alpha+1:7 5)-approximation, where alpha is the approximation factor for the trav-eling salesman problem, and an approximation algorithm based on linear programming rounding with approximation guarantee alpha+ln(2) +delta approximate to 3:1 94+delta in n(O(1=delta))time.