An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems

Mahdi Abbasi*, Milad Rafiee, Mohammad R. Khosravi, Alireza Jolfaei, Varun G. Menon, Javad Mokhtari Koushyar

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

A novel parallelization method of genetic algorithm (GA) solution of the Traveling Salesman Problem (TSP) is presented. The proposed method can considerably accelerate the solution of the equivalent TSP of many complex vehicle routing problems (VRPs) in the cloud implementation of intelligent transportation systems. The solution provides routing information besides all the services required by the autonomous vehicles in vehicular clouds. GA is considered as an important class of evolutionary algorithms that can solve optimization problems in growing intelligent transport systems. But, to meet time criteria in time-constrained problems of intelligent transportation systems like routing and controlling the autonomous vehicles, a highly parallelizable GA is needed. The proposed method parallelizes the GA by designing three concurrent kernels, each of which running some dependent effective operators of GA. It can be straightforwardly adapted to run on many-core and multi-core processors. To best use the valuable resources of such processors in parallel execution of the GA, threads that run any of the triple kernels are synchronized by a low-cost switching mechanism. The proposed method was experimented for parallelizing a GA-based solution of TSP over multi-core and many-core systems. The results confirm the efficiency of the proposed method for parallelizing GAs on many-core as well as on multi-core systems.

Original languageEnglish
Article number6
Pages (from-to)1-14
Number of pages14
JournalJournal of Cloud Computing
Volume9
DOIs
Publication statusPublished - 3 Feb 2020

Bibliographical note

Copyright the Author(s) 2020. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

  • Cloud computing
  • Genetic algorithm
  • Parallel
  • Transportation systems
  • Vehicle routing

Fingerprint Dive into the research topics of 'An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems'. Together they form a unique fingerprint.

  • Cite this