IDEAS home Printed from
   My bibliography  Save this article

Dynamic routing for milk-run tours with time windows in stochastic time-dependent networks


  • Güner, Ali R.
  • Murat, Alper
  • Chinnam, Ratna Babu


We consider finding static yet robust recurring milk-run tours while dynamically routing the vehicle between site visits. The network arcs experience recurrent congestion, leading to stochastic and time-dependent travel times. Based on vehicle location, time of day, and current and projected network congestion states, we generate dynamic routing policies (DRP) for every pair of sites using stochastic dynamic programming (SDP). By simulating DRP we find travel time distributions for each pair of sites which is used to build the robust tour using another SDP formulation. Results are very promising when the algorithms are tested in a simulated network using historical traffic data.

Suggested Citation

  • Güner, Ali R. & Murat, Alper & Chinnam, Ratna Babu, 2017. "Dynamic routing for milk-run tours with time windows in stochastic time-dependent networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 251-267.
  • Handle: RePEc:eee:transe:v:97:y:2017:i:c:p:251-267
    DOI: 10.1016/j.tre.2016.10.014

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Golob, Thomas F. & Regan, A C, 2003. "Traffic Congestion and Trucking Managers' Use of Automated Routing and Scheduling," University of California Transportation Center, Working Papers qt74z234n4, University of California Transportation Center.
    3. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    4. Irnich, S. & Schneider, M. & Vigo, D., 2014. "Four Variants of the Vehicle Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63514, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    6. Golob, Thomas F. & Regan, Amelia C., 2003. "Traffic congestion and trucking managers' use of automated routing and scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 39(1), pages 61-78, January.
    7. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    8. Keng Hoo Chuah & Jon C. Yingling, 2005. "Routing for a Just-in-Time Supply Pickup and Delivery System," Transportation Science, INFORMS, vol. 39(3), pages 328-339, August.
    9. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    10. Figliozzi, Miguel Andres, 2010. "The impacts of congestion on commercial vehicle tour characteristics and costs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(4), pages 496-506, July.
    11. Chang, Tsung-Sheng & Wan, Yat-wah & OOI, Wei Tsang, 2009. "A stochastic dynamic traveling salesman problem with hard time windows," European Journal of Operational Research, Elsevier, vol. 198(3), pages 748-759, November.
    Full references (including those not matched with items on IDEAS)


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:97:y:2017:i:c:p:251-267. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.