Deploying Mobility-On-Demand for All by Optimizing Paratransit Services

1 Introduction

There are more than 7,000 public transit agencies in the USA (and many more private agencies), and together, they are responsible for serving 60 billion passenger miles each year. A well-functioning public transit system fosters the growth and expansion of businesses, distributes social and economic benefits, and links the capabilities of community members, thereby enhancing what they can accomplish as a society [Beyazit, 2011; Harvey, 2010; Federal Highway Administration, 2003]. Transit infrastructure is especially important for low-income communities and individuals with disabilities (or short-term issues) as they often do not own or are unable to use private vehicles and must rely on public transit for connecting to employment opportunities, education, healthcare, and other essential services [Federal Highway Administration, 2003]. However, many transit agencies struggle to meet their mission due to decreasing ridership and increasing operational costs. Indeed, existing public transit infrastructure often shows stark inequities; e.g., low-wage workers, people with disabilities, and the elderly have poorer access to transit in USA [Stacy et al., 2020; DeGood, 2011].

A particularly critical component of public transit service in the USA is the paratransit service, which offers door-todoor transportation assistance for individuals who face challenges in using standard transit routes (e.g., individuals with physical disabilities). Paratransit services are directly tied to the United Nations Sustainable Development Goal (UNSDG) 11, which focuses on sustainable cities and communities; indeed, indicator 11.2.1 of UN-SDG 11 specifically seeks to measure the "proportion of the population that has convenient access to public transport, by sex, age, and persons with disabilities" [United Nations, 2020]. Despite its importance, transit agencies typically face operational challenges as there are often limited resources (vehicles, operational budget, and personnel), and paratransit requests are compliant with the regulations of the Americans with Disabilities Act (ADA), i.e., requested pickup and dropoff times must be adhered to (modulo some caveats, e.g., the difference between the pickup and dropoff time must be greater than the minimum time for traveling between the locations). 1

We directly work with a public transit agency in the Published in the Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-24)

1 Specifically, the ADA regulation states that transit agencies must provide service to "individuals with disabilities that is comparable to the level of service provided to individuals without disabilities who use the fixed route system."

southern USA, the Chattanooga Area Regional Transportation Agency (CARTA), that exemplifies the transit challenges faced by mid-sized southern cities, where agencies have to balance the dichotomy between improving service coverage, improving ridership, and lowering operational costs [Shrikant, 2018]. CARTA spends more than USD $1.1 million annually on fuel while supporting a number of different transportation modalities, including a fixed-route service, demand-response service (using neighborhood shuttles), and paratransit service (we show a snapshot of the paratransit service in Figure 1). CARTA provides over 3 million passenger trips per year through these three services. However, operations are inefficient regarding productivity and energy consumption per passenger per mile. In particular, the paratransit operations account for 22% of total service miles but less than 4% of passenger trips. We work with CARTA to improve the efficiency of their paratransit fleet.

From a technical standpoint, the operational challenge of optimizing transit fleets entails solving a set of complex mathematical optimization and planning problems. At the core of transit optimization lies a vehicle routing problem (VRP). VRPs can be divided into two major categories: offline VRPs consider how to optimally allocate vehicles to a set of requests that is known completely apriori, whereas online VRPs, process requests as they arrive in real-time. Paratransit service, in practice, deals with both these problems. Paratransit trips are usually scheduled at least a day beforehand, i.e., before each day, agencies can strategically plan paratransit vehicle routes based on requested pickup and dropoff spots and designated pickup time frames. A small percentage of the requests arrive in real-time, and operators seek to accommodate these requests as the vehicles move around the city. Second, to ensure that the algorithms translate to deployment in practice, we must develop production-quality software and visualization interfaces for transit operators and drivers. Third, and arguably most importantly, deploying artificial intelligence and data-driven solutions in practice requires active and sustainable collaborations with transit agencies. These problems of prediction, optimization, planning, and software development must be solved together to translate algorithmic development into practice.

In this paper, we discuss how we develop a set of principled data-driven optimization modules for improving the efficiency of paratransit services in a mid-sized city in the southern USA. We describe our collaboration with CARTA in this paper , provide a background of the algorithmic approaches we developed, share an overview of the software tool for optimizing paratransit, present simulation results for validation on real-world data, and finally present results from the deployment of our toolchain in the city. We make the following contributions:

1. We describe the paratransit optimization problem from the perspective of a real-world transit agency and discuss both offline and online versions of the problem.
2. We describe how our formulation accommodates specific constraints faced by paratransit services (often not by traditional ride-sharing services). Then, we describe an offline and an online solution approach for solving the paratransit service problem. Our solution approaches are

simple and can be implemented by using off-the-shelf VRP solvers, thereby facilitating easier deployment.

1. We present results from real-world data and a pilot study from a mid-sized southern city in the USA.

2 Background

We begin by providing a brief overview of VRPs. Broadly, the VRP is a well-studied combinatorial optimization problem that deals with the optimal design of routes to be used by a fleet of vehicles to serve a set of customers [Dantzig and Ramser, 1959]. Such problems have been extensively modeled as mixed-integer linear programs (MILP), a class of optimization problems known to be NP-hard, i.e., they are computationally intractable to solve for large problem instances [Lenstra and Kan, 1981]. Often, VRPs are also modeled as planning problems that involve optimizing decisions over time under future uncertainty, e.g., optimizing the set of routes for a fleet of vehicles in real-time to serve a given set of customers while new customer orders arrive dynamically [Toth and Vigo, 2002; Pillac et al., 2013]. Such problems are often modeled as Markov decision processes (MDP) [Archetti et al., 2020; Wilbur et al., 2022; Joe and Lau, 2020]. While both the ILP and the MDP settings for transportation optimization are computationally challenging to solve for large problem instances (e.g., optimizing city-wide transit), there are well-established heuristic approaches [Alonso-Mora et al., 2017; Kim et al., 2023; Wilbur et al., 2022], that can solve these problems reasonably well (i.e., close to optimality). While these approaches can be used to model generic on-demand ride-sharing problems, the paratransit domain presents several unique challenges that we highlight below.

2.1 Paratransit Challenges

Paratransit services can resemble traditional on-demand ridepooling services in some ways (e.g., the arrival of real-time requests and ride-sharing); however, our collaboration with CARTA revealed several critical differences between traditional DVRPs and paratransit services. We point out some of these key differences below, which are especially important for deployment.

Variable capacity constraints: Similar to traditional ondemand ride-pooling services, paratransit services have constraints on pickup times, dropoff times, and vehicle capacities. However, unlike most applications (or models) of VRPs, paratransit services pose the unique challenge of varying capacities due to the presence of both ambulatory and wheelchair-bound passengers. A wheelchair requires more space than a regular seat in a paratransit vehicle. In this setting, most agencies have flexible seating-enabled vehicles whose seats can be folded to accommodate additional wheelchair passengers at the expense of ambulatory passengers. Wheelchair passengers can also take longer to board and depart the vehicle, which must be considered as this constraint might potentially cause the vehicle to violate a future pickup or dropoff constraint.

Travel time constraint: In the case of our partner agency (and many other public transit agencies that operate paratransit ser-

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Special Track on AI for Good

Published in the Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-24)

(b) Paratransit deadhead miles

Figure 2: CARTA's paratransit metrics: (a) Paratransit wheelchair and ambulatory riders per day in February 2020. (b) Deadhead and passenger miles per day in February 2020 for paratransit vehicles. Deadhead miles are defined as miles driven without passengers.

vices), regulations dictate that paratransit trips must not take longer than the longest comparable fixed-line route.

Strict time windows: The Federal Transit Administration presents guidelines about the maximum wait times for paratransit passengers. Consequently, transit agencies must add substantial slack to their schedules and limit trips to only a few passengers each, leading to low efficiency.

Guaranteed service: Additionally, not all requests are equal. Requirements associated with the Americans with Disabilities Act (ADA) mandate that ADA-eligible clients must be serviced when requesting trips within a certain radius of public fixed-line services (with some caveats on the agency being given enough time to plan for the trip). We show a summary of paratransit ridership and miles traveled by vehicles for CARTA in Figures 2a and 2b, respectively.

3 Model

The core decision-making and computational problem that transit agencies must tackle for operating paratransit services is a VRP, i.e., the agency must assign routes to vehicles that pick up and drop off passengers at designated locations and times. As we highlighted before, paratransit requests can either be made (at least) a day in advance or in real-time. While agencies are not obligated to serve requests made in real-time, most public transit agencies, including CARTA, strive to accommodate these requests. As a result, transit agencies typically require two variants of VRPs-an offline VRP model (and solver) that handles the day-ahead requests and an online VRP model (and solver) for handling requests made in realtime. While both offline and online VRPs have been studied extensively, they have not been studied in the context of paratransit services, which pose domain-specific challenges. A notable exception is a prior work by Sivagnanam et al., who study offline VRPs (specifically, a VRPPDTW) with online bookings in the context of paratransit services [Sivagnanam et al., 2022]. Our offline model is closely related to theirs with a simplified booking process. Note that our focus on leveraging prior work and not seeking to present a novel problem definition is rooted in our goal of deployability. Crucially, as we highlight later, our model can be directly solved by offthe-shelf solvers.

We begin by introducing our model for the offline VRP, which builds upon the classical VRPPDTW model with time windows [Toth and Vigo, 2002]. We use the same notation as Toth and Vigo to allow readers to cross-reference between our formulation and the formulation provided in prior work [Toth and Vigo, 2002]. We use a request-based model for the VRPPDTW, which deals with n requests, each with its pickup and delivery locations (or nodes), and associated time windows. Let i be a request in the network made up of two nodes, i and n + i, which correspond to the request's pickup and dropoff locations, respectively. Naturally, in this formulation, different nodes can be simultaneously at the same geographical location. Let P be the set of pickup nodes, where P = {1, . . . , n} and let D be the set of drop-off nodes, where D = {n + 1, . . . , 2n} Let the set of all nodes be N, i.e., N = P ∪D. Let the number of ambulatory passengers and passengers who use wheelchairs for request i be denoted by dai and dwi , respectively. We use ℓai and ℓwi denote the incremental capacity affected by request i; therefore, ℓai = dai , ℓwi = dwi and thus ℓan+1 = -dai , ℓwn+i = -dwi .

Next, we define the set of vehicles as K. Where each vehicle has a set of nodes it can service, Nk = Pk ∪Dk, where Nk, Pk, and Dk are subsets of their respective sets. Each vehicle k has its own network where we let Gk = (Vk,Ak) be a directed graph. We set Vk = N ∪ {o(k), d(k)} to contains the set nodes of for vehicle k, including the origin, o(k), and destination d(k), which are its depots. Ak is the subset of Vk ×Vk, which is made up of all feasible arcs. Each vehicle k has a capacity Cak for ambulatory passengers and a capacity Cwk for wheelchair passengers. Each vehicle also has a travel time τijk and cost cijk between unique nodes i, j ∈ Vk. We make the assumption that vehicle k leaves its origin depot without any passengers at time ao(k) = bo(k), each vehicle must have an admissible route which a corresponding feasible path from o(k) to d(k) within the network Gk, no node in Gk can be visited more than once, and a vehicle must visit a chosen node, i ∈ N, within the time window [ai, bi] when the service si must begin.

3.1 Solution Space

We extend a standard vehicle routing problem with pickup and delivery and time windows [Toth and Vigo, 2002] with additional capacity constraints. Our decision variables are as follows: binary flow variables xijk ∈ {0, 1} that indicate if arc (i, j) ∈ Ak is used by vehicle k, time variables tik ∈ R≥0 that indicate when vehicle k starts the service at node i ∈ Vk, and two load variables yaik ∈ R≥0, for ambulatory passengers and ywik ∈ R≥0 for wheelchair passengers. Both give the load of vehicle k once the service at node i ∈ Vk has been completed. We minimize the total travel cost under the following linear objective function:

subject to the following sets of constraints M:

∑

i∈Nk∪{o(k)}

where constraints (2a) enforce that each request is served exactly once, and Constraints (2b) require that each request is served by the same vehicle. Constraints (2c-2e) ensure

xijkthat vehicle k starts from its origin depot o(k) and ends its route at its destination depot d(k), forming a multicommodity flow structure. Constraints (2f) handle the compatibility requirements between routes and schedules, while constraints (2g) implement the time windows for each vehicle and their nodes/stops. Constraints (2h) ensure that each request is picked up before it is dropped off. Constraints (2i2l) handle the compatibility requirements between routes and vehicle loads. Next, constraints (2j-2k, 2m-2n) enforce capacity intervals at pickup and delivery stops/nodes, for each vehicle. Lastly, Constraints (2o-2p) ensure that the starting load of each vehicle is 0. Note that under this implementation, a route's duration can only be at most bd(k) - ao(k). A vehicle is also allowed to wait before it visits a node under Constraints (2f-2g). Finally, the arrival time at an arbitrary node j can be calculated as:

For the online VRPPDTW, the same set of constraints apply. However, the requests arrive one at a time and must be accommodated into existing schedules. A summary of the notation can be found in Table 1 below.

3.2 Solution Approaches

To solve the offline VRP, we can directly use an off-the-shelf VRP solver. Specifically, we use the guided local search from Google OR-Tools VRPTW solver. For the online problem, we use an insertion heuristic [Wilbur et al., 2022] that seeks to insert a request into an existing schedule without violating any constraints. While an insertion heuristic is not optimal (as it does not alter the order of existing requests that a vehicle has committed to), it often works fairly well in practice. To quantify the insertion quality, we choose the insertion position that minimizes the VMT/PMT ratio for the resulting vehicle schedule, where VMT and PMT refer to vehicle and passenger miles traveled, respectively. Specifically, VMT represents the total vehicle miles traveled by a vehicle over a day, including the miles when the passenger(s) are on board and when a vehicle travels without any passengers on board; PMT, on the other hand, is the summation of the shortest path between origin and destination for each OD pair in the dataset for a specific day. Therefore, PMT represents Published in the Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-24)

the vehicle miles required if each passenger drove directly between their corresponding origin and destination. Using VMT/PMT as the criteria for insertion penalizes longer vehicle miles traveled compared to the shortest route for each passenger.

Human in the Loop Solution

While algorithmic solutions can maximize desired objectives, e.g., service rate, such approaches often do not consider the domain knowledge known by the public transit operators. During our discussions with CARTA, we found that considering such domain knowledge is imperative for the smooth operation of real-world transit fleets. For example, a transit supervisor might know that a physically disabled passenger trusts a specific driver over many years and feels comfortable boarding a vehicle with a wheelchair with help from the said driver. Such tacit knowledge is often critical in practice, and we hypothesize that algorithmic solutions deployed for realworld transit fleets (and particularly paratransit services) must enable human supervisors to modify solutions generated by the algorithm. To enable such modification, we provide ways for CARTA to edit the generated solutions while also suggesting to them the feasibility of potential for constraint violations. We also allow them to override a solution if they so choose. Figure 3 shows the online screens of the deployment system that show the routed trips and the ability to switch the trips between a route and another bucket, which can be another route or the unrouted category. In our developed software system, edits require a simple drag and drop validated through a constraint checker that facilitates easy and seamless operation for the end user. For example, the online interface does not allow a client's drop-off card to be moved before the pick-up card. Also, the schedule validation generates warnings based on potential travel time violations or if the pick-up and drop-off times are outside the windows. Once saved, the schedule is communicated to the corresponding driver in realtime (if it is a same-day change).

4 Experiments

4.1 Dataset and Experimental Setup

We conduct our validation in two phases. First, we validate the algorithmic approaches using real-world paratransit data collected by CARTA. Then, we validate the proposed approach through a deployment exercise. The code and a sample of simulated data is publicly available 2 .

Real-World Paratransit Data

We run experiments for all solvers with real-world paratransit data from CARTA from August 13th, 2023. The paratransit fleet consisted of 15 vehicles available with schedules staggered between morning and afternoon shifts according to CARTA's driver and vehicle availability and a total of 125 passengers. Each request in the dataset consisted of a geocoordinate (longitude, latitude) for the pick-up location and drop-off location, as well as the requested pickup time. It also contained the capacity type for each request, with the option of ambulatory or wheelchair.

In addition to the set of requests, we also use CARTA's scheduled manifest and driver schedules for August 13th, 2023, where a manifest refers to an ordered list of locations that a vehicle will visit. Each entry in the manifest is marked with an action, pick-up or drop-off, and estimated arrival time. The manifest and driver schedules allow us to calculate CARTA's metrics for comparison against our solvers. CARTA uses a black-box software product to generate the manifests. We instantiate constraints for the VRP by using the same real-world constraint that CARTA follows: 1) the time window, i.e., the amount of time before he requested pickup time that a request can be picked up, is set to 15 minutes; 2) The vehicle capacity is set to maximum 8 ambulatory passengers and 2 wheelchair passengers (based on CARTA paratransit vans); 3) the dwell time, i.e., the estimated duration that a vehicle will stay at a location to pick-up/drop-off a passenger is set to 5 minutes; and 4) any trip request that can not be serviced within the time windows is dropped, i.e., not considered.

Road Network and Travel Time Matrix

We use OpenStreetMap (OSM) [OpenStreetMap contributors, 2017] for the road network construction and OSMNX [Boeing, 2017] to generate a routing graph of the road network with travel time for edge weights. The travel time matrix is computed offline by calculating the shortest paths between all pairs in the network, with free flow speed as the edge weight.

4.2 Offline Solver

Given a set of requests for August 13, 2023, we generate a manifest using our offline VRP solver. The objective of the solver is to minimize vehicle miles traveled (VMT) with an additional large penalty term for dropping a trip request. Table 2 shows the manifest metrics for multiple solvers. We observe CARTA operations average a VMT/PMT ratio of 1.31; the offline solver reduces VMT/PMT by 21.3% while servicing the same number of requests with the same vehicle configurations. It is also important to note that the offline solver is more efficient with a higher shared rate than CARTA, meaning 85% of vehicle trips have more than one passenger on board for a given time. CARTA's manifest also contained 12-time window violations, meaning passenger requests were scheduled to be served outside of the 15-minute time window constraint, while the proposed offline solver did not violate any time constraints.

2 https://github.com/smarttransit-ai/ijcai-deploying-mobility-ondemand

4.3 Online Solver

To evaluate the online solver, we simulate real-time requests from the real-world data collected from CARTA. We randomly split the set of requests into two parts and treat one part as the set of day-ahead requests and another as the set of real-time requests. Our experiment design mimics CARTA's operational constraints, where a set of requests are available a day in advance, and at times, real-time requests must be accommodated while serving the day-ahead requests. For example, a 70-30 split denotes that 70% of requests are available a day in advance (to be solved by the offline solver), and 30% of requests arrive in real-time as same-day requests. In this case, our online solver is called for each real-time request as they arrive. The request arrival time, defined as the time before the requested pickup time that the request is available to the system, is set to 30 minutes.

We present the results of the online solver in Table 2. We observe that even when 70% of the requests are known in advance, the proposed approach outperforms CARTA's approach even if it knows all requests in advance. The performance gain is captured in lower VMT/PMT ratios, lower VMT, lower VDM, and a higher shared rate. We also observe that if a significant proportion of the trip requests are made in real-time (e.g., more than 40% of requests), then the proposed online solver fails to accommodate all requests while maintaining all paratransit constraints; e.g., in such a situation, 115 out of 125 passengers are served. In practice, the current operating conditions of CARTA resemble a 90-10 split, which the online solver can easily accommodate.

5 Paratransit Pilot

Having validated the proposed approach in simulation by using real-world data from CARTA, we conducted a pilot exercise. Before describing the results, we highlight that conducting a pilot exercise that deploys an algorithmic approach is extremely difficult for public transit agencies, particularly in the context of paratransit service, as regulations mandate performance and service standards. We ran a pilot in August 2023 with CARTA's paratransit team with the offline approach. The goal of our pilot was the following: first, we aimed to evaluate the integration of our offline VRP optimizer with the paratransit service of CARTA. Second, we wanted to evaluate the algorithm during real-time operations. This goal involved equipping drivers with a tablet mounted in the vehicle that contained their schedule and monitoring operations through a real-time web interface with members of CARTA's operations team (Fig. 4). Third, we wanted to gain feedback from schedulers and drivers on system usability and identify possible improvements going forward.

5.1 Pilot Design and Setup

We selected August 3, 2023, and August 10, 2023, for the pilot. We generated new manifests based on the proposed approach, which were actually deployed by CARTA. To compare the efficacy of the proposed approach, CARTA also generated manifests using their existing black-box approach. We exported the trip requests, driver schedules, vehicles, and scheduled manifests from CARTA's existing system. On both days, there were 15 vehicles available, with schedules staggered between morning and afternoon shifts according to CARTA's driver and vehicle availability. There were a total of 159 passengers and 129 passengers on August 3rd and 10th, respectively.

For the deployment, CARTA followed strict time window constraints for two types of passenger requests. CARTA mandated that pickup-constrained requests must be picked up within a 15-minute window before or after the requested pickup time, and the passenger must be dropped off within an hour of the requested pickup time at their destination. Dropoff-constrained requests represent situations where a passenger must be dropped off before the requested dropoff time and must be picked up no earlier than one hour before the appointment (e.g., these constraints often represent medical appointments in CARTA's data). Additionally, each vehicle had two capacity constraints-no more than 8 ambulatory passengers and 2 wheelchair passengers could be on a vehicle at a given time.

5.2 Evaluation of Offline VRP Solver

We present the key metrics related to the performance of CARTA's original schedule compared to the schedule generated by the offline VRP solver in Table 3. As shown, the proposed approach reduced VMT by 356 miles on August 3, 2023, and by 236 miles on August 10, 2023. There was a 24% and 17% improvement in VMT/PMT over CARTA's initial paratransit schedule for August 3, 2023, and August 10, 2023, respectively. The efficiency gain correlates with the finding that our implementation had a much higher shared Rate, which is the percentage of passengers who shared their trip with at least one other passenger compared to CARTA's schedule.

5.3 Post-Deployment Feedback

After the pilot, we conducted a qualitative survey of drivers to evaluate their experience with the proposed system. Recurring themes from the feedback were, User-Friendly, Efficient, and Easy to use with one driver noting that "It was great to have something like that to rely on when you need it [the application] instead of calling it [a problem] in to dispatch."

We also conducted interviews with paratransit operators at CARTA. When interviewing the operators, they explained that without the proposed offline optimizer, it would take approximately six hours in a ten-hour day to generate a schedule for a day, compared to the proposed offline optimized generating manifests 'within minutes'. When asked about positive attributes of the application, one operator said when it comes to tweaking schedules after generation, to account for domain knowledge and expertise, it took "...about 50% less than what we would have to do, which is very good to me."

6 Conclusion

In collaboration with CARTA, we present data-driven optimization modules for paratransit services. We evaluate the offline and online algorithms on real-world paratransit data. The successful validation of the proposed approaches resulted in a pilot deployment, which showed that our approach comprehensively outperforms existing approaches followed by CARTA. Our software module and the model can be configured easily with agency-specific constraints and allow for transit operator intervention with violation checking. Crucially, our technological intervention for CARTA only amplifies the existing paratransit initiative rather than creating a new one, thereby resulting in a framework that is more likely to reach and maintain deployment [Toyama, 2015].

Acknowledgements

This material is based upon work sponsored by the National Science Foundation under grant CNS-1952011 and the Department of Energy under Award Number DE-EE0009212.