|
|
|
In this research, we focus on vehicle routing and scheduling problems
for systems that face an uncertain operational environment. We propose both
new techniques for the analysis of such systems, and also simple (yet effective)
real-time operating strategies.
|
The Vehicle Routing Problem with Stochastic Demands and
Duration Constraints
to appear, Transportation Science , 2010.
(w/ J. Morales and M.W.P. Savelsbergh)
This paper studies the vehicle routing problem with stochastic demands,
focusing on vehicle tour duration constraints. In most stochastic
routing research, vehicle tour durations are ignored and thus
may lead to impractical plans that are not feasible to operate
in practice. This paper proposes an approach that preserves
vehicle duration feasibility for all scenarios in some
user-specified set of uncertain outcomes, and develops fast
methods for determining whether by this definition a vehicle
tour is robust. The ideas are used within a metaheuristic
search for good robust solutions.
|
|
Fixed Routes with Backup Vehicles for
Stochastic Vehicle Routing Problems with Time Constraints
Networks , 2009.
(w/ E. Uyar and M.W.P. Savelsbergh)
This paper studies vehicle routing problem with stochastic demands
that include hard time constraints, including customer time window
constraints. Traditional recourse policies developed for VRPSD
problems are not appropriate when customers have hard time windows,
or when vehicles have hard duration constraints, since recourse
strategies which require the vehicle to return to the depot to reload
are likely to be time infeasible in practice in these settings. We
propose an alternative strategy, where two vehicles are assigned a
priori to each customer and operational routes are constructed without
violating the a priori assignment. We show that this strategy
effectively hedges risk, and does not result in costs much worse than
a full reoptimization strategy.
|
|
A Paired-Vehicle Recourse Strategy for the Vehicle Routing Problem with Stochastic
Demands
Transportation Science, 2007.
(w/ A. Ak)
This paper develops a simple real-time operating strategy for the
load-constrained vehicle routing with uncertain demands, denoted the
paired locally-coordinated (PLC) strategy, where vehicles operate
in pairs to achieve risk pooling benefits. The paper provides
(1) the specification of a paired-vehicle strategy that requires minimal
coordination; (2) the development of a tabu search metaheuristic for
near-optimal configuration; and (3) a demonstration of the
cost-reduction potential of the PLC strategy, showing
operating cost reductions of 5% to 18% for large-scale problems.
|
|
A Dynamic Scheme for Stochastic Vehicle Routing
Technical Report, 2006.
(w/ C.F. Daganzo)
This paper develops an analyzes via continuous approximations
a vehicle-sharing strategy for stochastic vehicle routing
problems with uncertain customers and demands. Specifically,
the paper provides (1) the development of an operating strategy denoted
threshold global sharing (TGS) which jointly replans the full vehicle fleet
at a single decision epoch; (2) the development of an approximation approach
for determining a near-optimal configuration of a system operating
under the TGS scheme; and (3) a demonstration of the cost-reduction potential
of the TGS scheme by comparison to a traditional operating strategy,
showing using a set of representative test problems that reductions of 29%
to 82% in the fleet size penalty due to uncertainty and 15% to 45% in the
expected travel distance penalty are achievable.
|
|
On Planning and Design of Logistics Systems for Uncertain
Environments
in M.G. Speranza and P. Stahly, editors, New Trends in
Distribution Logistics, volume 480 of Lecture Notes in
Economics and Mathematical Systems, Springer-Verlag, 1999.
(w/ C.F. Daganzo)
This paper proposes a systematic approach for the design and control
of stochastic logistics problems, focusing on the key importance of
determining simple yet effective real-time control policies. Since
many effective control policies lead to intractable stochastic
optimization problems, the paper proposes to use approximation
approaches to configure system designs. Examples are provided for
simple location-allocation problems and stochastic vehicle routing
with uncertain customer demand.
|
|
|
|
