Efficient algorithms for ride-hitching in UAV travelling

The unmanned aerial vehicle (UAV) has emerged as a promising solution to provide delivery and other mobile services to customers rapidly, yet it drains its stored energy quickly when travelling on the way and (even if solar-powered) it takes time for recharging on the way before reaching the destination. To address this issue, existing works focus more on UAV's offline path planning with designated system vehicles providing charging service. Nevertheless, in some emergency cases and rural areas where system vehicles are not available, public vehicles can provide more cost-saving and feasible service in UAV travelling. In this paper, we explore how a single UAV can save flying distance by exploiting public vehicles for the purpose of minimizing the overall travel time of the UAV, which is from the perspective of online algorithm. For the offline setting where the information of future vehicles is known far ahead of time, we present an O(n²)-time shortest-path-like optimal solution by delicately transforming the problem into a graph capturing both time and energy constraints. For the online setting where public vehicles appear in real-time and only inform the UAV of their trip information some certain time Δt beforehand, we first construct lower bounds on the competitive ratio for different Δt. Then, we propose two online algorithms, including a greedy algorithm MYOPICHITCHING that greedily hitches truck rides and an improved algorithm Δt-ADAPTIVE that further tolerates a waiting time in hitching a ride. Our theoretical analysis shows that Δt-ADAPTIVE is asymptotically optimal in the sense that its ratio approaches the proposed lower bounds as Δt increases.