Improving the approximation ratio for capacitated vehicle routing

• 成果类型: Article
• 署名作者: Blauth, Jannis; Traub, Vera; Vygen, Jens
• 署名单位: University of Bonn; University of Bonn; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01841-4
• 发表日期: 2023
• 页码: 451-497
• 关键词: heuristics; bounds

摘要

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527-542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149-158, 1987).