Ride-Sharing Systems (RSS) have emerged as a promising approach to providing better urban transportation services since they are effective in saving cost, efficient in relieving traffic congestion, and sustainable in increasingly crowded cities. In a typical RSS, passengers with matching itineraries and schedules can share their trips by a single vehicle. In practice, riders in RSS are not limited to human passengers but could be small vehicles. For example, delivery companies allow unmanned aerial vehicles (UAVs) to ride on big trucks to save energy in their travel of last-mile delivery services. Centering around ride-sharing, we not only exploit the efficiency of ride-sharing in passenger delivery but also explore the effectiveness of ride-sharing in UAV travelling. More specifically, we pursue approximation and online algorithms that guarantee good worst-case performance in offline and online settings of the problems.

To begin with, one central issue of RSS is studied to assign drivers of vehicles to service passengers with the overall moving distance among all the vehicles minimized. To tackle the problem in the offline setting where complete information about both vehicles and passengers is given beforehand, we introduce some variants of the minimum-weight perfect matching problem. Built upon solutions to these matching problems, we propose an O(n⁴)-time 2.5-approximation algorithm and a dynamic assignment algorithm for restricted and general settings, respectively. Further, we extend our algorithm to the online setting where passengers submit their trip requests over time. We show by experiments that our algorithms achieve good performances in practice.

The second aspect is about ride-sharing in UAV travelling. In the most fundamental setting, we explore how a single UAV can save the most flying distance from hitching trucks while disregarding the UAV and trucks' energy and time constraints. To this end, we model the problem into the online maximum coverage problem on a line that aims to select at most k sub-intervals from an online sequence to achieve the maximum coverage over a given target interval. We comprehensively study different cases of the problem. For the offline setting, we propose a dynamic programming-based optimal algorithm. For the online setting, we derive lower bounds on the competitive ratio for the problem and explore both single-threshold-based and double-threshold-based deterministic online algorithms. Moreover, We show that more thresholds cannot induce better performance than our proposed algorithms as long as they are used in non-increasing order to accept sub-intervals.

Finally, we investigate how a single UAV could achieve the minimum overall travel time by hitching trucks halfway, in which time and energy constraints of both the UAV and trucks are further involved. Based on some inherent features of the problem, we formulate the problem mathematically, capturing well constraints in hitching rides. For the offline version of the problem, we first derive properties of an optimal solution, built upon which we present an O(n²)-time shortest-path-like optimal solution. For the online setting where trucks inform the UAV of their trip information some certain time Δt beforehand, we construct lower bounds on the competitive ratio for different cases. Then, we show that a greedy algorithm has a defect leading to negligible energy saved from hitching rides. Further, we propose a Δt-Adaptive algorithm by tolerating a waiting time at most (Δt)/2 in hitching a ride, which is proved to be asymptotically optimal in the sense that its ratio approaches the proposed lower bounds as Δt increases.