TY - BOOK

T1 - Vehicle routing on real road networks

AU - Dehghan Nasiri, Saeideh

PY - 2014/11/18

Y1 - 2014/11/18

N2 - The vehicle routing problem (VRP) has received particular attention, in the field of transportation and logistics. Producing good solutions for the problem is of interest both commercially and theoretically. Reliable solutions to real life applications require an approach based on realistic assumptions that resemble real-world conditions. In that respects, this thesis studies vehicle routing problems on real road networks addressing aspects of the problem that need to be modelled on the original road network graph and aims to provide appropriate modelling techniques for solving them.As a preliminary step, chapter 2 studies the travelling salesman problem (TSP)on real road networks, referred to as the Steiner TSP (STSP) and proposes alternative integer programming formulations for the problem and some other related routing problems. The performances of formulations is examined both theoretically and computationally. Chapter 3 highlights the fact that travel speeds on road networks are correlated and uses a real traffic dataset to explore the structure of this correlation. In conclusion, it is shown that there is still significant spatial correlations between speeds on roads that are up to twenty links apart, in our congested road network.Chapter 4 extends chapter 2 and incorporates the findings of chapter 3 intoa modelling framework for VRP. The STSP with correlated costs is defined asa potentially useful variant of VRP that considers the costs in the STSP to bestochastic random variables with correlation. The problem is then formulated asa single-objective problem with eight different integer programming formulations presented. It is then shown how to account for three different correlation structures in each of the formulations.Chapter 5 considers the VRPs with time windows and shows how most of theexact algorithms proposed for them, might not be applicable if the problem isdefined on the original road network graph due to the underlying assumption ofthese algorithms that the cheapest path between a pair of customers is the sameas the quickest path. This assumption is not always true on a real road network.Instead some alternative pricing routines are proposed that can solve the problem directly on the original graph.

AB - The vehicle routing problem (VRP) has received particular attention, in the field of transportation and logistics. Producing good solutions for the problem is of interest both commercially and theoretically. Reliable solutions to real life applications require an approach based on realistic assumptions that resemble real-world conditions. In that respects, this thesis studies vehicle routing problems on real road networks addressing aspects of the problem that need to be modelled on the original road network graph and aims to provide appropriate modelling techniques for solving them.As a preliminary step, chapter 2 studies the travelling salesman problem (TSP)on real road networks, referred to as the Steiner TSP (STSP) and proposes alternative integer programming formulations for the problem and some other related routing problems. The performances of formulations is examined both theoretically and computationally. Chapter 3 highlights the fact that travel speeds on road networks are correlated and uses a real traffic dataset to explore the structure of this correlation. In conclusion, it is shown that there is still significant spatial correlations between speeds on roads that are up to twenty links apart, in our congested road network.Chapter 4 extends chapter 2 and incorporates the findings of chapter 3 intoa modelling framework for VRP. The STSP with correlated costs is defined asa potentially useful variant of VRP that considers the costs in the STSP to bestochastic random variables with correlation. The problem is then formulated asa single-objective problem with eight different integer programming formulations presented. It is then shown how to account for three different correlation structures in each of the formulations.Chapter 5 considers the VRPs with time windows and shows how most of theexact algorithms proposed for them, might not be applicable if the problem isdefined on the original road network graph due to the underlying assumption ofthese algorithms that the cheapest path between a pair of customers is the sameas the quickest path. This assumption is not always true on a real road network.Instead some alternative pricing routines are proposed that can solve the problem directly on the original graph.

M3 - Doctoral Thesis

PB - Lancaster University

CY - Lancaster

ER -