Efficient algorithms for ride-hitching in UAV travelling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)140-156
Journal / PublicationTheoretical Computer Science
Volume929
Online published28 Jun 2022
Publication statusPublished - 11 Sep 2022

Abstract

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 (n2)-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.

Research Area(s)

  • Energy efficiency, Online algorithm, Ride-hitching, Unmanned aerial vehicle