Aug 10 Management System for Dial-a-Ride Operations
Industry partner: IT Curves
Lead: Matthew Mohebbi
with
Academic partner: Dept. of Civil and Env. Eng.
University of Maryland
Co-PIs: Elise Miller-Hooks and Paul Schonfeld
Student Researchers: Nikola Marković, Bing Qi and Lei Feng
Objective of our MIPS Project
Develop a commercially successful fleet management tool to support paratransit operations as part of the Mobile Resources Management System (MRMS)
Include algorithms within the MRMS to enable paratransit operators to efficiently schedule and route vehicles while satisfying various service constraints
Paratransit: Dial-a-Ride
Better accessibility to public transportation has become an important objective for many transit systems across the world
This objective has been partially achieved by installing elevators in metro stations, introducing low-floor buses, and implementing higher platforms
Some handicapped or elderly people need additional help, may find the closest stop to be too far away, or the headway too long to wait
Washington Metropolitan Area Transit Authority (WMATA) offers these people a special door-to-door transportation which is often referred to as dial-a-ride (DAR) service
Ridership and Eligibility
WMATA started providing DAR service in 1994, and since that time the annual ridership has grown from 200,000 to over 2.4 million passengers, making this the sixth largest U.S. DAR operation.
WMATA staff determines eligibility to use the service in response to written applications, based on the recommendations from Americans with Disability Act (ADA) from 1990.
ADA defines three categories of people who are eligible for paratransit. They include persons who:
1. Are unable to get on, ride, or get off an accessible public transit vehicle due to a physical or mental impairment
2. Need the assistance of a wheelchair lift or other boarding assistance device, BUT such a vehicle is not available on the route when the individual wants to travel
3. Have a specific impairment-related condition which prevents travel to or from a station or stop on the system
Subsidies
Riders pay twice the quickest fixed-route transit fare – up to a maximum of $7 per ride. This does not cover the cost of a trip. To cover the remainder, the local jurisdiction pays WMATA $45 for each trip!
WMATA does not provide these services directly, but instead contracts the work out to private companies like Challenger Transportation.
Trip Requests
Customers schedule a trip by specifying:
Pickup and drop-off address
Desired pickup or drop-off time
Based on desired pickup or drop-off time the operator can design related time windows:
Future Trends in Paratransit
Dial-a-Ride service is the fastest growing part of WMATA’s budget:
Paratransit ridership growth of more than 10% per year is reported for 2006 through 2009, and this trend is expected to continue
This implies that any efficiency gained in current operations of Challenger Transportation will only increase in the future
Similar trends are observed in other paratransit operations:
Metro Council of St. Paul, Minnesota warned that paratransit ridership may grow by as much as 6% per year for the next 10 years
In response to these trends, other DAR companies are looking for opportunities to switch to computerized vehicle routing and scheduling:
1. to reduce manual effort
2. increase operational efficiency
3. improve responsiveness to customer needs
Dial-a-Ride Problem (DARP)
The dial-a-ride (paratransit) operator seeks to design routes and schedules that:
We should distinguish between static and dynamic DARP In static DARP all the requests are made at least a day in advance and the operator typically allows his dispatchers several hours to design routes and schedules
In dynamic DARP additional requests may be received on short notice, after some vehicles are already providing service and the operator must quickly assign new requests while considering previously built routes and schedules
Static DARP: Solution Methods
1. Exact methods:
2. Dynamic programming
3. Mathematical optimization using: Branch & Cut, Branch & Price or integer L-shaped method
1. Heuristic methods:
2.Cluster first, chain second
3.Insertion heuristic
1. Metaheuristic methods:
2. Tabu search
3. Simulated annealing
4. Genetic algorithms
5. Variable neighborhood search
6. Ant colony optimization
Selecting a Solution Method
Company’s requirements regarding solution method for static DARP:
1.To provide feasible solution to problems involving up to 5000 requests
2.To yield a feasible solution within less than 5 hrs of computation time
Based on company’s requirements an insertion heuristic was devised The Parallel Insertion Heuristic (Jaw et al. 1986) was identified as the most promising core algorithm on which to build
Parallel Insertion Heuristic (PIN)
Sort all customers by the earliest pickup time (or other criteria)
Starting with the first customer and one vehicle
1. Insert the customer in vehicle route that has the lowest cost
2. If no vehicle can serve this customer, add vehicle to fleet, and assign this new vehicle to serve the customer
Modifications
Our insertion algorithm differs from the classic PIN in the following ways:
1. Blocks and Locked Blocks
2. Outlier Procedures
3. Additional Performance Measures
4. Improvement Procedure
5. Rejected-Reinsertion Operator
6. Objective Function(s)
7. Drop-off and Mixed Pick-up/Drop-off Modes
The above features enabled a state-of-the-art algorithm to be applied in the daily operations of Challenger Transportation]
Challenger Case Study
The parallel insertion heuristic was tested on real-world data coming from Challenger Transportation
Challenger Transportation receives about 450 requests that need to be served on the following day (static DARP) The common time window for specified pickup is 60 min, the maximum route duration is 12 hours, and vehicle capacity is 7 passengers
The parallel insertion algorithm took about 7 min to build a feasible solution
We compared the MRMS-based routes with manually built route manifest and concluded that the number of routes and vehicle-km decreased by 12.8% and 22.4%, respectively.
Any additional savings?
The effects of time windows and route duration limit on fleet size
Thus, fewer vehicles are needed as the time windows and route duration limits are relaxed
The effects of time windows and route duration limit on operator’s cost
Thus, the operator’s cost decreases as the time windows and route duration limits are relaxed.
The tool allows for further study to gain insights. For example:
Steadier demand reduces the fleet and operator costs needed to serve all requests
The effects of vehicle capacity on fleet size
The effects of time windows on system performance measures
Dynamic DARP
The vast majority (about 90%) of DAR requests are prescheduled; however, new requests can be made for the same day
The operator needs to insert these requests relatively quickly considering previously built routes and current GPS locations of vehicles
The vast majority (about 90%) of DAR requests are prescheduled; however, new requests can be made for the same day
The operator needs to insert these requests relatively quickly considering previously built routes and current GPS locations of vehicles
The Online Insertion Heuristic (Luo 2006), a dynamic extension of the PIN heuristic, was implemented.
The logic behind the Online Insertion Heuristic is straightforward Main ideas:
1. Freezing the current schedule
2. Inserting the trip into the best position while considering the current vehicle locations
Reason for selection:
1. Computational efficiency
2. Can exploit functions previously coded for the PIN algorithm
Straightforward and easy to explain to customers
The required input for the Online Insertion Heuristic:
1. General info on the newly requested trips (O/D and time windows) 2. List of stops that were already visited 3. Current GPS positions of vehicles
Dynamic requests were generated for preliminary tests of the algorithm. Other test elements:
1. Visited stops noted at time of dynamic request
2. Current GPS positions of vehicles – assumed that vehicles were located at the last stop it visited prior to receipt of dynamic request
Tests using data provided by Challenger Transportation will be completed by end of project.
Missing practical requirements will be identified and addressed.
Summary
We coded, adapted and tested heuristics for static and dynamic DARP. The algorithms were implemented into the Mobile Resources Management System (MRMS).
The MRMS is currently being tested at Challenger Transportation. Challenger Transportation is planning to switch to MRMS based routing and scheduling in upcoming months.
Future of MRMS
We hope that MRMS will achieve commercial success and become a widely used tool for managing paratransit operations.
We hope that UMD students will continue improving optimization algorithms built into MRMS, making this tool even more effective and powerful.
Extensions of MRMS
The MRMS can be improved by enhancing the current optimization algorithms and by adding more features Current algorithms may be improved by:
1. Building a metaheuristic on top of the current insertion-based heuristic
2. Parallelization of the algorithms (or some of their routines) for speed-up
3. Computing additional measures of effectiveness
Expected new features in a proposed new project include:
Phase 1
1. Continuous optimization of routes in real-time
2. Integrated management of taxi and ridesharing services
3. Multiple categories of users and alternative combinations of price and service levels
4. Improved estimates of travel times through congested regions
5. Reassigning trips among vehicles when some vehicles deviate from their schedules
6. Multiple “depots”, including driver homes
7. More detailed labor work rules, cost rates and revenue formulas
8. Responding to trip cancellations, no-shows, vehicle breakdowns and other surprises
Phase 2
1. Managing transfers among ridesharing vehicles, taxis and other modes
2. Heterogeneous ridesharing vehicles and optimized fleet mix
3. Predicting near-term traffic conditions and demand and preparing accordingly (e.g. by efficiently inserting, removing or repositioning vehicles)
4. Seeking robust solutions that perform well over the range of uncertain future conditions.
Improvements attained through this second project will enable even greater efficiencies in paratransit operations, like Challenger Transportation, and the competitiveness of the proposed MRMS management system.
Dynamic Dial-A-Ride in the Literature
Dynamic DARP]
