Hide/Show Apps

An algorithm for the capacitated vehicle routing problem with time windows

Download
2005
Pehlivanoğlu, Osman
In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)̕s and Homberger and Gehring (1999)̕s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.