Battery Electric Vehicle Traveling Salesman Problem with Drone

Tengkuo Zhu (), Stephen D. Boyles () and Avinash Unnikrishnan ()
Additional contact information
Tengkuo Zhu: University of Texas at Austin
Stephen D. Boyles: University of Texas at Austin
Avinash Unnikrishnan: University of Alabama at Birmingham

Networks and Spatial Economics, 2024, vol. 24, issue 1, No 3, 49-97

Abstract: 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.

Keywords: Traveling salesman problem; Electric vehicle; Unmanned aerial vehicle; Transportation logistics (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-023-09607-x Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:24:y:2024:i:1:d:10.1007_s11067-023-09607-x

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-023-09607-x

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().