Freight Distribution Problems in Congested Urban Areas: Fast and Effective Solution Procedures to Time-Dependent Vehicle Routing Problems

Miguel Figliozzi, Portland State University

This is a final report, OTREC-RR-11-05, from the NITC program of TREC at Portland State University, and can be found online at:


Congestion is a common phenomenon in all medium to large cities of the world. Reliability of freight movement in urban areas is an important issue to manufacturing or service companies whose operation is based in just-in-time approaches. These companies tend to provide high value or time sensitive products/services. As congestion increases, carriers face increasing challenges to satisfy their time sensitive customers in an economical way. Route designs or schedules which require long computation times or ignore travel time variations will result in inefficient and suboptimal solutions. Poorly designed routes that lead freight vehicles into congested arteries and streets not only increases supply chain and logistics costs but also exacerbate externalities associated with freight traffic in urban areas such as greenhouse gases, air pollution, noise, and accidents.

Whilst it is rarely possible to entirely avoid the impacts of congestion, it is feasible to schedule operations so that the effects of congestion are minimized. Better scheduling can be effectively supported by the advent of inexpensive and ubiquitous Information and Communication Technologies (ICT). The use of mobile phone technology and on-board routing devices allows fluid communication between truck drivers and fleet operators in real-time. In such a real time operation it becomes possible to dynamically reassign vehicles, including modifying the order in which customers are served and diverting a vehicle already en-route to service another customer. However, without fast routing methods that can take advantage of real time congestion information carriers cannot reap the benefits of real-time information.

From the operational point of view, congestion creates a substantial variation in travel times during peak morning and evening hours. This is problematic for all vehicle routing models which rely on a constant value to represent vehicle speeds. And while the ubiquitous availability of real time traffic information allows drivers to reactively alter routes and customer service sequences to better cope with congestion, static routing models are unable to take advantage of these advances in real-time information provision in order to proactively find adequate routing solutions. In addition, changes in travel time caused by congestion cannot be accurately represented in static models.

Research in time-dependent vehicle routing problem is comparatively meager and current solution methods are inadequate for practical carrier operations which need to provide fast solutions for medium to large instances. Even faster solution methods are essential to take advantage of real time information. The major aim of this proposal is to develop and evaluate new methods for vehicle routing in congested urban areas. The emphasis will be placed on improving the running time of the existing methods.