The Library
On vehicle routing with uncertain demands
Tools
Noorizadegan, Mahdi (2013) On vehicle routing with uncertain demands. PhD thesis, University of Warwick.
|
PDF
WRAP_THESIS_Noorizadegan_2013.pdf - Submitted Version - Requires a PDF viewer. Download (1068Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2722986~S1
Abstract
In this research, we present a theoretical and computational framework for
studying the vehicle routing problem with uncertain demands (VRPUD). We combine
approaches in stochastic optimization and techniques in mixed integer programming
to solve two main variants of the vehicle routing problem with uncertain
demands.
We first present a polyhedral study for deterministic heterogenous vehicle
routing problems (HVRP) to develop a relatively efficient formulation such that its
corresponding counterpart with uncertainty is tractable via mixed integer programming.
Having assumed customers’ demand is uncertain, we apply three single-stage
approaches within stochastic optimization to the HVRP with uncertain demands.
The three-single stage approaches are chance constrained programming, Ben-Tal and
Nemirovski, and Bertsimas and Sim robust optimization approaches. Then, we plug
the corresponding formulation for each approach into a branch-and-cut method.
Moreover, we propose a new framework within the branch-and-price framework
to formulate the capacitated vehicle routing problem (CVRP) with uncertain
demands. In addition to the three single-stage approaches, we apply a two-stage
stochastic approach to the capacitated vehicle routing problem with uncertain demands.
Our proposed framework enables us to model di↵erent types of uncertainty
while the complexity of the resulting problem remains the same.
Finally, we present extensive computational experiments for the deterministic
HVRP, the HVRP with uncertain demands and the CVRP with uncertain demands.
In the computational experiments we first investigate efficiency of several types of
valid inequalities and lifting techniques for the deterministic HVRP. Then, using
simulation and a scenario based technique we assess the performance, advantages
and disadvantages of the aforementioned stochastic optimization approaches for the HVRP with uncertain demands and the CVRP with uncertain demands. We show
that among single-stage approaches of stochastic optimization, those with control
parameters outperform those without control parameters in terms of total expected
cost. Also, we show that the higher protection level does not necessarily result
in better solutions as higher protection levels may impose unnecessary extra costs.
Moreover, as our computational experiments suggest, the two-stage models for the
CVRP dominate the single-stage approaches for all protection level scenarios.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HE Transportation and Communications Q Science > QA Mathematics |
||||
Library of Congress Subject Headings (LCSH): | Vehicle routing problem, Stochastic processes, Uncertainty (Information theory), Computational complexity, Mathematical optimization | ||||
Official Date: | November 2013 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Warwick Business School | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Chen, Bo, Dr.; Gulpinar, Nalan | ||||
Extent: | vi, 155 leaves. | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year