Premium
Two exact algorithms for the vehicle routing problem on trees
Author(s) -
Mbaraga Pontien,
Langevin André,
Laporte Gilbert
Publication year - 1999
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199902)46:1<75::aid-nav5>3.0.co;2-i
Subject(s) - column generation , vehicle routing problem , computer science , bin packing problem , algorithm , heuristic , routing (electronic design automation) , computation , mathematical optimization , tree (set theory) , bin , mathematics , artificial intelligence , combinatorics , computer network
This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time‐constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The other uses column generation. The first algorithm performs better on problems containing small customer demands and in which all vehicles are identical. Otherwise, the second algorithm is more powerful and more versatile. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 75–89, 1999