Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs

Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.