pith. sign in

arxiv: 2508.00241 · v2 · submitted 2025-08-01 · 🧮 math.OC

Paratransit Optimization with Constraint Programming: A Case Study in Savannah, Georgia

Liam Jagrowski , Kevin Dalmeijer , Tinghan Ye , Pascal Van Hentenryck This is my paper

Pith reviewed 2026-05-19 02:08 UTC · model grok-4.3

classification 🧮 math.OC
keywords paratransit optimizationconstraint programmingroute planningshift schedulingcase studySavannahtransportation planningvehicle routing
0
0 comments X

The pith

A constraint programming model optimizes paratransit routes and shifts to serve more requests.

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

The paper develops a Constraint Programming model that jointly optimizes route planning and shift scheduling for paratransit services. In a case study using data from Savannah, Georgia, this model is shown to be competitive with an AI-accelerated column generation framework. It significantly increases the number of requests served compared to current practices. Allowing flexible shift start times instead of fixed hourly starts provides an additional 5% improvement. The approach is presented as practical and easier to implement for transportation planners.

Core claim

The central discovery is that a Constraint Programming approach can simultaneously handle route planning and shift scheduling in paratransit operations. When applied to real-world data from Savannah, the model matches the effectiveness of more complex methods and outperforms existing operational practices by serving more passenger requests, with further gains from flexible scheduling.

What carries the argument

The Constraint Programming model for joint optimization of routes and shifts.

If this is right

  • The model serves significantly more requests than current paratransit practices.
  • It performs competitively with AI-accelerated column generation frameworks.
  • Flexible shift starts yield an additional 5% increase in served requests.
  • The method is easier to implement for real-world use by transportation planners.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same modeling approach could be tested in paratransit systems of other cities to assess generalizability.
  • Combining this optimization with real-time request handling might improve adaptability to dynamic conditions.
  • Similar joint optimization could apply to other transportation scheduling problems involving both routing and crew shifts.

Load-bearing premise

The model accurately reflects the real-world constraints and data from the Savannah paratransit operations and that comparisons to current practices are representative.

What would settle it

Applying the model to a new paratransit dataset from another location and observing no significant increase in served requests or underperformance relative to column generation methods would falsify the claim.

read the original abstract

Paratransit services are vital for individuals who cannot use fixed-route public transit, including those with disabilities. Optimizing these services is essential for transit agencies to deliver high-quality service efficiently. This paper introduces a Constraint Programming (CP) model to jointly optimize route planning and shift scheduling for paratransit operations, along with practical guidance for real-world implementation. A case study in Savannah, Georgia, demonstrates that the new approach is competitive with a recently proposed, highly effective AI-accelerated column generation framework, and significantly increases the number of requests served compared to current practices. The method is also easier to implement and provides an inherently practical solution for transportation planners. CP further provides the flexibility to optimize schedules without requiring shifts to start exactly on the hour, yielding an additional 5% improvement in the number of requests served.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a Constraint Programming (CP) model that jointly optimizes route planning and shift scheduling for paratransit services. In a Savannah, Georgia case study, the approach is reported to match or exceed the performance of a recent AI-accelerated column-generation method, serve substantially more requests than current practices, and deliver an additional 5% gain when shift start times are allowed to be continuous rather than fixed to the hour. The model is presented as easier to implement than column-generation alternatives.

Significance. If the computational results are reproducible and the modeling assumptions hold, the work supplies a practical, accessible optimization tool for paratransit agencies. The joint encoding of routing, time windows, capacities, and shift constraints in a single CP program, together with the demonstrated benefit of flexible shift starts, could improve service levels for riders with disabilities while remaining implementable by planners without specialized AI expertise.

major comments (2)
  1. [§4] §4 (Computational Experiments) and associated tables: the reported competitiveness with the AI column-generation baseline and the 5% gain from continuous shift starts rest on single-instance objective values and solve times; without multiple replications, statistical significance tests, or sensitivity analysis on key parameters (e.g., time-window widths or vehicle capacities), the strength of the central performance claims is difficult to assess.
  2. [§3] §3 (Model Formulation): the exact encoding of shift constraints, break rules, and the objective function (requests served versus total cost) is only summarized; full variable and constraint definitions are needed to verify that the joint route-and-shift model does not inadvertently relax real-world labor or regulatory restrictions present in the Savannah data.
minor comments (2)
  1. [Abstract] Abstract and §1: the phrase 'significantly increases the number of requests served' should be accompanied by the absolute or relative numbers from the Savannah instance for immediate context.
  2. [§5] §5 (Implementation Guidance): the claim that CP is 'easier to implement' would be strengthened by a brief comparison of modeling effort or solver interface complexity versus the column-generation baseline.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation of minor revision. The comments identify opportunities to strengthen the presentation of our computational results and model details. We respond to each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§4] §4 (Computational Experiments) and associated tables: the reported competitiveness with the AI column-generation baseline and the 5% gain from continuous shift starts rest on single-instance objective values and solve times; without multiple replications, statistical significance tests, or sensitivity analysis on key parameters (e.g., time-window widths or vehicle capacities), the strength of the central performance claims is difficult to assess.

    Authors: We acknowledge that the results are based on a single real-world case study instance drawn from Savannah paratransit operations. Because the work focuses on demonstrating practical applicability to an actual agency dataset rather than benchmarking across synthetic or replicated instances, multiple random replications and formal statistical tests are not directly applicable. To address the concern about robustness, we will add a sensitivity analysis on key parameters including time-window widths and vehicle capacities in the revised version of Section 4. We will also clarify in the text that the observed competitiveness with the AI column-generation method and the additional 5% improvement from continuous shift starts are specific to this operational setting, while emphasizing their practical significance for service levels. revision: partial

  2. Referee: [§3] §3 (Model Formulation): the exact encoding of shift constraints, break rules, and the objective function (requests served versus total cost) is only summarized; full variable and constraint definitions are needed to verify that the joint route-and-shift model does not inadvertently relax real-world labor or regulatory restrictions present in the Savannah data.

    Authors: We agree that the current summary in Section 3 leaves the precise encoding of shift constraints, break rules, and the objective open to interpretation. In the revised manuscript we will provide the complete variable definitions and all constraints, either expanded in the main text or moved to a dedicated appendix. The objective explicitly maximizes the number of served requests subject to a secondary cost term; all shift, break, and labor constraints are taken directly from the Savannah agency’s rules and data without relaxation. The expanded formulation will allow readers to confirm that no regulatory restrictions have been inadvertently omitted. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper applies a standard Constraint Programming formulation to jointly model route planning, time windows, capacities, and shift scheduling for paratransit. Central results consist of computational outcomes on the Savannah instance that are compared against an external AI column-generation baseline and reported current-practice numbers; these outcomes follow directly from solving the encoded model rather than from any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No uniqueness theorem, ansatz smuggled via prior author work, or renaming of known results is invoked to support the claims. The derivation is therefore self-contained against external benchmarks and data.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the validity of the CP formulation and the representativeness of the Savannah case study data. No free parameters, new axioms beyond standard domain assumptions, or invented entities are introduced in the abstract.

pith-pipeline@v0.9.0 · 5674 in / 1246 out tokens · 31330 ms · 2026-05-19T02:08:35.299274+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Fu, L. and G. Ishkhanov, Fleet Size and Mix Optimization for Paratransit Services. Trans- portation Research Record: Journal of the Transportation Research Board , V ol. 1884, No. 1, 2004, pp. 39–46

    work page 2004

  2. [2]

    Department of Transportation, Part 37–Transportation Ser- vices for Individuals with Disabilities

    U.S. Department of Transportation, Part 37–Transportation Ser- vices for Individuals with Disabilities . https://www.transit. dot.gov/regulations-and-guidance/civil-rights-ada/ part-37-transportation-services-individuals-disabilities , 2007

    work page 2007

  3. [3]

    Zhang, X., Y . Yang, A. L. Cochran, N. McDonald, and X. Zhao, Optimizing Demand- Responsive Paratransit Operations: A Mixed Integer Programming Approach. In Confer- ence on Information Sciences and Systems, 2021, pp. 1–6

    work page 2021

  4. [4]

    Lu, J., T. Ye, W. Chen, and P. Van Hentenryck, Boosting column generation with graph neural networks for joint rider trip planning and crew shift scheduling. Transportation Research Part E: Logistics and Transportation Review, V ol. 202, 2025, p. 104281

    work page 2025

  5. [5]

    Operations Re- search, V ol

    Cordeau, J.-F., A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Operations Re- search, V ol. 54, No. 3, 2006, pp. 573–586

    work page 2006

  6. [6]

    Rist, Y . and M. A. Forbes, A New Formulation for the Dial-a-Ride Problem. Transporta- tion Science, V ol. 55, No. 5, 2021, pp. 1113–1135

    work page 2021

  7. [7]

    Kilby, P. and P. Shaw, Vehicle Routing. In Foundations of Artificial Intelligence, Elsevier, V ol. 2, 2006, chap. 23, pp. 801–836

    work page 2006

  8. [8]

    Lam, E. and P. V . Hentenryck, A branch-and-price-and-check model for the vehicle routing problem with location congestion. Constraints, V ol. 21, 2016, pp. 394–412

    work page 2016

  9. [9]

    Van Hentenryck, and P

    Lam, E., P. Van Hentenryck, and P. Kilby, Joint Vehicle and Crew Routing and Scheduling. Transportation Science, V ol. 54, No. 2, 2020, pp. 488–511

    work page 2020

  10. [10]

    Cordeau, and G

    Paquette, J., J.-F. Cordeau, and G. Laporte, Quality of service in dial-a-ride operations. Computers & Industrial Engineering, V ol. 56, No. 4, 2009, pp. 1721–1734

    work page 2009

  11. [11]

    Transportation Research Part B: Methodological, V ol

    Karabuk, S., A nested decomposition approach for solving the paratransit vehicle schedul- ing problem. Transportation Research Part B: Methodological, V ol. 43, No. 4, 2009, pp. 448–465

    work page 2009

  12. [12]

    Kirchler, D. and R. W. Calvo, A Granular Tabu Search algorithm for the Dial-a-Ride Prob- lem. Transportation Research Part B: Methodological, V ol. 56, 2013, pp. 120–135

    work page 2013

  13. [13]

    Braekers, and A

    Molenbruch, Y ., K. Braekers, and A. Caris, Typology and literature review for dial-a-ride problems. Annals of Operations Research, V ol. 259, No. 1, 2017, pp. 295–325

    work page 2017

  14. [14]

    Ho, S. C., W. Y . Szeto, Y .-H. Kuo, J. M. Y . Leung, M. Petering, and T. W. H. Tou, A survey of dial-a-ride problems: Literature review and recent developments.Transportation Research Part B: Methodological, V ol. 111, 2018, pp. 395–421

    work page 2018

  15. [15]

    Rogers, A

    Pavia, S., D. Rogers, A. Sivagnanam, M. Wilbur, D. Edirimanna, Y . Kim, P. Pugliese, S. Samaranayake, A. Laszka, A. Mukhopadhyay, and A. Dubey, Deploying Mobility-On- Demand for All by Optimizing Paratransit Services. International Joint Conferences on Artificial Intelligence, 2024, pp. 7430–7437

    work page 2024

  16. [16]

    Freling, and A

    Huisman, D., R. Freling, and A. P. M. Wagelmans, Multiple-Depot Integrated Vehicle and Crew Scheduling. Transportation Science, V ol. 39, No. 4, 2005, pp. 491–502

    work page 2005

  17. [17]

    Amberg, B. and B. Amberg, Robust and Cost-Efficient Integrated Multiple Depot Vehi- cle and Crew Scheduling with Controlled Trip Shifting. Transportation Science, V ol. 57, No. 1, 2023, pp. 82–105. Jagrowski, Dalmeijer, Ye, and Van Hentenryck 16

    work page 2023

  18. [18]

    Pacheco, A

    Alves, F., F. Pacheco, A. M. A. C. Rocha, A. I. Pereira, and P. Leitão, Solving a Logistics System for Vehicle Routing Problem Using an Open-Source Tool.Computational Science and Its Applications, 2021, pp. 397–412

    work page 2021

  19. [19]

    Silva, A. S., F. Alves, J. L. Diaz de Tuesta, A. M. A. C. Rocha, A. I. Pereira, A. M. T. Silva, and H. T. Gomes, Capacitated Waste Collection Problem Solution Using an Open-Source Tool. Computers, V ol. 12, No. 1, 2023, p. 15

    work page 2023

  20. [20]

    Khanna, A., F. Liu, S. Gupta, S. Pavia, A. Mukhopadhyay, and A. Dubey, PDPTW-DB: MILP-Based Offline Route Planning for PDPTW with Driver Breaks. International Con- ference on Distributed Computing and Networking, 2025, pp. 73–83

    work page 2025

  21. [21]

    Ribeiro, J

    Silva, A., T. Ribeiro, J. Lima, F. P. Fernandes, A. M. T. Silva, H. T. Gomes, and A. I. Pereira, Hybrid Fleet Optimization for Waste Collection: Addressing Urban Constraints Using OR-Tools. SN Computer Science, V ol. 6, No. 5, 2025, p. 482

    work page 2025

  22. [22]

    Furnon, V . and L. Perron, Google OR-Tools Routing Library v9.10 . https:// developers.google.com/optimization/routing/, 2024

    work page 2024

  23. [23]

    Irnich, S. and G. Desaulniers, Shortest Path Problems with Resource Constraints. In Col- umn Generation (G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds.), Springer, 2005, chap. 2, pp. 33–65

    work page 2005

  24. [24]

    ORSA Journal on Computing , V ol

    Glover, F., Tabu Search–Part I. ORSA Journal on Computing , V ol. 1, No. 3, 1989, pp. 190–206

    work page 1989

  25. [25]

    D., Equivalent weights for lexicographic multi-objective programs: Charac- terizations and computations

    Sherali, H. D., Equivalent weights for lexicographic multi-objective programs: Charac- terizations and computations. European Journal of Operational Research, V ol. 11, No. 4, 1982, pp. 367–379

    work page 1982

  26. [26]

    https://catchacat.org/wp-content/uploads/2023-COA-TPD.pdf, 2023

    Chatham Area Transit, Comprehensive Operational Analysis and Transit Development Plan. https://catchacat.org/wp-content/uploads/2023-COA-TPD.pdf, 2023

    work page 2023

  27. [27]

    https://www.catchacat.org/wp-content/uploads/ CAT-State-of-the-System-Report-Final.pdf , 2023

    Chatham Area Transit, Chatham Area Transit State of the Sys- tem Report . https://www.catchacat.org/wp-content/uploads/ CAT-State-of-the-System-Report-Final.pdf , 2023

    work page 2023

  28. [28]

    PACE, Partnership for an Advanced Computing Environment (PACE), 2017

    work page 2017

  29. [29]

    https://www.graphhopper.com/open-source/, 2024

    GraphHopper, GraphHopper. https://www.graphhopper.com/open-source/, 2024

    work page 2024