Premium
An exact algorithm for the asymmetrical capacitated vehicle routing problem
Author(s) -
Laporte Gilbert,
Mercure Hélène,
Nobert Yves
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160104
Subject(s) - vehicle routing problem , travelling salesman problem , branch and bound , mathematical optimization , computer science , 2 opt , routing (electronic design automation) , branch and cut , tree (set theory) , branching (polymer chemistry) , algorithm , mathematics , integer programming , combinatorics , materials science , composite material , computer network
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.