Journal article

The asymmetric traveling salesman problem with replenishment arcs

NL Boland, LW Clarke, GL Nemhauser

European Journal of Operational Research | Published : 2000


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. © 2000 Elsevier Science B.V. All rights reserved.

University of Melbourne Researchers

Citation metrics