14th December 2009 10:30 a.m. Room 3041, Building 2, Highfield Campus
CORMSIS Seminars: An Iterated Tabu Search Heuristic for Vehicle Routing Problems
Professor Jean-Francois Cordeau
Department of Logistics and Operations Management, University of Montreal
- Web page
- http://www.cormsis.soton.ac.uk/seminars/default.php
- Submitter
- Deborah Guy
Prof Jean-Francois Cordeau
This talk will introduce a new iterated tabu search heuristic for the Vehicle Routing Problem (VRP) and three variants: the Multi-Depot VRP (MDVRP), the Period VRP (PVRP), and the Site-Dependent VRP (SDVRP). Iterated Local Search (ILS) is a simple meta-heuristic paradigm that was introduced by Lourenço, Martin and Stützle (2002) for general combinatorial optimization problems. In ILS, the search iterates between diversification and intensification steps. In each cycle, diversification is first performed by perturbing the incumbent solution through some (randomized) transformation. Intensification is then performed around the perturbed solution by applying a local search heuristic that yields a local minimum. In our Iterated Tabu Search (ITS) heuristic for vehicle routing problems, we replace the local search heuristic used in the intensification step with an existing tabu search heuristic. Given the same amount of CPU time, the new ITS heuristic clearly outperforms the original tabu search and is competitive with recent heuristics for the MDVRP, PVRP and SDVRP. The result is a simple heuristic that strikes a good balance between accuracy, speed and flexibility. The approach can also be adapted to address the VRP with time windows and other related problem variants.