research-article

Hybrid genetic algorithm for dynamic multi-objective route planning with predicted traffic in a real-world road network

Authors:

Kenta HaraAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 657 - 664

https://doi.org/10.1145/1389095.1389226

Published: 12 July 2008 Publication History

Abstract

Car navigation equipment in practical use has treated a route planning problem as a single-objective problem. In this paper, we formulate the problem as a dynamic multi-objective problem and show how it can be solved using a GA. There are three objective functions to optimize simultaneously in this problem: route length, travel time that changes rapidly with time, and ease of driving. The proposed method gives the Pareto-optimal set by using both the predicted traffic and a hybrid multi-objective GA (GA + Dijkstra algorithm) so that a driver can choose a favorite route after looking at feasible ones. We give the results of experiments comparing the proposed method with the Dijkstra algorithm and the single-objective GA in applications with a real road map and real traffic data in wide-area road network.

References

[1]

Golden, B., Shortest-path algorithms -- a comparison --, Operations Research, Vol. 24, No.9, pp. 1164--1168, 1976.

Digital Library

[2]

Chan, E. P. F. and Zhang, N., Finding shortest paths in large network systems, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, pp. 160--166, 2001.

Digital Library

[3]

Fu, M., Li, J., and Deng, Z, A practical route planning algorithm for vehicle navigation system, Fifth World Congress on Intelligent Control and Automation (WCICA 2004.), Vol. 6, pp. 5326--5329, 2004.

[4]

Pattanamekar, P., Park, D., Rilett, L.R., et al., Dynamic and stochastic shortest path in transportation networks with two components of travel time uncertainty, Transportation Research Part C 11, pp. 331--354, 2003.

[5]

Maria, J., Pangiliana, A., and Janssens, G. K., Evolutionary algorithms for the multiobjective shortest path planning problem, International journal of computer and information science and engineering, Vol. 1, No. 1, pp. 54--59, 2007.

[6]

Castillo, O., Trujillo, L., and Melin, P., Multiple objective genetic algorithms for path--planning optimization in autonomous mobile robots, Soft computing -- A Fusion of foundations, methodologies and applications, Vol. 11, No. 3, pp. 269--279, 2007.

Digital Library

[7]

Kanoh, H., Dynamic route planning for car navigation systems using virus genetic algorithms, International Journal of Knowledge and Intelligent Engineering Systems 11, pp. 65--78, 2007.

Digital Library

[8]

Kanoh, H., Furukawa, T., Tsukahara, S., Hara, K., Nishi, H., and Kurokawa, H., Short-term traffic prediction using fuzzy c--means and cellular automata in a wide-area road network, IEEE International Conference on Intelligent Transportation Systems, ITSC'2005, pp. 984--988, 2005.

[9]

Van Veldhuizen, D.A and Lamont, G.B., Multiobjective evolutionary algorithms: Analyzing the state-of-the-art, Evolutionary Computation, Vol. 8, No. 2, pp. 125--147, 2000.

Digital Library

[10]

Zitzler, E., Laumanns, M., and Bleuler, S., A tutorial on evolutionary multiobjective optimization, In Xavier Gandibleux et al, editor, Mathematics for Multiobjective Optimizationpp.3--37, Berlin, Springer. Lecture Notes in Economics and Mathematical Systems Vol. 535, 2004.

[11]

Carlos, A., Evolutionary multi-objective optimization: a historical view of the field, IEEE Computational Intelligence Magazine, February, pp. 28--37, 2006.

Digital Library

[12]

Navigation System Researchers' Association, http://www.naviken.jp/.

[13]

Shiraishi, T, et al., A personal navigation system with a schedule planning facility cased on multi--objective criteria, International conference on mobile computing and ubiquitous networking (ICMU 2005), pp.104--109, 2005.

[14]

Huang, B., Yao, L., and Raguraman, K., Bi-level GA and GIS for multi-^objective TSP route planning, Transportation planning and technology, Vol. 29, No. 2, pp.105--124, 2006.

[15]

Chakraborty, B., Maeda, T., and Chakraborty, G., Multiobjective route selection for car navigation system using genetic algorithm, IEEE Mid-Summer workshop on soft computing in industrial application (SMXia/05), pp. 190--195, 2005.

[16]

Farina, M., Deb, K., and Amato, P., Dynamic multiobjective optimization problems: test case, approximations, and applications, IEEE Transactions on evolutionary computation Vol. 8, No. 5, pp. 425--442, 2004.

Digital Library

[17]

Hatzakis, I. and Wallace, D., Dynamic multi-objective optimization with evolutionary algorithms: A forward-looking approach, Genetic and evolutionary computation conference (GECCO'06), pp. 1201--1208, 2006.

Digital Library

[18]

Lui, C. and Wang, Y., Dynamic multi-objective optimization evolutionary algorithm, International conference on natural computation (ICNC'07), Vol. 4, pp. 456--459, 2007.

Digital Library

[19]

Zhou, A., et al., Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization, Lecture note in computer science, Vol. 4403, pp. 832--846, 2007.

Digital Library

Cited By

Tei HKawakami TKawamoto Y(2024)A Safe Vehicle Routing System based on Road Characteristics from Telematics Data2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00272(1726-1731)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00272
Gao KXu L(2024)Novel strategies based on a gradient boosting regression tree predictor for dynamic multi-objective optimizationExpert Systems with Applications10.1016/j.eswa.2023.121532237(121532)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.121532
Röper EWeise JSteup CMostaghim S(2024)Innovization for Route Planning Applied to an Uber Movement Speeds Dataset for BerlinParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_7(100-116)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_7
Show More Cited By

Index Terms

Hybrid genetic algorithm for dynamic multi-objective route planning with predicted traffic in a real-world road network
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Multi-objective Transmission Expansion Planning Using an Elitist Non-dominated Sorting Genetic Algorithm with Fuzzy Decision Analysis
AMS '11: Proceedings of the 2011 Fifth Asia Modelling Symposium

The main objective of transmission expansion planning in deregulated power systems is to provide a non-discriminatory competitive environment for all stakeholders, while maintaining power system reliability. In this paper, a static transmission ...
The elitist non-dominated sorting genetic algorithm with inheritance (i-NSGA-II) and its jumping gene adaptations for multi-objective optimization

Initial random parent population with inheritance in NSGA-II (i-NSGA-II).Jumping gene (JG) adaptations in NSGA-II with inheritance.Improved speed of convergence to the global Pareto-optimal front.Metrics of multi-objective evolutionary algorithms.Multi-...
A multi-objective continuous genetic algorithm for financial portfolio optimization problem
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Financial portfolio management with both quantity and cardinality constraints can be modeled as a NP-hard continuous optimization problem where two objectives are optimized: maximizing the return of the portfolio and minimizing its risk. In this paper, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
879
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tei HKawakami TKawamoto Y(2024)A Safe Vehicle Routing System based on Road Characteristics from Telematics Data2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00272(1726-1731)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00272
Gao KXu L(2024)Novel strategies based on a gradient boosting regression tree predictor for dynamic multi-objective optimizationExpert Systems with Applications10.1016/j.eswa.2023.121532237(121532)Online publication date: Mar-2024
https://doi.org/10.1016/j.eswa.2023.121532
Röper EWeise JSteup CMostaghim S(2024)Innovization for Route Planning Applied to an Uber Movement Speeds Dataset for BerlinParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_7(100-116)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_7
Tsoukas VBoumpa EChioktour VKalafati MSpathoulas GKakarountas A(2023)Development of a Dynamically Adaptable Routing System for Data Analytics Insights in Logistic ServicesAnalytics10.3390/analytics20200182:2(328-345)Online publication date: 13-Apr-2023
https://doi.org/10.3390/analytics2020018
Tomić JGazivoda NKušljević MSovilj PŠaš M(2023)Travel Route Planning in Smart Cities2023 Zooming Innovation in Consumer Technologies Conference (ZINC)10.1109/ZINC58345.2023.10174121(88-92)Online publication date: 29-May-2023
https://doi.org/10.1109/ZINC58345.2023.10174121
Boumpa ETsoukas VChioktour VKalafati MSpathoulas GKakarountas ATrivellas PReklitis PMalindretos G(2022)A Review of the Vehicle Routing Problem and the Current Routing Services in Smart CitiesAnalytics10.3390/analytics20100012:1(1-16)Online publication date: 22-Dec-2022
https://doi.org/10.3390/analytics2010001
Weise JMostaghim S(2022)A Scalable Many-Objective Pathfinding Benchmark SuiteIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.308905026:1(188-194)Online publication date: Feb-2022
https://doi.org/10.1109/TEVC.2021.3089050
Goje BNayak P(2022)A Deep Survey on Vehicular Route Guidance Algorithms and Implemented Systems2022 3rd International Conference on Smart Electronics and Communication (ICOSEC)10.1109/ICOSEC54921.2022.9951975(689-696)Online publication date: 20-Oct-2022
https://doi.org/10.1109/ICOSEC54921.2022.9951975
Jocko POmbuki-Berman BEngelbrecht A(2022)Dynamic Multi-objective Optimisation Using Multi-guide Particle Swarm Optimisation2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870299(1-10)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870299
Pradhan RAgarwal ADe T(2022)A Multi-Criteria Route Selection Method for Vehicles Using Genetic Algorithms Based on Driver’s PreferenceWireless Personal Communications10.1007/s11277-022-09670-6125:3(2477-2496)Online publication date: 7-Apr-2022
https://doi.org/10.1007/s11277-022-09670-6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten