01333010

Component

https://doi.org/10.3141/2218-07

http://scholar.google.com...feld&publication_year=2011

This paper presents and compares online implementations of rejected-reinsertion heuristics for the dynamic multivehicle dial-a-ride problem (DARP), which the authors previously developed for static DARP. In dynamic DARP, transportation requests are received in real time, whereas in static DARP, all information about service requests is known in advance. The main objective for the DARP heuristics is to minimize the number of vehicles used to satisfy all trip requests, subject to service quality constraints. Two online implementation strategies, called “immediate insertion” and “rolling-horizon insertion,” coupled with two variations of the insertion heuristic rejected reinsertion without and with periodic improvement procedures, are developed and compared. Computational results show that the rolling-horizon insertion heuristics, which take advantage of the advance information available, achieve vehicle reductions of up to 10% more than their immediate-insertion counterpart. The proposed online rejected-reinsertion heuristics achieve vehicle reductions up to 16% and 10% more, respectively, than the online parallel insertion heuristics that use immediate insertion and rolling-horizon insertion strategies, while keeping the computation time at the same magnitude as the parallel-insertion heuristics. Sensitivity analysis shows that the rolling-horizon insertion heuristics are insensitive to the time horizon and the rolling interval.

01355106

11-1655

English

pp 59-67

2011

Transportation Research Record: Journal of the Transportation Research Board

9780309167406

Print

Figures (3) ; References (19) ; Tables (4)

Heuristic methods; Paratransit services; Routing; Scheduling; Sensitivity analysis

Rolling horizon

Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning

TRIS, TRB, ATRI

Feb 17 2011 5:53PM

• Accessible Transportation and the Built Environment on College Campuses
• Creation of Life-Cycle Cost Tool for Transit Buses to Evaluate Hybrid Electric Bus Technologies in Real-World Operation
• Feasibility of Converting Two-Way Left-Turn Lane into Bus Rapid Transit Lane
• High-Coverage Point-to-Point Transit: Study of Path-Based Vehicle Routing Through Multiple Hubs
• Innovative Operating Solutions for Bus Rapid Transit Through a Congested Segment of San Jose, California
• Introduction of a Reserved Bus Lane: Impact on Bus Running Time and On-Time Performance
• Joint Optimization of Bus Size, Headway, and Slack Time for Efficient Timed Transfer
• Model and Algorithm Considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem
• Safety and Operational Assessment of Yield-to-Bus Electronic Warning Signs on Transit Buses