Abstract:

According to the problems of the slow convergence and poor calculation accuracy for the vehicle path with time window based on intelligent water drop algorithm, firstly, depending on applying requirement of the vehicle path planning, using integer linear programming methods, a multiple-objectivesand multiple time windows vehicle path model is constructed, taking the minimum transportation cost, the shortest transportation distance and the minimum vehicle number as targets, the vehicle starting point, service point and loading capacity as well as other constraints are comprehensively considered. Secondly, in order to quickly solve this model, a complementary and improved optimization algorithm is proposed which is related to the pigeon inspired optimization and intelligent water drop algorithm, water droplets is discrete binary transformation. The map compass operator and landmark operator are used, flow speed and direction of water droplet are improved, and adaptive variable neighborhood perturbation strategy is employed to interfer the soil amount, improve the development and exploration capabilities of the water droplet algorithm. Finally, the multiple-objectives function and constraint conditions are processed using the ideal point method and the penalty function with multiple-objectives hybrid method, and taking two classic vehicle path with time windows as example, the calculation results of genetic algorithm, intelligent water drop algorithm, and pigeon-water drop algorithm are compared. The results show that the pigeon inspired optimization, water drop algorithm, and the basic water drop algorithm are compared, the transportation path is shorten by about 20 km, and the transportation cost is saved by about 403 yuan under the same algorithm parameters and economic indicators. At same time the solution time and iteration times of the algorithm are also significantly better than the other two artificial intelligence algorithms

Key words: pigeon inspired optimization algorithm, intelligent water drop algorithm, multiple time windows, vehicle routing plan, multiple-objectives

摘要：

针对智能水滴算法求解带时间窗车辆路径规划收敛速度慢、计算精度差的问题，根据带时间窗车辆路径问题的应用要求，利用整数线性规划方法，以配送车辆的最小运输总成本、最短运输距离和最少安排数量为目标，综合考虑了车辆出发点、服务点、装载量、行驶距离、服务时间窗等诸多约束条件，构建了多目标多时间窗车辆路径模型；为了精准快速求解多目标多时间窗车辆路径模型，提出一种鸽群-智能水滴互补改进优化算法，将河道水滴离散二进制变换后，采用地图罗盘算子和地标算子分别改进水滴的流动速度和方向，并利用自适应变邻域扰动策略干扰水滴携带的泥土量，提高水滴算法的开发和探索能力；利用理想点法和罚函数与多目标优化混合方法分别处理多目标函数与约束条件，并以两种经典的带时间窗车辆路径问题为实例，通过与遗传算法、智能水滴算法和鸽群-水滴算法的计算结果进行比较，结果表明：在相同的算法参数和经济指标下，鸽群-水滴算法相比于智能水滴算法求解模型中的运输路径缩短20 km左右、运输成本节约403元左右，且该算法的求解时间和迭代次数也明显优于其他两种人工智能算法。

关键词: 鸽群算法, 智能水滴算法, 多时间窗, 车辆路径规划, 多目标