Incentive Mechanism and Path Planning for UAV Hitching over Traffic Networks

Ziyi Lu, Na Yu, Xuehe Wang

Abstract

Package delivery via UAVs is a promising transport mode to provide efficient and green logistic services, especially in urban areas or complicated topography. However, the energy storage limit of the UAV makes it difficult to perform long-distance delivery tasks. In this paper, we propose a novel multimodal logistics framework, in which the UAVs can call on ground vehicles to provide hitch services to save their own energy and extend their delivery distance. This multimodal logistics framework is formulated as a two-stage model to jointly consider the incentive mechanism design for ground vehicles and path planning for UAVs. In Stage I, a dynamic pricing scheme is proposed to best balance the vehicle response time and payments to ground vehicles. In Stage II, the task allocation and path planning of the UAVs over traffic network is studied based on the vehicle response time obtained in Stage I. To address pathfinding with restrictions and performance degradation due to conflicts, we propose the suboptimal conflict avoidance-based path search (CABPS) algorithm, which has polynomial time complexity. Simulations show that our approach increases the success rate of UAV package delivery and is twice as fast as ground-only delivery even in pessimistic cases.

Introduction

Unmanned Aerial Vehicles (UAVs) offer a fast and agile solution for modern logistics, yet their operational utility is severely limited by battery capacity. While existing research has explored using public transit for "hitching," these systems lack the flexibility of crowdsourced ground vehicles. This paper addresses the challenges of integrating UAVs with private traffic networks, focusing on two critical hurdles: creating effective incentives for drivers and managing the computational complexity of multi-drone path planning.

Methodology

The proposed framework is structured into two sequential stages that bridge the gap between economic incentives and technical pathfinding.

The two-stage framework: Stage I focuses on ground vehicle incentives, while Stage II handles UAV task allocation and pathfinding.

Stage I: Dynamic Incentive Mechanism

To motivate private drivers to participate in the hitching network, the system employs a dynamic pricing scheme. Using dynamic programming, the platform calculates rewards based on traffic density and driver costs. The primary goal is to minimize vehicle response time—the time a drone spends waiting for a ride.

Dynamic price $p(t)$ convergence over time, demonstrating how the system stabilizes rewards to balance platform costs and drone waiting times.

As illustrated in Figure 2, the price $p(t)$ converges to a steady state. If response times increase, the system automatically raises the price to attract more vehicles, ensuring the logistics network remains efficient.

Stage II: Task Allocation and Path Planning

Once waiting times are estimated, the system plans the delivery routes in two layers:

  1. Task Allocation: This layer determines which drone handles which package. By simplifying the problem into a Minimum Cost Circulation (MCC) model, the system achieves polynomial-time complexity, enabling real-time processing of large-scale tasks.
  2. Pathfinding (CABPS): The Conflict Avoidance-Based Path Search (CABPS) algorithm is used to navigate the traffic network. Unlike traditional global optimization, CABPS plans paths successively, treating previously scheduled routes as occupied time-intervals at interchange points. This approach prevents collisions while maintaining high computational speed.

Results and Discussion

The framework was evaluated using simulated traffic networks with up to 846 nodes and 600 packages. Key findings include:

  • Range Extension: The multi-hop hitching strategy achieved a 325% increase in delivery success rates compared to direct-flight methods, which often failed due to battery exhaustion.
  • Speed: Even in "pessimistic" scenarios with high wait times, the multimodal system remained twice as fast as traditional ground-only delivery.
  • Scalability: Task allocation for 600 packages was completed in just 6 seconds, proving the system's viability for large-scale urban operations.
  • Conflict Mitigation: Increasing the capacity of interchange points significantly reduced total delivery time by minimizing "waiting-for-clearance" delays.

Conclusion

This research demonstrates that hitching UAVs on ground vehicles is a powerful method for overcoming energy constraints in drone logistics. By combining dynamic economic incentives with efficient path-planning algorithms, the proposed system offers a scalable and effective solution for urban delivery. Future work will investigate the impact of battery charging times and more flexible docking mechanisms to further improve operational flexibility.

Summary updated

Abstract

Package delivery via the UAVs is a promising transport mode to provide efficient and green logistic services, especially in urban areas or complicated topography. However, the energy storage limit of the UAV makes it difficult to perform long-distance delivery tasks. In this paper, we propose a novel multimodal logistics framework, in which the UAVs can call on ground vehicles to provide hitch services to save their own energy and extend their delivery distance. This multimodal logistics framework is formulated as a two-stage model to jointly consider the incentive mechanism design for ground vehicles and path planning for UAVs. In Stage I, to deal with the motivations for ground vehicles to assist UAV delivery, a dynamic pricing scheme is proposed to best balance the vehicle response time and payments to ground vehicles. It shows that a higher price should be decided if the vehicle response time is long to encourage more vehicles to offer a ride. In Stage II, the task allocation and path planning of the UAVs over traffic network is studied based on the vehicle response time obtained in Stage I. To address pathfinding with restrictions and the performance degradation of the pathfinding algorithm due to the rising number of conflicts in multi-agent pathfinding, we propose the suboptimal conflict avoidance-based path search (CABPS) algorithm, which has polynomial time complexity. Finally, we validate our results via simulations. It is shown that our approach is able to increase the success rate of UAV package delivery. Moreover, we estimate the delivery time of the UAV in a pessimistic case, it is still twice as fast as the delivery time of the ground vehicle only.
BibTeX
@misc{lu2022incentive,
  author = {Ziyi Lu and Na Yu and Xuehe Wang},
  title = {{Incentive Mechanism and Path Planning for UAV Hitching over Traffic Networks}},
  year = {2022},
  eprint = {2210.00490},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.00490},
}
Figure