Dial-a-Ride Solution

This paper describes the development and implementation of a computerized system for managing shared-ride prescheduled door-to-door transportation services for elderly and disabled passengers.


Nikola Marković1, Rahul Nair2, Paul Schonfeld1, Elise Miller-Hooks1
1University of Maryland, College Park, MD 20742; 2IBM Research, Dublin, Ireland nikola@umd.edu rahul.nair@ie.ibm.com pschon@umd.edu elisemh@umd.edu Matthew Mohebbi – IT Curves, Gaithersburg, MD 20879 – mmohebbi@itcurves.net

Download Article

This paper describes the development and implementation of a computerized system for managing shared-ride prescheduled door-to-door transportation services for elderly and disabled passengers. Cooperation between a research team from the University of Maryland (UMD) and the development team from Information Technologies Curves (IT Curves) resulted in an enhanced computerized ride-sharing system solution marketed by IT Curves in 2012. An IT Curves suite of transportation management solutions called Mobile Resource Management System (MRMS) was implemented in the operations of a number of midsize transportation service providers, yielding significant expense reductions. This paper describes the implementation of the MRMS in the operations of Regency Taxi, which is one of the largest dial-a-ride (DAR) service providers in Maryland, USA. Switching from manual to MRMS computerized vehicle routing and scheduling yielded Regency Taxi many benefits. Test comparison of manual and computer-based routes indicated an estimated annual operational expense reduction of $0.82 million, or about 17% of the total annual expense. The implemented management system also enabled Regency Taxi to quickly study different operational scenarios and explore tradeoffs between the level-of-service and various system characteristics. Such insights play a key role in making long-term investment decisions in the fleet, or when bidding for contracts that require certain levels-of-service. Broader societal and environmental benefits are also observed in reducing external cost by optimizing vehicle-km traveled to provide these services.

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-floor buses complemented with “kneeling devices” and specialized ramps, installing elevators in rail stations, and introducing higher platforms. Nevertheless, many handicapped and elderly people still find it difficult to use public transit despite these recent enhancements. Some handicapped or elderly people need additional help, while others may find the closest stop to be too far away, or the headway too long to wait (Borndoerfer et al. 1997). Transit systems across the world offer these people special door-to-door transportation, which is often called dial-a-ride (DAR) service.

One of the largest DAR service providers in Maryland, Regency Taxi (RT), switched from manual to computer-based routing in 2012, hoping thereby to improve the service quality as well as the efficiency of its DAR operations. RT implemented the computerized fleet management system MRMS marketed by IT Curves. The implemented system provided RT with a potential for considerable expense reductions and also enabled it to study its costs under different operating scenarios. This paper describes the development of the operations research (OR) tools built into the MRMS. It describes the adoption and implementation of vehicle routing and scheduling methods of OR in an actual application. Thus, it makes the following contributions:

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.

In the next section, the paper explains the development of the MRMS. The dial-a-ride problem is defined and the advantages and disadvantages of various solution methods are discussed in the following section. The next three sections include the mathematical formulation of the problem, a heuristic solution approach, and numerical tests of the proposed heuristic. The subsequent section provides an overview of RT’s operations and the challenges it faced while manually routing its vehicles. Then, the benefits from implementing the MRMS in RT’s operations are analyzed on both operational and tactical-strategic levels. Finally, conclusions are drawn and further extensions of this work are suggested.

Development of the MRMS

In 2011, IT Curves partnered with UMD to develop a tool for managing DAR services called the MRMS. The MRMS needed to include algorithms enabling a DAR operator to efficiently schedule and route vehicles while satisfying various level-of-service (LOS) and system constraints. The MRMS was expected to provide operators with many parameters that could be set for different runs allowing the operators to experiment and find the optimal tradeoff between LOS and operating and capital expenses. The joint objective of the research and development teams was to bring the state-of-the-art in managing DAR operations into the state-of-the-practice with an affordable and user-friendly software suite. Current wide availability of wireless data, powerful tablets and wireless devices, built-in navigation tools, and powerful back office computing power made this goal achievable.

The UMD team was requested to review operations research tools for routing and scheduling vehicles in DAR operations and adapt a chosen solution method that best fits requirements of several DAR companies that were seen as potential users of the MRMS. Since the vast majority of trips in DAR operations are scheduled one to seven days in advance, the emphasis was placed on the so called static DAR problem (DARP), which belongs to the generic class of vehicle routing problems. The static DARP and different solution methods are analyzed in details in subsequent sections of this paper.

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