A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems

arXiv:2311.06035 · eess.SY, cs.SY, math.OC · Submitted 2023-11-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems".

Rosa: A framework is presented to incorporate ride-pooling into time-invariant network flow models for Mobility-on-Demand systems, transforming a microscopic combinatorial phenomenon into a solvable linear problem.

Dev: First, who's behind it and why it matters.

Title and authors: Rosa: Now that we've discussed the core mechanism, let's look at the title and who came up with this work, specifically "A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems."

Dev: The title tells us right away that they are focusing on a time-invariant network flow model specifically for ride-pooling within Mobility-on-Demand systems.

Taro: It seems like the authors, Paparella, Pedroso, Hofman, and Salazar, were looking to bridge the gap between microscopic simulations and macroscopic flow models.

Rosa: I was thinking about how this relates to what we've seen in other papers on visual-tactile manipulation; is this framework something that could be tested outside of a controlled lab setting?

Dev: The authors mention that this model has been used for several design purposes, like minimizing fleet size and minimizing electricity costs, which shows it’s applicable across different operational goals.

Taro: The literature they review includes work on vehicle group assignment algorithms from Alonso-Mora et al., which gives us context on what existing methods are trying to solve before they introduce their new formulation.

Rosa: It seems like the authors are building on a rich body of literature in ride-pooling, but their contribution is providing a unified structure that can handle both on-demand and pooled scenarios within this flow model.

Dev: The paper explicitly states that for rho=zero Problem one which minimizes user travel time, is totally unimodular, meaning X and x r can be decoupled and computed separately six.

Taro: That decoupling is a very strong statement about the mathematical structure they’ve uncovered; it suggests a fundamental property of the problem when there's no cost associated with rebalancing.

Rosa: If we look at their mention of Problem two where rho=one it shifts the objective to minimizing vehicle minimum travel time, which is equivalent to solving a minimum fleet size problem five, six.

Dev: That transition shows they can use the same underlying flow structure to solve different operational problems depending on whether we are optimizing for user time or vehicle utilization.

Taro: It’s interesting how they frame it as transforming the original set of requests D into an equivalent set of requests accounting for ride-pooling, portrayed by D rp.

Rosa: So, what does this mean practically for us when we consider the broader implications? Does it suggest a way to model larger urban mobility challenges?

Dev: Yes, it suggests that complex urban mobility problems can be simplified into a linear problem structure that is computationally tractable for solving in polynomial time.

Taro: It moves the focus from modeling individual vehicle movements to modeling the aggregate flow of requests and rebalancing flows, which is a necessary step for large-scale autonomy research.

Rosa: That sounds like a solid direction; if we can model the aggregate system well, it helps us understand how autonomous systems interact with dense human movement patterns.

Dev: The authors use this framework for multiple design purposes beyond just ride-pooling, such as smart charging and joint optimization with public transport one, nine–twelve.

Taro: That shows the versatility of the mathematical model; it's not just specialized for one task but can be adapted to solve various infrastructure and operational challenges.

The paper's summary: Rosa: Okay, moving on to a more detailed summary, what is the actual essence of "A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems"?

Dev: Essentially, the paper presents a framework to incorporate ride-pooling from a mesoscopic point of view within time-invariant network flow models of Mobility-on-Demand systems.

Taro: They take the original set of requests, portrayed by D, and transform it into an equivalent set of requests accounting for ride-pooling, portrayed by D rp.

Rosa: The goal is to find a ride-pooling request assignment that minimizes user travel time under constraints derived from spatial feasibility and temporal feasibility.

Dev: They define the cost function as J(X, x r) = t (X one + rho x r) subject to BX = D and B(X one + x r) = zero where rho is a weighting factor.

Taro: When rho=zero this objective function is interpreted as the minimum user travel time, which is totally unimodular, allowing for decoupling of X and x r and solving them separately six.

Rosa: But when they introduce ride-pooling, they tackle Problem two by determining D rp based on four key conditions: serving individual requests, spatial feasibility based on a detour travel time threshold, temporal feasibility based on a maximum waiting time threshold, and minimizing the cost function of Problem two at its solution.

Dev: The core challenge here is deriving D rp using these four conditions, which are essentially constraints that must be met before we can proceed with the main flow optimization.

Taro: That means the feasibility of a pooling request isn't just about who wants to go where; it’s also heavily constrained by how far they have to detour or how long they can wait for a ride.

Rosa: The authors then use an approximation, Approximation II.one setting rho = zero to make the cost function J:= t one which allows them to compute D rp optimally with respect to this version in polynomial time.

Dev: This computation happens in two main steps: first, a spatial analysis determining feasible pooling itineraries by analyzing bags C in S K k one C delta, where feasibility requires finding a sequence s in S C such that delta C,s m, m in C.

Taro: That spatial analysis part is where the geometric constraints of the network and the detour limits are rigorously applied to define what constitutes a physically possible pool.

Rosa: Then there’s the temporal analysis using Lemma II.one which gives us a probability formula for k requests occurring within a maximum waiting time based on arrival rates alpha i.

Dev: After that, they use Algorithm one to find the optimal assignment iteratively by prioritizing bags with the highest relative improvement with respect to user flow and updating the demand matrix by setting alpha'm from alpha'm - gamma C m C(m), where gamma C is calculated based on the minimum arrival rate in that bag.

Taro: That iterative greedy approach, using gamma C = (alpha'm/m C(m), m in C) P(alpha'm, m in C), seems like a very effective way to balance spatial and temporal constraints simultaneously during the assignment phase.

Rosa: So, in summary, they've taken a complex flow problem and created an efficient algorithm that can determine the optimal ride-pooling request assignment by carefully analyzing spatial feasibility through bags and temporal likelihoods.

The paper's improvements: Dev: The authors propose several improvements to their initial framework, essentially refining how they handle the complexity of generating the demand matrix D rp.

Rosa: What are the main suggestions for improving this approach, especially regarding making it more robust or applicable in different real-world scenarios?

Taro: They focus on refining that process of deriving D rp based on those four key conditions, ensuring that the resulting assignment truly minimizes the cost function of Problem two at its solution.

Dev: They emphasize using the approximation rho=zero as a practical step to make the problem solvable in polynomial time, even though it means they are optimizing for minimum user travel time instead of vehicle minimum travel time.

Rosa: That seems like a necessary trade-off; sacrificing the exact objective function for computational tractability allows us to get a solution quickly, which is often more valuable in dynamic systems.

Taro: They also show the importance of network granularity analysis, demonstrating that even with pruned networks, reducing V from three hundred fifty-seven to one hundred twenty or one hundred sixty nodes, the quality of the solution remains acceptable.

Dev: That's a practical takeaway for deployment: you don't necessarily need an extremely fine map; you can make simplifications to the graph structure and still get a usable result.

Rosa: So, the improvements highlight that this model is not just about finding *a* solution, but finding a high-quality solution under realistic operational trade-offs defined by those thresholds.

Taro: The ability to quantify how changing these waiting time and delay thresholds affects vehicle hours traveled and overall pooled rides provides a way to tune the system's performance precisely.

Dev: That allows for quantitative prediction of operational metrics, enabling us to predict system behavior before we even deploy it in a full-scale environment.

Rosa: It moves the discussion toward practical tuning; we can now use this model to simulate scenarios and understand how tweaking service parameters impacts the entire system's efficiency.

Conclusion: Dev: To wrap up, the main conclusion of "A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems" is that they have successfully proposed a framework to capture ride-pooling in a time-invariant network flow model.

Rosa: So, in short, they've transformed this microscopic combinatorial phenomenon into a solvable linear problem, meaning we can compute an optimal ride-pooling request assignment in polynomial time for any given instance.

Taro: I think the biggest implication is that this provides a structured way to approach large-scale autonomy challenges by modeling the aggregate system flow rather than just individual vehicle movements.

Dev: The practical application lies in using this framework to determine, for any set of pending ride requests, the most efficient spatial and temporal pooling configuration that adheres to predefined service quality constraints.

Rosa: It opens up possibilities for real-time decision-making in urban environments by allowing us to quickly calculate optimal assignment flows using that polynomial-time greedy heuristic.

Taro: For me, the real value is the ability to provide operational intelligence to fleet managers by simulating the impact of changing service parameters on overall system efficiency, enabling proactive capacity planning.

Dev: This work gives us a way to assess network representations and recommend the most suitable graph structure based on our computational budget while maintaining acceptable solution quality for ride-pooling optimization.

Rosa: So, in conclusion, "A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems" provides a practical and efficient mathematical tool for integrating ride-pooling into large systems.

Eindhoven University of Technology

eess.SY, cs.SY, math.OC

Submitted: 2023-11-10

Updated: 2023-11-10

Comments: arXiv admin note: substantial text overlap with arXiv:2303.15051

Journal ref: IEEE Trans. Control Netw. Syst., vol. 12, no. 1, pp. 906-917, Mar. 2025

DOI: 10.1109/TCNS.2024.3431411

Code: https://github.com/fabiopaparella/LTI-pooling-K_people

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: A framework is presented to incorporate ride-pooling into time-invariant network flow models for Mobility-on-Demand systems, transforming a microscopic combinatorial phenomenon into a solvable linear

Key concepts

Multi-commodity network flow model: This is a mathematical structure used to model transportation systems where different types of goods (in this case, individual travel requests) need to be routed through a network (roads and intersections). It helps determine the most efficient way for all requests to move simultaneously.
Ride-pooling Formulation: This describes the core challenge: deciding which users should share a ride. Feasibility depends on whether the detour time for any user stays below a limit ($ar{ ho}$) and if waiting times are acceptable ($tar{ ho}$). The goal is to find the best way to group requests into shared rides.
Approximation (Approximation II.1): Since the exact problem is too complex, the authors simplify it by setting a cost factor ($ ho$) to zero. This simplification allows them to use a polynomial-time algorithm to find an optimal demand matrix ($D_{rp}$) that minimizes the simplified travel time objective.
Optimal Assignment Algorithm: This iterative procedure uses a specific heuristic (prioritizing bags with the highest relative improvement) and probabilistic estimates (Lemma II.1) to adjust the ride-pooling demand until it converges on a solution that minimizes the overall system cost.

Terminology

Objective Function — 11× in this paper · explained in 2 episodes
alpha — 5× in this paper · explained in 1 episode
Core — 4× in this paper · explained in 2 episodes
Clustering — 2× in this paper · explained in 2 episodes
Decoupling — 2× in this paper · explained in 2 episodes
Pruning — 2× in this paper · explained in 4 episodes
Alignment — 1× in this paper · explained in 1 episode
Approximation (Approximation II.1) — 1× in this paper · explained in 1 episode
Computational Tractability — 1× in this paper · explained in 2 episodes

Summary

A framework is presented to incorporate ride-pooling into time-invariant network flow models for Mobility-on-Demand systems, transforming a microscopic combinatorial phenomenon into a solvable linear problem. This approach allows for the computation of an optimal ride-pooling request assignment that minimizes user travel time, and case studies validate its significant benefits in real urban environments.

The gist

Model Foundation

The system is modeled as a multi-commodity network flow model on a directed graph G = (V, A), where V represents intersections and A represents road links. Travel requests are defined as tuples r = (o, d, α) in V × V × R>0. The problem structure is initially defined by Problem 1: minimizing the cost J(X, xr) = t⊤(X1 + ρxr) subject to BX = D and B(X1 + xr) = 0. Here, X represents active vehicle flows and x r represents rebalancing flows. For ρ=0, this objective function is interpreted as the minimum user travel time.

Ride-pooling Formulation

The paper extends this to Problem 2: minimizing J(X, xr) = t⊤(X1 + ρxr) subject to BX = Drp and B(X1 + xr) = 0. The core challenge is determining the ride-pooling demand matrix Drp based on four key conditions:

The individual requests, described by D, must be served.
Ride-pooling k ≤ K requests is only spatially feasible if the detour travel time of every user is not greater than a threshold ¯δ ∈ R≥0.
Temporal feasibility requires that the "maximum waiting time for a request to start being served does not exceed a threshold t¯ ∈ R>0."
The requests are pooled to minimize the cost function of Problem 2 at its solution.

Approximation and Computation

Due to the combinatorial nature, an approximation (Approximation II.1) is used: setting ρ = 0, making the cost function J˜(X):= t⊤X1. This allows for a polynomial-time algorithm to compute Drp optimally with respect to this approximated version. The computation of Drp involves two main steps:

Spatial Analysis: Determining feasible pooling itineraries by analyzing bags C ∈ SK k 1 C δ¯k(M), where feasibility requires finding a sequence s ∈ SC such that δC,s m ≤ ¯δ, ∀m ∈ C. The optimal demand matrix is then defined as DC,⋆ based on the best sequence s.
Temporal Analysis: Deriving the probability of k requests occurring within a maximum waiting time t¯ using Lemma II.1: Pt¯ (α1,..., αk) = X k i=1 αi Pk j=1 αj Y k j=1 j̸=i 1 − e −αj t¯.

Optimal Assignment Algorithm

The optimal ride-pooling assignment is computed iteratively using Algorithm 1. The algorithm prioritizes the bag C with the highest relative improvement w.r.t. the user flow, defined by ∆J˜C/C. It updates the demand matrix by setting α'm ← α'm − γCmC(m), where γC is calculated as γC = min (α'm/mC(m), m ∈ C) Pt¯(α'm, m ∈ C). This procedure repeats until convergence, establishing a minimizer of J˜(X⋆γ).

Case Studies and Findings

The framework was validated in two case studies: Sioux Falls (K=4) and Manhattan (K=2). The results highlight that for a sufficient number of requests, with maximum waiting time and delay thresholds of 5 minutes, it is possible to ride-pool more than 80% of the requests for both case studies. Furthermore, the paper shows that allowing for four people ride-pooling can significantly boost the performance of the system in dense urban environments. The analysis also shows that as demand increases, the delay decreases, and for larger demands, four people ride-pooling counts for more than 85%. Finally, network granularity analysis indicates that even with pruned networks (reducing V from 357 to 120-160), the quality of the solution remains acceptable.

Statement of Contributions

The main contributions are threefold:

Proposing a framework to capture ride-pooling in a time-invariant network flow model, ensuring complexity is independent of the number of travel requests.
Devising a method to compute a ride-pooling request assignment that is "

Improvements for AI systems

Here are specific improvements for AI systems based on the proposed framework:

Improvement of Ride-Pooling Optimization in Mobility-on-Demand Systems: The core improvement is moving from microscopic, request-by-request optimization (which is computationally intractable at scale) to a mesoscopic, time-invariant network flow model.
Enhanced Demand Matrix Generation: The system can now compute an optimal ride-pooling demand matrix that explicitly considers spatial feasibility (detour travel time threshold) and temporal feasibility (maximum waiting time threshold).
Polynomial-Time Optimal Assignment Algorithm: By leveraging the relaxation (Approximation II.1) and the proposed iterative greedy algorithm (Algorithm 1), the AI system can compute a ride-pooling request assignment in polynomial time, making it viable for real-time decision-making in large fleets.
Performance Prediction and System Tuning: The framework allows for quantitative prediction of key operational metrics (e.g., percentage of requests pooled, average experienced delay) as functions of network density, demand intensity, maximum waiting time thresholds, and maximum delay thresholds. This enables dynamic tuning of service parameters to maintain desired user experience levels.
Scalable Fleet Management: The model can effectively incorporate ride-pooling for up to K people without a change in the underlying optimization structure (Problem 2), allowing the AI to optimize for different pooling capacities based on real-time demand patterns.
Network Granularity Robustness Analysis: The system can analyze and quantify how network pruning (reducing nodes, V) impacts solution quality, ensuring that AI deployment decisions are robust against necessary simplifications of the urban road graph structure.

The improved AI system can perform the following specific functions:

It can proactively assign riders to pooled vehicles to minimize overall user travel time by solving a large-scale linear program derived from the network flow model.
It can determine, for any given set of pending ride requests, the most efficient spatial and temporal pooling configuration that adheres to predefined service quality constraints (e.g., no user detour exceeding 5 minutes).
It can operate in real-time urban environments by quickly calculating optimal assignment flows using a polynomial-time greedy heuristic (Algorithm 1), ensuring rapid response times for ride requests.
It can provide operational intelligence to fleet managers by simulating the impact of changing service parameters (like increasing or decreasing maximum waiting time thresholds) on overall system efficiency, enabling proactive capacity planning.
It can assess the trade-offs between different urban network representations (e.g., fine vs. coarse road maps) and recommend the most suitable graph structure for a given computational budget while maintaining acceptable solution quality for ride-pooling optimization.