Genetic algorithms for urban transit routing problems

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 transportati...

Full description

Saved in:

Bibliographic Details
Main Author:	Chew, Joanne Suk Chun
Format:	Thesis
Language:	English
Published:	2012
Subjects:	Genetic algorithms Local transit Urban transportation
Online Access:	http://psasir.upm.edu.my/id/eprint/32755/1/FS%202012%2058R.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.32755
record_format	uketd_dc
spelling	my-upm-ir.327552015-01-13T01:34:43Z Genetic algorithms for urban transit routing problems 2012-04 Chew, Joanne Suk Chun 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. Genetic algorithms Local transit Urban transportation 2012-04 Thesis http://psasir.upm.edu.my/id/eprint/32755/ http://psasir.upm.edu.my/id/eprint/32755/1/FS%202012%2058R.pdf application/pdf en public masters Universiti Putra Malaysia Genetic algorithms Local transit Urban transportation
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English
topic	Genetic algorithms Local transit Urban transportation
spellingShingle	Genetic algorithms Local transit Urban transportation Chew, Joanne Suk Chun Genetic algorithms for urban transit routing problems
description	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.
format	Thesis
qualification_level	Master's degree
author	Chew, Joanne Suk Chun
author_facet	Chew, Joanne Suk Chun
author_sort	Chew, Joanne Suk Chun
title	Genetic algorithms for urban transit routing problems
title_short	Genetic algorithms for urban transit routing problems
title_full	Genetic algorithms for urban transit routing problems
title_fullStr	Genetic algorithms for urban transit routing problems
title_full_unstemmed	Genetic algorithms for urban transit routing problems
title_sort	genetic algorithms for urban transit routing problems
granting_institution	Universiti Putra Malaysia
publishDate	2012
url	http://psasir.upm.edu.my/id/eprint/32755/1/FS%202012%2058R.pdf
_version_	1747811675632828416

Genetic algorithms for urban transit routing problems

Similar Items