Project number: MT-2-1a

Funding source: US DOT

Contract number: DTRT13-G-UTC57

Funding amount: $100,000

Performance period: 1/1/2014- 6/30/2015

Project description

The problem we study concerns routing a fleet of capacitated vehicles in real time to collect shipment orders placed by a known set of customers. On each day of operation, only a subset of all customers request service. Some of these requests are known at the beginning of the day, while the rest arrive dynamically during the day. It is not known when and from which customers these dynamic requests may come from. An example of such an application is the daily operation of a trucking company that consolidates shipments from multiple suppliers.

The objective of this dynamic vehicle routing problem (DVRP) is three fold: first, to minimize the impact (on total travel distance) of knowing only partial information; second, to maximize the flexibility of the existing routes in a dynamic environment; third, to provide fast responses to dynamic customer requests. Thus, we propose an optimization-based, look-ahead dynamic vehicle routing framework that periodically re-optimizes the current vehicle routes by using both the known and forecasted information. Heuristic algorithms are designed to construct an initial solution, improve the initial solution, and adjust the waiting time along the vehicle routes.

We perform simulation experiments on well-known benchmark problem instances in the literature. For each instance, we compare the quality of our solution with other routing strategies. We see that the look-ahead routing strategy with forecasting of future requests outperforms a routing strategy that only makes use of the known demand information, in terms of total travel distance for instances with relatively fewer advance requests and more dynamic requests. Thus the look-ahead dynamic routing strategy shows its merits for problems with high level of uncertainty. Overall our proposed approach could generate routing solutions that could reduce freight vehicle miles traveled, thus minimizing the impact of freight on passenger travel since they primarily share the same road network, especially in major urban centers like Los Angeles.