A NEW REGRET INSERTION HEURISTIC FOR SOLVING LARGE-SCALE DIAL-A-RIDE PROBLEMS WITH TIME WINDOWS

Document Type

Journal Article

Publication Date

2004

Subject Area

operations - scheduling, planning - methods, planning - route design, mode - paratransit

Keywords

Travel time, Scheduling, Routes and routing, Paratransit services, Los Angeles County (California), Journey time, Heuristic methods, Dial a ride, Algorithms

Abstract

The dial-a-ride problem is similar to the pickup and delivery problem with the added constraint of restricting the maximum passenger ride time. This study presents a parallel regret insertion heuristic to solve the dial-a-ride problem with time windows. A new route initialization procedure is implemented that keeps into account both the spatial and the temporal aspects of the problem, and a regret insertion is then performed to serve the remaining requests. The proposed algorithm was tested on data sets of 500 to 1000 requests built from data of paratransit service in the Los Angeles County area. Computational time for solving the problem is especially important for large-scale systems where numerous daily requests need to be processed. The results from the example show that this approach is effective in terms of trading-off solution quality and computational times.

Comments

Transportation Research Part B Home Page: http://www.sciencedirect.com/science/journal/01912615

Link to Full Text

Share

COinS