Model and algorithm for solving real time dial-a-ride problem

dc.contributor.advisorHaghani, Alien_US
dc.contributor.authorKIM, TAEHYEONGen_US
dc.contributor.departmentCivil Engineeringen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2011-10-08T06:01:40Z
dc.date.available2011-10-08T06:01:40Z
dc.date.issued2011en_US
dc.description.abstractThis 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.en_US
dc.identifier.urihttp://hdl.handle.net/1903/11963
dc.subject.pqcontrolledCivil engineeringen_US
dc.subject.pqcontrolledTransportation planningen_US
dc.subject.pquncontrolledDial-a-rideen_US
dc.subject.pquncontrolledHeuristicen_US
dc.subject.pquncontrolledOptimizationen_US
dc.subject.pquncontrolledParatransiten_US
dc.titleModel and algorithm for solving real time dial-a-ride problemen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
KIM_umd_0117E_12523.pdf
Size:
2.16 MB
Format:
Adobe Portable Document Format