Premium
Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs
Author(s) -
Mak V.,
Boland N.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00209.x
Subject(s) - mathematical optimization , travelling salesman problem , heuristic , subgradient method , simulated annealing , computer science , computation , mathematics , algorithm
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.