An algorithm for the capacitated vehicle routing problem with time windows

Download

index.pdf

Date

2005

Author

Pehlivanoğlu, Osman

Metadata

Show full item record

Item Usage Stats

376
views

105
downloads

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.

Subject Keywords

Transportation engineering.

URI

http://etd.lib.metu.edu.tr/upload/2/12606657/index.pdf
https://hdl.handle.net/11511/15569

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A column generation approach for the location-routing problem with time windows Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem (2018-02-01) The location-routing problem with time windows consists of opening a subset of depots, assigning customers to depots, and determining routes within allowable times such that the sum of depot opening, vehicle usage, and traveling costs is minimized. Customers have to be visited only once during their time windows and depot capacities and load limits of vehicles cannot be violated. In order to find the exact solution to the problem, we propose a branch-and-price algorithm based on set-partitioning approach. T...
An adaptive simulated annealing algorithm-based approach for assembly line balancing and a real-life case study Guden, H.; Meral, Fatma Sedef (2016-05-01) In this study, we address the deterministic assembly line balancing problem (ALBP) in a multiple product-models environment with multiple objectives. We have been motivated by the assembly line balancing problem of a white goods product production line that is a multi-model type line with 68 stations through which four product-models are assembled, each with approximately 400 precedence relations and 300 tasks. In the plant, to cope with the increasing demand in the medium term, the efficiency of the line i...
A new method to measure vehicle pass-by noise in a finite dimensioned semi-anechoic room Arslan, Ersen; Çalışkan, Mehmet; Department of Mechanical Engineering (2010) In this study, a method to predict vehicle pass-by noise in a finite dimensioned, semi-anechoic chamber with chassis dynamometer has been developed. Vehicle noise has been modeled as the summation of the individual contributions regarding the principal noise components, namely, engine including air intake, front tire and rear tire noises. This method employs wave propagation, Doppler shift, and time delay in the estimation of the sound pressure due to each component at points of interest specified by releva...
A risk-sensitive approach for airline network revenue management problems Çetiner, Demet; Köksalan, Murat; Department of Industrial Engineering (2007) In this thesis, airline network revenue management problem is considered for the case with no cancellations and overbooking. In literature, there exist several approximate probabilistic and deterministic mathematical models developed in order to maximize expected revenue at the end of the reservation period. The aim of this study is to develop models considering also the risks involved in the proposed booking control policies. Two linear programming models are proposed which incorporate the variance of the ...
A Generic and extendable system architecture for intelligent transportation systems / Çetinkaya, Kaan; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2015) Intelligent Transportation Systems (ITS) are distributed systems with different communicating parties which are vehicles with ITS-supporting On Board Units (OBUs), Road Side Units (RSU) and user mobile devices. These parties collectively run application services that are developed and managed by different application service providers by communicating among each other under certain timing constraints. In the current state of art, hardware, software and communications that are required to implement a given I...

Citation Formats

O. Pehlivanoğlu, “An algorithm for the capacitated vehicle routing problem with time windows,” M.S. - Master of Science, Middle East Technical University, 2005.