IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v91y2016icp34-51.html
   My bibliography  Save this article

A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands

Author

Listed:
  • Ghilas, Veaceslav
  • Demir, Emrah
  • Woensel, Tom Van

Abstract

The Pickup and Delivery Problem with Time Windows, Scheduled Lines and Stochastic Demands (PDPTW-SLSD) concerns scheduling a set of vehicles to serve a set of requests, whose expected demands are known in distribution when planning, but are only revealed with certainty upon the vehicles’ arrival. In addition, a part of the transportation plan can be carried out on limited-capacity scheduled public transportation line services. This paper proposes a scenario-based sample average approximation approach for the PDPTW-SLSD. An adaptive large neighborhood search heuristic embedded into sample average approximation method is used to generate good-quality solutions. Computational results on instances with up to 40 requests (i.e., 80 locations) reveal that the integrated transportation networks can lead to operational cost savings of up to 16% compared with classical pickup and delivery systems.

Suggested Citation

  • Ghilas, Veaceslav & Demir, Emrah & Woensel, Tom Van, 2016. "A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 34-51.
    • Handle: RePEc:eee:transb:v:91:y:2016:i:c:p:34-51
    DOI: 10.1016/j.trb.2016.04.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261515300485
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2016.04.015?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. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. 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.
    3. 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.
    4. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    5. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    6. Demir, Emrah & Huang, Yuan & Scholts, Sebastiaan & Van Woensel, Tom, 2015. "A selected review on the negative externalities of the freight transportation: Modeling and pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 95-114.
    7. Santos, Georgina & Behrendt, Hannah & Teytelboym, Alexander, 2010. "Part II: Policy instruments for sustainable road transport," Research in Transportation Economics, Elsevier, vol. 28(1), pages 46-91.
    8. Yuri Levin & Mikhail Nediak & Huseyin Topaloglu, 2012. "Cargo Capacity Management with Allotments and Spot Market Demand," Operations Research, INFORMS, vol. 60(2), pages 351-365, April.
    9. Nanry, William P. & Wesley Barnes, J., 2000. "Solving the pickup and delivery problem with time windows using reactive tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 107-121, February.
    10. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    11. Warren B. Powell & Yosef Sheffi & Kenneth S. Nickerson & Kevin Butterbaugh & Susan Atherton, 1988. "Maximizing Profits for North American Van Lines' Truckload Division: A New Framework for Pricing and Operations," Interfaces, INFORMS, vol. 18(1), pages 21-41, February.
    12. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2015. "Benders Decomposition for Production Routing Under Demand Uncertainty," Operations Research, INFORMS, vol. 63(4), pages 851-867, August.
    13. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    14. Braekers, Kris & Caris, An & Janssens, Gerrit K., 2014. "Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 166-186.
    15. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, 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. Han Zhang & Yongbo Lv & Jianwei Guo, 2022. "New Development Direction of Underground Logistics from the Perspective of Public Transport: A Systematic Review Based on Scientometrics," Sustainability, MDPI, vol. 14(6), pages 1-31, March.
    2. Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
    3. Yang, Tiannuo & Chu, Zhongzhu & Wang, Bailin, 2023. "Feasibility on the integration of passenger and freight transportation in rural areas: A service mode and an optimization model," Socio-Economic Planning Sciences, Elsevier, vol. 88(C).
    4. He, Dongdong & Guan, Wei, 2023. "Promoting service quality with incentive contracts in rural bus integrated passenger-freight service," Transportation Research Part A: Policy and Practice, Elsevier, vol. 175(C).
    5. Sun, Xuting & Chung, Sai-Ho & Choi, Tsan-Ming & Sheu, Jiuh-Biing & Ma, Hoi Lam, 2020. "Combating lead-time uncertainty in global supply chain's shipment-assignment: Is it wise to be risk-averse?," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 406-434.
    6. Bruzzone, Francesco & Nocera, Silvio & Pesenti, Raffaele, 2023. "Feasibility and optimization of freight-on-transit schemes for the sustainable operation of passengers and logistics," Research in Transportation Economics, Elsevier, vol. 101(C).
    7. Ahamed, Tanvir & Zou, Bo & Farazi, Nahid Parvez & Tulabandhula, Theja, 2021. "Deep Reinforcement Learning for Crowdsourced Urban Delivery," Transportation Research Part B: Methodological, Elsevier, vol. 152(C), pages 227-257.
    8. Ma, Mingyou & Zhang, Fangni & Liu, Wei & Dixit, Vinayak, 2022. "A game theoretical analysis of metro-integrated city logistics systems," Transportation Research Part B: Methodological, Elsevier, vol. 156(C), pages 14-27.
    9. Cleophas, Catherine & Cottrill, Caitlin & Ehmke, Jan Fabian & Tierney, Kevin, 2019. "Collaborative urban transportation: Recent advances in theory and practice," European Journal of Operational Research, Elsevier, vol. 273(3), pages 801-816.
    10. Tafreshian, Amirmahdi & Abdolmaleki, Mojtaba & Masoud, Neda & Wang, Huizhu, 2021. "Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 227-259.
    11. Lu, Chang & Wu, Yuehui & Yu, Shanchuan, 2022. "A Sample Average Approximation Approach for the Stochastic Dial-A-Ride Problem on a Multigraph with User Satisfaction," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1031-1044.
    12. Wanjie Hu & Jianjun Dong & Bon-gang Hwang & Rui Ren & Zhilong Chen, 2019. "A Scientometrics Review on City Logistics Literature: Research Trends, Advanced Theory and Practice," Sustainability, MDPI, vol. 11(10), pages 1-27, May.
    13. He, Dongdong & Ceder, Avishai (Avi) & Zhang, Wenyi & Guan, Wei & Qi, Geqi, 2023. "Optimization of a rural bus service integrated with e-commerce deliveries guided by a new sustainable policy in China," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    14. Machado, Bruno & Pimentel, Carina & Sousa, Amaro de, 2023. "Integration planning of freight deliveries into passenger bus networks: Exact and heuristic algorithms," Transportation Research Part A: Policy and Practice, Elsevier, vol. 171(C).
    15. Mourad, Abood & Puchinger, Jakob & Chu, Chengbin, 2019. "A survey of models and algorithms for optimizing shared mobility," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 323-346.
    16. Azcuy, Irecis & Agatz, Niels & Giesen, Ricardo, 2021. "Designing integrated urban delivery systems using public transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    17. Feng, Wenhao & Tanimoto, Keishi & Chosokabe, Madoka, 2023. "Feasibility analysis of freight-passenger integration using taxis in rural areas by a mixed-integer programming model," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    18. Ghiami, Yousef & Demir, Emrah & Van Woensel, Tom & Christiansen, Marielle & Laporte, Gilbert, 2019. "A deteriorating inventory routing problem for an inland liquefied natural gas distribution network," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 45-67.
    19. Wang, Yuan & Lei, Linfei & Zhang, Dongxiang & Lee, Loo Hay, 2020. "Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 38-63.
    20. Molenbruch, Yves & Braekers, Kris & Hirsch, Patrick & Oberscheider, Marco, 2021. "Analyzing the benefits of an integrated mobility system using a matheuristic routing algorithm," European Journal of Operational Research, Elsevier, vol. 290(1), pages 81-98.
    21. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2020. "A green delivery-pickup problem for home hemodialysis machines; sharing economy in distributing scarce resources," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).

    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. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    2. Ertan Yakıcı & Robert F. Dell & Travis Hartman & Connor McLemore, 2018. "Daily aircraft routing for amphibious ready groups," Annals of Operations Research, Springer, vol. 264(1), pages 477-498, May.
    3. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    4. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    5. 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.
    6. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    7. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    8. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    9. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    10. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    11. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    12. Li, Chongshou & Gong, Lijun & Luo, Zhixing & Lim, Andrew, 2019. "A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing," Omega, Elsevier, vol. 89(C), pages 71-91.
    13. Guo, Jiaqi & Long, Jiancheng & Xu, Xiaoming & Yu, Miao & Yuan, Kai, 2022. "The vehicle routing problem of intercity ride-sharing between two cities," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 113-139.
    14. 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.
    15. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    16. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    17. Emna Marrekchi & Walid Besbes & Diala Dhouib & Emrah Demir, 2021. "A review of recent advances in the operations research literature on the green routing problem and its variants," Annals of Operations Research, Springer, vol. 304(1), pages 529-574, September.
    18. Johnsen, Lennart C. & Meisel, Frank, 2022. "Interrelated trips in the rural dial-a-ride problem with autonomous vehicles," European Journal of Operational Research, Elsevier, vol. 303(1), pages 201-219.
    19. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2022. "Van-based robot hybrid pickup and delivery routing problem," European Journal of Operational Research, Elsevier, vol. 298(3), pages 894-914.
    20. Zhang, Shuai & Gajpal, Yuvraj & Appadoo, S.S. & Abdulkader, M.M.S., 2018. "Electric vehicle routing problem with recharging stations for minimizing energy consumption," International Journal of Production Economics, Elsevier, vol. 203(C), pages 404-413.

    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:transb:v:91:y:2016:i:c:p:34-51. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.