Noorizadegan, Mahdi (2013) On vehicle routing with uncertain demands. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Noorizadegan_2013.pdf - Submitted Version - Requires a PDF viewer. Download (1068Kb) | Preview

Request Changes to record.

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 or Dissertation (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:	Date Event November 2013 Submitted
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