On the Request-Trip-Vehicle Assignment Problem

Juan Carlos Martínez Mori, Samitha SamaranayakeAcda 2021 · DOI

TL;DR

This paper tackles the Request-Trip-Vehicle (RTV) assignment problem, a crucial component in modern ride-sharing systems. The authors introduce a novel LP-based randomized rounding algorithm that provides theoretical guarantees on assignment cost and request coverage, significantly outperforming previous approaches in practice due to the tight LP relaxations commonly observed.

What Problem Does This Paper Address?

Modern on-demand mobility services, like ride-sharing platforms, face the complex challenge of efficiently assigning incoming travel requests to available vehicles. This is often framed as the Request-Trip-Vehicle (RTV) assignment problem. The core difficulty lies in balancing several factors: minimizing the cost of assignments (e.g., travel distance), ensuring all requests are served, and respecting vehicle capacity and quality-of-service constraints (like maximum wait times). Traditional approaches often struggle with the combinatorial explosion of possibilities, especially in real-time, high-volume scenarios. This paper addresses this by proposing a theoretically grounded and practically efficient algorithmic solution.

Methods

The authors propose an Integer Linear Programming (ILP) formulation for the RTV assignment problem. Recognizing that solving this ILP directly can be computationally prohibitive, they focus on its Linear Programming (LP) relaxation. Their main contribution is a randomized rounding algorithm that leverages the fractional solutions obtained from the LP relaxation.

The algorithm works by:

  1. Solving the LP Relaxation: Obtaining fractional assignments for each trip-vehicle pair.
  2. Randomized Rounding: Independently assigning vehicles to trips based on these fractional probabilities.
  3. Multiplicity Correction: A crucial step to handle cases where a vehicle might be assigned multiple trips or a request might be assigned to multiple vehicles in the initial rounding. This step ensures feasibility while maintaining performance guarantees.

They also introduce a deterministic rounding heuristic inspired by their randomized approach. A key aspect of their work is analyzing the "penalty version" of the problem, where a cost is incurred for unassigned requests, making the problem always feasible.

Datasets

The paper uses simulated instances generated from the NYC Taxi and Limousine Commission (TLC) data. These simulations are based on the Alonso-Mora et al. framework [1] and cover various scenarios with different numbers of vehicles (500 and 1000) and vehicle capacities (k=2 to 6).

Key Insights and Ideas

  • LP Tightness is Key: The most striking insight is that while the RTV assignment problem is theoretically hard, its natural LP relaxation is "very tight in practice." This means the fractional solutions from the LP are often very close to integer solutions, which is why their rounding algorithms perform so well empirically.
  • Randomized Rounding for Guarantees: The paper demonstrates that randomized rounding, a standard technique, can provide provable guarantees (expected cost and request coverage) even for this complex problem.
  • Penalty Version for Robustness: Framing the problem in a "penalty version" (where unassigned requests incur a cost) makes the problem always feasible and allows the algorithm to be applied even when supply doesn't meet demand, with guarantees on the total cost (assignments + penalties).
  • Negative Association: The authors highlight that certain sets of random variables in their rounding process are "negatively associated." This is a technical detail that strengthens the theoretical analysis of their algorithm's behavior.

Key Results

  • Theoretical Guarantees: The randomized rounding algorithm guarantees an expected assignment cost no more than the optimal solution and an expected fraction of unassigned requests of at most 1/e (less than 36.8%). If costs are α-approximate, the expected cost increases by a factor of α.
  • Empirical Performance: In computational experiments, their rounding algorithms achieve performance (request rejection rate) very close to solving the full ILP to optimality, often within one percentage point.
  • Speedup: The rounding algorithms are significantly faster than solving the ILP, offering mean computation time improvements of around 27% and higher for worst-case instances. This speedup is crucial for real-time applications.
  • Integrality Gap: The paper shows that the integrality gap of the natural LP relaxation is at least 2, meaning the LP solution can be twice as good as the best integer solution in the worst case, though this is rare in practice.
  • Tightness of Rejection Bound: The authors construct specific instances where the 1/e rejection rate bound is tight, demonstrating the theoretical limits of their algorithm.

Limitations and Future Work

  • LP Tightness Assumption: While empirically observed, the paper acknowledges that a rigorous understanding of why the LP relaxation is so tight in practice is an open research question. They suggest further investigation using diverse real-world datasets.
  • Candidate Trip List Generation: The generation of the candidate trip list (T) is a bottleneck. The paper touches upon the difficulty of approximating the dual separation problem, which is related to generating this list efficiently.
  • Worst-Case Fractional Solutions: The authors developed algorithms robust to worst-case fractional solutions, but their empirical findings suggest these worst cases might be rare. Future work could explore whether there are practical instances where the LP is indeed not tight, and how LP rounding would then offer a more pronounced advantage over commercial ILP solvers.

Summary updated

BibTeX
@inproceedings{mori2021request,
  author = {Juan Carlos Martínez Mori and Samitha Samaranayake},
  title = {{On the Request-Trip-Vehicle Assignment Problem}},
  booktitle = {Acda},
  year = {2021},
  doi = {10.1137/1.9781611976830.21},
}
Figure