泰森多边形的离散蝙蝠算法求解多车场车辆路径问题

Voronoi diagram-based discrete bat algorithmfor multi-depot vehicle routing problem

中文关键词  泰森多边形  蝙蝠算法  多车场车辆路径问题  车辆路径

英文关键词  voronoi diagram  bat algorithm  multi-depot vehicle routing problem  vehicle routing

中文摘要

      本文提出了一种基于泰森多边形的离散蝙蝠算法求解多车场车辆路径问题(Multi-Depot Vehicle Routing Problem, MDVRP)。所提出算法以离散蝙蝠算法为核心，融入了一种基于多车场多车辆问题的编解码策略。所提出算法还使用基于泰森多边形的初始化策略加快算法的前期收敛速度，采用基于向量比较机制的适应度函数来控制算法收敛的方向，引入基于近邻策略和优先配送策略的局部搜索策略来提高算法的寻优能力。实验结果表明：在合理的时间耗费内，所提出的算法能有效地求解MDVRP，尤其是带配送距离约束的MDVRP；相对于对比算法，所提出的算法表现出较强的寻优能力和稳定性。

英文摘要

      This paper presents a voronoi diagram-based discrete bat algorithm to solve the multi-depot vehicle routing problem (MDVRP) which is a well-known NP-hard problem. The proposed algorithm takes the discrete bat algorithm as the core and integrates encoding and decoding strategies based on the multi-depot and multi-vehicle problem. The proposed algorithm also uses an initialized strategy based on the voronoi diagram to accelerate the previous convergent speed, and adopts a fitness function based on the vectorial comparison mechanism to control the convergent direction, as well as utilizing a local search algorithm based on the nearest neighbor strategy and the prior distribution strategy to enhance the optimization capability. Experimental results show that the proposed algorithm can effectively solve the MDVRP within a reasonable time consumption, especially the MDVRP with a delivery distance constraint; compared with contrast algorithms, the proposed algorithm has the stronger optimization ability and stability.