Research

Project Number:
06-11

Research Project:
Better Delivery/Pick Up in the Presence of Uncertainty

P.I. Name & Address:
Fernando Ordonez
Department of Industrial and Systems Engineering
University of Southern California
Los Angeles, CA  90089-0193
Tel:  (213) 821-2413
Fax:  (213)740-1120
Email:  fordon@usc.edu

Co-P.I.s:
Maged Dessouky
Department of Industrial and Systems Engineering
University of Southern California
Los Angeles, CA  90089-0193
Tel.  (213) 740-4891
Fax:  740-1120
Email:  maged@usc.edu

Project Objective:
Many industrial applications deal with the problem of routing a fleet of vehicles from a depot to service a set of customers that are geographically dispersed.    This type of problem is faced daily by courier services, local trucking companies, and demand responsive transportation services, just to name a few.  However, congestion and variability in demand and travel times affects these industries on three major service dimensions: travel time, reliability, and cost (Meyer 1996). Therefore, there is a need to develop routing and scheduling tools that directly account for the uncertainty in demand and varying congestion in the road network for this vital industry.  Identifying the most efficient routing strategies in practice for problems that face uncertainty can produce significant cost savings in operations for the industry.

Current methods to address the uncertainty in routing problems, such as stochastic programming or probabilistic analysis can have one (or all) of the following drawbacks: 1) strong assumptions of the uncertainty such as a known distribution and moments, 2) representation of uncertainty via discrete scenarios which can lead to excessive problem size and computational burden, and 3) the solution obtained can be sensitive to the uncertainty considered.  These potential drawbacks are addressed by a new methodology that aims at a robust routing solution, where by robust solution we mean the solution which has the best worst case uncertainty.  Although such a robust solution is potentially attractive, there is no study to date that identifies which routing solution is best in practice for an applied problem.

We propose to study routing solutions for an applied industry problem in detail.  This research will shed light into problem conditions that make a certain routing solution preferable over another, and provide a quantitative approach to identify the best routing strategy in applied problems.   The research is broken down into the following steps:  1) from real industry data (see letter of support from United Parcel Service), we plan to construct representative uncertainty models; 2) determine routing solutions that consider this uncertainty (stochastic programming, probabilistic analysis, robust optimization, best practices); 3) introduce benchmarking metrics of interest to compare the performance of these solutions.  Metrics can include expected total travel time and its standard deviation, percent of catastrophic responses, adaptability of solution to unexpected changes, and others.

Task Descriptions:
1. Data collection and analysis
2. Construction of representative problem instances
3. Computation of different routing solutions
4. Comparison of different routing solutions
5. Preparation of final report

Milestones, Dates:
February 15, 2006 - February 14, 2007

Total Budget:
$85,000

Student Involvement:
One Student @ 50% effort, 12 months

Relationship to Other Research Projects:
Related to 03-07, 03-18, 03-01, part of goods movement and international trade focus area

Technology Transfer Activities:
Project report posted on the website

Potential Benefits of the Project:
More efficient goods movement; reduced truck traffic

TRB Keywords:
Freight routing

Primary Subject:
4b.2 Transportation and logistics system operations and management

Goals:
4c.3 Economic growth and trade

Enabling Research:
4c.11 Tools for modeling and design

Modal Orientation:
4c.13 Highway