A Parallel Genetic Algorithm Framework for Transportation Planning and Logistics Management
A Parallel Genetic Algorithm Framework for Transportation Planning and Logistics Management
复制标题
DOI：
10.1109/access.2020.2997812
复制
发表时间：
2020-01-01
期刊：
影响因子：
3.9
通讯作者：
Regan, Amelia C.
中科院分区：
文献类型：
--
作者：
Arkhipov, Dmitri I.;Wu, Di;Regan, Amelia C.
中小型运输和物流公司通常受到有限的计算和IT专业资源的限制，无法实现高效的并行元启发式算法来规划或管理解决方案。本文用一个简单的非平凡并行实现扩展了遗传算法（GA）的标准元描述。我们的并行遗传算法框架主要关注的是开发一种简单的方法，工程师可以修改现有的遗传算法实现，以解决实际的运输和物流问题，从而利用普遍可用的硬件资源，而无需完全重做复杂、有用和可用的代码。在其并行基础上提出的框架是对原始并行化概念的修改，但如果按照所描述的实现，它可能会逐渐扩展以更好地适应任何潜在问题的质量（通过对合并和通信功能的适应）。本文给出了一个经典的运输相关组合优化问题的框架和计算结果& x2013；旅行商问题用标准序列遗传算法实现。我们的实证分析表明，这个简单的扩展可以带来相当大的解决方案改进。我们还测试了我们的假设，即框架很容易由最初不熟悉遗传算法的工程师实现，以实现另一个最小多处理器调度问题的框架。这些案例研究验证了我们的框架比原始并行化更好，因为它在公平条件下提供了更好的经验结果。它还优于细粒度并行化，因为它更容易更快地实现。
Small to medium sized transportation and logistics companies are usually constrained by limited computing and IT professional resources on implementing an efficient parallel metaheuristic algorithm for planning or management solutions. In this paper we extend the standard meta-description for genetic algorithms (GA) with a simple non-trivial parallel implementation. Our parallel GA framework is chiefly concerned with the development of a straightforward way for engineers to modify existing genetic algorithm implementations for real transportation and logistics problems to make use of commonly available hardware resources without completely reworking complex, useful and usable codes. The framework presented at its parallel base is a modification of the primitive parallelization concept, but if implemented as described it may be gradually extended to fit the qualities of any underlying problem better (via the adaptation of the merging and communications functions).We present our framework and computational results for a classical transportation related combinatorial optimization problem & x2013; the traveling salesman problem with a standard sequential genetic algorithm implementation. Our empirical analysis shows that this simple extension can lead to considerable solution improvements. We also tested our assumptions that the framework is easily implemented by an engineer not initially familiar with genetic algorithms to implement the framework for another minimum multiprocessor scheduling problem. These case studies verify that our framework is better than primitive parallelization because it gives empirically better results under equitable conditions. It also outperforms fine grained parallelization as it is easier and faster to implement.