UPM Institutional Repository

Genetic algorithms for urban transit routing problems


Citation

Chew, Joanne Suk Chun (2012) Genetic algorithms for urban transit routing problems. Masters thesis, Universiti Putra Malaysia.

Abstract

The problem of road congestion occurs in most of the urban cities in the world. An e±cient public transportation system is vitae in helping to reduce the overall tra±c on the road. The urban transit routing problem (UTRP) is involved in searching for a set of routes for the urban public transportation system, which proved to be a highly complex multi-constrained problem. UTRP is a NP-hard problem where a lot of criteria need to be met in order to generate a feasible solution. Metaheuristic algorithm is suitable for the di±culties of this problem. Thus in this study, one such metaheuristic algorithm, genetic algorithm (GA) is developed to solve the UTRP. The objective of this study is to design a GA to solve the UTRP. Due to the complexity of the UTRP, there is always a possibility of getting an infeasible chro- mosome. Thus, each chromosome is tested by a set of feasible criteria and modi¯-cation is made for the infeasible chromosomes. The genetic operations of crossover and mutation are also introduced to help the GA in exploring new characteristics for the chromosome and to maintain the diversity of the population as the GA evolves in each generation. The proposed algorithm is ¯rst applied to the single objective of UTRP which involves only the passengers' cost. It is later expanded to the bi-objective of UTRP which looks into the operator's cost as well. Due to the contradicting objective functions of the bi-objective UTRP, a trade-o® between the two objective functions is needed. Our proposed GA will search the Pareto Frontier and Pareto-optimal solutions are returned as the non-dominated solu- tions. The results obtained from the single and bi-objective of UTRP show that our proposed GA signi¯cantly improves the results compared to other published results in the literature for the Mandl's Swiss road network benchmark problem.


Download File

[img]
Preview
PDF
FS 2012 58R.pdf

Download (833kB) | Preview

Additional Metadata

Item Type: Thesis (Masters)
Subject: Genetic algorithms
Subject: Local transit
Subject: Urban transportation
Call Number: FS 2012 58
Chairman Supervisor: Lee Lai Soon, PhD
Divisions: Faculty of Science
Depositing User: Haridan Mohd Jais
Date Deposited: 13 Jan 2015 01:34
Last Modified: 13 Jan 2015 01:34
URI: http://psasir.upm.edu.my/id/eprint/32755
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item