IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v255y2016i3p699-718.html
   My bibliography  Save this article

Solving the stochastic time-dependent orienteering problem with time windows

Author

Listed:
  • Verbeeck, C.
  • Vansteenwegen, P.
  • Aghezzaf, E.-H.

Abstract

This paper introduces the stochastic time-dependent orienteering problem with time windows. The orienteering problem occurs in logistic situations where an optimal combination of locations must first be selected and then the routing between these selected locations must be optimized. In the stochastic time-dependent variant, the travel time between two locations is a stochastic function that depends on the departure time at the first location. The main contribution of this paper lies in the design of a fast and effective algorithm to solve this challenging problem. To validate the performance and the practical relevance of this proposed algorithm, several experiments were carried out on realistic benchmark instances of varying size and properties. These benchmark instances are constructed based on an actual large road network in Belgium with historic travel time profiles for every road segment.

Suggested Citation

  • Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    • Handle: RePEc:eee:ejores:v:255:y:2016:i:3:p:699-718
    DOI: 10.1016/j.ejor.2016.05.031
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171630368X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.05.031?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. Evers, Lanah & Barros, Ana Isabel & Monsuur, Herman & Wagelmans, Albert, 2014. "Online stochastic UAV mission planning with time windows and time-sensitive targets," European Journal of Operational Research, Elsevier, vol. 238(1), pages 348-362.
    2. Yildirimoglu, Mehmet & Geroliminis, Nikolas, 2013. "Experienced travel time prediction for congested freeways," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 45-63.
    3. Souffriau, Wouter & Vansteenwegen, Pieter & Vanden Berghe, Greet & Van Oudheusden, Dirk, 2011. "The planning of cycle trips in the province of East Flanders," Omega, Elsevier, vol. 39(2), pages 209-213, April.
    4. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    5. Y. Y. Fan & R. E. Kalaba & J. E. Moore, 2005. "Arriving on Time," Journal of Optimization Theory and Applications, Springer, vol. 127(3), pages 497-513, December.
    6. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    7. Lanah Evers & Twan Dollevoet & Ana Barros & Herman Monsuur, 2014. "Robust UAV mission planning," Annals of Operations Research, Springer, vol. 222(1), pages 293-315, November.
    8. Jeffrey P. Kharoufeh & Natarajan Gautam, 2004. "Deriving Link Travel-Time Distributions via Stochastic Speed Processes," Transportation Science, INFORMS, vol. 38(1), pages 97-106, February.
    9. Chao, I-Ming & Golden, Bruce L. & Wasil, Edward A., 1996. "A fast and effective heuristic for the orienteering problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 475-489, February.
    10. Evers, L. & Glorie, K.M. & van der Ster, S. & Barros, A.I. & Monsuur, H., 2012. "The Orienteering Problem under Uncertainty Stochastic Programming and Robust Optimization compared," Econometric Institute Research Papers EI 2012-21, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. Nguyen, Phuong Khanh & Crainic, Teodor Gabriel & Toulouse, Michel, 2013. "A tabu search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 231(1), pages 43-56.
    12. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    13. Bernhard Fleischmann & Martin Gietz & Stefan Gnutzmann, 2004. "Time-Varying Travel Times in Vehicle Routing," Transportation Science, INFORMS, vol. 38(2), pages 160-173, May.
    14. Fu, Liping & Rilett, L. R., 1998. "Expected shortest paths in dynamic and stochastic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(7), pages 499-516, September.
    15. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    16. El-Houssaine Aghezzaf & Yiqing Zhong & Birger Raa & Manel Mateo, 2012. "Analysis of the single-vehicle cyclic inventory routing problem," International Journal of Systems Science, Taylor & Francis Journals, vol. 43(11), pages 2040-2049.
    17. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    18. Donati, Alberto V. & Montemanni, Roberto & Casagrande, Norman & Rizzoli, Andrea E. & Gambardella, Luca M., 2008. "Time dependent vehicle routing problem with a multi ant colony system," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1174-1191, March.
    19. S. Y. Teng & H. L. Ong & H. C. Huang, 2004. "An Integer L-Shaped Algorithm For Time-Constrained Traveling Salesman Problem With Stochastic Travel And Service Times," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(02), pages 241-257.
    20. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    21. 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.
    22. Naoki Ando & Eiichi Taniguchi, 2006. "Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows," Networks and Spatial Economics, Springer, vol. 6(3), pages 293-311, September.
    23. Clark, Stephen & Watling, David, 2005. "Modelling network travel time reliability under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 39(2), pages 119-140, February.
    24. Lecluyse, Christophe & Sörensen, Kenneth & Peremans, Herbert, 2013. "A network-consistent time-dependent travel time layer for routing optimization problems," European Journal of Operational Research, Elsevier, vol. 226(3), pages 395-413.
    25. Zhang, Shu & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2014. "A priori orienteering with time windows and stochastic wait times at customers," European Journal of Operational Research, Elsevier, vol. 239(1), pages 70-79.
    26. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    27. Tao Zhang & W. Art Chaovalitwongse & Yuejie Zhang, 2014. "Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 288-309, July.
    28. Laoucine Kerbache & T. van Woensel & N. Vandaele & Herbert Peremans, 2008. "Vehicle routing with dynamic travel times: A queueing approach," Post-Print hal-00465127, HAL.
    29. Li, Xiangyong & Tian, Peng & Leung, Stephen C.H., 2010. "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, Elsevier, vol. 125(1), pages 137-145, May.
    30. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    31. Fu, Liping, 2002. "Scheduling dial-a-ride paratransit under time-varying, stochastic congestion," Transportation Research Part B: Methodological, Elsevier, vol. 36(6), pages 485-506, July.
    32. Pieter Vansteenwegen & Wouter Souffriau & Greet Vanden Berghe & Dirk Van Oudheusden, 2009. "Metaheuristics for Tourist Trip Planning," Lecture Notes in Economics and Mathematical Systems, in: Kenneth Sörensen & Marc Sevaux & Walter Habenicht & Martin Josef Geiger (ed.), Metaheuristics in the Service Industry, chapter 2, pages 15-31, Springer.
    33. Jan Fabian Ehmke, 2012. "Routing in City Logistics," International Series in Operations Research & Management Science, in: Integration of Information and Optimization Models for Routing in City Logistics, edition 127, chapter 0, pages 119-156, Springer.
    34. H Tang & E Miller-Hooks, 2005. "Algorithms for a stochastic selective travelling salesperson problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(4), pages 439-452, April.
    35. Chen, Huey-Kuo & Hsueh, Che-Fu & Chang, Mei-Shiang, 2006. "The real-time time-dependent vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 42(5), pages 383-408, September.
    36. Ann Campbell & Michel Gendreau & Barrett Thomas, 2011. "The orienteering problem with stochastic travel and service times," Annals of Operations Research, Springer, vol. 186(1), pages 61-81, June.
    37. Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.
    38. W Maden & R Eglese & D Black, 2010. "Vehicle routing and scheduling with time-varying data: A case study," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(3), pages 515-522, March.
    39. Robert B. Noland & John W. Polak, 2002. "Travel time variability: A review of theoretical and empirical issues," Transport Reviews, Taylor & Francis Journals, vol. 22(1), pages 39-54, January.
    40. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    41. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    2. Bijun Wang & Zheyong Bian & Mo Mansouri, 2023. "Self-adaptive heuristic algorithms for the dynamic and stochastic orienteering problem in autonomous transportation system," Journal of Heuristics, Springer, vol. 29(1), pages 77-137, February.
    3. Zhang, Shu & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2020. "Multi-period orienteering with uncertain adoption likelihood and waiting at customers," European Journal of Operational Research, Elsevier, vol. 282(1), pages 288-303.
    4. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    5. Qinxiao Yu & Chun Cheng & Ning Zhu, 2022. "Robust Team Orienteering Problem with Decreasing Profits," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3215-3233, November.
    6. Yang, Yu & Yan, Chiwei & Cao, Yufeng & Roberti, Roberto, 2023. "Planning robust drone-truck delivery routes under road traffic uncertainty," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1145-1160.
    7. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    2. Diego Cattaruzza & Nabil Absi & Dominique Feillet & Jesús González-Feliu, 2017. "Vehicle routing problems for city logistics," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 51-79, March.
    3. Cédric Verbeeck & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "The time-dependent orienteering problem with time windows: a fast ant colony system," Annals of Operations Research, Springer, vol. 254(1), pages 481-505, July.
    4. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    5. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    6. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    7. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.
    8. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    9. Rifki, Omar & Chiabaut, Nicolas & Solnon, Christine, 2020. "On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    10. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    11. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    12. Rincon-Garcia, Nicolas & Waterson, Ben & Cherrett, Tom J. & Salazar-Arrieta, Fernando, 2020. "A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 429-446.
    13. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    14. Lecluyse, Christophe & Sörensen, Kenneth & Peremans, Herbert, 2013. "A network-consistent time-dependent travel time layer for routing optimization problems," European Journal of Operational Research, Elsevier, vol. 226(3), pages 395-413.
    15. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    16. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    17. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    18. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    19. Liu, Zeyu & Li, Xueping & Khojandi, Anahita, 2022. "The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    20. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "The on-demand bus routing problem with real-time traffic information," Working Papers 2022003, University of Antwerp, Faculty of Business and Economics.

    Corrections

    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:ejores:v:255:y:2016:i:3:p:699-718. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.