引用本文:戚远航,蔡延光,蔡颢,黄何列,OLE Hejlesen.泰森多边形的离散蝙蝠算法求解多车场车辆路径问题[J].控制理论与应用,2018,35(8):1142~1150.[点击复制]
QI Yuan-hang,CAI Yan-guang,CAI Hao,HUANG He-lie,OLE Hejlesen.Voronoi diagram-based discrete bat algorithmfor multi-depot vehicle routing problem[J].Control Theory and Technology,2018,35(8):1142~1150.[点击复制]
泰森多边形的离散蝙蝠算法求解多车场车辆路径问题
Voronoi diagram-based discrete bat algorithmfor multi-depot vehicle routing problem
摘要点击 2374  全文点击 1276  投稿时间：2017-06-21  修订日期：2018-02-10
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2018.70421
  2018,35(8):1142-1150
中文关键词  泰森多边形  蝙蝠算法  多车场车辆路径问题  车辆路径
英文关键词  voronoi diagram  bat algorithm  multi-depot vehicle routing problem  vehicle routing
基金项目  国家自然科学基金(61074147)；广东省自然科学基金(S2011010005059)；广东省教育部产学研结合项目(2012B091000171,2011B090400460)；广东省科技计划项目(2012B050600028,2014B010118004,2016A050502060),广州市花都区科技计划项目(HD14ZD001),广州市科技计划项目(201604016055)。
作者单位E-mail
戚远航 广东工业大学自动化学院 1243021611@qq.com 
蔡延光* 广东工业大学自动化学院  
蔡颢 广东工业大学自动化学院  
黄何列 广东工业大学自动化学院  
OLE Hejlesen 奥尔堡大学健康科学与工程系,丹麦奥尔堡  
中文摘要
      本文提出了一种基于泰森多边形的离散蝙蝠算法求解多车场车辆路径问题(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.