A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM WITH SOFT TIME WINDOWS

Citation
E. Taillard et al., A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM WITH SOFT TIME WINDOWS, Transportation science, 31(2), 1997, pp. 170-186
Citations number
17
Categorie Soggetti
Transportation,Transportation
Journal title
ISSN journal
00411655
Volume
31
Issue
2
Year of publication
1997
Pages
170 - 186
Database
ISI
SICI code
0041-1655(1997)31:2<170:ATSHFT>2.0.ZU;2-T
Abstract
This paper describes a tabu search heuristic for the vehicle routing p roblem with soft time windows. In this problem, lateness at customer l ocations is allowed although a penalty is incurred and added to the ob jective value. By adding large penalty values, the vehicle routing pro blem with hard time windows can be addressed as well. In the tabu sear ch, a neighborhood of the current solution is created through an excha nge procedure that swaps sequences of consecutive customers (or segmen ts) between two routes. The tabu search also exploits an adaptive memo ry that contains the routes of the best previously visited solutions. New starting points for the tabu search are produced through a combina tion of routes taken from different solutions found in this memory. Ma ny best-known solutions are reported on classical test problems.