IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v25y2017i3d10.1007_s10100-016-0459-2.html
   My bibliography  Save this article

Probabilistic time-dependent vehicle routing problem

Author

Listed:
  • Tomáš Režnar

    (VŠB - Technical University of Ostrava)

  • Jan Martinovič

    (VŠB - Technical University of Ostrava)

  • Kateřina Slaninová

    (VŠB - Technical University of Ostrava)

  • Ekaterina Grakova

    (VŠB - Technical University of Ostrava)

  • Vít Vondrák

    (VŠB - Technical University of Ostrava)

Abstract

The probabilistic time-dependent vehicle routing problem is presented in this paper. It is a novel variant of the vehicle routing problem. The variant is a problem of finding optimal routes for a fleet of vehicles visiting customers in order to proceed delivery or pick-up. All customers must be visited in designated times with given probabilities and services must begin within the given time windows. Each vehicle has a given capacity, which must not be exceeded. The travel time between each two locations is dependent on a vehicle departure time. The paper also contains examples and solution results of testing data sets using the adaptive large neighbourhood search algorithm.

Suggested Citation

  • Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(3), pages 545-560, September.
    • Handle: RePEc:spr:cejnor:v:25:y:2017:i:3:d:10.1007_s10100-016-0459-2
    DOI: 10.1007/s10100-016-0459-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10100-016-0459-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10100-016-0459-2?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. Franceschetti, Anna & Honhon, Dorothée & Van Woensel, Tom & Bektaş, Tolga & Laporte, Gilbert, 2013. "The time-dependent pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 265-293.
    2. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2015. "The load-dependent vehicle routing problem and its pick-up and delivery extension," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 158-181.
    3. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    4. 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.
    5. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    6. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    7. Goetschalckx, Marc & Jacobs-Blecha, Charlotte, 1989. "The vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 42(1), pages 39-51, September.
    8. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    9. 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.
    10. John D. C. Little & Katta G. Murty & Dura W. Sweeney & Caroline Karel, 1963. "An Algorithm for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 11(6), pages 972-989, December.
    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. Jalel Euchi & Malek Masmoudi & Patrick Siarry, 2022. "Home health care routing and scheduling problems: a literature review," 4OR, Springer, vol. 20(3), pages 351-389, September.
    2. Mojtaba Rajabi-Bahaabadi & Afshin Shariat-Mohaymany & Mohsen Babaei & Daniele Vigo, 2021. "Reliable vehicle routing problem in stochastic networks with correlated travel times," Operational Research, Springer, vol. 21(1), pages 299-330, March.
    3. Dragoš Cvetković & Mirjana Čangalović & Zorica Dražić & Vera Kovačević-Vujčić, 2018. "Complexity indices for the traveling salesman problem based on short edge subgraphs," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(3), pages 759-769, September.
    4. Andrej Kastrin & Janez Povh & Lidija Zadnik Stirn & Janez Žerovnik, 2021. "Methodologies and applications for resilient global development from the aspect of SDI-SOR special issues of CJOR," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(3), pages 773-790, September.

    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. 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.
    2. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    3. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    4. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "A review of recent research on green road freight transportation," European Journal of Operational Research, Elsevier, vol. 237(3), pages 775-793.
    5. 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.
    6. 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.
    7. Ramon Faganello Fachini & Vinícius Amaral Armentano & Franklina Maria Bragion Toledo, 2022. "A Granular Local Search Matheuristic for a Heterogeneous Fleet Vehicle Routing Problem with Stochastic Travel Times," Networks and Spatial Economics, Springer, vol. 22(1), pages 33-64, March.
    8. M. Alinaghian & M. Ghazanfari & N. Norouzi & H. Nouralizadeh, 2017. "A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 17(4), pages 1185-1211, December.
    9. Fontaine, Pirmin, 2022. "The vehicle routing problem with load-dependent travel times for cargo bicycles," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1005-1016.
    10. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    11. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    12. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    13. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    14. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    15. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    16. TALARICO, Luca & SÖRENSEN, Kenneth & SPRINGAEL, Johan, 2013. "The risk constrained cash-in-transit vehicle routing problem with time windows," Working Papers 2013012, University of Antwerp, Faculty of Business and Economics.
    17. Behnke, Martin & Kirschstein, Thomas & Bierwirth, Christian, 2021. "A column generation approach for an emission-oriented vehicle routing problem on a multigraph," European Journal of Operational Research, Elsevier, vol. 288(3), pages 794-809.
    18. Wang, Jiawei & Guo, Qinglai & Sun, Hongbin & Chen, Min, 2023. "Collaborative optimization of logistics and electricity for the mobile charging service system," Applied Energy, Elsevier, vol. 336(C).
    19. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2017. "A hybrid solution approach for the 3L-VRP with simultaneous delivery and pickups," FEMM Working Papers 170005, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    20. Franceschetti, Anna & Demir, Emrah & Honhon, Dorothée & Van Woensel, Tom & Laporte, Gilbert & Stobbe, Mark, 2017. "A metaheuristic for the time-dependent pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 972-991.

    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:spr:cejnor:v:25:y:2017:i:3:d:10.1007_s10100-016-0459-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.