This research studies a static and real-time dial-a-ride problem with time varying travel times, soft time windows, and multiple depots. First, a static DARP model is formulated as a mixed integer programming and in order to validate the model, several random small network problems are solved using commercial optimization package, CPLEX.
Three heuristic algorithms based on sequential insertion, parallel insertion, and clustering first-routing second are proposed to solve static DARP within a reasonable time for implementation in a real-world situation. Also, the results of three heuristic methods are compared with the results obtained from exact solution by CPLEX to validate and evaluate three heuristic algorithms. Computational results show that three heuristic algorithms are superior compared to the exact algorithm in terms of the calculation time as the problem size (in terms of the number of demands) increases. Also among the three heuristic algorithms, the heuristic algorithm based on sequential insertion is more efficient than other heuristic algorithms that are based on parallel insertion and clustering first-routing second.
For the case study, Maryland Transit Administration (MTA)'s real operation of Dial-a-ride service is introduced and compared with the results of developed heuristic. The objective function values from heuristic based on clustering first- routing second are better than those from MTA's operation for all cases when waiting cost, delay cost, and excess ride cost are not included in the objective function values.
Also, the algorithm for real-time DARP considering dynamic events such as customer no shows, accidents, cancellations, and new requests is developed based on static DARP. The algorithm is tested in a simulation framework. In the simulation test, we compared the results of cases according to degree of gap between expected link speeds and real link speeds. Also for competitive analysis, the results of dynamic case are compared with the results of static case, where all requests are known in advance. The simulation test shows that the heuristic method could save cost as the uncertainty in new requests increases.
|Commitee:||Chang, Gang-Len, Golden, Bruce, Lee, Sung, Schonfeld, Paul|
|School:||University of Maryland, College Park|
|School Location:||United States -- Maryland|
|Source:||DAI-B 73/02, Dissertation Abstracts International|
|Subjects:||Civil engineering, Transportation planning|
|Keywords:||Dial-a-ride, Heuristic algorithms, Optimization, Paratransit, Travel times|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be