A genetic-based clustering approach to traffic network design for car navigation system

Author

Wen, Feng ; Gen, Mitsuo

Author_Institution

Grad. Sch. of Inf., Production & Syst., Waseda Univ., Kitakyushu

fYear

2008

fDate

12-15 Oct. 2008

Firstpage

1688

Lastpage

1693

Abstract

This paper considers the multicriteria route selection problem (mRSP) for car navigation systems in traffic road network. A multilayer hierarchy network method is proposed to substantially reduce the computation time when solving mRSP in big scale road network. In our proposed hierarchical method, an efficient genetic-based cluster method is used to overcome the size limitations with acceptable loss of accuracy. This hierarchical method is used to preprocess original road network. Then, multiobjective genetic algorithm (MOGA) is used to find a set of near-optimal routes is evaluated in a large city road network containing up to ten thousand nodes. Solutions provided by the proposed algorithm are compared with the optimal solutions to analyze and quantify the loss of accuracy.

Keywords

automobiles; genetic algorithms; graph theory; pattern clustering; road traffic; car navigation system; clustering approach; graph theory; multicriteria route selection problem; multilayer hierarchy network method; multiobjective genetic algorithm; road traffic network design; Algorithm design and analysis; Cities and towns; Clustering algorithms; Costs; Genetic algorithms; Navigation; Production systems; Roads; Shortest path problem; Telecommunication traffic; clustering; genetic algorithm; multi-layer hierarchy network; multicriterion route selection problem (mRSP);

fLanguage

English

Publisher

ieee

Conference_Titel

Systems, Man and Cybernetics, 2008. SMC 2008. IEEE International Conference on

Conference_Location

Singapore

ISSN

1062-922X

Print_ISBN

978-1-4244-2383-5

Electronic_ISBN

1062-922X

Type

conf

DOI

10.1109/ICSMC.2008.4811531

Filename

4811531