Artificial Intelligence for 8/10/2025 Optimizing Integrated Service in Mixed Fleet Transit Operations DE-EE0009212 Final Scientific Report Contents 1 Introduction 1 2 Progress Report (Phase I and II) 2 2.1 Paratransit optimization algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Offline Vehicle Routing Problem with Online Bookings . . . . . . . . . . 3 2.1.2 Offline Paratransit Vehicle Scheduling via Rolling Horizon Optimization . 5 2.1.3 Online Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Transit-Gym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 E-Transit Bench: Extending the Transit-Gym with Electric Grid Simulation 13 2.3 Improving the Occupancy Estimation Algorithm . . . . . . . . . . . . . . . . . . . 15 2.3.1 Using Neural Network Architectures . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Using Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Application Programming Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 Paratransit Web Application . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Community Engagement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Performance Analysis and Go/No Go Milestone 22 4 Progress Report (Phase III) 22 4.1 Field Test Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1 Algorithm Evaluation and Pre-Deployment . . . . . . . . . . . . . . . . . 23 4.1.2 Offline Solver Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.3 Online Solver Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.4 Improvement to the Operational Backbone . . . . . . . . . . . . . . . . . 24 4.2 Initial Pilot Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.1 Initial Pilot Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Clifton Hills Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.1 Ridership Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3.2 Common Destinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3.3 Operational Obstacles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3.4 Community Engagement . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3.5 Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Conclusion and DOE Impact 29 A API Documentation 32 B Publications 47 2 Chattanooga Area Regional Transportation Authority | August 2025 1 Introduction CARTA exemplifies the efficiency challenges that transit agencies face throughout the U.S., espe- cially in mid-sized southern cities, where agencies have to balance the tension between improving service coverage and improving ridership. CARTA spends more than $1.1 million annually on fuel while supporting several different transportation modalities, including a fixed-route service, demand-response service (using neighborhood shuttles), and paratransit service. Through these three services, CARTA provides over 3 million passenger trips per year. The goal of the project is to integrate the operations to gain efficiency. For example, paratransit operations account for 22% of total service miles but less than 4% of passenger trips. We hypothesize that there is a significant opportunity for lowering the overall energy cost if we focus on systemwide integration, which co-designs the schedules and services of fixed-route transit, microtransit, and paratransit. In particular, we observe the transit agencies can solve these problems at three levels (a) deciding the area and frequency of fixed-line trips; (b) deciding the areas and services that can be served through integrated paratransit and microtransit operations; (c) optimizing the vehicles that are used for each trip, considering that the advantage of Electrical Vehicles (EVs) over Internal Combustion Engine Vehicles (ICEVs) varies depending on the route and time of day (e.g., the benefit of EVs is higher in slower traffic with frequent stops and lower on highways), the assignment can have a significant effect on energy use and, hence, environmental impact; and finally, (d) working to optimize the charging schedules and charger placements to reduce the overall impact on electrical grid. Developing scalable algorithms for real-time fleet management and operational optimization is a challenging problem. Specifically, it requires solving scheduling problems that are variants of the classical Vehicle Routing Problem (VRP) and the related Dial-a-Ride Problem, which are NP- hard and typically solved using heuristic methods. Further, the problem solution poses a big data challenge due to scale and heterogeneity. While there is a long and rich literature of heuristic techniques for solving VRP problems, scala- bility has been an issue even for heuristic methods. Typically, scalability is handled by decompos- ing the VRP problem into a trip generation phase, which creates candidate trips, and an assignment phase, assigning the fleet to a subset of the candidate trips. While this decomposition leads to in- creased scalability, these two sub-problems are NP-hard and require algorithmic sophistication. Further, decisions must be made facing uncertainty (e.g., future demand requests and traffic con- ditions). Despite these uncertainties, transit services must meet strict requirements: paratransit requests must be served within a limited time, fixed-route schedules must be closely followed, and many of these decisions must be made in real-time. In this project, we are designing decision- theoretic algorithms that solve the aforementioned challenges. The project is divided into three phases. In the first phase, we focused on the paratransit services as it provides a great opportunity for optimization.1 Paratransit services are provided by transit agencies as a supplement to fixed-route services to ensure equity for disabled people who can- not use fixed-route transportation. However, the demand varies significantly over the course of a week (Fig. 1b). One of the challenges in handling paratransit operations is the Federal Transit Administration guideline that limits the maximum wait times for passengers. Without adequate 1 In prior work [1], the team has already developed algorithms for optimally (minimizing total energy impact) assigning vehicles of different types to fixed-route trips given predicted traffic and weather conditions and considering road elevation changes. Page 1 Chattanooga Area Regional Transportation Authority | August 2025 (a) Fixed route transit (b) Paratransit ridership (c) Paratransit deadhead miles Figure 1: (a) Courtesy and planned stops for fixed-route transit per route from January 2020 to April 2020. (b) Paratransit wheelchair and ambulatory riders per day in February 2020. (c) Deadhead and passenger miles per day in February 2020 for paratransit vehicles. Deadhead miles defined as miles driven without passengers. optimization procedures, transit agencies add substantial slack to their schedules and limit trips to only a few passengers each, which leads to low energy efficiency. We can quantify this loss using deadhead miles, which are miles driven by paratransit vehicles without any passengers (Fig. 1c). 2 Progress Report (Phase I and II) Table 1: Milestones and Status Milestone Type Description Status API Design Technical API design of all services is complete and compati- API Design and prototype in- bility checked. Final design and compatibility sum- tegration is complete. De- mary sent to DOE Project Officer. tails are included in the re- port. (Section 2.4.1) Data Collection Design Technical Design and Develop Camera Based OD and CTU We have achieved passenger Data Collection. Algorithms for camera-based OD detection with a MAPE of and CTU data collection will be deployed and val- less than 9%. (Section 2.3.2) idated with test camera streams with 75% or better accuracy First Simulation Table-Top Exercises Technical Demonstration with simulation. The results show im- We have demonstrated the provement of coverage and energy efficiency with use of the three algorithms the AI methods compared to the operation research and the complete integrated benchmark optimization. The simulation table exer- system through papers and cise report will show a full day transit trip execution presentations. The associated scenario. papers are attached in the re- port. (Appendix B) Initial Concept Report Go/No-Go Demonstration with simulation and comparison on Our algorithms show im- the scenario between the AI methods and the bench- provement by 5 % for fixed mark method complete with more than 5% improve- line systems and our para- ment in the coverage and energy efficiency shown us- transit algorithms uses 42 ve- ing the simulation. The demonstration results will be hicle runs instead of 96 in documented in a report. real-word. (Section 3) Our tasks in Phase I and Phase II are summarized below. 1. Develop the paratransit optimization algorithms that can reduce the slack in the system and make the system more efficient. 2. Design and develop camera based algorithms that can provide accurate information about occupancy levels in the vehicles. 3. Develop a simulation system which can be used to simulate the impact of transit policies and charging times on the stability of the grid. 4. Integrate the para-transit application into an online web application and develop the neces- sary application programming interfaces. 5. Demonstrate that the efficiency improvement of the designed algorithms is greater than 5%. Page 2 Chattanooga Area Regional Transportation Authority | August 2025 Table 2: Milestones and Status for Budget Phase II Milestone Type Description Status Data Collection Technical OD Data collection installed and operational on 50% Complete. of the fleet. OD data collection has been delayed due to operational constraints on vehicle data transfers – pending resolution. New camera technology is in pi- lot phase. AI Optimization Engine Technical Demonstration of the capability of the AI optimiza- Complete. tion engine to handle uncertainty in trip times, main- tenance, and trip roster concerns for 10% of the trips. The AI engine will be shown to operate at full trip load of the agency in the simulation. System Integration and Evaluation Technical Demonstration with simulation and comparison on Complete. the scenario with the benchmark methods. Analyses to compare energy spent per passenger per mile, pas- senger wait times, service coverage, and computation costs complete. Results and analysis sent to the DOE Project Officer. Refined Concept Tested Report Go/No-Go Report of major findings on the design of the system Pilot testing completed; anal- sent to the program manager. The AI Engine is able yses and report submitted. to schedule the two-day pilot study trips (2 paratransit vehicles). Plan for the full experiments in BP3 sent to the DOE Project Officer. 6. Install origin and destination collection systems on 50% of the fleet. 7. Demonstrate the AI optimization engine on a scaled-down version of the real-world data and synthetic datasets calibrated for the real world. 8. Analyze the performance of the simulations with benchmark methods on several metrics. The tasks and their status are shown in Table 1 and Table 2. Tasks for both Phases were com- pleted in sequence however the reports have been aggregated into a single, self-contained section for completeness. 2.1 Paratransit optimization algorithms Our current progress includes three parts of the online integrated optimizer that arranges the paratransit dispatch trip roster: online booking, day-ahead scheduling, and real-time requests. The offline vehicle routing problem with online bookings is a reinforcement-learning inspired technique that provides the ability to create coarse solutions as each request from a client arrives on the phone (at least a day before). The technique uses a simulated-annealing method as the any-time algorithm to reduce the size and complexity of the action space [2]. Eventually, the solutions are refined using a day ahead scheduling algorithm [3] that builds upon prior work by Co-PI Samaranayake from Cornell University [4]. The critical insight is that we can use an online solver in the offline mode and avoid the complexity of computing the solution for the whole day in one shot and considering smaller time windows in a rolling horizon fashion. Finally, the real-time requests on the day of travel are addressed using a Monte Carlo tree search approach [5]. The advantage of online scheduling is the ability to handle uncertainties and complex constraints. Our initial results are promising and show that the heuristics can handle large vehicle capacities and provide results within a few seconds. We describe the key algorithms below. 2.1.1 Offline Vehicle Routing Problem with Online Bookings Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. During the research, we identified a real-world problem that is not addressed Page 3 Chattanooga Area Regional Transportation Authority | August 2025 Reduction in Cost 60 % 40 % 20 % 0% −20 % 2 hours 3 hour 4 hour Broad Window Size Figure 2: Reduction in total cost due to using our approach for selecting tight pickup windows supported by anytime algorithm, compared to using naı̈ve pickup windows with VROOM (■) and Google OR-Tools (■) as offline VRP solvers. by existing formulations. When passengers book trips over the phone, they often request broad pickup windows (e.g., going for groceries in the afternoon, sometime between 2pm and 5pm). While passengers may have no preference between pickup times within these broad windows, they do strongly prefer to know in advance when they will be picked up. So, transit agencies must confirm a tight pickup window (e.g., 30 minute interval within the broad window) at the time of booking. The reason for this is very practical: vehicles may arrive at any time within the confirmed windows, and passengers need to be ready to be picked up. This presents an interesting online optimization problem: how to select tight pickup windows at the time of booking, based on information available at the time, assuming that vehicle routes will be optimized as an offline VRP once all the trips have been booked? To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests—similar to offline VRPs—but must abide by strict constraints on running time— similar to online VRPs. We formulate this as the offline vehicle routing problem with online bookings. We assume that trip requests with broad pickup windows are received one-by-one, and for each request, a tight pickup window must be selected in a matter of seconds. At the end of the booking process, vehi- cle routes are optimized as an offline VRP based on the selected tight windows.The objective of optimizing the tight pickup windows is to minimize the cost of the resulting offline VRP. Our so- lution approach combines an anytime algorithm with a reinforcement-learning based policy. The anytime algorithm is executed between consecutive requests and provides supporting input for the policy, taking advantage of the extra time between requests (e.g., there may be 5 minutes between consecutive calls, but only a few seconds to respond during a call). The policy is responsible for selecting tight pickup windows, taking advantage of the input received from the anytime algorithm. The advantage of a learning based policy is that its computational cost is very low once it has been trained on historical data. Next, we demonstrate the effectiveness of our proposed approach by showing that optimizing tight pickup windows can lead to significant reductions in cost. Since the online bookings problem is novel to the best of our knowledge, existing VRP solvers do not address the online selection of tight pickup windows. Therefore, to provide baselines for comparison, we consider existing offline VRP solvers with “naı̈vely selected” pickup windows, which we define as selecting the middle interval of broad pickup windows as tight windows. Fig. 2 shows the reduction in the total cost of vehicle routes due to using our proposed approach, Page 4 Chattanooga Area Regional Transportation Authority | August 2025 compared to using VROOM and Google OR-Tools with naı̈vely selected pickup windows. For each comparison, we evaluate the algorithms on 180 days of paratransit data, and plot the distributions. We observe a significant reduction in costs compared to both baseline solvers. Further, we find that our approach is robust to variations in the duration of broad pickup windows since it maintains a significant advantage when broad windows are 2- or 4-hours long, even though the decision policy was trained only on 3-hour broad windows. This approach was published in the following paper: Amutheezan Sivagnanam et al. “Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit”. In: 31st International Joint Conference on Artificial Intelligence (IJCAI). July 2022. 2.1.2 Offline Paratransit Vehicle Scheduling via Rolling Horizon Optimization While the previous approach described above was focused on optimized and changing the book- ing windows to be more optimal, the second algorithm we have developed focuses on the day-ahead optimization once the booking windows have been finalized. Our approach uses a rolling horizon framework that provides a better trade-off between computational efficiency and solution qual- ity. In particular, our approach uses an online optimization technique that decomposes the fixed time horizon and solves a sequence of much smaller optimization problems. The benefit of such an approach is tractability and fast computation. However, using small batch sizes has an innate limitation of being myopic because it makes greedy vehicle dispatching decisions with restricted information in each batch. Therefore, in our approach we use a a rolling horizon framework that considers a sliding window of larger time intervals and utilizes more information (from the offline problem instance), while still limiting the computational cost in each batch. Note that for each batch we utilize our prior work [4]. Table 3: Overview of Datasets NYC NYC CARTA Scenario 1 Scenario 2 Number of Days 30 31 31 Mean Requests Per Day 172 129 2587 Std. Dev. Requests Per Day 33 29 570 We tested our algorithm on two datasets as shown in Table 3. First, we used paratransit trip requests data provided by a public transit agency. Second, we used New York City taxi data to investigate the scalability of our approach on a larger dataset. In particular, we randomly sampled 20% of the NYC requests with an average of 2,587 requested trips per day. Our comparison is against two baselines. The first baseline is a fully online solver where we we use our own approach with a rolling horizon factor of 0 to represent the online solver. By setting the rolling horizon factor to 0, our solver is simplified to a purely online approach as it does not utilize future knowledge. We refer to this baseline as RH0 comparing to our approach RH1, RH2, RH3, which used rolling horizon factor of 1, 2, 3, respectively. Note we tried the problem with a a heuristic using guided local search (GLS) [6] implemented in Google OR-Tools, the commonly used open source VRP solver [7] as well. However, the scale of the problem with a limited maximum computation time for a given day of one second per request was unable to be solved by the Google OR tool. Page 5 Chattanooga Area Regional Transportation Authority | August 2025 RH0 RH1 RH2 RH3 RH0 RH1 RH2 100 % 100 % 90 % 90 % 80 % 80 % 70 % 70 % 60 % 60 % 50 % 50 % 40 % 40 % 3 4 5 6 7 30 40 50 60 Number of Vehicles Number of Vehicles (a) (b) RH0 RH1 RH2 RH3 RH0 RH1 RH2 1 1.5 0.8 0.6 1 0.4 0.5 0.2 0 0 3 4 5 6 7 30 40 50 60 Number of Vehicles Number of Vehicles (c) (d) Figure 3: (a) Service rate evaluated on the CARTA paratransit dataset. (b) Service rate evaluated on NYC dataset. (c) Computation time per request evaluated on the CARTA dataset. (d) Compute time, NYC dataset. The service rate per day for the 30 experimental days is provided in Fig. 3a. Overall, our frame- work (RH1, RH2, RH3) outperforms the online approach (RH0). In an experiment with 7 fleets, RH3 brings an increase in service rate from 84.2% to 92.2% compared to RH0, which corresponds to a 9.5% increase. We observe that the slope of the service rate is reduced as the rolling hori- zon factor increases. This is because future information has a more significant impact on current decisions when the events are imminent. However, computational time exponentially increases as we increase the rolling horizon factor as in Fig. 3c. In practice, operators can decide a proper look-ahead time by trading off between desirable service rate and allowable computation time. The results of the scalability test with NYC scenario highlight the scalability of our framework. The number of requests per day is significantly larger than the CARTA use case. While the GLS could not get any feasible solution within the given time limit, our framework achieves the solution within 1 second. In the rolling horizon framework, the increases in look ahead time are restricted, because the computation time explodes as the rolling horizon factor increases. We could not get the result of RH3 within the time limit as in Fig. 3d, thus the reasonable rolling horizon factor in this setting would be 2. Likewise, in practice, operators can decide a proper look-ahead time by considering how much time they can spend for computation. The service rate achieved is shown in Fig. 3b. These results are presented in a paper that is currently under review: Youngseo Kim et al. “Offline Paratransit Vehicle Scheduling via Rolling Horizon Optimization”. In: 25 International Confer- ence on Intelligent Transportation Systems, ITSC 2022 (under review). 2022. 2.1.3 Online Scheduling Algorithm While the day-ahead algorithms discussed in the previous sections provide the schedule of trips, transit agencies also have to respond to trip requests that arrive in real-time, which entails solving Page 6 Chattanooga Area Regional Transportation Authority | August 2025 Figure 4: An overview of MC-VRP. A decision epoch corresponds with a new trip request Rt . We generate request- vehicle (RV) and vehicle-vehicle (VV) graphs by combining a heuristic based pickup and delivery problem with time-windows (PDPTW) solver with metrics to quickly estimate the utility of route plans. The PDPTW is NP-hard [8, 9]; as a result, we use a heuristic subroutine to solve it. We then select promising actions from the graphs by sampling independent sets of high weights to be evaluated by an online approach based on MCTS. hard combinatorial and sequential decision-making problems under uncertainty. To avoid deci- sions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a my- opic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic con- ditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we developed a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction as it performs planning online. Our approach is called MC-VRP (Monte Carlo tree search based solution for vehicle routing problem). We model the DVRP as a route-based Markov decision process (MDP) [10]. Given an arbitrary state of the MDP, we use generative models over customer requests and travel time to simulate the environment under consideration, which in turn enables us to use Monte Carlo tree search [11] to find promising actions for the state. Our approach does not require offline training, the only requirement is a generative model that can be sampled at run-time. To tackle the intractably large action space, we leverage the structure of the problem to find promising actions. Specifically, given a set of routes and a new request, we create a weighted graph based on a budget-based heuristic whose edges represent: (a) which vehicles can serve the new request, and (b) which vehicles can swap unpicked requests from their routes to maximize utility. Then, we sample independent sets from the graph that correspond to feasible actions for the given state of the MDP. We provide an overview of MC-VRP in Fig. 4. Our approach consists of the following three broad components: 1) For a given state of the MDP, we sample feasible and promising actions by exploiting the structure of the problem. To compute feasibility, we use a heuristic-based solution approach to the PDPTW. To compute the potential utility of a feasible action, we introduce two heuristics, one based on passenger travel times and another based on budget (or slack) in route plans. 2) We compute weighted graphs based on the feasible actions and their potential utilities. Specifically, we create vehicle-vehicle (VV) and request-vehicle (RV) graphs (we describe the Page 7 Chattanooga Area Regional Transportation Authority | August 2025 DRLSA MA-RTV greedy-PTT greedy-budget MC-VRP (PTT) MC-VRP (budget) 100 % 80 % 60 % 40 % 20 % 0% 3 Vehicles 4 Vehicles 5 Vehicles Number of Vehicles Figure 5: Service rate, defined as percentage of trips served, per day on 15 day test set for 3, 4 and 5 vehicles. 5 vehicles was enough to service all request on most days for MC-VRP (budget), MC-VRP (PTT) and MA-RTV. MC- VRP (budget) had the highest median service rate for 3 and 4 vehicles. MC-VRP (PTT) MC-VRP (budget) 80 MC-VRP (budget) DRLSA MA-RTV greedy MC-VRP 6% Compute Time per Request (s) 0% 4% % Change in Service Rate % Change in Service Rate 60 2% −10 % 40 0% −20 % −2 % 20 −30 % −4 % 0 −6 % −40 % 3 Vehicles 4 Vehicles 5 Vehicles 3 Vehicles 4 Vehicles 5 Vehicles 3 Vehicles 4 Vehicles 5 Vehicles Number of Vehicles Number of Vehicles Number of Vehicles (a) (b) (c) Figure 6: (a) Computation time per request in seconds for each day in the test set for 3, 4 and 5 vehicles. Median computation time per request for MC-VRP (budget) is 38 seconds, 49 seconds and 40 seconds for 3, 4 and 5 vehicles respectively. DRLSA, MA-RTV and greedy all had median computation times less than 3 seconds per request. (b) Runtime analysis: Percent change in service rate for MC-VRP (budget) with a cutoff of 30 seconds per request compared to no cutoff. For three vehicles there was a median of 1.2 percent decrease in service rate on test set while the computation cutoff had negligible affect for four and five vehicles. (c) Robustness to roadway congestion: Percent change in service rate for DRLSA, MA-RTV, greedy-budget and MC-VRP (budget) on test set using congested travel time matrix compared to free-flow speed matrix. MC-VRP (budget) had less of a decrease in service rate for 3, 4 and 5 vehicle fleets compared to the baselines. graphs below). Then, we generate promising actions by sampling independent sets from the graphs (based on the weights of the sets). 3) The sampled actions are then used by our online non-myopic planner based on Monte Carlo tree search. To build the search tree into the future, we sample future requests from a data-driven generative model. Finally, to lower computation time, we utilize pre-computed samples of requests and root parallelization [12] to efficiently explore the search space and recommend an action for the given state. We evaluate the performance of MC-VRP against two greedy approaches: greedy-PTT, greedy- budget. We use six months of paratransit trip requests between January 1, 2021 and July 1, 2021 from CARTA. Our dataset consists of a total of 25,843 trip requests. We randomly selected 15 days from the dataset for the evaluation (test) set. The remaining 114 days were use to compute 100 synthetic days worth of trip requests (i.e., chains) for the generative model required by our approach as it looks into the future during planning. Greedy assignment consists of first generating feasible actions and then selecting the action with the highest utility. For comparison, we include greedy assignment using both the passenger travel time (PTT) and the utility that maximizes the budget (or slack) in route plans. We also compare Page 8 Chattanooga Area Regional Transportation Authority | August 2025 our approach to two myopic online approaches (greedy and MA-RTV) and one non-myopic hybrid approach called Deep reinforcement learning-based vehicle routing [13] (DRLSA). The MA-RTV stands for Myopic and Anytime trip-vehicle assignment-based on RTV graphs [4]. It is the baseline standard developed by Co-PI Samarnayake and is known to be the state of the art algorithm that batches requests together and then maximizes the myopic utility for the specific batch of requests. For each batch, the algorithm creates an RTV graph by checking shareability between requests as well as requests and vehicles. Since the best passengers-vehicle pair is found in each batch, the approach works well in practice despite being myopic (our experiments confirm this). For all baselines, we use the same number of vehicles (we present results by varying the number of vehicles) and vehicle capacity as MC-VRP. Our primary objective is to maximize the number of requests serviced each day. The service rate per day for the 15 days in the evaluation (test) set is provided in Fig. 5 with fleet sizes of 3, 4, and 5 vehicles. We first present results in a setting where MC-VRP (budget) and MC-VRP (PTT) are allowed to run for 1000 iterations without early termination. First, we note that 5 vehicles is enough to service all of the requests on most days as MC-VRP (budget), MC-VRP (PTT), and MA-RTV all have a median service rate of 100%. We observe that MC-VRP (budget) outperforms all baselines for fleet sizes of 3 and 4 with with a median service rate of 87.0% and 97.6% respectively. MC- VRP (PTT) had a service rate of 84.7% and MA-RTV had a service rate of 81.7% for 3 vehicles. MA-RTV outperformed MC-VRP (PTT) in the case of 4 vehicles with a median service rate of 96.2% compared to 95.8%. We also observe that the budget-based heuristic works better than the travel time-based heuristic for both Monte Carlo tree search as well as greedy assignment. Indeed, MC-VRP (budget) results in a higher service rate than MC-VRP (PTT) and greedy-budget outperforms greedy-PTT for all fleet sizes. This indicates that the budget utility, which aims to maximize time for which a vehicle has no passengers on-board, can be used to quickly compute promising actions to explore. It is important to note that while we focus on paratransit services, the budget-based heuristic can be applied for other DVRPs with capacity and time window constraints. We also observe that DRLSA had the lowest service rate across all fleet sizes. An influencing factor, is that time windows are soft constraints in DRSLA which is not particularly suited to paratransit settings. The computation time per request for MC-VRP and the baselines is shown in Fig. 6a. MC-VRP (budget) takes slightly longer than MC-VRP (PTT) to compute a decision, with a median compu- tation time of 38 seconds, 49 seconds, and 40 seconds as compared to 36 seconds, 44 seconds, and 37 seconds for 3, 4, and 5 vehicles respectively. DRLSA, MA-RTV, and greedy all had median computation times less than 3 seconds. In this context, the fact that MC-VRP is both non-myopic and fully online is reflected in the higher runtimes; while the observed runtimes are acceptable in our setting, i.e., paratransit services, the application of online and non-myopic methods remains an open question in general VRP settings. Note that if the MCTS evaluation of our approach is not used (i.e., the early stopping time approaches 0), our approach simplifies to the greedy baseline, which takes less than a second on average. This observation means that the majority of computa- tion time in our approach is spent on MCTS. Being an anytime algorithm, the MCTS evaluation can be run in the background between calls. In such a setting, the algorithm is stopped early (in our case, before the default number of iterations is reached), but outputs a feasible solution. In our dataset, 99% of requests arrive more than 30 seconds after the previous request and the median time between requests was approximately 5 minutes. Therefore, we evaluate the performance of MC-VRP with a 30 second cut-off time in Page 9 Chattanooga Area Regional Transportation Authority | August 2025 Fig. 6b. We observe only a negligible decrease in service rates; the median service rate decreases by 1.2% for 3 vehicles and 0% for 4 and 5 vehicles. To evaluate the robustness of the proposed approach with respect to changing environmental conditions, we change the travel time distribution in the city. We evaluated DRLSA, MA-RTV, greedy-budget and MC-VRP (budget) on the 15 day evaluation set using the congested travel time network and compared the resulting service rates to those generated without congestion. We ob- serve that MC-VRP (budget) incurs less of a decrease in service rate compared to DRLSA, MA- RTV and greedy-budget across all sizes of vehicle fleets as shown in Fig. 6c. As expected, DRLSA had the greatest decreases in service rate due to its reliance on a value function that was trained offline using the free-flow travel time matrix. While hybrid approaches such as DRLSA have ac- cess to the real-time travel conditions, it is difficult to re-train offline components, resulting in a higher degradation in performance. Both MA-RTV and greedy-budget outperform DRLSA when evaluated for robustness. This result is expected since MA-RTV and greedy-budget are both online approaches, it is able to adapt to the updated matrix. We also observe that MC-VRP (budget) per- forms better MA-RTV and greedy-budget, showing that our non-myopic online solution improved upon the myopic online approaches as well. This paper is published in the proceedings of the ICCPS 2022 conference: Michael Wilbur et al. “An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Re- quests for Paratransit Services”. In: 13th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS). May 2022. 2.2 Simulation Environment We have completed the initial work on a transportation and power grid simulation during Phase I. The simulator can help evaluate the impact of different transit trips and subsequent vehicle choices and charging schedules. The core component of this simulator is he transit-gym which is described next. This is then integrated with the GridLab-D based power grid simulator. 2.2.1 Transit-Gym T RANSIT-G YM [14] is a SUMO-based general-purpose transit simulator carefully calibrated for the city of Chattanooga. This has been achieved by careful calibration of the underlying model. Note that for the simulator to remain viable, it is crucial to keep the physical transit network of the city and the simulated transit network in sync. The geometric design of roads evolves as new roads, and additional lanes are built on existing transportation infrastructure. This adds a layer of complexity to developing precise simulation environments. It is common for developers and researchers to procure transportation data, and network files from existing platforms, such as OpenStreetMap (OSM) [15]. The data available on these platforms is traditionally crowdsourced, and in many cases, it is not up to date with the actual transportation infrastructure. Therefore, we have developed and integrated specialized procedures to perform a stochastic check against the designed network and real traffic data collected from the city and then fix any discrepancies in the network. This process ensures that road geometries and map files are continuously updated, providing an accurate environment for testing and validation. Fig. 7 presents the framework of T RANSIT-G YM. SUMO [16] is used to conduct microscopic traffic simulations, wherein vehicles, public transport, and persons are modeled explicitly. A sce- nario description language that comes with the simulator provides the ability to customize the transit simulation configurations. The simulation gym is equipped with microscopic energy pre- diction models developed by the team [17, 18, 19] previously. They are used to estimate the energy Page 10 Chattanooga Area Regional Transportation Authority | August 2025 Figure 7: Framework of simulation platform. Figure 8: Passenger occupancy of each bus along the bus stops by trips across 24 hours. consumption for each vehicle trip as simulated through the SUMO network. Overall, the simulation engine is capable of providing road-based traffic measurement output, including the macroscopic values such as the mean speed, the mean density, the mean occupancy of road edge during specified time intervals. For each bus stop, we output the simulated schedule: time of arrival and departure, stopping place, and the number of persons that boarded and got off from the bus. The passenger itineraries are configurable and are simulated based on input demand models provided by the local transportation planning office. For each transit vehicle, we also provide current speed and acceleration. Finally, we also provide the estimated energy consumption, calculated after the simulation using the energy estimation models. Examples of the output analysis visualizations are as follows. Fig. 8 shows the passenger oc- cupancy of each bus along with its stops by trips for a whole day. Fig. 9a shows the maximum passenger occupancy of each bus along with the bus stops by routes. The bar within each box represents the median of the maximum passenger occupancy of different buses on each route and Page 11 Chattanooga Area Regional Transportation Authority | August 2025 (a) (b) Figure 9: (a) Maximum passenger occupancy of each bus along the bus stops by routes across 24 hours. (b) Distribu- tions of bus occupancy between specific hours on route 4. (a) (b) Figure 10: (a) Energy consumption rate for buses in half a day. (b) Energy consumption rates (miles per gallon) for buses in different trip assignment scenarios. Electric vehicles go longer per equivalent gallon of diesel fuel. the two sides of box correspond to the first and the third quartile of the data for each route. To investigate the occupancy status during different times in a day, the distributions of bus occupancy between three specific hours (8am, 12pm, and 17pm, representing morning, midday, and afternoon) on route 4 are shown in Fig. 9b. Fig. 10a shows the estimated consumption rates for buses on dif- ferent routes. Fig. 10b presents the comparison of the energy consumption rate of buses among different trip assignment scenarios. It shows that using all-electric vehicles is the best strategy in terms of energy consumption. This work appeared in the following publication: R. Sun et al. “TRANSIT-GYM: A Simulation and Evaluation Engine for Analysis of Bus Transit Systems”. In: 2021 IEEE International Con- ference on Smart Computing (SMARTCOMP). Los Alamitos, CA, USA: IEEE Computer Society, Aug. 2021, pp. 69–76. DOI: 10.1109/SMARTCOMP52413.2021.00030. Page 12 Chattanooga Area Regional Transportation Authority | August 2025 Figure 11: Sequence diagram. 150 0.77 0.76 Number of vehicles 100 0.75 0.74 0.73 GIS 50 0.72 0.71 0.7 0 0.00 1.40 2.80 4.20 5.60 7.00 8.40 9.80 11.20 12.60 14.00 15.40 16.80 18.20 19.60 21.00 22.40 23.80 25.20 26.60 28.00 29.40 30.80 32.20 33.60 35.00 0.69 0 5 10 15 20 25 Average speed (mi/hr) Time (hrs) (a) (b) (c) Figure 12: Results from the transit simulation for a day in January in Chattanooga. (a) SoC change for one bus with sequential trips. (b) Average speed of the electric buses across all trips for 24 hours (c) Grid Impact Score across 24 hours. 2.2.2 E-Transit Bench: Extending the Transit-Gym with Electric Grid Simulation The integrated simulation is designed to make the individual underlying components work in unison, namely, the power grid simulation (using GridLAB-D) and the vehicle transit simulation (using SUMO). The information exchange that goes on between these simulators needs to be care- fully handled as it is time-sensitive. This information exchange is performed with the use of the Hierarchical Engine for Large-scale Infrastructure Co-Simulation (HELICS) [20], an open-source co-simulation framework. It is the Co-simulator coordinator, responsible for time synchronization, and also acts as an agent to interact with the grid models in GridLAB-D and the Python feder- ate. There are dedicated computations modules programmed in Python to perform computations that interact with the Python federate, that utilize the various parameters or information from the interface. All of these components work in tandem and run the entire simulation platform syn- chronously. The work is described in Fig. 11. GridLAB-D subscribes to the state of charge (SoC) values from Page 13 Chattanooga Area Regional Transportation Authority | August 2025 288 80 200 40 287 Phase A Phase B Phase C 70 Reactive Losses (kVAr) 30 Real Losses (kW) Node Voltage (V) 286 60 150 Cost ($) 285 50 20 284 40 100 10 283 30 282 20 50 0 281 10 Real Loss Reactive Losses CH#1 CH#2 CH#3 CH#4 CH#5 280 0 0 Charging instances 0 5 10 15 20 25 0 5 10 15 20 25 Time (hrs) Time (hrs) Usage (non-peak) Usage (peak) (a) (b) (c) Figure 13: Results from the transit simulation for a day in January in Chattanooga. (a) Node Voltage at the charger location. (b) Total Feeder Loss. (c) Usage charge breakdown in 5 charging instances. the transit simulator when the EV arrives at the charging station to get charged. This translates to the grid as an additional load that follows a charging profile, predefined for the EV battery and the charger at the charging station. The charger profile is also season-dependent (it uses the city weather profile) to ensure the charging time and the impact on the grid behavior are realistic. The simulation goes on for a specified time duration. During this time, it can monitor the move- ment of all the individual vehicles (electric buses) as well as the state of charge (SoC) of the vehicles. The important checks that go on in the simulation are: (i) checking the SoC of electric buses and how much it has depleted, and (ii) checking for any changes in the grid load. The SOC of the bus drops as it moves around in its set route. When the SoC is below a critical level, the bus needs to charge soon to replenish its battery, or else, it may run out of charge and stop in its tracks. We want to avoid that scenario and direct the bus to a charger as soon as possible. As soon as the bus moves on to the charging location and charging begins, its movements are stopped and the power consumption is added to the grid, in the grid simulation. The grid load is then measured throughout the period of charging the bus and can be done for multiple charging buses at a time. This is important as it provides an understanding of how much power is drawn from the grids at the charging stations and more importantly, how much the grid is affected by this usage and its effects on the surrounding neighborhoods. Once the bus reaches the desired charge level, it is disconnected from the grid. The power draw at that charger is reduced to zero. The transit sim then resumes the movement of the bus along its planned route for the rest of the duration. This cycle can go on whenever the buses are low on a battery charge or are pre-planned to charge. Data about all the required parameters (like SoC, bus movement, weather, trips completed, and so on) can be collected and stored during this period. The simulation ends when it has run for the desired duration. The Python federate gets the message from both the grid simulator and the transit simulator that their execution has stopped. Subsequently, the federate performs any necessary post-processing on the collected data (like grid analysis, and bus efficiency). After these are performed, the program terminates, marking the end of the integrated simulation cycle. We now describe the analysis of a day from January 11, 2022 as simulated on the E-transit bench. The SoCs for the electric vehicles is then generated (Fig. 12a) and made available to the grid simulator for analysis of the GIS. The average speed of the electric buses is shown in Fig. 12b. During the simulation, we constantly check the SOC of the vehicles and then estimate when the vehicle is ready for charging (once it finishes its trip in the transit simulation). Figs. 13a and 13b demonstrate the impact of charging during the peak and off-peak load times. The voltage dips during charging due to an increase in the load and since the charger is located at the end of the feeder the loss increase in the system during the charging times can be observed clearly. Page 14 Chattanooga Area Regional Transportation Authority | August 2025 A grid impact score (GIS) is determined for the given scenario and location of the charger. This GIS depends on various parameters like the location of the charger, seasonal impact on the charging profile. The GIS, shown in Fig. 12c, is relatively higher during charging (compared to the instant just before charging) as there is a significant drop in voltage and an increase in the system losses. The GIS is a normalized value and if it is greater than 1, it indicates a violation of the grid operating limits. The GIS will be used in the future work on the project to coordinate the charging events to minimize the impact to the grid. The usage charge breakdown is shown in Fig. 13c. 2.3 Improving the Occupancy Estimation Algorithm Accurately estimating the maximum occupancy of each scheduled transit-vehicle trip is crucial to understanding the demand for transit in an area. This data is useful for generative models that we use in non-myopic optimization as well as real-time adjustments to headways and transit schedule—decisions that impact the overall efficiency of the transit operations. Our team has worked on developing two approaches for solving this problem. We describe them below. 2.3.1 Using Neural Network Architectures The first approach is a statistical procedure where we set up a deep neural network architecture to learn the underlying distribution as a function of several covariates, including the weather and the region of operation. These neural network models form the core of the generative models discussed in our MC-VRP work (Section 2.1.3). Further, we designed a neural-architecture and feature search algorithm that fine-tunes the architecture’s hyper-parameters and predictor variables. [21]. The hyper-parameter and feature-set optimization is based on a randomized local search, which minimizes both prediction error and the complexity of the model. Minimizing the complexity of the model is crucial since it reduces computational cost and time during both training and inference. Best Architecture NAS Score for 6 4 RMSE 2 4 min 0 300 600 900 4-In 4-Out 1-In 1-Out 9-In 9-Out 2-In 2-Out 7-In 7-Out Search Iteration Tasks (a) (b) Figure 14: (a) Neural architecture search with score based on model complexity and the average RMSE over all tasks. (b) Comparison between architectures that were found by generic (yellow ) and task-specific searches (blue ) based on NAS score for each specific task. Fig. 14a shows the first 900 scores of the accepted architectures of a generic search. After trying around 600 different architectures, the search reaches the best architecture based on average RMSEs on the validation sets and model complexity. Fig. 14b shows the score after training for a specific transit route with both generic and route-specific architectures. There is a clear gap between the two losses, which indicates that the architecture and feature set found by the route- specific search outperforms the ones found when optimizing for all route. So, prediction error and model complexity can be reduced by optimizing the hyper-parameters for a specific route, which is made possible by our novel search algorithm. Page 15 Chattanooga Area Regional Transportation Authority | August 2025 Figure 15: Sample image with passengers detected using a computer-vision model trained on our dataset. Faces are blurred in this report to protect the passengers’ privacy. Labels show the confidence of the computer-vision model (from 0% to 100%) about the presence of a passenger; we reduce false-positive errors by filtering all detections below 80% confidence. This work appeared in the following publication: Afiya Ayman et al. “Neural Architecture and Feature Search for Predicting the Ridership of Public Transportation Routes”. In: 8th IEEE Inter- national Conference on Smart Computing (SMARTCOMP). June 2022. 2.3.2 Using Computer Vision The second approach is to improve vehicle-load information accuracy and reliability by lever- aging data streams from existing on-board video cameras on transit vehicles. Specifically, the goal is to study the feasibility of applying state-of-the-art machine-learning based computer-vision models to videos recorded on transit vehicles in order to estimate ridership, and to develop proof- of-concept implementations. Table 4: Results with a model based on Faster R-CNN [22], a state-of-the-art object-detection architecture. 10-fold cross validation Precision Recall Mean absolute percentage error Average over folds 97% 93% 8% In Phase I of the project, we accomplished the following key results in the area of computer- vision based ridership estimation. We collected two diverse datasets (one low-resolution video dataset and one high-resolution image dataset, covering both daytime and nighttime as well as crowded and non-crowded settings) from transit vehicles operated by the public transit agency of Chattanooga, TN. We developed formal guidelines for annotating videos and images with ground- truth labels for on-board passengers, considering the unique requirements and challenges of our application. We manually annotated the video dataset by attaching a ground-truth label to every passenger on every frame, which enables using the video datasets to train and evaluate computer- vision models. We trained multiple state-of-the-art computer-vision models to detect passengers using our own video dataset as well as public computer-vision datasets. We created an ensemble- averaging based committee machine, which combines the outputs of these computer-vision models Page 16 Chattanooga Area Regional Transportation Authority | August 2025 Figure 16: Integrated System Architecture of the designed system to provide more accurate predictions than the individual models. Finally, we rigorously evaluated the computer-vision models, considering the metrics of mean absolute percentage error, recall, and precision. Fig. 15 shows sample images from the training and test sets. Table 4 shows the results from a dataset of 600 images. Our mean absolute percentage error achieved on this set was 8%. 2.4 Application Programming Interfaces One of the last tasks of Phase I was the design of a paratransit software application that can be de- ployed at CARTA. The architecture we chose is a REST based micro-services architecture. Fig. 16 describes the complete system architecture that the team has developed for Phase I. It includes online data streaming and storage capabilities, including the integration of the vehicle telemetry storage system that the team developed in the prior DOE project “High-Dimensional Data-Driven Energy Optimization for Multi-Modal Transit Agencies.” The architecture also includes the para- transit application that is described next. This application integrates the scheduling algorithms described earlier in the report. 2.4.1 Paratransit Web Application The paratransit application provides web-based paratransit operations services to transit agen- cies. The application aims to improve the efficiency and consistency of reservation/bookings pro- cess for rides, the ability to schedule and modify the ordering and assignment of trips to the opti- mal vehicles and trip routes, and the ability to have insights into metrics and tools of historical and planned vehicle runs. Further, the application makes use of automatically optimizing all scheduled routes for a day given a fleet of vehicles, but also gives management the ability to make ad-hoc changes to a vehicles manifest, remove or add vehicles to the fleet, quickly modify reservations, and view real-time shuttle locations with status of their planned trips. The application’s services are built upon a strong data management platform. Application ser- vices utilize data including rider information and historical trips, active fleet vehicles and their model’s ambulatory and wheelchair capacities, versioned daily Timetables, which allow easily edited client trip information, reordering and reassignment of trips throughout the vehicle fleet, and editable vehicle manifests containing the details of each trip that will be serviced by a particu- lar vehicle on a given day. The application was developed utilizing the Dash Plotly user interface Page 17 Chattanooga Area Regional Transportation Authority | August 2025 Figure 17: Applications Hub of the Paratransit Web Application Developed by the Team in Phase I and Flask micro web framework, both in Python 3.8. Dash is written on top of Plotly.js and Re- act.js. The backend is developed using a Mongo database. These services, described in detail below, were designed to simplify and automate the operations workflow, reduce data entry errors, and provide more insight into trends and potential cost savings initiatives. The services also allow for the ability to make ad-hoc changes, review summary metrics for vehicles, vehicle routes, and daily timetables. • Bookings Service: The bookings service allows the creation and saving of rider bookings to a centralized database with interactive mapping of addresses. This service allows quick searching of a database of existing riders with insight into their information and past trips. These rider’s information can be updated quickly, or new riders can also be added. The book- ings process also utilizes interactive mapping of pickup and dropoff locations so operators can ensure their address meets expectations. A routing algorithm is utilized to provide initial draft route distances and durations. Next, a recommendation engine provides an interactive scoring mechanism that shows the operator timeframes that may result in improved fuel effi- ciency compared to the initial requested pickup time. Finally, a summarize view is provided with all client and trip details along with interactive maps before saving trip to database for scheduling. • TimeTable Service: The timetables service allows the creation, review, and modification of versioned Timetables. A timetable consists of a set of vehicle runs, which in turn consist of a set of requested trips. Each calendar day maintains only one ‘Current’ timetable used for dispatch. However, this application keeps a versioned history of timetables identified by a version number and timestamp showing the last time it was saved. Operators can work off the ‘current’ version or choose an older version with which to start their review or modification. Operators are allowed to reorder trips within a vehicle, reassign trips from one vehicle to Page 18 Chattanooga Area Regional Transportation Authority | August 2025 another, cancel/delete trips, modify existing trips, or place trips as temporarily unassigned. These unassigned trips can later be assigned to an existing vehicle, or a new vehicle run can be created. Batch operations such as the un-assignment of all trips from a vehicle (e.g., in the case of a vehicle break-down) can be done. • Manager Review Service: The manager review service allows a higher-level review of timeta- bles. Summary metrics of the current (or past) timetables are provide, and can be produced at the vehicle level, as well. Metrics include total trips assigned to the timetable or vehicle run, total distinct riders, first pickup time of the day, and last dropoff time of the day. Man- agers can also review changes. For instance, if a client or trip was changed after the ‘current’ timetable was created, the timetable and associated trip(s) are flagged for review. Changes could include a change in pickup/dropoff address or time, or a change in notes specific to the client’s requirements, or the fact that a rider might utilize a wheelchair for the first time. • Logistics Service: This service provides the ability to make high-level changes to opera- tions such as the adding of new vehicles/vehicle manifests or the deletion/removal of vehi- cles/vehicle manifests (e.g., if a vehicle was temporarily out of service). • Real-time Service [under construction]: The real-time service allows a review of real-time locations of paratransit shuttles. The map of the shuttles not only shows locations but show which trips have been completed but which trips are in-process or upcoming. It also helps enter the real-time same day bookings into the system and helps the driver’s know their schedule and plans. Figure 18: AI Optimization Engine Framework for Data Integration with Railigent. Data Collection Siemens Technology has primarily focused on exploring the Railigent platform services and in- terfaces and mapping them to the requirements of the project. The Railigent platform consists of multiple data ingestion techniques including manual and automatic S3 data ingest, ETL rela- tional import tool and real-time data processing. It also supports graph databases such as Amazon Neptune and Neo4j, a key requirement of the project for representing the origin-destination (OD) Page 19 Chattanooga Area Regional Transportation Authority | August 2025 matrices and dependency graphs. Further, the platform provides APIs and blueprint templates to speed up the development work. Transit Operations Insights (TOI) of Railigent is a power- ful visualization tool to render the insights for the operation of vehicle fleets. We have gauged the cloud-based Railigent platform and its TOI application for the specific needs of agencies with mixed-vehicle vehicles. Specifically, we identified the interfaces that we are going to utilize and build upon to import CARTA datasets to Railigent platform and set up the infrastructure to execute JSON schema transformation. The next steps will involve defining and implementing the interfaces and schema transformation APIs to import the datasets. Figure 18 shows the entire framework with the integration with the Railigent platform. The complete API documentation is included in the appendix (Appendix A). 2.5 Community Engagement Figure 19: Results of the Initial Community Engagement and Outreach. The community focus group questions have been formulated and initial engagement with com- munity organizations and leading organizations has been accomplished. Continued COVID transmission rates during the winter months precluded in person survey col- lection. CARTA has recruited a community outreach coordinator who began work on July 27, 2022, and has begun preliminary organizational outreach to support direct public survey engage- ment. The engagement team has posted QR codes on 10+ bus shelters located along popular stops. In addition, CARTA’s two most frequented stops along Route 4 have signage about our new service: CARTA GO. We have had team members out at bus stops to collect survey responses. CARTA’s social media accounts (Twitter, Facebook, and LinkedIn) have been used to post about the survey and has been highlighted in several community partners’ newsletters. The Chattanooga Housing Authority (CHA) conducted four outreach events at their housing sites (Emma Wheeler, College Hill, East Lake Courts, and Cromwell) to gather survey responses. They were able to gather over 130 responses. Page 20 Chattanooga Area Regional Transportation Authority | August 2025 Paratransit Vehicle Runs for week of 2021-04-12 variable base_runs google_or_tools_runs mcvrp_runs Paratransit Vehicle Requests for week of 2021-04-12 booking_algo_2_hour_windows booking_algo_4_hour_windows 30 250 25 200 number of vehicle runs 20 no_of_requests 150 15 100 10 50 5 0 Monday Tuesday Wednesday Thursday Friday Saturday Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sunday day_of_week day_of_week (a) (b) Figure 20: We compared our on-demand paratransit scheduling algorithms for vehicle routing problem to real-world paratransit data from CARTA for the week of Monday April 12, 2021. (a) The requests from the week per day. (b) comparative performance of our algorithms against the baseline number of vehicles used at Carta. We also compare against the vanilla Google OR tools, a state of the art VRP solver. The survey has been posted in the Chattanoogan which is the local online newspaper along with their Facebook. The Chattanooga Public Library has posted the survey on their social media, newsletter, and at their local computers. In addition, we have been featured in green—spaces, Outdoor Chattanooga, Therapeutic Recreation Center, ChattaTransit, and NoogaToday. From August 2022 to November 2022, CARTA, worked with other local agencies to dissem- inate surveys to the local Housing Authority residents, CARTA bus riders, CARTA’s email list, and targeted organizations. The surveys were available both online, using survey monkey, and in paper format. Participant recruitment was conducted via word of mouth, fliers at bus shelters, and having CARTA workers at some of the more populous bus stops. Other local agencies assisting in promoting survey participation include local media outlets such as The Chattanoogan and Nooga Today, the Chattanooga Library, the Chattanooga Housing Authority (from now referred to as CHA), Chattanooga’s Therapeutic Recreation Center, Green—Spaces, and Outdoor Chattanooga. This effort represents a convenience sample, as the sample were not randomly selected and often were selected due to their relationship with one of our many community partners. A total of 673 surveys were collected. The largest number of survey participants were from Chattanooga Housing Authority (CHA) (34%) and targeted organizations listed above (43%). The remaining respondents came from CARTA bus riders (10%) and the CARTA email list (12%). The majority of the respondents in the study used the bus (47%) as their primary form of transportation, while roughly 38% of respondents indicated they used other modes of transportation to get around (ie., personal vehicle, bike, ride-sharing, or bike-sharing. The bus rider sample were from our efforts with the Chattanooga Housing Authority, CARTA bus riders, the CARTA email list, and target organizations. Initial survey of our CARTA GO microtransit application began in May, 2023, to create baseline data for future pilot operations. This included personal on-board surveys with passengers and drivers, and development of a directed survey plan in the following quarter. The results of the initial focus groups and surveys are shown in Fig. 19. Page 21 Chattanooga Area Regional Transportation Authority | August 2025 3 Performance Analysis and Go/No Go Milestone To analyze the performance of our algorithms in saving energy while maintaining 100 percent service rate, we compared the algorithms discussed in Section 2.1 for the week of Monday April 12, 2021. Recall that the MC-VRP [5] (Section 2.1.3) is a fully online, non-myopic approach to solve the dynamic vehicle routing problem (DVRP) for paratransit services. For this comparison we used the budget-based heuristic which aims to maximize the time a vehicle has no passengers on board to provide slack for future requests. The heuristic is used to prune the search space and select a finite number of promising actions which are then evaluated with Monte Carlo tree search. The approach is non-myopic in that it considers future states of the system at each time epoch without relying on models trained offline. We used the vehicle capacity of 9 passengers and required that all passengers will picked up within 15 minutes of their requested pickup time. Additionally, when a customer requests a trip we provide an estimated dropoff time which is the sum of the requested pickup time and the minimum travel time to the dropoff location. The late time window is 15 minutes after the estimated dropoff time which is again, in accordance with settings used by CARTA. Our results (Fig. 20) show that our MC-VRP algorithm used 42 vehicle trips. The actual CARTA real-world assignment used 96 vehicle trips. The Google OR Tools used 141 vehicle trips. The online bookings algorithm with a 4 hour tight window used 71 vehicle runs. The online bookings algorithm with a 2 hour tight window used 64 vehicle runs. This improvement is greater than 5% that was indicated in our milestone. Recall that in earlier work [1], we had showed that our approach of fixed line scheduling where we choose the best vehicle class for each trip can save $399 of Energy Cost daily, which is approx- imately 5% of daily cost. In the future work, we are working on integrated scheduling, which we believe can lead to even more energy savings. 4 Progress Report (Phase III) Table 5: Milestones and Status Milestone Type Description Status Field Test Technical Field tests with the integrated system are com- Pilot field test completed. plete. Community Engagement Technical Surveys and focus groups complete. Summary Survey plan complete. Fi- results and methodology sent to the DOE Project nal engagement completed Officer. in December 2024. Field Test Evaluation Report Technical Transit accessibility and trip performance im- Final report in preparation. provement evaluation. Mobility Energy Produc- tivity Evaluation for the Recipient’s service area complete. Evaluation of the Recipient’s park- ing system usage relative to transit trips and sub- scription package utilization complete. Project Completion Report Technical Report on the final analy- AI Engine field testing sis/findings/recommendations from sur- complete with 21% im- vey/focus groups. Ability of the AI Engine provement in service per- to successfully schedule the trips during the formance. testing period. Improvement of at least 10% in service coverage and energy efficiency com- pared to current state of the operation before the project in Chattanooga. Page 22 Chattanooga Area Regional Transportation Authority | August 2025 Our tasks and the current progress in Phase III are summarized below. 1. Design experiments to validate the feasibility of our approach on an actual field test. 2. Develop the field tests with the fully integrated system. 3. Deploy a complete end-to-end pilot within CARTA’s real world workflow, that would allow us to evaluate the performance improvement provided by our AI Optimization Engine. The tasks and their status are shown in Table 5. 4.1 Field Test Preparation For the final phase of the project, we aimed at testing the platform in a real-world setting. This deployment was essential not only for validating the software’s capabilities but also for optimizing transit operations within the Chattanooga community through effective data-driven decisions. In collaboration with the Chattanooga Area Regional Transportation Authority (CARTA), we suc- cessfully launched the platform into their existing infrastructure as part of a pilot, focusing on enhancing paratransit and microtransit services. 4.1.1 Algorithm Evaluation and Pre-Deployment 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 be- tween 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 geo-coordinate (longitude, lat- itude) 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’s 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. 4.1.2 Offline Solver Evaluation Prior to extensive deployment, the algorithmic approaches were rigorously validated both in simulation using real-world paratransit data from CARTA and two small pilots [23]. Experi- ments demonstrated that the proposed offline solver significantly improved efficiency compared to CARTA’s existing black-box software. The solver reduced Vehicle Miles Traveled (VMT) per Passenger Miles Traveled (VMT/PMT) by 21.3%, achieved an 85% shared rate (meaning more than one passenger on board for a given time), and eliminated time window violations present in CARTA’s original manifest. Similarly, the online solver showed improved performance even when accommodating real-time requests, particularly in scenarios resembling CARTA’s typical operating conditions (e.g., a 90-10 split between day-ahead and real-time requests). This validation provided a strong foundation for subsequent pilot deployments of similar on-demand transit technologies. Page 23 Chattanooga Area Regional Transportation Authority | August 2025 Figure 21: Solver Metrics recorded for paratransit data on compared with PTA’s real schedule. VMT: Vehicle Miles Travelled, VDM: Vehicle Detour Miles, VMT/PMT: Vehicle Miles Travelled to Passenger Miles Travelled, Shared Rate: percentage of trip requests that shared their trip with another passenger, Violations: number of time window constraint violations. We observe that the proposed offline solver serves all passengers without any violations, with significantly fewer detour miles and a significantly higher shared rate, thereby reducing the total number of miles the vehicles have to drive. 4.1.3 Online Solver Evaluation 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 ex- ample, 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 Fig. 21. 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. 4.1.4 Improvement to the Operational Backbone The pilot’s operational backbone is an overall improvement of the initial paratransit web appli- cation that was created during the initial phases of the project. The new application is built upon three custom-developed and interconnected applications [24] we called “SmartTransit.AI”: • Dispatcher App ( Fig. 22): A cloud-hosted web application that enabled CARTA personnel to book rides for customers, track real-time operations, generate reports, and manage schedule modifications. • Driver App ( Fig. 24 (left)): Installed on iPads within the service vehicle, this application pro- vided real-time schedule information to drivers and transmitted pickup/drop-off data, along with location details. • Client App ( Fig. 24 (right)): A cloud-hosted web application, optimized for mobile viewing, Page 24 Chattanooga Area Regional Transportation Authority | August 2025 Figure 22: Supervisors can edit the schedule and override the machine-generated schedule through dispatcher web application that allowed customers to sign up for the service, plan and book trips, and monitor their trip progress. However, practical issues such as low cell phone and internet access among users meant the client app was primarily utilized by customer service for trip planning rather than direct customer usage. A key innovation is the modular and reusable software design, which allows new algorithms to be incorporated by simply changing a configuration file, as solvers are accessible via a REST API. The software, shown in Fig. 23) is designed with the domain knowledge of transit experts in mind. Thus, the focus on integrating human-in-the-loop, enabling human overriding of machine- generated schedules. Operators can drag and drop scheduled trips, with the system providing im- mediate feedback on potential constraint violations, and changes are communicated to drivers in real-time. The system also offers real-time operations monitoring via the web application, display- ing vehicle locations and route status, and alerting the team to violations, no-shows, and anticipated delays. 4.2 Initial Pilot Test 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 ef- ficacy 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 stag- gered 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 situ- ations 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 medi- cal 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 Page 25 Chattanooga Area Regional Transportation Authority | August 2025 Figure 23: A screenshot of the real-time operations view in the operations management page of the dispatcher app while a driver served route 15 time. 4.2.1 Initial Pilot Evaluation 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 Fig. 25. 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. 4.3 Clifton Hills Deployment The culmination of the project is the Clifton Hills microtransit pilot program, an initiative by CARTA to explore the efficacy of flexible, on-demand transit solutions in meeting community mobility needs. Conducted over 27 service days in June and July 2024. During its operational hours, from 9 am to 3 pm, a dedicated vehicle, driver, and booking agent were deployed to serve the community. The pilot served as a practical demonstration and evaluation of novel technol- ogy solutions for on-demand transit, building upon extensive research in paratransit optimization and vehicle routing problems. The program utilized a custom-developed system architecture com- prising dispatcher, driver, and client applications, aiming to provide energy-efficient and equitable transit access in areas typically underserved by traditional fixed-route services. Despite facing operational and technological hurdles, the pilot achieved significant community engagement and provided invaluable insights, confirming the potential of microtransit as a feeder system for high- capacity public transport. The insights gained from this pilot will be instrumental in refining and expanding microtransit services to better serve the community. Our long-term vision is to provide on-demand microtransit services that act as feeders for high-capacity, fixed-route transit services. Implementing this vision will enable agencies to provide energy-efficient and equitable transit access in areas with low pop- Page 26 Chattanooga Area Regional Transportation Authority | August 2025 Figure 24: Different application screens for (left) drivers, (middle and right) client Figure 25: Pilot Metrics recorded for system testing for both deployments. VMT: Vehicle Miles Travelled, VDM: Vehicle Detour Miles, VMT/PMT: Vehicle Miles Travelled to Passenger Miles Travelled, Shared Rate: percentage of trip requests that shared their trip with another passenger. We observe that the proposed offline solver serves all passengers without any violations, with significantly fewer detour miles and a significantly higher shared rate, thereby reducing the total number of miles the vehicles have to drive. ulation density, which are often underserved by existing transit solutions, by combining the energy efficiency of high-capacity transit with the flexibility of microtransit. The Clifton Hills microtransit pilot served to demonstrate and evaluate our novel technology solutions for on-demand transit. The pilot focused on the Clifton Hills community, shown in Section 4.3, with the primary opera- tions hub located at the Metropolitan Ministries (MetMin). MetMin, a local impact center offering services related to housing and food insecurity and medical needs, served as a key location for on-site ride bookings and as a bus station. While most trips were booked in person at MetMin, requests were also accommodated via phone from other locations. 4.3.1 Ridership Statistics Throughout the service period, the Clifton Hills pilot successfully completed 55 public requests, in addition to numerous simulated and internal requests. In total, 68 rides were completed, with round trips counted as two separate rides. This averaged approximately 2.5 rides per service day. Of the 45 individuals who registered for the service, 24 ultimately utilized it by taking at least one ride. On average, customers took 2.8 rides each, with 12 repeat customers indicating a degree of satisfaction and utility. The service experienced a peak of six rides in a single day, although there were seven days with no ridership. The installation of a bike rack two weeks into the pilot, on June Page 27 Chattanooga Area Regional Transportation Authority | August 2025 Figure 26: (a) The area covered by the Clifton Hills project. (b) A CARTA driver using the driver application to identify the next stop on their trip. 18th, was noted as a potential enhancement to the service’s appeal. 4.3.2 Common Destinations The primary operations hub was MetMin, a local impact center that offers services to individuals facing housing and food insecurity, medical needs, and more. MetMin’s facilities were utilized for on-site booking and as a station for the bus. Most trips were booked in person at MetMin, although requests were also taken via phone from other locations. The most frequently visited destination was Market Street, which emerged as the most popular location outside of MetMin, accounting for 18 trips. Market Street was a favorable location for customers that were transfering to fixed routes. Other common destinations included Workman Road (an encampment area, outside the service zone, with 13 trips) and East 11th Street (Chatt Foundation/community kitchen, also outside the service zone, with 12 trips). Additional destina- tions included doctor’s appointments, Suboxone treatment centers, social security offices, shelters, and potential job sites, illustrating the diverse needs of the service users. Regarding trip origins, 17 rides were not booked on-site at MetMin but were instead arranged over the phone by CARTA dispatchers or pre-arranged at MetMin. Furthermore, six rides did not originate or terminate at MetMin, indicating some flexibility in the service’s operational scope. 4.3.3 Operational Obstacles As with any innovative initiative, the pilot encountered both practical and technological chal- lenges. • Practical Issues: Initially, the absence of a bike rack led to some potential riders being turned away. A recurring challenge involved requests for trips slightly outside the designated ser- vice zone, complicating adherence to established boundaries. Furthermore, low cell phone and internet access among users limited the direct utilization of the customer app by patrons, necessitating its use by customer service as a trip planner. • Technological Issues: Technical hurdles included a server going offline due to a power out- Page 28 Chattanooga Area Regional Transportation Authority | August 2025 age, issues with dispatcher feedback for input field validations, difficulties with driver adop- tion and understanding of the technology, system instability when all daily requests were canceled, and errors related to concurrency protections. Despite these technical impedi- ments, the team’s ability to implement quick workarounds and fixes ensured nearly 100% service availability. 4.3.4 Community Engagement The community engagement component of this project seeks to study the ecology of participa- tory organizations in Chattanooga and, once identified, to connect with indigenous networks of residents who are engaged with those organizations. This socio-relational approach to community engagement will facilitate identifying organizations as well as indigenous networks of residents. This contrasts with historical approaches to outreach that focus on mass dissemination of surveys and flyers without regard to existing personal relationships in the community. Our data collec- tion process is less concerned about transportation per se than about the key issues and struggles communities are dealing with (i.e., employment opportunities, development of their children with education and safe activities, care for loved ones like elderly parents, access and affordability of healthy foods). All these struggles have transportation components to them, but we are looking first to what struggles are priorities, and only then will we inquire about transportation options to those priority issues. Another way of thinking about this is that our community engagement process is not looking for customer preferences, but for resident interests. The outreach strategy of our focus groups and interviews is designed to support an increase in ridership and public utilization of the transit system that is being designed. We are currently in the first phase of our engagement plan and have started setting up the focus groups. In addition, we have started aggregating and merging data providing information about census and demographics variable. 4.3.5 Lessons Learned The Clifton Hills microtransit pilot successfully demonstrated the tangible potential of flexible, on-demand transit solutions in effectively addressing community mobility needs. This deployment, as a culmination of research into advanced vehicle routing and paratransit optimization, provided invaluable real-world insights. Despite navigating various practical and technological challenges, the pilot achieved significant engagement and maintained consistent service availability. The lessons learned from this pilot are crucial for refining and expanding future microtransit services, ensuring they better serve communities in a more energy-efficient and equitable manner. The collaborative approach, integrating robust algorithmic optimization with crucial human over- sight, proved key to adapting and maintaining service continuity, thereby paving the way for more seamless and inclusive urban transportation systems. 5 Conclusion and DOE Impact Enhancing public transit competitiveness is especially critical in mid-sized cities typically char- acterized by relatively low-density land use, widely available parking opportunities, and limited transit coverage and frequency. This project is developing operational optimization algorithms that are energy efficient and will support a more significant percentage of the population, improving their transportation choice through enhanced access to transit. The project provides mechanisms to improve transit accessibility with a projected increase from 41% to 73% of residents in the planned study areas while optimizing the energy efficiency of the mixed fleet operations. This will reduce Page 29 Chattanooga Area Regional Transportation Authority | August 2025 single-occupancy vehicle trips by those residents, significantly decreasing transportation energy use at the city level. References [1] Amutheezan Sivagnanam et al. “Minimizing Energy Use of Mixed-Fleet Public Transit for Fixed-Route Service”. In: Proceedings of the 35th AAAI Conference on Artificial Intelli- gence (AAAI-21). 2021. [2] Amutheezan Sivagnanam et al. “Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit”. In: 31st International Joint Conference on Artificial Intelligence (IJCAI). July 2022. [3] Youngseo Kim et al. “Offline Paratransit Vehicle Scheduling via Rolling Horizon Optimiza- tion”. In: 25 International Conference on Intelligent Transportation Systems, ITSC 2022 (under review). 2022. [4] Javier Alonso-Mora et al. “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment”. In: Proceedings of the National Academy of Sciences 114.3 (2017), pp. 462– 467. [5] Michael Wilbur et al. “An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services”. In: 13th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS). May 2022. [6] Philip Kilby, Patrick Prosser, and Paul Shaw. “Guided local search for the vehicle routing problem with time windows”. In: Meta-heuristics. Springer, 1999, pp. 473–486. [7] Laurent Perron and Vincent Furnon. OR-Tools. Version 7.2. Google, 2019. [8] Yvan Dumas, Jacques Desrosiers, and Francois Soumis. “The pickup and delivery problem with time windows”. In: European Journal of Operational Research 54.1 (1991), pp. 7–22. [9] Maria Gabriela S Furtado, Pedro Munari, and Reinaldo Morabito. “Pickup and delivery problem with time windows: a new compact two-index formulation”. In: Operations Re- search Letters 45.4 (2017), pp. 334–341. [10] Marlin W Ulmer et al. Route-based markov decision processes for dynamic vehicle routing problems. Tech. rep. 2017. [11] Levente Kocsis and Csaba Szepesvári. “Bandit based monte-carlo planning”. In: European Conference on Machine Learning. 2006, pp. 282–293. [12] Ayan Mukhopadhyay et al. “An online decision-theoretic pipeline for responder dispatch”. In: International Conference on Cyber-Physical Systems. 2019, pp. 185–196. [13] Waldy Joe and Hoong Chuin Lau. “Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers”. In: Conference on Automated Planning and Scheduling (ICAPS). Vol. 30. 2020, pp. 394–402. [14] R. Sun et al. “TRANSIT-GYM: A Simulation and Evaluation Engine for Analysis of Bus Transit Systems”. In: 2021 IEEE International Conference on Smart Computing (SMART- COMP). Los Alamitos, CA, USA: IEEE Computer Society, Aug. 2021, pp. 69–76. DOI: 10.1109/SMARTCOMP52413.2021.00030. Page 30 Chattanooga Area Regional Transportation Authority | August 2025 [15] Mordechai Haklay. “How good is volunteered geographical information? A comparative study of OpenStreetMap and Ordnance Survey datasets”. In: Environment and planning B: Planning and design 37.4 (2010), pp. 682–703. [16] Daniel Krajzewicz et al. “Recent development and applications of SUMO-Simulation of Ur- ban MObility”. In: International Journal on Advances in Systems and Measurements 5.3&4 (2012). [17] Yuche Chen et al. “A Review and Outlook of Energy Consumption Estimation Models for Electric Vehicles”. In: Society of Automotive Engineers (SAE) International Journal of Sus- tainable Transportation, Energy, Environment, & Policy (2021). [18] Yunteng Zhang et al. “A Data Partitioning-based Artificial Neural Network Model to Esti- mate Real-driving2 Energy Consumption of Electric Buses”. In: Transportation Research Board 100th Annual Meeting (2021). [19] Ruixiao Sun et al. “Hybrid electric buses fuel consumption prediction based on real-world driving data”. In: Transportation Research Part D: Transport and Environment 91 (2021), p. 102637. ISSN: 1361-9209. DOI: https://doi.org/10.1016/j.trd.2020. 102637. [20] Bryan Palmintier et al. “Design of the HELICS high-performance transmission-distribution- communication-market co-simulation framework”. In: 2017 Workshop on Modeling and Simulation of Cyber-Physical Energy Systems (MSCPES). IEEE. 2017, pp. 1–6. [21] Afiya Ayman et al. “Neural Architecture and Feature Search for Predicting the Ridership of Public Transportation Routes”. In: 8th IEEE International Conference on Smart Computing (SMARTCOMP). June 2022. [22] Shaoqing Ren et al. “Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks”. In: CoRR abs/1506.01497 (2015). arXiv: 1506.01497. [23] Sophie Pavia et al. “Deploying mobility-on-demand for all by optimizing paratransit ser- vices”. In: Proceedings of the Thirty-Third International Joint Conference on Artificial In- telligence. IJCAI ’24. Jeju, Korea, 2024. ISBN: 978-1-956792-04-1. DOI: 10 . 24963 / ijcai.2024/822. [24] Sophie Pavia et al. “SmartTransit.AI: a dynamic paratransit and microtransit application”. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI ’24. Jeju, Korea, 2024. ISBN: 978-1-956792-04-1. DOI: 10 . 24963 / ijcai . 2024/1028. Page 31 Chattanooga Area Regional Transportation Authority | August 2025 A API Documentation The API Documentation of the key interfaces through which an external system can interact with the system backend is shown in the next page Page 32 core.db CLIENTS = {'home_address': , 'first_name': , 'last_name': , 'home_lat': , 'home_lon': , 'wc_type': , 'client_id': , 'phone': , 'email': , 'general_client_notes': , 'last_modified': 'datetime_obj'} Description: the clients model schema in Mongo. Refers to paratransit users. For collection name in Mongo see core/config.py/CLIENTS_COLLECTION_NAME. home_address (str): text address of this client first_name (str): first name of client last_name (str): last name of client home_lat (float): latitude of client's home address home_lon (float): longitude of client's home address wc_type (int): see WHEELCHAIRS client_id (int): unique identifier of this client phone (int): phone number of client, for example 1231231234 email (str): email address of client, for example (john@gmail.com) general_client_notes (str): a notes field for the client. Unique keys: client_id Foreign keys: wc_type (WHEELCHAIRS) REQUESTS = {'pickup_address': , 'dropoff_address': , 'pickup_lat': , 'pickup_lon': , 'dropoff_lat': , 'dropoff_lon': , 'am': , 'requested_pickup_dt': 'datetime_obj', 'requested_dropoff_dt': 'datetime_obj', 'request_type': , 'client_id': , 'booking_id': , 'ada': , 'status': , 'last_modified': 'datetime_obj'} Description: the requests model schema in Mongo. Refers to unique trip requests. Each request consists of a pickup and dropoff for a trip requested by a client. For collection name see core/config.py/REQUESTS_COLLECTION_NAME pickup_address (str): text representation of the pickup location dropoff_address (str): text representation of the dropoff location pickup_lat (float): latitude of the pickup location pickup_lon (float): longitude of the pickup location dropoff_lat (float): latitude of the dropoff location dropoff_lon (float): longitude of the dropoff location am (int): number of additional ambulatory passengers accompaning the client on this trip requested_pickup_dt (datetime_obj): the datetime requested for pickup requested_dropoff_dt (datetime_obj): the datetime requested for dropoff request_type (int): is this a pickup constrained request (0) or a drop-off constrained (1) request. client_id (int): see CLIENTS booking_id (int): unique identifier of this trip request ada (bool): true if this request is an ADA trip, false if not ADA status (str): "active", "cancelled", "serviced", "no show" Unique keys: booking_id Foreign keys: client_id (CLIENTS) VEHICLE_MODELS = {'vehicle_model_id': , 'am_capacity': , 'wc_capacity': , 'vehicle_model_name': , 'last_modified': 'datetime_obj'} Description: the vehicle models schema in Mongo. Refers to the types of vehicles. For collection name in Mongo see core/config.py/VEHICLE_MODELS_COLLECTION_NAME. vehicle_model_id (int): unique identifier of this vehicle model am_capacity (int): the maximum number of ambulatory passengers (passengers without wheelchairs) this vehicle can accomidate. wc_capacity (int): the maximum number of wheelchair passengers this vehicle can accomidate. vehicle_model_name (str): the text name of the vehicle Unique keys: vehicle_model_id Foreign keys: None VEHICLES = {'vehicle_model_id': , 'vehicle_id': , 'active': , 'last_modified': 'datetime_obj'} Description: the vehicles model schema in Mongo. Refers to specific vehicles. Each vehicle will be associated with a vehicle model. For collection name in Mongo see core/config.py/VEHICLES_COLLECTION_NAME. vehicle_model_id (int): see VEHICLE_MODELS vehicle_id (int): unique identifier of this vehicle active (bool): True if this vehicle is currently active, False if not (for example because its in the shop). Unique keys: vehicle_id Foreign keys: vehicle_model_id (VEHICLE_MODELS) OPERATORS = {'operator_id': , 'first_name': , 'last_name': , 'phone': , 'email': , 'last_modified': 'datetime_obj'} Description: the operators data schema in Mongo. Operators are drivers to drive the care-a-vans. For collection name in Mongo see core/config.py/OPERATORS_COLLECTION_NAME. TODO need to add operators to development Mongo database. operator_id (int): unique identifier of this operator first_name (str): first name of the operator last_name (str): last name of the operator phone (int): phone number of the operator (for example: 1231231234) email (str): email address of the operator (for example: john@gmail.com) Unique keys: operator_id Foreign keys: None DRIVER_RUNS = {'run_id': , 'start_time': , 'end_time': , 'activation_date': , 'inactivation_date': , 'vehicle_model_id': , 'dow': , 'last_modified': 'datetime_obj'} Description: the driver runs model schema in Mongo. Driver runs are set blocks of time a vehicle (and a driver to drive the vehicle) are available on a given day. For collection name in Mongo see core/config.py/DRIVER_RUNS_COLLECTION_NAME. run_id (int): unique identifier of this run. start_time (str): time of day this run starts in isoformat (for example: "05:00:00" is 5:00AM, "14:00:00" is 2:00PM), EST. end_time (str): time of day this run ends in isoformat (for example: "05:00:00" is 5:00AM, "14:00:00" is 2:00PM), EST. activation_date (str): first date this vehicle run is active in isoformat (for example: "2021-01-01") inactivation_date (str): the last date this vehicle run is active in isoformat (for example: "2021-01- 01") vehicle_model_id (int): see VEHICLE_MODELS dow (int): day of the week, 0 = Monday.... 6= Sunday Unique keys: run_id Foreign keys: vehicle_model_id (VEHICLE_MODELS) TIMETABLES = {'date': , 'state': , 'timetable_version': , 'last_modified': 'datetime_obj'} timetables are unique by date+timetable_version. date (str): date in isoformat (for example: "2021-01-01") state (str): active or inactive. There can only be one active planned schedule in a day. timetable_version (int): identifier of this timetable. MANIFESTS = {'run_id': , 'timetable_version': , 'booking_id': , 'order': , 'early_arrival_dt': 'datetime_obj', 'late_depart_dt': 'datetime_obj', 'date': , 'state': , 'operator_id': , 'action': , 'last_modified': 'datetime_obj'} Description: the manifests model schema in Mongo. A single manifest is an ordered set of locations starting at the depot and ending at the depot for a corresponding driver run on a specific date. The current manifest for a driver run on a date is the manifest with the highest timetable_version. A timetable is a collection of manifests on a given date with the same timetable_version. A unique manifest is governed by run_id + date + timetable_version. run_id (int): see DRIVER_RUNS timetable_version (int): identifier of this timetable. booking_id (int): see REQUESTS order (int): the order of this location in the unique manifest. early_arrival_dt ("datetime_obj"): the datetime at which the vehicle is scheduled to arrive at this location. late_depart_dt ("datetime_obj"): if the vehicle leaves this location later than late_depart_dt, it is running behind and the remaining locations can be affected. date (str): date in isoformat (for example: "2021:01:01") state (str): either "completed", "in-transit", "planned" operator_id (int): see OPERATORS action (str): either "depot_start", "depot_end", "pickup" or "dropoff" Unique key: run_id + date + timetable_version Foreign keys: run_id (DRIVER_RUNS), operator_id (OPERATORS), booking_id (REQUESTS) WHEELCHAIRS = {'wc_type': , 'name': , 'wc': , 'am': , 'manufacturer': , 'year': , 'width_inches': , 'length_inches': , 'last_modified': 'datetime_obj'} Description: the wheel chairs model schema in Mongo. It describes the type of wheelchairs available in the CARTA system. For collection name in Mongo see core/config.py/WHEELCHAIR_COLLECTION_NAME. TODO: need to add this to the mongo dev database. wc_type (int): unique identifier of this wheelchair type name (str): the name of this wheelchair (for example, "standard wheelchair") wc (int): how many WC seats this wheelchair takes up (used in optimization) am (int): how many ambulatory seats this takes up manufacturer (str): text of the manufacturer year (int): year of this wheelchair model width_inches (float): width of wheelchair length_inches (float): length of wheelchair Unique keys: wc_type Foreign keys: none def get_mongo_connection(): Description: Path to mongo credentials must be set in core/config.py/MONGO_CONFIG_PATH. Returns the Mongo client to the database specified in core/config.py/MONGO_CONFIG_PATH. Needs to have write access to the database. Args None Returns pymongo.Client Raises TODO def validate_document_schema(doc, schema): Validates the data types of a document match schema. If doesn't match, returns a NameError. Args doc: (dict) dictionary of a document. schema: (dict) the schema to verify the document with. For example it can be the dictionary associated with CLIENTS or REQUESTS ect. Returns (bool) True if all fields in doc match the provided schema. Raises (KeyError) if there is a field in doc that is not in schema definition, or if there is a field in schema not in doc (TypeError) if there is a field in doc that does not match the type specified in schema def validate_document_schema_batch(docs, schema): Validates the data types of a batch of documents match schema. If a document doesn't match, returns NameError. Args docs: (list[dict]) a list of documents. schema: (dict) the schema to verify the document with. For example it can be the dictionary associated with CLIENTS or REQUESTS ect. Returns (bool) True if all documents match the provided schema. Raises TODO def validate_collection_schema(client, db_name, collection_name, schema): def add_new_client(client, doc): Given a new client as json (python dictionary), write the new client to mongo backend under the database specified at core/config.py/CARTA_DB_NAME and collection at core/config.py/CLIENTS_COLLECTION_NAME. Will autogenerate a unique client ID. It will return the "client_id" of the new client. Args Returns (int) the client_id for this client Raises None def update_client(client, new_doc): new_doc is a json/python dictionary of the client. It will replace the document in Mongo for that client with new_doc. Args new_doc: (dictionary) Returns (int) client_id from new_doc Raises (KeyError) client_id is not in doc (ValueError) client_id does not exist in mongo or client_id is not unique in mongo def get_client_by_client_id(client, client_id): Will return the document associated with the client with client_id. Args client_id: (int) Returns (ValueError) if booking_id is not in mongo or there are multiple documents for this booking_id def add_new_request(client, doc): Adds a new request to mongo. Will autogenerate a unique booking id. Args Returns (int) the booking_id for this request Raises None def update_request_status(client, booking_id, new_status): Will update the "status" field of the request associated with booking_id to new_status. new_status must be "active", "cancelled", "serviced" or "no show" Args booking_id: (int) new_status: (str) Returns None Raises (NameError) new_status is not in "active", "cancelled", "serviced" or "no show" (ValueError) there is 0 or more than 1 documents with this booking_id def update_request(client, new_doc): new_doc is a json/python dictionary of the request. It will replace the document in Mongo with the booking_id in new_doc with new_doc in Mongo. Args new_doc: (dictionary) Returns (int) booking_id from new_doc Raises (KeyError) booking_id is not in doc (ValueError) booking_id does not exist in mongo or booking_id is not unique in mongo def get_request_by_booking_id(client, booking_id): Given a booking_id, it will return a document for this booking_id Args booking_id: (int) Returns (dictionary) Raises (ValueError) if booking_id is not in mongo or there are multiple documents for this booking_id def query_requests_by_date(client, date, as_dataframe=False): Date should be a string in isoformat (i.e. "year-month-day") or a python datetime.date object. Will return all requests of type REQUESTS from the collection specified at core/config.py/REQUESTS_COLLECTION_NAME. If as_dataframe is True, then returns a pandas.DataFrame of all requests on date, otherwise returns a list[dict] of all requests on date. Args client: (pymongo.client) the mongo client connection to the database. date: (str or datetime.date object) the date to return all requests on. as_dataframe: (bool) if True, return the results as a pandas.DataFrame, if False then return a list of dictionaries. Returns pandas.DataFrame or list[dict] Raises def add_vehicle_model(client, doc): Will write doc to core/config.py/VEHICLE_MODELS_COLLECTION_NAME. Will first autogenerate unique "vehicle_mode_id". Args Returns (int) the "vehicle_model_id" of this vehicle. Raises None # def add_vehicle(client, doc): Will write doc to core/config.py/VEHICLES_COLLECTION_NAME. Will autogenerate a unique "vehicle_id". Args Returns (int) the "vehicle_id" for this vehicle. Raises None def add_operator(client, doc): Adds doc to core/config.py/OPERATORS_COLLECTION_NAME. Will autogenerate "operator_id". Args Returns (int) operator_id of new operator Raises None def add_driver_runs(client, doc): Args client: doc: Returns (int) run_id of the new driver run Raises None def query_available_driver_runs_by_date(client, date, join_vehicle_models=False): Date should be a string in isoformat (i.e. "year-month-day") or a python datetime.date object. This function will query the driver_runs that are active on "date". driver_runs collection name is specified at core/config.py/DRIVER_RUNS_COLLECTION_NAME. If join_vehicle_models is True then join with result with vehicle_models table (vehicle_models collection is specified at core/config.py/VEHICLE_MODELS_COLLECTION_NAME). Returns a pandas.DataFrame. Args client: (pymongo.client) the mongo client connection to the database. date: (str or datetime.date object) the date to return all requests on. join_capacity: (bool) if True, will join with vehicle_models Returns pandas.DataFrame Raises def write_timetable(client, manifests, set_as_active_timetable=False): Takes in a timetable (manifests) as a pandas.DataFrame where each column in the dataframe corresponds to a key in MANIFESTS, without the timetable_version field. This method will first get the current timetable_version for that date from Mongo, it will increment it by 1 and set this new timetable version as timetable_version for this set of manifests and then will write it to mongo. Returns date, timetable_version Will also write to TIMETABLES as an inactive timetable. Use set_as_active_timetable to set it as active. Args client: (pymongo.Client) the mongo client connection to the database. Requires write access. manifests: (pandas.DataFrame) set of manifests for a given timetable. Returns (str, int) date, timetable_version Raises TODO def set_active_timetable(client, date, timetable_version): Will set the timetable_version on date as "active" and all other timetable_versions on that date as "inactive". See core/config.py/CARTA_DB_NAME and core/config.py/TIMETABLE_COLLECTION_NAME for collection in mongo. Args date: (str or datetime.date object) the date for which we want to retrieve the current timetable version. timetable_version: (int) Returns None Raises (ValueError) date, timetable_version is not in mongo or there is more than 1 of that timetable_version on date (TypeError) date is not a string or datetime.date object def get_last_timetable_version(client, date): Given a date, this function will return the current timetable_version from MANIFESTS in mongo. The current timetable_version is the greatest timetable_version for that date. If there are no manifests for the given date (i.e. no timetable) then it will return -1. Args client: (pymongo.Client) the mongo client connection to the database. date: (str or datetime.date object) the date for which we want to retrieve the current timetable version. Returns (int) corresponds to timetable_version in MANIFESTS. Raises (TypeError) date is not a string or datetime.date object def query_timetable(client, date, timetable_version, as_dataframe=False): Given a date in either isoformat (for example, "2021-01-01") or a datetime.date object, return the set of manifests (timetable) on "date" for timetable_version. Args date: (str or datetime.date object) timetable_version: (int) as_dataframe: (bool) if True, return the results as a pandas.DataFrame, if False then return a list of dictionaries. Returns (list[dict] or pandas.DataFrame, depending on as_dataframe) active manifests (timetable) for the date Raises (ValueError) if there is not exactly 1 document in timetables collection of timetable_version on date (TypeError) date is not a string or datetime.date object def get_active_timetable_version(client, date): Will return the "timetable_version" that is active for this date. Date is of type datetime.date or str in isoformat. Args date: (str or datetime.date object) Returns (int) the timetable_version that is active on this date. If there is not active timetable then = -1 Raises def write_to_mongo(client, db_name, collection_name, doc, schema=None): Writes a single document to mongo. Returns hash of inserted ID. Args client: (pymongo.Client) the mongo client connection to the database. Requires write access. db_name: (str) database name to write to collection_name: (str) collection name to write to doc: (dict) document to be written schema: (dict) schema to verify document against, if None then no schema validation required. Will not write if validate_document_schema(doc, schema) is False Returns (str) Raises (KeyError) if there is a field in doc that is not in schema definition, or if there is a field in schema not in doc. only if schema is not none. (TypeError) if there is a field in doc that does not match the type specified in schema. only if schema is not none. def write_to_mongo_batch( client, db_name, collection_name, docs, schema=None, ignore_last_modified=False ): Writes a batch of documents to mongo. Returns list of hashes of inserted IDs. Args client: (pymongo.Client) the mongo client connection to the database. Requires write access. db_name: (str) database name to write to collection_name: (str) collection name to write to docs: list(dict) list of documents to write schema: (dict) schema to verify documents against. If None then no schema validation required. Will not write if validate_document_schema_batch(docs, schema) is False Returns (list[str]) Raises (KeyError) if there is a field in doc that is not in schema definition, or if there is a field in schema not in doc. only if schema is not none. (TypeError) if there is a field in doc that does not match the type specified in schema. only if schema is not none. def query_full_collection( client, db_name, collection_name, as_dataframe=False, return_id_field=True ): Returns all documents in a mongo collection. Args client: (pymongo.Client) the mongo client connection to the database. db_name: (str) the database name for this query. collection_name: (str) the collection name for this query. as_dataframe: (bool) if True, return the results as a pandas.DataFrame, if False then return a list of dictionaries. return_id_field: (bool) if True, then '_id' will be included, else ignored. Returns (list[dict] or pandas.DataFrame, depending on as_dataframe) all documents in this collection. Raises None def date_to_datetime_range(date): Date should be a string in isoformat (i.e. "year-month-day") or a python datetime.date object. Will return a datetime.datetime object representing the start and another for the end. For example if date="2021-01-01", then will return datetime.datetime(year=2021, month=1, day=1, hour=0, minute=0, second=0), datetime.datetime(year=2021, month=1, day=1, hour=23, minute=59, second=59). Useful for converting a date into a time range query for Mongo. Will be timezone aware based on the timezone specified at core/config.py/TIMEZONE. Args date: (str or datetime.date) Returns (dt.datetime, dt.datetime) Raises def load_sample_data_to_mongo(client): def delete_sample_data_from_mongo(client): def docs_equal(doc1, doc2, schema): def dateobj_to_datestr(date): converts date (which can be either a datetime.date object or str) to a string in isoformat. Args date: (str or datetime.date object) Returns (str) Raises Chattanooga Area Regional Transportation Authority | August 2025 B Publications The next set of appendices include the key publications that we have referenced in the re- port. Page 47 An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services Michael Wilbur1 , Salah Uddin Kadir2 , Youngseo Kim3 , Geoffrey Pettet1 , Ayan Mukhopadhyay1 , Philip Pugliese4 , Samitha Samaranayake3 , Aron Laszka2 , and Abhishek Dubey1 1 Vanderbilt University, Nashville TN, United States 2 University of Houston, Houston TX, United States 3 Cornell University, Ithaca NY, United States 4 Chattanooga Area Regional Transportation Authority (CARTA), Chattanooga TN, United States ABSTRACT may be available about potential future requests [3]. Although the arXiv:2203.15127v2 [cs.AI] 31 Mar 2022 Many transit agencies operating paratransit and microtransit ser- dynamic and the stochastic versions have traditionally been tackled vices have to respond to trip requests that arrive in real-time, which separately, Bent and Van Hentenryck [3] and Hvattum et al. [13], entails solving hard combinatorial and sequential decision-making among others, showed that dynamic planning could use the sto- problems under uncertainty. To avoid decisions that lead to signifi- chastic information to improve performance. There are three broad cant inefficiency in the long term, vehicles should be allocated to approaches for solving DVRPs with stochastic requests. First, as requests by optimizing a non-myopic utility function or by batching requests arrive, a group of requests can be batched together, and requests together and optimizing a myopic utility function. While routes can be optimized myopically for the particular batch in an the former approach is typically offline, the latter can be performed online manner [1]. Second, the routing problem can be solved to online. We point out two major issues with such approaches when maximize a non-myopic utility function by learning a policy in applied to paratransit services in practice. First, it is difficult to an offline manner that maps any given state of the problem to an batch paratransit requests together as they are temporally sparse. action (i.e., a route plan for the vehicles) [22]. Third, a combina- Second, the environment in which transit agencies operate changes tion of offline computation and online heuristics can be used for dynamically (e.g., traffic conditions can change over time), causing non-myopic planning [3, 15]. the estimates that are learned offline to become stale. To address A fundamental challenge in solving the DVRP non-myopically is these challenges, we propose a fully online approach to solve the computational tractability; indeed, real-world applications of DVRP dynamic vehicle routing problem (DVRP) with time windows and are often intractable since they entail solving a hard combinato- stochastic trip requests that is robust to changing environmental rial optimization problem with consideration for future requests. dynamics by construction. We focus on scenarios where requests Prior work based on the combination of offline learning and on- are relatively sparse—our problem is motivated by applications to line heuristics has addressed this bottleneck to some extent. Bent paratransit services. We formulate DVRP as a Markov decision and Van Hentenryck [3] continuously generate and store a pool process and use Monte Carlo tree search to evaluate actions for any of promising plans. Then, at the time of execution, they use a given state. Accounting for stochastic requests while optimizing a least-commitment strategy to select a key plan from the pool. Shah non-myopic utility function is computationally challenging; indeed, et al. [30] use approximate dynamic programming and leverage the action space for such a problem is intractably large in practice. a neural network-based approximation of the value function to To tackle the large action space, we leverage the structure of the handle the complexity from combinations of passenger requests. problem to design heuristics that can sample promising actions Joe and Lau [15] ensure near real-time response by combining on- for the tree search. Our experiments using real-world data from line routing-based heuristics (e.g., simulated annealing) with offline our partner agency show that the proposed approach outperforms approaches (e.g., value function approximation) [15]. Myopic ap- existing state-of-the-art approaches both in terms of performance proaches, on the other hand, focus on pooling requests together to and robustness. optimally allocate a specific batch of requests to routes [1]. A major challenge in such a setting is computing solutions fast enough to KEYWORDS assign vehicles to requests in real-time (in practice, some delay is acceptable after a request is made). Hence, myopic approaches that Vehicle Routing Problem, Monte Carlo Tree Search, Online Plan- operate in an online manner must be anytime or able to compute a ning, Smart Transit, Decision-making under Uncertainty feasible action quickly; requests are stochastic and a decision must be computed before future requests arrive. Alonso-Mora et al. [1] 1 INTRODUCTION scale a myopic approach to assigning routes to pooled requests The vehicle routing problem (VRP) is a well-known combinatorial for real-world use cases by using an anytime algorithm that starts optimization problem that seeks to assign a fleet of vehicles to from a greedy solution and then improves it through constrained routes to serve a set of customers/requests [7]. Many real-world optimization. use cases of transportation agencies are modeled by the dynamic We focus on paratransit services [20] in this paper, which are version of the problem (DVRP) with stochastic trip requests. In such an important real-world example of DVRPs. Paratransit service is settings, some customer requests may be known at the time of plan- a socially beneficial curb-to-curb transportation service provided ning while others are unknown, and some stochastic information by public transit agencies for passengers who are unable to use fixed-route transit (e.g., passengers with disabilities). Our partner Table 1: Symbols agency, the Chattanooga Area Regional Transportation Authority Notation Description (CARTA), operates paratransit services in a mid-sized metropolitan 𝑉 A set of vehicles each of capacity 𝑐 area in the USA. While paratransit services resemble traditional The set of route plans for all the vehicles with 𝜃 𝑡𝑖 𝜃𝑡 on-demand ride-pooling services in some ways (e.g., the arrival denoting the plan vehicle 𝑣𝑖 ∈ 𝑉 of real-time requests and ride-sharing), our collaboration revealed Θ𝑡 The set of all possible route plans at time 𝑡 A set consisting of locations of all vehicles at time 𝑡 some crucial differences between canonical examples of DVRPs 𝑣𝑙𝑜𝑐𝑡 with 𝑣𝑙𝑜𝑐 𝑡𝑖 denoting the location of 𝑣𝑖 ∈ 𝑉 in prior literature (e.g., ride-pooling or cargo delivery) and para- 𝑅𝑡 A new trip request at time 𝑡 transit services. First, the frequency of requests is usually lower R Ordered set of trip requests for a day [𝑒𝑡 , 𝑝𝑡 ] Service time window for request 𝑅𝑡 than services like taxis. For example, CARTA operates paratransit 𝐶 (𝜃𝑖𝑚 ) Cost of vehicle 𝑚 servicing at route plan services in a metropolitan area with about 1.8 million people and 𝑀 Set of vehicles in the paratransit fleet usually serves about 200 requests per day (with 10 hours of opera- 𝑆𝑖 State tuple < 𝑇𝑖 , 𝑣𝑙𝑜𝑐𝑖 , 𝜃 𝑖 > for timestep 𝑖 tion each day). This constraint makes it difficult to batch requests 𝐸 Generative demand model together for myopic algorithms. Note that while the requests are Maximum number of feasible actions 𝐾𝑚𝑎𝑥 temporally sparse, the decision for each request must be computed to consider at each time epoch quickly. Second, paratransit services operate under the Americans sets from the graph that correspond to feasible actions for the given with Disabilities Act (ADA), which enforces time windows as a state of the MDP. hard constraint, unlike on-demand taxi services, thereby requiring To evaluate the proposed approach, we consider three baselines. strict adherence to such constraints. Our discussion with CARTA First, we look at a greedy strategy, which assigns a new request also revealed a potential issue with offline approaches for solving to the vehicle that provides the highest myopic utility. Second, we DVRPs. In practice, the environment in which CARTA operates look at recent work by Joe and Lau [15], which outperformed well- is highly dynamic; traffic conditions in a city can change due to known state-of-the-art approaches such as the multiple scenario- construction, events, or accidents, and the number of available ve- based approach [3] and the approximate value iteration [35]. Third, hicles or drivers can vary. In such cases, offline approximations can we compare our approach with a batched myopic setting by using potentially lead to decisions that are far from optimal. the work by Alonso-Mora et al. [1]. Our experimental evaluations This paper introduces a fully online approach for use-cases such show that MC-VRP approach outperforms the baselines in terms of as paratransit services that is anytime, non-myopic, robust to dy- performance and robustness to changing environmental conditions. namic changes in the environment, and also scalable to real-world applications. Designing a completely online approach to solve DVRPs in a non-myopic setting is extremely challenging — the 2 PROBLEM DESCRIPTION AND MODEL action space for such a problem is intractably large for real-world Table 1 provides a notation lookup table used throughout this work. applications. For example, for our partner agency in a midsize met- Typically, in paratransit services, passengers request pick-up times ropolitan city in US with five vehicles, each with a capacity of eight in advance of the trip, even when requesting on the same day. This is passengers, the action space is of the order of 1022 . Also, note that in contrast of on-demand ride services that are often requested with while requests are relatively sparse in our problem setting (one re- a short lead time. For example, customers can call in the morning quest every few minutes on average), computation for each decision to request for a ride during early afternoon. However, in some needs to be fairly quick; naturally, it is infeasible to keep customers cases customers request rides with a short lead time. We assume waiting for more than some exogenously defined duration. that requests are i.i.d. according to a distribution 𝐷. We denote the The summary of contributions are as follows: (1) We design request at a given time 𝑡 by 𝑅𝑡 , which consists of a pick-up location, a fully online and non-myopic solver for DVRP with stochastic a drop-off location, a pick-up time, and a drop-off time. requests that scales to real-world problems by leveraging the struc- In practice, it is common for paratransit services to use a pick- ture of the problem instance. Our approach, MC-VRP (Monte Carlo up window, e.g., they commit to picking passengers up at most 15 tree search based solution for vehicle routing problem) is robust to minutes before the requested pickup time and drop them off at most environmental dynamics by construction. (2) We model the DVRP 15 minutes after the requested drop-off time. For a request 𝑅𝑡 , we as a route-based Markov decision process (MDP) [32]. Given an refer to such time points as the earliest pick-up time (denoted by 𝑒𝑡 ) arbitrary state of the MDP, we use generative models over cus- and the latest drop-off time (denoted by 𝑝𝑡 ). Naturally, the latest tomer requests and travel time to simulate the environment under drop-off time must be greater than the sum of the earliest pick-up consideration, which in turn enables us to use Monte Carlo tree time and the minimum time it takes to travel to the drop-off location search [19] to find promising actions for the state. Our approach from the pick-up location. We assume that requests follow such does not require offline training, the only requirement is a gen- constraints. In practice, the application used for making requests or erative model that can be sampled at run-time. (3) To tackle the a human operator can enforce such constraints. Note that the time intractably large action space, we leverage the structure of the prob- windows specified by the customers are treated as strict guidelines lem to find promising actions. Specifically, given a set of routes and making this a pickup and delivery problem with time-windows a new request, we create a weighted graph based on a budget-based (PDPTW) [8]. In case constraints cannot be met, the system rejects heuristic whose edges represent: (a) which vehicles can serve the requests. Given this setting, the goal of the decision-maker is to new request, and (b) which vehicles can swap unpicked requests maximize the total number of requests that can be served in a day from their routes to maximize utility. Then, we sample independent while ensuring that the pick-up and drop-off constraints are met. 2 2.1 Route-based Markov Decision Process is equal to the earliest pick-up time for the customer; otherwise, we Our problem consists of a set of identical vehicles, denoted by 𝑉 , set it to some default value. Third, 𝑝 (𝜃 𝑡𝑖 , 𝑙 𝑗 ) denotes the latest time each with a capacity of 𝑐 passengers. The set of all possible locations at which service is desired at this location. If 𝑙 𝑗 is a dropoff location, in the area is represented by the graph 𝐺 = (𝐿, 𝐸), where 𝐿 denotes 𝑝 (𝜃 𝑡𝑖 , 𝑙 𝑗 ) is set to the latest drop-off time for the customer associated the set of vertices (or locations) in the graph, and 𝐸 denotes the set with the location; otherwise, we set it to some default value. We of edges weighted by travel time. A route plan for vehicle 𝑣 𝑖 ∈ 𝑉 also maintain the number of passengers on-board the vehicle at at time 𝑡 is denoted by 𝜃 𝑡𝑖 , which is an ordered sequence of pick- each location as 𝑤 (𝜃 𝑡𝑖 , 𝑙 𝑗 ). Lastly, let 𝑦 𝑗 be a binary variable set to 0 up/drop-off locations that the vehicle needs to visit in its route. if 𝑙 𝑗 is a pickup location and set to 1 otherwise. Therefore, a route plan 𝜃 𝑡𝑖 can be represented as an ordered set Actions We denote the set of all feasible actions at time 𝑡 by 𝑋𝑡 . {𝑙 1, 𝑙 2, . . .}, where each 𝑙 𝑖 ∈ 𝐿 is a vertex of graph 𝐺. At any given An arbitrary action in 𝑋𝑡 involves assigning the new trip request 𝑅𝑡 time 𝑡, the set of all feasible route plans is denoted by Θ𝑡 (we define to a vehicle 𝑣 𝑖 ∈ 𝑉 and subsequently updating the route plan of all feasibility below). We assume that vehicles start operations at a the vehicles. Note that in our problem setting, 𝑋𝑡 simply reduces depot and return to the depot at the end of the day (𝑑𝑒𝑝𝑜𝑡 ∈ 𝐿). to Θ𝑡 , the set of all feasible route plans at time 𝑡. Updating the To solve the problem of identifying the best routes for all vehi- route plan can entail changing the order in which existing requests cles, we model the dynamic vehicle routing problem (DVRP) as a are picked up/dropped off in a vehicle’s route plan or swapping Markov decision process (MDP) based on prior work done by Ulmer requests that have not been picked up between vehicles. While et al. [32]. An MDP is defined by a 4-tuple {𝑆, 𝐴, 𝑃, 𝛾 }, where 𝑆 is a allowing swapping between vehicles increases the complexity of set of states that capture relevant information for decision-making, the problem significantly, we include such actions nonetheless to 𝐴 is a set of control choices or actions, 𝑃 is a state-action transition maximize utility. The action space is, therefore, the set of all feasible function, and 𝛾 is a reward function that defines the utility of taking route plans. A feasible route must meet three requirements: first, an action at a given state [18]. The route-based MDP formulation the pick-up location for each trip requests must appear before the is beneficial in DVRP settings where actions involve assigning the corresponding drop-off location in the route plan. Second, the pick- current request to a vehicle and optimizing the entire route under up time for a request must not occur before its earliest pick-up time, consideration. Since our goal is to maximize the number of requests and finally, the drop-off time must not occur after its latest possible that can be served in expectation (with respect to the distribution drop-off time. 𝐷), optimizing the route as a whole towards this goal is a natural State Transitions and Rewards At decision-epoch 𝑡, the choice. decision-maker can take an action 𝑥 𝑗 ∈ 𝑋𝑡 (say), which results in a Decision Epoch We define decision epochs as in prior work by transition from the pre-decision state 𝑠𝑡 to the post-decision state Joe and Lau [15]. A decision epoch occurs at the time a request is 𝑠𝑡𝑥 . Then, the system transitions from 𝑠𝑡𝑥 to the next pre-decision received. Between requests, the environment evolves in continuous state 𝑠𝑡 +1 , within which a new request might arrive. We assume time, e.g., the vehicles move continuously, and requests can arrive that requests are drawn from a distribution 𝐷. We refrain from at any point in time. At each decision-epoch, the decision-maker defining the exact state-action transition function since we use a takes an action (states and actions are defined below). The effect of simulator (or a generative model) for online planning. The reward the action results in a state transition, which consists of two parts for an action 𝑥 𝑗 ∈ 𝑋𝑡 , denoted by 𝛾 (𝑥 𝑗 ), is simply the number of — a transition from a pre-decision state to a post-decision state, and additional requests served by the action. Since only one request from the post-decision state to the next pre-decision state [26, 32]. arrives at any decision epoch, the reward simplifies to 1 if the re- State We denote the set of states by 𝑆. We use 𝑠𝑡 to denote the pre- quest can be accommodated and 0 otherwise. Since paratransit decision state at time 𝑡, which includes the vehicle locations, current services require strict adherence to time windows, note that some route plans for all vehicles, and details about passengers aboard the requests can be rejected. In practice, human operators can suggest vehicles. Note that while it suffices to keep track of the route plan alternative choices to customers in such situations. for some formulations, we must track drop-off times for passengers already on board as actions may dynamically change routes. For- 3 APPROACH mally, we represent the state 𝑠𝑡 by the tuple (𝑅𝑡 , 𝑅, 𝑣𝑙𝑜𝑐𝑡 , 𝜃 𝑡 ), where 𝑅𝑡 is the new trip request at time epoch 𝑡, 𝑅 = {𝑅 1, . . . , 𝑅 |𝑉 | } is the We provide an overview of MC-VRP in Figure 1. Our approach set of requests assigned to each of the vehicles, 𝑣𝑙𝑜𝑐𝑡 is a vector of consists of the following three broad components: 1) For a given state of the MDP, we sample feasible and promising actions by location of all the vehicles at time 𝑡, and 𝜃 𝑡 = {𝜃 𝑡1, . . . , 𝜃 𝑡 } is the |𝑉 | exploiting the structure of the problem. To compute feasibility, we current route plan for each of the vehicles. The post-decision state use a heuristic-based solution approach to the PDPTW. To compute is denoted by 𝑠𝑥𝑡 , which denotes the effect of an action 𝑥 on 𝑠𝑡 , and the potential utility of a feasible action, we introduce two heuristics, includes the updated route plan [32]. one based on passenger travel times and another based on budget We associate some additional information with each route plan. (or slack) in route plans. 2) We compute weighted graphs based Consider a route plan 𝜃 𝑡𝑖 for vehicle 𝑣 𝑖 ∈ 𝑉 . For each location 𝑙 𝑗 in on the feasible actions and their potential utilities. Specifically, we the route plan, we associate four pieces of information. First, let create vehicle-vehicle (VV) and request-vehicle (RV) graphs (we 𝑎(𝜃 𝑡𝑖 , 𝑙 𝑗 ) denote the planned arrival time of the vehicle 𝑣𝑖 at location describe the graphs below). Then, we generate promising actions by 𝑙 𝑗 . We can calculate the arrival time from a pre-computed travel sampling independent sets from the graphs (based on the weights time matrix (or a router). Second, let 𝑒 (𝜃 𝑡𝑖 , 𝑙 𝑗 ) be the earliest time of the sets). 3) The sampled actions are then used by our online service may begin at this location. If 𝑙 𝑗 is a pick-up location, 𝑒 (𝜃 𝑡𝑖 , 𝑙 𝑗 ) non-myopic planner based on Monte Carlo tree search. To build 3 Figure 1: An overview of MC-VRP. A decision epoch corresponds with a new trip request 𝑅𝑡 . We generate request-vehicle (RV) and vehicle- vehicle (VV) graphs by combining a heuristic based PDPTW solver with metrics to quickly estimate the utility of route plans. We then select promising actions from the graphs by sampling independent sets of high weights to be evaluated by an online approach based on MCTS. the search tree into the future, we sample future requests from a 𝑉1 𝑉1 data-driven generative model. Finally, to lower computation time, we utilize pre-computed samples of requests and root paralleliza- tion [21] to efficiently explore the search space and recommend 𝑉2 𝑅𝑡 𝑉2 an action for the given state. We describe each component of our approach in detail below. 𝑉3 𝑉3 (a) (b) 3.1 PDPTW Solver Figure 2: (a) RV-graph (𝐺𝑅𝑉 ): there is an edge between a request and a vehicle for every feasible route plan in which a vehicle can service At each decision epoch, our goal is to optimize existing vehicles’ the new request. (b) VV-graph (𝐺𝑉 𝑉 ): an edge between vehicle 𝑣𝑖 routes to accommodate a new request. First, we check whether a and 𝑣 𝑗 represents the swap with the highest utility between the two vehicle can accommodate the request given its current route plan. vehicles. Recall that accommodating a request in our setting requires strict adherence to time windows. We use a heuristic-based solver for the 3.2 Handling Exponential Action Space pickup and delivery problem with time-windows (PDPTW). The A feasible action in our problem corresponds to a set of route plans solver enables us to check if the current request can be accommo- for all vehicles, given that one of them can accommodate the new dated in a feasible route plan. The PDPTW is NP-hard [8, 10]; request in consideration. In case no feasible action is found, the as a result, we use a heuristic subroutine to solve it. Using a request is rejected. Additionally, we design our action space to let heuristic approach is critical in our setting; as we show below, vehicles swap requests from their assigned routes that have not the PDPTW solver needs to be invoked for the given state of the been picked up (we describe how we use the PDPTW solver to MDP as well as for states we sample as we look into the future. this end below). As a result, the number of possible actions for While any heuristic designed for solving PDPTW can be incorpo- a given state is combinatorially large; on average, an arbitrary rated in our framework, we use the insertion heuristic [1], which state in our MDP has 1022 possible actions. Such an action space is seeks to insert the pickup and dropoff locations of the new request infeasible to explore in an online setting. To address this challenge, within the existing route plan. We introduce some additional no- we introduce an approach that enables us to sample promising tation to describe the PDPTW solver. Consider a vehicle 𝑣 𝑖 ∈ 𝑉 actions from the set of feasible actions. We start by introducing two that has an assigned route 𝜃 𝑡𝑖 at time 𝑡. For a new request 𝑅𝑡 , we heuristic metrics that can be used to gauge the long-term utility of use 𝑃𝐷𝑃𝑇𝑊 .𝑓 𝑒𝑎𝑠𝑖𝑏𝑙𝑒𝑃𝑙𝑎𝑛𝑠 (𝜃 𝑡𝑖 , 𝑅𝑡 ) to denote a module that returns a route plan quickly. the set of all feasible route plans for the vehicle 𝑣 𝑖 that include 1.) Maximizing the budget to serve future requests: Our goal is to maximize the number of requests the vehicles serve on a given day while following the specified time constraints. Intuitively, a argmax𝜃 𝑈𝜔 (𝑃𝐷𝑃𝑇𝑊 .𝑓 𝑒𝑎𝑠𝑖𝑏𝑙𝑒𝑃𝑙𝑎𝑛𝑠 (𝜃 𝑡𝑖 , 𝑅𝑡 )), which denotes a vehicle can accommodate future requests in an existing route plan function that computes the utility of each feasible route plan gen- if there is sufficient room (time) in the route. To capture this idea erated by the PDPTW solver based on a specific utility function formally, we build upon prior work by Ulmer et al. [34] to extend 𝑈 and a metric 𝜔, and returns the one with the highest utility. For the idea of a budget-based heuristic to DVRPs with capacity and example, a metric could be the total travel time of the route, and the time window constraints. Our budget-based heuristic captures the utility function, in the simplest case, can be the identity function. idea that maximizing the time a vehicle has no passengers on board 4 also maximizes the slack to serve future requests. We define the distribution). However, a specific realization of 𝑅𝑡 presents an op- budget-based utility for a route plan for vehicle 𝑣 𝑖 ∈ 𝑉 at time 𝑡 as portunity for vehicles to re-plan and potentially swap requests. In ∑︁  order to represent such swapping actions, we create an undirected 𝑏 (𝜃 𝑡𝑖 ) = 𝑡𝑚𝑎𝑥 − 𝑡 − 1 (𝑤 (𝜃𝑡𝑖 , 𝑙 𝑗 ) > 0) 𝑎 (𝜃𝑡𝑖 , 𝑙 𝑗 +1 ) − 𝑎 (𝜃𝑡𝑖 , 𝑙 𝑗 ) vehicle-vehicle (VV) graph at each decision epoch. We denote a VV 𝑗 ∈{1,...,|𝜃𝑡𝑖 |−1} graph by 𝐺𝑉𝑉 = (𝐿𝑉𝑉 , 𝐸𝑉𝑉 ). (1) To construct the graph, we add a node for each vehicle 𝑣 𝑖 ∈ 𝑉 . where 𝑡𝑚𝑎𝑥 denotes the maximum time up to which the vehicle is Edges between two vehicles denote potential swaps of requests available to serve requests (e.g., end of a day), (𝑤 (𝜃 𝑡𝑖 , 𝑙 𝑗 )) denotes that have not been picked up. An edge e𝑉 𝑉 (𝑖, 𝑗, 𝑘) ∈ 𝐸𝑉𝑉 denotes the number of passengers on board vehicle 𝑣 𝑖 from location 𝑙 𝑗 in its the potential swap of request 𝑅𝑘 from vehicle 𝑣 𝑖 to vehicle 𝑣 𝑗 . Note route plan to the next location, 1 () denotes the indicator function, that a swap action creates two new route plans, one for each vehi- and 𝑎(𝜃, 𝑙 𝑘 ) denotes the time a vehicle operating under a route plan cle. We use 𝜃 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘), 𝑣 𝑖 ) to denote the route plan for vehicle 𝜃 reaches location 𝑙 𝑘 . The summation in the equation 1 represents 𝑣 𝑖 after the swap (similarly, we use 𝜃 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘), 𝑣 𝑗 ) to denote the total time in the route plan for which at least one passenger is the route plan for vehicle 𝑣 𝑗 ). The utility of a swapping action, on-board. denoted by 𝑈𝜔 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘)) is denoted as the difference in utility 2.) Minimizing passenger travel time: An alternative to the of the updated route plans and the original route plans, i.e., the budget-based heuristic is to minimize passenger travel time (PTT). plans without the swapping action. As before, 𝑈𝜔 denotes util- Intuitively, by minimizing passenger travel time, we maximize the available capacity in each vehicle over the time horizon. We define ity computed according to a function 𝑈 and metric 𝜔. For exam- the utility of the PTT-based heuristic for a route plan 𝜃 𝑡𝑖 as 𝑃𝑇𝑇 (𝜃 𝑡𝑖 ) ple, using an identity utility function and a metric based on the budget heuristic introduced in equation 1, 𝑈𝑏𝑢𝑑𝑔𝑒𝑡 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘)) = for vehicle 𝑣 𝑖 ∈ 𝑉 at time 𝑡 as shown in equation: ∑︁ 𝑗 𝑏 (𝜃 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘), 𝑣 𝑗 )) + 𝑏 (𝜃 (e𝑉 𝑉 (𝑖, 𝑗, 𝑘), 𝑣 𝑖 )) − 𝑏 (𝜃 𝑡𝑖 ) − 𝑏 (𝜃 𝑡 ). Note 𝑃𝑇𝑇 (𝜃 𝑡𝑖 ) = 𝑤 (𝜃 𝑡𝑖 , 𝑙 𝑗 ) ∗ (𝑎 (𝜃 𝑡𝑖 , 𝑙 𝑗 +1 ) − 𝑎 (𝜃 𝑡𝑖 , 𝑙 𝑗 )) (2) that once a request is swapped, its pickup and dropoff can be in- 𝑗 ∈{1,...,|𝜃𝑡𝑖 |−1} serted at multiple places within the existing route of the vehicle that receives it. For computational tractability, we choose the best inser- In this case 𝑃𝑇𝑇 (𝜃 𝑡𝑖 ) is the summation of the number of passen- tion point using the module 𝑃𝐷𝑃𝑇𝑊 .𝑏𝑒𝑠𝑡𝐹𝑒𝑎𝑠𝑖𝑏𝑙𝑒𝑃𝑙𝑎𝑛 (introduced gers on board after picking up the passenger at location 𝑗, repre- in section 3.1). We show an example of an VV graph in figure 2. sented by 𝑤 (𝜃 𝑡𝑖 , 𝑙 𝑗 ), multiplied by the time to reach the next location, Generating Feasible Actions: A feasible action is an updated 𝑗 + 1. Therefore, by minimizing 𝑃𝑇𝑇 (𝜃 𝑡𝑖 ) we maximize the number set of route plans for all vehicles that do not violate the time win- of seats available to incorporate future requests. dow or capacity constraints. We seek to sample a feasible route Having described metrics to assess the potential utility of a plan from the constructed graph. Our approach is motivated by specific vehicle route for a given vehicle, we now introduce an prior work by Zalesak and Samaranayake [37]. Each edge in the RV approach to sample feasible route plans. We begin by describing graph represents an operation that creates an updated route plan two graphs we construct based on the new request that arrives at a for a vehicle that includes the new request. Additionally, each edge decision epoch and the existing route plans of the vehicles. in the VV-graph represents a swapping operation which creates a RV graph: At each decision epoch, we first generate a graph new route plan for the two vehicles involved in the swap. Therefore, that incorporates which vehicles can service the new request. Our any selected edge in 𝐺𝑅𝑉 ∪ 𝐺𝑉𝑉 represents a feasible action. Addi- idea is based on prior work by Alonso-Mora et al. [1]. We denote tionally, multiple edges can be selected to generate a new action, the RV graph by 𝐺𝑅𝑉 = (𝐿𝑅𝑉 , 𝐸𝑅𝑉 ), where 𝐿𝑅𝑉 denotes a set of if and only if the set of selected edges includes only one of the vertices and 𝐸𝑅𝑉 denotes a set of edges. To create the RV graph, edges from the RV graph. The rationale for such a condition is we add a node for each vehicle 𝑣𝑖 ∈ 𝑉 . We add an additional node straightforward; a new request can only be assigned to one vehicle, to denote the request 𝑅𝑡 . Then, for each feasible vehicle route that and consequently, only one edge from the RV graph can be selected can accommodate the request, we add an edge between the node for a particular feasible action at each decision epoch. To generate denoting the request and each node representing a vehicle. We potential feasible actions quickly, we sample independent sets (a set denote a specific edge in 𝐸𝑅𝑉 by e𝑅𝑉 (𝑖, 𝑗), which denotes the 𝑗th of edges that have no vertices in common) from 𝐺𝑅𝑉 ∪ 𝐺𝑉𝑉 that feasible route plan for vehicle 𝑣 𝑖 that can accommodate the request includes one edge from 𝐺𝑅𝑉 . Such an independent set guarantees under consideration. The feasible route plans are generated by feasibility, as we show below: request 𝑅𝑡 ). We associate two pieces of information with each edge. Theorem 1. Consider graphs 𝐺𝑅𝑉 and 𝐺𝑉𝑉 generated at decision First, for an edge e𝑅𝑉 (𝑖, 𝑗), we use 𝑈𝜔 (e𝑅𝑉 (𝑖, 𝑗)) to denote the utility epoch 𝑡. An independent set of edges from 𝐺𝑅𝑉 ∪ 𝐺𝑉𝑉 that includes of the edge based on a utility function 𝑈 and metric 𝜔. Also, we one and only one edge from 𝐺𝑅𝑉 must be a feasible action for the use 𝜃 (e𝑅𝑉 (𝑖, 𝑗)) to denote the updated route plan corresponding to current state 𝑠𝑡 of the MDP. the edge e𝑅𝑉 (𝑖, 𝑗). We show an example of an RV graph in figure 2. VV-graph: While an RV graph is useful to represent which vehi- Proof. We first list the conditions for feasibility: 1) An action cles can accommodate the new request in their existing route plans, is feasible if it services the current request with adherence to time it is possible that vehicles might want to swap requests that have constraints, and 2) time constraints for existing requests are met not been picked up to maximize utility. Note than in a non-myopic (including potential swaps). An independent set with one edge from setting, the route plans are optimized at each decision-epoch to 𝐺𝑅𝑉 meets condition 1 by construction—all edges from 𝐺𝑅𝑉 service maximize the expected utility with respect to 𝐷 (the request arrival the current request and meet time constraints (recall that edges are 5 checked for feasibility through the PDPTW solver). As the vehicle Algorithm 1 Generating feasible actions that services the request cannot swap requests (by the property of Require: 𝜃 𝑡 , 𝑅𝑡 , 𝐾𝑚𝑎𝑥 , 𝑀, 𝐺𝑉 𝑉 , 𝐺𝑅𝑉 independence), all swaps sampled from 𝐺𝑉𝑉 are also feasible—all 1: Θ𝑡 ← { } ⊲ empty set of feasible actions edges in 𝐺𝑉𝑉 are checked for feasibility through the PDPTW solver. 2: U ← { } ⊲ empty set of utilities for each action Hence the set of independent edges must correspond to a feasible 3: for e𝑅𝑉 (𝑖, 𝑗) ∈ 𝐸𝑅𝑉 do action for the given state. □ 4: 𝜃 ← 𝜃𝑡 5: 𝜃 [𝑖 ] = 𝜃 (e𝑅𝑉 (𝑖, 𝑗)) 6: Θ𝑡 .𝑎𝑝𝑝𝑒𝑛𝑑 (𝜃 ) Notice that the only condition in which a chosen set of edges 7: 𝑈𝑥 ← 𝑈𝜔 (e𝑅𝑉 (𝑖, 𝑗)) from 𝐺𝑅𝑉 ∪𝐺𝑉𝑉 might result in an infeasible action is the following: 8: U.𝑎𝑝𝑝𝑒𝑛𝑑 (𝑈𝑥 ) consider a situation in which the vehicle (say 𝑣 𝑖 ) that is assigned 9: 𝐺𝑉′ 𝑉 = 𝐺𝑉 𝑉 [ {𝑣𝑘 ∈ 𝐿𝑉 𝑉 : 𝑘 ≠ 𝑖 }] the request (denoted by an edge from the RV graph) also engages in 10: while |𝐸𝑉′ 𝑉 | > 0 do swapping and receives an additional request from a different vehicle 11: e𝑉 𝑉 (𝑚, 𝑛, 𝑘) = arg max (𝑚,𝑛,𝑘 ) (𝑈𝜔 (e𝑉 𝑉 (𝑚, 𝑛, 𝑘)) 12: 𝜃 [𝑚] = 𝜃 (e𝑉 𝑉 (𝑚, 𝑛, 𝑘), 𝑣𝑚 ) (say 𝑣 𝑗 ). While both the actions, namely the swapping action and the 13: 𝜃 [𝑛] = 𝜃 (e𝑉 𝑉 (𝑚, 𝑛, 𝑘), 𝑣𝑛 ) servicing of the new request, are checked for feasibility in isolation, 14: Θ𝑡 .𝑎𝑝𝑝𝑒𝑛𝑑 (𝜃 ) vehicle 𝑣 𝑖 might violate time constraints if it seeks to service both. 15: 𝑈𝑥 = 𝑈𝑥 + 𝑈𝜔 (e𝑉 𝑉 (𝑚, 𝑛, 𝑘)) In theory, it is possible to enumerate over each possible set of edges 16: U.𝑎𝑝𝑝𝑒𝑛𝑑 (𝑈𝑥 ) in 𝐺𝑅𝑉 ∪𝐺𝑉𝑉 and check for feasibility; however, enumerating over 17: 𝐺𝑉′ 𝑉 = 𝐺𝑉′ 𝑉 [ {𝑣𝑘 ∈ 𝐿𝑉 𝑉 : 𝑘 ≠ 𝑚 & 𝑘 ≠ 𝑛 }] all such sets is intractable in practice. Therefore, we point out that 18: end while the vehicle that services the request can engage in swapping and 19: end for still maintain feasibility; however, ensuring that such a vehicle does 20: // Filter: 𝑋𝑡 is the 𝐾𝑚𝑎𝑥 actions with highest utility not participate in swapping guarantees feasibility. As a result, we 21: 𝑋𝑡 = Θ𝑡 [𝑎𝑟𝑔𝑆𝑜𝑟𝑡 (𝑈 ) [1 : 𝐾𝑚𝑎𝑥 ] ] use the heuristic of sampling independent sets (with one edge from 22: Return: 𝑋𝑡 the RV graph) that guarantee feasibility by construction. MCTS is that the search tree can be explored asymmetrically, bias- Recall that our goal is to sample promising actions from the ing the search toward actions that appear promising. To estimate set of feasible actions since evaluating all feasible actions in an the value of an action, MCTS simulates a “rollout” to the end of online setting is not tractable. We present our approach to select- the planning horizon using a default policy. In practice, the rollout ing promising actions in algorithm 1. Our approach is based on policy only needs to be computationally cheap; a common method sampling independent sets based on the cumulative sum of edge involves selecting actions randomly during rollout. As the tree is weights of the sets. First, we initialize an empty set of feasible ac- explored and nodes are revisited, each node’s utility is estimated. tions Θ𝑡 and an empty set of utilities U. Then, we begin selecting As the search progresses, the estimates converge towards the true an independent set by selecting an edge from 𝐺𝑅𝑉 (step 3). Next, value of the node. This asymmetric tree exploration allows MCTS we initialize the utility for the route plan (that the independent set to search very large action spaces quickly. MCTS typically requires corresponds to) with the utility of the chosen edge (step 7). Then, a few domain specific components: a generative model of the envi- we drop the corresponding vehicle node from 𝐺𝑉𝑉 and consider ronment, the tree policy used to navigate the search tree, and the swaps iteratively (step 9-10). The utility of the resulting action is default policy used to estimate the value of a node. We describe calculated by adding the utility of serving the request and the swap- each component below. ping action (step 15). Finally, we return a subset of 𝐾𝑚𝑎𝑥 actions Generative demand model: The generative demand model with the highest total utility (step 21-22) to be evaluated by the tree (denoted by 𝐸) provides a method for sampling new requests as search, where 𝐾𝑚𝑎𝑥 is an exogenous parameter. the tree is built into the future. We use a hierarchical modeling approach to sample trip requests based on historical data. We opti- 3.3 MCTS Evaluation mize model parameters based on maximum likelihood estimation. Non-myopic approaches to DVRP rely on hybrid offline-online We model two processes as part of the generative demand model. solutions in which an offline component is trained on historical First, we model the distribution of the number of requests per day data and embedded in an online search [15, 33]. Offline components as a Gaussian distribution. We learn the parameters of the distri- typically require long training periods and must be re-trained each bution by maximizing the likelihood of historical paratransit data. time the environment changes, making them unsuitable for highly Second, to model individual trip requests, we aggregate historical dynamic environments. This motivates us to use MCTS, an online trip requests and weigh each trip request by the number of times it probabilistic search algorithm, to evaluate the long-term utility of is observed (often, some passengers in paratransit services request potential actions. MCTS is an anytime algorithm, and any changing trips that have the same source, destination, and time every week). environmental conditions that are detected can immediately be To sample a sequence of trip requests for a day, we perform the incorporated into its underlying generative models for making following steps: 1) we sample the number of requests (say 𝑚) from decisions [24]. the learned Gaussian distribution over trip requests. 2) We sample MCTS represents the planning problem as a “game tree,” where 𝑚 requests from the weighted aggregation of trip requests.This states are represented by nodes in the tree. The current state is process is repeated a number of times to generate multiple sampled treated as the root node, and actions represent edges that mark chains offline. During inference at decision epoch 𝑡, we provide a transitions from one state to another. The fundamental idea behind 6 Algorithm 2 MCTS evaluation Requested Travel Duration 1200 1000 (seconds) 800 1: 𝑒𝑣𝑒𝑛𝑡𝐶ℎ𝑎𝑖𝑛𝑠 = 𝐸.𝑠𝑎𝑚𝑝𝑙𝑒 (𝑆𝑡 , 𝑛𝑐ℎ𝑎𝑖𝑛𝑠 ) ⊲ sample chains 600 2: 𝐴 = 𝑀𝐶𝑇 𝑆 (𝑋𝑡 , 𝑒𝑣𝑒𝑛𝑡𝐶ℎ𝑎𝑖𝑛𝑠) ⊲ action scores 400 3: 𝐴¯ = { } 200 0 4: for 𝑎 ∈ 𝐴 do parallel 04 b 05 0 05 0 06 0 06 0 07 0 07 0 08 0 08 0 09 0 09 0 10 0 10 0 11 0 11 0 12 0 12 0 13 0 13 0 14 0 14 0 15 0 15 0 16 0 16 0 17 0 17 0 18 0 18 0 19 0 19 0 20 0 20 0 21 0 21 0 22 0 22 0 ¯ :3 2, :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 :0 :3 Fe 5: ⊲ aggregate across chains 0 20 21 6: end for Requested pick up times 7: // Return action with highest action score 8: Return: 𝑎𝑟𝑔𝑚𝑎𝑥𝑥𝑖 ∈𝑋 (𝐴¯ [𝑖 ]) Figure 3: The temporal distribution of requests and the requested travel duration for the requests from one day. method 𝐸.𝑠𝑎𝑚𝑝𝑙𝑒 (𝑡, 𝑛) which samples 𝑛 chains uniformly at ran- dataset consists of a total of 25,843 trip requests. Each request in dom from 𝐸 and returns the requests in each chain that occur after our dataset consists of a geo-coordinate (longitude, latitude) for the current time 𝑡. the pickup location and dropoff location, and also the requested Search policy: We use the standard Upper Confidence bound for pickup time. As an example, we show the temporal distribution of Trees (UCT) [19] to navigate the search tree and decide which nodes one of the days and the requested travel duration for each request to expand. When expanding a node, we use algorithm 1 to sample in figure 3. For pre-processing, each pickup and dropoff location feasible actions for the given state. When working outside the was assigned to the nearest node in the road network graph. We MCTS tree to estimate the value of an action during rollout, we rely used the haversine distance to calculate the distance between two on a default policy. This is a lightweight policy which is simulated geo-coordinates. We filtered out any requests that had a pickup or up to a time horizon and the utility of the simulation is propagated dropoff location that was farther than 200 meters from the nearest up the tree. Our default policy is a greedy assignment—for a given node in the road network; this process filtered out approximately state, we choose the edge with the highest myopic utility from the 5% of the requests. Of the 25843 trips in the original dataset, 24543 RV-graph. To ensure tractability, we do not incorporate swapping remained after the distance filter. As paratransit services are sig- requests between vehicles into our rollout policy; this saves time nificantly more sparse on weekends, we included only weekday during MCTS evaluation as the VV graph is not generated during trips for our analysis that spanned 129 days (94% of the trips in rollout. our data occur on weekdays).We randomly selected 15 days from Root parallelization: Given that the sampled paratransit re- the dataset for the evaluation (test) set. The remaining 114 days quests can be both sparse and highly uncertain in time and space, were use to compute 100 synthetic days worth of trip requests (i.e., sampling one chain of requests might not adequately represent chains) for the generative model using the procedure outlined in future demand. To handle this uncertainty, we use root paralleliza- section 3.3. Three more chains were generated as a calibration set tion, which involves sampling many chains, and instantiating a for parameter tuning. separate MCTS tree for each with the current request as the root Road Network and Travel Time Matrix: We use Open- node. Crucially, each tree is explored in parallel. After execution, StreetMap (OSM) [23] for the road network for the area under the score for each of the actions from the common root node is consideration and OSMNX [4] to generate a routing graph of the averaged across trees. Then, the action with the highest average road network with travel time for edge weights. Unless otherwise score across the trees is returned as the selected action. noted, the experiments used the free flow speed as edge weight. The process for evaluating and selecting an action is provided in Then, we calculated the shortest paths between all pairs of net- algorithm 2. The algorithm takes 𝑋𝑡 from the feasible actions com- work to generate a matrix of travel times. The travel time matrix is ponent as well as the current state 𝑆𝑡 , the generative model 𝐸 and the generated offline and therefore, provides constant lookup time for number of chains to sample 𝑛𝑐ℎ𝑎𝑖𝑛𝑠 . First, the set of 𝑒𝑣𝑒𝑛𝑡𝐶ℎ𝑎𝑖𝑛𝑠 is querying travel times between arbitrary locations in the area under sampled from the generative model (line 1). Second, a tree is instan- consideration. Additionally, we collected historical traffic data from tiated and MCTS is performed in parallel on each of the trees. This INRIX [14] to estimate typical travel times during times of high processed is represented by 𝐴 = 𝑀𝐶𝑇 𝑆 (𝑋𝑡 , 𝑒𝑣𝑒𝑛𝑡𝐶ℎ𝑎𝑖𝑛𝑠), where 𝐴 congestion. We use congestion data for evaluating the robustness is a two dimensional tensor of size |𝑋𝑡 | × 𝑛𝑐ℎ𝑎𝑖𝑛𝑠 (line 2). In this of the proposed approach. sense, each row in 𝐴 represents a feasible action and the columns Road network and travel time matrix: We use Open- represent the chains. The mean of each row in 𝐴 represents the StreetMap (OSM) [23] for the road network for the area under action score and is stored in 𝐴¯ (line 5). Finally, the action with the consideration and OSMNX [4] to generate a routing graph of the maximum action score in 𝐴¯ is returned (line 8). road network with travel time for edge weights. To evaluate robust- ness we use INRIX traffic data to generate new travel time matrices 4 EXPERIMENTS AND RESULTS that represent typical congested patterns in the city. The INRIX In this section we describe the data, experimental setup, system dataset included average roadway speeds per hour for each day in parameters, baselines and results. the week and included an OSM ID which was mapped to the OSM road network. 4.1 Data Description and Pre-Processing Paratransit Data: We acquired six months of paratransit trip re- quests between January 1, 2021 and July 1, 2021 from CARTA. Our 7 4.2 System Parameters Table 2: Parameter settings Our experimental parameters are as follows: we vary the number Parameter Values of vehicles from 3 to 5 as we find that 5 vehicles can serve 100% of Number of vehicles (𝑀 ) 3, 4, 5 the trip requests in our setting using MC-VRP. The vehicle capacity Vehicle capacity 8 Request arrival time 60m is set to 8, which is in accordance with the capacity of typical para- Time window 15m transit vans. The request arrival time, defined as the time before the Runtime cutoff Inf, 30s requested pickup time that the request is available to the system, 𝐾𝑚𝑎𝑥 10 is set to 60 minutes. In practice, such requests can also be made MCTS depth 20 MCTS iterations 1000 before 60 minutes. The time window, i.e., the amount of time before 𝑛𝑐ℎ𝑎𝑖𝑛𝑠 25 the requested pickup time that a request can be picked up is set to 15 minutes (in accordance with settings used by CARTA). Addi- setting. Also, the problem formulation by Joe and Lau [15] seeks tionally, when a customer requests a trip we provide an estimated to minimize the sum of the travel and waiting times of all vehicles. dropoff time which is the sum of the requested pickup time and the It serves all requests and incurs a penalty cost for time-window minimum travel time to the dropoff location. The late time window violations. To apply DRLSA to our problem formulation, where is 15 minutes after the estimated dropoff time which is again, in time-windows constraints are strict, we take the route plans out- accordance with settings used by our partner agency. Additionally, put by DRLSA and iteratively remove requests that violate time we reiterate that as the time windows are hard constraints, a trip is windows until a maximal feasible set of requests is left. Further, only feasible if the passenger is picked up and dropped off between for a fair comparison, we run the DRLSA algorithm itself with the early pickup window and late dropoff window. shorter time windows but remove requests that violate the origi- Since our online approach is anytime, we vary the amount of time nal time windows, which we found significantly improves the that is allocated to the algorithm for making a decision (referred to service rate of DRLSA in our setting. Finally, we point out that as runtime cutoff). Practitioners can vary this parameter to account since there was no open-source implementation available for this for the maximum time they can afford to assign a request to a approach, we implemented DRLSA for this paper. vehicle. Note that the passenger making the request need not wait • Myopic and Anytime trip-vehicle assignment-based on for this duration to receive a feedback; whether a request can be RTV graphs [1] (MA-RTV): We also compare our approach serviced or not can be computed in less than a second using our with an anytime algorithm that batches requests together and approach (we only need to construct the RV graph to find at least then maximizes the myopic utility for the specific batch of re- one feasible action). We consider two variants of our proposed MC- quests. For each batch, the algorithm creates an RTV graph by VRP approach. MC-VRP (budget) uses our budget-based utility checking shareability between requests as well as requests and for scoring feasible actions in algorithm 1, while MC-VRP (PTT) vehicles. Since the best passengers-vehicle pair is found in each uses the PTT-based utility for scoring feasible actions. The MCTS batch, the approach works well in practice despite being my- evaluation as outlined in section 3.3 remains the same for both opic (our experiments confirm this). We refer to this baseline variants. as MA-RTV. To adapt MA-RTV for our problem setting, we set the parameters as follows. First, as MA-RTV is not able to han- dle requests in advance, we set the request arrival time to the 4.3 Baselines early time window. Second, we set the latest dropoff time to 30 We evaluate the performance of MC-VRP against the following minutes (15 minutes for early time window and 15 minutes for baselines. For all baselines, we use the same number of vehicles late time window) plus the shortest path between the pickup and (we present results by varying the number of vehicles) and vehicle dropoff locations. Therefore, the time window requirements are capacity as MC-VRP. We compare our approach to two myopic equivalent to our problem setup. Lastly, MA-RTV is a batching online approaches (greedy and MA-RTV) and one non-myopic approach which waits for a set period of time before grouping hybrid approach (DRLSA). requests together for assignment. In the paratransit setting, re- • Greedy assignment (greedy-PTT, greedy-budget): Greedy quests rarely arrive very close together and are expected to be assignment consists of first generating feasible actions according handled one at a time, typically over the phone. Therefore we to algorithm 1 and then selecting the action with the highest set the batch interval to 20 seconds, which closely mimics the utility. For comparison, we include greedy assignment using observed paratransit data. both the PTT and budget utilities. We refer to greedy assignment with the PTT utility as greedy-PTT and greedy assignment with the budget utility as greedy-budget. 4.4 Parameter Tuning • Deep reinforcement learning-based vehicle routing [15] We used 3 days of paratransit data for hyperparameter tuning. (DRLSA): Joe and Lau combine deep reinforcement learning, MC-VRP has two parameters for tuning—the depth of the search which approximates a state-value function for routing, with a tree and the number of feasible actions. MCTS tree depth, which simulated-annealing based routing heuristic to solve the dynamic is the number of future requests to consider from the generative vehicle routing problem [36]. The state representation of DRLSA model, was varied between {10, 20, 30}. The number of feasible is based on the total cost of the planned routes of the vehicles. actions to explore, denoted by 𝐾𝑚𝑎𝑥 , effectively sets the maximum While the original approach is designed for cargo-delivery prob- branching factor for MCTS. We varied this parameter between lems, we add pickup and dropoff constraints given our problem {10, 15, 20, 25, 30}. We performed a grid search using the calibration 8 DRLSA MA-RTV greedy-PTT greedy-budget MC-VRP (PTT) MC-VRP (budget) 100 % 80 % 60 % 40 % 20 % 0% 3 Vehicles 4 Vehicles 5 Vehicles Number of Vehicles Figure 4: Service rate, defined as percentage of trips served, per day on 15 day test set for 3, 4 and 5 vehicles. 5 vehicles was enough to service all request on most days for MC-VRP (budget), MC-VRP (PTT) and MA-RTV. MC-VRP (budget) had the highest median service rate for 3 and 4 vehicles. The budget-based heuristic improves service rate for MC-VRP by 2.2% and 2.1% and greedy assignment by 3.4% and 4.9% for 3 and 4 vehicles respectively. set and found the best parameters in terms of service rate (MCTS We also observe that the budget-based heuristic works better depth of 20 and 𝐾𝑚𝑎𝑥 = 10). The final parameters for MC-VRP are than the travel time-based heuristic for both Monte Carlo tree provided in Table 2. search as well as greedy assignment. Indeed, MC-VRP (budget) The calibration set was also used to select the parameters for results in a higher service rate than MC-VRP (PTT) and greedy- DRLSA. The neural network of the DRLSA baseline approach con- budget outperforms greedy-PTT for all fleet sizes. This indicates sists of 1 hidden layer with 64 neurons. The activation function of that the budget utility, which aims to maximize time for which a the hidden layer is rectified linear (ReLu) and linear for the output vehicle has no passengers on-board, can be used to quickly compute layer. We trained the network with a batch size of 32, the discount promising actions to explore. It is important to note that while we factor for future reward is 0.99, and the learning rate is 0.01. We focus on paratransit services, the budget-based heuristic can be found the best result with 𝐾𝑚𝑎𝑥 = 500 for Simulated Annealing. applied for other DVRPs with capacity and time window constraints. Similar to MC-VRP, we used grid search to find the best parameters We also observe that DRLSA had the lowest service rate across all for DRSLA. fleet sizes. An influencing factor, as discussed in section 4.3, is that time windows are soft constraints in DRSLA which is not particularly suited to paratransit settings. 4.5 Reproducibility Computation Time: The computation time per request for MC- Our source code, implementation of the baseline approaches, and VRP and the baselines is shown in figure 5. MC-VRP (budget) takes samples of our datasets are available online (https://github.com/ slightly longer than MC-VRP (PTT) to compute a decision, with a smarttransit-ai/iccps-2022-paratransit-public). We implemented median computation time of 38 seconds, 49 seconds, and 40 seconds MC-VRP in the Julia programming language using the pomdps.jl as compared to 36 seconds, 44 seconds, and 37 seconds for 3, 4, framework [9]. Results presented in this paper were obtained using and 5 vehicles respectively. DRLSA, MA-RTV, and greedy all had the Chameleon testbed supported by the National Science Founda- median computation times less than 3 seconds. In this context, the tion [16]. fact that MC-VRP is both non-myopic and fully online is reflected in the higher runtimes; while the observed runtimes are acceptable 4.6 Results in our setting, i.e., paratransit services, the application of online Service Rates: Our primary objective is to maximize the number of and non-myopic methods remains an open question in general requests serviced each day. The service rate per day for the 15 days VRP settings. Note that if the MCTS evaluation of our approach is in the evaluation (test) set is provided in figure 4 with fleet sizes not used (i.e., the early stopping time approaches 0), our approach of 3, 4, and 5 vehicles. We first present results in a setting where simplifies to the greedy baseline, which takes less than a second on MC-VRP (budget) and MC-VRP (PTT) are allowed to run for 1000 average. This observation means that the majority of computation iterations without early termination. First, we note that 5 vehicles time in our approach is spent on MCTS. is enough to service all of the requests on most days as MC-VRP As discussed, the MCTS evaluation can be run in the background (budget), MC-VRP (PTT), and MA-RTV all have a median service between calls. Therefore, a potentially limiting factor for our ap- rate of 100%. We observe that MC-VRP (budget) outperforms all proach is the rate at which requests arrive; even when running in baselines for fleet sizes of 3 and 4 with with a median service rate background between requests, MC-VRP must be stopped on the of 87.0% and 97.6% respectively. MC-VRP (PTT) had a service rate arrival of a new request. Since MC-VRP is an anytime algorithm, of 84.7% and MA-RTV had a service rate of 81.7% for 3 vehicles. it is possible to set a maximum computation time per request. In MA-RTV outperformed MC-VRP (PTT) in the case of 4 vehicles such a setting, the algorithm is stopped early (in our case, before with a median service rate of 96.2% compared to 95.8%. 9 MC-VRP (PTT) MC-VRP (budget) Compute Time per Request (s) 80 60 40 20 0 3 Vehicles 4 Vehicles 5 Vehicles Figure 7: (a) Free-flow speed vs (b) Irregular travel times in seconds. Number of Vehicles Irregular travel times represent a congested roadway network. Each Figure 5: Computation time per request in seconds for each day in cell shows the travel time from a location x to another location y. the test set for 3, 4 and 5 vehicles. Median computation time per re- There are total 10788x10788 combinations in the travel time matrix. quest for MC-VRP (budget) is 38 seconds, 49 seconds and 40 seconds for 3, 4 and 5 vehicles respectively. DRLSA, MA-RTV and greedy all had median computation times less than 3 seconds per request. DRLSA MA-RTV greedy MC-VRP % Change in Service Rate 0% MC-VRP (budget) 6% −10 % % Change in Service Rate 4% −20 % 2% 0% −30 % −2 % −40 % −4 % 3 Vehicles 4 Vehicles 5 Vehicles −6 % Number of Vehicles 3 Vehicles 4 Vehicles 5 Vehicles Figure 8: Robustness to roadway congestion: Percent change in ser- Number of Vehicles vice rate for DRLSA, MA-RTV, greedy-budget and MC-VRP (budget) Figure 6: Runtime analysis: Percent change in service rate for MC- on test set using congested travel time matrix compared to free-flow VRP (budget) with a cutoff of 30 seconds per request compared to speed matrix. MC-VRP (budget) had less of a decrease in service rate no cutoff. For three vehicles there was a median of 1.2 percent de- for 3, 4 and 5 vehicle fleets compared to the baselines. crease in service rate on test set while the computation cutoff had The original travel time matrix was calculated by finding shortest negligible affect for four and five vehicles. paths between all nodes in an OSM graph where the edge weights the default number of iterations is reached), but outputs a feasi- were travel time between the nodes using free flow speed. Each ble solution. In our dataset, 99% of requests arrive more than 30 edge in the OSM graph had a unique OSM ID which mapped to seconds after the previous request and the median time between roadway speeds in the INRIX dataset. The INRIX dataset included requests was approximately 5 minutes. Therefore, we evaluate the average roadway speeds per hour for each day in the week. For performance of MC-VRP with a 30 second cut-off time in figure 6. each OSM ID we took the speed at the 5th percentile and updated We observe only a negligible decrease in service rates; the median the edge weights accordingly. On average, the congested travel time service rate decreases by 1.2% for 3 vehicles and 0% for 4 and 5 matrix had speeds that were 30% slower than the free-flow speed. vehicles. We evaluated DRLSA, MA-RTV, greedy-budget and MC-VRP Robustness: To evaluate the robustness of the proposed ap- (budget) on the 15 day evaluation set using the congested travel time proach with respect to changing environmental conditions, we network and compared the resulting service rates to those generated change the travel time distribution in the city. For experiments, we without congestion. We observe that MC-VRP (budget) incurs less assume the existence of a service that uses short term observations of a decrease in service rate compared to DRLSA, MA-RTV and about an environmental variable (e.g., travel times) and provides greedy-budget across all sizes of vehicle fleets as shown in figure 8. an updated model. In practice, transit agencies can use services like As expected, DRLSA had the greatest decreases in service rate due Google maps for this purpose. In this case, when a user requests a to its reliance on a value function that was trained offline using ride, we can use the updated travel time matrix to give an accurate the free-flow travel time matrix. While hybrid approaches such as estimate of the dropoff time. We assume that all approaches have DRLSA have access to the real-time travel conditions, it is difficult access to the updated travel time matrix at inference time, i.e. when to re-train offline components, resulting in a higher degradation in a user requests a ride. However, approaches that rely on models performance. Both MA-RTV and greedy-budget outperform DRLSA trained offline do not have the ability to update their model. when evaluated for robustness. This result is expected since MA- We generate a modified travel time matrix that resembles a con- RTV and greedy-budget are both online approaches, it is able to gested road network. The distribution of the free-flow travel time adapt to the updated matrix. We also observe that MC-VRP (budget) matrix and the congested travel time matrix is shown in Figure 7. performs better MA-RTV and greedy-budget, showing that our 10 non-myopic online solution improved upon the myopic online heuristics that can sample promising actions for evaluation through approaches as well. MCTS. Our experimental results demonstrate superior performance and increases robustness against state-of-the-art baselines. 5 RELATED WORK ACKNOWLEDGEMENTS Vehicle Routing Problems (VRPs) can be broadly classified as ei- ther static or dynamic [27]. In static VRPs, all inputs are received This material is based upon work sponsored by National Science before optimizing routes, whereas in dynamic VRPs inputs are up- Foundation under grant CNS-1952011 and Department of Energy dated concurrently with the determination of the route. The focus under Award Number DE-EE0009212. of this paper is on dynamic VRPs (DVRP), which can be either dynamic-deterministic, in which no stochastic information about REFERENCES future inputs is known, or dynamic-stochastic, in which some prob- [1] Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017. On-demand high-capacity ride-sharing via dynamic trip- abilistic information is known about the inputs that dynamically vehicle assignment. Proceedings of the National Academy of Sciences 114, 3 (2017), evolve [25]. These stochastic inputs can include models over travel 462–467. [2] Andrea Attanasio, Jean-François Cordeau, Gianpaolo Ghiani, and Gilbert Laporte. times, demands, and customer information [28]. DVRPs can be 2004. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride solved to maximize myopic rewards [1] or a non-myopic utility problem. Parallel Comput. 30, 3 (2004), 377–387. function [15, 30]. Exact methods for solving DVRPs seek to find [3] Russell W Bent and Pascal Van Hentenryck. 2004. Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research an optimal solution, but are often constrained to small problem 52, 6 (2004), 977–987. instances due to computational complexity, e.g., such approaches [4] Geoff Boeing. 2017. OSMnx: New methods for acquiring, constructing, analyzing, include column-generation [5] and the set-partitioning method [6]. and visualizing complex street networks. Computers, Environment and Urban Systems 65 (2017), 126–139. Metaheuristic approaches have also been applied to DVRPs, includ- [5] Huey-Kuo Chen, Che-Fu Hsueh, and Mei-Shiang Chang. 2006. The real-time ing particle swarm optimization [17], genetic algorithms [31], and time-dependent vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review 42, 5 (2006), 383–408. tabu search [2, 11]. Decision theoretic approaches have also been [6] Christian H Christiansen and Jens Lysgaard. 2007. A branch-and-price algorithm applied to DVRPs. DVRP is a sequential decision-making problem, for the capacitated vehicle routing problem with stochastic demands. Operations and can be modeled as a Markov Decision Process (MDP). One Research Letters 35, 6 (2007), 773–781. [7] George B Dantzig and John H Ramser. 1959. The truck dispatching problem. approach is to use a conventional MDP structure, where actions Management Science 6, 1 (1959), 80–91. consist of determining the next customer to serve at each decision [8] Yvan Dumas, Jacques Desrosiers, and Francois Soumis. 1991. The pickup and epoch. Another approach, proposed by Ulmer et al. [32], is based on delivery problem with time windows. European Journal of Operational Research 54, 1 (1991), 7–22. using a route-based MDP where the state-action space includes not [9] Maxim Egorov, Zachary N Sunberg, et al. 2017. POMDPs. jl: A framework for only assigning an incoming request to a vehicle, but also optimizing sequential decision making under uncertainty. The Journal of Machine Learning Research 18, 1 (2017), 831–835. the vehicles’ routes. [10] Maria Gabriela S Furtado, Pedro Munari, and Reinaldo Morabito. 2017. Pickup There are three ways to solve the DVRP MDPs: offline, online, and delivery problem with time windows: a new compact two-index formulation. and hybrid solution methods. Offline methods pre-compute a policy Operations Research Letters 45, 4 (2017), 334–341. [11] Michel Gendreau et al. 1999. Parallel tabu search for real-time vehicle routing that is queried while executing a plan [22, 30, 35]. Offline policies and dispatching. Transportation Science 33, 4 (1999), 381–390. can be slow to learn, but can make decisions very quickly at ex- [12] Justin C Goodson, Barrett W Thomas, and Jeffrey W Ohlmann. 2017. A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic ecution time, and are therefore useful when there are strict time programs. European Journal of Operational Research 258, 1 (2017), 216–229. constraints on decision-making. Online solution methods perform [13] Lars M Hvattum et al. 2006. Solving a dynamic and stochastic vehicle routing computations during plan execution. These are generally sampling problem with a sample scenario hedging heuristic. Transportation Science 40, 4 (2006), 421–438. approaches, and only focus on the states of the system relevant to [14] INRIX. 2014. INRIX Interface Guide. (2014). the current decision being made. Online methods include rollout al- [15] Waldy Joe and Hoong Chuin Lau. 2020. Deep reinforcement learning approach to gorithms [12, 29] and multiple scenario approach (MSA) [3]. Online solve dynamic vehicle routing problem with stochastic customers. In Conference on Automated Planning and Scheduling (ICAPS), Vol. 30. 394–402. approaches have typically been applied to problem settings without [16] Kate Keahey, Jason Anderson, et al. 2020. Lessons Learned from the Chameleon strict time constraints on decision-making (the time it takes to com- Testbed. In Proceedings of the 2020 USENIX Annual Technical Conference (USENIX pute a decision), and in dynamic environments where policies gen- ATC ’20). [17] Mostepha R Khouadjia, Briseida Sarasola, Enrique Alba, Laetitia Jourdan, and erated offline can become stale. Hybrid solution methods attempt El-Ghazali Talbi. 2012. A comparative study between dynamic adapted PSO to combine offline and online approaches to leverage the strengths and VNS for the vehicle routing problem with dynamic requests. Applied Soft Computing 12, 4 (2012), 1426–1439. of both. For example, Ulmer et al. [33] propose an approach that [18] Mykel J Kochenderfer. 2015. Decision Making Under Uncertainty: Theory and embeds a value function learned using ADP into an online roll- Application. MIT press. out algorithm. Joe and Lau [15] propose a similar approach, which [19] Levente Kocsis and Csaba Szepesvári. 2006. Bandit based monte-carlo planning. In European Conference on Machine Learning. 282–293. combines Deep Reinforcement Learning to approximate a value [20] Roy Lave and Rosemary Mathias. 2000. State of the Art of Paratransit. Trans- function offline with an online simulated annealing approach. portation in the New Millennium 478 (2000), 1–7. [21] Ayan Mukhopadhyay, Geoffrey Pettet, Chinmaya Samal, Abhishek Dubey, and Yevgeniy Vorobeychik. 2019. An online decision-theoretic pipeline for responder 6 CONCLUSION dispatch. In International Conference on Cyber-Physical Systems. 185–196. [22] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder, and Martin Takáč. We design a non-myopic online approach for DVRP for paratransit 2018. Reinforcement learning for solving the vehicle routing problem. Neural services that is robust to environmental changes by construction Information Processing Systems (2018). [23] OpenStreetMap contributors. 2017. https://planet.osm.org . and scalable to real-world applications. To tackle the intractable [24] Geoffrey Pettet, Ayan Mukhopadhyay, Mykel J Kochenderfer, and Abhishek action space, we leverage the structure of the problem to design Dubey. 2021. Hierarchical planning for resource allocation in emergency response 11 systems. In International Conference on Cyber-Physical Systems. 155–166. Transportation Research Part C: Emerging Technologies 12, 3-4 (2004), 235–250. [25] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L Medaglia. 2013. [32] Marlin W Ulmer et al. 2017. Route-based markov decision processes for dynamic A review of dynamic vehicle routing problems. European Journal of Operational vehicle routing problems. Technical Report. Research 225, 1 (2013), 1–11. [33] Marlin W Ulmer, Justin C Goodson, Dirk C Mattfeld, and Marco Hennig. 2019. [26] Warren B Powell. 2007. Approximate Dynamic Programming: Solving the curses Offline–online approximate dynamic programming for dynamic vehicle routing of dimensionality. Vol. 703. John Wiley & Sons. with stochastic requests. Transportation Science 53, 1 (2019), 185–202. [27] Harilaos N Psaraftis, Min Wen, and Christos A Kontovas. 2016. Dynamic vehicle [34] Marlin W Ulmer, Dirk C Mattfeld, and Felix Köster. 2018. Budgeting time for routing problems: Three decades and counting. Networks 67, 1 (2016), 3–31. dynamic vehicle routing with stochastic customer requests. Transportation Science [28] Ulrike Ritzinger, Jakob Puchinger, and Richard F Hartl. 2016. A survey on dynamic 52, 1 (2018), 20–37. and stochastic vehicle routing problems. International Journal of Production [35] Marlin W Ulmer, Barrett W Thomas, and Dirk C Mattfeld. 2019. Preemptive Research 54, 1 (2016), 215–231. depot returns for dynamic same-day delivery. EURO Journal on Transportation [29] Nicola Secomandi. 2001. A rollout policy for the vehicle routing problem with and Logistics 8, 4 (2019), 327–361. stochastic demands. Operations Research 49, 5 (2001), 796–802. [36] Peter JM Van Laarhoven and Emile HL Aarts. 1987. Simulated annealing. In [30] Sanket Shah, Meghna Lowalekar, and Pradeep Varakantham. 2020. Neural approx- Simulated annealing: Theory and applications. 7–15. imate dynamic programming for on-demand ride-pooling. In AAAI Conference [37] Matthew Zalesak and Samitha Samaranayake. 2021. Assignment algorithms for on Artificial Intelligence, Vol. 34. 507–515. on-demand high-capacity ridepooling. Technical Report (2021). [31] Eiichi Taniguchi and Hiroshi Shimamoto. 2004. Intelligent transportation sys- tem based dynamic vehicle routing and scheduling with variable travel times. 12 Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit Amutheezan Sivagnanam1 , Salah Uddin Kadir1 , Ayan Mukhopadhyay2 , Philip Pugliese3 , Abhishek Dubey2 , Samitha Samaranayake4 and Aron Laszka1 1 University of Houston , 2 Vanderbilt University , 3 Chattanooga Area Regional Transportation Authority , 4 Cornell University Abstract A socially beneficial application of VRPs is optimizing paratransit services [Lave and Mathias, 2000], which are Vehicle routing problems (VRPs) can be divided curb-to-curb transportation services provided by public tran- into two major categories: offline VRPs, which sit agencies for passengers who are unable to use fixed-route consider a given set of trip requests to be served, transit (e.g., passengers with disabilities). These services are and online VRPs, which consider requests as they crucial for providing transit accessibility to disadvantaged arrive in real-time. Based on discussions with pub- populations. Paratransit trips are typically booked at least one lic transit agencies, we identify a real-world prob- day in advance, which enables transit agencies to optimize lem that is not addressed by existing formulations: routes as an offline VRP: before each day, an agency can opti- booking trips with flexible pickup windows (e.g., 3 mize paratransit routes for that day based on all the requested hours) in advance (e.g., the day before) and con- pickup and drop-off locations and pickup time windows. firming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is of- However, based on discussions with public transit agen- ten required in paratransit service settings, where cies, we identified a problem that is not addressed by exist- passengers typically book trips for the next day ing VRP formulations. When passengers book trips over the over the phone. To address this gap between of- phone, they often request broad pickup windows (e.g., going fline and online problems, we introduce a novel for- for groceries in the afternoon, sometime between 2pm and mulation, the offline vehicle routing problem with 5pm). While passengers may have no preference between online bookings. This problem is very challeng- pickup times within these broad windows, they do strongly ing computationally since it faces the complexity prefer to know in advance when they will be picked up. So, of considering large sets of requests—similar to of- transit agencies must confirm a tight pickup window (e.g., 30 fline VRPs—but must abide by strict constraints on minute interval within the broad window) at the time of book- running time—similar to online VRPs. To solve ing. The reason for this is very practical: vehicles may arrive this problem, we propose a novel computational at any time within the confirmed windows, and passengers approach, which combines an anytime algorithm need to be ready to be picked up. This presents an interesting with a learning-based policy for real-time deci- online optimization problem: how to select tight pickup win- sions. Based on a paratransit dataset obtained from dows at the time of booking, based on information available our partner transit agency, we demonstrate that our at the time, assuming that vehicle routes will be optimized as novel formulation and computational approach lead an offline VRP once all the trips have been booked? to significantly better outcomes in this service set- We formulate this as the offline vehicle routing problem ting than existing algorithms. with online bookings. We assume that trip requests with broad pickup windows are received one-by-one, and for each re- quest, a tight pickup window must be selected in a matter of 1 Introduction seconds. At the end of the booking process, vehicle routes are Vehicle routing problems (VRPs) can be divided into two ma- optimized as an offline VRP based on the selected tight win- jor categories. Offline VRPs consider a set of requests at dows. The objective of optimizing the tight pickup windows once and optimize their assignment to planned vehicle routes is to minimize the cost of the resulting offline VRP. Note that [Golden et al., 2008; Laporte, 1992]. Online VRPs, on the this booking problem can be defined with respect to a wide other hand, process requests as they arrive in real-time— range of offline VRP formulations (that consider pickup win- either one-by-one or in small batches—and optimize their as- dows), so our framework could be applied to a range of real- signment to vehicle routes that may already be in progress world problems where tight pickup windows must be chosen [Toth and Vigo, 2002; Pillac et al., 2013]. While online VRPs during booking (e.g., scheduling the delivery of refrigerated typically optimize fewer requests at a time, they are subject goods or dial-a-ride services). In this paper, we consider an to stricter constraints on running time due to the online nature offline VRP formulation that models paratransit services. of the problems. This problem is very challenging computationally since Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). it faces the complexity of considering large sets of trips— corresponding dropoff Ldropoff i is also included in Rj , and ev- similar to offline VRPs—but must abide by strict limits on ery route satisfies time constraints (passengers are picked up running time—similar to online VRPs. To address this chal- within the pickup time windows, travel times between loca- lenge, we propose a novel computational approach that com- tions are respected, etc.) and vehicle capacity constraints (see bines an anytime algorithm with a reinforcement-learning Appendix B). We let R(T , w) denote the set of feasible so- based policy. We demonstrate that our novel formulation and lutions for a VRP instance (T , w). computational approach lead to significantly better outcomes The cost of a solution depends on the number of vehicle in the paratransit-booking setting than existing algorithms us- routes and the duration of each route (see Appendix B). By ing real-world data from a public transit agency. letting C(R) denote the cost of a solution R, we can express the offline VRP problem as argminR∈R(T ,w) C(R). Finally, 2 Model and Problem Formulation we let VRP∗ (T , w) denote the total cost of an optimal solu- tion for problem instance (T , w). That is, VRP∗ (T , w) = We formulate the offline VRP with online bookings by first minR ∈ R(T ,w) C(R). Since there is a vast literature on solv- introducing an offline vehicle routing problem, which models ing offline VRPs, we assume that an offline VRP solver (i.e., the optimization of allocating trip requests to vehicle routes heuristic or approximation algorithm for VRP∗ ) is given, and once all the trip requests have been booked and their tight focus on the online bookings problem in this paper. pickup windows have been confirmed. Building on this of- fline problem, we then formulate the online booking prob- 2.2 Online Bookings Problem lem, which models the optimization of tight pickup windows in real time, assuming that vehicle routes will be optimized Building on the offline VRP formulation, we now introduce afterwards. Table 1 in Appendix A provides a list of sym- the online bookings problem. In this real-time decision prob- bols [Sivagnanam et al., 2022]. lem, trip requests T1 , T2 , . . . are received one-by-one, and each trip request Ti is accompanied by a broad pickup win- 2.1 Vehicle Routing Problem with Time Windows dow Wi . Our goal is to select a tight pickup window wi ⊂ Wi Offline VRPs with time windows is a family of classical com- for each trip request Ti in real-time (i.e., in a few seconds af- binatorial problems. Here, we introduce the offline VRP for- ter the request is received), so that once we have received all mulation that we employ in our experiments, which we de- the trip requests T and selected all the pickup windows w, the veloped to model paratransit services. However, it is impor- total cost VRP∗ (T , w) of the resulting offline VRP is mini- tant to note that the online bookings problem could be defined mized. To model uncertainty and expectations about future with respect to a wide range of offline VRP formulations with requests, we assume that the sets of trip requests and broad pickup time windows, and our proposed solution approach pickup windows (T , W ) are drawn at random from a known can incorporate existing offline VRP solvers for these prob- probability distribution D (note that the number of requests is lems. Since our offline VRP is a minor variation of classical variable). So, each decision is based on previously received formulations, here we provide only a concise summary of this requests and expectation of future ones (i.e., distribution D). problem, which is sufficient for formulating the novel online Problem Input Formally, the input for the ith decision is bookings problem. Due to lack of space, we provide a full the ordered set of trip requests (including the ith request) formal definition in Appendix B [Sivagnanam et al., 2022]. ⟨T1 , . . . , Ti ⟩, the ordered set of previously selected tight Problem Input The input of the offline VRP problem is an pickup windows (up to the (i − 1)th request) ⟨w1 , . . . , wi−1 ⟩, ordered set of trip requests T = ⟨T1 , T2 , . . . , Tn ⟩, where each and a broad pickup window Wi , which specifies the earliest Wistart and latest Wiend pickup time for request Ti . The in- trip request Ti contains a pickup location Lpickup , a drop-off i put also includes the probability distribution D, the maximum location Ldropoff i , and the number of passengers to be trans- duration of tight pickup windows Dwindow (e.g., 30 minutes), ported Pi ; and a corresponding ordered set of tight pickup and any additional inputs that are required by the offline VRP time windows w = ⟨w1 , w2 , . . . , wn ⟩, where each time win- (e.g., vehicle capacity, maximum route duration); for ease of dow wi is defined by an earliest wistart and latest wiend pickup presentation, we will not list these additional inputs explicitly. time. The input also includes constants, such as the maximum allowed duration Dmaxroute of a vehicle route, the passenger Decision Space and Objective The output of the ith deci- capacity V of the vehicles, and so on (see Appendix B). For sion is a tight pickup window wi that is at most Dwindow long ease of presentation, we will not list these constants explic- (i.e., wiend − wistart ≤ Dwindow ) and falls within the broad win- itly and represent a VRP instance simply as (T , w), assuming dow (i.e., Wistart ≤ wistart ≤ wiend ≤ Wiend ). that the constants are provided implicitly. Whether a decision wi is optimal depends not only on the Solution and Objective A solution to the offline VRP received requests and on our expectation of future requests, problem is a set of vehicle routes R = {R1 , R2 , . . . , Rm }, but also on how we will respond to those future requests. Thus, instead of trying to formulate the online booking prob- where each route is an ordered set of pickups Lpickupi and lem as optimizing each decision wi , we formulate it as op- drop-offs Ldropoff i (note that trips may be combined in a route, timizing a decision-making policy µ, which maps each in- i.e., pickups and drop-offs of different trips may be inter- put (⟨T1 , . . . , Ti ⟩, ⟨w1 , . . . , wi−1 ⟩, Wi ) to a tight pickup win- leaved). A set of vehicle routes R is a feasible solution if dow wi . Formally, our goal is to find an optimal decision each pickup Lpickup i is included in exactly one route Rj , the policy µ∗ , which minimizes the expected cost of the resulting 2 Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). offline VRP instance (T , w): (achieving feasibility, but leaving all of the VRP optimization  to the anytime algorithm); we of course train our policy to argminµ E(T ,W )∼D VRP∗ (T , w) provide better solutions.  Anytime Algorithm Input and Output The input for the . ith execution of the anytime algorithm consists of the trip re- wi =µ(⟨T1 ,...,Ti ⟩,⟨w1 ,...,wi−1 ⟩,Wi ) quests ⟨T1 , . . . , Ti ⟩, the tight pickup windows ⟨w1 , . . . , wi ⟩, Since the decision problem is subject to real-time constraints and a feasible VRP solution R̂(i) , provided by the ith deci- (i.e., when someone calls over the phone to book a paratransit sion of the policy. The output of the ith execution of the any- trip, the transit agency must respond during the phone call, time algorithm is an improved feasible VRP solution R(i) , within seconds), we must be able to evaluate the policy µ∗ in provided for the (i+1)th decision of the policy. a matter of seconds for any input. The objective of the anytime algorithm α is to find a minimum-cost feasible solution for the VRP instance 3 Solution Approach (⟨T1 , . . . , Ti ⟩, ⟨w1 , . . . , wi ⟩), using the solution R̂(i) as a warm start (e.g., as initial solution for simulated annealing): 3.1 Anytime Algorithm  The online booking problem is computationally challenging R(i) = α ⟨T1 , . . . , Ti ⟩, ⟨w1 , . . . , wi ⟩, R̂(i) since it incorporates the offline VRP into its objective, which ≈ argminR ∈ R(⟨T1 ,...,Ti ⟩,⟨w1 ,...,wi ⟩) C(R). is a computationally-hard combinatorial optimization prob- lem ([Lenstra and Kan, 1981]). Indeed, existing approaches Note that the objective of the anytime algorithm does not con- for solving offline VRPs are not well suited for real-time ap- sider future requests, only ones that have been received. In plications (i.e., finding solutions within a matter of seconds). our experiments, we found that we can attain very good per- To address this challenge, we propose performing compu- formance by letting the decision policy handle expectations tation between consecutive decisions. While there is limited about future requests, and restricting the anytime algorithm time for each real-time decision, there is significantly more to optimizing for requests that have been received. time between consecutive decisions (i.e., from when a tight Optimal Decision Policy Finally, we can reformulate our window is selected to when the next request is received). We goal for the online bookings problem as finding an optimal can take advantage of this extra time by continuously work- decision policy µ∗ for selecting tight pickup windows, sup- ing on a vehicle-routing solution, which can then be used as ported by the anytime algorithm α: supporting input in the next real-time decision. h Unfortunately, the amount of time between consecutive re- argminµ E(T ,W )∼D VRP∗ (T , w) quests is not known in advance since calls arrive at random i    . times (note that the arrival time of a request is different from (i) wi ,R̂ (i−1) (i) =µ ⟨T1 ,...,Ti ⟩,⟨w1 ,...,wi−1 ⟩,Wi ,R ,R =α ... its broad pickup window). Thus, we propose to employ an anytime VRP algorithm, which we can start after each real- Note that the anytime algorithm α can be implemented using time decision and stop when the next request arrives. an existing offline VRP solver—as long as it is anytime. Anytime-supported Online Bookings Problem 3.2 Decision Policy Based on the above ideas, we reformulate our online decision We can view online bookings as a Markov deci- problem as the anytime-supported online bookings problem. sion process (MDP): a decision input (⟨T1 , . . . , Ti ⟩, Policy Input and Decision Space The input for the ith de-  ) is a state of the environment, a ⟨w1 , . . . , wi−1 ⟩, Wi , R(i−1) cision is the same as before, but now also includes a feasible decision output wi , R̂(i) is an action, and running the any- VRP solution R(i−1) (i.e., a set of routes), provided by the time algorithm until a new request arrives at random is the (i−1)th execution of the anytime algorithm, which we spec- state transition (reaching a terminal state when no more re- ify below. For ease of exposition, we define R(0) = ∅ for the quests arrive for the day). To formulate an MDP, we also very first request T1 . The output of the ith decision is also the have to define the immediate cost (i.e., immediate negative same as before, but now also includes a feasible VRP solution reward) that we incur for taking an action. The online book- R̂(i) (i.e., R̂(i) ∈ R(⟨T1 , . . . , Ti ⟩, ⟨w1 , . . . , wi ⟩), provided ings problem quantifies costs at the end of the day—after the as supporting input for the ith execution of the anytime algo- last decision—based on the total cost of the resulting offline rithm. Note that we could omit the VRP solution R̂(i) from VRP instance (T , w). Thus, the immediate cost ci incurred the output of the online decision and let the anytime algo- for the ith decision is  rithm assign the new request to a route. However, we found 0 if i < |T | that providing a feasible solution as a starting point for the ci = VRP∗ (T , w) if i = |T |. anytime algorithm is very beneficial in practice since the se- lection of the pickup window must consider anyway how the By formulating the online bookings problem as an MDP, we request will “fit” into the routes. Also note that finding a fea- enable the application of reinforcement learning (RL) to find sible VRP solution does not introduce a computational chal- an optimal decision policy µ∗ . The advantage of RL is that lenge since we can let the decision policy assign each new once a policy µ∗ has been trained, the computational cost of request to a new route and leave existing routes unchanged execution is low, which is crucial for real-time decisions. 3 Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). To find an optimal policy, an RL algorithm gathers expe- with all the trip requests T . Hence, we can use experiences riences by repeatedly interacting with the environment in a to learn a value function that estimates the expected imme- number of training episodes, recording the experienced states, diate shaped cost c̃i of a given action in a given state; once actions, and immediate costs. In our case, experiences can be the value function has been learned, our policy is to simply gathered by running simulations of the online bookings pro- choose an action that minimizes the value (i.e., cost) in the cess, where an input (T , w) is drawn at random from distribu- current state. This significantly reduces the complexity of tion D for each episode. From these experiences, an RL algo- learning and, thus, the number of experiences required. rithm can learn an optimal policy that minimizes the expected Note that during training, we can estimate shaped cost c̃i cumulative cost. Many popular RL algorithms, such as deep since we simulate the environment, so we can generate all the Q-learning (DQN) and its variants, learn a policy by learn- trip requests (T , W ) before feeding them to the policy one- ing an action-value function, which estimates the expected by-one. Once the value function has been learned, calculating cumulative cost when taking a given action in a given state the shaped cost c̃i is no longer necessary since the policy is to (e.g., using the recursive Bellman equation to consider future choose an action that minimizes the learned value (i.e., cost) costs). Once the action-value function has been learned, the function in the current state. Finally, note that calculating optimal policy is to simply choose an action that minimizes VRP∗ is computationally hard, so we can use a heuristic VRP the action-value function in the current state. solver during training to estimate shaped cost c̃i . Cost Design RL approaches face two significant challenges Value Function Since our value function considers only the in our environment. First, the total cost of the offline VRP in- immediate shaped cost c̃i , we can apply a simplified version stance depends as much on the decision inputs (e.g., on the of the popular DQN algorithm. Before applying DQN, we sheer number of trip requests) as it does on the decisions of have to discretize the action space, that is, constrain each de- the policy. Since the decision inputs are random and vary cision to a discrete set of choices (e.g., pickup times must be significantly (e.g., there are significant differences between multiples of 15 minutes). Such discretization is natural for the number of trip requests each day), experiences will be transit agencies that prefer “round” pickup times. extremely noisy and difficult to learn from. Second, simulat- Our goal is to learn the value function Q: ing the environment is very expensive computationally since  each state transition requires running the anytime algorithm Q ⟨T1 , . . . , Ti ⟩, ⟨w1 , . . . , wi−1 ⟩, Wi , R(i−1), wi , R̂(i) ≈ c̃i . | {z } | {z } for a significant amount of time (e.g., 5 minutes of running state action time to obtain a single experience). This greatly exacerbates the problem of noisy experiences since a low number of noisy Once we have learned the value function Q, our policy µ∗ is experience can lead to very inaccurate action-value functions. to iterate over the actions and select one that minimizes the To address these challenges, we replace the original imme- cost in the current state: diate cost ci of the MDP with a shaped cost c̃i , which assigns µ∗ (state) = argminwi ,R̂(i) Q(state, wi , R̂(i) ). a cost to each individual decision: c̃i =VRP∗ (T , ⟨w1 , . . . , wi−1 , wi , Wi+1 , . . . , W|T | ⟩) To enable learning, we represent Q as a neural network, which we initialize with random weights. During training, − VRP∗ (T , ⟨w1 , . . . , wi−1 , Wi , Wi+1 , . . . , W|T | ⟩). we execute our policy in simulated environments, where the The rationale behind the above formulation is to capture inputs (T , w) are drawn at random from distribution D. We the impact of narrowing down the broad window Wi to a tight collect experiences, that is, tuples of state, action, and imme- window wi in the ith decision. This shaped cost c̃i formula- diate cost, and we use these experiences to train the neural tion has two advantages. First, notice that network. As is standard in RL, we also include random ac- tions in the training to balance exploration and exploitation. |T | |T | ! X X Features Learning the value function Q poses one last chal- c̃i = ci − VRP∗ (T , W ). lenge due to the size and complexity of the state space (i.e., i=1 i=1 space of all possible decision inputs, including possible sets In other words, P the difference between the original P cumula- of requests ⟨T1 , . . . , Ti ⟩ and feasible sets of runs R(i−1) ). tive cost ci and the shaped cumulative cost c˜i is remov- While similar state spaces have been considered in prior work ing a part of the cost that does not depend on the decisions (e.g., [Joe and Lau, 2020; James et al., 2019]), the challenge (i.e., removing the cost VRP∗ (T , W ) of a “baseline” VRP in our problem is exacerbated by the prohibitively high com- instance (T , W ), where we could schedule pickups for any putational cost of the environment (one state transition may time within the broad windows W ). So, shaped costs c̃i cap- require running an anytime algorithm for 5 minutes), which ture only the impact of the decisions, thereby reducing noise. limits the number of experiences that we can collect. Second, since the shaped cost c̃i captures the impact of a To reduce the number of experiences required for training decision considering all future requests (i.e., considering the the value function, we map the large and complex space of complete ordered sets T and W ), we can use it to quantify the states and actions to a low- and fixed-dimensional space of value of a decision without taking future costs into account. feature vectors, and we replace the input of the value func- In other words, the expected impact of a decision on the total tion Q with a feature vector. Specifically, we map each state- cost VRP∗ (T , w) is captured by the immediate shaped cost c̃i action pair to a vector of features, which consider how well since this cost c̃i is the increase in the cost of the offline VRP the action fits the current state (i.e., the previously chosen 4 Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). tight windows ⟨w1 , . . . , wi−1 ⟩ and vehicle routes R(i−1) ) and agency of a mid-sized U.S. city. This dataset spans 180 days our expectation of future trip requests (i.e., distribution D). of paratransit service, with an average of 140 trips per day Features that consider how well the action (wi , R̂(i) ) fits (minimum of 7 and maximum of 234 trips). Each trip has an the previously chosen tight windows ⟨w1 , . . . , wi−1 ⟩ and ve- associated pickup and drop-off location (specified as latitude- hicle routes R(i−1) include (1) the increase in the duration of longitude pairs), the number of passengers, and the scheduled routes due to taking the action (compared between R̂(i) and pickup time. The anonymized data and our software code are available at https://github.com/smarttransit-ai/ijcai22 R(i−1) ), (2) the increase in the driving distance of routes, Based on input from the agency, we instantiate our model and (3) the “tightness” of the route schedule R̂(i) , that is, with vehicle capacity V = 9, maximum route duration how much time slack is left in the route before and after serv- Dmaxroute = 10 hours, and maximum tight pickup window du- ing trip request Ti . Features that consider the distribution D ration Dwindow = 30 minutes. Since the agency did not record include the expected number of trips requests whose pickup the requested broad windows (current over-the-phone book- locations are nearby the pickup location Lpickup i of request Ti ing process is manual), we assume each broad window Wi and/or whose drop-off locations are nearby the drop-off loca- to be 3 hours long (which is a practical value for the service) tion Ldropoff i and/or whose broad pickup windows are around and centered around the scheduled pickup time. the same time as window wi , as well as the expected num- Experimental Setup We calculate travel times between ber of future trip requests (i.e., expectation of |T | − i). For the locations using road-network data from OpenStreetMaps. any state and action, these features can be calculated at a rela- The road network contains 10,788 nodes (i.e., intersection) tively low computational cost based on historical data, which and 28,100 edges (i.e., roads). For calculating feature vec- enables real-time application. Due to lack of space, we pro- tors, we consider two locations to be nearby if they have the vide a formal description of these features in Appendix C [Sivagnanam et al., 2022]. same ZIP code. We assume that the transit agency operat- ing paratransit services must serve all the passenger requests Training Process Before we begin training, we initialize according to the Americans with Disabilities Act. the value function Q, which is represented by a neural net- We implemented our framework in Python 3.8. To pro- work, with random weights. We then train the policy µ (i.e., vide anytime algorithms, we implemented a heuristic greedy value function Q) over a number of training episodes, where αGreedy and a meta-heuristic simulated annealing algorithm each episode is a simulation of the online booking process αSimAnn , which we use in tandem as our anytime VRP solver with a random input (T , W ) drawn from the probability dis- αSimAnn+Greedy . Since these are based on standard techniques, tribution D, which we estimate based on historical data. To we describe them in Appendix D [Sivagnanam et al., 2022]. simulate the online booking process, we process the trip re- During both training and evaluation, we let the anytime algo- quests T one-by-one, first applying the decision policy µ and rithm run for 5 minutes on average. In our experiments, we then the anytime algorithm α for each request Ti . To apply consider two offline VRP solvers: VROOM and the Google the policy µ, we calculate the feature vector for every action OR-Tools Vehicle Routing framework. We do not impose a (wi , R̂(i) ), evaluate the value function Q over these feature running time limit on either VROOM or Google OR-Tools. vectors, and select the action that minimizes the value (i.e., To represent the value function Q, we use a neural network cost). Next, we run the anytime algorithm α, which provides with one input layer, one hidden layer (64 neurons, ReLU ac- supporting input for the next policy decision. We terminate tivation), and one output layer (linear activation). To train the the algorithm after a random amount of running time, which network, we use the Adam optimizer [Kingma and Ba, 2014] models the random inter-arrival time of requests (based on from the Keras library. historical data). Then, we repeat with next request Ti+1 ; or with the next episode if i = |T |. 4.2 Results After each simulated decision, we collect an experience We provide supplementary numerical results in Appendix E (i.e., a tuple of the feature vector and the shaped cost ci ) by [Sivagnanam et al., 2022]. calculating the shaped cost c̃i using T , W , ⟨w1 , . . . , wi ⟩, and a heuristic for VRP∗ . We use these experiences to train the Running Time We run all algorithms on an Intel Xeon E5- value function Q (i.e., the neural network). In the beginning, 2680 28-core CPU with 128GB of RAM. The running time the policy µ chooses actions at random since function Q is of the trained decision-making policy µ∗ , including the cal- initialized randomly; but as we train function Q using more culation of the feature vector, is 0.25 seconds on average and and more experiences, the policy improves and converges to 2 seconds in the worst case. This is sufficiently low for our an optimum µ∗ (given feature-vector inputs and objective ci ). problem setting, where we typically have a couple of sec- To balance exploration and exploitation and to avoid converg- onds to make an online decision. The running time of one ing to a local optimum, we occasionally take random actions episode of training is 1 day on average and 2 days in the during training, as is standard in RL. worst case. Note that this running time cannot be signif- icantly lowered (other than simulating multiple episodes in 4 Evaluation parallel) because the training environment has to simulate the real bookings process, where the anytime algorithm is run- 4.1 Dataset and Experimental Setup ning for the entire day. As for the offline VRP solvers, the Paratransit Data To evaluate our proposed approach, we greedy algorithm αGreedy can assign all trip requests R for obtained real-world paratransit data from the public transit a day in 15 seconds with tight pickup windows w and in 3 5 Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). 60 % Advantage of Combining Policy with Anytime Algorithm Reduction in Cost While Figure 1 demonstrates the effectiveness of our pro- 40 % posed approach, it does not prove that every element of our 20 % approach is necessary. One may wonder if a simpler approach would work equally well. To demonstrate that both the any- 0% time algorithm and the learning-based decision policy are cru- −20 % cial, we compare our complete approach to (1) using the de- cision policy µ∗ without anytime support and (2) using the 2 hours 3 hour 4 hour anytime algorithms αSimAnn+Greedy as offline VRP solvers with Broad Window Size naı̈ve pickup windows (i.e., without decision policy). Figure 2 shows the reduction in the total cost of vehicle Figure 1: Reduction in total cost due to using our approach for se- lecting tight pickup windows (policy µ∗ supported by anytime algo- routes due to using our complete approach compared to in- rithm αSimAnn+Greedy ), compared to using naı̈ve pickup windows with complete variants (1) and (2). We observe that there is a VROOM (■) and Google OR-Tools (■) as offline VRP solvers. significant reduction in cost compared to both, which demon- strates that both the learning-based decision policy µ∗ and the anytime algorithms αSimAnn+Greedy are crucial. 60 % Reduction in Cost 40 % 5 Related Work 20 % Some prior works has been focused on solving the dial-a-ride 0% problem [Berbeglia et al., 2012; Liu et al., 2015; Parragh et −20 % al., 2015; Gschwind and Irnich, 2015]. Mo et al. [2018] focus on advance booking in an offline 2 hours 3 hours 4 hours VRP. We also consider advance bookings (i.e., day before Broad Window Size the travel). De Filippo et al. [2021] consider enhancing the solution quality of offline VRP by using online algorithms Figure 2: Reduction in total cost due to using our complete ap- that can optimize the solution obtained from offline VRP proach (policy µ∗ supported by anytime algorithm αSimAnn+Greedy ), algorithms. Prior works such as [Lowalekar et al., 2019; compared to using a policy µ∗ without anytime support (■) and us- Shen et al., 2019; Alonso-Mora et al., 2017; Ota et al., 2016; ing naı̈ve pickup windows with algorithm αSimAnn+Greedy as the offline Simonetto et al., 2019; James et al., 2019; Joe and Lau, VRP solver (■). 2020] consider real-time demand. Among them, Simonetto et al. [2019] and Alonso-Mora et al. [2017] consider real- time positioning of vehicles. Gupta et al. [2010] and Wen et minutes with broad pickup windows W ; the simulated an- al. [2018] consider both real-time vehicle scheduling and ad- nealing algorithm αSimAnn performs around 30 iterations per vance booking. Simonetto et al. [2019] consider a system second; and VROOM and Google OR-Tools take around 3.3 where the agency uses idle vehicles by relaxing the time- minutes and 1 minute on average, respectively, to solve an related constraints, rather than rejecting user requests. offline VRP instance. Nguyen et al. [2019] consider a hierarchical approach by Proposed Approach vs. Naı̈ve Pickup Windows Next, we prioritizing requests. In our paratransit service setting, we demonstrate the effectiveness of our proposed approach by treat all service requests with the same priority. Simonetto showing that optimizing tight pickup windows can lead to sig- et al. [2019] assign one request to one vehicle from a given nificant reductions in cost. Since the online bookings problem batch of requests for faster real-time assignment. Goodson is novel to the best of our knowledge, existing VRP solvers et al. [2017] consider a lookahead strategy by using rollout do not address the online selection of tight pickup windows. algorithms. Joe and Lau [2020] consider a route-based MDP. Therefore, to provide baselines for comparison, we consider existing offline VRP solvers with “naı̈vely selected” pickup windows, which we define as selecting the middle interval of 6 Conclusion broad pickup windows as tight windows. Optimizing pickup windows during day-ahead trip booking Figure 1 shows the reduction in the total cost of vehicle can be crucial for offline VRPs (e.g., paratransit service ap- routes due to using our proposed approach, compared to using plications). In this paper, we propose a novel problem for- VROOM and Google OR-Tools with naı̈vely selected pickup mulation to capture offline VRPs with online bookings. We windows. For each comparison, we evaluate the algorithms also introduce a novel computational approach that combines on 180 days of paratransit data, and plot the distributions. a learning-based policy with an anytime algorithm. Based We observe a significant reduction in costs compared to both on experiments with real-world paratransit data, we observe baseline solvers. Further, we find that our approach is robust a significant reduction in costs due selecting pickup windows to variations in the duration of broad pickup windows since using our decision policy instead naı̈ve selection. Further, our it maintains a significant advantage when broad windows are experiments also show a reduction of 14 - 18% in costs due to 2- or 4-hours long, even though the decision policy µ∗ was using our policy in tandem with an anytime algorithm instead trained only on 3-hour broad windows. of using the policy by itself. 6 Accepted for publication in the proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). Acknowledgements [Lave and Mathias, 2000] Roy Lave and Rosemary Mathias. This material is based upon work sponsored by the National State of the art of paratransit. Transportation in the New Science Foundation under grant CNS-1952011 and by the Millennium, 478:1–7, 2000. Department of Energy under Award Number DE-EE0009212. [Lenstra and Kan, 1981] Jan Karel Lenstra and AHG Rin- nooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227, 1981. References [Liu et al., 2015] Mengyang Liu, Zhixing Luo, and Andrew [Alonso-Mora et al., 2017] Javier Alonso-Mora, Samitha Lim. A branch-and-cut algorithm for a realistic dial-a-ride Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela problem. Transportation Research Part B: Methodologi- Rus. On-demand high-capacity ride-sharing via dynamic cal, 81:267–288, 2015. trip-vehicle assignment. Proceedings of the National [Lowalekar et al., 2019] Meghna Lowalekar, Pradeep Academy of Sciences, 114(3):462–467, 2017. Varakantham, and Patrick Jaillet. ZAC: A zone path [Berbeglia et al., 2012] Gerardo Berbeglia, Jean-François construction approach for effective real-time ridesharing. Cordeau, and Gilbert Laporte. A hybrid tabu search In 29th International Conference on Automated Planning and constraint programming algorithm for the dynamic and Scheduling, volume 29, pages 528–538, 2019. dial-a-ride problem. INFORMS Journal on Computing, [Mo et al., 2018] Daniel Y Mo, Yue Wang, YCE Lee, and 24(3):343–355, 2012. Mitchell M Tseng. Mass customizing paratransit services [De Filippo et al., 2021] Allegra De Filippo, Michele Lom- with a ridesharing option. IEEE Transactions on Engineer- bardi, and Michela Milano. Integrated offline and online ing Management, 67(1):234–245, 2018. decision making under uncertainty. Journal of Artificial [Nguyen et al., 2019] Quoc Chinh Nguyen, Liuqin Yang, Intelligence Research, 70:77–117, 2021. Zhuolun Li, and Wenqing Chen. Hierarchical vehicle rout- [Golden et al., 2008] Bruce L Golden, Subramanian Ragha- ing for online delivery platform. In 22nd IEEE Intelligent van, and Edward A Wasil, editors. The vehicle routing Transportation Systems Conf., pages 1709–1714, 2019. problem: latest advances and new challenges, volume 43. [Ota et al., 2016] Masayo Ota, Huy Vo, Claudio Silva, and Springer, 2008. Juliana Freire. Stars: Simulating taxi ride sharing at scale. [Goodson et al., 2017] Justin C Goodson, Barrett W IEEE Transactions on Big Data, 3(3):349–361, 2016. Thomas, and Jeffrey W Ohlmann. A rollout algorithm [Parragh et al., 2015] Sophie N Parragh, Jorge Pinho de framework for heuristic solutions to finite-horizon Sousa, and Bernardo Almada-Lobo. The dial-a-ride prob- stochastic dynamic programs. European Journal of lem with split requests and profits. Transportation Science, Operational Research, 258(1):216–229, 2017. 49(2):311–334, 2015. [Gschwind and Irnich, 2015] Timo Gschwind and Stefan Ir- [Pillac et al., 2013] Victor Pillac, Michel Gendreau, Chris- nich. Effective handling of dynamic time windows and its telle Guéret, and Andrés L Medaglia. A review of dy- application to solving the dial-a-ride problem. Transporta- namic vehicle routing problems. European Journal of Op- tion Science, 49(2):335–354, 2015. erational Research, 225(1):1–11, 2013. [Shen et al., 2019] Bilong Shen, Bo Cao, Ying Zhao, Haojia [Gupta et al., 2010] Diwakar Gupta, Hao-Wei Chen, Lisa A Zuo, Weimin Zheng, and Yan Huang. Roo: Route plan- Miller, and Fajarrani Surya. Improving the efficiency of ning algorithm for ride sharing systems on large-scale road demand-responsive paratransit services. Transport. Re- networks. In 6th IEEE International Conference on Big search Part A: Policy and Practice, 44(4):201–217, 2010. Data and Smart Computing (BigComp), pages 1–8, 2019. [James et al., 2019] JQ James, Wen Yu, and Jiatao Gu. On- [Simonetto et al., 2019] Andrea Simonetto, Julien Monteil, line vehicle routing with neural combinatorial optimiza- and Claudio Gambella. Real-time city-scale ridesharing tion and deep reinforcement learning. IEEE Trans. on In- via linear assignment problems. Transportation Research telligent Transport. Systems, 20(10):3806–3817, 2019. Part C: Emerging Technologies, 101:208–232, 2019. [Joe and Lau, 2020] Waldy Joe and Hoong Chuin Lau. Deep [Sivagnanam et al., 2022] Amutheezan Sivagnanam, reinforcement learning approach to solve dynamic vehicle Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, routing problem with stochastic customers. In 30th Inter- Abhishek Dubey, Samitha Samaranayake, and Aron national Conference on Automated Planning and Schedul- Laszka. Offline vehicle routing problem with online ing (ICAPS), volume 30, pages 394–402, 2020. bookings. arXiv preprint arXiv:2204.11992, 2022. [Kingma and Ba, 2014] Diederik P Kingma and Jimmy Ba. [Toth and Vigo, 2002] Paolo Toth and Daniele Vigo. The ve- Adam: A method for stochastic optimization. arXiv hicle routing problem. SIAM, 2002. preprint arXiv:1412.6980, 2014. [Wen et al., 2018] Jian Wen, Yu Xin Chen, Neema Nas- [Laporte, 1992] Gilbert Laporte. The vehicle routing prob- sir, and Jinhua Zhao. Transit-oriented autonomous vehi- lem: An overview of exact and approximate algorithms. cle operation with integrated demand-supply interaction. European Journal of Operational Research, 59(3):345– Transportation Research Part C: Emerging Technologies, 358, 1992. 97:216–234, 2018. 7 Offline Paratransit Vehicle Scheduling via Rolling Horizon Optimization Youngseo Kim1 , Danushka Edirimanna1 , Michael Wilbur2 , Philip Pugliese4 , Aron Laszka3 , Abhishek Dubey2 , and Samitha Samaranayake1 Abstract— Paratransit scheduling is an offline Dial-a-Ride the fixed time horizon and solves a sequence of much smaller problem that is challenging to solve exactly. Many heuristics optimization problems. However, a purely online approach have been developed to make the problem tractable. We has an innate limitation of being myopic because it makes focus on one such strategy of decomposing the problem in time and solving a sequence of much smaller problems. This greedy vehicle dispatching decisions with restricted infor- allows the utilization of new online optimization techniques mation in each batch. Therefore, in this paper, we propose a developed in the context of demand-responsive shuttle systems. rolling horizon framework that considers a sliding window However, a purely online approach has the innate limitation of of larger time intervals and utilizes more information (from being myopic—ignoring knowledge about the future. Thus, we the offline problem instance), while still limiting the com- introduce a rolling horizon framework that provides a better trade-off between computational efficiency and solution quality. putational cost. In the limit of the sliding window being the Based on real-world data from a partner transit agency, our entire time horizon, theoretically, the solution is equivalent results show that the rolling horizon framework can outperform to one obtained from a purely offline solver, however, this is a purely online approach while still being computationally computationally intractable. The rolling horizon framework tractable. Our framework increases the service rate of the with an appropriate time horizon provides a desired tradeoff entire system by up to 9.5% compared to the purely online approach. Additional experiments using New York City taxi between computational efficiency and solution quality. data sampled with an average of 129 requests per day, the A major highlight of our approach is its flexibility and ease results show our framework is as competitive as benchmark of generalization. Our framework can be easily modified to offline algorithm using Google OR-Tools. We also show that add physical or performance-related constraints. To the best our framework is scalable to approximately 2,500 requests per of our knowledge, as we discuss in Section II-B, alternative day while the benchmark algorithm cannot find any feasible solution with a compute time budget of one second per request. approaches in the literature do not provide this level of generalizability. A recent survey paper [1] also pointed out this research gap, and encouraged the development of I. INTRODUCTION techniques that can be adapted to solve the many variants of Paratransit is a service provided by public transit agencies the Dial-a-Ride problem. for passengers who are unable to use fixed-route transit, as II. LITERATURE REVIEW mandated by the Americans with Disabilities Act (ADA). Due to the large costs associated with operating paratransit A. Pickup and delivery problem with time windows services, transit agencies are constantly looking to improve The paratransit vehicle scheduling problem is a variant service efficiency and provide a high level of service at a of dial-a-ride problem (DARP). In particular, the paratransit lower cost. Customers book paratransit trips either by phone problem is typically an offline optimization problem because or via an app, and can make a reservation as early as two most service providers require reservations to be made by weeks in advance or within a few days of travel. Customers the end of the previous business day, with a few exceptions are given a confirmation of travel with an estimated pickup allowing reservations to be placed during the service day. and drop-off time shortly after the booking request. The DARP is a special case of an offline multi-vehicle pickup and service is required to provide a tight pickup time and drop- delivery problem with time windows (M-PDPTW) and side off window, typically around 30 minutes. Some paratransit constraints. A comprehensive survey of DARPs developed services allow customers to request trips in real time, but up to 2007 is reported by Ropke, Cordeau, and Laporte [2]. service is not guaranteed for these trips. Another survey from 2007 to 2018 is reported by Ho, Szeto, The paratransit day-ahead vehicle scheduling problem is Kuo, et al. [1]. NP-hard, and in general, finding optimal solutions to the B. DARP variants for real-world application problem is computationally intractable in real-world problem instances. Many heuristics and metaheuristics have been Most previous literature motivated by real-world applica- developed to solve real-world scale problems. In this context, tions has addressed various realistic features. For example, we utilize an online optimization technique that decomposes in paratransit service, user convenience metrics (e.g., total ride time, user waiting time, pickup/dropoff time window) 1 Cornell University, Ithaca NY, United States are required to be met by the ADA. In that sense, waiting 2 Vanderbilt University, Nashville TN, United States 3 University of Houston, Houston TX, United States time and detour constraints are required to be hard con- 4 Chattanooga Area Regional Transportation Authority, Chattanooga TN, straints (e.g., 30 minutes in most cases) in the optimization United States model. Another consideration in practice is vehicle and TABLE I: Literature for DARP variants (published after 2018) Single (S) Single (S) Single (S) Single (S) Vehicle Time Ride Route Selective Static(S) Stoch.(S)b /Multi (M) /Multi (M) /Multi (M) Fleet /Multi (M) capacity windows time duration visits /Dyn.(D)a /Det.(D)c depots trips vehicles objectives [3] S S M HE ✓ ✓ ✓ S S D [4] S M M HO ✓ ✓ M D D [5] M S M HE ✓ ✓ ✓ S S D [6] S M M HE ✓ ✓ ✓ ✓ M S D [7] M M M HE ✓ ✓ ✓ ✓ S S D [8] M S M HO ✓ ✓ ✓ ✓ ✓ S D S [9] M S M HE ✓ ✓ ✓ ✓ S S D [10] S S M HO ✓ ✓ ✓ ✓ S S D a Abbreviation for dynamic, b Abbreviation for stochastic, c Abbreviation for deterministic passenger heterogeneity. Service providers are required to 11) Dynamic allowing dynamic modification of existing plans serve different types of passengers with various equipment in response to new information. (e.g., wheelchairs and stretchers). Qu and Bard solved the DARP with vehicle configuration, i.e., how to compose C. Solution methods for DARP equipment and capacities of vehicle [11]. Tellez, Vercraene, Different solution approaches have been proposed to solve Lehuédé, et al. added further complexity on this problem DARP and its variants. The vast majority of exact algorithms by considering en-route reconfiguration [5]. Dynamic DARP are developed using techniques such as branch-and-cut [2], has also been studied for realistic settings to deal with the [15], branch-and-price [16], and branch-and-price-and-cut appearance of new requests, cancellations/no show, delays [17]. Exact methods are unable to solve large instances from congestion or unexpected events. Previous literature within a reasonable time due to the intrinsic hardness of suggested methods to modify existing plans in response to DARPs. According to the survey [1], the largest instance new information received after the start of the operation that has been solved via an exact method was a basic DARP [8], [12]–[14]. Including features that we have discussed, instance with 8 vehicles and 96 requests. Furthermore, the all other typical features that have been considered in DARP largest solvable instance size gets smaller for more complex variants are listed below. variants of the problem. Heuristics and metaheuristics are the most common ap- 1) Multi vehicle utilizing multiple vehicles. proaches for solving real-world scale instances. These meth- 2) Multi depots multiple starting and ending locations for ods include insertion based heuristics [18], [19], tabu search the vehicle fleet. [20], [21], simulated annealing [22], variable neighborhood 3) Multi trips allowing a vehicle to return to a depot multiple search [23], large neighborhood search [24], and genetic times in a single day. algorithms [25]. It is hard to compare performance among 4) Heterogeneous fleet various combinations of equipment these algorithms due to the articles considering different for different types of passengers. problem variants as well as different benchmark instances 5) Vehicle capacity limiting the maximum number of pas- of different sizes. sengers. 6) Time window user-specified earliest and latest time bound D. Ease of integration for pick-up and drop-off.1 7) Ride time limiting the maximum time a user spends in a To the best of our knowledge, the existing literature does vehicle (i.e., the difference between the scheduled pickup not focus on methods that are general enough to consider all and dropoff time). the typical features of the DARP variants. Ho, Szeto, Kuo, 8) Route duration limiting the maximum time that a vehicle et al. conducted a comprehensive literature review with the can be deployed with the same driver (i.e., the difference same criteria for papers published before 2018 (see Table between the times of leaving from and returning to a 5-8 in their paper [1]) and we provide an extended table depot). for papers published after 2018 in Table I. All of these 9) Selective service allowing selective pickups and deciding features can be accommodated by our framework. Some which requests to accommodate. portion of this flexibility stems from the online optimiza- 10) Multiple objectives objective functions consisting of mul- tion framework from [26] that our approach is being built tiple measures. upon. This framework decomposes the high-capacity vehicle- passenger matching problem into a routing problem and an assignment problem, and develops heuristics for effectively 1 Although our framework does not explicitly have the concept of the time computing feasible routes. This gives room for introduc- window, inputs of our model can translate to time windows. Desired pickup ing considerations for variants because adding complexity time/earliest drop-off time corresponds to the start of the time window. Then, the end of the time window can be set by adding maximum waiting into the decomposed problem is easier than its original time/detour time. Definition of the inputs can be found in Section III-A. problem. Our extension of this framework with a rolling 2 horizon approach allows us to solve a sequence of tractable iteration. To track requests that were picked up, we store optimization problems. Furthermore, it provides us with a Pv,t , a list of passengers for vehicle v ∈ V until time t. unified framework that can also deal with online dispatching Then, we solve the matching problem RTV-ILP between decisions because we can use the same framework which the active request set R̂ and the vehicle set V. As a result, is used the planning stage. Given a solution obtained in the we obtain (vj , [r1 , ..., rk ]) ∈ Assignments, a set of tuples planning stage, we can execute periodic re-optimization to of a vehicle and a list of scheduled visits by order. Then, update the solution based on new operational information, in SimulateVehicle is executed to finalize the routes until the real time. The only changes are that 1) the current state is current simulation time. As a result of vehicle simulation, defined by real-world data which is obtained in real time and we get a set of vehicle routes until time t, Rt . The finalized 2) we prioritize pre-planned trips to ensure service reliability. routes in the current iteration cannot be changed in the next iterations. We will describe batch processing and RTV-ILP III. M ETHODOLOGY in more detail in the following sections. A. Problem input and output An input of our model is a set of vehicles V = {v1 , ..., vm } Algorithm 1: DayAheadScheduling(R, V) with a fixed vehicle specific capacity. Another input of the t←0 model is a set of requests R = {r1 , ..., rn }, where each R̂ ← ∅ request rk contains a pickup and drop-off location, and while t < tmax do desirable pickup time t̂pickup k . Based on the pickup and drop- R̂ ← R̂ ∪ BatchProcessing(t) off location, we calculate t̂dropoff k , the earliest possible drop-off Assignments ← RTV-ILP(R̂, V) time, by adding estimated travel time to the desirable pickup Pv∈V,t , Rt ← SimulateVehicle(Assignments, t) time. The other inputs are constants, which are maximum for v ∈ V do allowed delay time Dmax and waiting time Wmax of R̂ ← R̂ \Pv,t customers. Rolling horizon factor cRH is also given as a end constant, which is defined as how many intervals we look t ← t + ∆t ahead for the future. When multiplying cRH by the length of end interval ∆t, we obtain the look ahead time which is defined Result: R as the time length we consider beyond the current simulation time. The output of the model is a set of vehicle routes 1) Batch processing: the procedure for selecting a set R = {R1 , R2 , ..., Rm }, where each route is an ordered set of requests to be considered, R̃. Algorithm 2 demonstrates of pickup and drop-off locations. batch processing in the rolling horizon framework where we select requests based on the desired pickup time. B. Computational approach Figure 1 illustrates batch processing, the process by which Algorithm 2: BatchProcessing(t) a solver completes batches of optimization problems in sequential order, for both the online and rolling horizon R̃← ∅ frameworks. In both frameworks, an optimization problem if t == 0 then is solved at each time step to determine the best passenger- for rk ∈ R do vehicle matching and to plan for the vehicle schedule over if PickupTime(rk ) ≤ cRH × ∆t then a fixed time horizon. After solving an optimization problem R̃ ← R̃ ∪ {rk } for the first batch, vehicle simulation runs to finalize the end schedule until the end of the current simulation time. In end the next batch, we solve another optimization problem in end a new batch interval which is shifted one step forward. else The online approach is a purely greedy approach because for rk ∈ R do its batch intervals include only those requests that have if PickupTime(rk ) ≤ (t + cRH × ∆t) already entered the system. In contrast, the rolling horizon ∧PickupTime(rk ) > (t + cRH − 1) × ∆t framework considers batch intervals that are extended to the then future. R̃ ← R̃ ∪ {rk } end C. Problem formulation and algorithm end Algorithm 1 shows the overview of our day-ahead para- end transit scheduling problem, or DARP. The algorithm follows Result: R̃ an iterative process. In each batch, an optimization problem considers active request set R̂(⊂R). New requests obtained 2) RTV-ILP: integer linear programming (ILP) for assign- from BatchProcessing are added to the active requests set. ment problem upon Request-Trip-Vehicle (RT-V) graph. We Also, requests that have been picked up by any vehicle strongly recommend readers to refer the paper by Alonso- were deleted in the active request set at the end of each Mora, Samaranayake, Wallar, et al. for more detail [26]. 3 Fig. 1: Batch processing in (a) online framework (b) rolling horizon framework (example when rolling horizon factor is 3) ignored requests. Thus, objective function maximizes service rate and minimizes the total delays. Equation 4 guarantees that a vehicle is assigned to at most one trip. Equation 5 imposes that each request should be either served by a vehicle or ignored. X X argmin cij ϵij + ck χk (3) ϵij ,χk {ij:ϵij ∈ET V } k∈R X s.t. ϵij ≤ 1 , ∀vj ∈ V (4) {i:Ti ∈T } X X Fig. 2: RT-V graph for an example instance (reconstructed ϵij + χk = 1 , ∀rk ∈ R (5) from the schematic figure in Alonso-Mora, Samaranayake, {i:Ti ∈T } {j:Vj ∈V} Wallar, et al.’s work) IV. E XPERIMENTAL D ESIGN Requests R are aggregated into trips T if a vehicle can serve the requests within a desirable service level. RT- We obtained data from two different sources for experi- V graph in Figure 2 contains all possible candidate pairs ments. First, we used paratransit trip requests data provided between trip and vehicle, ET V . An existence of the edge by a public transit agency. Second, we used New York City between a trip Ti ∈ T and a vehicle vj ∈ V, means that taxi data to investigate the scalability of our approach on a it is feasible for the vehicle j to serve all requests in the larger dataset. We provide two baselines. The first baseline is trip Ti . For constructing an edge, an optimization problem is a fully online solver while the second baseline is an offline solved to minimize delays of a trip while serving all requests heuristic solver. and satisfying constraints in Equation 1 and 2, then store the A. Data description objective value as a weight of an edge. The constraints ensure waiting time to be not greater than maximum Wmax and An overview of the two datasets is provided in Table II. delay time to be not greater than maximum delay time Dmax . tpickup denotes actual pickup time and tdropoff denotes actual TABLE II: Overview of Datasets k k drop-off time. Since this routing problem is a pickup and CARTA NYC NYC Scenario 1 Scenario 2 delivery problem with time windows, it is still hard to solve Number of Days 30 31 31 and an insertion based heuristic is used. Mean Requests Per Day 172 129 2587 Std. Dev. Requests Per Day 33 29 570 tpickup k − t̂pickup k ≤ Wmax , ∀k (1) 1) Real-world paratransit data (CARTA): We used 6 tdropoff − t̂dropoff ≤ Dmax , ∀k (2) k k months of paratransit trip requests between January 1, 2021 After building the RT-V graph, we need to solve an ILP and June 30, 2021. The data is provided by our partner to obtain the optimal matching. Decision variables ϵij and agency, the Chattanooga Area Regional Transportation Au- χk are binary. If vehicle j is assigned to trip Ti , ϵij = 1; thority (CARTA), a mid-sized public transit agency in the Otherwise, ϵij = 0. If the request rk cannot be served by United States. As this dataset is directly from an operating any vehicle, χk = 1; Otherwise, χk = 0. In the objective transit agency, we use it to show the performance of our function, there is cost cij which is the sum of delays for approach on real-world data. Each trip request contains trip Ti served by vehicle vj and the value stored in the pickup and dropoff location and requested pickup time. For corresponding edge. ck is a large enough constant to penalize privacy, the requests were aggregated by CARTA in 15 4 minute intervals. We randomly selected 30 weekdays for an so as to deal with the NYC data which is larger than the experiment. There were an average of 172 trip requests per previous dataset. Likewise, we can make batch intervals even day in this dataset. smaller to deal with larger demand. One caveat is that the 2) New York City taxi data: Recall that a primary ad- decreasing length of the interval may lead decisions in each vantage of our approach is its ability to scale to a large batch to become more myopic and deteriorate the solution number of requests. To test this, we acquired 31 days of quality. taxi trip requests (January 1, 2016 to January 30, 2016) for New York City [27]. To better represent paratransit trips, we C. Metrics deleted short-distance trips which are less than 5 km. For each day, we calculate three metrics to evaluate the As shown in Table IV, we randomly sampled 1% and 20% performance of our approach compared to the baselines. of the NYC taxi data to generate two new paratransit datasets Service rate is the number of requests served divided by for our investigation. The 1% sample had an average of 129 the total number of requests in a day. The compute time per trips per day which is similar to the CARTA dataset. The request is the total time the solver takes to run for a day 20% dataset had an average of 2,587 requested trips per day divided by the number of requests on that day. The average and was used to investigate the scalability of our approach. delay time is the average time difference between the actual We refer to the 1% sampled data as Scenario 1 and the 20% dropoff time and the earliest possible dropoff time that is sampled data as Scenario 2. calculated by adding shortest travel time to the requested pickup time. B. System parameters D. Baselines TABLE III: Parameter settings for CARTA dataset Our approach provides an efficient, tune-able approach that provides a better trade-off between computational ef- Parameter Values Fleet size 3, 4, 5, 6, 7 ficiency and solution quality. To investigate this trade-off, Vehicle capacity 8 we implement a fully online, myopic solution and a fully Maximum waiting time 30 (min) offline heuristic solver. Maximum delay time 30 (min) 1) Online Solver: We use our own approach with a rolling Dwell time 10 (min) Batch interval 15 (min) horizon factor of 0 to represent the online solver. By setting the rolling horizon factor to 0, our solver is simplified to a purely online approach as it does not utilize future TABLE IV: Parameter settings for New York City dataset knowledge. We refer to this baseline as RH0 comparing to our approach RH1, RH2, RH3, which used rolling horizon Parameter Scenario 1 Scenario 2 factor of 1, 2, 3, respectively. Data 1% sampled 20% sampled 2) Offline Solver: An offline VRP benchmark solver Fleet size (M ) 3, 4, 5, 6 30, 40, 50, 60 Batch interval 5 (min) 5 (min) utilizes a heuristic using guided local search (GLS) [28] RH factor 0,1,2,3 0,1,2,3 implemented in Google OR-Tools, the commonly used open source VRP solver [29]. Guided local search is an anytime We identified parameter settings based on discussion with algorithm, i.e., provide the best solution it can find in a given the public transit agency, which are shown in Table III. We time budget. We set the maximum computation time for a vary the number of vehicles from 3 to 7 and each vehicle given day to be one second per request. In other words, the can accommodate up to 8 passengers at a time. Maximum time-out is set to the number of requests in a day in seconds. waiting time is defined as the time difference between actual We refer to this baseline as GLS. pickup time and desirable pickup time which is set to 30 E. Reproducibility minutes. The maximum delay time is defined as the time difference between the actual dropoff time and the earliest Our implementation and samples of the datasets are avail- possible dropoff time and is also set to 30 minutes. In able online: https://github.com/MAS-Research/ practice, our partner agency set the same goal of the service RollingHorizon.git levels. On average, our partner agency plans for 5-10 minutes V. R ESULTS to load/unload a passenger, thus we conservatively set dwell time to 10 minutes. We set batch interval to 15 minutes, A. Evaluation on CARTA paratransit dataset which is the minimum interval that we can use because time The service rate per day for the 30 experimental days is information in original data was aggregated by 15 minutes. provided in Figure 3. Overall, our framework (RH1, RH2, The parameter settings for the NYC taxi investigation are RH3) outperforms the online approach (RH0). In an exper- provided in Table IV. For scenario 1 we vary the fleet size iment with 7 fleets, RH3 brings an increase in service rate from 3 to 6 vehicles while for scenario 2 we investigate fleet from 84.2% to 92.2% compared to RH0, which corresponds sizes of 30, 40, 50, and 60. The vehicle capacity is again set to a 9.5% increase. We observe that the slope of the service to 8. Due to the higher frequency of trip requests, we set the rate is reduced as the rolling horizon factor increases. This is batch interval to 5 minutes instead of 15 minutes interval because future information has a more significant impact on 5 RH0 RH1 RH2 RH3 RH0 RH1 RH2 RH3 900 Average Delay Time (sec) 100 % 80 % 800 60 % 700 40 % 600 3 4 5 6 7 3 4 5 6 7 Number of Vehicles Number of Vehicles Fig. 3: Service rate evaluated on the CARTA paratransit Fig. 5: Average delay time of customers evaluated on the dataset. CARTA dataset. RH0 RH1 RH2 RH3 that of GLS within less than a quarter of the computational time of GLS as shown in Figure 8. Also, the average delay 1.5 time from the rolling horizon framework was smaller than that of GLS, which would lead to better user experiences. 1 The results of scenario 2 highlight the scalability of our framework. Recall that the number of requests in scenario 0.5 2 is 20 times larger than that of scenario 1. While the GLS could not get any feasible solution within the given time 0 limit, our framework achieves the solution within 1 second. In the rolling horizon framework, the increases in look ahead 3 4 5 6 7 time are restricted, because the computation time explodes Number of Vehicles as the rolling horizon factor increases. We couldn’t get the Fig. 4: Computation time per request evaluated on the result of RH3 within the time limit as in Figure 9, thus the CARTA dataset. reasonable rolling horizon factor in this setting would be 2. Likewise, in practice, operators can decide a proper look- ahead time by considering how much time they can spend current decisions when the events are imminent. However, for computation. computational time exponentially increases as we increase VI. CONCLUSIONS the rolling horizon factor as in Figure 4. In practice, operators can decide a proper look-ahead time by trading off between Paratransit day-ahead scheduling problem is NP-hard, and desirable service rate and allowable computation time. Lastly, several considerations in practice make the problem even Figure 5 shows that passengers would experience longer ride more complicated. Our framework breaks down the original times due to detours caused by higher service rates. However, NP-hard problem into tractable problems by using two the delay times are still within half of the maximum delay different techniques. First, our framework building upon the time. RTV graph decomposes the high-capacity vehicle-passenger matching problem into a routing problem and an assignment B. Evaluation of NYC datasets: scenario 1 and scenario 2 problem. Second, we discretize the time horizon and solve The results of scenario 1 show that the performance of the smaller problems in each batch. Then, we resolve the myopic rolling horizon framework is as good as that of GLS. GLS is limitation of the online approach by the rolling horizon an anytime algorithm from which we obtain the best among framework that considers extended batch interval with a the solutions that have been found within a time limit, which sliding window. These two techniques make our approach is the reason why the computation time of GLS is exactly 1 flexible as well as scalable. second. We obtain the best solution in terms of the service We show the performance of our framework in different rate of GLS after the given time limit. The mean of the scales of networks. In real-world size instances, we show service rate of our framework increases as the rolling horizon that the rolling horizon framework performs better than a factor increases and it has a saturation point in all vehicle purely online approach in terms of service rate and level of columns as in the previous experiment. The saturation points service. The performance of the rolling horizon framework are close to or even exceed the service rates of GLS as shown is as high as that of the benchmark offline solver with in Figure 6. This indicates that the rolling horizon framework better computational efficiency. Moreover, our framework obtains good enough solution quality which is comparable to can be scaled up to around 2,500 requests per day while the 6 RH0 RH2 RH4 RH6 GLS RH0 RH1 RH2 100 % 100 % 80 % 80 % 60 % 60 % 40 % 40 % 3 4 5 6 30 40 50 60 Number of Vehicles Number of Vehicles Fig. 6: Service rate evaluated on NYC dataset, Scenario 1. Fig. 7: Service rate evaluated on NYC dataset, Scenario 2. RH0 RH2 RH4 RH6 GLS RH0 RH1 RH2 1 1 0.8 0.6 0.5 0.4 0.2 0 0 3 4 5 6 30 40 50 60 Number of Vehicles Number of Vehicles Fig. 8: Compute time, NYC dataset-Scenario 1. Fig. 9: Compute time, NYC dataset-Scenario 2. RH0 RH2 RH4 RH6 GLS RH0 RH1 RH2 1,500 1,500 Average Delay Time (sec) Average Delay Time (sec) 1,000 1,000 500 500 0 3 4 5 6 30 40 50 60 Number of Vehicles Number of Vehicles Fig. 10: Delay time, NYC dataset-Scenario 1. Fig. 11: Delay time, NYC dataset-Scenario 2. benchmark solver cannot find any feasible solution within vehicles from multiple depots and drivers on different shifts. the time limit. Our framework can be continuously used for Also, it is trivial to consider any real-world considerations, paratransit operations keeping up with the service expansion. such as heterogeneous fleets or several types of users. Hence, Other than performance and scalability, flexibility is another including more real-world constraints to make the suggested important aspect of our framework. We can consider real-life planner as close to real life would be worthwhile to receive situations of paratransit operation. We have hard constraints future attention. in the level of service attributes, i.e., maximum waiting time and detour time of customers. Our framework considers 7 R EFERENCES [18] Y. Luo and P. Schonfeld, “A rejected-reinsertion heuristic [1] S. C. Ho, W. Y. Szeto, Y.-H. Kuo, J. M. Leung, M. Petering, for the static dial-a-ride problem,” Transportation Research and T. W. Tou, “A survey of dial-a-ride problems: Literature Part B: Methodological, vol. 41, no. 7, pp. 736–755, 2007. review and recent developments,” Transportation Research [19] L. Häme, “An adaptive insertion algorithm for the single- Part B: Methodological, vol. 111, pp. 395–421, 2018. vehicle dial-a-ride problem with narrow time windows,” [2] S. Ropke, J.-F. Cordeau, and G. Laporte, “Models and European Journal of Operational Research, vol. 209, no. 1, branch-and-cut algorithms for pickup and delivery problems pp. 11–22, 2011. with time windows,” Networks: An International Journal, [20] D. Kirchler and R. W. Calvo, “A granular tabu search algo- vol. 49, no. 4, pp. 258–272, 2007. rithm for the dial-a-ride problem,” Transportation Research [3] M. A. Masmoudi, M. Hosny, E. Demir, K. N. Genikomsakis, Part B: Methodological, vol. 56, pp. 120–135, 2013. and N. Cheikhrouhou, “The dial-a-ride problem with electric [21] P. Detti, F. Papalini, and G. Z. M. de Lara, “A multi- vehicles and battery swapping stations,” Transportation re- depot dial-a-ride problem with heterogeneous vehicles and search part E: logistics and transportation review, vol. 118, compatibility constraints in healthcare,” Omega, vol. 70, pp. 392–420, 2018. pp. 1–14, 2017. [4] H. R. Sayarshad and H. O. Gao, “A scalable non-myopic [22] K. Braekers, A. Caris, and G. K. Janssens, “Exact and meta- dynamic dial-a-ride and pricing problem for competitive on- heuristic approach for a general heterogeneous dial-a-ride demand mobility systems,” Transportation Research Part C: problem with multiple depots,” Transportation Research Part Emerging Technologies, vol. 91, pp. 192–208, 2018. B: Methodological, vol. 67, pp. 166–186, 2014. [5] O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, and T. [23] S. N. Parragh, K. F. Doerner, and R. F. Hartl, “Variable Monteiro, “The fleet size and mix dial-a-ride problem with neighborhood search for the dial-a-ride problem,” Computers reconfigurable vehicle capacity,” Transportation Research & Operations Research, vol. 37, no. 6, pp. 1129–1138, 2010. Part C: Emerging Technologies, vol. 91, pp. 99–123, 2018. [24] S. Ropke and D. Pisinger, “An adaptive large neighbor- [6] Z. Luo, M. Liu, and A. Lim, “A two-phase branch-and-price- hood search heuristic for the pickup and delivery problem and-cut for a dial-a-ride problem in patient transportation,” with time windows,” Transportation science, vol. 40, no. 4, Transportation Science, vol. 53, no. 1, pp. 113–130, 2019. pp. 455–472, 2006. [7] C. Bongiovanni, M. Kaspi, and N. Geroliminis, “The electric [25] R. M. Jorgensen, J. Larsen, and K. B. Bergvinsdottir, autonomous dial-a-ride problem,” Transportation Research “Solving the dial-a-ride problem using genetic algorithms,” Part B: Methodological, vol. 122, pp. 436–456, 2019. Journal of the operational research society, vol. 58, no. 10, [8] X. Liang, G. H. de Almeida Correia, K. An, and B. van pp. 1321–1331, 2007. Arem, “Automated taxis’ dial-a-ride problem with ride- [26] J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, sharing considering congestion-based dynamic travel times,” and D. Rus, “On-demand high-capacity ride-sharing via dy- Transportation Research Part C: Emerging Technologies, namic trip-vehicle assignment,” Proceedings of the National vol. 112, pp. 260–281, 2020. Academy of Sciences, vol. 114, no. 3, pp. 462–467, 2017. [9] I. Malheiros, R. Ramalho, B. Passeti, T. Bulhões, and A. [27] N. Y. City, Tlc trip record data, 2016. [Online]. Available: Subramanian, “A hybrid algorithm for the multi-depot het- https://www1.nyc.gov/site/tlc/about/tlc- erogeneous dial-a-ride problem,” Computers & Operations trip-record-data.page. Research, vol. 129, p. 105 196, 2021. [28] P. Kilby, P. Prosser, and P. Shaw, “Guided local search for [10] Y. Rist and M. A. Forbes, “A new formulation for the the vehicle routing problem with time windows,” in Meta- dial-a-ride problem,” Transportation Science, vol. 55, no. 5, heuristics, Springer, 1999, pp. 473–486. pp. 1113–1135, 2021. [29] L. Perron and V. Furnon, OR-Tools, version 7.2, Google, [11] Y. Qu and J. F. Bard, “The heterogeneous pickup and Jul. 19, 2019. [Online]. Available: https : / / delivery problem with configurable vehicle capacity,” Trans- developers.google.com/optimization/. portation Research Part C: Emerging Technologies, vol. 32, pp. 1–20, 2013. ACKNOWLEDGMENT [12] K.-I. Wong, A. Han, and C. Yuen, “On dynamic demand This material is based upon work partially sponsored by responsive transport services with degree of dynamism,” the National Science Foundation under grant CNS-1952011 Transportmetrica A: Transport Science, vol. 10, no. 1, and the Department of Energy under Award Numbers DE- pp. 55–73, 2014. [13] C. H. Häll, J. T. Lundgren, and S. Voss, “Evaluating the per- EE0009212 and DE-EE0008464. We thank Matthew Zalesak formance of a dial-a-ride service using simulation,” Public for his assistance with implementing the proposed frame- Transport, vol. 7, no. 2, pp. 139–157, 2015. work. [14] M. Schilde, K. F. Doerner, and R. F. Hartl, “Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem,” European journal of operational research, vol. 238, no. 1, pp. 18–30, 2014. [15] J.-F. Cordeau, “A branch-and-cut algorithm for the dial-a- ride problem,” Operations Research, vol. 54, no. 3, pp. 573– 586, 2006. [16] T. Garaix, C. Artigues, D. Feillet, and D. Josselin, “Vehicle routing problems with alternative paths: An application to on-demand transportation,” European Journal of Operational Research, vol. 204, no. 1, pp. 62–75, 2010. [17] Y. Qu and J. F. Bard, “A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with con- figurable vehicle capacity,” Transportation Science, vol. 49, no. 2, pp. 254–270, 2015. 8 E-Transit-Bench: Simulation Platform for Analyzing Electric Public Transit Bus Fleet Operations Rishav Sen1 , Alok Kumar Bharati2 , Seyedmehdi Khaleghian3 , Malini Ghosal2 , Michael Wilbur1 , Toan Tran3 , Philip Pugliese4 , Mina Sartipi3 , Himanshu Neema1 , and Abhishek Dubey1 1 Vanderbilt University, Nashville TN, United States 2 Pacific Northwest National Laboratory 3 University of Tennessee at Chattanooga 4 Chattanooga Area Regional Transportation Authority (CARTA), Chattanooga TN, United States ABSTRACT 1 INTRODUCTION When electrified transit systems make grid aware choices, improved Transportation in the modern world is responsible for extensive social welfare is achieved by reducing grid stress, reducing system environmental impact, namely air pollution and emission of vast loss, and minimizing power quality issues. Electrifying transit fleet amounts of greenhouse gases, posing a severe threat to energy has numerous challenges like non availability of buses during charg- security. In the United States, the transportation sector accounts ing, varying charging costs and so on, that are related the electric for 28% of the total energy use [11]. Transitioning to greater use of grid behavior. However, transit systems do not have access to the in- public transit systems can remarkably reduce energy use, thus pro- formation about the co-evolution of the grid’s power flow and there- viding a positive impact on society and the environment. However, fore cannot account for the power grid’s needs in its day-to-day even public transit systems require substantial amounts of energy; operation. In this paper we propose a framework of transportation- for example, public bus transit services in the US are responsible grid co-simulation, analyzing the spatio-temporal interaction be- for at least 19.7 million metric tons of CO2 emission annually [17]. tween the transit operations with electric buses and the power Electric vehicles (EVs) can have a much lower environmental im- distribution grid. Real-world data for a day’s traffic from Chat- pact than comparable internal combustion engine vehicles (ICEVs) tanooga city’s transit system is simulated in SUMO and integrated [26] [27], especially in urban areas. However, in addition to the with a realistic distribution grid simulation (using GridLAB-D) to cost1 , the increasing electrification of transportation raises critical understand the grid impact due to transit electrification. Charging problems of the impact of EV charging on the power grid as well as information is obtained from the transportation simulation to feed the location and schedule of charging. This issue comprises several into grid simulation to assess the impact of charging. We also discuss key concerns. the impact to the grid with higher degree of transit electrification First, the locations of charging stations have to be strategically that further necessitates such an integrated transportation-grid co- located to minimize nodal losses. Second, the electric utility opera- simulation to operate the integrated system optimally. Our future tors have to balance the distribution network and estimate the daily work includes extending the platform for optimizing the charging needs considering the variation in demand. The service areas of and trip assignment operations. the buses span major residential and commercial areas, which have already stressed electric supply feeders. Therefore, both a large CCS CONCEPTS number of buses charging at night in the depot (for low rates and minimizing disruption in transit) and individual buses charging • Computer systems organization → Embedded and cyber- en-route (at extremely high rates) can significantly affect grid re- physical systems; • Computing methodologies → Modeling liability. For example, grid-agnostic charging assignments might and simulation; • General and reference → Cross-computing result in power supply and demand imbalances, reduced power tools and techniques. quality, excessive nodal losses, and price peaks. Since the charging times and locations of EVs drive this problem, it is imperative to un- KEYWORDS derstand the spatio-temporal interaction between mobility and the Cyber-physical systems, traffic simulation, powergrid simulation, electric grid’s distribution system. Third, the transit operators must model-integration, co-simulation also minimize the cost of charging EVs. Finally, the transit operators must also determine buses to trip assignments. The advantage of EVs over ICEVs depends on the route and time of day (e.g., the benefit of EVs is higher in slower traffic with frequent stops and Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed lower on highways), hence the assignment can significantly affect for profit or commercial advantage and that copies bear this notice and the full citation energy usage and the environment [28]. on the first page. Copyrights for components of this work owned by others than ACM Several efforts have attempted to manage the power grid along must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a with route optimization and planning for the electric buses [23] fee. Request permissions from permissions@acm.org. SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany 1 EVs are also much more expensive than ICEVs – typically, diesel transit buses cost © 2022 Association for Computing Machinery. ACM ISBN 978-1-4503-abcd-e/ff/gg. . . $15.00 less than $500K, while electric ones cost more than $700K ($̃1M with charging infras- https://doi.org/10.1145/xxxxxxx.yyyyyyy tructure) [28]. SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Sen, R., et al. [12] [34] [22]. However, these solutions are often decoupled. Large address electric vehicle charging and route optimization while min- scale agent-based simulation platforms such as SUMO [18] and imizing grid impact and transit operation costs. Pettet et al. [23] MATSim [16] have been crucial for planning future transportation bring together optimizing bus charging for electric buses taking scenarios, but they must be interfaced with micro-scale modeling into consideration the grid load. The grid load is crucial to consider systems for co-simulation with the power grid. For example, a as it impacts the proper function of the entire electric grid of the system that works in this way can simulate a transit system using city under consideration. Exacting too much from it may cause SUMO or MATSim and then analyze it in the context of the power blackouts and additional infrastructure repairs. One of the crucial distribution grid (e.g., using GridLAB-D [8]). Such a system can be aspects of this model is the electric grid simulations. A simulation used for integrated transit and power grid analysis (e.g., to analyze platform using Gridlab-D and smart grid sim is demonstrated by "a peak-day scenario where a major event in the downtown area Hansen et al. in [15]. While it fails to take into account the opti- leads to a sudden spike in demand on the transit system [13]. This mizations of bus scheduling and grid loads, it provides a reference not only constrains the road and transit systems but may cause framework for the electrical simulations that are undertaken and is a surge in power demand on the city’s power distribution grid"). a fundamental example to show the integration between an electric Further, it can also analyze the impact of different numbers of simulator and the load balancing of a smart grid. The work provides charging slots on the operating availability of electric vehicles. a starting point for further simulation-based integrations. In the past, we have developed Transit-Gym [30], a SUMO-based Note though integrated transit and electric simulations are lack- general-purpose transit simulator carefully calibrated for the city of ing, some works approach the charge scheduling problem entirely Chattanooga, TN. This has been achieved by careful calibration of from the perspective of transit operations. For example, Paul and the underlying model. Note that for the simulator to remain viable, Yamada [22] provides a k-Greedy Algorithm-based approach for it is crucial to keep the physical transit network of the city and the bus charge scheduling. Their work is one of the early efforts to simulated transit network in sync. Overall, the simulation engine address the issue of maximizing bus travel for each EV and in effect is capable of providing road-based traffic measurement output, reducing emissions. Zhang et al. [34] use a bilevel optimization (us- including macroscopic values such as the mean speed, the mean ing a genetic algorithm) to address the issue of the cost to operate density, and the mean occupancy of road edge during specified electric vehicles by transit agencies. On the other hand, the extent time intervals. For each bus stop, we output the simulated schedule: to which the charger and battery configurations in an already ex- time of arrival and departure, stopping place, and the number of isting environment can cope with a city’s transit requirements is persons that boarded and got off the bus. The passenger itineraries discussed by El-Taweel et al. in [12]. are configurable and are simulated based on input demand models Another aspect of electric transit systems is the day ahead trad- provided by the local transportation planning office. For each transit ing for bus depot operators to minimize the cost of electricity and vehicle, we can provide the current speed and acceleration battery degradation cost which has been addressed by Rafique et al. In this paper, we extend the Transit-Gym [30] and focus on in [25]. It aims at minimizing the cost of electricity by using a two- bridging the gap between these two facets and develop an inte- stage multi-objective stochastic optimization technique based on grated simulation model that can replicate the complete function- a mixed-integer linear programming approach. The calculation of ing of the electric buses, their routes and charging schedules along battery degradation is a vital cog in the operation of all EVs and with the real-time impact of charging them on the power grid. We the precise penalty cost for battery capacity degradation is added demonstrate our system within the context of the city of Chat- to the objective function to account for the exploitation of Vehicle tanooga. The system is designed such that the electric buses can Grid flexibilities. Similarly, Alizadeh et al. in [1] study collaborative dynamically interact with the power grid, causing changes in the and non-collaborative effects on pricing, when the owners of the grid load depending on whether they are charging or not. In this vehicles are cooperating compared to when they are not - highlight- way, we can reliably perform integrated electric vehicle and elec- ing the improved benefits of cooperation(aggregation) of electric tric grid simulations, and have a view of a complete scenario of vehicle fleets. Lastly, there have been efforts to address the electric buses moving along their route, getting discharged, stopping at the vehicle routing, optimization, and charging at a macro scale that needed charging station, and recharging. The entire schedule of the studies this as an interdisciplinary problem to address the issue vehicles can be simulated for any required period. Further, we can economically, environmentally, and to aid in social welfare [7, 10, 19]. have improved simulation scenarios for the functioning of an elec- However, most of these optimizations do not emphasize the need tric vehicle, as the load on the power grid is an important factor to and the capability of coupled micro-simulations that can capture consider for charging all types of EVs. The effect on the power grid dynamics (node losses, surges, load loss) that will impact operations can be instantaneously generated in our simulated environment. at the community scale. Further, the simulations are mostly focused Although this paper is limited to the discussion of the co-simulation on electric optimization. The movement of electric vehicles is not environment, our ongoing work is focused on the optimization of generally prioritized. The charge levels used are usually drawn transit trip plans and schedules for charging electric buses. off of energy estimates and the stochasticity introduced by the variation of degrading battery capacity and charging patterns is not clearly stated. This calls for the true integration of an electric and transit environment that will facilitate a smoother and more 2 RELATED RESEARCH dynamic scenario for EVs to operate in and to locate, monitor, and It is important to emphasize that the overall problem is the inte- instruct them. grated co-simulation and online optimization procedures that can Framework to Evaluate Electrified Public Transit Policies SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Figure 1: Sequence Diagram of co-simulation, describing the interaction between the transit and the power grid simulation Our approach to solving this problem emphasizes the need for of these components work in tandem and run the entire simulation firmly grounding the simulation concepts within the performance platform synchronously. The work is described in Fig 1. as observed in the real world. Collecting and integrating multi- The co-simulation is based on a publish-subscribe model. GridLAB- modal, spatiotemporal datasets is a challenging problem [33]. Our D subscribes to the state of charge (SoC) values from the transit prior work with the city of Chattanooga developing approaches simulator when the EV arrives at the charging station. This trans- for assigning mixed-fleet vehicles to routes showed that operations lates to the grid as an additional load that follows a charging profile, teams can generate savings and reduce carbon emissions by opti- predefined for the EV battery and the charger at the charging station. mizing scheduling [2], [28]. These optimization approaches require The charger profile is also season-dependent to ensure the charging accurate predictive models of energy consumption [3]. It is also time and the impact on the grid behavior are realistic. GridLAB-D important to note that the energy consumption of various vehicle publishes the parameters needed to compute the Grid Impact Score classes (such as electric, hybrid, and diesel) responds to covariates (GIS). Further expansion of the Transit-Grid co-simulation will such as weather, traffic, and elevation differently [32]. include energy market decisions and also Transit systems sched- Our previous work in multi-modal data collection, energy con- uling that will add additional publications and subscriptions from sumption model, and scheduling motivates the development of the various entities being co-simulated. The details of the publish E-Transit-Bench. Specifically, we aim to provide an integrated and subscribe mechanism applied to power grid simulation can be Transportation-Grid simulation that can be used both in day-to-day found in an application involving multiple federate integrated into scheduling and optimization as well as future planning. a time-synchronized co-simulation in references [5, 6, 9]. The python federate is the instructor for all the other compo- nents, storing crucial instructions and passing them to the other 3 OUR APPROACH components. The transit routes, power grid profiles, and other pa- rameters are stored in memory for use by the respective simulators The integrated simulation is designed to make the individual un- before the system is started. The Start message from the python derlying components work in unison, namely, the power grid simu- federate instructs both the grid simulator and the transit simulator lation (using GridLAB-D) and the vehicle transit simulation (using to begin their simulation cycles. This message is passed through the SUMO). The information exchange that goes on between these co-simulator coordinator onto the power grid simulator. The times- simulators needs to be carefully handled as it is time-sensitive. This tamps are synchronized for the execution to begin. The power grid information exchange is performed with the use of the Hierarchi- starts generating its load and GIS and the transit sim emulate the cal Engine for Large-scale Infrastructure Co-Simulation (HELICS) movement of the buses on their designated routes and schedules. [21], an open-source co-simulation framework. The Co-simulator The simulation goes on for the specified time duration. During coordinator is responsible for time synchronization and acts as an this time, it can monitor the movement of all the individual vehicles agent between grid models in GridLAB-D and the python federate. (electric buses) as well as the state of charge (SoC) of the vehicles. There are dedicated computations modules programmed in Python The important checks that go on in the simulation are: (i) checking to perform computations that interact with python federate, that the SoC of electric buses and how much it has depleted, and (ii) utilize the various parameters or information from the interface. All SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Sen, R., et al. checking for any changes in the grid load. The SoC of the bus route may be traversed multiple times a day, going back and forth drops as it moves around in its set route. When the SoC is below between the originating stop and destination stop. a critical level, then the bus needs to charge soon, else, it may The GTFS data can be further analyzed to produce comprehen- run out of charge and stop in its tracks. We want to avoid that sive information about all the trips (aggregating the arrival times scenario and direct the bus to a charger as soon as possible. As at stops, heading off the bus, its block id, and trip id). A block id soon as the bus moves on to the charging location and charging implies the sequence of trips that the same vehicle has to make. begins, its movements are stopped and the power consumption There are other details that we want to incorporate into the model, is added to the grid, in the grid simulation. The grid load is then by using the vehicle types used. The transportation demand is also measured throughout the period of charging the bus and can be modeled into the system to give an estimate of the number of peo- done for multiple charging buses at a time. This is important as ple wanting to take the transit, along with the actual number of it provides an understanding of how much power is drawn from people that are getting on and off the bus. The Traffic Control Inter- the grids at the charging stations and more importantly, how much face (TraCI) allows for controlling the SUMO simulator to extract the grid is affected by this usage and its effects on the surrounding detailed information. neighborhoods. In the process, we want to generate the trips - their trajectory Once the bus reaches the desired charge level, it is disconnected and the route paths being traversed (in the form of edges). Taking from the grid. The power draw at that charger is reduced to zero. into consideration all these multiple factors discussed, we can feed The transit sim then resumes the movement of the bus along its them to our simulator (SUMO). The simulator can be configured to planned route for the rest of the duration. This cycle can go on run for a set duration of time (most commonly, 24 hours). whenever the buses are low on a battery charge or are pre-planned The final step in this is to form the details of each trip that to charge. Data about all the required parameters (like SoC, bus were earlier defined in the GTFS. The simulator generates results movement, weather, trips completed, and so on) can be collected that consist of the unique trip id, bus types, bus stops, arrival and and stored during this period. This technique helps us devise more departure times, and the route that the trip served. The list of trips efficient and battery-healthy bus routes. generated from the simulation successfully emulates the trips that The simulation ends when it has run for the desired duration. would have been made by the transit agency during a specific day. The python federate gets the message from both the grid simu- lator and the transit simulator that their execution has stopped. 3.1.2 Energy Estimation. With all the trips generated, we need to Subsequently, the federate performs any necessary post-processing know how much energy is used by each of the buses on the spe- on the collected data (like grid analysis, and bus efficiency). After cific routes. Therefore, predictive models are required to estimate these are performed, the program terminates, marking the end of the vehicle’s energy needs. As SUMO is a continuous, microscopic the integrated simulation cycle. simulator the predictive models are also microscopic in nature. The microscopic models take as input distance covered, speed, accelera- tion, weather, and elevation change and predict energy consumed at 3.1 Transit Simulation one-second intervals. There are three classes of vehicles (diesel, hy- The task of energy estimation for the electric buses requires us brid and electric), each of which responds to the input features, and to know about the movement of these vehicles. It is necessary to impacts the grid, differently [32]. Therefore, separate energy con- know the time, location, route, speed, state of charge (SoC), and sumption models are trained for each of the three-vehicle classes. some other parameters of the vehicles, for proper measurements The energy models are built on artificial neural networks, in ac- and calculations. The movement of vehicles is simulated using cordance with current state-of-the-art [2]. Energy demands at the the transit-gym model [30]. The buses under consideration can be trip level are derived by aggregating predictions along with the diesel-powered, diesel-electric hybrid, or electric-powered. scheduled trips in GTFS. This section discusses the procedures undertaken to perform the Each of the trips is processed through its respective model and simulations and generate the data required for further processing. its speed, acceleration, distance covered, time taken, and weather We are trying to emulate the actual movement of buses for an conditions are analyzed. These parameters help define the total entire day. The various steps undertaken during this simulation are energy consumption for each trip. As one bus may travel multiple shown. trips (denoted by the same block id), the cumulative energy use can also be measured for the entire day’s running for the bus. The 3.1.1 Simulating a day’s activity. The General Transit Feed Speci- trips generated here contain a mix of ICE buses and electric buses. fication (GTFS) [20] provides the transit data for the specific day For ICE buses, the energy use is in gallons of fuel consumed. For we want to simulate. This data contains the details about all of the the electric buses, the total energy used by them is considered transit buses that run during the day. It includes the concerned in terms of kWh (kilowatt-hours). Since our primary focus is on agency, the dates for the service to run, the different routes, the electric buses, we separate them from the rest and continue further shapes forming the routes with their distances, the bus stops on analysis, such as finding the grid impact score (it is detailed in each of the routes, the times when buses arrive and leave those further sections). stops, and most important - it contains all the trips per day that the The total energy use, in turn, is used to generate the state of agency plans to undertake with this schedule, indexed by trip id. charge (SoC) metric. SoC is the primary metric of concern - low This value can be filtered and changed to meet each day’s demand SoC indicates the bus needs to be charged soon. An electric bus by reducing the number of trips that are undertaken. A specific usually starts the day’s first trip with a high SoC (almost 90% of its Framework to Evaluate Electrified Public Transit Policies SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Charger Load as a Function of State of Charge 0.8 Residential Commercial Load Multipliers 400 Charger Load per Phase (kW) 350 0.6 300 250 0.4 200 150 100 0.2 Substation 50 0 0 Charging Station 0 20 40 60 80 100 0 5 10 15 20 25 State of Charge, SoC (%) Time (hrs) (a) (b) (c) Figure 2: (a) Taxonomy Feeder Model with Charger Location. (b) Load induced on charger when charged from a specific State of Charge. (c) 24-hr external load on the simulated power grid. battery capacity). It gradually uses up the battery’s energy through- cause sudden spikes of load increase in the distribution grid that out the day’s trip, lowering its SoC. Thus, we can estimate the can cause issues like imbalance, increased losses in the network, SoC of the electric buses from the simulated results, which can be and drop-in voltages due to the increased load. The location of further provided to the grid simulator, to perform the de-coupled the charger along with the amount of charging load should be co-simulation. considered along with the detailed grid models to evaluate the grid Next, we describe the case study from our partner community impact accurately. in Chattanooga that will be useful in understanding the simulation In the current work, the location of the charger is chosen to be operation. Then, we proceed to discuss the various steps involved closest to the largest load in the system mimicking a large commer- in the grid simulations and incorporate the information from the cial location3 . The charging station is modeled with two chargers. Transit simulations into the EV or electric bus charging and analyze The simulation of the electric bus and its impact on the grid is con- its impact on the grid behavior. This section also provides the details sidered with a winter seasonal profile and a corresponding charging of quantifying the impact of EV charging on the grid performance profile is considered, based on the charging loads given in refer- through a formulated grid impact score that includes the voltage ence [4]. The charger load on the grid is determined by a linear measurements, losses in the system, and total distribution system function (an approximation based on data presented in [4]). This load. load function (Fig. 2b) describes the expected increase in the load per phase on the grid when the EV gets charged. This exercise can 3.2 Case study of Chattanooga be repeated for advanced chargers and improved charging profiles In our simulation environment, the data is obtained from the Chat- too, and the developed framework can easily integrate it into the tanooga Area Regional Transportation Authority (CARTA). The power grid models through the load that is reflected on the grid GTFS generated is from the actual day’s trips for Jan 11, 2022, for during a charging event. Fig. 2b also gives the charger load per 24 hours, from 12 AM to 11:59 PM. This data contains the various phase and the derived 3-phase charger load function. The peak 3𝜙 trips and the associated buses. To model the grid aspect (discussed 3-phase load due to the charger (𝑃𝐶ℎ𝑎𝑟𝑔𝑒𝑟 ) is approximately 1 MW in the next section) we use a taxonomy feeder with 265 nodes (R5- for a single charger at the charging station. The charging current 12.47-1) and a root node voltage of 13.8 kV that includes overhead and the charging power depend on the SoC of the battery when it lines, underground cables, triplex lines, and triplex meters. The is charging. This profile is different for different kinds of batteries medium voltage parts of the distribution feeder at the primary and and chargers. Based on the data available in reference [4], an aver- secondary distribution systems are usually modeled using over- age linear approximation is constructed that is used to model the head lines and underground cables. These parts of the network increase in the load on the distribution system as a function of the feed the large commercial loads and tertiary distribution networks, SoC of the battery. Depending on the charging station models, the where the terminal loads are located. The terminal connections to rate of charging and the load on the grid can be modeled. These the low voltage consumer loads at the residential level are usually are also dependent on the season, the charging time is slower in connected using triplex lines and the corresponding meters at such winter as compared to summer. nodes in the distribution feeder are called triplex meters. The feeder The loads in the power distribution feeder are modeled with two represents a sub-urban and urban feeder section that has potential load profiles: commercial; and residential load profiles. The largest connectivity to other feeders and models the representative archi- 3-phase balanced loads in the feeder are modeled as commercial tecture from Chattanooga2 . The structure of the feeder is shown in loads. The remaining loads in the feeder are modeled as residential Fig 2a. The feeder structure is similar to the real feeder profile of the loads with a residential load profile. The commercial and residential Chattanooga region and hence is chosen for the present analysis. load profiles are also considered for the winter season and shown in Fig. 2c. These load profiles for the loads are assumed for a typical 3.2.1 Distribution Grid Components. Transportation electrification weekday in winter in the US. has a direct relation to power grid operations. The EV charging can 3 In future work, we will work on optimizing the location based on the analysis enabled 2 The actual city feeder architecture is security-critical and cannot be shared publicly by the co-simulation discussed in this paper. SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Sen, R., et al. Start Read the energy consumed by electric bus (EB) at a time ‘t’ 100 State of Charge (%) Compute the SoC at time ‘t’ (in pu) 80 SoC = -0.31xEnergy + 90 EB charging simulated in grid simulation based on the Expected charging end time sent to the Transit simulation for Transit Route Scheduling 60 Grid Impact Score Computation Grid Impact Score sent to Charging 40 based on the Grid Simulation Scheduling to minimize impact 20 Record the grid simulation outputs 0 Stop 0 100 200 300 Energy Consumed by the Electric Bus (kWh) (a) (b) Figure 3: (a) Overall steps to integrate the transportation and energy simulations.(b) The Transit system provides energy used at every instant. We use the following linear function to estimate the SoC (this is calibrated for the electrical vehicles in Chattanooga Fleet.). 3.3 Modeling and Simulating the Impact on • Imbalance factor [31] of the circuit after charging at node 𝑖 at Electric Grid time 𝑡 approximated by √︄ √ Note the electric simulation used in this study (as implemented 𝑣2 1 − 3 − 6𝛼 by GridLAB-D) is a quasi-steady-state time series analysis with an I𝑖 = ≈ √ , (2) 𝑣1 1 + 3 + 6𝛼 unbalanced distribution system power flow at every second. This simulation is configured with the feeder described in the previous where, section and configured with weather profiles from the city. The 4 + 𝑣4 + 𝑣4 𝑣𝑎𝑏 𝑐𝑎 steps involved in utilizing the Transit simulation output to simulate 𝛼= 𝑏𝑐 2 + 𝑣 2 + 𝑣 2 )2 , (3) (𝑣𝑎𝑏 the charging of the electric buses for the corresponding SoC and 𝑏𝑐 𝑐𝑎 time are described in the flowchart shown in Fig. 3a. Estimating the and 𝑣 1 and 𝑣 2 are the positive and negative sequence voltage, and SoC based on total energy consumed is one important step in the 𝑣𝑎𝑏 , 𝑣𝑏𝑐 , 𝑣𝑐𝑎 are the phase voltages corresponding to the phases present decoupled co-simulation analysis. The Transit simulation 𝑎𝑏, 𝑏𝑐, 𝑐𝑎. records the energy consumed in every trip along with the amount • Total line losses 𝐿 in underground cables (𝐿𝑢𝑔 ), overhead lines of discharge of the battery (in terms of a drop in SoC with respect (𝐿𝑜ℎ ) and triplex lines (𝐿𝑡𝑥 )after charging in the distribution to full charge). This information is represented through a linear feeder for charger at node 𝑖, regression fit using all the discharge and energy consumption val- 𝑢𝑔 𝐿𝑖 = 𝐿𝑖 + 𝐿𝑖𝑜ℎ + 𝐿𝑖𝑡𝑥 (4) ues for all trips simulated for a day in the Transit simulations. The resultant linear function is shown in Fig. 3b. Using the SoC-Energy • Apparent power drawn from the feeder head (substation) 𝑓 cor- relation, the end SoC is computed for every electric bus in simu- responding to the node 𝑖 where the charger is placed at time lation at the end of its day’s trip or when SoC reached values in a 𝑡, ∑︁ range of 15% − 20%. S𝑓 = 𝑉𝑓 ,𝜙 𝐼 𝑓 ,𝜙 , ∀𝜙 (5) 𝜙 3.4 Grid Impact Score where, the complex voltage and current at the feeder 𝑓 are de- A key aspect of our analysis is the generation of grid impact score noted by 𝑉𝑓 and 𝐼 𝑓 . (GIS) which is a modified version of the grid score introduced in Now, we introduce a novel metric to measure the impact on grid. [24]. This requires collation of charging load, daily load, and load This grid impact score(GIS) 𝑔𝑖 is given by,  ∑︁ flow analysis is performed to monitor nodal voltage deviations, 1 1 |Δ𝑣𝑖,𝑗 | I𝑖 𝑅𝑒{𝐿𝑖 } phase imbalances, line losses, and the apparent power drawn from 𝑔𝑖 = Í 𝑤1 + 𝑤2 + 𝑤3 𝑛 𝑤 𝑛 3 Δ𝑣 𝑚𝑎𝑥 I𝑚𝑎𝑥 𝑅𝑒{𝐿𝑚𝑎𝑥 } the feeder head to analyze equipment thermal loading. These mea- 𝑗 ∈𝜙  surements are: 𝑅𝑒{S 𝑓 } +𝑤 4 (6) 𝑠𝑢𝑏 } 𝑅𝑒{S𝑚𝑎𝑥 • Nodal voltage deviation of the phases 𝜙 ∈ {𝑎, 𝑏, 𝑐}, Here, Δ𝑣𝑚𝑎𝑥 , I𝑚𝑎𝑥 , 𝐿𝑚𝑎𝑥 , S𝑚𝑎𝑥 𝑠𝑢𝑏 denote the maximum allowable limits of nodal voltage deviation, imbalance factor, total system loss 𝑣𝑖,𝜙 − 𝑣𝑛𝑜𝑚 and the apparent power drawn, respectively. Based on the above Δ𝑣𝑖,𝜙 = (1) 𝑣𝑛𝑜𝑚 measurands in (2)-(5), a novel grid score metric of charging at node Framework to Evaluate Electrified Public Transit Policies SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany 1,000 Energy consumed (in mi/gal) 350 Distance covered (in miles) Passenger occupancy 30 Energy consumed 300 800 20 250 600 200 10 150 400 0 100 Route1 Route10A Route10C Route10G Route13 Route14 Route15A Route16 Route21 Route28 Route2A Route3 Route33 Route4 Route9 RouteDTS Route1 Route3 Route4 Route9 Route10C Route10A Route10G Route16 Route21 Route13 Route28 Route2A Route4 Route9 Route16 Route33 Route15A Route Routes (a) (b) Figure 4: Results from the transit simulation for a day in January in Chattanooga. (a) Maximum passenger occupancy of each bus along the bus stops by routes over 24 hours. (b) Energy consumed rates (in gallon) and the total distance travelled across trips on each route. ℎ𝑜𝑢𝑟 8 ℎ𝑜𝑢𝑟 12 ℎ𝑜𝑢𝑟 17 Energy efficiency (in mi/gal) electric 15 0.8 diesel Passenger density 0.6 10 0.4 5 0.2 50 100 150 200 250 300 350 400 450 500 550 600 650 0 0 5 10 15 20 25 30 35 40 45 50 55 60 Trip number Minutes (a) (b) Figure 5: Results from the transit simulation for a day in January in Chattanooga. (a) Energy efficiency of vehicles across trips. In general, electric vehicles are most efficient. But there are places where diesel vehicles are more efficient. This points to a need for optimizing trip assignment [28]. (b) Distributions of bus occupancy at specific hours on route 4. 𝑖 at time 𝑡 is defined, where, 𝑤𝑛 , ∀𝑛 ∈ {1, 2, 3, 4}’s are the various for the provided GTFS (obtained from the local transit agency), weights associated with the additive terms in (6) (normalized volt- to find the energy usage for the electric buses. Figure 4a shows age violation, imbalance factor, loss, and apparent power drawn at the maximum passenger occupancy across all trips grouped by feeder’s head). These weights are introduced so that the planner routes. Figure 5b shows the aggregated passenger density. Figure 5a can choose to prioritize each contributing factor in the metric dif- describes the energy efficiency in miles per gallon (we convert ferently. Uniform contribution from the contributing factors would the kWh from electric vehicles to gallons per mile - this is done require each weight to be equal to 1. The joint grid score of multiple according to the standard conversion factor as defined by the United chargers’ charging impact at a particular time can be derived using States Environmental Protection Agency 4 ) Figure 4b shows the an extension of the expression in (6). The time variable 𝑡 is dropped cumulative energy consumed and distance traveled across all trips for simplicity in the above derivation. The purpose of introducing on each route. the grid impact score is it include in the planning and operation decisions of the grid. This would enable the transit to make grid- Table 1: Summary of five different charging scenarios that friendly choices resulting in reduced loss (otherwise to be borne by were simulated all the users), and power quality issues and would aid in different infrastructure upgrades benefiting everyone. Bus # SoC at Charging Instant (%) Charging Start Time Charging End Time 1 49.93 12:00 12:18 2 24.30 14:17 14:47 4 CASE STUDY 3 33.65 15:12 15:38 4 15.68 15:35 16:11 The simulator and its working are put to test here, as we discuss 5 66.75 18:14 18:23 simulating the operations of the electric buses and the effect on the electric grid due to charging them. We look into two scenarios - first, for a regular day’s traffic for the present day. The second case The energy estimator runs through all the generated trips accord- is for the forecasted use of electric vehicles, as the EV load on the ing to the steps discussed earlier. It can provide a comprehensive grid is projected to be 15-30% of the total capacity, by 2050 [29]. consumption metric not only for each trip, but also for blocks of The figures in our modeled assumptions are not far away from the trips, and for each vehicle that ran. The SoCs for the electric ve- expected rise. hicles are then generated (Fig. 6a) and made available to the grid simulator for analysis of the GIS. The average speed of the electric 4.1 Analysis of the day of operation buses is shown in Fig. 6b. During the simulation, we constantly check the SoC of the vehicles and then estimate when the vehicle is We now introduce the analysis of a day from January 11, 2022, as described in Section 3.2. The traffic and trip data are generated 4 https://www3.epa.gov/otaq/gvg/learn-more-technology.htm SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Sen, R., et al. Energy consumed Distance covered 0.77 150 100 0.76 Energy consumed (in mi/gal) Distance covered (in miles) 0.8 0.75 Number of buses 0.6 0.74 100 0.73 GIS 50 0.4 0.72 50 0.71 0.2 0.7 0 0 0 0.69 0 5 10 15 20 25 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.0 20.0 21.0 22.0 23.0 24.0 25.0 26.0 27.0 29.0 10:15 11:28 12:28 13:24 14:38 15:04 15:35 16:13 16:42 17:15 Time Speed (in mi/hr) Time (hrs) (a) (b) (c) Figure 6: Results from the transit simulation for a day in January in Chattanooga. (a) SoC change for one bus with sequential trips. (b) Average speed of the electric buses across all trips for 24 hours (c) Grid Impact Score across 24 hrs. 288 80 200 40 287 Phase A Phase B Phase C 70 Reactive Losses (kVAr) 30 Real Losses (kW) Node Voltage (V) 286 60 150 Cost ($) 285 50 20 284 40 100 10 283 30 282 20 50 0 281 10 Real Loss Reactive Losses CH#1 CH#2 CH#3 CH#4 CH#5 280 0 0 Charging instances 0 5 10 15 20 25 0 5 10 15 20 25 Time (hrs) Time (hrs) Usage (non-peak) Usage (peak) (a) (b) (c) Figure 7: Results from the transit simulation for a day in January in Chattanooga. (a) Node Voltage at the charger location. (b) Total Feeder Loss (c) Usage charge breakdown in 5 charging instances (Table 1). ready for charging (once it finishes its trip in the transit simulation). 4.2 Impact of additional electrical vehicles Table 1 shows the summary of the inputs to one of the simulations For this part of the study, we estimate the presence of additional discussed in Section 4.1. The end SoC for each bus is assumed to be electric vehicles that are charging in the vicinity. To analyze this, 80% of its capacity. For the time duration between 15:35 hours to the charging loads for the previous scenario are increased by 10 15:38 hours, both the chargers at the charging station are actively times. In this scenario, the GIS increases and may cause serious charging the buses and during the rest of the charging cycles, only disruption to the grid. Fig. 8c shows the comparison of the GIS and one charger at the charging station is actively charging based on how it increases under high penetration of other electrical vehicles the schedule of the Transit system. The grid simulation results are considering no other changes in the grid models. However, with the summarized below. Figures 7a and 7b demonstrate the impact of evolving grid-edge technologies like real-time retail market designs, charging on the grid performance. The results show the voltage and increased integration of renewable energy sources (RES), the at the charging node and the total feeder losses. The voltage dips GIS is expected to be significantly higher. The deviation terms in the during charging due to an increase in the load and since the charger GIS formulation are usually normalized by the maximum allowable is located at the end of the feeder the loss increase in the system deviation - corresponding to each of the factors (e.g., voltage, loss, during the charging times can be observed clearly. etc). Thus, in case of no grid-related constraint violation, its value A grid impact score (GIS) is determined for the given scenario should be within 0 and 1. However, in this case, the normalization and location of the charger. This GIS will depend on various pa- factor is chosen to be the maximum observed deviation in the lower rameters like the location of the charger, seasonal impact on the EV penetration scenario for ease of comparison. Therefore, in this charging profile, etc. For the presented simple case of low penetra- paper, the GIS value is allowed to exceed 1. In case of using the tion of electric buses that has five electric buses charging at various framework for the charging optimization problem in the future, the times that are modeled in a 24-hour day-long simulation, the GIS high penetration scenario is likely to cause constraint violations is computed and its variation in 24 hours duration is shown in Fig. leading to GIS values exceeding 1, and thus such scenarios would 6c. The GIS is relatively higher during charging (compared to the be discarded. instant just before charging) as there is a significant drop in voltage Note that the Grid Impact Score (GIS) is a reflection of grid per- and an increase in the system losses. formance parameters like voltages, systems losses, etc. Figures 8a However, as other electric vehicles in the city are considered and 8b shows the impact of high penetration of electrical vehicles and modeled to be charged in the area at the same time, the GIS and the integration of the charging infrastructure with the grid. would be much higher. A hypothetical case of high penetration of The losses and the voltage drop in the system are more profound in electrical vehicles is described next. this case, however, these can be addressed by optimally scheduling the EV (in our case, electric bus) charging to distribute these peaks Framework to Evaluate Electrified Public Transit Policies SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany 295 700 2000 3.5 GIS_Low Penetration of EV Phase A Phase B Phase C 600 Real Loss Relative GIS_High Penetration of EV Reactive Losses (kVAr) 290 Real Losses (kW) Node Voltage (V) 500 Reactive Losses 1500 2.5 GIS 285 400 1000 280 300 1.5 200 500 275 100 270 0 0 0.5 0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 Time (hrs) Time (hrs) Time (hrs) (a) (b) (c) Figure 8: The figures show results of the impact on Grid when consider the load induced by additional transit vehicles. (a)Node Voltage Magnitudes at Charger Location. (b)Total Feeder Loss (c) GIS under High Penetration of EV Charging Relative to Low EV Penetration Case. caused by the sudden increase in the charging loads. The GIS used This leaves room for additional improvement in planning and op- for these computations can be utilized as an indicator for determin- eration that would be optimal for both systems. The framework ing the optimal operation of the integrated transit-grid systems. of the transportation-grid model presented in the paper provides These results indicate that considering various kinds of distributed additional knobs for the integrated transit-grid system to account energy resources (DERs) along with large-scale electrification of for bringing greater social welfare by achieving the following goals: transportation will impact the grid behavior and will need coordi- • Reduced loss: As we can observe from Fig. 8b, the loss is often nated efforts to avoid unwanted disruptions to the operations of significant due to the event of charging for the high penetration the transportation and the grid infrastructure. of electric bus charging scenario. The loss also varies from node to node. Any additional loss occurring in the system burdens not 4.3 Charging Cost only the EV fleet owner but all the customers by driving the cost CARTA and the electric utility’s rate structure are used to obtain of production up. the cost of the charging model. The total cost of electricity for • Scaling down infrastructure upgrade cost: By considering GIS into recharging a bus’s battery does not only depend on how much a scheduling algorithm, infrastructure upgrades could be scaled energy is consumed from the grid but also, on the rate at which down, in the process bringing additional benefits for the cus- energy is drawn, i.e., power (kilowatts). The distribution utility tomers by allowing for lower transportation costs. (EPB) bills two types of charges a large customer-usage charge and • Absorbing solar energy: The framework is also capable of inte- a demand charge. The usage charge is proportional to the energy grating weather-dependent distributed energy resources models used. This rate varies from peak to non-peak hours. Moreover, the in the form of high solar energy scenarios, encouraging charging peak hours vary in season. The demand charge is proportional to a during these peak production hours. portion of power drawn and applies only if it aggravates the peak Enabling all of the above with the framework would ensure that load. Based on EPB’s rates structure for commercial, government, increased social benefit is achieved when the two entities (the and industrial consumers, as shown in the GSA-2 rate [14], the power grid and the transit agency) cooperate. worst case and best-case costs for recharging the buses during the stated times would be following as shown in Table 2. In addition 5 CONCLUSION to the rate structure outlined in GSA-2, to introduce a time-of-use Electrification of the transit fleet provides numerous societal ben- usage charge, the peak time usage charge is assumed to be 1.5 times efits including a reduction in greenhouse gas emissions, reduced the non-peak usage charge. The usage charge breakdown of the cost, and improved environmental health. However, owing to the charging instance shown in Table 2 is shown in Fig. 7c. The demand substantial need to charge electric buses, it can cause major im- charge for any of the instances, if applied, would be $5886. balances in power supply and demand leading to grid instability. Therefore, in this paper, we presented a grid-aware approach and Table 2: Electric Bus Charging Cost a simulation platform that can co-evaluate the grid impact of an electrified transit system. A framework is presented to combine Case Usage Charge ($) Demand Charge ($) detailed, agent-based simulations of public transportation, and the Best case (non-peak) 71 0 power flow of the power grid distribution system. Both the systems Worst case (peak) 106 5886 independently represent realistic daily conditions such as the tran- sit’s traffic flow, energy use, schedules, etc. for the transportation systems and also for power flow occurring due to nodal demands 4.4 Discussion at the distribution systems. The systems interact and influence The electrified transit operates in tandem with the underlying grid each other with a common point of coupling taking place when system. However, electrified transit’s day-to-day operation often the charging of buses takes place. We further validated our exper- does not consider the grid’s health. The transportation system also iments using real world data and presented a detailed case study has limited visibility into the grid. Some grid-related preferences to demonstrate our approach. The initial results presented here are baked into the offline, coarse pricing model of the charging. show how we can capture and quantify several charging events’ SD-SSCPS ’2022, June 28, 2022, Oldenburg, Germany Sen, R., et al. impacts on the grid to further optimize the integrated operation. interface for Smart distribution Grid simulations. In 2015 IEEE Power & Energy This framework can further be used for developing and testing algo- Society General Meeting. IEEE, 1–5. [16] Andreas Horni, Kai Nagel, and Kay W. Axhausen. 2016. The multi-agent transport rithms for grid-aware transit operations. The framework is capable simulation MATSim. Ubiquity Press. of including customized charging profiles making it future proof to [17] Alan Jenn, Katalin Springel, and Anand R Gopal. 2018. Effectiveness of electric vehicle incentives in the United States. Energy policy 119 (2018), 349–356. account for newer charger models and improved charging profiles [18] Daniel Krajzewicz, Georg Hertkorn, Christian Rössel, and Peter Wagner. 2002. that reflect as the load on the grid. The GIS can be used as a metric SUMO (Simulation of Urban MObility)-an open-source traffic simulation. In in future optimal charging solution methods where it can reflect Proceedings of the 4th middle East Symposium on Simulation and Modelling (MESM20002). 183–187. on the feasible and infeasible regions for optimal charging. In the [19] Tai-Yu Ma and Yumeng Fang. 2021. Survey of charging scheduling, fleet man- future, we also plan to work on developing a decision agent in our agement, and location planning of charging stations for electrified demand- responsive transport systems: methodologies and recent developments. arXiv platform that uses machine learning techniques for optimizing the preprint arXiv:2112.04221 (2021). charging and trip assignment operations. [20] Bibiana McHugh. 2013. Pioneering open data standards: The GTFS Story. Beyond transparency: open data and the future of civic innovation (2013), 125–135. [21] Bryan Palmintier, Dheepak Krishnamurthy, Philip Top, Steve Smith, Jeff Daily, ACKNOWLEDGMENTS and Jason Fuller. 2017. Design of the HELICS high-performance transmission- This material is based upon work supported by the Department of distribution-communication-market co-simulation framework. In 2017 Workshop on Modeling and Simulation of Cyber-Physical Energy Systems (MSCPES). 1–6. Energy, Office of Energy Efficiency and Renewable Energy (EERE), https://doi.org/10.1109/MSCPES.2017.8064542 under Award Number DE-EE0009212 and National Science Foun- [22] Topon Paul and Hisashi Yamada. 2014. Operation and charging scheduling of electric buses in a city bus route network. In 17th international IEEE conference dation under Award Numbers 1952011 and 1818901. on intelligent transportation systems (ITSC). IEEE, 2780–2786. [23] Geoffrey Pettet, Malini Ghosal, Shant Mahserejian, Sarah Davis, Siddharth Srid- REFERENCES har, Abhishek Dubey, and Michael Kintner-Meyer. 2021. A Decision Support Framework for Grid-Aware Electric Bus Charge Scheduling. In 2021 IEEE Power & [1] Mahnoosh Alizadeh, Hoi-To Wai, Mainak Chowdhury, Andrea Goldsmith, Anna Energy Society Innovative Smart Grid Technologies Conference (ISGT). IEEE, 1–5. Scaglione, and Tara Javidi. 2016. Optimal pricing to manage electric vehicles [24] Geoffrey Pettet, Malini Ghosal, Shant Mahserejian, Sarah Davis, Siddharth Srid- in coupled power and transportation networks. IEEE Transactions on control of har, Abhishek Dubey, and Michael Kintner-Meyer. 2021. A Decision Support network systems 4, 4 (2016), 863–875. Framework for Grid-Aware Electric Bus Charge Scheduling. In 2021 IEEE Power & [2] Afiya Ayman, Amutheezan Sivagnanam, Michael Wilbur, Philip Pugliese, Ab- Energy Society Innovative Smart Grid Technologies Conference (ISGT). IEEE, 1–5. hishek Dubey, and Aron Laszka. 2020. Data-Driven Prediction and Optimization [25] S Rafique, MSH Nizami, UB Irshad, MJ Hossain, and SC Mukhopadhyay. 2022. A of Energy Use for Transit Fleets of Electric and ICE Vehicles. ACM Transations of two-stage multi-objective stochastic optimization strategy to minimize cost for Internet Technology 22, 1 (2020), 1–29. electric bus depot operators. Journal of Cleaner Production 332 (2022), 129856. [3] Afiya Ayman, Michael Wilbur, Amutheezan Sivagnanam, Philip Pugliese, Ab- [26] David B Richardson. 2013. Electric vehicles and the electric grid: A review of hishek Dubey, and Aron Laszka. 2020. Data-Driven Prediction of Route-Level modeling approaches, Impacts, and renewable energy integration. Renewable Energy Use for Mixed-Vehicle Transit Fleets. In 2020 IEEE International Conference and Sustainable Energy Reviews 19 (2013), 247–254. on Smart Computing (SMARTCOMP) (SMARTCOMP 2020). Bologna, Italy. [27] Muhammad Shafique, Anam Azam, Muhammad Rafiq, and Xiaowei Luo. 2022. [4] Muhammad Aziz and Takuya Oda. 2016. Load Leveling Utilizing Electric Ve- Life cycle assessment of electric vehicles and internal combustion engine vehicles: hicles and their Used Batteries. In Modeling and Simulation for Electric Vehicle A case study of Hong Kong. Research in Transportation Economics 91 (2022), Applications, Mohamed Amine Fakhfakh (Ed.). IntechOpen, Rijeka, Chapter 6. 101112. https://doi.org/10.5772/64432 [28] Amutheezan Sivagnanam, Afiya Ayman, Michael Wilbur, Philip Pugliese, Ab- [5] Alok Kumar Bharati and Venkataramana Ajjarapu. 2021. A Scalable Multi- hishek Dubey, and Aron Laszka. 2021. Minimizing Energy Use of Mixed-Fleet Timescale T&D Co-Simulation Framework using HELICS. (2021), 1–6. Public Transit for Fixed-Route Service. Proceedings of the AAAI Conference on [6] Alok Kumar Bharati and Venkataramana Ajjarapu. 2021. SMTD Co-Simulation Artificial Intelligence 35, 17 (May 2021), 14930–14938. https://ojs.aaai.org/index. Framework with HELICS for Future-Grid Analysis and Synthetic Measurement- php/AAAI/article/view/17752 Data Generation. IEEE Transactions on Industry Applications (2021). [29] Daniel Steinberg, Dave Bielen, Josh Eichman, Kelly Eurek, Jeff Logan, Trieu [7] Benjamin Daniel Blat Belmonte and Stephan Rinderknecht. 2021. Optimization Mai, Colin McMillan, Andrew Parker, Laura Vimmerstedt, and Eric Wilson. 2017. Approach for Long-Term Planning of Charging Infrastructure for Fixed-Route Electrification and Decarbonization: Exploring US Energy Use and Greenhouse Gas Transportation Systems. World Electric Vehicle Journal 12, 4 (2021), 258. Emissions in Scenarios with Widespread Electrification and Power Sector Decar- [8] David P. Chassin, Jason C. Fuller, and Ned Djilali. 2014. GridLAB-D: An Agent- bonization. Technical Report. National Renewable Energy Lab.(NREL), Golden, Based Simulation Framework for Smart Grids. Journal of Applied Mathematics CO (United States). 2014 (1 2014). https://doi.org/10.1155/2014/492320 [30] R. Sun, R. Gui, H. Neema, Y. Chen, J. Ugirumurera, J. Severino, P. Pugliese, A. [9] Selim Ciraci, Jeff Daily, Jason Fuller, Andrew Fisher, Laurentiu Marinovici, and Laszka, and A. Dubey. 2021. TRANSIT-GYM: A Simulation and Evaluation Engine Khushbu Agarwal. 2014. FNCS: A Framework for Power System and Communi- for Analysis of Bus Transit Systems. In 2021 IEEE International Conference on cation Networks Co-Simulation. In Proceedings of the Symposium on Theory of Smart Computing (SMARTCOMP). IEEE Computer Society, Los Alamitos, CA, Modeling & Simulation - DEVS Integrative (Tampa, Florida) (DEVS ’14). Society USA, 69–76. https://doi.org/10.1109/SMARTCOMP52413.2021.00030 for Computer Simulation International, San Diego, CA, USA, Article 36, 8 pages. [31] Azhar Ul-Haq, Carlo Cecati, Kai Strunz, and Ehsan Abbasi. 2015. Impact of [10] Sanchari Deb, Kari Tammi, Karuna Kalita, and Pinakeswar Mahanta. 2018. Review electric vehicle charging on voltage unbalance in an urban distribution network. of recent trends in charging infrastructure planning for electric vehicles. Wiley Intelligent Industrial Systems 1, 1 (2015), 51–60. Interdisciplinary Reviews: Energy and Environment 7, 6 (2018), e306. [32] Michael Wilbur, Ayan Mukhopadhyay, Sayyed Vazirizade, Philip Pugliese, Aron [11] Abhishek Dubey, Philip Pugliese, Chattanooga Area Regional Transportation, Laszka, and Abhishek Dubey. 2021. Energy and Emission Prediction for Mixed- Aron Laszka, and Yuche Chen. 2021. High-Dimensional Data-Driven Energy Vehicle Transit Fleets Using Multi-task and Inductive Transfer Learning. In Optimization for Multi-Modal Transit Agencies. (2021). Machine Learning and Knowledge Discovery in Databases. Applied Data Science [12] Nader A El-Taweel, Hany EZ Farag, Gouri Barai, Hatem Zeineldin, Ahmed Al- Track, Yuxiao Dong, Nicolas Kourtellis, Barbara Hammer, and Jose A. Lozano Durra, and Ehab F El-Saadany. 2021. A Systematic Approach for Design and (Eds.). Springer International Publishing, Cham, 502–517. Analysis of Electrified Public Bus Transit Fleets. IEEE Systems Journal (2021), [33] Michael Wilbur, Philip Pugliese, Aron Laszka, and Abhishek Dubey. 2021. Efficient 1–12. Data Management for Intelligent Urban Mobility Systems. In Proceedings of the [13] Robert F Engle, Chowdhury Mustafa, and John Rice. 1992. Modelling peak Workshop on Data-Driven and Intelligent Cyber-Physical Systems (Nashville, TN, electricity demand. Journal of forecasting 11, 3 (1992), 241–251. USA) (DI-CPS’21). Association for Computing Machinery, New York, NY, USA, [14] EPB of Chattanooga. 2018. GSA Rate Schedule Summary, version 1. Retrieved 22–26. https://doi.org/10.1145/3459609.3460527 October 1, 2018 from https://assets.epb.com/media/ratesp [34] Wenwei Zhang, Hui Zhao, and Ziqi Song. 2021. Integrating transit route network [15] Timothy M Hansen, Bryan Palmintier, Siddharth Suryanarayanan, Anthony A design and fast charging station planning for battery electric buses. IEEE Access Maciejewski, and Howard Jay Siegel. 2015. Bus. py: A GridLAB-D communication 9 (2021), 51604–51617. D EPLOYING M OBILITY-O N -D EMAND FOR A LL BY O PTIMIZING PARATRANSIT S ERVICES∗ Sophie Pavia David Rogers Amutheezan Sivagnanam Vanderbilt University Vanderbilt University The Pennsylvania State University sophie.r.pavia@vanderbilt.edu david.rogers@vanderbilt.edu amutheezan@psu.edu Michael Wilbur Danushka Edirimanna Youngseo Kim Philip Pugliese Vanderbilt University Cornell University Cornell University CARTA michael.p.wilbur@vanderbilt.edu ke233@cornell.edu yk796@cornell.edu philippugliese@gocarta.org Samitha Samaranayake Aron Laszka Ayan Mukhopadhyay Cornell University The Pennsylvania State University Vanderbilt University samitha@cornell.edu laszka.aron@gmail.com ayan.mukhopadhyay@vanderbilt.edu Abhishek Dubey Vanderbilt University abhishek.dubey@vanderbilt.edu A BSTRACT While on-demand ride-sharing services have become popular in recent years, traditional on-demand transit services cannot be used by everyone, e.g., people who use wheelchairs. Paratransit services, operated by public transit agencies, are a critical infrastructure that offers door-to-door transporta- tion assistance for individuals who face challenges in using standard transit routes. However, with declining ridership and mounting financial pressure, public transit agencies in the USA struggle to operate existing services. We collaborate with a public transit agency from the southern USA, highlight the specific nuances of paratransit optimization, and present a vehicle routing problem formulation for optimizing paratransit. We validate our approach using real-world data from the transit agency, present results from an actual pilot deployment of the proposed approach in the city, and show how the proposed approach comprehensively outperforms existing approaches used by the transit agency. To the best of our knowledge, this work presents one of the first examples of using open-source algorithmic approaches for paratransit optimization. 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; ∗ Accepted in the AI and Social Good Track at the International Joint Conference on Artificial Intelligence (IJCAI), 2024 Figure 1: (left) The van that CARTA uses for paratransit operations. (right) A driver helping a passenger with a wheelchair board the paratransit van. Paratransit services are compliant with the Americans with Disabilities Act (ADA) and offer competitive transit services to the section of the population who cannot avail standard transit routes. e.g., low-wage workers, people with disabilities, and the elderly have poorer access to transit in the USA [Stacy et al., 2020, DeGood, 2011]. A particularly critical component of public transit service in USA is the paratransit service, which offers door-to-door 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 (UN- SDG) 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).2 We directly work with a public transit agency in the southern USA, CARTA, Chattanooga Area Regional Transporta- tion Agency, 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 trans- portation 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 pas- senger 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 ser- vice 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 drop-off 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 2 Specifically, the ADA regulation states that transit agencies must provide service to “individuals with disabilities that is com- parable to the level of service provided to individuals without disabilities who use the fixed route system.” 2 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. 3. We present results from real-world data and a pilot study from a mid-sized southern city in the USA. 2 Background (a) Paratransit ridership (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. 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., 2022a, 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., 2022a], 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 on-demand ride-pooling services, paratransit services have con- straints 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. 3 Travel time constraint: In the case of our partner agency (and many other public transit agencies that operate paratransit services), 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 para- transit 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 Dis- abilities 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 Figure 2a and 2b, respectively. 3 Model The core decision-making and computational problem that transit agencies must tackle for operating paratransit ser- vices 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 real-time. 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. [2022], 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 off-the-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 [2002] 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 1: 4 X X min cijk xijk (1) k∈K (i,j)∈Ak Subject to the following sets of constraints M : X X xijk = 1, ∀i ∈ P (2a) k∈K j∈Nk ∪{d(k)} X X xijk − xj,n+i,k = 0, ∀k ∈ K, i ∈ Pk (2b) j∈Nk j∈Nk X xo(k),jk = 1, ∀k ∈ K (2c) j∈Pk ∪{d(k)} X xijk − i∈Nk ∪{o(k)} X xjik = 0, ∀k ∈ K, j ∈ Nk (2d) i∈Nk ∪{d(k)} X xi,d(k),k = 1, ∀k ∈ K (2e) i∈Dk ∪{o(k)} xijk (tik + si + τijk − tjk ) ≤ 0, ∀k ∈ K, (i, j) ∈ Ak (2f) ai ≤ tik ≤ bi , ∀k ∈ K, i ∈ Vk (2g) tik + τi,n+i,k ≤ tn+i,k , ∀k ∈ K, i ∈ Pk (2h) xijk (yaik + ℓaj − yajk ) = 0, ∀k ∈ K, (i, j) ∈ Ak (2i) ℓai ≤ yaik ≤ Cak , ∀k ∈ K, i ∈ Pk (2j) 0 ≤ yan+i,k ≤ Cak − ℓai , ∀k ∈ K, n + i ∈ Dk (2k) xijk (ywik + ℓwj − ywjk ) = 0, ∀k ∈ K, (i, j) ∈ Ak (2l) ℓwi ≤ ywik ≤ Cwk , ∀k ∈ K, i ∈ Pk (2m) 0 ≤ ywn+i,k ≤ Cwk − ℓwi , ∀k ∈ K, n + i ∈ Dk (2n) yao(k),k = 0, ∀k ∈ K (2o) ywo(k),k = 0, ∀k ∈ K (2p) xijk ∈ {0, 1}, ∀k ∈ K, (i, j) ∈ Ak tik ∈ R≥0 , ∀k ∈ K, i ∈ Vk yaik ∈ R≥0 , ∀k ∈ K, i ∈ Vk ywik ∈ R≥0 , ∀k ∈ K, i ∈ Vk 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 that 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 (2i–2l) 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: xijk = 1 ⇒ tjk = max (aj , tik + si + τijk ) (i, j) ∈ Ak 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. 5 Symbol Description n number of transportation requests; N the set of nodes; P the set of pick-up nodes; D the set of drop-off nodes; ℓai number of ambulatory passengers at node i; ℓwi number of wheelchair passengers at node i; Cak ambulatory capacity of a vehicle; Cwk wheelchair capacity of a vehicle; K the set of available vehicles; τijk travel time between distinct nodes; cijk cost between distinct nodes; si service time at node i; Table 1: Notation Table VIEW SCHEDULE EDIT SCHEDULE (Human supervision) Validate Schedule schedule list With actions, addresses & times Drag and drop cards Figure 3: Supervisors can edit the schedule and override the machine-generated schedule. 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., 2022b] 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 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. 3.2.1 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 6 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 real-world 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 real-time (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. Upon acceptance, we will release our code and a sample of simulated data. 4.1.1 Real-world paratransit data We run experiments for all solvers with real-world paratransit data from CARTA from August 13th, 2023. The para- transit fleet consisted of 15 vehicles available with schedules staggered between morning and afternoon shifts accord- ing to CARTA’s driver and vehicle availability and a total of 125 passengers. Each request in the dataset consisted of a geo-coordinate (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’s 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. Shared Passengers Solver VMT VDM VMT/PMT Violations Rate Served Offline Solver 990 252 1.03 85% 125 0 PTA - Offline 1278 538 1.31 53% 125 12 Online Solver, 90%/10% split 1145 301 1.19 83% 125 0 Online Solver, 80%/20% split 1157 370 1.21 79% 125 0 Online Solver, 70%/30% split 1220 454 1.27 65% 125 0 Online Solver, 60%/40% split 1172 384 1.35 76% 115 0 Online Solver, 50%/50% split 1142 437 1.39 59% 110 0 Table 2: Solver Metrics recorded for paratransit data on compared with PTA’s real schedule. VMT: Vehicle Miles Travelled, VDM: Vehicle Detour Miles, VMT/PMT: Vehicle Miles Travelled to Passenger Miles Travelled, Shared Rate: percentage of trip requests that shared their trip with another passenger, Violations: number of time window constraint violations. We observe that the proposed offline solver serves all passengers without any violations, with significantly fewer detour miles and a significantly higher shared rate, thereby reducing the total number of miles the vehicles have to drive. 7 4.1.2 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. 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. Shared Passengers Pilot Solver VMT VDM VMT/PMT Rate Served PTA 1531 601 1.41 61% 159 Pilot 1 Offline Optimizer 1175 300 1.07 86% 159 PTA 1269 517 1.27 68% 129 Pilot 2 Offline Optimizer 1061 281 1.06 84% 129 Table 3: Pilot Metrics recorded for system testing for both deployments. VMT: Vehicle Miles Travelled, VDM: Vehicle Detour Miles, VMT/PMT: Vehicle Miles Travelled to Passenger Miles Travelled, Shared Rate: percentage of trip requests that shared their trip with another passenger. We observe that the proposed offline solver serves all passengers without any violations, with significantly fewer detour miles and a significantly higher shared rate, thereby reducing the total number of miles the vehicles have to drive. 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 ap- proach 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 8 Figure 4: CARTA driver using the proposed algorithm to follow the manifest during a real-world deployment. 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 gen- erated 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.” 9 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 genera- tion, 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 on work sponsored by the National Science Foundation under grant CNS-1952011 and the Department of Energy under Award Number DE-EE0009212. References Eda Beyazit. Evaluating social justice in transport: lessons to be learned from the capability approach. Transport Reviews, 31(1):117–134, 2011. David Harvey. Social justice and the city, volume 1. University of Georgia press, 2010. Federal Highway Administration. Status of the nation’s highways, bridges, and transit: 2002 conditions and perfor- mance report. https://www.fhwa.dot.gov/policy/2002cpr/, 2003. Christina Plerhoples Stacy, Yipeng Su, Eleanor Noble, Alena Stern, Kristin Blagg, Macy Rainer, and Richard Ezike. Access to opportunity through equitable transportation: Lessons from four metropolitan regions. Technical report, Urban Institute, 2020. Kevin DeGood. Aging in place, stuck without options: Fixing the mobility crisis threatening the baby boom genera- tion. Technical report, Transportation for America, 2011. United Nations. Sustainable development goals. https://www.un.org/sustainabledevelopment/health/, 2020. Aditi Shrikant. Why US public transportation is so bad — and why Americans don’t care. https://www.vox.com/ the-goods/2018/9/26/17903146/mass-transit-public-transit-rail-subway-bus-car, 2018. G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management Science, 6(1):80–91, 1959. doi: 10.1287/mnsc.6.1.80. URL https://doi.org/10.1287/mnsc.6.1.80. Jan K Lenstra and AHG Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11(2): 221–227, 1981. Paolo Toth and Daniele Vigo. The vehicle routing problem. Society for Industrial and Applied Mathematics, 2002. Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1):1–11, 2013. Claudia Archetti, Dominique Feillet, Andrea Mor, and Maria Grazia Speranza. Dynamic traveling salesman problem with stochastic release dates. European Journal of Operational Research, 280(3):832–844, 2020. Michael Wilbur, Salah Kadir, Youngseo Kim, Geoffrey Pettet, Ayan Mukhopadhyay, Philip Pugliese, Samitha Sama- ranayake, Aron Laszka, and Abhishek Dubey. An online approach to solve the dynamic vehicle routing problem with stochastic trip requests for paratransit services. In ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS). IEEE, April 2022a. Waldy Joe and Hoong Chuin Lau. Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. In Proceedings of the international Conference on Automated Planning and Scheduling, volume 30, pages 394–402, 2020. 10 Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. On-demand high- capacity ride-sharing via dynamic trip-vehicle assignment. Proceedings of the National Academy of Sciences, 114 (3):462–467, 2017. Youngseo Kim, Danushka Edirimanna, Michael Wilbur, Philip Pugliese, Aron Laszka, Abhishek Dubey, and Samitha Samaranayake. Rolling horizon based temporal decomposition for the offline pickup and delivery problem with time windows. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI-23), 2023. Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, Abhishek Dubey, Samitha Sama- ranayake, and Aron Laszka. Offline vehicle routing problem with online bookings: A novel problem formulation with applications to paratransit. In 31st International Joint Conference on Artificial Intelligence (IJCAI), July 2022. Michael Wilbur, Salah Uddin Kadir, Youngseo Kim, Geoffrey Pettet, Ayan Mukhopadhyay, Philip Pugliese, Samitha Samaranayake, Aron Laszka, and Abhishek Dubey. An online approach to solve the dynamic vehicle routing problem with stochastic trip requests for paratransit services. In 2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS), pages 147–158. IEEE, 2022b. OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org, 2017. Geoff Boeing. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65:126–139, 2017. Kentaro Toyama. Geek Heresy: Rescuing Social Change from the Cult of Technology. PublicAffairs, 2015. 11 S MART T RANSIT.AI: A DYNAMIC PARATRANSIT AND M ICROTRANSIT A PPLICATION∗ Sophie Pavia David Rogers Amutheezan Sivagnanam Vanderbilt University Vanderbilt University The Pennsylvania State University sophie.r.pavia@vanderbilt.edu david.rogers@vanderbilt.edu amutheezan@psu.edu Michael Wilbur Danushka Edirimanna Youngseo Kim Vanderbilt University Cornell University Cornell University michael.p.wilbur@vanderbilt.edu ke233@cornell.edu yk796@cornell.edu Ayan Mukhopadhyay Philip Pugliese Samitha Samaranayake Vanderbilt University CARTA Cornell University ayan.mukhopadhyay@vanderbilt.edu philippugliese@gocarta.org samitha@cornell.edu Aron Laszka Abhishek Dubey The Pennsylvania State University Vanderbilt University laszka.aron@gmail.com abhishek.dubey@vanderbilt.edu A BSTRACT New rideshare and shared mobility services have transformed urban mobility in recent years. Such services have the potential to improve efficiency and reduce costs by allowing users to share rides in high-capacity vehicles and vans. Most transit agencies already operate various ridepooling services, including microtransit and paratransit. However, the objectives and constraints for implementing these services vary greatly between agencies and can be challenging. First, off-the-shelf ridepool- ing formulations must be adapted for real-world conditions and constraints. Second, the lack of modular and reusable software makes it hard to implement and evaluate new ridepooling algorithms and approaches in real-world settings. We demonstrate a modular on-demand public transportation scheduling software for microtransit and paratransit services. The software is aimed at transit agen- cies looking to incorporate state-of-the-art rideshare and ridepooling algorithms in their everyday operations. We provide management software for dispatchers and mobile applications for drivers and users and conclude with results from the demonstration in Chattanooga, TN. 1 Introduction Public transit systems are crucial for economic growth, equitable distribution of benefits, and community connectivity. Offering cost-effective commuting options not only catalyzes economic development and mitigates poverty through better access to employment opportunities but also fosters social inclusivity and community cohesion [Sørensen, 2018, O’Sullivan and Jackson, 2002, Taylor and Morris, 2015]. While the benefits of public transportation are apparent, operational challenges and commuters’ personal choices lead to a wide gap between the promise and the reality of shared public transportation in our communities. To address these issues, transit agencies strive to transform their operations by introducing innovative multi-modal services like on-demand dynamic-route microtransit to complement traditional fixed-line transit [Lu et al., 2023, Shaheen and Wong, 2022, Friedman and Friedman, 2021]. ∗ This is a preprint version for the paper accepted in the Demo track at the International Joint Conference on Artificial Intelligence (IJCAI), 2024 Figure 1: (Left) Operations manager web application: allows the transit agency to manage clients, take bookings, update route manifests, and monitor real-time operations and dispatching. (Right) DVRP Interface: we defined a common interface for the input and output for incorporating real-time ride-pooling algorithms within SmartTransit-AI so that new algorithms can be quickly adapted and included within the software framework. In recent years, several communities have experimented with such systems; however, while some of the pilots have had promising results [Cohen, 2019], most of them had to shut down. A recent report [Westervelt et al., 2018] lists (among others) the following critical lessons learned from these failures: (a) the need for passenger-centric and flexible transit design, (b) avoiding uncertainty in service quality, (c) focus on sustainable operational plans, and (d) transparency in software design and seamless maintenance. Given the complexity of this process, most agencies have to either design their own software or manually augment their workflows to adapt existing off-the-shelf software. This ad-hoc process makes it hard for researchers to implement new ridepooling algorithms and approaches in real-world settings. 2 SmartTransit-AI In collaboration with the Chattanooga Area Regional Transportation Authority (CARTA), our team has designed a community-centric paratransit and microtransit service that improves the status quo by integrating novel algorithms and focusing on modular design and the ability to customize the system. From the city’s perspective, microtransit services are available to all residents and can be considered a low-cost extension of their public transit system. They can be used for direct point-to-point travel and in hybrid transit systems where the vehicles shuttle passengers to and from fixed-line transit [Salazar et al., 2018]. Similarly, paratransit is a ridepooling service run by a transit agency that provides curb-to-curb service for passengers who are unable to use fixed-route transit (e.g., passengers with disabilities). The software includes three interfaces—an operations manager web application for dispatchers, a vehicle operator (or driver) mobile application, and a user mobile application for residents to book requests (fig. 1). The operations manager interface allows the transit agency to manage clients, take bookings, update schedules, and monitor real-time operations. It also includes optimization components that can automate or recommend trip-to-vehicle assignments. In microtransit and paratransit, requests can be for some day in the future, which we refer to as ahead-of-time requests, or can be for the same day. To tackle this challenge, the tool has components to solve both offline and online vehicle routing problems (VRPs). The solvers are made available by a REST API, which means for a new solver to be incorporated, the solver endpoint needs to be changed in a configuration file. A visual representation of the real-time dynamic VRP (DVRP) interface is shown in Figure 1 (right). The input consists of a manifest and the status of each vehicle in the fleet that is currently active. The manifest is an ordered list of locations the vehicle will visit. Each location is either a pickup or dropoff for a passenger and the estimated arrival time is the calculated time to arrive at said location. The status of the vehicle includes the current location of the vehicle, the passengers currently onboard as well as any constraints on the vehicle. Example vehicle-level constraints include the time in which the vehicle can leave the depot or must return to the depot as well as capacities for different types of passengers. The locations in the manifest correspond with existing trip requests that are currently or scheduled to be serviced. Each request has a pickup and dropoff location and any constraints applied to that request. Common constraints may be time windows for which the pickup or dropoff must be serviced, the number of passengers on this trip as well as types of passengers (wheelchair passengers, ambulatory passengers). The new trip request or set of new trip requests includes the same information as the existing requests, but these requests are not yet assigned to any vehicle. 2 The goal of the DVRP solver is to assign these new trip requests to vehicles in a way that does not violate any constraints and optimizes an objective function. Both the constraints and objective function are set by the transit agency through a SmartTransit-AI configuration file. For routing, we generate a travel time and distance matrix indexed by Node ID. A Node ID is the set of all pickup and dropoff locations for both existing and new requests as well as the depot. In this way, the DVRP solver is provided with travel times and distances to be used when optimizing the manifests without having to rely on an external shortest path module. Finally, the DVRP solver must return the updated set of manifests, which is processed by the SmartTransit-AI backend and pushed to the various SmartTransit- AI frontends (driver applications so that drivers have the updated routes as well as the operations manager web UI). The offline VRP interface follows a similar structure, except all requests are considered new (unassigned) requests, and the vehicle manifests are initially empty. The interfaces rely on a set of APIs to manage the various automated processes and to help inform decision-making. We are running a customized Open Source Routing Machine (OSRM) deployment that is augmented with historical traffic conditions. For same-day operations, we rely on Mapbox for routing with real-time traffic conditions. For managing bookings, we integrated Google Maps Places Autocomplete in the text inputs related to addresses, and we used a combination of Mapbox and Google Maps APIs for geo-encoding. The primary data store is MongoDB, and we utilize Google Pub-Sub for pushing updates to drivers and users as well as processing real-time vehicle locations. The software is deployed on the Google Cloud Platform (GCP). Together, these optimization APIs allow us to support a number of algorithms—first, for generating day-ahead man- ifests (mapping of bookings to trips) and the second, a same-day real-time solver that adds real-time bookings to ongoing and future trips considering future uncertainty. The day-ahead algorithm is the offline vehicle routing problem with online bookings—a reinforcement-learning inspired technique that provides the ability to create coarse solutions as each request from a client arrives on the phone (at least a day before). The technique uses a simulated-annealing method as the any-time algorithm to reduce the size and complexity of the action space [Sivagnanam et al., 2022]. A variation of the approach utilizing Google-OR tools has been included in the system to ensure redundancy. A third version of the day-ahead system is based on rolling horizon temporal decomposition that improves scalability. Our common interface allows users to easily switch between any of the available algorithms, as well as integrate new al- gorithms on demand. Finally, the same-day algorithm is handled as a dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests. Our approach is called MC-VRP [Wilbur et al., 2023] (Monte Carlo tree search based solution for vehicle routing problem). We model the DVRP as a route-based Markov decision process (MDP) [Ulmer et al., 2017]. Given an arbitrary state of the MDP, we use generative models over customer requests and travel time to simulate the environment under consideration, enabling us to use Monte Carlo tree search [Kocsis and Szepesvári, 2006] to find promising actions for the state. A key innovation of our system is the ability to allow for human overriding of generated schedules. This is important because transit experts often have unspecified constraints and customer preferences that are known but not expressed mathematically. To support such use cases, our system enables the operators to create views that enable drag and drop of scheduled trips while ensuring that all constraints are checked and information provided to ensure that a particular edit will conform to the requirements. 3 Real-time Operations We also provide two mobile applications that can run on a tablet or phone. The driver application allows vehicle operators (or drivers) to manage their daily routes. It allows a driver to log in and get their route for the day, which is a schedule of users to pick up and drop off. The driver application interacts directly with our backend to get up-to-date routes and communicate with the dispatchers as drivers service their schedules. GPS locations are published every second to our backend so the operations managers, dispatchers, and real-time algorithms can access vehicle locations and status in real-time. Lastly, we provide a mobile application for users to schedule trips through their smartphone. Users can also call to request trips over the phone which are then booked through the operations manager interface. Figure 2 shows a screenshot of the real-time view in the web operations application while a driver serviced route 15 on August 10, 2023. This real-time view shows the current location of the vehicle servicing the route and the status of all locations in the route manifest. We also provide real-time tags to alert the operations team when 1) a violation occurs, 2) there was a no-show because the rider did not board at a pickup location, and 3) warnings related to future locations where the vehicle is anticipated to arrive late and may be a potential violation. As shown in Figure 2, the driver was late to the first pickup location but quickly could make up time and remain on schedule for the subsequent locations. This functionality allows the operations team to know what violations have occurred in real time and anticipate future delays. 3 Figure 2: A screenshot of the real-time operations view in the operations management web application while a driver served route 15 on August 10, 2023 (names and locations are hidden) 4 Demonstration To demonstrate the system, we will use a generative demand model that generates synthetic trip requests based on pre-collected movement and job census data. Each trip is represented as an origin-destination (OD) pair with a start and end location and the requested time of day. The generative demand model generates an OD dataset for a day, and the number of trips in the dataset can be scaled up or down based on the use case. The model can scale over 80,000 requests daily, capturing a significant percentage of regional trips. Further, we have the capability to analyze previously collected real-life pilot data for both paratransit and microtransit operations. The paratransit operations have strict time window constraints for two types of passenger requests. 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 appointments where a passenger must be dropped off before their appointment and must be picked up no earlier than one hour before the appointment. Additionally, each vehicle had two capacity constraints - no more than 8 ambulatory passengers and 2 wheelchair passengers could be on a vehicle at any given time. Key metrics we will demonstrate are as follows for two days of data when we ran our initial test pilot: August 3, 2023, and August 10, 2023: our solvers reduced VMT by 356 miles on August 3, 2023, and by 236 on August 10, 2023. We use Vehicle Miles Travelled to Passenger Miles Travelled VMT/PMT as the metric to represent normalized efficiency, where PMT was the total shortest path distance between origin and destination for all trip requests. There was a 24% and 17% improvement in VMT/PMT over CARTA’s initial 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 (86% compared to 61% for August 3, 84% compared to 68% for August 10). 5 Conclusion We demonstrate a cloud-based on-demand transportation scheduling software for microtransit and paratransit services. Our optimization module within the software includes three modular routing algorithms which we evaluate on syn- thetic and real-world data. Our results show that with real-world data, we have a positive impact on utilization and efficiency as we increase the shared rate and decrease the overall VMT/PMT ratio. 4