Incentive Mechanism and Path Planning for UAV Hitching over Traffic Networks

In recent years, the continuous expansion of the e-commerce market has promoted the rapid development of the express logistics industry [1]. Especially during the epidemic, people’s living habits have changed dramatically in order to maintain social distance. New logistics service models have emerged in order to avoid face-to-face contact, such as non-contact delivery [2]. However, the rapid development of urban logistics has also brought a series of problems, such as traffic congestion, air pollution, low logistics efficiency [3]. Due to its agility and mobility, the delivery services enabled by the Unmanned Aerial Vehicle (UAV) are not restricted by terrain and traffic conditions, which can freely pass through urban region during rush hours to provide logistics services flexibly and efficiently. Many companies all over the world have launched commercial UAV delivery services, such as Amazon, Google, and UPS in the United States, DHL in Germany, and JD, SF-express in China [4]. However, due to the limitation of UAV energy capacity, current UAV logistics services are limited to short-distance delivery [5]. Therefore, how to expand the range of UAV delivery services is an urgent problem to be solved.

With the development of new technologies such as 5G, Internet of Things (IoT), and Artificial Intelligence (AI), crowdsourcing, as a mode of using large-scale network users to assist in specific tasks, has received more and more attention from different application platforms, and has been widely used in various scenarios, such as food delivery riders, car sharing, and data cleaning, etc [6]. Inspired by the crowdsourcing model, the ground vehicles such as trucks can be utilized to offer riding for the UAVs, which greatly saves the battery consumption of UAVs and extend their delivery distance. Amazon has proposed a UAV-truck riding strategy to allow UAVs to land on transportation vehicles from different shipping companies for temporary transport, by making an agreement with the owner of the transportation vehicles [7]. In addition, the technology of docking UAVs on stationary or high-speed moving vehicles is relatively mature [8, 9], which lays the foundation for the development of air-ground collaborative multimodal logistics system.

However, this new multimodal logistics system based on crowdsourcing faces the following challenges:

• •

  Incentives for ground vehicles’ cooperation. The provision of hitch services by ground vehicles is the basis for the implementation of multimodal logistics systems. However, the ground vehicles incur hitching costs (e.g., fuel consumption) when offer riding service, and they should be rewarded and well motivated to assist UAV delivery. Moreover, the ground vehicles are heterogeneous in nature. They will randomly arrive the targeting interchange point and their private costs for offering riding service are different and unknown. Thus, the pricing design under the incomplete vehicle information is challenging. In addition, a higher monetary reward leads to a shorter vehicle response time (i.e., UAV waiting time), which improves the delivery efficiency of multimodal logistics system. For sustainable management of the multimodal logistics system, the pricing strategy should be dynamic to best balance the payment to ground vehicles and their response time.

• •

  Crowdsourcing-based multimodal logistics system modeling under time-varying traffic networks and UAV energy constraint. By integrating the UAVs with the ground vehicles, the UAVs should decide where to hitch on ground vehicles and whether hopping between different vehicles to complete one delivery task, which creates large number of interchange points on the basis of the road network for path planning. Moreover, due to the mobility of ground vehicles and the instability of traffic conditions, the modeling of the integrated system is challenging.

• •

  Design of fast and efficient task allocation and path planning algorithms for the multimodal logistics system. The ground vehicles’ arrivals and response time in the vicinity of the UAVs at a certain time are unknown. In addition, the path planning of the UAVs should be carefully designed to prevent conflicts between UAVs, such as multiple UAVs landing at the same vehicle at the same time. Such combinatorial optimization problems are often NP-hard problems and challenging to solve.

To tackle the above challenges, a two-stage model is proposed to jointly analyze the incentive mechanism design for ground vehicles and path planning for UAVs. We summarize our main contributions as follows:

• •

  Crowdsourcing-based multimodal logistics system modeling. To our best knowledge, this paper is the first work studying the crowdsourcing-based multimodal logistics system, in which the ground vehicles are invited to offer hitching services for UAVs. Such multimodal logistics system effectively extends the range and efficiency of UAV deliveries. We formulate this system as a two-stage model to jointly study the incentive mechanism design for ground vehicles and path finding for UAVs. In Stage I, a dynamic pricing scheme is proposed to motivate the ground vehicles to assist UAV delivery under the incomplete information about the ground vehicles’ random arrivals and private hitching costs. In Stage II, the task allocation and path planning of the UAVs over traffic network by considering the UAV energy constraint and the conflicts between UAVs.

• •

  Dynamic pricing for ground vehicle under incomplete information. To balance the payment to ground vehicles and their response time for efficient delivery, a optimal dynamic pricing scheme is proposed under incomplete information case regarding ground vehicles’ random arrivals and private hitching costs. We prove that if the vehicle response time is long, a high price offer should be decided to encourage the ground vehicles to assist delivery. According to the proposed dynamic pricing, the vehicle response time for each interchange station can be predicted and utilized for the path planning in Stage II.

• •

  Algorithm Design for fast and efficient task allocation and path planning. To reduce the computation complexity, the deployment of UAV delivery tasks is split into two layers. In task allocation layer, we propose a near-optimal algorithm with polynomial computation complexity to generate the delivery sequence. In path planning layer, to avoid the computational burden due to the order-of-magnitude increase in conflicts, we propose a conflict avoidance-based path search algorithm and prove that the bounded suboptimal paths for all UAVs can be obtained in polynomial time.

The access path planning problem for UAVs can be viewed as the Traveling Salesman Problem (TSP) [10, 11]. This type of combinatorial optimization problem is a classical NP-hard problem. Once the order of package delivery for all UAVs is found, the system begins to find the optimal delivery path for each UAV. Classical algorithms such as $\text{A}*$ or Dijkstra for solving the shortest path are often used to solve the optimal UAV trajectory problem [12, 13]. In addition, control theory is also utilized for modeling and solving UAV path planning problems [14, 15]. The constraints of UAV energy storage and conflicts between UAVs make the UAV path planning problem more challenging, which is NP-hard to get the optimal solution. Some methods such as Conflict-based search (CBS) [16], have been shown to be efficient methods to solve this Multi-Agent Path Finding (MAPF) problem.

Utilizing the ground vehicles to extend the UAVs’ delivery range has attracted wide attentions from both academia and industry. The researchers in Stanford University have shown that combining UAVs with the existing transit network can increase the delivery coverage of UAVs by up to $360\%$ [17]. However, using buses for UAV delivery lacks fault tolerance. For example, the bus schedules may not be accurate. If the UAV happens to miss the arrival time of the current bus, the UAV needs to wait longer for the next bus to arrive, or has to change its route, which may cause the delivery task to fail. In the crowdsourcing-based system considered in this paper, the request is sent to the ground vehicle at the time when the UAV needs the hitching service and any passing-by ground vehicle along the UAV’s routes can be the UAV carrier, so there is no case of missing a vehicle. E-commerce giant Amazon has proposed in its patent that commercial vans from different operators can be used to assist UAVs in delivery services [7]. However, this is also based on the pre-signed agreement with the van operators. The number of available commercial vans is limited and cannot cover the entire transportation network, which will greatly reduce the efficiency of UAV delivery. In this paper, the ground vehicles (such as trucks, buses) with wide coverage are added to the logistics network based on crowdsourcing technology, which helps keep the waiting time for UAVs to a minimum.

The rest of this paper is organized as follows. The system model is given in Section II, in which the multimodal logistics system is formulated as two stages. In Section III, the incentive mechanism for the crowdsourcing-based hitching services is designed in Stage I. Sections IV and V discuss the task allocation and multi-agent path finding for the UAVs in Stage II. Section VI validates our results via simulations. Section VII concludes this paper.

Consider a logistics system with $N$ UAVs performing delivery tasks to $M$ known delivery addresses from $K$ depots. Denote the set of $M$ delivery addresses as $V_{G}=\{g_{1},\dots,g_{M}\}\subset\mathbb{R}^{2}$ and the set of $K$ depot locations as $V_{D}=\{d_{1},\dots,d_{K}\}\subset\mathbb{R}^{2}$. We assume that any package can be dispatched from any depot and the depot can also charge or change the battery of the UAV quickly. When a UAV delivers a package from a depot to a delivery location, the UAV can call a vehicle on the ground to provide a hitch service, which significantly extends the UAV’s delivery range. In order to facilitate management, we specify that the UAV can stop and wait for ground vehicles only at specific interchange points equipped with surveillance cameras for safety’s sake. We generate $L$ potential interchange routes on the traffic network starting and ending at certain interchange points, where the UAV can wait for ground vehicles while performing delivery tasks. The set of interchange points is denoted as $V_{I}=\{i_{1},\dots,i_{L^{{}^{\prime}}}\}\subset\mathbb{R}^{2}$ ($L^{{}^{\prime}}\leq L$).

In the crowdsourcing-based multimodal logistics system, the goal is to (i) design the optimal dynamic pricing to deal with the tradeoff between the payment to ground vehicles and UAVs’ waiting time; (ii) find the delivery path of each UAV to deliver all packages in a reasonable combination of UAVs’ own flight path and transit routes on the traffic network, while minimizing the maximum delivery time for each UAV without exceeding the storage capacity limit of the UAV.

In a crowdsourcing-based air-ground collaborative logistics system, the behavioral decisions of the ground vehicles will affect the UAV transportation efficiency. If the UAV waits long time for the ground vehicles’ response to assist in transportation, the passage time of the corresponding road section will be prolonged, which will lead to the delay of UAV mission completion time. Therefore, it is crucial to design an effective crowdsourcing incentive mechanism to encourage the ground vehicles to assist delivery. The passage time of each road section will also influence the design of subsequent task allocation and path planning algorithms. However, higher incentives can shorten the UAV waiting time, but cause an increase in UAV platform’s cost. Therefore, we will design a dynamic pricing scheme to best balance the reward expenditure to ground vehicles and the expected vehicle response time of each road section.

Completing all package delivery requests means that each package needs to be assigned to one and only one UAV. So this problem can be viewed as a variation of the traveler problem. Because of the limitations of UAV carrying capacity and energy storage, we specify that a UAV can only deliver one package at a time and return to some depot for charging after completing the delivery task (charging time for UAVs is ignored here). The delivery time of a package by a UAV consists of the UAV flight time and the ride time including the vehicle response time (i.e., UAV waiting time) and the vehicle traveling time when carrying the UAV. We describe the energy storage limit of each UAV as a maximum flight time constraint, and each UAV must not exceed the maximum flight time when performing its delivery tasks. In addition, to avoid collisions between UAVs, multiple UAVs can’t land at the same interchange point at the same time. The above joint optimization problem for UAV-vehicle path planning can be modeled as mixed integer linear programming. However, most of the existing mixed integer linear programming algorithms can only handle small-scale models, which are not suitable for large number of UAVs/packages and vast traffic network scenarios. We decompose the joint path planning problem into two layers of decision models for discussion, and design algorithms with low computational complexity at each layer, respectively.

We formulate our multimodal logistics system as two stages as shown in Fig. 1. In stage I, we predict the vehicle response time at each interchange point based on our designed dynamic pricing scheme, and update this information into the time weights of the interchange routes in the traffic network for the following path planning. In Stage II, we first analyze the task allocation of UAVs to solve the problem of which UAV delivers which packages and the order of delivery between packages, and then the path finding for each delivery subtask. To be specific, for task allocation in Layer 1, we temporarily ignore the specific route of the UAV from the depot to the package delivery address. We only decide which packages are sent from which depot and which UAV is responsible for which series of packages to be delivered, depending on the estimated time (the shortest path from a certain depot to the destination) between the depot and delivery location. We use linear programming algorithms with relaxation conditions that accomplish the task allocation problem in polynomial time. For path finding in Layer 2, we take one UAV to deliver a package from a depot and then return to a depot as a subtask, and perform route planning for the UAV fleet to execute the allocated delivery subtask. To avoid collisions between multiple UAVs, only a limited number of UAVs are allowed to stay at each interchange. We adopt the idea of CBS to design an efficient MAPF algorithm called conflict avoidance-based path search (CABPS), i.e., each UAV jointly maintains the same list of interchange occupancy information and performs its own path planning based on this constraint.

In Stage I, we motivate the ground vehicles to offer riding for UAVs by proper incentive mechanism design, e.g., monetary reward. However, the ground vehicles are mobile and their private costs for carrying the UAVs for certain distance is unknown. Under this circumstance, the waiting time for the UAVs to call for ground vehicles at different interchange points at different time is variable and unknown. In the following, we design a dynamic pricing scheme to balance the response time of ground vehicles and the monetary payment under the incomplete information about the ground vehicles’ random arrivals at certain interchange point and private carrying costs. On the basis of the designed dynamic pricing scheme, the expected response time of ground vehicles at each interchange can be generated, which will be taken into consideration when performing path planning for each UAV.

In Stage II, we propose a comprehensive algorithm UAV-Task-Allocation-Path-Planning for building an efficient air-ground cooperative multimodal logistics system. It guarantees a near-optimal solution in polynomial time. Our goal is to plan delivery paths for $N$ UAVs after accepting requests for $M$ packages.

The detailed design is given in Algorithm 1. Denote the traffic network graph as $G_{T}=(V_{T},E_{T})$, where the vertex set $V_{T}=V_{G}\cup V_{D}\cup V_{I}$, and each directed edge $(u,v)$ for every $u,v\in V_{T}$ contains a weight $w_{uv}$ denotes the passage time from $u$ to $v$ and an attribute $a_{uv}$ denotes the power consumption of the UAV from $u$ to $v$. We divide the directed edges $(u,v)$ into two types, one is the flight edge, which indicates that the UAV flies from $u$ to $v$. The other is the transit edge, which indicates that the UAV hitches a ground vehicle from $u$ to $v$. It is worth mentioning that if the directed edge $(u,v)$ is a transit edge, its power consumption $a_{uv}$ is $0$. Relatively, it has a longer passage time $w_{uv}$ (the passage time from $u$ to $v$ includes the UAV’s waiting time and the carrying time from $u$ to $v$) than the flight edge.

Layer 1 (line 1): Task Allocation is the first layer of our algorithm, which takes the traffic network graph $G_{T}$, the set of depot location $V_{D}$, the set of package locations $V_{G}$, and the number of UAVs $N$ as inputs, returns the set of UAV paths $O$, where $O_{n}^{i}$ indicates the $i^{th}$ delivery subtask for the $n^{th}$ UAV. Each subtask $O_{n}^{i}$ consists of three values: starting depot, package address and returning depot.

Layer 2 (lines 2-10): The second layer Multi-Agent-Path Finding uses the Conflict Avoidance Based Path Search (CABPS) algorithm to calculate the path for each UAV separately. CABPS takes the $i^{th}$ subtask $O_{n}^{i}$ delivered by the $n^{th}$ UAV, the current waiting time estimate for each interchange and the occupancy time of each interchange as inputs, it gives the specific delivery path $P_{n}^{i}$ for each UAV’s subtask $O_{n}^{i}$.

Our system eventually returns the set of delivery path $P$ for all UAVs. $P_{n}^{i}$ refers to the path planned by the $n^{th}$ UAV performing its own $i^{th}$ delivery subtask, and we use $\text{Time}({P_{n}})$ to indicate the total time taken by the $n^{th}$ UAV to complete all its delivery tasks. The purpose of our algorithm is to minimize ${\max}_{n\in N}\text{Time}({P_{n}})$. Note that in the second layer of the algorithm, the paths for all delivery subtasks of the UAVs are not computed simultaneously. The delivery subtask of each UAV is computed successively once the previous subtask is accomplished, by considering the conflicts between UAVs. In the following sections, we will describe the design of the dynamic pricing mechanism and the two-layer algorithms in more detail.

This section focuses on the first layer of the stage II. We design the UAV task allocation scheme to traverse all packages and minimize the maximum delivery time of each UAV. Package nodes $V_{G}$ and the depot nodes $V_{D}$ in the traffic network graph $G_{T}$ are picked out to generate the task allocation graph, which is denoted as $G_{A}=(V_{A},E_{A})$, where the set of vertices $V_{A}=V_{G}\cup V_{D}$, and the weight $w_{uv}$ of directed edge $(u,v)\in E_{A}$ is the predicted passage time from position $u$ to position $v$. We run the shortest path search algorithm in the traffic network graph $G_{T}$ to obtain the predicted passage time $w_{uv}$ between all points of the task allocation graph $G_{A}$. We solve such a problem in $G_{A}$ to find a shortest path to access all packages, which means we find the delivery sequence of all packages and it has the smallest total predicted passage time.

This layer aims to design the task allocation scheme $P_{n}=d_{1}g_{1}d_{2}g_{2}\dots d_{k}g_{k}d_{k+1},n\in\{1,\dots,N\}$ to minimize the longest UAV task completion time, i.e., $\min{\max}_{n\in N}\text{Time}(P_{n})$, where $\text{Time}(P_{n})$ is the total time for the $n^{th}$ UAV to complete the corresponding package delivery service and return to depot $d_{k+1}$ under task allocation $P_{n}$ from depot $d_{1}$ in delivery order $\{g_{1},\dots,g_{k}\}$. Task allocation $P_{n}$ contains the information of which UAV delivers which packages and the delivery order. To find the task allocation scheme for $N$ UAVs, we first consider the minimum connection tours (MCT) problem that connects all packages:

where constraint (25) indicates that each package address $g\in V_{G}$ must be visited once and comes from one depot, and the UAV must return to one depot after completing delivery. Constraint (26) indicates that the UAVs entering and exiting each depot are equal, which paves the way for subsequently transforming this problem into a minimum cost circulation problem and designing algorithms in polynomial time. Constraint (27) indicates that the edge connected to the package address is used at most once. The last constraint (28) indicates that multiple round trips between depots are possible.

The detailed design is given in Algorithm 2, in which we aim to minimize the sum of the estimated passage time between depots and packages while ensuring that each package is dispatched by one and only one depot.

SubGraph. At the task allocation layer, we seek a set of $N$ paths that minimize the maximum delivery time of any UAV. Here we ignore the specific routes from the depot to the package and only consider how they are connected. A new task allocation graph $G_{A}$ is generated from the network $G_{T}$ based on the known geographic locations of depots and packages, $G_{A}$ contains only the nodes of depots and packages, and the weights between them are the estimated passage times between the two locations.

MinimumCostCirculation (MCC). The problem $P1$ can be viewed as an $N$ minimal visiting paths problem[11] and is NP-hard. Note that the structure of the minimal visiting paths problem is very similar to the MCC problem, and the latter can be solved by a polynomial-time algorithm[18]. In problem $P1$, $x_{uv}$ indicates the number of times to select the edge $(u,v)$, which is an integer. To reduce the computational complexity of the linear programming problem, we transform the integer constraints of the combinatorial optimization problem $P1$ into real numbers, thus transforming the problem into a MCC problem for analytical solution. Finally, we divide the minimum connected path obtained by linear programming into $N$ paths for each UAV.

GetStrongConnectedComponent. The solution $X=\{x_{uv}$, $u$, $v\in V_{A}\}$ given by MCC shows the number of times the edge $(u,v)$ is used in the task allocation graph $G_{A}$. The depot nodes are connected to the package nodes according to the edges used and forming multiple connected components. Then we combine all the connected components to generate the entire connected graph, which has edges covering the trips we need to traverse all the packages with the least cost.

SplitTours. After obtaining the trip that traverses all the packages with minimum cost, we distribute it evenly among all the UAVs. Evenly means that the estimated time of package delivery undertaken by each UAV is close to the total estimated time divided by the total number of UAVs $N$. The estimated package delivery time is not equivalent to the actual UAV delivery time. The time spent by the UAV includes the flight time, carrying time (hitching time), waiting time (vehicle response time), and the time spent by the UAV for conflict resolution.

Since we relax the variable $X=\{{x_{uv},u,v\in V_{A}}\}$ in linear programming from an integer constraint to a real number constraint, the MCT problem is converted to a MCC problem. For the MCC problem, we can compute an integer optimal solution in polynomial time[18, 19].

Our goal is to minimize the maximum delivery time of UAVs, by returning the set $P={P_{1},...,P_{N}}$, where $P_{n}$ indicates the sequence of package delivered by the $n^{th}$ UAV. Then our objective can be expressed as

Let the optimal task allocation set be $\widetilde{P}=\{\widetilde{P_{1}},\dots,\widetilde{P_{N}}\}$, where $OPT:={\max}_{n\in N}\text{Time}(\widetilde{P_{n}})$. In the task allocation algorithm, linear programming usually returns more than one connected component, and we aim to find the minimum weights of the edges between depots to connect different connected components, which finally generates a strongly connected path over the graph. Such a path $T$ traverses all the packages from a depot and then back to a depot, and contains the newly added edges (the depot to another depot), which makes our result slightly deviate from the optimal solution. We observe that

where $|T|$ is the total weights of the paths $T$ and $\alpha$ is the number of times to merge the connected components. We assign a task to each UAV by specifying that its package delivery prediction time is less than the total prediction time divided by total number of UAVs $N$. The worst outcome of this is that a UAV is assigned an additional task after it has been assigned exactly the average prediction time, such that we can derive that

We find that the predicted time undertaken by any one UAV in this layer of the algorithm does not exceed the average predicted time plus the estimated time for one maximum package delivery time. Combining the above equations, we finally get the gap between our results and the optimal solution:

where $\beta:=\frac{a}{N}\mathop{\max}_{d,d^{{}^{\prime}}\in V_{D}}(w_{dd^{{}^{\prime}}}+w_{d^{{}^{\prime}}d})$, $\gamma:=\mathop{\max}_{d,d^{{}^{\prime}}\in V_{D},g\in V_{G}}(w_{dg}+w_{gd^{{}^{\prime}}})$. Obviously, as the number $N$ of UAVs and the number $M$ of package delivery requests rises, our result gets closer to the optimal solution and solves in polynomial time.

In a direct flight network, UAVs are utilized for delivering packages without the help of ground vehicles. In this case, we consider that the UAVs deliver packages by flying from the depot to the package address directly, and thus the delivery time of a UAV is equal to the straight-line distance from the depot to the package address divided by the UAV’s average flight speed. Though delivering directly by UAVs saves a lot of time especially during peak hours or in an a complex geographical environment, the energy limitation of the UAVs has restricted their service range. In the direct flight network, for each package delivery request executed by the UAV, we need to consider the constraint that whether the flight distance consumed in the whole journey exceeds its own limit. When the UAV cannot reach the designated location, we consider the delivery mission to fail. The multimodal logistics system can solve the flight distance limitation of direct flight network, and we compare the mission delivery failure rates of the three networks in Section VI later.

In a single-hop hitch network, the UAV hitch on a ground vehicle only once during the journey. For a delivery subtask of $dgd^{{}^{\prime}}$, the UAV can depart from the depot $d$, fly to the interchange point $i$ to wait and hitch on the vehicle through the transit section $r=(i,j)$, and then fly from $j$ to the delivery destination $g$. After completing the subtask, it returns to the depot $d^{{}^{\prime}}$ in order to perform the next subtask. Denote the passage time of the UAV from the depot to the package address be $T_{n,r,dg}=t^{{}^{\prime}}_{di}+t_{ij}+t^{{}^{\prime}}_{jg}$, where $t^{{}^{\prime}}_{di}$ and $t^{{}^{\prime}}_{jg}$ are the corresponding UAV flight time (which can be obtained from the UAV speed) and $t_{ij}$ is the ride time. Based on the crowdsourcing incentive mechanism, the vehicle response time for the transit section $r=(i,j)$ is predicted to be $\overline{W}_{i}$. So the ride time is $t_{ij}=\overline{W}_{i}+t^{v}_{ij}$, where $t^{v}_{ij}$ is the vehicle passage time for section $r$ (which can be obtained from the average vehicle speed). We decompose one delivery subtask into two segments $dg$ and $gd^{{}^{\prime}}$. The transit sections $r$ and $r^{{}^{\prime}}$ can be the same or different sections. The transit sections are directed edges and the set of all transit sections is $P_{r}$. With the objective of minimizing delivery subtask completion time, the UAV hitch problem is modeled as

where constraint (34) indicates that the UAV that selects a transit section $r$ cannot exceed its capacity $C_{r}$ (no more than $C_{r}$ UAVs can stay at an interchange point at the same time), thereby avoiding UAV conflicts. The constraint (35) indicates that only one transit section can be selected from $d$ to $g$ and from $g$ to $d^{{}^{\prime}}$. And constraint (36) indicates that the total flight time of the UAV cannot exceed its maximum flight time $\overline{T}$, where ${t^{{}^{\prime}}_{n,r,dg}}$ is the flight time of the UAV $n$ that selects section $r$.