Article ID: | iaor20012984 |
Country: | United Kingdom |
Volume: | 7 |
Issue: | 4/5 |
Start Page Number: | 431 |
End Page Number: | 447 |
Publication Date: | Jul 2000 |
Journal: | International Transactions in Operational Research |
Authors: | Boland Natashia, Mak Vicky |
The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problem arising from work related to aircraft routing. This paper describes the problem and presents heuristic approaches for solving the RATSP. We use simulated annealing to obtain feasible solutions, and hence, upper bounds on the optimum value, and solve a Lagrangean dual problem using a subgradient optimization method to obtain lower bounds. While previous methods failed to obtain optimal solutions to some problem classes after 2 h of computation time, with average gaps ranging from 15% to 30%, our heuristic approaches take only 15–20 min to obtain feasible solutions, with gaps of less than 3%. We give computational results comparing these approaches.