带时间窗的车辆路径问题的离散蝙蝠算法

摘要

This paper presents a discrete bat algorithm to solve the vehicle routing problem with time window (VRPTW). The proposed algorithm defines position, velocity, updated operation of the position, updated operation of the velocity and updated operation of the frequency, and uses a method which combines the penal function with vectorial comparison to deal with constrained conditions. The proposed algorithm adopts random inserted strategy, inserted research strategy for the vehicle with minimum customers, ordinary inserted research strategy, exchanged research strategy and 2-Opt strategy with time window to expand the search space and enhance the convergent rate. Experimental results show that, the proposed algorithm has a stronger optimization capability, higher robustness and less time consumption, key parameter values and strategies used in this paper can improve performances of the proposed algorithm, and according to the hypotheses testing, there exsits a significant difference between the proposed algorithm and comparative algorithms.%本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题(vehicle routing problem with time window).该算法提出了蝙蝠位置的定义、速度的定义、位置更新操作、速度更新操作、频率更新操作,并采用惩罚机制与向量比较机制相结合的方法处理相关约束条件.该算法引人了随机插人策略、最少客户车辆插入搜索、普通插人搜索、交换搜索、带时间窗的2-Opt搜索等策略来扩大搜索空间、加强算法的收敛效率.实验结果表明:所提出算法具有较强的寻优能力、较高的鲁棒性、较少的时间耗费;本文所采用的关键参数值和策略能提高所提出算法的性能;通过假设检验证明了所提出算法与对比算法之间的算法性能均有显著性差异.