Continuous Dynamic Optimization: Impacts on ADA Paratransit Services (2023)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

7   Paratransit Scheduling Technology: A History Continuous dynamic optimization (CDO), as applied to Americans with Disabilities Act (ADA) paratransit services (and other demand-responsive services), is an automated process by which a scheduling/dispatching technology continuously or frequently considers additional trips just booked, changes to booked trips, cancellations, and day-of-service events in solving problems or taking advantage of opportunities. In view of those changes, the CDO process then re-optimizes the assignment of trips to dedicated vehicle runs and to available overflow non-dedicated service providers to achieve the transit agency’s desired balance of service/cost efficiency and service quality. Any research on CDO and how it currently affects ADA paratransit must begin with an underlying understanding of how both paratransit and the computerized scheduling technology that supports it have evolved over the years. Paratransit: The Early Years Paratransit services emerged as a distinct service model in the late 1960s and 1970s. These early services were provided to the general public, were generally known as dial-a-ride services, and were not specialized. As dial-a-ride services became more popular and larger, there was a desire to automate the scheduling process—not only to make it more manageable for staff but also to improve the efficiency and objectivity of the results. Automating this process first required the development of scheduling algorithms that direct the computer to specify how a vehicle should most optimally be routed in a shared-ride, demand- responsive setting, and how trips should optimally be assigned to a fleet of vehicles. The key to this definition is the word optimally and what that means to a transit agency as it considers its goal of achieving a desired balance between service/cost efficiency and service quality. First Computerized Paratransit System In the United States, the path to CDO began at the Massachusetts Institute of Technology (MIT), where a set of scheduling algorithms was first developed between 1967 and 1971 under the direc- tion of Dr. Nigel H. M. Wilson. These algorithms were subsequently used for the Haddonfield (NJ) Dial-a-Ride Demonstration (February 1972 to October 1974). The Haddonfield service is gener- ally recognized as the first dial-a-ride service in the United States to benefit from computerized scheduling. The algorithms used for this scheduling system were later improved upon, again by MIT, as part of the Advanced Dial-a-Ride Algorithms Research Project, and they were subsequently demonstrated in the Rochester, NY, dial-a-ride service in the mid-1970s. C H A P T E R   1 Overview of the Technology

8 Continuous Dynamic Optimization: Impacts on ADA Paratransit Services Section 504 Paratransit as a more specialized transportation service gained more momentum in the United States with the enactment of Section 504 of the Rehabilitation Act in 1973. This law required feder- ally assisted transportation programs to be accessible to people with physical disabilities, including wheelchair users. Section 504 gave transit agencies a choice: they could use accessible buses on their fixed-route system, or they could implement a paratransit service. After the Section 504 implementation requirements were clarified in 1979 by the U.S. Department of Transportation, most transit agencies did one or the other; some did both. But the majority of transit agencies opted to provide paratransit rather than accessible fixed-route service. Thus, with the proliferation of paratransit during the 1980s, there was an increased need for computerized scheduling, and several new paratransit scheduling systems entered the U.S. market. All of these software products provided ways to track customer profiles, identify the customer when booking trips, schedule a trip to a run, print the driver manifests, input service data (as written by the driver on the printed manifest), and generate reports. But several of the products did not have a computerized scheduling function, so scheduling was essentially done manu- ally, one trip at a time. Other companies in both the United States and Canada, however, were developing software systems that automated the scheduling process, as had been demonstrated in Haddonfield and Rochester. The companies also converted the software to run on DOS and UNIX/XENIX (multi-user) personal computers, as described in the next section. National Paratransit Scheduling Software Systems Emerge During the early 1980s, a company called OnLine Data, based in Scottsdale, AZ, developed PASS, the first DOS-based computerized product for paratransit. Meanwhile, two Canadian com- panies, Trapeze and GIRO, developed their own multi-user computerized scheduling systems for paratransit. Trapeze, which started out as a family business and then became part of UMA Engineering and later Constellation Software, acquired OnLine Data in 1986 to get the lion’s share of the U.S. market. Trapeze then rewrote the OnLine Data product as a Windows application and adopted PASS as the name of its paratransit scheduling system. Nevertheless, the degree to which the Trapeze PASS algorithms drew upon the original algorithms from the OnLine Data product remains unclear. GIRO entered the U.S. market via an agreement with a company called Multisystems, based in Cambridge, MA, that had ties to MIT. When Multisystems ended its marketing agreement with GIRO a few years later, Multisystems developed its own paratransit scheduling system, MIDAS, which in large part used and further advanced the same scheduling algorithms that were demonstrated in Rochester in the mid-1970s. One of the features of the computerized paratransit scheduling systems from Trapeze and Multisystems that differentiated them from other paratransit scheduling systems of the 1980s was that they supplied ways for transit agency staff to directly configure the scheduling parameters to reflect both the environment in which the service operates and the balance between service/cost efficiency through the use of costing weights (described in the next section). While it was certainly possible to tailor the scheduling parameters of other computerized scheduling systems that were then in use in the United States, an installer or a programmer had to do it. Americans with Disabilities Act of 1990 In 1990, the enactment of the ADA brought new requirements for public transit agencies, eliminating the choice of services that was available under Section 504. The ADA requires not

Overview of the Technology 9   only that all transit vehicles used for fixed-route service be accessible to people with disabilities but also that transit agencies provide “ADA complementary paratransit” for people who cannot access or use accessible fixed-route service because of their disability or disabilities. Also, the term disability was not limited to physical disabilities as it was with Section 504. With the new require- ment came associated clarifying regulations and guidelines provided by the FTA. Since 1991, all transit agencies with local fixed-route services have been obligated to provide ADA paratransit service at a minimum where and when they provided local fixed-route service. For many transit agencies, this was a new service. Many of them sought the help of computerized scheduling systems, especially because the per-trip cost of providing such a service was far higher than the per-trip cost of providing fixed-route service, and the demand for ADA paratransit grew rapidly. Automated paratransit scheduling was therefore a way not only to mitigate what would potentially be a very labor-intensive process (if done manually) but also to improve the service/cost efficiency of the service, especially when budgets were constrained. Not surprisingly, several new computerized scheduling systems entered the market during this decade. Capabilities Needed for Paratransit Scheduling During the 1990s, and up until the advent of CDO in the late 2000s, paratransit scheduling focused on the need to handle next-day scheduling as required for ADA paratransit as well as the scheduling of advance reservations and recurring subscription trips (also called standing orders). While the policy of some transit agencies allowed only next-day booking for their ADA paratransit services and still do, most transit agencies adopted advance reservation policies allowing ADA paratransit customers to make reservations up to a certain number of days in advance. Initially, many of these transit agencies had policies allowing customers to book trips up to 14 days (or more) in advance. This policy, however, prompted many customers to make placeholder reservations, which in turn led to a high level of cancellations and late cancellations, which damped down productivity. Over the years, most transit agencies shortened their advance reservation period to a maximum of three to seven days to reduce the number of placeholder reservations. Most computerized scheduling systems can support both of the following: • Real-time scheduling. Trips are assigned to a run based on suggestions provided by the system so that a confirmed scheduled pickup or pickup window can be given to customers immediately after their trip request has been entered into the scheduling system. The system’s suggested solutions are based on the scheduling algorithms and parameters configured by the transit agency. An agency can also configure the number of solutions shown to the booking agent: as few as one and as many as five are common. • Batch scheduling. All trips (or selected trips) are optimized by the system, again according to the scheduling algorithms and parameters configured by the transit agency, which sometimes means relaxing some of the parameters. Most systems allow a scheduler to do a batch schedule on command (at any time). With some systems, however, a scheduler can automate batch scheduling to run at certain times and certain days, such as three days out, without manu- ally having to invoke the batch-scheduling process. Some systems also allow a scheduler to configure different batch processes tailored to different sets of parameters (both of which set the table for CDO). Most transit agencies with computerized scheduling systems do both real-time scheduling and batch scheduling. The ability to do both lies with systems that allow customers the opportu- nity to book trips well in advance; however, an optimal solution seven days in advance may be very different from the optimal solution the day before the trip when all trips have been booked and a batch optimization is run.

10 Continuous Dynamic Optimization: Impacts on ADA Paratransit Services Some transit agencies with computerized scheduling systems direct their booking agents to do real-time scheduling only. Most of these agencies argue that the batch processes do not do as good a job as good schedulers do. Their job is then to do the following: • Schedule any trips that were not initially scheduled by the booking agent. • Fix any tightly scheduled runs by transferring trips to a run with a looser schedule. • Fix any scheduling issues they happen to see. Underlying the decision to avoid batch scheduling is a distrust in how the scheduling para- meters have been set for that agency (or for a particular process). For such agencies, the scheduling parameters and cost weighting may not have been tuned properly, giving credence to the transit scheduling staff’s claims that they can do a better job. However, these parameters are, in most cases, the same parameters that are being used to provide real-time scheduling solutions. Other transit agencies do not use real-time scheduling at all. Instead, their booking agents enter the trip requests into the paratransit scheduling/dispatching software and tell the customer that a confirmed pickup time or window will be forthcoming; as long as this happens on the day before the trip date, the agency meets the FTA’s minimum requirement. Still other agencies do real-time scheduling but only to ensure that there is room for the trip. If there is no room, agencies negotiate an alternative with the customer. In these cases, too, a confirmed pickup time or window is not given to the customer while he or she is still on the phone. In both cases, the transit agencies then rely on batch scheduling after the reservation period is over and then manually schedule those trips that fall out of the batch process as unassigned. The confirmed pickup time or window for the next day is then communicated to the customer typically that evening via an interactive voice recognition (IVR) system, which calls or texts customers with the confirmed pickup time/window information for all trips to be served on the following day. Prior to the widespread use of IVR for such notifications, it was common to simply grant callers a pickup window based on their request time rather than to negotiate it using predicted vehicle movements, thereby locking in what were often inefficient commitments. All computerized paratransit scheduling systems handle subscription trips similarly. Master schedules, also called daily templates, are established for each day of the week. For each schedule, the day’s runs are loaded into the system, and subscription trips are then assigned to these runs. For example, a trip for a dialysis patient with the same appointment time on Monday, Wednesday, and Friday and going to/from the same origin would be scheduled separately in the Monday master schedule, in the Wednesday master schedule, and in the Friday master schedule. It is not uncommon for a scheduler to do this manually in order to schedule the trip onto the same run on each of the three days. When the dated schedule for Monday, July 11, 2022, is then created (before advance reservation trips can be booked), the scheduler then copies all the runs for the Monday schedule and any trips scheduled to those runs into the July 11 dated schedule. Therefore, when an agent books the first advance reservation trip for July 11, the only trips that appear on the schedule are the subscription trips. When the dated schedules are later batched as described, some software systems allow the scheduler to anchor the subscription trips in place or, to put it another way, to select only the advance reservation trips to optimize. With some systems, schedulers may elect to unschedule the sub- scription trips altogether before the entire set of trips is optimized. The flexibility to do these kinds of batches—either with a live dated schedule or in a practice area to see the results of an experiment—is a key feature of many computerized systems. Continuous Dynamic Optimization Capabilities Emerge CDO as a standard and featured capability was introduced in the mid- to late 2000s by both Trapeze and Ecolane, a Finnish company that honed its own scheduling algorithms in Finland

Overview of the Technology 11   and saw a market for its paratransit scheduling and dispatching in the United States. While many of Trapeze’s paratransit users have not taken advantage of its service-day optimization capability, Ecolane promoted its CDO capability as a strategic part of its marketing tactics, and it worked. Scores of transit agencies, especially small to midsize agencies, bought Ecolane in large part because of its CDO capability. As a result, use of CDO in the scheduling and dispatching function became much more common in support of ADA paratransit services. From 2010 to 2019, CDO technology got an additional jumpstart with the introduction and widespread use of tablets, in many cases, replacing mobile data terminals (MDTs). Until then, CDO relied on the geo-stamping function of MDTs when a driver performed each event; however, the functionality of these MDTs was limited. In comparison, the driver software loaded onto the tablets provided guards or warnings against drivers performing an event early and forgetting to perform an event. (Transit agencies also found the tablets easier to replace than MDTs if a related problem was found during the pre-trip inspection, which in turn resulted in fewer downed vehicles. Drivers appreciated the navigation assistance that the tablets provided.) As more and more transit agencies replaced MDTs with tablets, the agencies found that the data were more accurate, which led more agencies to try CDO during the service day. In the past few years, CDO for ADA paratransit services has been given another boost. A few microtransit technology vendors whose products were developed for on-demand microtransit services—notably Via Mobility, Spare Labs, and RideCo—added advance reservation and sub- scription booking capabilities. The vendors also modified their software to support ADA para- transit services. As a result, their CDO capabilities (which were an inherent need of microtransit) are now also being used to support service-day optimization for ADA paratransit services. This function is further discussed later in this chapter. How Scheduling Parameters and Cost Weighting Work Preliminaries: Geographic Information System Map and Calculations of Distance, Speed, and Travel Time To understand how CDO works, it is important to first understand how paratransit scheduling parameters generally work. It is also important to understand how scheduling systems figure out the speed of vehicles and how many miles a vehicle will travel between two points. Together, this information will tell the system how long it takes to travel between two points. Underlying the paratransit and dispatching software is a geographic information system (GIS) map of the service area, which is used to geocode locations either by address or in some cases by a point and click when the address is unknown. Some of the early paratransit scheduling systems used triangulation, basing the distance on the straight-line distance and adding in a factor (often 1.3) to reflect the truer distance a vehicle might have to travel. The evolution of triangulation led to enhanced triangulation, which took natural barriers, such as rivers and a limited number of bridge crossings, into consideration. In essence, there would be two calculations—one from the trip origin to the bridge and one from the bridge to the destination. Within the last decade, though, street routing as a capability of the underlying GIS map has become much more prevalent, provid- ing a more accurate estimate of miles traveled. As advancements were made in calculating distance, so too were they made in calculating the average speed of a vehicle. Some of the early paratransit scheduling systems provided the ability to input one speed systemwide. As the systems evolved, some provided the ability to categorize speeds by road category, such as highways, arterials, and local streets. In other systems, users were also able to carve out an area in the underlying map (by defining a polygon) and associate a completely separate speed or a factor of the overall systemwide speed that would then be applied to trips through the carved-out area.

12 Continuous Dynamic Optimization: Impacts on ADA Paratransit Services While these advances helped, several shortcomings persisted, including the inability to differ- entiate speeds by day and direction of travel. This problem was solved in the past decade through machine learning or artificial intelligence. Most of the prominent paratransit scheduling and dispatching software systems that are commercially available in the United States today do this. In essence, these systems maintain a database of all trips including day of the week, time of day, and general direction. Thus, when a customer calls to request a trip from point A to point B for next Tuesday at 2:00 p.m., the systems look at the actual speeds for all similar trips on Tuesdays at 2:00 p.m. and trips that are going in the same general direction; the system uses that average speed to calculate how long it would take to travel between the origin and destination or to a point in between if a shared ride is being considered by the system. Moreover, a nuanced option of this methodology, available with some systems, enables transit systems to weight more heavily in the calculation the speeds from more recent trips. In this way, new factors that cause traffic congestion (e.g., a road construction project) can be considered in the calculation of speed. Parameter Tuning and Cost Weighting With the basics of travel-time calculation explained, it is now important to understand how the scheduling parameters can be set, or tuned, to achieve a particular desired balance between service/cost efficiency and service quality. In paratransit, these two service characteristics have an inverse relationship. As a system becomes more productive, it serves more trips in a given amount of time; a schedule jammed with trips, on-time performance is bound to suffer. Conversely, a service is typically able to meet, if not exceed, on-time performance standards if the schedule is loose and has a lot of slack time. Most transit agencies lean one way or the other. It is fairly common for agencies with ADA paratransit services to strive to be as productive as possible (as good stewards of public funds) without compromising service standards and while operating within often-limited resources (e.g., drivers, vehicles, and budget). Within the context of the paratransit scheduling system, the balance between efficiency and quality can be achieved by controlling how the system schedules. This, in turn, is done by weighting the scheduling parameters to reflect their importance. However, tuning the parameters to reflect the characteristics of the local geography and road network, and achieving the particular balance are not easy tasks and often require itera- tive, time-consuming attempts (in a test area) until an optimal solution is found. For example, most paratransit scheduling systems have a way to define the span of the pickup and drop-off windows. The greater the span of the window, the more flexibility a scheduling system has to be productive and on time. However, a narrower window is more convenient for the customer, but it adversely affects productivity and may cause a transit agency to revise its internal/contractual standard for on-time performance. Another set of parameters that affects productivity is the defined loading and unloading time for ambulatory and non-ambulatory customers. The less time scheduled for loading and unload- ing passengers, the more productive the service. However, if the load and unload times do not accurately reflect the longer time incurred by most customers in boarding and alighting a vehicle, the vehicle will fall behind its schedule and on-time performance will be adversely affected. It is important that a transit agency understands the possible outcomes of such decisions, including the impact on customers who need to be at their destination at a certain time. Loading and unloading time is a parameter that some of the newer technologies calculate for an individual based on machine learning—similar to the calculation of trip-specific speed described previously. Other parameters that put a premium on service/cost performance include the following: • The minimization of total miles traveled. • The minimization of deadhead miles traveled (i.e., with no passengers on board). • Shared rides.

Overview of the Technology 13   • The minimization of vehicle runs, revenue service hours, or both (within work rules). • Stretching of the confines of the on-time pickup window, the drop-off window, or both. For each parameter, some systems allow the user to identify how important each service factor is. For example, if a transit agency is consciously striving for service efficiency, it might stress the importance of all of the parameters in the preceding list. If, in contrast, the transit agency is striving for a high on-time performance, the agency would indicate that the first four parameters are as important or less important. Another parameter introduced by at least one vendor is the concept of waypoints, particularly in large areas. Waypoints, which can be assigned to each vehicle, keep vehicles in the same areas of deployment, all else being equal. The idea is that by not sending a vehicle all over the service area, deadheading can be minimized, and productivity can be maximized. This concept is particularly relevant to service models that have centralized scheduling (as performed by the transit agency, broker, or call center manager) and multiple zoned carriers. Virtually all of the paratransit scheduling/dispatching systems also include parameters that focus on service quality. Examples include the following: • Not exceeding a maximum onboard time. Some systems are linked to transit agency trip- planning software to ensure that the travel time for a particular trip does not exceed the travel time of the same trip made on local fixed-route transit. • Minimizing backtracking or zigzagging to serve other trips. A transit agency can identify how important these parameters are. If on-time performance and the customer’s service experience are important to the transit agency, staff will weight them heavily. In contrast, if service/cost efficiency is more important, the transit agency might de-emphasize the importance of these two parameters. With many paratransit systems, the parameter settings described thus far in this section are not “yes or no” options; instead, transit agencies are given the opportunity to weight the importance of the parameters either as a numerical value or as a slide bar with more important and less important on the two ends of the bar. The trick—which can be an art form—is for the transit agency to develop the settings that are right for itself. This process often takes time because it involves experimenting with different settings. Indeed, how the settings of different parameters are set and contrasted with one another can have a profound effect on how trips are scheduled. When a customer calls to make an advance reservation and the booking agent asks the system to suggest some solutions (real-time scheduling), or when a scheduler instructs the system to run a batch-schedule optimization, the system first identifies the sets of parameters needed for the job. With some systems, a transit agency can identify different sets of parameters for different types of jobs. With other systems, there is only one set of parameters for all scheduling/dispatching processes. The scheduling system then uses these parameters and develops various permutations, with each solution being scored, or “costed.” The lowest cost translates into the highest score. For individual trip requests, the lowest-cost/highest-score solution is then presented first if more than one solution is requested or by itself if only one solution is requested. Most transit agencies discuss the specifics of the solution(s) with the customer. If the customer accepts the solution, the trip details, including the scheduled pickup time or window, are con- firmed while the customer is still on the phone. With many computerized systems, a specific pickup time is translated into a pickup window, depending on the transit agency’s pickup window policy. Most systems can also schedule a trip based on an appointment or a requested drop-off time; for such requests, a pickup time or window, as scheduled by the system at that point in time, is provided to the customer.

14 Continuous Dynamic Optimization: Impacts on ADA Paratransit Services If the computerized system cannot find a solution, the booking agent can negotiate the trip details with the customer by exploring alternative times plus or minus 60 minutes until a solution is found. Or the trip can be left unscheduled, awaiting a subsequent batch run or the attention of a scheduler (or a late-night/early-morning dispatcher) if batch scheduling is not used. While the trip could also be denied, this is unusual unless the trip is booked on the day before the trip date. Some transit agencies choose not to deny these trips if it is likely that subsequent cancellations or other events may present an opportunity for the dispatcher—or the system via CDO—to fit the trip in somehow. Parameter tuning also plays a large role in batch scheduling. As mentioned previously, most transit agencies use batch scheduling in addition to real-time scheduling, especially late in the day on the day before the trip date and after reservation hours have ended. This is because a trip that is scheduled in advance might be more optimally reassigned to another run or shifted slightly within the run to which it was originally scheduled. Most systems have configurable parameters, or “guards,” to prevent shifting the pickup times of a trip too much, whether by a certain number of minutes or beyond the confirmed pickup window or both. When a scheduler invokes a batch process (or when it is invoked automatically according to a predefined occurrence), the system runs through a myriad of permutations and finally settles on the lowest-cost, highest-scoring solution when considering the entire day’s worth of trips. The batch process can be tailored so that some trips can “float” when re-batched, depending on policies and the transit agency’s commitment to the confirmed pickup window, while other trips are locked down, or “anchored.” A number of trips may fall out of this process as unassigned, especially if a system has capacity constraints. If this happens, a scheduler may relax some of the parameters to schedule more trips on a subsequent batch run, may try to fit in trips manually, or both. The scheduler may also leave the trips for the evening or morning dispatcher to schedule as new holes (created by cancellations) occur, setting the stage for CDO. Overflow Providers and Brokering to Non-dedicated Providers Some ADA paratransit services have one or more overflow providers. The most common are taxi companies, and the less common are livery operators and non-emergency medical transpor- tation (NEMT) providers operating vehicles in a non-dedicated fashion. In some cases, the over- flow providers can operate dedicated runs instead of or in addition to the agency’s drivers. For example, some transit agencies or their prime contractor, if no non-dedicated service providers are available, may assign dedicated runs to another carrier to help the agency meet its Disadvan- taged Business Enterprise goals. But in any case, drivers of overflow providers need to be ADA paratransit certified—that is, trained to proficiency, and drug and alcohol tested—to serve ADA paratransit trips. As documented in TCRP Report 121: Toolkit for Integrating Non-Dedicated Vehicles in Para- transit Service: The main advantage of using a combined service structure that includes both dedicated and non-dedicated services is its cost-effectiveness in dealing with the inherent daily and seasonal fluctuations of demand. By purchasing supplementary non-dedicated services from a third party to cover peak overflow trips [hence, the term overflow provider] or low demand periods, fewer dedicated vehicles are needed. (Nelson\Nygaard Consulting Associates, TWJ Consulting, and RLS and Associates 2007) Non-dedicated services also proved to be an effective resource in serving low-demand areas as well as will-call return trips, reemerging no-show trips, reassigned trips to get a dedicated run back on schedule, and trips that were interrupted because of an accident, breakdown, or other incident.

Overview of the Technology 15   The manner in which traditional paratransit scheduling and dispatching technologies handle scheduling and dispatching to overflow providers on a trip-by-trip basis or in a batch-scheduling process varies, but essentially, the systems were developed to make as much use of the dedi- cated fleet (or fleets in a multi-carrier environment) as possible. The technologies operate on the premise that these runs, typically paid by the hour, are sunk costs. If the system has exhausted the dedicated fleet (at a certain time) in real-time scheduling mode, and if the negotiation between an agency and a customer does not unveil a solution, the trip can be left unassigned or put on the taxi list to be sent to an overflow provider. If the system encounters this situation in a batch- optimization process, the system needs to decide which trips will be scheduled for the dedicated fleet and which trips will be sent to the overflow provider. Generally, the more traditional paratransit scheduling/dispatch systems provide two ways to handle this situation. A trip can be scheduled or assigned according to the following: • A mix of service quality and efficiency parameters determined by the agency. • The cost to the transit agency. If quality/efficiency metrics are used, a transit agency user can apply an additional weight to reflect its preference for relative cost or other policy considerations. Typically, however, trips are assigned to a non-dedicated carrier only if no solution is available within the dedicated fleet. Basing the scheduling assignment on cost instead of efficiency works primarily when the cost is based exclusively on the attributes of the trip and the provider, and not on how the trip fits into a route. In more complex situations, the system supports basic pricing such as flat trip rates, zone rates, and mileage rates but can also accommodate comprehensive pricing rules such as taxi flag drop charges, loading time, deadheading, guaranteed time, and so forth. This pricing can also come into play if there is more than one non-dedicated service provider (i.e., when the specific contract pricing dictates the non-dedicated provider to which a trip must be assigned). Prior to the day of service and regardless of which approach is used, the system might decide— in any given optimization process—to take back a trip that it had already assigned to an overflow provider if a hole opens on a dedicated run because of a cancellation. Links with Trip-Planning Software Another technological breakthrough with paratransit scheduling systems is the establishment of links between these systems and the transit agency’s fixed-route transit trip-planning systems. This link comes into play with ADA paratransit services in two respects: maximum travel times and fares. In complex environments, there may be several fixed-route solutions, sometimes with different fares, to which a paratransit trip is compared. The more advanced paratransit scheduling systems can identify—all in real time when a single trip or a batch run is being considered—the fixed-route options that are comparable to the paratransit trip. The systems identify the lowest onboard travel time standard for that trip and the lowest fare; fares cannot be more than two times the lowest adult local bus fare. How Continuous Dynamic Optimization Works Frequency, Offsets, and Exclusions At least three national paratransit scheduling/dispatching systems have a CDO function as a standard capability, and they all work similarly. In each system, a scheduler is able to set an automated batch optimization to run continuously or at certain configurable intervals (e.g., every

16 Continuous Dynamic Optimization: Impacts on ADA Paratransit Services 30 minutes) beginning at a designated time. That start time is typically the time of the day before the trip date when the schedulers go home for the evening—that is, when the scheduling function is done for the next day. The end time can be set for the end of the service day or, in some systems, earlier when the process is consistently not generating any changes. If the interval is set to every 10 minutes, for example, and it takes more than 20 minutes for the batch optimization process to run, then at the end of the process, the system will immediately start the batch optimization process anew. This sequence explains the term continuous in CDO. If the interval is set to every 30 minutes, and it takes 20 minutes to run the batch optimization process, the process will start every 30 minutes. Moreover, most systems with CDO also have the capability to specify an offset of a certain number of hours and minutes for service-day optimization. This capability removes the next X number of hours or minutes from the re-optimization process. In this way, the optimization process does not change the driver’s itinerary for the next X number of hours or minutes. In addition, a user of these systems has the option of setting up CDO so that it optimizes certain trips while excluding others from the optimization process. For example, a user may opt to exclude from the optimization process trips for which a pickup time has already been confirmed. CDO Response to Real-Time Changes The idea behind CDO is that it responds to changes as they happen. For instance, on the day before the trip date and throughout the service day, there are cancellations, late cancellations, and no-shows. There are runs that are late and runs that have not pulled out on time because of a driver callout or perhaps because the vehicle was downed as a result of a problem found in the pre-trip inspection. In both cases, there might not be a backup driver or vehicle to swap in, so trips need to be moved, which may trigger the additional reassignment of trips later in the day. In a sense, the CDO process identifies problems and opportunities that exist beyond the offset period and fixes problems before they manifest themselves in real time, which could otherwise double the work for dispatchers. The CDO process takes advantage of the opportunities to mini- mize the number of problems that might still occur. Many paratransit services (with a large enough staff) designate a dispatcher—often the lead dispatcher—to do proactive dispatching. CDO auto- mates the proactive dispatching function in an objective way, which in turn enables the dispatch staff to focus on the here and now, because the barrage of problems that they are focusing on is lessened by CDO. If efficiency is lost because a trip on a dedicated vehicle is canceled, the CDO process will attempt to reschedule the trip to another run according to the decision rules discussed previously or to an available overflow provider—whichever is the more efficient option overall. If there is a service mix of dedicated and non-dedicated vehicles (see the previous section, “Overflow Providers and Brokering to Non-dedicated Providers”), the CDO system may decide to assign a trip to the over- flow provider or providers as a way to handle a reemerging no-show or a will-call return, or just to get a run back on schedule. At the same time, the system can also take back a trip that had been assigned to an overflow provider should a hole open up on a dedicated run as a result of a cancel- lation (if this is permitted by the subcontract provisions—that is, in some cases, advance notice of an hour or two is required). Factors Enabling CDO Two factors enable CDO on the day of service. The first is accurate real-time locations of vehicles as supplied by MDTs or tablets in the vehicles. When a driver arrives at a location for a pickup or drop-off, the driver is supposed to log the arrival on the MDT or tablet and again

Overview of the Technology 17   when he or she departs that location, although some transit agencies direct the driver to per- form only one event at each stop. Either way, when a driver logs the event, the location of the vehicle is geo-stamped and time-stamped by the global positioning system. CDO relies on this information. If drivers are not routinely performing these events, or if the events are not being communicated to the system because of malfunctioning hardware, the results of CDO will be nonsensical and may even be counterproductive because the system will be making decisions based on inaccurate information. The second factor that may cause poor results is how the scheduling parameters are set up for the CDO. The point made previously about some schedulers not trusting the batch-scheduling process because the results of the process are not optimal is probably due to untuned and poorly turned scheduling parameters. If the CDO generates suboptimal results, it may mean that para- meters require refinement. A common remark that paratransit managers hear from their schedulers and dispatchers is “We can do better.” This point of view is often traced back to a distrust in the batching and underlying parameters and in how a human communicates the optimum balance to the computer system. Technologies from Microtransit Vendors Within the last five years, microtransit services (on-demand, shared-ride services for the general public) have become more and more prevalent across the country. Transit agencies seek to replace underperforming fixed routes and expand access to public transit in areas that are not conducive to fixed-route service. Microtransit comes in many service models, but some are served wholly or partially by dedicated service operated by the transit agencies themselves or their paratransit operations/management contractor. Other microtransit service models involve one or more transportation network companies and/or taxi companies providing the service with non-dedicated service providers or supplementing the dedicated vehicles operated by the transit agency or its contractors. In an interesting development, some of the technology vendors have become the sole prime contractor for such microtransit services, using individual drivers or operating entities (e.g., taxi companies) for service delivery. With the advent of microtransit service, about a dozen technology vendors have entered the market, with some taking on a greater role as prime contractors. Three of them have entered the ADA paratransit market: RideCo, Spare Labs, and Via Mobility. (Spare Labs and Via Mobility provide the technology to transit agencies and, for some transit agencies, also serve as the ADA paratransit contractor.) In all cases but to varying degrees, this shift involved modifying the tech- nology for the intricacies of ADA paratransit. At the same time, the basic algorithms that were used for on-demand services were applied to ADA paratransit. In essence, these systems were already capable of taking advance reservations, with scheduling to dedicated vehicles accomplished at the time of the reservations and dispatching to service providers with non-dedicated vehicles delayed until the service day at the appropriate time. One of the real benefits of the new technology to transit agencies has been that they can use the same software platform for both services: ADA paratransit and microtransit. In this way, micro- transit vehicles, if operated by ADA-paratransit-certified drivers, can be used by ADA paratransit dispatchers as a backup resource. Using the same software platform for both services also allows the consolidation of ADA paratransit and microtransit service.