A generic exact solver for vehicle routing and related problems

• 成果类型: Article
• 署名作者: Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo; Vanderbeck, Francois
• 署名单位: Universidade Federal Fluminense
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01523-z
• 发表日期: 2020
• 页码: 483-523
• 关键词: cut-and-price; exact algorithm; Lower bounds; delivery problem; rank-1 cuts; tabu search; bin-packing; branch; inequalities; pickup

摘要

Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best existing VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, path enumeration, and rounded capacity cuts; all generalized through the new concepts of packing set and elementarity set. The concepts are also used to derive a branching rule based on accumulated resource consumption and to generalize the Ryan and Foster branching rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.