SmartTransit.AI: A Dynamic Paratransit and Microtransit Application

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 fixedline transit [Lu et al., 2023; Shaheen and Wong, 2022; Friedman and Friedman, 2021].

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-tocurb 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.

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 manifests (mapping of bookings to trips) and the second, a sameday real-time solver that adds real-time bookings to ongoing and future trips considering future uncertainty. The dayahead 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 anytime 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 algorithms on demand. Finally, the sameday 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 and others, 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´ari, 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.

4 Demonstration

To demonstrate the system, we will use a generative demand model that generates synthetic trip requests based on precollected 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. Pickupconstrained 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 synthetic 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.

Acknowledgements

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