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.

Suggestions

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...
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...
A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements
Ogan, Dilek; Azizoğlu, Meral (2015-07-01)
In this study we consider a U-shaped assembly line balancing problem where each task uses a specified set of equipments and each type of equipment has a specified cost. Our problem is to assign the tasks together with their equipments to the workstations so as to minimize the total equipment cost. We formulate the problem as a mixed integer linear programming model that is capable of solving small sized instances. We propose a branch and bound algorithm that uses efficient precedence relations and lower bou...
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.