An exact algorithm for the asymmetrical capacitated vehicle routing problem

作者：Gilbert Laporte, Hélène Mercure, Yves Nobert · 发表于：Networks · 年份：1986 · DOI：10.1002/net.3230160104 · 被引用次数：161 · 研究领域：Vehicle Routing Optimization Methods、Optimization and Packing Problems、Urban and Freight Transport Logistics

Abstract The aim of this article is to develop an exact algorithm for the asymmetrical capacitated vehicle routing problem, i. e., the multiple traveling salesman problem subject to capacity restrictions. The problem is solved by means of a branch and bound tree in which subproblems are modified assignment problems subject to some restrictions. Two branching rules and three partitioning rules are examined. Computational results for problems involving up to 260 nodes (cities) are reported.