Capacitated vehicle routing problem with time windows

Özaydın, Ekim (2003) Capacitated vehicle routing problem with time windows. [Thesis]

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://risc01.sabanciuniv.edu/record=b1163464 (Table of Contents)


Vehicle Routing Problem with Time Windows (VRPTW) is an extension of the Capacitated Vehicle Routing Problem. The objective is to design optimal routes that satisfy all of the constraints. In this study, a linear IP model and hybrid heuristics for the VRPTW are proposed. The objective function considered in the model is the total distance traveled by all vehicles. Vehicles are identical, capacities of the vehicles are finite and the time window constraints are assumed to be strict. The proposed hybrid heuristics are combined by two parts. The first part, which has both parallel and sequential versions, finds an initial solution. Both parallel and sequential initial solution algorithms are based on the idea of clustering the customers while doing the insertion. Second part is an improvement heuristic, which is a combination of three procedures: Inter-route exchanges, inter-route moves and intra-route exchanges. In the proposed heuristics, these operators are used nested with each other. There are two improvement heuristics proposed that use these operators in different ways. The improvement algorithms are supported with a restart mechanism called diversification in order to escape the local optima and widen the search space. In this study, two diversification methods are proposed. The hybrid algorithms in this study are the combinations of the initial solution, improvement and diversification methods proposed. The algorithms have been tested on the 56 benchmark problem instances of Solomon (1987), which were used widely in the literature. The hybrid algorithms are proven to give better results when compared to not only some known metaheuristics, but also to the best known results in the literature.

Item Type:Thesis
Uncontrolled Keywords:Vehicle routing problem with time windows. -- Heuristics. -- Combinatorial optimization. -- Metaheuristics. -- Zaman kısıtlı araç rotalama problemi. -- Sezgisel algoritmalar. -- Kombinatoryal optimizasyon. -- Sezgisel-ötesi algoritmalar
Subjects:T Technology > T Technology (General)
ID Code:8533
Deposited By:IC-Cataloging
Deposited On:23 May 2008 09:52
Last Modified:25 Dec 2008 13:11

Repository Staff Only: item control page