AI Research Portal

This paper addresses the RIDE-SHARING ASSIGNMENT PROBLEM (RSAP), which involves assigning a set of transportation requests to a fleet of vehicles to minimize total travel distance while respecting vehicle capacity constraints. The core idea is to develop new approximation algorithms with provable guarantees for two cases: when the number of requests equals the total vehicle capacity (n = mk) and when it is less than the total vehicle capacity (n < mk). The main empirical claim is that the proposed algorithms consistently outperform the previously best-known algorithm (LADG) in terms of solution quality, particularly when the vehicle capacity 'k' is not a power of 2.

The paper identifies several bottlenecks and challenges in ride-sharing assignment:

Computational Complexity: Efficiently matching passengers with vehicles and planning feasible routes under real-world constraints gives rise to computationally complex optimization problems. The RSAP is NP-hard even for k = 2.
Limited Approximation Guarantees: Previous algorithms for the n = mk case had an O(√k) approximation ratio only when k was a power of 2, with an incomplete analysis for general k, and failed to achieve constant-factor approximation for k = 3 in some instances. For non-power-of-2 values of k, the best known ratio remained 2k-1.

The paper claims the following main contributions:

Improved Algorithms for n = mk: Two new algorithms, ALG.1 and ALG.2, are proposed for the case where n = mk. ALG.1 achieves an approximation ratio of O(√k), which is O(n) in the worst case. ALG.2 achieves an approximation ratio of O(√(n/k)). By taking the better of the two, a min{O(√k), O(√(n/k))}-approximation algorithm is obtained, which is at most O(n) in the worst case, improving upon previous O(√k) for k being a power of 2 and 2k-1 otherwise.
First Non-Trivial Algorithm for n < mk: A new algorithm, ALG.3, is presented for the case where n < mk, achieving an approximation ratio of O(√k log max{n, m}), which breaks the natural O(k) barrier.
Experimental Validation: Experiments demonstrate that the proposed algorithms for the n = mk case consistently outperform the previous existing algorithm (Luo et al. 2022), especially when k is not a power of 2.

The paper proposes three algorithms: ALG.1 and ALG.2 for the n = mk case, and ALG.3 for the n < mk case.

ALG.1 (for n = mk) The algorithm proceeds as follows:

Graph Construction: A complete graph H = (V_H, E_H, ŵ) is constructed, where V_H = [n] and ŵ(i, j) := w(s_i, s_j) + w(t_i, t_j) for any i, j ∈ [n].
k-Path Partition: A 4(1 - 1/k)-approximate k-path partition P in H is computed using Gw.1 (Goemans and Williamson 1995). This partitions the n requests into m disjoint groups R, each containing exactly k requests.
Bipartite Matching: A complete bipartite graph B = (U ∪ R, E_B, c) is constructed. For any vehicle u ∈ U and group R ∈ R, the cost of the edge c(u, R) is defined as min(s_i,t_i)∈R(w(u, s_i) + w(s_i, t_i)). A minimum cost perfect matching M* in B is computed using Edmonds' blossom algorithm (Schrijver 2003).
Route Construction: For each matched pair (u, R_u) ∈ M*, all requests in R_u are assigned to vehicle u. Based on the k-path P_u from P corresponding to R_u, two k-paths P_s and P_t are obtained. An edge set E_u is formed, and a walk W_u is computed in G[E_u] that traverses all edges. Finally, a feasible route I_u is constructed by shortcutting W_u.

ALG.2 (for n = mk) This algorithm uses a constrained spanning forest approach:

Constrained Spanning Forest: A 2-approximate constrained spanning forest F in G[S ∪ T] is computed using Gw.2 (Goemans and Williamson 1995).
Path Construction: For each tree F ∈ F, a path P_s (resp., P_t) is constructed by doubling all edges in E(F) and shortcutting all t_i (resp., s_i) in V[F]. These paths are collected into sets P_s and P_t.
SPLIT Subroutine: If any path in P_s (or P_t) has length lk where l > 1, the SPLIT subroutine is invoked to divide these into consistent sets of k-paths. This process is repeated until all paths are k-paths.
Bipartite Matching and Route Construction: Similar to ALG.1, a minimum cost perfect matching M* is computed to assign groups of k requests to vehicles, and routes I_u are constructed based on the corresponding k-paths.

ALG.3 (for n < mk) This algorithm adapts the approach for n < mk:

Graph Construction: A complete graph H = (V_H, E_H, ŵ) is constructed, where V_H = U ∪ [n]. The weight function ŵ is defined as: ŵ(i, j) = w(s_i, s_j) + w(t_i, t_j) for i, j ∈ [n]; ŵ(u_i, j) = w(u_i, s_j) + w(u_i, t_j) for u_i ∈ U and j ∈ [n]; and ŵ(u_i, u_j) = 2w(u_i, u_j) for u_i, u_j ∈ U.
Approximate Forest: An O(log max{n, m})-approximate forest F in H is computed using an algorithm for the airport and railway problem (Salavatipour and Tian 2025). Each tree in F contains exactly one vehicle from U and at most k requests from [n].
Route Construction: For each tree F ∈ F, assuming the vehicle in F is u_F, the corresponding tree F' in graph G is obtained. The requests covered by F' are assigned to u_F. A route I_uF is constructed by doubling all edges in E(F') and then shortcutting.

Objective: The objective of the RIDE-SHARING ASSIGNMENT PROBLEM (RSAP) is to minimize the total distance traveled by all vehicles.
Key Equations:
- ALG.1 approximation ratio: 56(k-1)2√k-1 / k2 + 1 (Theorem 1)
- ALG.2 approximation ratio: √288n/k + 1 (Theorem 2)
- ALG.3 approximation ratio: O(√k log max{n, m}) (Theorem 4)
Optimization:
- Gw.1 (Goemans and Williamson 1995) for k-path partition: O(n² log n) time.
- Edmonds' blossom algorithm (Schrijver 2003) for minimum cost perfect matching: O(m³) time, or O(n²⁺ε) for bipartite graphs.
- Gw.2 (Goemans and Williamson 1995) for constrained spanning forest: O(n² log n) time.
- Algorithm from Salavatipour and Tian (2025) for O(log max{n, m})-approximate forest: O(log max{n, m}) approximation ratio, polynomial time.
Implementation Details:
- All algorithms are implemented in C++.
- Compiled with g++ -O3.
- Executed on a server with an Intel Xeon Gold 6226R CPU @ 2.90GHz, 512 GB RAM, running Ubuntu Server 20.04 LTS.
- A minor modification was made to ALG.1's route selection step: instead of a fixed edge pair, all k such edge pairs are evaluated, and the one with minimum weight is chosen. This does not affect the theoretical approximation ratio.

Datasets: RSAP instances were generated following the approach in (Bei and Zhang 2018; Luo et al. 2022) within a 4000 × 4000 Euclidean square region p = [0, 4000]². Instances are characterized by four parameters:
- m: number of vehicles (varied: 100, 150, 200, 250, 300, 350, 400)
- k: vehicle capacity (varied: 2, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 34)
- c: number of centers (varied: 10, 15, 20, 25, 30, 35, 40)
- σ²: covariance (varied: 40, 60, 80, 100, 120, 140, 160) For each configuration, 10 independent instances were generated, and average performance was reported.
Metrics:
- Solution quality (solution weight)
- Running time
Baselines: The LADG algorithm from (Luo et al. 2022).
Numeric Results:
- Solution Quality: ALG.1 consistently achieves the best solution quality. ALG.2 also achieves better solution quality than LADG. LADG performs the worst, especially when k is not a power of 2. LADG's quality improves when k is a power of 2 but deteriorates sharply when k = 2^r - 1.
- Running Time: When varying m or k, ALG.1 and LADG have comparable running times. ALG.2 is the slowest, roughly four times slower than ALG.1.
- Variations in c and σ² have a limited effect on performance.

Complexity of ALG.3 Implementation: The algorithm for the n < mk case (ALG.3) was not implemented in the experiments due to its complexity, as it requires invoking a complex algorithm from (Salavatipour and Tian 2025).
Practical Deployment of ALG.3: For practical deployment, ALG.3 may require further engineering effort to design more efficient components or simplify intricate procedures to ensure scalability and performance in real-world applications.

Method evidence: "In this paper, we study the RIDE-SHARING ASSIGNMENT PROBLEM (RSAP) (Bei and Zhang 2018), which formalizes this fundamental decision task: how to assign a set of transportation requests, each with pickup and drop-off locations, to a fleet of vehicles in a way that respects capacity constraints and minimizes total travel cost." (section: Introduction)
Result evidence: "ALG.1 not only outperforms LADG in solution quality but also runs faster. ALG.2 likewise achieves better solution quality than LADG, albeit with a slightly longer running time. Moreover, the running time of ALG.2 is roughly four times that of ALG.1." (section: Summary under Experiments)
Limitation evidence: "We did not implement ALG.3 for the case n < mk in our experiments. This is because achieving the desired approximation ratio requires invoking the algorithm from (Salavatipour and Tian 2025), which is complex and hard to implement. ALG.3 is primarily designed to establish a theoretical approximation guarantee. For practical deployment, it may be necessary to design more efficient components or simplify certain intricate procedures to ensure scalability and performance in real-world applications. These aspects deserve further investigation." (section: Conclusion and Discussion)

Improved Algorithms for Trip-Vehicle Assignment in Ride-Sharing

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures