An exact algorithm for the asymmetrical capacitated vehicle routing problem

✍ Scribed by Gilbert Laporte; Hélène Mercure; Yves Nobert

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 619 KB
• Volume: 16
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230160104

✦ Synopsis

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.

*The authors are grateful to the Canadian Natural Sciences and Engineering Research Council (Grants A4747 and A5486) and to the Quebec Government (FCAC Grant 80EQ0428) for their financial support. Thanks are also due to Giorgia Carpaneto and Paolo Toth who made their TSP code [4] available to the authors and to an anonymous referee for his judicious comments.