IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v326y2025i1p124-140.html

A two-echelon vehicle routing problem with mobile satellites and multiple commodities

Author

Listed:
  • Dahimi, Aria
  • Lurkin, Virginie
  • Mohammadi, Mehrdad
  • Van Woensel, Tom

Abstract

This paper extends the two-echelon vehicle routing problem (2E-VRP) by considering multiple commodities, multiple depots, and mobile satellites (i.e., the so-called 3M-2E-VRP). This problem also accommodates flexible last-mile delivery strategies by allowing direct deliveries via first-echelon vehicles (mobile satellites) and indirect deliveries through goods exchanges at meeting points, such as parking lots or customer locations. We first model the problem as a mixed-integer linear programming (MILP); and then develop an innovative metaheuristic algorithm to solve medium and large problem instances. The proposed metaheuristic (the so-called AS-LNS) combines an innovative Approximate Scheduling (AS) approach with Large Neighborhood Search (LNS). Computational experiments validate the 3M-2E-VRP formulation and demonstrate the effectiveness of the proposed AS-LNS algorithm. Key managerial insights are further presented through a comprehensive sensitivity analysis, wherein the impact of key parameters, such as fuel consumption and wage costs, and comparison of different problem variants, is investigated on last-mile delivery strategies.

Suggested Citation

  • Dahimi, Aria & Lurkin, Virginie & Mohammadi, Mehrdad & Van Woensel, Tom, 2025. "A two-echelon vehicle routing problem with mobile satellites and multiple commodities," European Journal of Operational Research, Elsevier, vol. 326(1), pages 124-140.
    • Handle: RePEc:eee:ejores:v:326:y:2025:i:1:p:124-140
    DOI: 10.1016/j.ejor.2025.04.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725002978
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.04.027?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

    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. 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. 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.
    4. Quanwu Zhao & Wei Wang & Robert De Souza, 2018. "A heterogeneous fleet two-echelon capacitated location-routing model for joint delivery arising in city logistics," International Journal of Production Research, Taylor & Francis Journals, vol. 56(15), pages 5062-5080, August.
    5. Li, Jiliu & Xu, Min & Sun, Peng, 2022. "Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 261-291.
    6. 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.
    7. Tayeb Mhamedi & Henrik Andersson & Marilène Cherkesly & Guy Desaulniers, 2022. "A Branch-Price-and-Cut Algorithm for the Two-Echelon Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 56(1), pages 245-264, January.
    8. Nico Dellaert & Fardin Dashty Saridarq & Tom Van Woensel & Teodor Gabriel Crainic, 2019. "Branch-and-Price–Based Algorithms for the Two-Echelon Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 53(2), pages 463-479, March.
    9. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2024. "Electric van-based robot deliveries with en-route charging," European Journal of Operational Research, Elsevier, vol. 317(3), pages 806-826.
    10. 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.
    11. Martin Savelsbergh & Tom Van Woensel, 2016. "50th Anniversary Invited Article—City Logistics: Challenges and Opportunities," Transportation Science, INFORMS, vol. 50(2), pages 579-590, May.
    12. 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.
    13. 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.
    14. 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.
    15. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti & Roberto Wolfler Calvo, 2013. "An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem," Operations Research, INFORMS, vol. 61(2), pages 298-314, April.
    16. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    17. 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.
    18. Ziqi Wang & Peihan Wen, 2020. "Optimization of a Low-Carbon Two-Echelon Heterogeneous-Fleet Vehicle Routing for Cold Chain Logistics under Mixed Time Window," Sustainability, MDPI, vol. 12(5), pages 1-22, March.
    19. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    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. 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.
    2. Wang, Decheng & Xie, Xiaolan & Moon, Ilkyeong, 2025. "Two-echelon container drayage with multiple transportation modes and overall-network time interdependence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    3. Yu, Vincent F. & Jodiawan, Panca & Hou, Ming-Lu & Gunawan, Aldy, 2021. "Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    4. Dumez, Dorian & Tilk, Christian & Irnich, Stefan & Lehuédé, Fabien & Olkis, Katharina & Péton, Olivier, 2023. "A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows," European Journal of Operational Research, Elsevier, vol. 305(1), pages 64-84.
    5. Natasja Sluijk & Alexandre M. Florio & Joris Kinable & Nico Dellaert & Tom Van Woensel, 2023. "A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 57(1), pages 252-272, January.
    6. 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.
    7. 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.
    8. Tadaros, Marduch & Migdalas, Athanasios & Quttineh, Nils-Hassan & Larsson, Torbjörn, 2025. "Evaluating metaheuristic solution quality for a hierarchical vehicle routing problem by strong lower bounding," Operations Research Perspectives, Elsevier, vol. 14(C).
    9. 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).
    10. Raúl Soto-Concha & John Willmer Escobar & Daniel Morillo-Torres & Rodrigo Linfati, 2025. "The Vehicle-Routing Problem with Satellites Utilization: A Systematic Review of the Literature," Mathematics, MDPI, vol. 13(7), pages 1-29, March.
    11. Xiong, Xiaoyun & Han, Jialin & Yin, Yunqiang & Cheng, T.C.E., 2025. "An exact method for the two-echelon split-delivery vehicle routing problem for liquefied natural gas delivery with the boil-off phenomenon," European Journal of Operational Research, Elsevier, vol. 321(1), pages 123-146.
    12. 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.
    13. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    14. Peng, Xiaoshuai & Zhang, Lele & Thompson, Russell G. & Wang, Kangzhou, 2023. "A three-phase heuristic for last-mile delivery with spatial-temporal consolidation and delivery options," International Journal of Production Economics, Elsevier, vol. 266(C).
    15. Zhang, Lele & Ding, Pengyuan & Thompson, Russell G., 2023. "A stochastic formulation of the two-echelon vehicle routing and loading bay reservation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    16. Guillaume Marques & Ruslan Sadykov & Rémy Dupas & Jean-Christophe Deschamps, 2022. "A Branch-Cut-and-Price Approach for the Single-Trip and Multi-Trip Two-Echelon Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 56(6), pages 1598-1617, November.
    17. Yang, Hongtai & Wu, Jianzhang & Zhang, Zhaolin & Liu, Xiaobo & D’Ariano, Andrea, 2025. "Optimal design for an urban truck-drone collaborative delivery system enhanced with relay points," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    18. 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.
    19. 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).
    20. Eder, Peter J. & Ramoser, Simon & Braun, Sarah & Weltge, Stefan, 2025. "Efficient active–passive vehicle coordination in multimodal transportation networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 203(C).

    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:eee:ejores:v:326:y:2025:i:1:p:124-140. 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.