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

The pickup and delivery problem with transshipments: Critical review of two existing models and a new formulation

Author

Listed:
  • Lyu, Zefeng
  • Yu, Andrew Junfang

Abstract

The pickup and delivery problem with transshipments (PDP-T) is generalized from the classical pickup and delivery problem (PDP) by allowing the transfer of requests between vehicles. After considering the time window constraints, the PDP-T is further generalized to the pickup and delivery problem with time windows and transshipments (PDPTW-T). In this paper, we review two state-of-the-art models for the PDP-T and PDPTW-T. We point out the possible issues existing in the models and provide our revisions. In addition, we develop a new mixed-integer linear programming formulation to solve the PDP-T and PDPTW-T. The performance of the proposed model is evaluated by solving 340 generated PDP-T instances and 360 open-access PDPTW-T instances. Computational results show that the proposed model outperforms the existing models in terms of solution quality and computing time. PTP-T instances with up to 25 requests and 2 transfer stations are solved to optimality by using the proposed model. As a comparison, the best-known benchmarks in the literature are instances with 5 requests and 1 transfer station. In addition, the computing time is significantly reduced. In our experiments, the average computational time for solving PDP-T is reduced by 96%. For PDPTW-T instances, the solvable scale is increased from 3 requests and 4 transfer stations to 5 requests and 4 transfer stations. The average computing time is reduced by 40%.

Suggested Citation

  • Lyu, Zefeng & Yu, Andrew Junfang, 2023. "The pickup and delivery problem with transshipments: Critical review of two existing models and a new formulation," European Journal of Operational Research, Elsevier, vol. 305(1), pages 260-270.
    • Handle: RePEc:eee:ejores:v:305:y:2023:i:1:p:260-270
    DOI: 10.1016/j.ejor.2022.05.053
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722004556
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.05.053?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. 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.
    2. Jean-François Cordeau, 2006. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem," Operations Research, INFORMS, vol. 54(3), pages 573-586, June.
    3. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    4. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    5. Wolfinger, David & Salazar-González, Juan-José, 2021. "The Pickup and Delivery Problem with Split Loads and Transshipments: A Branch-and-Cut Solution Approach," European Journal of Operational Research, Elsevier, vol. 289(2), pages 470-484.
    6. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    7. Cortes, Juan David & Suzuki, Yoshinori, 2020. "Vehicle Routing with Shipment Consolidation," International Journal of Production Economics, Elsevier, vol. 227(C).
    8. Renaud Masson & Fabien Lehuédé & Olivier Péton, 2013. "An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers," Transportation Science, INFORMS, vol. 47(3), pages 344-355, August.
    9. Rais, A. & Alvelos, F. & Carvalho, M.S., 2014. "New mixed integer-programming model for the pickup-and-delivery problem with transshipment," European Journal of Operational Research, Elsevier, vol. 235(3), pages 530-539.
    Full references (including those not matched with items on IDEAS)

    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. Mahmoudi, Monirehalsadat & Chen, Junhua & Shi, Tie & Zhang, Yongxiang & Zhou, Xuesong, 2019. "A cumulative service state representation for the pickup and delivery problem with transfers," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 351-380.
    2. 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.
    3. Fu, Zhexi & Chow, Joseph Y.J., 2022. "The pickup and delivery problem with synchronized en-route transfers for microtransit planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    4. Falkenberg, Sven F. & Spinler, Stefan & Strauss, Arne K., 2024. "An algorithm for flexible transshipments with perfect synchronization," European Journal of Operational Research, Elsevier, vol. 315(3), pages 913-925.
    5. 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.
    6. Wei Zhou & Jane Lin, 2019. "An On-Demand Same-Day Delivery Service Using Direct Peer-to-Peer Transshipment Strategies," Networks and Spatial Economics, Springer, vol. 19(2), pages 409-443, June.
    7. Wolfinger, David & Salazar-González, Juan-José, 2021. "The Pickup and Delivery Problem with Split Loads and Transshipments: A Branch-and-Cut Solution Approach," European Journal of Operational Research, Elsevier, vol. 289(2), pages 470-484.
    8. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    9. David Wolfinger & Fabien Tricoire & Karl F. Doerner, 2019. "A matheuristic for a multimodal long haul routing problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 397-433, December.
    10. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    11. Molenbruch, Yves & Braekers, Kris & Caris, An, 2017. "Benefits of horizontal cooperation in dial-a-ride services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 107(C), pages 97-119.
    12. Paul Buijs & Jose Alejandro Lopez Alvarez & Marjolein Veenstra & Kees Jan Roodbergen, 2016. "Improved Collaborative Transport Planning at Dutch Logistics Service Provider Fritom," Interfaces, INFORMS, vol. 46(2), pages 119-132, April.
    13. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    14. Emrah Demir & Tom Van Woensel & Ton de Kok, 2014. "Multidepot Distribution Planning at Logistics Service Provider Nabuurs B.V," Interfaces, INFORMS, vol. 44(6), pages 591-604, December.
    15. 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.
    16. 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.
    17. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    18. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    19. Neves-Moreira, F. & Amorim, P. & Guimarães, L. & Almada-Lobo, B., 2016. "A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations," European Journal of Operational Research, Elsevier, vol. 248(2), pages 487-506.
    20. Marcus Posada & Henrik Andersson & Carl H. Häll, 2017. "The integrated dial-a-ride problem with timetabled fixed route service," Public Transport, Springer, vol. 9(1), pages 217-241, July.

    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:305:y:2023:i:1:p:260-270. 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.