Impact of Drone Battery Recharging Policy on Overall Carbon Emissions: The Traveling Salesman Problem with Drone

Murray and Chu [2] introduced a coordinated delivery approach involving a truck and a drone. In addition to a mathematical model that can solve instances of up to 10 customers, they proposed a heuristic approach constructed on the TSP. They first obtained a truck route and split it into drone tours regarding cost savings. Es Yurek and Ozmutlu [4] developed a two-stage iterative solution approach. In the first stage, they determined the truck route for a given subset of customers and then solved an MILP to assign drone tours optimally in the second stage. Vasquez et al. [21] applied Benders’ decomposition using a similar approach, obtaining the truck route for a subset of customers in the master problem and optimizing drone tours in the subproblem. Agatz et al. [3] allowed the truck to remain stationary and wait for the drone at the launch node. They developed a new formulation based on the enumeration of drone and truck route combinations between each possible launch and rendezvous node. Their results were improved through dynamic programming and applied to larger instances [22]. Their study shows that restricting the truck’s travel during the drone flight can significantly reduce the solution time. Dell’Amico et al. [23] presented a branch-and-bound algorithm that can solve instances involving up to 15 customers. In another study [24], they developed three formulations enhanced by diminishing the number of “big-M” constraints. Performance was quantified by solving 20-customer instances. The TSP-D assumes that the drone hovers while waiting for the truck at the rendezvous node. This was relaxed by Dell’Amico et al. [25], and the drone could land at the customer node to save battery charge. Boccia et al. [26] solved several instances with 20 nodes by combining a branch-and-cut algorithm with a column generation procedure. They proposed dealing with synchronization constraints through column generation. Schermer et al. [27] also proposed a branch-and-cut algorithm to solve 20-customer instances within a one-hour runtime limit. El-Adle et al. [28] developed an MILP formulation and enhanced its tractability with valid inequalities, preprocessing, and bound-tightening strategies.

Some researchers mainly focus on heuristic approaches. de Freitas and Penna [29] proposed a hybrid heuristic algorithm. Inspired by Murray and Chu [2], they obtained a TSP solution and then produced an initial TSP-D solution by assigning some truck nodes to the drone and considering cost savings. General Variable Neighborhood Search (GVNS) was applied to improve the initial solution. Another hybrid heuristic algorithm was presented by Ha et al. [30]. Initial solutions were generated through a genetic algorithm. Then, a split procedure was applied to obtain truck and drone chromosomes. The quality of the solutions was improved through a local search. They incorporated a repairing mechanism into the hybrid algorithm to repair infeasible chromosomes. Similarly, Kundu et al. [31] developed a two-stage heuristic. They first obtained a TSP tour and split it using the shortest path problem, which is the novelty of the solution approach. The solution was improved by a local search. El-Adle et al. [32] proposed a variable neighborhood search in which intensification was achieved in two stages. Gunay-Sezer et al. [33] improved some of the best-known solutions by presenting a hybrid heuristic algorithm composed of genetic and ant colony algorithms.

Liu et al. [34] investigated the problem with stochastic travel times. This was modeled as a Markov decision problem and solved using a reinforcement learning algorithm. They reported significant savings in the delivery time by dynamic decision making based on traffic conditions.

The above studies assume that the truck can only launch and pick up the drone at customer nodes. Marinelli et al. [13] relaxed this assumption for battery efficiency by allowing launch and pickups along edges. After obtaining a TSP-D solution through a greedy algorithm without relaxation, they improved the solution by intersecting a spanning area of the drone node with the related arcs on the truck route. The experimental study demonstrated that relaxation is helpful when the vehicles travel at the same speed. Masone et al. [14] assumed the drone can carry multiple packages simultaneously. The problem was solved with edge launches using edge discretization.

Some researchers have studied the multi-truck and multi-drone version of the problem. Wang et al. [35] provided a worst-case analysis to reveal the maximum savings obtained in the last-mile delivery by a fleet of trucks equipped with several drones on top. They also provided some bounds demonstrating how the drone speed and the number of drones per truck affect the maximum saving. The same authors extended the previous study considering cost issues and limited battery life [36].

Beyond the theoretical perspective of the early research in the literature, Murray and Raj [7] analyzed the TSP-D, operating a truck and multiple drones with varying battery limits, and proposed a three-stage heuristic approach. The multi-drone case leads to the replenishment order of the arriving (departing) drones at the same rendezvous (launch) node. It is considered a scheduling problem by Dell’Amico et al. [8], who proposed several formulations. Thomas et al. [37] extended this problem by relaxing the assumption that the truck can only launch and pick up the drones at customer nodes. Moshref-Javadi et al. [38] described three delivery models based on the level of synchronization between a truck and several drones. They reported that the maximum saving is obtained with the highest level of synchronization. The congested and clustered instances provided higher saving rates compared to uniforms. Tiniç et al. [39] proposed flow-based and two cut-based models to solve a truck and multi-drone delivery problem with cost minimization. They enhanced the formulation with valid inequalities. Kitjacharoenchai et al. [10] simplified the multiple truck–drone delivery problem based on two assumptions. First, the drones can return to the depot or visit a recharging station when needed. Second, the truck can launch or pick up only one drone at any customer node. The authors provided a mathematical model and a heuristic algorithm based on two phases. Tamke and Buscher [40] developed an MILP formulation and introduced problem-specific valid inequalities to strengthen linear relaxation. They solved 20-node instances, assuming unlimited drone ranges and 30-node instances with range-limited drones. Their study reveals that coordinated delivery can reduce the fleet size so that the delivery speed and the operator’s workload do not deteriorate.

Di Puglia Pugliese and Guerriero [41] extended the problem by incorporating time windows into the truck–drone delivery system. Coindreau et al. [6] assumed drone-eligible customers and time windows. The heuristic results obtained by applying an adaptive large neighborhood search with 100 parcel instances report a decrease of up to 34% in delivery costs. Yin et al. [42] proposed an enhanced branch-and-price-and-cut algorithm for the multiple trucks and multiple drone delivery problem with time windows.

A number of recent studies have investigated heuristic approaches for the multi-truck case. Lei et al. [43] proposed a dynamical artificial bee colony algorithm to minimize operational costs when multiple trucks are equipped with one drone. Kuo et al. [44] formulated an MIP model and proposed a variable neighborhood search heuristic for time window extension. The truck can pick up or launch the drone without parking [45]. This assumption entails synchronization on arcs. A nonlinear programming formulation and an adaptive large neighborhood search heuristic were proposed to solve the problem.

Beyond these extensions, some studies have investigated multi-visit drone flight. Luo et al. [46] studied the TSP-D and allowed for multiple drone visits per flight. The drone performed only delivery services. Energy consumption depends on the drone’s payload, self-weight, and flight time. This study proposed a multi-start tabu search algorithm, revealing that multi-visit drone flight can reduce delivery costs. Liu and Liu [47] solved a similar problem and developed a hybrid heuristic approach. This approach involved first constructing a feasible solution quickly and then improving it through simulated annealing and tabu search algorithms. They reported that, in a 30-customer network, the drone performs 12 deliveries in the single-visit case, whereas it delivers 20 parcels in the multi-visit case. Huang et al. [48] minimized the delivery cost for a similar problem by applying an ant colony algorithm. They concluded that the single-visit case performs better with clustered instances rather than random instances and that, for the multi-visit case, the opposite is true. Meng et al. [49] allowed drones to provide a pickup service in addition to delivery on each flight.

In most of the studies outlined above, the flight time constrained the drone’s travel. However, other parameters, such as payload and energy consumption, can affect drone flight. Campuzano et al. [50] considered the interdependencies among energy consumption, weather conditions, drone payload, and drone speed. Since the drone range depends on energy consumption, they determined the drone speed and the routes to minimize delivery time. The drone speed was discretized, and three levels were specified in their computational study. Mahmoudi and Eshghi [11] evaluated energy consumption based on payload and flight mode: takeoff, cruise, landing, and hovering. In [12], energy consumption depended on the drone load and was formulated as a nonlinear function. Similarly, Jeong et al. [51], Wu et al. [52], and Murray and Raj [7] considered payload-dependent energy consumption while satisfying the flight range. In [46], energy consumption depended on the drone’s payload, self-weight, and flight time.

Contrary to the above studies, Es Yurek and Ozmutlu [19] were the first to investigate the coordinated delivery concept under the battery recharging assumption. They developed an MIP model to solve the problem under full and partial recharging policies. They conducted an extensive computational study comparing the delivery times obtained by recharging and swapping policies under varying battery lives, recharging rates, short and long swapping times, and customer distributions. The results indicate the potential of the recharging policy to reduce delivery time. Tamke and Buscher [20] recently proposed an MIP model to determine routes and drone speed while minimizing delivery costs under the battery recharging policy. When the drone travels faster, the delivery time is reduced; however, the energy consumption increases, which leads to a trade-off between energy consumption and drone speed. Energy consumption was evaluated based on drone speed and payload. The MIP model was tested as a heuristic using 50-customer data.

The studies reviewed thus far focus on improving delivery performance through cost or delivery time minimization. However, the sustainability performance of the coordinated delivery concept is as significant as operational efficiency. When sustainability is the subject, studies mostly focus on minimizing carbon emissions or energy consumption. Meng et al. [49] investigated coordinated delivery by a truck and a drone from economic and sustainability perspectives. They analyzed the trade-off between carbon emissions and cost. Truck emission is the weight of carbon emitted by the truck during the delivery process, which is evaluated based on fuel consumption, and drone emission is based on the amount of carbon indirectly emitted during the electricity production process. The total cost includes the energy consumption cost, carbon emission cost, and drivers’ wages. A dual-objective MIP model has been formulated to solve this problem. The model was tested on data with ten demand nodes based on a firm in China. The study reported that coordinated delivery can reduce carbon emissions by 24.90%, the total cost by 22.13%, and the delivery time by 20.65% compared to traditional truck-based delivery. Like the authors of [49], Baldisseri et al. [53] analyzed the same system’s cost and emission. However, they compared its performance with three delivery systems: delivery by diesel vans, delivery by electric vans, and delivery by drones. In all cases, the coordinated delivery approach produced the lowest emissions. They defined different scenarios to evaluate carbon emissions. These scenarios were distinguished based on the drone utilization rate, wind speed, truck acceleration, and electricity production mix. Chiang et al. [18] minimized carbon emissions, which were evaluated as proportional to the distance traveled by the truck and the drone. A genetic algorithm was proposed to solve the problem. Banyai [54] minimized energy consumption and greenhouse gas emissions and reported that integrated delivery can significantly reduce energy consumption and emissions.

Zhang et al. [55] minimized the total energy consumption, delivery cost, and delivery time while determining delivery routes. The drone’s energy consumption was neglected since it was slight compared to the truck’s energy consumption, which was evaluated considering the truckload and distance. None of those studies considered the geographic information of the customer locations. Baek et al. [56] maximized battery utilization through energy-efficient routes. Delivery was performed concurrently by an electric truck and a drone. Since the energy consumption of the truck is sensitive to the altitude and road conditions, drone use could lead to efficient battery use by visiting customers located in energy-consuming terrains. The drone battery is not replaced or recharged and is used until it is depleted. However, the drone must return to the truck after each flight due to its payload capacity of one. A greedy heuristic algorithm was proposed to solve this problem. The computational results based on 30-customer data reported truck battery energy savings of up to 69%. Similarly, Xiao et al. [57] considered steep roads and travel distance, payload, and drone speed in energy consumption. They proposed an adaptive large neighborhood search to minimize total energy consumption.