IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v323y2023i1d10.1007_s10479-023-05177-w.html
   My bibliography  Save this article

A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method

Author

Listed:
  • Hendri Sutrisno

    (Academia Sinica)

  • Chao-Lung Yang

    (National Taiwan University of Science and Technology)

Abstract

In last-mile delivery, the turbulence of traffic uncertainties is often solved by establishing and utilizing multiple buffering warehouses (satellites) with setup and operational costs, which are very costly in implementation. This distribution system involving satellites is often derived as the two-echelon location routing problem (2E-LRP). This study proposes a new variety of 2E-LRP problems with mobile satellites, called 2E-LRP-MS, which aims to reduce the cost of 2E-LRP by replacing fixed-located satellites with mobile satellites. Rather than utilizing fixed-location satellites, 2E-LRP-MS employs the first echelon vehicles (CT) as the mobile satellites moving around the city to replenish multiple second echelon vehicles (CF) en-route. For the cargo replenishment process, CT and CF can temporarily park at the consolidation points (CP), such as public parking lots or paid loading-unloading zones. With this flexibility, the high operational costs of the fixed-location satellites can be exchanged with CP’s relatively low maintenance or renting fees, such as parking expenses. In this work, we introduce a heuristic method called clustering-based simultaneous neighborhood search (CSNS) to solve the proposed 2E-LRP-MS problem. The proposed CSNS considers the probabilistic mechanism and k-means clustering algorithm for facility selection, simultaneous neighborhood search to generate the routing solution, and local searches for optimizing the routing solution. Experimental results highlight the flexibility advantage of 2E-LRP-MS over 2E-LRP models and the searching efficiency of the proposed CSNS over the recent heuristic methods for two-echelon routing problems and commercial solver CPLEX.

Suggested Citation

  • Hendri Sutrisno & Chao-Lung Yang, 2023. "A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method," Annals of Operations Research, Springer, vol. 323(1), pages 203-228, April.
  • Handle: RePEc:spr:annopr:v:323:y:2023:i:1:d:10.1007_s10479-023-05177-w
    DOI: 10.1007/s10479-023-05177-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-023-05177-w
    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/s10479-023-05177-w?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. Grangier, Philippe & Gendreau, Michel & Lehuédé, Fabien & Rousseau, Louis-Martin, 2016. "An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization," European Journal of Operational Research, Elsevier, vol. 254(1), pages 80-91.
    2. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    3. Zhou, Lin & Baldacci, Roberto & Vigo, Daniele & Wang, Xu, 2018. "A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution," European Journal of Operational Research, Elsevier, vol. 265(2), pages 765-778.
    4. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    5. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    6. Julian Hof & Michael Schneider, 2021. "Intraroute Resource Replenishment with Mobile Depots," Transportation Science, INFORMS, vol. 55(3), pages 660-686, May.
    7. Kitjacharoenchai, Patchara & Min, Byung-Cheol & Lee, Seokcheon, 2020. "Two echelon vehicle routing problem with drones in last mile delivery," International Journal of Production Economics, Elsevier, vol. 225(C).
    8. Schneider, M. & Stenger, A. & Hof, J., 2015. "An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Nguyen, Viet-Phuong & Prins, Christian & Prodhon, Caroline, 2012. "Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking," European Journal of Operational Research, Elsevier, vol. 216(1), pages 113-126.
    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. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    2. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    3. Julian Hof & Michael Schneider, 2021. "Intraroute Resource Replenishment with Mobile Depots," Transportation Science, INFORMS, vol. 55(3), pages 660-686, May.
    4. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    5. Wolfinger, David & Gansterer, Margaretha & Doerner, Karl F. & Popper, Nikolas, 2023. "A Large Neighbourhood Search Metaheuristic for the Contagious Disease Testing Problem," European Journal of Operational Research, Elsevier, vol. 304(1), pages 169-182.
    6. Liu, Dan & Yan, Pengyu & Pu, Ziyuan & Wang, Yinhai & Kaisar, Evangelos I., 2021. "Hybrid artificial immune algorithm for optimizing a Van-Robot E-grocery delivery system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    7. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2021. "Two-echelon vehicle routing problem with satellite bi-synchronization," European Journal of Operational Research, Elsevier, vol. 288(3), pages 775-793.
    8. Mühlbauer, Ferdinand & Fontaine, Pirmin, 2021. "A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles," European Journal of Operational Research, Elsevier, vol. 289(2), pages 742-757.
    9. Yue Lu & Maoxiang Lang & Xueqiao Yu & Shiqi Li, 2019. "A Sustainable Multimodal Transport System: The Two-Echelon Location-Routing Problem with Consolidation in the Euro–China Expressway," Sustainability, MDPI, vol. 11(19), pages 1-25, October.
    10. 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.
    11. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    12. Soares, Ricardo & Marques, Alexandra & Amorim, Pedro & Parragh, Sophie N., 2024. "Synchronisation in vehicle routing: Classification schema, modelling framework and literature review," European Journal of Operational Research, Elsevier, vol. 313(3), pages 817-840.
    13. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2020. "Two-echelon vehicle routing problem with time windows and mobile satellites," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 179-201.
    14. Li, Hongqi & Liu, Yinying & Jian, Xiaorong & Lu, Yingrong, 2018. "The two-echelon distribution system considering the real-time transshipment capacity varying," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 239-260.
    15. Darvish, Maryam & Archetti, Claudia & Coelho, Leandro C. & Speranza, M. Grazia, 2019. "Flexible two-echelon location routing problem," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1124-1136.
    16. Li, Hongqi & Chen, Jun & Wang, Feilong & Bai, Ming, 2021. "Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1078-1095.
    17. 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.
    18. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    19. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    20. Sergio Maria Patella & Gianluca Grazieschi & Valerio Gatta & Edoardo Marcucci & Stefano Carrese, 2020. "The Adoption of Green Vehicles in Last Mile Logistics: A Systematic Review," Sustainability, MDPI, vol. 13(1), pages 1-29, December.

    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:annopr:v:323:y:2023:i:1:d:10.1007_s10479-023-05177-w. 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.