The asymmetric traveling salesman problem with replenishment arcs
- 1 June 2000
- journal article
- Published by Elsevier BV in European Journal of Operational Research
- Vol. 123 (2), 408-427
- https://doi.org/10.1016/s0377-2217(99)00266-0
Abstract
We consider a constrained asymmetric traveling salesman problem with knapsack-like constraints on subpaths of the tour. This problem arises in routing aircraft. We formulate the problem with an exponential number of variables that correspond to feasible subpaths. We study certain polyhedral aspects of the reformulation and present a branch-and-price-and-cut algorithm for solving it. We test the algorithm on both random instances and real instances that arise in the airline application.Keywords
This publication has 15 references indexed in Scilit:
- Chapter 2 Time constrained routing and schedulingPublished by Elsevier BV ,1995
- Solving binary cutting stock problems by column generation and branch-and-boundComputational Optimization and Applications, 1994
- MINTO, a mixed INTeger optimizerOperations Research Letters, 1994
- A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facetsMathematical Programming, 1993
- An analytical comparison of different formulations of the travelling salesman problemMathematical Programming, 1991
- Chapter II Linear programmingPublished by Elsevier BV ,1989
- A new approach for crew pairing problems by column generation with an application to air transportationEuropean Journal of Operational Research, 1988
- Algorithms for finding paths with multiple constraintsNetworks, 1984
- Lagrangean relaxation for integer programmingPublished by Springer Science and Business Media LLC ,1974
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965