An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems
An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems
复制标题
DOI：
10.1186/s13677-020-0157-4
复制
发表时间：
2020-02-03
影响因子：
4
通讯作者：
Koushyar, Javad Mokhtari
中科院分区：
文献类型：
--
作者：
Abbasi, Mahdi;Rafiee, Milad;Koushyar, Javad Mokhtari
提出了一种新的遗传算法求解旅行商问题的并行化方法。该方法可以大大加快智能交通系统云实现中的许多复杂车辆路径问题（VRP）的等效TSP的解决方案。该解决方案除了提供车辆云中自动驾驶车辆所需的所有服务外，还提供路由信息。遗传算法被认为是一类重要的进化算法，可以解决日益增长的智能交通系统的优化问题。但是，为了满足智能交通系统的时间约束问题的时间标准，如路由和控制自动驾驶车辆，需要高度并行化的GA。该方法通过设计三个并行核来实现遗传算法的并行化，每个核运行一些相互依赖的有效遗传算子。它可以直接适应在众核和多核处理器上运行。为了最好地利用这些处理器在并行执行GA的宝贵资源，运行任何三重内核的线程通过低成本的切换机制进行同步。该方法进行了实验，并行遗传算法为基础的解决方案的TSP多核和众核系统。结果证实了所提出的方法的效率，并行遗传算法的众核以及多核系统。
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.