Jean-Yves Potvin

Université de Montréal. Centre de recherche sur les transports

Tanguy Kervahut

Jean-Marc Rousseau

Centre for Research on Transportation (Montréal, Québec)

This paper describes a tabu search heuristic for the vehicle routing problem with time windows (VRPTW). The tabu search incorporates an exchange heuristic which is specifically designed for problems with time windows. Computational results on the standard set of problems of Solomon are included at the end of the paper.

A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows

Michel Gendreau

Patrick Soriano

Tabu search is a relatively new general heuristic framework successfully applied to a wide variety of hard combinatorial optimization points. In two previous projects, three variants of this approach were developed for the unweighted maximum clique problem, two deterministic ones and a probabilistic one. These algorithms were extensively tested on randomly-generated problems and were found to be very effective in that context. This paper evaluates the performance of these algorithms on the benchmark instances of the second DIMACS Challenge that, along with the results reported previously, will provide a fairly precise assessment of the merits of the heuristics.

Tabu Search Algorithms for the Maximum Clique Problem

Computer Scheduling of Public Transport 2

Université de Montréal. Centre de recherche sur les transports

About

Books

Join the club