A metaheuristic approach to the urban transit routing problem |
| |
Authors: | Lang Fan Christine L Mumford |
| |
Institution: | (1) Civil and Environmental Engineering Department, University of Nevada, 4505 Maryland Parkway, P. O. Box 454015, Las Vegas, NV 89154-4015, USA;(2) School of Civil Engineering, Purdue University, 550 Stadium Mall Drive, West Lafayette, IN 47907-2051, USA |
| |
Abstract: | The urban transit routing problem (UTRP) is NP-Hard and involves devising routes for public transport systems. It is a highly
complex multi-constrained problem and the evaluation of candidate route sets can prove both time consuming and challenging,
with many potential solutions rejected on the grounds of infeasibility. Due to the problem difficulty, metaheuristic algorithms
are highly suitable, yet the success of such methods depend heavily on: (1) the quality of the chosen representation, (2) the effectiveness of the initialization procedures and (3) the suitability of the chosen neighbourhood moves. Our paper focuses on these three issues, and presents a framework which can be used as a starting point for solving this
problem. We devise a simple model of the UTRP to evaluate candidate route sets. Finally, our approach is validated using simple
hill-climbing and simulated annealing algorithms. Our simple method improves upon published results for Mandl’s benchmark
problems. In addition, the potential for solving larger problem instances has been explored. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|