A New Heuristic for the Traveling Salesman Problem with Time Windows

Roberto Wolfler Calvo
Additional contact information
Roberto Wolfler Calvo: Istitute for Systems Informations and Safety, Joint Research Centre, European Commision, via E. Fermi, 21020 Ispra, and Politecnico di Milano–Dipartimento di Elettronica e Informazione, Piazza Leonardo da Vinci, 32, 20133 Milano, Italy

Transportation Science, 2000, vol. 34, issue 1, 113-124

Abstract: The aim of this paper is to present a new heuristic method for the Traveling Salesman Problem with Time Windows, based on the solution of an auxiliary problem. The idea is to solve an assignment problem with an ad hoc objective function to obtain a solution close enough to a feasible solution of the original problem. Given this solution, made by a long main tour containing the depot and few small subtours, it is easy to insert all the subtours into the main path using a greedy insertion procedure. The algorithm described applies the proposed constructive scheme and then uses a local search procedure to improve the initial solution. The computational results show the effectiveness of this approach.

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.34.1.113.12284 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:34:y:2000:i:1:p:113-124

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().