An exact algorithm for the asymmetrical capacitated vehicle routing problem
- 1 March 1986
- Vol. 16 (1) , 33-46
- https://doi.org/10.1002/net.3230160104
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.Keywords
This publication has 14 references indexed in Scilit:
- Two exact algorithms for the distance‐constrained vehicle routing problemNetworks, 1984
- A branch and bound algorithm for the capacitated vehicle routing problemOR Spectrum, 1983
- A restricted Lagrangean approach to the traveling salesman problemMathematical Programming, 1981
- Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxationsMathematical Programming, 1981
- State‐space relaxation procedures for the computation of bounds to routing problemsNetworks, 1981
- A Cutting Planes Algorithm for the m-Salesmen ProblemJournal of the Operational Research Society, 1980
- Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman ProblemManagement Science, 1980
- On the symmetric travelling salesman problem: A computational studyPublished by Springer Nature ,1980
- Scheduling of Vehicles from a Central Depot to a Number of Delivery PointsOperations Research, 1964
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962