A metaheuristic approach to the urban transit routing problem

Fan, Lang and Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 2010. A metaheuristic approach to the urban transit routing problem. Journal of Heuristics 16 (3) , pp. 353-372. 10.1007/s10732-008-9089-8

Full text not available from this repository.

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Uncontrolled Keywords:	Urban transit routing; Hill-climbing; Simulated annealing
Additional Information:	From the issue entitled 'Special Issue on Recent Advances in Metaheuristics. Guest Editors: Teodor Gabriel Crainic, Michel Gendreau, and Louis-Martin Rousseau'
Publisher:	Springer
ISSN:	1381-1231
Last Modified:	18 Oct 2022 13:29
URI:	https://orca.cardiff.ac.uk/id/eprint/14119

Citation Data

Cited 66 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item