Institute of Transportation, MOTC-Digital Archive-Transportation Dissertation-A Study on the Optimal Assignment Operation for the Dial-and-Ride Problem.

Digital Archive

:::

Transportation Dissertation

Title	A Study on the Optimal Assignment Operation for the Dial-and-Ride Problem.
Year	2006
Summary	Han-Hsuan Huang, 2006.06 Graduate Institute of Transportation Science, Tamkang University 　　The Dial-a-Ride system can provide door-to-door and real-time service with the capacity of the traditional bus system. It is special transportation service for the handicapped citizen. The service usually is carried by the advanced order of passengers, and routing plan of service is scheduled based on these demands. The Dial-a-Ride Problem (DARP) is a vehicle routing problem for the arrangement of the Dial-a-Ride service. 　　The DARP has been proved to be a NP-Hard problem, therefore, most researches addressed this problem adopted heuristic methods as the solution methods. "Vertex Reinsertion" has been adopted by previous studies. Although, it is popular solution procedure, its computation efficiency is not impressed. With tremendous interest of the Meta-heuristics on the combinatorial problem, there is few study discuss its application on the DARP. The purpose of this study is to evaluation of the application of the Genetic Algorithm (GA) and the Ant Colony Optimization (ACO) on the DARP. 　　Two solution procedures are proposed in this study, i.e., an integrated approach and cluster first route second approach. A series of revised GA and ACO algorithms are developed for these two approaches. A series of case studies with different characteristics such as demand density, demand size were used to test the solution capability of the proposed algorithms. Based on the results of the case studies, the Diversity-controlling Adaptive Genetic Algorithm is identified as the best algorithm in solution quality, and the Ant Colony Optimization is proved to be able to solve the problem quickly. 　　In addition, the DARP with stochastic travel times has been test in the final part of the analysis. Different types of the decision criteria have been used to identify good decision criteria for the dynamic DARP. Based on the test results, threshold value is 20% of the difference of sum routing durations between new and old routing plans has been proven to be better decision criteria for the dynamic DARP.

Title

A Study on the Optimal Assignment Operation for the Dial-and-Ride Problem.

Year

2006

Summary

Han-Hsuan Huang, 2006.06
Graduate Institute of Transportation Science, Tamkang University

　　The Dial-a-Ride system can provide door-to-door and real-time service with the capacity of the traditional bus system. It is special transportation service for the handicapped citizen. The service usually is carried by the advanced order of passengers, and routing plan of service is scheduled based on these demands. The Dial-a-Ride Problem (DARP) is a vehicle routing problem for the arrangement of the Dial-a-Ride service.
　　The DARP has been proved to be a NP-Hard problem, therefore, most researches addressed this problem adopted heuristic methods as the solution methods. "Vertex Reinsertion" has been adopted by previous studies. Although, it is popular solution procedure, its computation efficiency is not impressed. With tremendous interest of the Meta-heuristics on the combinatorial problem, there is few study discuss its application on the DARP. The purpose of this study is to evaluation of the application of the Genetic Algorithm (GA) and the Ant Colony Optimization (ACO) on the DARP.
　　Two solution procedures are proposed in this study, i.e., an integrated approach and cluster first route second approach. A series of revised GA and ACO algorithms are developed for these two approaches. A series of case studies with different characteristics such as demand density, demand size were used to test the solution capability of the proposed algorithms. Based on the results of the case studies, the Diversity-controlling Adaptive Genetic Algorithm is identified as the best algorithm in solution quality, and the Ant Colony Optimization is proved to be able to solve the problem quickly.
　　In addition, the DARP with stochastic travel times has been test in the final part of the analysis. Different types of the decision criteria have been used to identify good decision criteria for the dynamic DARP. Based on the test results, threshold value is 20% of the difference of sum routing durations between new and old routing plans has been proven to be better decision criteria for the dynamic DARP.

Count Views:310

Pre Page