| Summary |
Chi-Wai Yuen,2007.06
Department of Transportation Technology and Management National Chiao Tung University
The Dial-A-Ride problem (DARP) is a problem of providing demand responsive transport that delivers passengers from their specified origins to destinations with desired time windows. To keep a level of services, the operator should deliver the passengers subject to maximum riding time and waiting time constraints. Such problem is similar to the pick-up and delivery problem with time windows in the theme of supply chain management, but considering passenger transportation rather than goods transportation. In a Static Dial-A-Ride Problem, the operator accepts requests before the day of operation, while the Dynamic Dial-A-Ride Problem (DDARP) allows receiving requests throughout the operating period. This study focused on solving DDARP, under different degree of dynamism (dod), with minimum operating vehicles and minimum total travel distance.
There are two sub-problems solving DDARP: routing and scheduling is a sub-problem for route constructions which aims to plan the vehicle routes and stops in visiting the requests with several objectives. The Cheapest Insertion (CI) method is used to construct initial routes which can later be improved by exchange method.
Scheduling is a sub-problem for designing the arrival and departure time for each stop along the routes. It aims to insert as many real-time requests as possible in each vehicle during the day of operation. Three different strategies, namely, Drive First (DF), Wait First (WF) and Dynamic Wait (DW) are described in this study.
A set of simulation experiments were designed to evaluate the performance of the three waiting strategies under different dod. Compared to the results of DF strategy and WF strategy, the DW strategy provides a better solution with requiring less operating vehicles and shorter travel distance. We found that the requirement of extra operating costs serving a fixed number of dynamic requests decreased as more requests were known in-advance. This observation follows the principle of “economy of scale”.
An interesting finding in the study was that the system may require less operating vehicles and total travel distance in a fully dynamic environment (dod = 100%) as compared to a highly dynamic problem (say dod = 60%), under a fixed number of total requests. This is in opposition to our intuition that more information can bring the system to a lower cost, and we name this case a “counter-intuitive” observation. |
