**13**

*April*

### Optimizing dial-a-ride services

Optimizing dial-a-ride services in Maryland: Benets of computerized routing and scheduling ^{1}

Nikola Markovica, Rahul Nairb, Paul Schonfelda, Elise Miller-Hooksa, Matthew Mohebbie

Department of Civil and Environmental Engineering, University of Maryland, College Park, USA bIBM Research, Dublin, Ireland cIT Curves, Gaithersburg, USA

Download Article**Abstract**

This paper reports on a system developed to address the dial-a-ride problem and an implementation for Maryland where real-world practical constraints are considered in providing customized vehicle routing and scheduling for about 450 trip requests daily. The system, called Mobile Resource Management System (MRMS), allows for dispatch operators to quickly study dierent operational scenarios and, in a strategic setting, explore tradeos between level-of-service and various system characteristics, including eet composition, eet size and dispatch rules. Such insights play a key role in making long-term investment decisions or estimating cost of servicing contracts that have service level agreements. Test comparison of manual and MRMS-based routes indicated an estimated annual operational expense reduction of $0.82 million, or about 18% of the total annual expense. In addition to the cost benets, improved quality of service and the reduction in total vehicle-kilometers traveled leading to environmental benets are demonstrated.

**1. Introduction**

Better accessibility to public transportation has become an important objective for many transit systems across the world. This objective has been partially achieved by introducing low- oor buses complemented with \kneeling devices” and specialized ramps, installing elevators in rail stations, and introducing higher platforms. Never- 1An earlier version of this paper (Markovic et al., 2014) was presented at the Transportation Research Board meeting in 2014.

Preprint submitted to Transportation Research Part C: Emerging Technologies January 6, 2015

theless, many handicapped and elderly people still nd it dicult to use public transit despite these recent enhancements. Some handicapped or elderly people need additional help, while others may nd the closest stop to be too far away, or the wait too long (Borndorfer et al., 1999). Transit systems across the world oer these people a special demand-responsive door-to-door transportation service, which is often called dial-a-ride (DAR) service. The major dierence between DAR and taxi service is that DAR allows ridesharing; thus, multiple unrelated passengers, with dierent origins and destinations, may be served simultaneously with the same vehicles.

The average number of paratransit trips provided by a transit agency has increased by 7% from 2007 to 2010 (GAO, 2012), and such trend will likely continue because of the aging population. Due to increasing ridership, the DAR services have been among the fastest growing budget fractions of many transit agencies. These trends pressed DAR service providers to improve the eciency of their operations and thereby limit some of the budget increases. To better control costs and manage their growing operations more eciently, DAR agencies have started to implement communication and computer technology. These technologies also serve as enablers for optimization algorithms to generate better routes and schedules for drivers and vehicles.

This paper addresses the vehicle routing and scheduling problem in DAR operations and makes the following contributions. First, key practical considerations in realworld dispatching operations, such as \locked-blocks” and the heterogeneous nature of demand and supply, are identied and modeled. A \locked-block” refers to a series of passenger demands that do not change from one day to the next, and as such, must be served in the same order every day. Heterogeneity of supply manifests in two ways. Trip requests that have associated with it particularly egregious costs due to spatial or time criteria can be outsourced to a taxi. Additionally, the operator may have a eet of vehicles with varying capacity. This capacity should be allocated based on the heterogeneity of demand for particular routes. For example, such demand variation is likely to occur when there are wheelchair-bound passengers who require additional space onboard. Such practical constraints have been considered only in a limited manner (for example Madsen et al. (1995) considers demand and eet heterogeneity).

The second contribution of the work is in deploying the proposed algorithm to a suite of test instances, and for a real-world deployment in Maryland. The paper examines the benets of improved eciency and results from deployment in the eld, including the improvement in quality of service. Most of all, the results reported in 2 this paper indicate that considerable savings can be achieved in providing DAR services through implementation of custom-designed vehicle routing and scheduling algorithms. These results show a potential for reducing the governmental expenditures provided proper investments in computer-aided decision making in DAR operations.

The remainder of the paper is organized in ve sections. Section 2 describes the overall system architecture and its components. In Section 3 we present the model, solution algorithm, and its application on benchmark problems. Section 4 describes a real-world deployment of MRMS in Maryland, and emphasizes benets of computerized routing and scheduling. In Section 5 we discuss components of the MRMS used to dynamically optimize DAR systems. Finally, Section 6 draws conclusions and recommends further implementations.

**2. The MRMS system**

A system to manage DAR services, from trip request management to dispatch and operations was implemented. At the core of the system is the algorithm for ecient scheduling and dispatching of vehicles satisfying various operational and level-of-service (LOS) constraints. The MRMS was designed to provide operators with many parameters that could be set for dierent runs allowing the operators to experiment and nd the optimal tradeo between LOS and operating and capital expenses. Current wide availability of wireless data, tablets and wireless devices, built-in navigation tools, and powerful back oce computers enable the role of optimization algorithms to improve operations.

The MRMS development and implementation included three distinct parts:

1. In-vehicle navigation and communication equipment that work over standard 3G or 4G wireless data services. This equipment allows monitoring and controlling the location and status of the vehicles at all times. It also allows dynamic modi- cations of driver task lists, which include the sequence of pick-up and drop-o locations and time windows.

2. Cloud-based monitoring, control and rule-based decision-making that provides the intelligence for routing and performance optimization based on provided LOS and system constraints.

3. A presentation layer that enables operators to view in real-time the performance of the operation. It also provides the operators the ability to set up performance 3 parameters, and modify the constraints and optimization rules

The key element of the MRMS is an algorithm used to eciently solve the vehicle routing and scheduling problem in DAR operations. Since a vast majority of trips are scheduled between one and seven days in advance, the main algorithm was based on the static DAR problem. For large-scale instances exact solutions to DAR problem are computationally prohibitive. So, a specialized solution heuristic was developed, incorporating the practical considerations such as, outsourcing of outlier requests, locked-blocks, and heterogeneity in eet and requests. Elements of the aforementioned algorithm were also used to tackle requests arising in the real-time, and to continuously reoptimize the DAR system throughout its operations.

**3. Static dial-a-ride problem**

When the DAR requests are made long in advance, which is the case with 90% of requests, the problem of assigning multiple trip requests to be served concurrently on multiple vehicles is called a static DAR Problem (DARP) (Cordeau and Laporte, 2007). The static DARP is usually formulated as a generalized vehicle routing problem with pick-up and delivery (Cordeau, 2006). Since DARP involves transportation of people, tighter time windows and an additional maximum ride time constraint are considered (Luo and Schonfeld, 2007). The latter ensures that a passenger does not spend too much time onboard while other passengers are picked up and dropped o. The most commonly dened objective is to design m least cost vehicle routes to accommodate requests under a set of constraints (Cordeau and Laporte, 2007; Cordeau, 2006; Cordeau and Laporte, 2003a,b). The mathematical formulations assume that mis a given integer. The problem is repeatedly solved by imputing dierent values for m to nd the minimum number of vehicles that can accommodate all the requests (Cordeau and Laporte, 2003b). For a more detailed literature survey, readers are referred to (Berbeglia et al., 2007).

In the following section, we provide the mathematical formulation of the static DARP that explains the practical decisions and issues arising in real-world DAR operations. We formulate it as a eet size and mix vehicle routing problem (Golden et al., 1984) with pick-up and delivery and trip outsourcing. This formulation includes features like eet size, trip outsourcing to taxis, and no idling of loaded vehicles that are very important in practical applications and are commonly considered in heuristic solution methods (Luo and Schonfeld, 2007; Jaw et al., 1986). Despite the practical 4 importance of the aforementioned features, the mathematical formulations found in the literature typically assume a xed eet (i.e., treated m as a constant), and few consider trip outsourcing (Heilporn et al., 2011) or idling for loaded vehicles (Parragh, 2011). The proposed formulation is built upon Cordeau (2006) and follows most of its notation.

The static DARP arising in the real-world operations can be formulated as the following mixed integer program:

The objective function (1) minimizes xed and variable vehicle routing and trip outsourcing costs. Constraints (2) ensure that each request is served exactly once or is outsourced to a taxi. onstraints (3) ensure that the origin and destination nodes are visited by the same vehicle. Constraints (4)-(6) guarantee that the route of each used vehicle starts and ends at the depot. Constraints (7) ensure consistency of the time windows, while (8)-(10) prevent a loaded vehicle from idling. Consistency of the load variable is ensured by constraints (11). Equalities (12) dene the ride time of each user, which is bounded by constraints (15). The latter also act as precedence constraints, because the non-negativity of the Lk i variables ensures that node i will be visited before node n+i for every user i. Inequalities (13) bound the duration of each route. Finally, constraints (14) and (16) impose time windows and capacity limits, respectively. This formulation builds on the math program in Cordeau (2006), but diers in that it includes outsourcing of trips ((1) and (2)), variable eet size ((1) and (4)), and

precludes idling of loaded vehicles ((7)-(11)). The locked blocks can be considered via preprocessing. Namely, an optimal itinerary for a group of passengers traveling together can be found separately, and inputed in the above formulation as one long request with a load equivalent to capacity of the vehicle.

**3.2. Solution method implemented in MRMS**

The optimization model presented above can be solved optimally with branch-andbound- based algorithms, but only for relatively small instances, e.g. n < 50 (Cordeau, 2006). For somewhat larger instances of the static DARP, several metaheuristics proved successful in nding very good or near-optimal solutions (Cordeau and Laporte, 2003b; Parragh et al., 2010). The downside of these latter techniques is that they often require signicant time to tackle practically small instances, e.g. over an hour with 144 requests (Parragh et al., 2010). Since run times have been noted to increase nonlinearly with problem size, a practical solution technique for instances with several hundred or thousand requests is a greedy insertion heuristic. Such a heuristic can construct good feasible solutions to very large problems in reasonable time. In Table 1 we summarize several of these potential solution techniques as well as their pros and cons. Due to its eciency relative to other methods, an insertion-based heuristic (Algorithm 1) was implemented in the MRMS. In particular, the parallel insertion heuristic (Jaw et al., 1986) with improvement operators (Toth and Vigo, 1996; Luo and Schonfeld, 2007) was implemented and modied to incorporate several operational requirements specied by potential users. These requests included working with blocks of trips that may or may not be modied, considering dierent passenger needs, and dierent 7 specications of the objective function. The insertion algorithm outlined next diers from other insertion heuristics mentioned previously as follows:

1. Several changes in trip insertion are made to account for groups of trips that are often referred to as \blocks” and \locked-blocks” in the DAR industry. The MRMS allows a user to specify a sequence of trips that may or may not be changed with subsequent insertions. Blocks and locked-blocks are often formed for repetitive trips that are requested from day-to-day or week-to-week. This is also the case for groups of people with common origins or destinations. Lockedblocks refer to groups of trips that are not only required to travel together, but also for contractual reasons, operators are not allowed to add additional trips to these groups.

2. Early morning, late afternoon, or long trips are ltered and exempt from the insertion. The operator is notied of these trips and may decide whether to outsource them to taxis. Outsourcing requests to taxis is common practice in DAR operations. It occurs when dispatchers assess that some trips have particularly egregious costs due to spatial or time criteria demand and, thus, would be cheaper to outsource to a third party rather than force into ridesharing tours.

Similar to Jaw et al. (1986) and Madsen et al. (1995) the developed method considers heterogeneity of demand and supply. Dierent weights are be associated with passengers depending on the required capacity (e.g., passengers in wheelchairs need more space than others). The vehicles in the depot are heterogeneous in their capacity and number of wheelchair passengers they can carry, and each route has a pre-specied start time.

The above modications enabled an algorithm with academic origins to be implemented in the eld, allowing its application in the daily operations of several DAR companies. Others, including Madsen et al. (1995) and Luo (2006), also extended Jaw’s parallel insertion algorithm to account for practical aspects arising in the applications they considered.

3.3. Testing the solution method on benchmark problems To demonstrate the validity of the implemented solution, the algorithm was run on several benchmark instances where solutions from exact methods were known. The benchmark problems including 24 instances were taken from Cordeau (2006). He used

**Algorithm 1 Outline of the algorithm implemented in MRMS**

Initialize: Sort requests according to desired pick-up time and introduce the rst vehicle.

Step 0: Notify operator of early, late, and long trips.

Step 1: Consider the next unassigned request.

Step 2: For each introduced vehicle:
Generate all feasible insertions of the request into the schedule and compute the change in the objective function

Step 3: If there exists a feasible insertion of the request, then the insertion with the minimum increase in the objective function is selected and the request is inserted while updating the schedule. If a feasible insertion does not exist, a new vehicle is introduced and the request is assigned to it.

Step 4: If there are unassigned requests, then go to step 1, otherwise go to step 5.

Step 5: Apply the following two operators through desired number of iterations:
Trip reinsertion operator: remove trip i from its current route and try reinserting it into all the vehicle routes. Make the reinsertion with the minimum associated cost (the nal route may be the same as the current one); Trip exchange operator: remove trip i from its route r and remove trip j from its route s, (r 6= s); insert the two stops of trip i in the best positions of route s and insert the two stops of trip j in the best positions of route r. If the exchange yields a cost reduction, make the swap.

a branch-and-cut algorithm to nd m least cost vehicle routes to accommodate n requests, assuming that m is given. The benchmark problems include up to 48 trips. The largest instance solved optimally has 32 requests. Table 2 compares Cordeau’s solutions and lower bounds with solutions obtained by the implemented heuristic method. Note that the implemented heuristic ensures higher LOS since it prevents loaded vehicles from idling. Here, we do not consider outsourcing of requests to taxi in order to make the heuristic comparable with Cordeau’s setting. The heuristic was implemented in Matlab 2010a on a PC with an AMD Athlon 3300 GHz processor and the computation times are compared with those reported in Cordeau (2006).

The implemented heuristic provides competitive results within no more than 35 seconds computation time. In 75% of the cases, the implemented heuristic provided results with the same or fewer vehicles. The driving time was within 25 to 55% of the optimal solution or bound reported in Cordeau 2006. Moreover, computation times needed to solve optimally the instances in Table 2 justify the use of the heuristic. For example, instance b4-32 includes 32 requests and is solved optimally in about 3 hours with the branch-and-cut algorithm. Thus, solution of the problem instances with several hundred requests that face midsize or large DAR companies would be computationally intractable. Even with recent developments in computer technology, nding exact solutions would be formidable and heuristics or metaheuristics must be applied.

**4. Regency Taxi case study**

Regency Taxi (RT) is a taxi company and a DAR service provider located in Maryland, US. Currently, RT has 40 employees and 150 drivers who are fully trained in handling transportation needs of disabled and senior citizens. The company’s eet consists of 150 vehicles, some of which are equipped with ramps or lifts that facilitate access for disabled passengers traveling in wheelchairs. Moreover, the vehicles are equipped with 3G or 4G wireless smart devices, i.e., tablets, which allow regular communication with the dispatch center.

In RT’s operations, about 90% of DAR requests are made in advance. A passenger schedules a trip by specifying pick-up and delivery locations, as well as the desired pick-up or drop-o time. After the trip requests are gathered, the dispatchers use the afternoon to design routes and schedules for the following day. A route manifest is electronically sent to drivers who can start their assignments on the following morning

with the schedules available on their tablets. The routes are given in the form of a sequence of pick-up and drop-o locations with requested arrival times, and drivers are asked to serve the routes in exactly the same sequence that is provided to them. Another 10% of requests are made for the same day and those trips are quickly inserted into previously built routes while considering the GPS positions of the vehicles. When dispatchers determine that a request is an \outlier,” i.e., does not t well with the rest of the demand, they dispatch these trips as a single taxi trip.

As RT’s DAR operations have grown over the past several years, its management determined that manual dispatch not only produced inecient routes but also became impractical. Therefore, they decided to computerize the dispatching process. The management envisioned that computerized routing will considerably reduce dispatching eort and provide an even higher LOS to their passengers than through manual routing. LOS is an essential part of any DAR contract. Considering its daily routine, the company sought a solution method capable of nding good feasible solutions to problems of forming routes/manifests within less than an hour. The management studied the specications of several commercially available software solutions and decided that the MRMS would be the best t for their operation. In the following section we evaluate the benets of implementing the MRMS in the described operations.

**4.1. Benets of implementing the MRMS: Operational level**

The immediate benets of implementing the MRMS system were observed in reducing dispatching, transportation, and external costs. RT receives about 450 requests on a daily basis. The MRMS was able to route this number of trips within 7 minutes and thereby save the dispatch sta about 12 dispatcher-hr/day that were previously needed to build the manifests manually. Moreover, the transportation cost was reduced by decreasing the number of vehicles and drivers needed to serve all requests. The MRMS-based routes were compared with the manually built route manifest for one day of RT’s operations (Table 3). Test comparisons showed that the number of routes and vehicle-km traveled decreased by 12.8% and 22.4%, respectively. Moreover, the number of routes and vehicle-km traveled decreased despite the imposition of tighter LOS constraints than those observed in manually built routes. Table 3 indicates that the MRMS-based routes yield estimated total annual savings of approximately $0.82 million. This represents roughly 18% of total operating cost. Finally, negative external costs, such as emissions and trac congestion, were similarly substantially reduced as a result of signicant anticipated reductions in the number of vehicle-hours driven.

In addition to evident cost reductions shown in Table 3, the MRMS allowed computation of various performance measures and visualization of schedules and routes.These features were especially important for gaining trust in the methodologies and the ultimate adoption of the tool and its operations research-based techniques. In manual routing and scheduling it is dicult to keep track of performance measures, because they require tedious computations. In computer-based routing, on the other hand, a variety of statistics can be readily generated. These statistics provide increased insight into overall system performance, which is of particular interest to system managers. Moreover, statistics allow better control of vehicle utilization and, thus, discourage drivers from using the vehicles for their own needs. Some of the performance measures that the management found useful are shown in Table 4. Additionally, the tool’s user-friendly interface (Figure 1) produced recognizable savings in time and eort for the dispatchers and drivers, thus also aiding the tool’s acceptance.

**4.2. Benets of implementing the MRMS: Tactical level**

Besides cost reductions achieved at the operational level, the MRMS provided its user with a valuable tool that can be used for decision making at the tactical level. The MRMS allows operators to quickly study dierent operational scenarios and explore tradeos between LOS and various system characteristics. Such insights play a key role in making long-term investment decisions in the company’s eet, or when signing a contract which promises a certain LOS. Some of the insights that operators using MRMS are nding useful are provided next. One of the factors in uencing LOS is the time window promised to customers. Intuitively, wider time windows provide more exibility to the operator, but lower LOS for

the customers. The MRMS allowed its users to quantify the cost of providing dierent time windows and explore these tradeos. The required eet size ranged between 45 and 35 vehicles as the time windows were relaxed from 30 to 105 min, respectively, while keeping a xed 12 hour limit on route duration (pentagrams in Figure 2a). This insight is especially important in signing contracts with transit agencies that typically specify minimum LOS to passengers in terms of time windows and maximum system response time. The corresponding operating daily cost may be reduced from roughly $12,650 to $10,200 as time windows are relaxed from 30 to 105 minutes (pentagrams in Figure 2b).

Operators using MRMS were also able to quantify the change in eet needed to meet its demand when the route duration limit was relaxed from 8 to 10 and 12 hours (Figure 2a). This insight is useful in negotiating general agreement contracts that may impose a limit on driver working hours. It also allows operators to better estimate the value of driver overtime hours by assessing the corresponding operating cost (Figure 2b).

A factor that considerably in uences operator costs is the distribution of demand over time. It is theoretically expected that steadier demand yields better utilization of transportation assets (Fitzsimmons and Fitzsimmons, 2006). The MRMS allows its users to quantify eects of potential changes in demand distribution. Figure 3 shows the original and two slightly modied demand distributions (Original, Modied 1, and

Modied 2). The two modied demand distributions were obtained by redistributing some of the requests originally scheduled during the peak hours. Results in Figure 3 indicate that fewer vehicles are needed to satisfy steadier demand, while keeping the same number of trips and their origin-destination locations, 30 minute time windows, and 12 hour route limit. This insight is important in anticipating potential savings that could be achieved by spreading some of the peak demand. To reach this goal, the DAR operators could provide incentives that encourage their customers to travel during o-peak hours, such as discounts in co-pay paid by the customer and more direct service due to fewer on-board passengers.

Through sensitivity analysis, it was determined that increasing vehicle capacity from a base of 7 passengers does not improve the solutions. This occurs because other operational constraints, including a time window of between 30 and 105 minutes, route durations of between 8 and 12 hours and maximum ride times per passenger prevent the algorithm from taking full advantage of vehicle capacity. This nding is valuable in determining long-term eet composition.

**5. Dynamic optimization within the MRMS**

The majority of DAR requests are generally pre-scheduled (e.g., 90% RT’s demand), which makes the static DARP the key component in managing DAR operations. Solving static DARP is also expected to yield the greatest savings for a DAR company. A similar concept can be applied to tackle requests that need to be served on a short notice (i.e., dynamic requests which should be served on the same day). The MRMS employs Steps 2-3 outlined in Algorithm 1 to sequentially insert dynamic requests as they arrive in the real-time. Every time a new request is received, the system collects locations of all the vehicles as well as information about their remaining schedules. The MRMS then examines all feasible trip insertions, and opts for the insertion with the smallest incremental cost. This automated handling of dynamic requests reduces human eort, and also yields more ecient routes due to ability to examine all feasible insertions.

Moreover, the route improvement procedure (Step 5, Algorithm 1) is constantly applied to reoptimize routes by reinserting or swapping requests. This reoptimization is particularly useful when deviations from the schedule occur either due to congestion or vehicle break downs. These components further increase the eciency of the DAR operations, as well as the competitiveness of the proposed management system. The whole concept of the MRMS which tackles both static and dynamic DARP is currently patent pending (Mohebbi et al., 2011). It should be noted that concrete savings from dynamically managing a DAR system are much harder to evaluate than in the case of static DARP. For static DARP, a simple o-line comparison of manual and MRMS-based routes suce to estimate the savings. However, a similar comparison for dynamic DARP would require vast data in order to realistically simulate a day of operations with and without computerized management. Since dynamic components of the MRMS were gradually introduced in the operations of RT, we were unable to quantify the savings. This will be done in future implementations of the MRMS.

**6. Conclusions**

A computerized system, the MRMS, for managing DAR operations was developed. The developed management system was implemented in a number of midsize transportation companies yielding considerable cost reductions. Test comparisons of manual 17 and MRMS-based routes indicated that a typical mid-size operator performing approximately 450 trips per day could reduce its annual dispatching and transportation costs by an estimated 0.82 million dollars, roughly 18% of the total operational expense. The MRMS also provided the operators with a powerful tool for quickly exploring system performance under dierent operational scenarios. Insights gleaned from studying a variety of operational scenarios were found important for tactical planning where an operator needs to determine the cost of providing a certain level-of-service, long-term eet composition, and utility of driver overtime hours. These ndings encourage further implementation of optimization methods with realistic constraints in DAR operations, because they can considerably reduce the costs of providing these services. Since DAR operations are heavily subsidized, computerized systems like MRMS could also help reduce some of these governmental expenditures.

**Acknowledgments**

This work was funded by the Maryland Industrial Partnership and the IT Curves company. This support is gratefully acknowledged, but implies no endorsement of the fndings.

**References**

Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I. and Laporte, G. (2007), `Static pickup and delivery problems: a classication scheme and survey’, Top 15(1), 1{31.

Borndorfer, R., Grotschel, M., Klostermeier, F. and Kuttner, C. (1999), Telebus Berlin: Vehicle scheduling in a dial-a-ride system, Springer.

Cordeau, J.-F. (2006), `A branch-and-cut algorithm for the dial-a-ride problem’, Op- erations Research 54(3), 573{586.

Cordeau, J.-F. and Laporte, G. (2003a), `The dial-a-ride problem (DARP): Variants, modeling issues and algorithms’, Quarterly Journal of the Belgian, French and Italian

Operations Research Societies 1(2), 89{101. Cordeau, J.-F. and Laporte, G. (2003b), `A tabu search heuristic for the static multi-vehicle dial-a-ride problem’, Transportation Research Part B: Methodological 37(6), 579{594. 18
Cordeau, J.-F. and Laporte, G. (2007), `The dial-a-ride problem: models and algorithms’, Annals of Operations Research 153(1), 29{46.

Fitzsimmons, J. A. and Fitzsimmons, M. J. (2006), Service management: operations, strategy, and information technology, McGraw-Hill New York.

GAO (2012), Ada paratransit services: Demand has increased, but little is known about compliance, Report, United States Government Accountability Oce.

Golden, B., Assad, A., Levy, L. and Gheysens, F. (1984), `The eet size and mix vehicle routing problem’, Computers & Operations Research 11(1), 49{66.

Heilporn, G., Cordeau, J.-F. and Laporte, G. (2011), `An integer L-shaped algorithm for the dial-a-ride problem with stochastic customer delays’, Discrete Applied Math- ematics 159(9), 883{895.

Jaw, J.-J., Odoni, A. R., Psaraftis, H. N. and Wilson, N. H. (1986), `A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows’, Transportation Research Part B: Methodological 20(3), 243{257.

Luo, Y. (2006), Heuristics and performance metamodels for the dynamic dial-a-ride problem, PhD thesis.

Luo, Y. and Schonfeld, P. (2007), `A rejected-reinsertion heuristic for the static diala- ride problem’, Transportation Research Part B: Methodological 41(7), 736{755.

Madsen, O. B., Ravn, H. F. and Rygaard, J. M. (1995), `A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives’,Annals of operations Research 60(1), 193{208.

Markovic, N., Nair, R., Schonfeld, P., Miller-Hooks, E. and Mohebbi, M. (2014), Optimizing dial-a-ride services in maryland, in `Transportation Research Board 93rd

Annual Meeting’, number 14-1705.

Mohebbi, M., Ditu, C. V. and Siddiqui, M. I. Y. (2011), `Ecient automated ride sharing system’. US Patent Application 13/247,446.

Parragh, S. N. (2011), `Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem’, Transportation Research Part C: Emerging Technologies 19(5), 912{930. 19

Parragh, S. N., Doerner, K. F. and Hartl, R. F. (2010), `Variable neighborhood search for the dial-a-ride problem’, Computers & Operations Research 37(6), 1129{1138.

Toth, P. and Vigo, D. (1996), Fast local search algorithms for the handicapped persons transportation problem, in `Meta-Heuristics’, Springer, pp. 677{690.

1. Identifies practical issues arising when applying a state-of-the-art solution methodology in real-world operations;

2. Develops the algorithmic means for addressing the above concerns;

3. Shows an actual application of an OR tool to the DAR services of RT;

4. Examines the benefits of improved efficiency that results from the tool’s application and its impact on revenue and quality of service.

Figure 1: The MRMS is a computerized ride-sharing system solution that enables design of efficient routes and monitoring of the entire transportation process in the real-time. It consists of in-vehicle navigation and communication equipment, cloud-based monitoring and vehicle routing, and a presentation layer that enables system monitoring and management.

The MRMS system was designed as an end-to-end turnkey transportation Enterprise Management System (EMS), also referred to as a Transportation Information System (TIS) in DAR terminology. The MRMS development and implementation included three distinct parts:

1. In-vehicle navigation and communication equipment that work over standard 3G or 4G wireless data services. This equipment allows monitoring and controlling the location and status of the vehicles at all times. It also allows dynamic modifications of driver task lists, which include the sequence of pick-up and drop-off locations and time windows.

2. The cloud-based monitoring, control and rule-based decision making is the segment that provides the intelligence for routing and performance optimization based on provided LOS and system constraints. The heuristic for solving the DARP is located in this component.

3. The presentation layer enables operators to view in real-time the performance of the operation. It also provides the operators the ability to setup performance parameters, modify the constraints, and optimization rules.

The key element of the MRMS is the OR tool that is applied to efficiently solve the vehicle routing and scheduling problem in the DAR operations. The following sections provide an overview of the static DARP and solution methods, as well as the outline of the algorithm implemented in MRMS.

The key element of the MRMS is the OR tool that is applied to efficiently solve the vehicle routing and scheduling problem in the DAR operations. The following sections provide an overview of the static DARP and solution methods, as well as the outline of the algorithm implemented in MRMS.

** Static DARP and Solution Methods**

When the DAR requests are made long in advance, which is the case with 90% of requests, the problem of assigning multiple trip requests to be served concurrently on multiple vehicles is called a static DARP (Cordeau and Laporte 2007). The static DARP has been extensively studied since the 1970’s and various solution methods have been developed to tackle it. These solution methods may be classified into three groups: exact, heuristic, and metaheuristic. All of them have advantages and disadvantages, as summarized in Table 1.

When the DAR requests are made long in advance, which is the case with 90% of requests, the problem of assigning multiple trip requests to be served concurrently on multiple vehicles is called a static DARP (Cordeau and Laporte 2007). The static DARP has been extensively studied since the 1970’s and various solution methods have been developed to tackle it. These solution methods may be classified into three groups: exact, heuristic, and metaheuristic. All of them have advantages and disadvantages, as summarized in Table 1.

**Table 1: Overview of solution methods for the DARP (Cordeau and Laport 2003a, Berbeglia et al. 2007).**

The static DARP is usually formulated as a generalized vehicle routing problem with pick-up and delivery (VRPPD) (Cordeau 2006). Since DARP involves transportation of people, tighter time windows and an additional maximum ride time constraint are considered (Luo and Schonfeld 2007). The latter ensures that a passenger does not spend too much time onboard while other passengers are picked up and dropped off. The most commonly defined objective is to design least cost vehicle routes to accommodate requests under a set of constraints (Cordeau and Laporte 2003a, 2003b, 2007, and Cordeau 2006). The mathematical formulations assume that is a given integer. The problem is repeatedly solved by imputing different values for to find the minimum number of vehicles that can accommodate all the requests (Cordeau and Laporte 2003b).

In the following section, we provide the mathematical formulation of the static DARP that clearly explains the practical decisions and issues arising in RT’s operations. We formulate it as a fleet size and mix vehicle routing problem (Golden et al. 1986) with pick-up and delivery and trip outsourcing. This formulation includes features like fleet size or trip outsourcing to taxis that are very important in practical applications and are commonly considered in heuristic solution methods (Jaw et al. 1986, Luo and Schonfeld 2007). Despite the practical importance of the aforementioned features, the mathematical formulations found in the literature typically assume a fixed fleet (i.e. treat as a constant) and few of them consider trip outsourcing (Heliporn et al. 2011) or idling for loaded vehicles (Parragh 2010). The proposed formulation is built upon (Cordeau 2006) and follows most of his notation.

**Formulation**

Let denote the number of users (or requests) to be served. The DARP may be defined on a complete directed graph , where , , and . Subsets and contain pick-up and drop-off nodes, respectively, while nodes and represent the depot. With each user are thus associated an origin node and a destination node .

Let be the set of vehicles. Each vehicle has a capacity , and the total duration of its route cannot exceed . With each node are associated a load and a nonnegative service duration such that , , and . A time window is also associated with node , where and represent the earliest and latest time, respectively, at which service may begin at node . With each arc and vehicle are associated a routing cost and a travel time which is assumed to be identical for all the vehicles. Let denote the fixed cost for using vehicle , and let and denote the fixed and variable taxi cost, respectively. Finally, let denote the maximum ride time coefficient such that represents the maximum ride time for user .

For each arc and each vehicle , let if vehicle travels from node to node . For each node and each vehicle , let be the time at which vehicle begins service at node , and be the load of vehicle after visiting node . Let if vehicle is non-empty after visiting node . For each user , be the ride time of user on vehicle , and if the customer is outsourced to a taxi.

he DARP arising in RT’s operations can be formulated as the following mixed integer program

The objective function (1) minimizes fixed and variable vehicle routing and trip outsourcing costs. Constraints (2) ensure that each request is served exactly once, or is outsourced to a taxi. Constraints (3) ensure that the origin and destination nodes are visited by the same vehicle. Constraints (4)-(6) guarantee that the route of each used vehicle starts and ends at the depot. Constraints (7) ensure consistency of the time windows, while (8)-(10) prevent a loaded vehicle from idling. Consistency of the load variable is ensured by constraints (11). Equalities (12) define the ride time of each user, which is bounded by constraints (15). The latter also act as precedence constraints, because the non-negativity of the variables ensures that node will be visited before node for every user . Inequalities (13) bound the duration of each route. Finally, constraints (14) and (16) impose time windows and capacity limits, respectively.

**Solution Method implemented in MRMS**

Due to its efficiency relative to other methods, an insertion-based heuristic was implemented. In particular, the parallel insertion heuristic (Jaw et al. 1986) with improvement operators (Toth and Vigo 1996, Luo 2006, Luo and Schonfeld 2007) was implemented and modified to incorporate several operational requirements specified by potential users, including RT. These requests included working with blocks of trips that may or may not be modified, considering different passenger needs, and different specifications of the objective function. The insertion algorithm (Table 2) differs from other insertion heuristics mentioned above as follows.

1. Several changes in trip insertion are made to account for groups of trips that are often referred to as “blocks” and “locked-blocks” in the DAR industry. The MRMS allows a user to specify a sequence of trips that may or may not be changed with subsequent insertions. Blocks and locked-blocks are often formed for repetitive trips or groups of people with common origins or destinations. Locked-blocks refer to groups of trips that not only are required to travel together, but also for contractual reasons, operators are not allowed to add additional trips to these groups.

2. Early, late, or long trips are filtered and exempt from the insertion. The operator is notified of these trips and may decide whether to outsource them to taxis. Outsourcing requests to taxis is common practice in DAR operations. It occurs when dispatchers assess that some trips do not fit well into the rest of the demand and, thus, would be cheaper to outsource to a third party rather than force into ridesharing tours.

3. Different weights may be associated with passengers depending on the required capacity (e.g. passengers in wheelchairs need more space than others).

4. The vehicles in the depot are heterogeneous in their capacity and number of wheelchair passenger they can carry, and each route has a pre-specified start time. The MRMS implementation starts the routes after their specified start time.

**Table 2: Outline of the algorithm implemented in MRMS.**

The above modifications enabled an algorithm with academic origins to be implemented in the field, allowing its application in the daily operations of RT and a number of other companies. Others, including Madsen et al. (1995) and Toth and Vigo (1997), also extended Jaw’s parallel insertion algorithm to account for different practical aspects arising in the applications they considered.

**Testing the Solution Method**

This section explores the performance of the implemented solution method on benchmark problems defined in (Cordeau, 2006) in order to assess the optimality gap. Cordeau specified two sets of problems each including 12 instances. He used a branch-and-cut algorithm to find least cost vehicle routes to accommodate requests, assuming that is given. The benchmark problems include up to 48 trips. The largest instance solved optimally has 32 requests. Tables 3 and 4 compare Cordeau’s solutions and lower bounds with solutions obtained by the implemented heuristic method. Note that the implemented heuristic ensures higher LOS since it prevents loaded vehicles from idling. Here, we do not consider outsourcing of requests to taxi in order to make the heuristic comparable with Cordeau’s setting. The heuristic was implemented in Matlab 2010a on a PC with an AMD Athlon 3300 GHz processor and the computation times are compared with those reported in Cordeau 2006.

**Table 3: The implemented heuristic provided competitive results in terms of fleet size.
Note: n, T, Q, L stand for the number of requests, route duration, capacity, and maximum ride time for each user, respectively. Values marked with ‘*’ represent optimal total driving time for m vehicles. Other values for driving time represent lower bounds. The last column shows the percentage gap in driving time between the solution obtained through heuristic and the lower bound.**

**Table 4: The implemented heuristic provided results within 25 to 55 percent of the optimal driving time.**

The implemented heuristic provides competitive results within no more than 35 seconds computation time. In 75% of the cases, the implemented heuristic provided results with the same or fewer vehicles. The driving time was within 25 to 55% of the optimal solution or bound reported in Cordeau 2006. These results justify the use of the heuristic. For example, instance b4-32 includes 32 requests and is solved optimally in about 3 hours with the branch-and-cut algorithm. Thus, solution of the problem instances of a size addressed in RT’s operations would be computationally intractable. Even with recent developments in computer technology, finding exact solutions would be formidable and heuristics or metaheuristics must be applied.

**Regency Taxi**

RT started its DAR operations in 1999 and has experienced continuous growth in annual ridership ever since. Currently, RT has 110 employees, including 90 drivers who are fully trained in handling transportation needs of disabled and senior citizens. The company’s fleet consists of 80 vehicles, most of which are vans with 11 or 14 seats that are used for providing DAR and other types of services. Most vehicles are equipped with ramps or lifts that facilitate access for disabled passengers traveling in wheelchairs. Moreover, the vehicles are equipped with 3G or 4G wireless smart devices, i.e. tablets, which allow regular communication with RT’s dispatch center.

In RT’s operations, about 90% of DAR requests are made one to seven days in advance. A passenger schedules a trip by specifying pick-up and delivery locations, as well as the desired pick-up or drop-off time. After the trip requests are gathered, the dispatchers use the afternoon to design routes and schedules for the following day. A route manifest is electronically sent to drivers who can start their assignments on the following morning with the schedules available on their tablets. The routes are given in the form of a sequence of pick-up and drop-off locations with requested arrival times, and drivers are asked to serve the routes in exactly the same sequence that is provided to them. Another 10% of requests are made for the same day and those trips are quickly inserted into previously built routes while considering the GPS positions of the vehicles. A common practice in DAR operations is outsourcing of difficult-to-serve requests to taxis. When RT’s dispatchers determine that a request is an “outlier”, i.e. does not fit well with the rest of the demand, they outsource it, thereby assessing that it is cheaper to pay for a taxi than to introduce an additional paratransit vehicle or make a long detour.

As RT’s operations have grown over the past several years, its management determined that manual dispatch not only produced inefficient routes but also became impractical. Therefore, RT decided to computerize its fleet management system. RT’s management envisioned that computerized routing will considerably reduce dispatching effort and provide an even higher LOS to their passengers, which is an essential part of any DAR contract. Considering its daily routine, RT sought a solution method capable of finding good feasible solutions to problems including nearly 1,000 requests within less than an hour. RT’s management studied the specifications of several commercially available software solutions and decided that the MRMS would be the best fit for their operation. In the following section we stress the benefits of implementing the MRMS in the operations of RT.

**Business Analytics: Operational Level**

The immediate benefits of implementing the MRMS system were observed in reducing dispatching, transportation, and external costs. RT receives about 450 requests on a daily basis. The MRMS was able to route the same number of trips within 7 minutes and thereby save the dispatch staff about 12 dispatcher-hr/day that were previously needed to build the manifests manually. Moreover, the transportation cost was reduced by decreasing the number of vehicles and drivers needed to serve all requests. The MRMS-based routes were compared with the manually built route manifest for one day of RT’s operations (Table 5). Test comparisons showed that the number of routes and vehicle-km traveled decreased by 12.8% and 22.4%, respectively. Moreover, the number of routes and vehicle-km traveled decreased despite the imposition of tighter LOS constraints than those observed in manually built routes. Table 5 indicates that the MRMS-based routes yield estimated total annual savings of approximately $0.82 million. This represents roughly 17% of RT’s total operating cost. Finally, negative external costs, such as emissions and traffic congestion, were similarly substantially reduced as a result of significant anticipated reductions in the number of vehicle-hours driven.

**Table 5: Savings achieved on the operational level assuming: $25/dispatcher-hr, $170/driver-day, $20/vehicle-day (vehicle depreciation), $0.27/vehicle-km (variable cost), and 350 working days/year.
Note: The savings are computed by UMD and IT Curves based on the field data provided by RT. LOS and operator’s constraints for computer-based routing correspond to those observed in manual routes.**

In addition to evident cost reductions shown in Table 5, the MRMS allows computation of various performance measures and visualization of schedules and routes. These features were especially important for gaining trust in the methodologies and the ultimate adoption of the tool and its OR-based techniques. In manual routing and scheduling it is difficult to keep track of performance measures, because they require tedious computations. In computer-based routing, on the other hand, a variety of statistics can be readily generated. These statistics provide increased insight into overall system performance, which is of particular interest to system managers. Moreover, statistics allow better control of vehicle utilization and, thus, discourage drivers from using the vehicles for their own needs. Some of the performance measures that RT found useful are shown in Table 6. Additionally, the tool’s user-friendly interface (Figures 2 and 3) produced recognizable savings in time and effort for the dispatchers and drivers, thus also aiding the tool’s acceptance.

**Table 6: Performance measures provide management with many insights and better control over drivers.**

**Note: DPT = desired pick-up time, PaVHr = pass/veh-hr, and PKmVhr = pass-km/veh-hr.**

**Figure 2: User-friendly interface and the visual aspect of the MRMS help the OR-based tool become accepted by the employees.**

**Figure 3: Compact menu for entering new requests by specifying origin and destination locations, number of**

**Business Analytics: Tactical and Strategic Level**

Besides cost reductions achieved at the operational level, the MRMS provided RT with a valuable tool that could be used for decision making on tactical and strategic levels. The MRMS allowed RT to quickly study different operational scenarios and explore tradeoffs between LOS and various system characteristics. Such insights play a key role in making long-term investment decisions in the company’s fleet, or when signing a contract which promises a certain LOS. Some of the insights that RT found useful are provided below.

One of the factors influencing LOS is the time window promised to customers. Intuitively, wider time windows provide more flexibility to the operator, but lower LOS for the customers. The MRMS allowed RT to quantify the cost of providing different time windows and explore these tradeoffs. The required fleet size ranged between 45 and 35 vehicles as the time windows were relaxed from 30 to 105 min, respectively, while keeping a fixed 12 hour limit on route duration (solid line in Figure 4). This insight is especially important in signing contracts with transit agencies that typically specify minimum LOS to passengers in terms of time windows and maximum system response time. The corresponding operating daily cost may be reduced from roughly $12,650 to $10,200 as time windows are relaxed from 30 to 105 minutes (solid line in Figure 5).

RT was also able to quantify the change in fleet needed to meet its demand when the route duration limit was relaxed from 8 to 10 and 12 hours (Figure 4). This insight is useful in negotiating general agreement contracts that may impose a limit on driver working hours. It also allows RT to better estimate the value of driver overtime hours by assessing the corresponding operating cost (Figure 5).

**Figure 4: Fewer vehicles are needed as the time windows and route duration limits are relaxed.**

**Figure 5: Operating cost decreases as the time windows and route duration limits are relaxed. Note: The assumed costs are: $170/driver-day + $20/vehicle-day (vehicle depreciation); $0.27/vehicle-km**

A factor that considerably influences operator costs is the distribution of demand over time. It is theoretically expected that steadier demand yields better utilization of transportation assets (Fitzsimmons 2001). The MRMS allowed RT to quantify effects of potential changes in demand distribution. Figure 6 shows the original and two slightly modified demand distributions (Original, Modified 1, and Modified 2). The two modified demand distributions were obtained by redistributing some of the requests originally scheduled during the peak hours. Results in Figure 6 indicate that fewer vehicles are needed to satisfy steadier demand, while keeping the same number of trips and their origin-destination locations, 30 minute time windows, and 12 hour route limit. This insight is important in anticipating potential savings that could be achieved by spreading some of the peak demand. Some transit agencies do not allow variable pricing strategies for paratransit services (MetroAccess 2012), but DAR operators may find other incentives that encourage their customers to travel during off-peak hours, such as discounts in co-pay and more direct service due to fewer on-board passengers.

**Figure 6: More uniform demand results in smaller fleet and operator’s cost needed to serve all the requests**

An additional finding is that vehicle capacity in RT’s operations is currently not binding. Through sensitivity analysis for different vehicle capacity, it was determined that increasing vehicle capacity from a base of 7 passengers does not improve the solutions. This occurs because other operational constraints, including time window of 30-105 minutes, route durations of 8-12 hours and maximum ride times per passenger prevent the algorithm to take full advantage of vehicle capacity. This finding is valuable in determining long-term fleet composition.

**Conclusions**

In 2012, RT switched from manual to computer-based routing to better manage its growing dial-a-ride operation. A computerized management system was developed jointly by IT Curves and the University of Maryland. The implemented management system (MRMS) included a vehicle routing and scheduling heuristic. Test comparisons of manual and MRMS-based routes indicated that RT’s annual dispatching and transportation costs could be reduced by an estimated 0.82 million dollars, which is nearly 17% of RT’s operational expense. The MRMS also provided RT with a powerful tool for quickly exploring system performance under different operational scenarios as well as user-friendly support for the dispatchers and drivers. Insights gleaned from studying a variety of operational scenarios are important for tactical and strategic level planning where an operator needs to determine the cost of providing certain level-of-service, long-term fleet composition, and utility of driver overtime hours.

Dial-a-ride services are one of the fastest growing budget fractions of many transit agencies and reports from several cities in the US indicate that paratransit ridership is expected to increase nationwide. For example, paratransit ridership growth of more than 10% per year is reported for 2006 through 2009 in the D.C. region (Review of MetroAccess Ridership, Costs and Policy, 2009) and the Metro Council of St. Paul, Minnesota warned that paratransit ridership may grow by as much as 6% per year for the next 10 years (Metro Mobility, 2010). This implies that additional efficiency gains in operations of DAR contractors is required to limit some of this increase in budget. In response to these trends, paratransit agencies in North America and Europe are starting to implement communication and computer technology to control costs and improve service (Trends in Paratransit Technology, 2004). This indicates the timeliness of the developed management system and its market potential.

Future work will include the development and implementation of a dynamic dial-a-ride algorithm to efficiently serve requests that are received with slight advance notice, while the DAR vehicles are already working. Additional features will be included to continuously reoptimize routes in real-time and to manage vehicle deviations from the schedule. The dynamic algorithm will be able to quickly reinsert passengers initially assigned to vehicles that either fall behind schedule or break down. These improvements will further increase the efficiency of RT, as well as the competitiveness of the proposed management system.

**Acknowledgments**

This work was funded by the Maryland Industrial Partnership (MIPS) with matching funds and a direct grant from IT Curves. This support is gratefully acknowledged, but implies no endorsement of the findings.

**References**

Berbeglia, G., Cordeau, J.F., Gribkovskaia, I., G. Laporte. 2007. Static pickup and delivery problems: A classification scheme and survey. Top 15, 1–31.

Borndoerfer, R., Groetschel, M., Klostermeier F., C. Kuettner. 1997. Telebus Berlin: Vehicle scheduling in a dial-a-ride system. Technical Report SC 97-23, Konrad-Zuse-Zentrum fuer Informationstechnik Berlin.

Cordeau, J.K, Laporte, G. 2003a. The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. 4OR-Quart. J. Belgian, French Italian Oper. Res. Soc. 1, 89-101.

Cordeau, J.K, Laporte, G. 2003a. The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. 4OR-Quart. J. Belgian, French Italian Oper. Res. Soc. 1, 89-101.

Cordeau, J.F., G. Laporte. 2003b. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research. 37B, 579-594.

Cordeau, J.F. 2006. A branch and cut algorithm for the dial-a-ride problem. Operations Research 54, 573-586

Cordeau, J.F., G. Laporte. 2007. The dial-a-ride problem: Models and algorithms. Annals of Operations Research 153, 29–46.

Fitzsimmons, J.A., Fitzsimmons, M.J. 2001. Service Management: Operations, Strategy, and Information Technology, 3rd Edition, Irwin/McGraw-Hill

Golden, B., Assad, A., Levy, L., Gheysens, F. 1984. The fleet size and mix vehicle routing problem. Computers & Operations Research, Volume 11, Issue 1, 49-66

Heliporn, G., Cordeau, J.F., Laporte, G. 2011. An integer L-shaped algorithm for the dial-a-ride problem with stochastic customer delays. Discrete Applied Mathematics, 159(9), 883-895

Jaw, J. J., Odoni, A. R., Psaraftis, H. N., N.H.M. Wilson. 1986. A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows. Transportation Research, 20B(3), 243-257

Luo, Y. Heuristics and Performance Metamodels for the Dynamic Dial-a-Ride Problem. 2006. PhD dissertation, University of Maryland, College Park.

Luo, Y., Schonfeld P. 2007. A rejected-reinsertion heuristic for the static Dial-A-Ride Problem. Transportation Research, 41B(7), 736–755

Madsen, O.B.G., Ravn, H.F., Rygaard, J.M. 1995. A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Annals of Operations Research, 60(1), 193–208.

MetroAccess http://en.wikipedia.org/wiki/Washington_Metropolitan_Area_Transit_Authority accessed on 03/27/2012

Metro Mobility: Independence and opportunity for 13,000 metro residents. Metro Council Newsletter, 2010

Parragh, S.N. 2011. Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C, July 2010.

Review of MetroAccess Ridership, Costs and Policy. WMATA Finance Committee Report. June 11, 2009

Toth, P., Vigo, D. 1996. Fast local search algorithms for the handicapped persons transportation problem. In: Osman, I.H., Kelly, J.P. (Eds.), Meta-Heuristics: Theory and Applications. Kluwer, Boston, 677–690.

Toth, P., Vigo, D. 1997. Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, 31(1), 60–71.

Trends in Paratransit Technology: A White Paper by Trapeze Software Group. Trapeze Group 2004