Pith. sign in

REVIEW 4 major objections 4 minor 22 references

En Route Path-planning for Partially Occupied Vehicles in Ride-pooling Systems

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For partially occupied ride-pooling vehicles, the route that maximizes the chance of an en-route second pickup is not the shortest path; the paper plans it as an integer linear program and shows it improves service in simulation.

desk verdict A plausible ride-pooling detour planner with a real formal flaw: the ILP does not enforce a single path, and the validation is too thin to support the claims. read the letter →

arxiv 2506.04968 v1 pith:BNOSEA2X submitted 2025-06-05 eess.SY cs.SY

Pengbo Zhu , Giancarlo Ferrari-Trecate , Nikolas Geroliminis This is my paper
classification eess.SYcs.SY
keywords ride-poolingen-routepathplanningintegerlinearprogrammingmatchingprobabilitydetourroutingvehiclecoordinationdemandresponsivenessArcOrienteeringProblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper addresses the routing problem for ride-pooling vehicles that have already picked up one passenger and have a free seat. It argues that following the shortest path to the current passenger's destination is often not the best choice: a slightly longer route through areas with many compatible requests and few competing vehicles raises the chance of picking up a second passenger. The authors build a trip-specific matching-probability model for each road edge, approximate the route-level objective in linear form, and cast the planning task as an integer linear program with a detour budget. Simulation on a realistic Shenzhen road network indicates that this policy outperforms shortest-path routing on answer rate, waiting time, shared orders, and empty distance.

What carries the argument

The load-bearing mechanism is the per-edge match probability of Eq. (6): $P^t_{ij} = 1 - (1 - p^t_{\mathrm{edge}}(i,j,O_A,D_A))^{\hat{T}(i,j)}$, where $p^t_{\mathrm{edge}}$ is the average of the node-level match probabilities at the two endpoints. The node-level probability (Eq. (1)) is $1 - \zeta \exp(-\lambda_{\mathrm{Att}} / (\eta n_t(i)))$, in which $\lambda_{\mathrm{Att}}$ is the expected compatible passenger demand weighted by how efficiently the two trips can be pooled, and $n_t(i)$ counts nearby empty, dropping-off, and partially occupied vehicles. By assuming match opportunities occur independently over time, the route-level probability of no match becomes the product over edges of $(1 - P^t_{ij})$, and the small-probability logarithm approximation turns the objective into a linear sum, making the planning problem an instance of the Arc Orienteering Problem cast as ILP (11), whose optimal path is the route that most improves the chance of a second pickup within the detour budget.

What would settle it

Run the same Shenzhen simulator with demand arriving in short bursts or with vehicles clustering, and compare the realized fraction of trips that gain a second passenger under routes chosen by the ILP versus routes chosen by shortest path. If the ILP routes do not yield a higher realized match rate, the independence product (Eq. (6) and (8)) mis-ranks routes and the central claim is not robust.

Watch

Extended reading notes

Core claim

The central claim is that en-route path planning for partially occupied vehicles should maximize the sum of edge-level match probabilities, subject to flow and detour constraints, and that solving this ILP yields routes that measurably improve service. Specifically, the paper solves $\max \sum_{(i,j)\in E} P^t_{ij} x_{ij}$ with binary edge variables, start/end constraints, flow conservation, no cycles, and total length at most $\alpha$ times the shortest-path length. The probabilities $P^t_{ij}$ combine a passenger-demand attractiveness term with a vehicle-competition repulsiveness term. In the reported Shenzhen case study, the proposed policy achieves an 81.4% answer rate versus 80.0% for the shortest-path policy, a shorter average waiting time (151.3 s versus 153.8 s), more shared orders (656 versus 614), longer total shared distance, and lower empty distance. A corollary emphasized by the authors is that serving the same share of requests without ride-pooling would need a fleet about 20% larger, with much more empty driving.

Load-bearing premise

The decisive assumption is that the chance of failing to find a match on one road edge is independent of the chance on every other edge, so the route-level probability is just the product of per-edge probabilities; in reality nearby matching opportunities are correlated in time and space.

Editorial extensions

If this is right

  • Ride-pooling fleets can raise the share of trips that become shared without waiting for passive batch matching: the planned detour is computed at pickup time and can be updated as conditions change.
  • Because routes avoid areas already crowded with other partially occupied vehicles, the method acts as a lightweight coordination mechanism across the fleet, reducing oversupply and undersupply.
  • The detour budget adapts to demand: in the case study the planned path is longer in the low-demand hour (10.39 km) than in the high-demand hour (10.29 km), both within the 20% threshold.
  • Without ride-sharing, matching the same answer rate requires about 20% more vehicles and much more empty driving, so the routing gains translate directly into fleet-size and congestion savings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the independence assumption is the most exposed part of the model; a natural test is to compute route-level no-match probabilities by simulation instead of by multiplication and see whether the ILP's ranking of candidate routes changes.
  • Editorial inference: the same attractiveness/repulsiveness machinery could be applied to empty-vehicle repositioning or to the final drop-off leg, not only to partially occupied vehicles; the paper does not explore these.
  • Editorial inference: the reported gains are obtained under a first-come-first-served matching policy that does not itself optimize for pooling, so the benefits might change under a proactive matching policy; extending the comparison would clarify how much of the gain is routing versus matching.
  • Editorial inference: using an online predictor of demand instead of historical averages, as the paper notes as future work, could make the edge probabilities time-consistent with bursty arrivals; such an extension is testable with the same ILP.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes an en-route path-planning algorithm for partially occupied vehicles in ride-pooling systems. A matching probability model is introduced that combines "attractiveness" of demand and "repulsiveness" of competing vehicles, and the route choice is formulated as an integer linear program (ILP) maximizing the sum of edge-level match probabilities under a detour budget. The method is evaluated in an agent-based simulator on a Shenzhen road network, with results reported in Table I. The central claim is that the proposed ILP-based routing yields higher answer rates, shorter waiting times, and more shared trips than a shortest-path policy.

Significance. If the central claim held, the paper would offer a practical and computationally tractable approach to real-time detour planning for ride-pooling, and the joint modeling of passenger demand and vehicle competition is a reasonable idea worth exploring. The use of a realistic simulator on a real urban network is a strength. However, the current manuscript does not yet support the central claim because the ILP as stated may not produce a valid path, the linearization underlying the objective is not justified, and the calibration/evaluation setup may bias the reported improvements. These issues are load-bearing for the claim that the proposed method outperforms the shortest-path baseline.

major comments (4)
  1. [Section III-B, Eqs. (11c)-(11e)] The ILP formulation does not enforce that the selected edges form a single simple path from OA to DA. Constraint (11d) imposes flow balance only at intermediate nodes, and (11e) bounds the in-degree and out-degree of each node by one, but this does not rule out directed cycles that are disjoint from the main path, or cycles attached at OA or DA, or a cycle passing through OA or DA. Since the objective coefficients P^t_ij are nonnegative, adding such a cycle never decreases the objective and, whenever the detour budget (11f) has slack, the ILP optimum will include extra cycle edges that are not on the OA-DA route. The statement in Section III-B that (11e) "prevent[s] cycles in the path" is therefore incorrect, and the claim that the route rcurrent is "constructed by sequentially connecting these selected edges" is not well-defined. Consequently, Table I may be evaluating a trajectory that differs from the ILP optimum, so the reported performance of the proposed method is not attributable to the algorithm as stated. Subtour-elimination constraints or an explicit path-based formulation are needed.
  2. [Section III-A, Eqs. (9)-(10)] The transformation from the multiplicative objective (8) to the linear objective (10) relies on the approximation log(1-y) ≈ -y, which is valid only when all P^t_ij · x_ij are close to zero. The paper does not report typical values of P^t_ij for the Shenzhen case study, and if some edge probabilities are not small (e.g., above 0.1), this approximation can change the ranking of candidate routes and hence the optimal solution. The authors should either justify the small-probability regime using the actual data, solve the exact nonlinear objective (8), or provide a sensitivity analysis comparing the solutions of (8) and (10). Without this, the claim that the ILP maximizes the likelihood of picking up a second passenger is unsupported.
  3. [Section IV-B, Experimental setup] The hyperparameters ζ and η are selected via grid search to maximize the answer rate, which is also the primary metric used for comparison in Table I. The paper does not describe a separate calibration/validation split or report how sensitive the comparative results are to ζ and η. As a result, the reported improvement of the proposed method over the shortest-path policy could be at least partly an artifact of tuning to the evaluation metric rather than a genuine advantage of the routing mechanism. Please clarify whether the tuning was performed on a period disjoint from the evaluation scenarios, or report results across a range of hyperparameter values.
  4. [Section II-C, Eq. (6)] The route-level probability of no match is computed as the product of per-edge no-match probabilities, which assumes that match opportunities on different edges are statistically independent. In the simulator, however, requests arrive in the network and the matching process is centralized and sequential (Section IV-A), and the presence of other vehicles creates spatial and temporal correlation in match opportunities. Under such correlation, the product form is not the true probability and can mis-rank routes. The authors should justify the independence assumption or test its impact, for example by comparing the optimized routes with routes selected using a simulator-based estimate of the actual route-level match probability.
minor comments (4)
  1. [Section III-B, after Eq. (11f)] The sentence "Constraint (11e) ensures that each node is visited at most once, preventing cycles in the path" should be revised, since (11e) only bounds degrees and does not prevent disconnected or attached cycles; this is already covered in the major comments but the wording should be corrected.
  2. [Fig. 1 caption] The caption describes Path 3 as having passengers traveling "in the opposite direction of the current trip, from OA to DA"; the phrase "from OA to DA" appears to mean the opposite direction of the current origin-destination pair, but the wording is confusing and should be clarified.
  3. [Table I] The row label "No share ( f leet+ 20%)" should be typeset as "No share (fleet + 20%)" for consistency, and the meaning of the +20% fleet scenario could be spelled out explicitly in the table caption.
  4. [Section IV-B, Algorithm 1] In Algorithm 1, the update step augments R with rcurrent but does not specify when routes are removed; a brief comment on the lifecycle of planned routes would improve reproducibility.

Circularity Check

1 steps flagged · score 4.0 of 10

Partial circularity: match-probability hyperparameters are tuned to maximize the very answer-rate metric that Table I then reports as evidence, though the ILP routing mechanism itself is independent.

  1. fitted input called prediction [Section IV-B (Experimental setup) and Table I in Section IV-C (Results and Analysis)]
    "In our method, other parameters such as ζ and η are tuned via grid search, evaluating performance across combinations to maximize the answer rate."

    The model's two free parameters are selected by grid search to maximize the 'answer rate' metric in the same simulator that is later used to evaluate the method. Table I then reports 'Answer rate (%) Proposed 81.4 Shortest 80.0' as headline evidence of superiority. This makes the reported answer-rate gain an in-sample tuning artifact rather than an independent prediction of the model. The circularity is partial because the ILP route optimization is a separate mechanism and other metrics (waiting time, shared orders) are not directly the tuning objective.

full rationale

The ILP path-planning model is built from explicit modeling assumptions, Eqs. (1)-(6), and external references ([7], [18]) rather than from the performance metrics it is claimed to improve. The logarithmic transformation and linearization in Eqs. (8)-(10) are standard algebraic steps and do not make the objective equivalent to the simulation outcome by construction. The route-selection mechanism, ILP (11), is a distinct algorithmic component not defined in terms of the evaluation metrics. The only near-circular step is the grid-search tuning of ζ and η to maximize the answer rate in the same simulator that later produces Table I; that makes the headline answer-rate improvement partly a fitting artifact, but it does not collapse the entire derivation into a tautology. The missing subtour-elimination constraint is a correctness concern, not a circularity. No load-bearing self-citation, imported uniqueness theorem, or ansatz smuggled via citation is present, and the simulator [22] is an independent, previously published tool.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The core model is an assumed exponential matching function with two fitted parameters (ζ, η). The ILP then optimizes a linear approximation of this surrogate. The central comparison in Table I evaluates the method in the same simulator used for tuning, which limits external validity.

free parameters (3)
  • ζ (zeta) = 1
    Matching radius parameter in Eq. (1), tuned via grid search to maximize answer rate in the simulation.
  • η (eta) = 0.001
    Region-specific difficulty parameter in Eq. (1), tuned via grid search to maximize answer rate in the simulation.
  • Partial vehicle availability weight (0.5) = 0.5
    Hand-chosen discount for partially occupied vehicles' availability in the competition count (Eq. 4).
assumptions (6)
  • domain assumption Passenger requests arrive as independent Poisson processes with rate λ_t(i,j) estimated from historical data
    Used in Eq. (2) to compute expected compatible demand; Section II-B.
  • domain assumption Matching opportunities occur independently over time and across edges
    Used to derive edge match probability P_t_ij in Eq. (6); Section II-C.
  • ad hoc to paper The functional form of matching probability in Eq. (1) (exponential in attractiveness/repulsiveness) is correct
    Inspired by [18] and [7] but not derived; parameters ζ, η tuned to the simulation.
  • domain assumption Only two pooling sequences are considered (O_A→O_B→D_A→D_B and O_A→O_B→D_B→D_A)
    Defines L_p in Eq. (3); limits the set of feasible shared trips.
  • ad hoc to paper log(1-y) ≈ -y is valid for all edge probabilities encountered
    Used in Section III-A to linearize the objective; no bounds on P_t_ij are given.
  • domain assumption Start and end nodes of an edge contribute equally to the match probability (Eq. 5)
    Averaging assumption with no justification for equal contribution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of En Route Path-planning for Partially Occupied Vehicles in Ride-pooling Systems." pith.science (2026). https://pith.science/paper/BNOSEA2X

@misc{pith2026250604968,
  author       = {Pith},
  title        = {Pith review of: En Route Path-planning for Partially Occupied Vehicles in Ride-pooling Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BNOSEA2X}},
  note         = {Machine review of arXiv:2506.04968}
}
read the original abstract

Ride-pooling services, such as UberPool and Lyft Shared Saver, enable a single vehicle to serve multiple customers within one shared trip. Efficient path-planning algorithms are crucial for improving the performance of such systems. For partially occupied vehicles with available capacity, we introduce a novel routing algorithm designed to maximize the likelihood of picking up additional passengers while serving the current passengers to their destination. Unlike traditional methods that group passengers and vehicles based on predefined time windows, our algorithm allows for immediate responses to passenger requests. Our approach optimizes travel time while dynamically considering passenger demand and coordinating with other vehicles. Formulated as an integer linear programming (ILP) problem, our method is computationally efficient and suitable for real-time applications. Simulation results demonstrate that our proposed method can significantly enhance service quality.

Figures

Figures reproduced from arXiv: 2506.04968 by the authors.

Figure 1
Figure 1. Four different path choices for a partially occupied vehicle. The shortest path, labeled ‘Path 0’, is shown in green. Waiting passengers are indicated by square markers, with arrows pointing to their intended travel directions. The arc lengths represent the lengths of each path. Assume that taxis have a capacity of two, meaning they can serve up to two passengers with separate origins and destinations on one trip. A… view at source ↗
Figure 2
Figure 2. Evolution of the number of passengers In a ride-sharing scenario, a taxi can serve multiple passen￾gers simultaneously. Specifically, we focus on the common case where two ride requests are shared. Initially, at time t 0 , the vehicle is empty and idle. The evolution of the number of passengers in the taxi over time is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Illustration of the paths for a partially occupied vehicle traveling from the origin O A of its first passenger to the destination D A under different demand levels: (a) low-demand hour and (b) high-demand hour. A heat map is superimposed over the road network, representing the matching probability p t edge(i, j, OA, DA) of each edge (i, j). The shortest path between O A and D A is depicted as a dashed line, with ed… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    On ride-pooling and traffic congestion,

    J. Ke, H. Yang, and Z. Zheng, “On ride-pooling and traffic congestion,” Transportation Research Part B: Methodological , vol. 142, pp. 213– 231, 2020

    work page 2020

  2. [2]

    A partition-based match making algorithm for dynamic ridesharing,

    D. Pelzer, J. Xiao, D. Zehe, M. H. Lees, A. C. Knoll, and H. Aydt, “A partition-based match making algorithm for dynamic ridesharing,” IEEE Transactions on Intelligent Transportation Systems , vol. 16, no. 5, pp. 2587–2598, 2015

    work page 2015

  3. [3]

    Predictive routing for autonomous mobility-on-demand systems with ride-sharing,

    J. Alonso-Mora, A. Wallar, and D. Rus, “Predictive routing for autonomous mobility-on-demand systems with ride-sharing,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017, pp. 3583–3590

    work page 2017

  4. [4]

    Optimizing vehicle dis- tributions and fleet sizes for shared mobility-on-demand,

    A. Wallar, J. Alonso-Mora, and D. Rus, “Optimizing vehicle dis- tributions and fleet sizes for shared mobility-on-demand,” in 2019 International Conference on Robotics and Automation (ICRA) , 2019, pp. 3853–3859

    work page 2019

  5. [5]

    Hierarchical control for vehicle repositioning in autonomous mobility-on-demand systems,

    P. Zhu, G. Ferrari-Trecate, and N. Geroliminis, “Hierarchical control for vehicle repositioning in autonomous mobility-on-demand systems,” IEEE Transactions on Control Systems Technology , pp. 1–14, 2024

    work page 2024

  6. [6]

    Incentive-driven transi- tion to high ride-sharing adoption,

    D.-M. Storch, M. Timme, and M. Schr ¨oder, “Incentive-driven transi- tion to high ride-sharing adoption,” Nature Communications, vol. 12, 06 2021

    work page 2021

  7. [7]

    Data-driven analysis on match- ing probability, routing distance and detour distance in ride-pooling services,

    J. Ke, Z. Zheng, H. Yang, and J. Ye, “Data-driven analysis on match- ing probability, routing distance and detour distance in ride-pooling services,” Transportation Research Part C: Emerging Technologies , vol. 124, p. 102922, 2021

    work page 2021

  8. [8]

    Routing optimization with vehicle–customer coordination,

    W. Zhang, A. Jacquillat, K. Wang, and S. Wang, “Routing optimization with vehicle–customer coordination,” Management Science , vol. 69, no. 11, pp. 6876–6897, 2023

    work page 2023

Show all 22 references
  1. [9]

    Designing an on- line ride-sharing system,

    B. Cici, A. Markopoulou, and N. Laoutaris, “Designing an on- line ride-sharing system,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, ser. SIGSPATIAL ’15. New York, NY , USA: Association for Computing Machinery, 2015

    2015

  2. [10]

    Price- aware real-time ride-sharing at scale: an auction-based approach,

    M. Asghari, D. Deng, C. Shahabi, U. Demiryurek, and Y . Li, “Price- aware real-time ride-sharing at scale: an auction-based approach,” in Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems , 2016

    2016

  3. [11]

    The shared-taxi problem: Formulation and solution methods,

    H. Hosni, J. Naoum-Sawaya, and H. Artail, “The shared-taxi problem: Formulation and solution methods,” Transportation Research Part B: Methodological, vol. 70, pp. 303–318, 2014

    2014

  4. [12]

    A unified approach to route planning for shared mobility,

    Y . Tong, Y . Zeng, Z. Zhou, L. Chen, J. Ye, and K. Xu, “A unified approach to route planning for shared mobility,” Proc. VLDB Endow., vol. 11, no. 11, p. 1633–1646, July 2018

    2018

  5. [13]

    Ridesharing: The state-of-the-art and future directions,

    M. Furuhata, M. Dessouky, F. Ord ´o˜nez, M.-E. Brunet, X. Wang, and S. Koenig, “Ridesharing: The state-of-the-art and future directions,” Transportation Research Part B: Methodological , vol. 57, pp. 28–46, 2013

    2013

  6. [14]

    Neural approximate dynamic programming for on-demand ride-pooling,

    S. Shah, M. Lowalekar, and P. Varakantham, “Neural approximate dynamic programming for on-demand ride-pooling,” Proceedings of the AAAI Conference on Artificial Intelligence , vol. 34, pp. 507–515, 2020

    2020

  7. [15]

    Ppvf: A novel framework for supporting path planning over carpooling,

    B. Wang, R. Zhu, S. Zhang, Z. Zhao, X. Yang, and G. Wang, “Ppvf: A novel framework for supporting path planning over carpooling,” IEEE Access, vol. 7, pp. 10 627–10 643, 2019

    2019

  8. [16]

    A detour planning algorithm in crowd- sourcing systems for multimedia content gathering,

    C.-C. Liao and C.-H. Hsu, “A detour planning algorithm in crowd- sourcing systems for multimedia content gathering,” in Proceedings of the 5th Workshop on Mobile Video , ser. MoVid ’13. New York, NY , USA: Association for Computing Machinery, 2013, p. 55–60

    2013

  9. [17]

    The planning of cycle trips in the province of east flanders,

    W. Souffriau, P. Vansteenwegen, G. Vanden Berghe, and D. Van Oudheusden, “The planning of cycle trips in the province of east flanders,” Omega, vol. 39, no. 2, pp. 209–213, 2011

    2011

  10. [18]

    Spatial Equilibrium, Search Frictions, and Dynamic Efficiency in the Taxi Industry,

    N. Buchholz, “Spatial Equilibrium, Search Frictions, and Dynamic Efficiency in the Taxi Industry,” The Review of Economic Studies , vol. 89, no. 2, pp. 556–591, 09 2021

    2021

  11. [19]

    Dynamic pricing and matching in ride-hailing platforms,

    C. Yan, H. Zhu, N. Korolko, and D. Woodard, “Dynamic pricing and matching in ride-hailing platforms,” Naval Research Logistics (NRL) , vol. 67, no. 8, pp. 705–724, 2020

    2020

  12. [20]

    Algorithm 97: Shortest path,

    R. W. Floyd, “Algorithm 97: Shortest path,” Commun. ACM, vol. 5, no. 6, p. 345, June 1962

    1962

  13. [21]

    Travel time estimation of a path using sparse trajectories,

    Y . Wang, Y . Zheng, and Y . Xue, “Travel time estimation of a path using sparse trajectories,” in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , ser. KDD ’14. New York, NY , USA: Association for Computing Machinery, 2014, p. 25–34

    2014

  14. [22]

    On the inefficiency of ride- sourcing services towards urban congestion,

    C. V . Beojone and N. Geroliminis, “On the inefficiency of ride- sourcing services towards urban congestion,” Transportation Research Part C: Emerging Technologies, vol. 124, p. 102890, 2021

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.