An algorithm for the capacitated vehicle routing problem with time windows


Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 2005

Thesis Language: English

Student: Osman Pehlivanoğlu

Supervisor: FATMA SEDEF MERAL

Abstract:

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.