United States Department of Transportation
i
Better delivery/pick up routes in the presence of uncertainty.
-
2007-08-01
[PDF-816.70 KB]
Details:
-
Creators:
-
Corporate Creators:
-
Subject/TRT Terms:
-
Publication/ Report Number:
-
Resource Type:
-
Geographical Coverage:
-
Corporate Publisher:
-
Abstract:We consider the Courier Delivery Problem, a variant of the Vehicle Routing Problem with
time windows in which customers appear probabilistically and their service times are uncertain.
We use scenario-based stochastic optimization with recourse for uncertainty in
customers and robust optimization for uncertainty in service times. Our proposed model
generates a master plan and daily schedules by maximizing the coverage of customers and
the similarity of routes in each scenario while minimizing the total time spent by the couriers
and the total earliness and lateness penalty. For the large scale problem instance, we develop
a two-phase insertion based approximate solution procedure, MADS, to balance these
different objectives. We provide simulation results and show that our heuristic improves the
similarity of routes and the lateness penalty at the expense of increased total time spent when
compared to a solution by independently scheduling each day. Our experimental results also
show improvements over a real-life solution.
-
Format:
-
Collection(s):
-
Main Document Checksum:
-
Download URL:
-
File Type:
