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.