An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems
| Autor: | Milad Rafiee, Varun G. Menon, Javad Mokhtari Koushyar, Mohammad Reza Khosravi, Mahdi Abbasi, Alireza Jolfaei |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Optimization problem
lcsh:Computer engineering. Computer hardware Computer Networks and Communications Computer science Distributed computing Evolutionary algorithm Cloud computing lcsh:TK7885-7895 02 engineering and technology Travelling salesman problem lcsh:QA75.5-76.95 Genetic algorithm Vehicle routing problem 0202 electrical engineering electronic engineering information engineering Intelligent transportation system business.industry 020206 networking & telecommunications Transportation systems Parallel Vehicle routing 020201 artificial intelligence & image processing lcsh:Electronic computers. Computer science Routing (electronic design automation) business Software |
| Zdroj: | Journal of Cloud Computing: Advances, Systems and Applications, Vol 9, Iss 1, Pp 1-14 (2020) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|