Article ID: | iaor20011058 |
Country: | Netherlands |
Volume: | 123 |
Issue: | 2 |
Start Page Number: | 408 |
End Page Number: | 427 |
Publication Date: | Jun 2000 |
Journal: | European Journal of Operational Research |
Authors: | Nemhauser G.L., Boland N.L., Clarke L.W. |
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.