IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v136y2020ics1366554519303722.html
   My bibliography  Save this article

Design and evaluation of a multi-trip delivery model with truck and drones

Author

Listed:
  • Moshref-Javadi, Mohammad
  • Lee, Seokcheon
  • Winkenbach, Matthias

Abstract

We extend the Traveling Repairman Problem (TRP) by assuming a single truck which can stop at customer locations and launch drones multiple times from each stop location to serve customers. The problem is mathematically modeled, several bound analyses are conducted to determine the maximum possible improvements in customer waiting times, and an efficient hybrid Tabu Search-Simulated Annealing algorithm is developed to solve the problem. The results of evaluations on several problem instances suggest that the system can yield considerable reductions in customer waiting time for a wide range of model parameters compared to the conventional delivery models.

Suggested Citation

  • Moshref-Javadi, Mohammad & Lee, Seokcheon & Winkenbach, Matthias, 2020. "Design and evaluation of a multi-trip delivery model with truck and drones," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    • Handle: RePEc:eee:transe:v:136:y:2020:i:c:s1366554519303722
    DOI: 10.1016/j.tre.2020.101887
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554519303722
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.101887?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. Carl Gaigne & Hans R.A. Koster & Fabien Moizeau & Jacques-Francois Thisse, 2017. "Amenities and the Social Structure of Cities," HSE Working papers WP BRP 162/EC/2017, National Research University Higher School of Economics.
    2. ., 2017. "Hegemonic Big Cities and the rising Sunbelt," Chapters, in: A History of American State and Local Economic Development, chapter 15, pages 453-488, Edward Elgar Publishing.
    3. Lai, David S.W. & Caliskan Demirag, Ozgun & Leung, Janny M.Y., 2016. "A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 86(C), pages 32-52.
    4. David Pisinger & Stefan Ropke, 2019. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, edition 3, chapter 0, pages 99-127, Springer.
    5. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    6. ., 2017. "Big Cities: New Deal, war years," Chapters, in: A History of American State and Local Economic Development, chapter 10, pages 293-320, Edward Elgar Publishing.
    7. Roel Gevaers & Eddy Van de Voorde & Thierry Vanelslander, 2011. "Characteristics and Typology of Last-mile Logistics from an Innovation Perspective in an Urban Context," Chapters, in: Cathy Macharis & Sandra Melo (ed.), City Distribution and Urban Freight Transport, chapter 3, Edward Elgar Publishing.
    8. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    9. Matteo Fischetti & Gilbert Laporte & Silvano Martello, 1993. "The Delivery Man Problem and Cumulative Matroids," Operations Research, INFORMS, vol. 41(6), pages 1055-1064, December.
    10. Silva, Marcos Melo & Subramanian, Anand & Vidal, Thibaut & Ochi, Luiz Satoru, 2012. "A simple and effective metaheuristic for the Minimum Latency Problem," European Journal of Operational Research, Elsevier, vol. 221(3), pages 513-520.
    11. Li, Xiangyong & Tian, Peng & Aneja, Y.P., 2010. "An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1111-1127, November.
    12. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    13. Chowdhury, Sudipta & Emelogu, Adindu & Marufuzzaman, Mohammad & Nurre, Sarah G. & Bian, Linkan, 2017. "Drones for disaster response and relief operations: A continuous approximation model," International Journal of Production Economics, Elsevier, vol. 188(C), pages 167-184.
    14. Wei, Lijun & Zhang, Zhenzhen & Zhang, Defu & Leung, Stephen C.H., 2018. "A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 265(3), pages 843-859.
    15. ., 2017. "Introduction: architecture and modern cities," Chapters, in: Creating Cities/Building Cities, chapter 1, pages 1-16, Edward Elgar Publishing.
    16. Moshref-Javadi, Mohammad & Lee, Seokcheon, 2016. "The Latency Location-Routing Problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 604-619.
    17. Tuzun, Dilek & Burke, Laura I., 1999. "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 87-99, July.
    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. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    2. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    3. Büyüközkan, Gülçin & Ilıcak, Öykü, 2022. "Smart urban logistics: Literature review and future directions," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    4. Zhou, Hang & Qin, Hu & Cheng, Chun & Rousseau, Louis-Martin, 2023. "An exact algorithm for the two-echelon vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 124-150.
    5. Amine Masmoudi, M. & Mancini, Simona & Baldacci, Roberto & Kuo, Yong-Hong, 2022. "Vehicle routing problems with drones equipped with multi-package payload compartments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    6. Jiang, Jie & Dai, Ying & Yang, Fei & Ma, Zujun, 2024. "A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services," European Journal of Operational Research, Elsevier, vol. 312(1), pages 125-137.
    7. Kangye Tan & Weihua Liu & Fang Xu & Chunsheng Li, 2023. "Optimization Model and Algorithm of Logistics Vehicle Routing Problem under Major Emergency," Mathematics, MDPI, vol. 11(5), pages 1-18, March.
    8. Mohammad Moshref-Javadi & Kristof P. Cauwenberghe & Brent A. McCunney & Ahmad Hemmati, 2023. "Enabling same-day delivery using a drone resupply model with transshipment points," Computational Management Science, Springer, vol. 20(1), pages 1-31, December.
    9. 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.
    10. Zhao, Lei & Bi, Xinhua & Li, Gendao & Dong, Zhaohui & Xiao, Ni & Zhao, Anni, 2022. "Robust traveling salesman problem with multiple drones: Parcel delivery under uncertain navigation environments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    11. 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).
    12. Yang, Yu & Yan, Chiwei & Cao, Yufeng & Roberti, Roberto, 2023. "Planning robust drone-truck delivery routes under road traffic uncertainty," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1145-1160.
    13. Jianxun Li & Hao Liu & Kin Keung Lai & Bhagwat Ram, 2022. "Vehicle and UAV Collaborative Delivery Path Optimization Model," Mathematics, MDPI, vol. 10(20), pages 1-22, October.
    14. Luigi Di Puglia Pugliese & Francesca Guerriero & Maria Grazia Scutellá, 2021. "The Last-Mile Delivery Process with Trucks and Drones Under Uncertain Energy Consumption," Journal of Optimization Theory and Applications, Springer, vol. 191(1), pages 31-67, October.
    15. Yan, Rui & Zhu, Xiaoping & Zhu, Xiaoning & Peng, Rui, 2022. "Optimal routes and aborting strategies of trucks and drones under random attacks," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    16. Wang, Haibo & Alidaee, Bahram, 2023. "White-glove service delivery: A quantitative analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    17. Pahwa, Anmol & Jaller, Miguel, 2022. "A cost-based comparative analysis of different last-mile strategies for e-commerce delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Pahwa, Anmol & Jaller, Miguel, 2023. "Assessing last-mile distribution resilience under demand disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    19. He, Xinyu & He, Fang & Li, Lishuai & Zhang, Lei & Xiao, Gang, 2022. "A route network planning method for urban air delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    20. Salama, Mohamed R. & Srinivas, Sharan, 2022. "Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    21. 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.
    22. Meng, Shanshan & Guo, Xiuping & Li, Dong & Liu, Guoquan, 2023. "The multi-visit drone routing problem for pickup and delivery services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(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. Hast, Aira & Syri, Sanna & Lekavičius, Vidas & Galinis, Arvydas, 2018. "District heating in cities as a part of low-carbon energy system," Energy, Elsevier, vol. 152(C), pages 627-639.
    2. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    3. Wusheng Liu & Wang Li & Qing Zhou & Qian Die & Yan Yang, 2022. "The optimization of the "UAV-vehicle" joint delivery route considering mountainous cities," PLOS ONE, Public Library of Science, vol. 17(3), pages 1-21, March.
    4. Sandun Perera & Milind Dawande & Ganesh Janakiraman & Vijay Mookerjee, 2020. "Retail Deliveries by Drones: How Will Logistics Networks Change?," Production and Operations Management, Production and Operations Management Society, vol. 29(9), pages 2019-2034, September.
    5. Akbari, Vahid & Shiri, Davood, 2021. "Weighted online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 295(1), pages 51-65.
    6. Nguyen, Minh Anh & Dang, Giang Thi-Huong & Hà, Minh Hoàng & Pham, Minh-Trien, 2022. "The min-cost parallel drone scheduling vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 299(3), pages 910-930.
    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. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    9. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    10. Qiqian Zhang & Xiao Huang & Honghai Zhang & Chunyun He, 2023. "Research on Logistics Path Optimization for a Two-Stage Collaborative Delivery System Using Vehicles and UAVs," Sustainability, MDPI, vol. 15(17), pages 1-20, September.
    11. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    12. Yang Xia & Wenjia Zeng & Xinjie Xing & Yuanzhu Zhan & Kim Hua Tan & Ajay Kumar, 2023. "Joint optimisation of drone routing and battery wear for sustainable supply chain development: a mixed-integer programming model based on blockchain-enabled fleet sharing," Annals of Operations Research, Springer, vol. 327(1), pages 89-127, August.
    13. Snežana Tadić & Mladen Krstić & Ljubica Radovanović, 2024. "Assessing Strategies to Overcome Barriers for Drone Usage in Last-Mile Logistics: A Novel Hybrid Fuzzy MCDM Model," Mathematics, MDPI, vol. 12(3), pages 1-25, January.
    14. Mohammad Moshref-Javadi & Kristof P. Cauwenberghe & Brent A. McCunney & Ahmad Hemmati, 2023. "Enabling same-day delivery using a drone resupply model with transshipment points," Computational Management Science, Springer, vol. 20(1), pages 1-31, December.
    15. Zhao, Lei & Bi, Xinhua & Li, Gendao & Dong, Zhaohui & Xiao, Ni & Zhao, Anni, 2022. "Robust traveling salesman problem with multiple drones: Parcel delivery under uncertain navigation environments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    16. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    17. Jeong, Ho Young & Song, Byung Duk & Lee, Seokcheon, 2019. "Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones," International Journal of Production Economics, Elsevier, vol. 214(C), pages 220-233.
    18. Boysen, Nils & Schwerdfeger, Stefan & Weidinger, Felix, 2018. "Scheduling last-mile deliveries with truck-based autonomous robots," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1085-1099.
    19. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    20. Dongwook Kim & Kyungsik Lee & Ilkyeong Moon, 2019. "Stochastic facility location model for drones considering uncertain flight distance," Annals of Operations Research, Springer, vol. 283(1), pages 1283-1302, 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:eee:transe:v:136:y:2020:i:c:s1366554519303722. 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/600244/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.