IDEAS home Printed from https://ideas.repec.org/p/mag/wpaper/23002.html

Consistent Time Window Assignments for Stochastic Multi-Depot Multi-Commodity Pickup and Delivery

Author

Listed:
  • Shohre Zehtabian
  • Marlin W. Ulmer

Abstract

In this paper, we present the problem of assigning consistent time windows for the collection of multiple fresh products from local farmers and delivering them to distribution centers for consolidation and further distribution in a short agri-food supply chain with stochastic demand. We formulate the problem as a two-stage stochastic program. In the first stage, the time windows are assigned from a set of discrete time windows to farmers and in the second stage, after the demand is realized, the collection routes are planned by solving yet a newly introduced multi-depot multi-commodity team orienteering problem with soft time windows. The objective is to minimize the overall travel time and the time window violations. To solve our problem, we design a (heuristic) progressive hedging algorithm to decompose the deterministic equivalent problem into subproblems for a sampled set of demand scenarios and guide the scenarios toward consensus time windows. Through numerical experiments, we show the value of considering demand uncertainty over solving the deterministic expected value problem and the superiority of our approach over benchmarks when it comes to reducing the routing cost as well as the inconvenience for farmers.

Suggested Citation

  • Shohre Zehtabian & Marlin W. Ulmer, 2023. "Consistent Time Window Assignments for Stochastic Multi-Depot Multi-Commodity Pickup and Delivery," FEMM Working Papers 23002, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    • Handle: RePEc:mag:wpaper:23002
    as

    Download full text from publisher

    File URL: https://www.fww.ovgu.de/fww_media/femm/femm_2023/2023_02.pdf
    File Function: First version, 2011
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    2. 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.
    3. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    4. Teodor Crainic & Fausto Errico & Federico Malucelli & Maddalena Nonato, 2012. "Designing the master schedule for demand-adaptive transit systems," Annals of Operations Research, Springer, vol. 194(1), pages 151-166, April.
    5. Ilgaz Sungur & Yingtao Ren & Fernando Ordóñez & Maged Dessouky & Hongsheng Zhong, 2010. "A Model and Algorithm for the Courier Delivery Problem with Uncertainty," Transportation Science, INFORMS, vol. 44(2), pages 193-205, May.
    6. Charlotte Ackva & Marlin W. Ulmer, 2022. "Consistent Routing for Local Same-Day Delivery via Micro-Hubs," FEMM Working Papers 22007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    7. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    8. Kevin Dalmeijer & Guy Desaulniers, 2021. "Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 495-510, May.
    9. Anirudh Subramanyam & Chrysanthos E. Gounaris, 2018. "A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling," Transportation Science, INFORMS, vol. 52(2), pages 386-401, March.
    10. Fernando Veliz & Jean-Paul Watson & Andres Weintraub & Roger Wets & David Woodruff, 2015. "Stochastic optimization models in forest planning: a progressive hedging solution approach," Annals of Operations Research, Springer, vol. 232(1), pages 259-274, September.
    11. John Gunnar Carlsson & Erick Delage, 2013. "Robust Partitioning for Stochastic Multivehicle Routing," Operations Research, INFORMS, vol. 61(3), pages 727-744, June.
    12. Claudia Archetti & Ann Melissa Campbell & M. Grazia Speranza, 2016. "Multicommodity vs. Single-Commodity Routing," Transportation Science, INFORMS, vol. 50(2), pages 461-472, May.
    13. 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.
    14. Remy Spliet & Said Dabia & Tom Van Woensel, 2018. "The Time Window Assignment Vehicle Routing Problem with Time-Dependent Travel Times," Transportation Science, INFORMS, vol. 52(2), pages 261-276, March.
    15. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    16. Anastasios D. Vareias & Panagiotis P. Repoussis & Panagiotis P. Repoussi, 2019. "Assessing Customer Service Reliability in Route Planning with Self-Imposed Time Windows and Stochastic Travel Times," Service Science, INFORMS, vol. 53(1), pages 256-281, February.
    17. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    18. Remy Spliet & Adriana F. Gabor, 2015. "The Time Window Assignment Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 721-731, November.
    19. Dhirendra Prajapati & Felix T. S. Chan & Yash Daultani & Saurabh Pratap, 2022. "Sustainable vehicle routing of agro-food grains in the e-commerce industry," International Journal of Production Research, Taylor & Francis Journals, vol. 60(24), pages 7319-7344, December.
    20. Spliet, Remy & Desaulniers, Guy, 2015. "The discrete time window assignment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 379-391.
    21. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    22. Stavropoulou, F. & Repoussis, P.P. & Tarantilis, C.D., 2019. "The Vehicle Routing Problem with Profits and consistency constraints," European Journal of Operational Research, Elsevier, vol. 274(1), pages 340-356.
    23. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    24. Hongsheng Zhong & Randolph W. Hall & Maged Dessouky, 2007. "Territory Planning and Vehicle Dispatching with Driver Learning," Transportation Science, INFORMS, vol. 41(1), pages 74-89, 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. Daniel Cuellar-Usaquén & Marlin & Camilo Gomez & David Alvarez-Martinez, 2023. "Adaptive stochastic lookahead policies for dynamic multi-period purchasing and inventory routing," FEMM Working Papers 23004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.

    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. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2024. "An updated survey of attended home delivery and service problems with a focus on applications," Annals of Operations Research, Springer, vol. 343(2), pages 885-922, December.
    2. Yang, Meng & Ni, Yaodong & Song, Qinyu, 2022. "Optimizing driver consistency in the vehicle routing problem under uncertain environment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    3. Yao, Yu & Van Woensel, Tom & Veelenturf, Lucas P. & Mo, Pengli, 2021. "The consistent vehicle routing problem considering path consistency in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 21-44.
    4. Çelik, Sifa & Schrotenboer, Albert H. & Martin, Layla & Van Woensel, Tom, 2026. "Is waiting worth it? the value of delaying time window assignment in vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 204(C).
    5. Charlotte Ackva & Marlin W. Ulmer, 2024. "Consistent routing for local same-day delivery via micro-hubs," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(2), pages 375-409, June.
    6. 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.
    7. Paradiso, Rosario & Roberti, Roberto & Ulmer, Marlin, 2025. "Lookahead scenario relaxation for dynamic time window assignment in service routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    8. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    9. Jean-François Cordeau & Manuel Iori & Dario Vezzali, 2023. "A survey of attended home delivery and service problems with a focus on applications," 4OR, Springer, vol. 21(4), pages 547-583, December.
    10. Subramanyam, Anirudh & Wang, Akang & Gounaris, Chrysanthos E., 2018. "A scenario decomposition algorithm for strategic time window assignment vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 296-317.
    11. Cavaliere, Francesco & Fischetti, Matteo & Roberti, Roberto & Salvagnin, Domenico, 2026. "Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times," European Journal of Operational Research, Elsevier, vol. 329(1), pages 96-111.
    12. Daniel Cuellar-Usaquén & Marlin & Camilo Gomez & David Alvarez-Martinez, 2023. "Adaptive stochastic lookahead policies for dynamic multi-period purchasing and inventory routing," FEMM Working Papers 23004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    13. Côté, Jean-François & Mansini, Renata & Raffaele, Alice, 2024. "Multi-period time window assignment for attended home delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 295-309.
    14. Marlin W. Ulmer & Justin C. Goodson & Barrett W. Thomas, 2023. "Optimal Service Time Windows," FEMM Working Papers 23001, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    15. Zhou, Lin & Zhen, Lu & Baldacci, Roberto & Boschetti, Marco & Dai, Ying & Lim, Andrew, 2021. "A Heuristic Algorithm for solving a large-scale real-world territory design problem," Omega, Elsevier, vol. 103(C).
    16. Cuellar-Usaquén, Daniel & Ulmer, Marlin W. & Gomez, Camilo & Álvarez-Martínez, David, 2024. "Adaptive stochastic lookahead policies for dynamic multi-period purchasing and inventory routing," European Journal of Operational Research, Elsevier, vol. 318(3), pages 1028-1041.
    17. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    18. Marlin W. Ulmer & Justin C. Goodson & Barrett W. Thomas, 2024. "Optimal Service Time Windows," Transportation Science, INFORMS, vol. 58(2), pages 394-411, March.
    19. Shohre Zehtabian & Marlin W. Ulmer, 2026. "Consistent Time Window Assignments for Stochastic Multi-Depot Multi-Commodity Pickup and Delivery," Transportation Science, INFORMS, vol. 60(1), pages 1-21, January.
    20. Koch, Sebastian & Klein, Robert, 2020. "Route-based approximate dynamic programming for dynamic pricing in attended home delivery," European Journal of Operational Research, Elsevier, vol. 287(2), pages 633-652.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:mag:wpaper:23002. 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: IT Administrators at FWW (email available below). General contact details of provider: https://edirc.repec.org/data/fwmagde.html .

    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.