Premium
Two exact algorithms for the distance‐constrained vehicle routing problem
Author(s) -
Laporte Gilbert,
Desrochers Martin,
Nobert Yves
Publication year - 1984
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.3230140113
Subject(s) - branch and cut , vehicle routing problem , routing (electronic design automation) , branch and bound , constraint (computer aided design) , upper and lower bounds , integer programming , mathematical optimization , relaxation (psychology) , integer (computer science) , algorithm , cutting plane method , mathematics , exact solutions in general relativity , computer science , geometry , psychology , computer network , mathematical analysis , social psychology , programming language
This paper considers a version of the vehicle routing problem in which all vehicles are identical and where the distance travelled by any vehicle may not exceed a prespecified upper bound. The problem is first formulated as an integer program which is solved by means of a constraint relaxation procedure. Two exact algorithms are developed: one based on Gomory cutting planes and one on branch and bound. Numerical results are reported.