Research

Project Number:
03-01

Research Project:
A Novel Approach to Routing and Dispatching Trucks Based on Partial Information in a Dynamic Environment

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

Project Objective:
Congestion affects the trucking industry on three major service dimensions: travel time, reliability, and cost. Trucking is a commercial activity, and trucking operations are driven by the need to satisfy customer demands and the need to operate at the lowest possible cost (Meyer, 1996). This industry is highly competitive, with easy entry into almost any market, relatively little differentiation between operators and slim profit margins.

However, most of the developed techniques and models for planning, routing and scheduling in the trucking industry assume 'known' static data as their input. For instance, in the Vehicle Routing Problem (VRP) the customer demands, travel costs, and travel times are known in advance.In this case, the fundamental problem is to determine the optimal route that minimizes a certain objective such as fleet size and travel distance.The built-in assumption of these approaches is that there will be small deviations on the realization of the demand and travel times from the plan so that the pre-determined routes form a basis for either the pickup or delivery schedule.In the real world, however, operations in any traffic network contain a fairly high degree of uncertainties including variable waiting and travel times due to traffic congestion, arrival of new orders, and cancellation of existing orders.In a highly dynamic and stochastic environment, the pre-planned optimal routes are no longer of practical use.In this case, most of the research effort has focused on easy to control dispatching rules.The drawback with these techniques is that they do not make use of pre-planned and known information.

There is a gap in the routing literature for systems that operate between the two ends of the spectrum, which is the most realistic condition for trucking operations.Our research on partial route development will develop new theory and methodologies within an area that has received little attention.The research will benefit an industry that is vital to the economy.The trucking and package delivery industry has grown substantially in recent years.These companies are implementing new technologies for tracking and communication that will make real-time routing a reality.The project will impact this industry by developing techniques to support efficient routing of systems opportunity between the two ends of the spectrum.

Project Poster

Task Descriptions:
1. Evaluate and compare different policies for vehicle routing and dispatching in uncertain environments (6 months)
2. Develop partial routing algorithms (3 months)
3. Develop metrics to evaluate the uncertainties in networks and translate these uncertainties into the levels of route planning (2 months)
4. Combine and fully validate our algorithms in Task 2 and Task 3 (1 month)
5. Cooperate with the trucking industry (2 months)
6. Write the final report (1 month)

Milestones, Dates:
August 25, 2003 - August 24, 2004

Total Budget:
$90,000

Student Involvement:
One student @ 50% time for 12 months

Relationship to Other Research Projects:
Related to 99-27, 00-15, and 03-07

Technology Transfer Activities:
Project report posted on the website

Potential Benefits of the Project:
More efficient vehicle routing, reduced truck traffic

TRB Keywords:
Vehicle routing, dynamic modeling

Primary Subject:
Transportation and logistics

Goals:
Economic growth and trade

Enabling Research:
Tools for modeling and design

Modal Orientation:
Highway