1. Introduction

In recent years, with the property of E-commercial development, people’s consumption concepts have started to change. The application of the Internet has increased the mobile phone penetration rate in China to 76.4%. Also, the brand-new shopping mode of a larger amount, lower unit cost and group shop brought from E-commerce also attract more rural people to join this wave. Until the end of 2023, the number of Chinese Internet rural users has reached 308 million, accounting for 28.9% of the total population. But because of the rugged and complex terrain of some rural areas, most express always need to spend more than 5 days to hit the destination. Like some mountainous scattered villages of Guizhou or inner magnolia, the last mile delivery problem even needs to be solved by manpower. Thus, applying truck-drone terminal distribution stations to work out the adaptive optimal last mile design starts becoming a new potential cost-effective solution for this status [1-3].

Taking a retrospection of truck-drone delivery development, it originated from the Flying Sidekick System mentioned by Murray [4]. Under this mode, one truck will follow the role to cooperate with one drone for customer service. Then this model was iterated by Poikonen with the mothership system, the truck will work as a landing platform to serve for last mile delivery and first put forward the problem of vehicle routing problem with drone (VRPD) [5]. On the basis of VRPD, Sacramento put forward an adaptive large neighborhood search metaheuristic for better working out the route setting of each truck-drone delivery combo to minimize the extra shipping cost and decrease the total delivery time [6]. Also, this UAV delivery has started to be used by some enterprises like the “Prime Air” of Amazon, “Project Wing” of Google and “UAV food delivery” of Meituan but no data show that these projects could wildly be adapted to most scenarios of good delivery under lower cost especially in rural area [7]. Thus, based on the background, this paper will focus on how to optimize truck-drone last mile delivery in mountainous rural areas based on routing sequence resetting to balance shipping cost and delivery efficiency [8].

2. Problem Description

This paper puts forward a new design of a truck-UAV cooperative model to fit the scattered village last mile delivery problem in real application. Based on the investigation, the distribution of villages could be divided into two different genres. One is cluster distribution, like part 1 and part 2 in Figure 1, and another is distributed aggregation, most of these houses are allocated in the areas which is hard to reach. From Figure 1, the truck will take responsibility for the long-distance shipping or the shipping by the round-trip route, each truck will carry at least two drones for last mile delivery. During the process, the truck will work as a movable server to release and recycle the drone as well as good delivery, and the drone will work as the intermediary to improve some distanced part's last mile delivery efficiency. Based on the drone capacity and cost calculation, the system will automatically work out the clients of each drone and the route of their delivery. For the clients whose goods are relatively light, each drone will take at least two missions. But for the part that is relatively far or hard to ship (because of the weight or volume), each drone will take one mission, for the villages that are not too far from the distribution center, the drone will take responsibility for their delivery work.

The specific delivery steps can be seen in Figure. 1:

/

Figure 1: Truck and Drone collaborative delivery model

Based on the understanding of the model, some assumptions need to be cared about:

All the goods are shipped from same the distribution center.

Both drones and trucks have their maximum loading limit, and drones have maximum flight limit.

The payload of drones will not affect their flight distance.

Every client will only be shipped at once by trucks or drones, no overlapping part exists.

No consideration on loading and unloading time spent.

Trucks keep still during the drones’ mission; every drone can execute more than one delivery mission.

3. Model Construction

Based on the mother-ship model and ant colony algorithm research, Figure 2 optimizes the definition of drone path setting as well as assigned good weights, goes through with multiple iterations to test the most cost-effective path setting and pick the elite operator from the cluster to test as service station, to make sure that products could be delivered safely.

Like the setting of the model in Figure 2, the frame will operate the following logic to execute:

:

Figure 2: The logic of truck-drone cooperative last mile delivery optimization

As Figure 2 shows, the model will follow the rule of ant colonial algorithm to set up the cooperation path setting of the truck and drone at the beginning of the whole flow. The system goes through the decode of the map and order locations’ distribution to set up the delivery group numbers and separate the mountainous rural parts into several areas. Then system will calculate the group of pending order weights and numbers to figure out the path of each drone and assign each truck corresponding drone numbers (2-3 drones). With the preliminary path setting design, the elite operator (the specific locations of delivery) will be picked out to be assumed as a service station to stimulate the total cost spent and affection on the whole trip. If this point could be iterated with lower values and point settings, the service station assumption would be updated until the iteration could not be continued. At last, these values will be recorded and imported into the system as optimized path settings to guide the whole trip setting as well as the movement of the whole system.

3.1. Period 1: Combined Path Optimization

Starting considered the design of the cooperative path, we need to apply with ant system to schedule the path of trucks and drones, following the defined parameters to design the path:

Parameters define:

N=rural village, A=(I,j)= Vector location of rural receiving point

\( \text{d}_{\text{ij}}\text{=} \) Euclidean distance between point i and point j

\( \text{τ}_{\text{ij}}\text{(t)} \) = Pheromone intensity between two points of i, j during delivery time(t)

\( \text{η}_{\text{ij}} \) =1/ \( \text{d}_{\text{ij}} \) =visibility of ant

All the points that exceed the maximum payload of the drones will be sorted to a tabu set W which will be delivered by trucks. Then randomly pick an ant k to generate the overall distribution path, this path will form a set M, the farthest point in this set may automatically be sorted to tabu W with the latest drones’ delivery points will be also put into this set.

All the points which need to be delivered will form a set \( \text{allow}_{\text{k}} \) ,

Then, follow the ant system, it has:

\( \text{P}_{\text{ij}}^{\text{k}} \) (t)= \( \begin{cases}\frac{\text{[}\text{τ}_{\text{ij}}(\text{t})\text{]}^{\text{α}}\text{×}\text{[}\text{η}_{\text{ij}}\text{]}^{\text{β}}}{\sum _{\text{n∈}\text{allow}_{\text{k}}}^{} \text{[}\text{τ}_{\text{in}}(\text{t})\text{]}^{\text{α}}\text{×}\text{[}\text{η}_{\text{in}}\text{]}^{\text{β}}}\text{ n∈}\text{allow}_{\text{k}}\text{ } \\ \text{0 n∈}\text{allow}_{\text{k}}\end{cases} \) (1)

With the justification of \( \text{P}_{\text{ij}}^{\text{k}} \) (t) shown in the formula above, the selection of ant K will be repeatedly processed until all the sets of \( \text{allow}_{\text{k}} \) are empty. Then a clear truck delivery path will be figured out.

The design of drones’ delivery path needs to be selected following the definition of the truck stop, so following the ant algorithm, the truck service station set has been defined as \( \text{T}_{\text{n}} \) ={ \( \text{t}_{\text{1}} \) , \( \text{t}_{\text{2}} \) , \( \text{t}_{\text{3}} \) , \( \text{t}_{\text{4}} \) ,… \( \text{t}_{\text{n}} \) }, the drone service station has been defined as set \( \text{D}_{\text{n}} \) ={ \( \text{d}_{\text{1}} \) , \( \text{d}_{\text{2}} \) , \( \text{d}_{\text{3}} \) , \( \text{d}_{\text{4}} \) … \( \text{d}_{\text{n}} \) }

Pick \( \text{t}_{\text{1}} \) as the first element of the gathering center set \( \text{G}_{\text{n}} \) to calculate the distance of all the elements in \( \text{D}_{\text{n}} \) and \( \text{t}_{\text{1}} \) , set as \( \text{a}_{\text{1}} \) . Then move to \( \text{t}_{\text{2}} \) following the same way to find \( \text{a}_{\text{2}} \) , pick min ( \( \text{a}_{\text{1}} \) , \( \text{a}_{\text{2}} \) ) from the set. Then repeat this step until all the elements in \( \text{T}_{\text{n}} \) have been processed.

At last, each drone delivery point is matched to the nearest truck service station. The UAV service points linked to each truck will be counted, and the straight-line distance between multiple UAV service points carried by a single truck will be measured as well. If the total delivery distance of multiple UAV service points carried by a single truck (including the distance between the truck service point and single UAV service point, the distance between two UAV service points) is lower than the maximum flight distance of the UAV under specific load, a single drone will generate a flight trajectory to connect several service points in series and perform good tasks.

3.2. Period 2: Detailed Path Optimization

Based on the combined path optimization setting, it also could involve the choices of elite ant operators to optimize the detailed path set. The algorithm can randomly select an appropriate elite ant operator D1 and K1 from \( \text{droneroute}_{\text{K}} \) and \( \text{truckroute}_{\text{K}} \) , put them into respective location pending removal sets \( \text{Removal}_{\text{D}} \) and \( \text{Removal}_{\text{K}} \) , and temporarily remove them out of the service path of drones and trucks. The corresponding coefficients between the drone and truck removal operators and the remaining service points will be calculated according to the following formula:

\( \text{R}_{\text{ij}} \) = \( \frac{\text{1}}{\text{D}_{\text{ij}}\text{+j}} \) ; \( \text{T}_{\text{ij}} \) = \( \frac{\text{1}}{\text{K}_{\text{ij}}\text{+j}} \) (2)

In this formula, \( \text{R}_{\text{ij}} \) and \( \text{T}_{\text{ij}} \) represent the coefficient of drone and truck operators, \( \text{D}_{\text{ij}} \) and \( \text{K}_{\text{ij}} \) represent the distance reciprocal of the specific operator (drone and truck) to the other service stations of \( \text{droneroute}_{\text{K}} \) and \( \text{truckroute}_{\text{K}} \) . For j in the formula, it just represents a constant, if the removal operator is settled on the same delivery path of \( \text{D}_{\text{ij}} \) and \( \text{K}_{\text{ij}} \) , j=1; otherwise, j=0. If one operator has finished this process, the algorithm will apply with the roulette way to pick the next factor until the major points on the path have been processed.

For the UAV service point optimization, the algorithm will select two delivery paths near the removal operator for insertion according to the specific location distribution and calculate the distance increment of these two paths after operator insertion. Then the algorithm will select the solution with a small distance increment to remain and compare whether the total load of goods after the operator insertion is still in the maximum loading range. If it exceeds the maximum load of UAV, the solution with a larger distance increment will be replace it to optimize the overall delivery path of UAV delivery.

For truck service points optimization, the algorithm will insert the removed operator into the truck delivery paths in sequence to calculate the distance increment after insertion and select the solution that meets the truck capacity requirements well to retain. All the path increments after operator insertion will be compared to help the system figure out the smallest incremental path, and this path will be remained to form the optimal solutions of the delivery route setting. Finally, the best truck delivery route will be figured under this mode will a complete calculation of each operator.

At last, the UAV optimal route and truck optimal route will involve together to form the best delivery route to ensure that both delivery cost and time spent can be controlled in the reasonable range.

3.3. Adaptive Model Adjustment of Ant Colony Pheromone

Involved with the combined path optimization and detailed path optimization, the UAV-trucks delivery path in mountainous areas really could be quantitatively optimized compared to a random path setting. However, if the overall delivery area is too broad or the total service points are too many, the algorithm will converge slower than regular and the relative path choices may be biased. In this case, the partial route allocation of specific UAV or truck may have a local distribution optimal solution but not for the overall delivery path setting. Therefore, the algorithm will compare the optimal solutions of each round after multiple cycles. If the optimal solution is too weak to optimize the overall path, the following pheromone formula will be involved to adjust the overall path setting:

\( \text{ρ}(\text{t})\text{= }\begin{cases}\text{0.95ρ}(\text{t-1})\text{ 0.95ρ}(\text{t-1})\text{\text{>}}\text{ρ}_{\text{min}} \\ \text{ρ}_{\text{min}}\text{ Others}\end{cases} \) (3)

In this formula, t means the number of iterations, and the system will apply with the setting of \( \text{ρ}(\text{t}) \) to adjust the rationality of the delivery path setting arrangement.

4. Discussion

Truck-UAV cooperative delivery model as an emerging distribution mode, after many rounds of pilot by different companies, it still has not been widely rolled out in large-scale form in various mountainous areas and towns. In addition to the consideration of technological development stability, the initial large-scale capital investment and overall return of investment(ROI) measurement have also become the main reasons why many enterprises still maintain a wait-and-see attitude under this wave. In general, the cost of a single ride of the Truck-UAV cooperative model for unit distance pickup and delivery is about 693.42 yuan, although the cost is 21.91% lower than the cost of truck or drone independent delivery at the same distance and destination, considering the upper limit of the overall loading range and the lower cost of human distribution, most of the mountain towns still maintain the form of human distribution to solve the problem of last mile delivery [9]. Therefore, if this model wants to take full advantage of the technical wave to be widely applied in rural or mountainous areas, both financial support and policy support from local governments are indispensable.

5. Conclusion

Looking back on the optimization of truck-drone collaborative delivery algorithm, this paper makes full use of operator implantation of hybrid ant colony algorithm to strategically optimize both the overall delivery path and detailed delivery path as well as completes the final convergence test and operator iteration of this model based on adaptive pheromone implantation. Since this model right now is still in the stage of rapid development and iteration, the upper load limit of the UAV in this model and the movable recycling of the UAV last-mile delivery (after the delivery is completed, the movable truck service station which is nearest to UAV final distribution point will work for UAV recycling). With the significant increase of e-commerce development, the truck-drone collaborative last-mile delivery model will be rapidly iterated and used in the next decade.