Tabu search heuristic for minimizing the number of vehicles in VRPTW

Project during masters in mathematics

Abstract:

This thesis discusses a tabu search algorithm variant for solving the vehicle routing problem with time windows (VRPTW). First, basic theory of heuristics and meta-heuristics are introduced. Thereafter the original algorithm used to solve bin packaging problems is discussed and adapted to the VRPTW setting.

The algorithm naturally focuses on the packaging dimension of the VRPTW and tries to empty selected vehicles thereby minimizing the number of vehicles in a solution. A key component of the algorithm is a so-called filling function trying to identify vehicles from which all customers are easy removeable. A tuning of the filling function is performed and compared to the original filling function from the bin packaging setting. The tuned version performs significantly better on the Solomon benchmark problems, but is still far from the best-known solutions.

The adaption of the algorithm seems promissing and suggestions for further research and areas of interest are provided.

Adviser Louise Kallehauge
Author Jerôme Baltzersen
Size 15 ECTS-points
Language English
Handed in January 29, 2010
Downloads PDF-file
  Jave-code
  Data (OpenOffice document)