改进智能水滴算法在车辆调度问题中的应用

Application of Improved Intelligent Water Drop Algorithm in Vehicle Scheduling Problem

目的克服标准智能水滴(IWD)算法泥土含量更新对象较为单一的缺点,提高其求解车辆调度问题的全局搜索能力。方法在IWD算法基础上,设计一种改进智能水滴(IIWD)算法用于车辆调度问题的求解。引入次优解集合的概念,每次迭代结束后同时更新最优解集合和次优解集合中的泥土含量;设计浑沌扰动机制,对陷入局部最优解的智能水滴进行浑沌扰动;根据车辆调度问题的特点,提出求解车辆调度问题的IIWD算法。结果得到含有8条子路径,总行驶距离为842.60 km的最优调度方案,相对于标准IWD算法(941.35 km)和遗传算法(860.76 km)的求解结果分别缩短了98.75和18.16km。结论与遗传算法和标准IWD算法相比较,IIWD算法在求解车辆调度问题时收敛速度更快,全局优化能力更高。

This work aimed to overcome the shortcoming of standard intelligent water drop（IWD） algorithm in soil content updating and improve its global search ability to solve the vehicle scheduling problem（VSP）. Based on IWD algorithm,an improved intelligent water drop（IIWD） algorithm was designed to solve VSP. Firstly,a concept of sub optimal solution set was introduced,and the soil contents in the optimal solution set and sub optimal solution set were updated after every iteration. Secondly,a chaos disturbance mechanism was designed,and the individuals fallen into the local optimal solution were disturbed by it. At last,the IIWD algorithm was used to solve the vehicle scheduling problem.The optimal scheduling scheme with 8 distribution paths containing a total traveling length of 842.60 km was obtained,which saved 98.75 and 18.16 km comparing with the genetic algorithm（GA） and IWD algorithm. In conclusion,compared with GA and IWD algorithm,the IIWD algorithm converged faster and had stronger global optimization ability when used to solve the vehicle scheduling problem.