IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v24y2024i1d10.1007_s11067-023-09607-x.html
   My bibliography  Save this article

Battery Electric Vehicle Traveling Salesman Problem with Drone

Author

Listed:
  • Tengkuo Zhu

    (University of Texas at Austin)

  • Stephen D. Boyles

    (University of Texas at Austin)

  • Avinash Unnikrishnan

    (University of Alabama at Birmingham)

Abstract

The idea of deploying electric vehicles and unmanned aerial vehicles (UAVs), also known as drones, to deliver packages in logistics operations has attracted increasing attention in the past few years. In this paper, we propose an innovative problem where a battery electric vehicle (BEV) paired with drone is utilized to deliver first-aid items in a rural area. This problem is termed battery electric vehicle traveling salesman problem with drone (BEVTSPD). In BEVTSPD, the BEV and the drone perform delivery tasks coordinately while the BEV can serve as a drone hub. The BEV can also refresh its battery energy to full capacity in battery-swap stations available in the network. An arc-based mixed-integer programming model defined in a multigraph is presented for BEVTSPD. An exact branch-and-price (BP) algorithm and a Variable Neighborhood Search (VNS) heuristic are developed to solve instances with up to 25 customers in one minute. Numerical experiments show that the heuristic is much more efficient than solving the arc-based model using the ILOG CPLEX solver and BP algorithm. A real-world case study and the sensitivity analysis of different parameters are also conducted and presented. The results indicate that drone speed has a more significant effect on delivery time than the BEV’s driving range.

Suggested Citation

  • Tengkuo Zhu & Stephen D. Boyles & Avinash Unnikrishnan, 2024. "Battery Electric Vehicle Traveling Salesman Problem with Drone," Networks and Spatial Economics, Springer, vol. 24(1), pages 49-97, March.
    • Handle: RePEc:kap:netspa:v:24:y:2024:i:1:d:10.1007_s11067-023-09607-x
    DOI: 10.1007/s11067-023-09607-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11067-023-09607-x
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-023-09607-x?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. Yang, Fei & Dai, Ying & Ma, Zu-Jun, 2020. "A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    2. Juho Andelmin & Enrico Bartolini, 2017. "An Exact Algorithm for the Green Vehicle Routing Problem," Transportation Science, INFORMS, vol. 51(4), pages 1288-1303, November.
    3. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    4. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    5. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    6. 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.
    7. Dell’Amico, Mauro & Montemanni, Roberto & Novellani, Stefano, 2021. "Algorithms based on branch and bound for the flying sidekick traveling salesman problem," Omega, Elsevier, vol. 104(C).
    8. 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.
    9. Christensen, Linda & Klauenberg, Jens & Kveiborg, Ole & Rudolph, Christian, 2017. "Suitability of commercial transport for a shift to electric mobility with Denmark and Germany as use cases," Research in Transportation Economics, Elsevier, vol. 64(C), pages 48-60.
    10. Feyijimi Adegbohun & Annette von Jouanne & Kwang Y. Lee, 2019. "Autonomous Battery Swapping System and Methodologies of Electric Vehicles," Energies, MDPI, vol. 12(4), pages 1-14, February.
    11. Rebecca S. Widrick & Sarah G. Nurre & Matthew J. Robbins, 2018. "Optimal Policies for the Management of an Electric Vehicle Battery Swap Station," Transportation Science, INFORMS, vol. 52(1), pages 59-79, January.
    12. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    13. M. L. Balinski & R. E. Quandt, 1964. "On an Integer Program for a Delivery Problem," Operations Research, INFORMS, vol. 12(2), pages 300-304, April.
    14. Chungmok Lee, 2021. "An exact algorithm for the electric-vehicle routing problem with nonlinear charging time," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(7), pages 1461-1485, July.
    15. Nicholas D. Kullman & Justin C. Goodson & Jorge E. Mendoza, 2021. "Electric Vehicle Routing with Public Charging Stations," Transportation Science, INFORMS, vol. 55(3), pages 637-659, May.
    16. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    17. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. 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).
    19. 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.
    20. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    21. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    22. Roberto Roberti & Mario Ruthmair, 2021. "Exact Methods for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 55(2), pages 315-335, March.
    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. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    2. Vichitkunakorn, Panupong & Emde, Simon & Masae, Makusee & Glock, Christoph H. & Grosse, Eric H., 2024. "Locating charging stations and routing drones for efficient automated stocktaking," European Journal of Operational Research, Elsevier, vol. 316(3), pages 1129-1145.
    3. Themistoklis Stamadianos & Nikolaos A. Kyriakakis & Magdalene Marinaki & Yannis Marinakis, 2023. "Routing Problems with Electric and Autonomous Vehicles: Review and Potential for Future Research," SN Operations Research Forum, Springer, vol. 4(2), pages 1-34, June.
    4. 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.
    5. 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.
    6. 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.
    7. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    8. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    9. 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.
    10. 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.
    11. Virginia Casella & Daniel Fernandez Valderrama & Giulio Ferro & Riccardo Minciardi & Massimo Paolucci & Luca Parodi & Michela Robba, 2022. "Towards the Integration of Sustainable Transportation and Smart Grids: A Review on Electric Vehicles’ Management," Energies, MDPI, vol. 15(11), pages 1-23, May.
    12. Alberto Ceselli & Ángel Felipe & M. Teresa Ortuño & Giovanni Righini & Gregorio Tirado, 2021. "A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies," SN Operations Research Forum, Springer, vol. 2(1), pages 1-33, March.
    13. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    14. Leandro do C. Martins & Rafael D. Tordecilla & Juliana Castaneda & Angel A. Juan & Javier Faulin, 2021. "Electric Vehicle Routing, Arc Routing, and Team Orienteering Problems in Sustainable Transportation," Energies, MDPI, vol. 14(16), pages 1-30, August.
    15. 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.
    16. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    17. Azra Ghobadi & Mohammad Fallah & Reza Tavakkoli-Moghaddam & Hamed Kazemipoor, 2022. "A Fuzzy Two-Echelon Model to Optimize Energy Consumption in an Urban Logistics Network with Electric Vehicles," Sustainability, MDPI, vol. 14(21), pages 1-31, October.
    18. Koyuncu, Işıl & Yavuz, Mesut, 2019. "Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 605-623.
    19. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    20. Xu, Min & Meng, Qiang, 2019. "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 23-49.

    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:kap:netspa:v:24:y:2024:i:1:d:10.1007_s11067-023-09607-x. 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.