A start-time based tabu search approach for vehicle routing problem with time windows.

摘要

The Vehicle Routing Problem with Time Windows (VRPTW) deals with finding an optimal set of routes for a fleet of vehicles with given capacities, starting and ending their trips at a central depot while serving geographically dispersed customers with known demands in their respective time windows, and simultaneously minimizing the number of vehicles to be used. This problem is difficult to solve, which calls for the use of fast approximation or enumerative optimization [Gol88].; Simulated Annealing (SA) and Tabu Search (TS) are fairly recent heuristic methods for solving difficult optimization problems. This thesis aims to make a comparison between these two approaches. Gunn and MacAdam [Gun05] developed a simulated annealing (SA) approach to the VRPTW that uses a start time vector. This approach is an original idea. It also uses a simple neighborhood definition. In this thesis, a new Start-time Method Embedded Tabu Search (SMETS) approach is developed to solve VRPTW. This approach also uses a start time vector and a very simple neighborhood definition. The neighborhood definition is an original idea. This approach of finding neighboring solutions is deterministic and dynamic in nature.* (Abstract shortened by UMI.); *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation).