Network-consistent travel times can help vehicle routing algorithms avoid traffic jams

traffic-jam

Time-dependent vehicle routing is all about avoiding traffic jams by taking into account recurring congestion on our roads, and essentially “routing around” it. For researchers to be able to develop effective time-dependent vehicle routing algorithms, realistic time dependent data sets are necessary. A recent paper by Christophe Lecluyse, Kenneth Sörensen, and
Herbert Peremans shows how this can be done.

  • C. Lecluyse, K. Sörensen, and H. Peremans, "A network-consistent time-dependent travel time layer for routing optimization problems," European journal of operational research, vol. 226, iss. 3, pp. 395-413, 2013.
    [PDF] [DOI] [Bibtex]
    @article{lecluyse2013network,
    title = {A network-consistent time-dependent travel time layer for routing optimization problems},
    author = {Lecluyse, Christophe and Sörensen, Kenneth and Peremans, Herbert},
    journal = {European Journal of Operational Research},
    volume = {226},
    number = {3},
    pages = {395--413},
    year = {2013},
    doi = {10.1016/j.ejor.2012.11.043},
    publisher = {Elsevier},
    keywords = {vehicle routing problem},
    }

Traffic jams are everywhere, and recent technology allows us to predict and (at least sometimes) avoid them. Vehicle routing algorithms, however, determine a routing plan some time in advance (e.g., the night before). Because of appointments made with customers or for other reasons, these routing plans should not change too much during the day. Most traffic jams, however, are recurring, i.e., they appear around the same time and same location every day. These traffic jams can (in principle) be taken into account by vehicle routing algorithms.

To develop such vehicle routing algorithms, researchers need artificially generated data sets. These data sets consist of customer information (location of the customers, demand of the customers, time windows, etc.) and travel information (i.e., travel times between pairs of customers).time_paper

Time-dependent data sets have an extra dimension, as the model the travel time between two customers not as a constant, but as a function of time. Currently, however, such data sets have lacked a property that we have called “network consistent”. In reality, traffic jams on different roads are not independent, but correlated in both space and time. Typically, congestion starts at a certain location and at a certain time and then gradually expands (like an expanding circle) to neighboring roads. After the congestion peak, the congestion area shrinks again until free-flow conditions are restored.

Creating time-dependent data sets with this property proved to be a challenge, but the result is an elegant method that can be used by researchers for any kind of vehicle routing problem. You can try out the (free) Java software to generate the data sets.

Network-consistent travel times can help vehicle routing algorithms avoid traffic jams