一种基于车辆路径规划的改进人工鱼群优化方法

摘要

本发明涉及一种基于车辆路径规划的改进人工鱼群优化方法。现有的算法计算量大、耗时长。本发明将人工鱼群算法仿生学原理和决策者主观偏好进行有效结合，对人工鱼群算法进行改进，引入鱼群感知范围的概念一排斥区、中性区和吸引区重构了人工鱼群算法的寻优公式；通过判断车辆路径上节点的需求量和当前车辆剩余运输能力，以及决策者主观偏好的角度对人工鱼的移动步长、视野范围和邻域值进行动态调整，以提高人工鱼群算法的全局搜索能力和搜索速度。最终应用改进的人工鱼群算法优化车辆的取、送货行为，完成可回程取货车辆路径调度问题。本发明在计算精度和稳定方面优于遗传算法、模拟退火算法等传统优化算法，具有良好的寻优能力。

主权项

1.一种基于车辆路径规划的改进人工鱼群优化方法，其特征在于该方法包括如下步骤：步骤1.随机生成初始规模的人工鱼群，将t时期车辆的状态用人工鱼个体的状态向量X＝(X_i(t)，i＝1，2，…，F_number)表示，其中，i为车辆将要驶离的节点，X_i(t)为当前车辆的可支配货容量；目标函数Y决定人工鱼当前所在位置的食物浓度，Y_i＝F(X_i(t))；人工鱼个体之间的距离表示为d_i，i+1＝||X_i-X_i+1||；步骤2.自适应的设定邻域搜索范围：t时期人工鱼个体X_k的邻域定义为：VisualScope＝{X_k|d_k，k+1＜R_k}，R_k表示邻域半径；设人工鱼的邻域距离为R₁，在R₁距离之内的其他鱼对此鱼有排斥作用；邻域距离在R₁和R₂之间为中性区域，在R₁和R₂之间范围内的其他鱼对此鱼的作用包括排斥和吸引；邻域距离R₂和R₃之间的区域为吸引区，在R₂和R₃之间区域的其他鱼对此鱼有吸引作用；距离R₃之外不属于鱼的感知范围，其中R₁＜R₂＜R₃；步骤3.自适应的觅食行为：设定α，β分别为速度向量与两个坐标轴的方向角，根据式(1)分别确定参数α_k(t)，β_k(t)的值来决定人工鱼个体X_k下一步的移动方向；引入交换序操作符重构人工鱼群算法的觅食公式(2)，扩大人工鱼群算法的搜索范围；${\alpha }_k\left(t\right)=\frac{1}{n_k(t-1)}\underset{j\in N_k(t-1)}{\Sigma }{\alpha }_j(t-1)$${\beta }_k\left(t\right)=\frac{1}{n_k(t-1)}\underset{j\in N_k(t-1)}{\Sigma }{\beta }_j(t-1)---\left(1\right)$式中：N_k(t-1)为t-1时刻人工鱼X_k邻域VisualScope中存在的客户服务点集合，n_k(t-1)是该集合内客户服务点总数；α_j(t-1)和β_j(t-1)分别表示当前人工鱼与邻域中第j个服务客户点的方向角度；通过求平均数α_k(t)，β_k(t)来决定人工鱼X_k下一步将要移动的方向；$X_{i(k+1)}={\alpha }_k\left(t\right)X_{\mathrm{ik}}\oplus {\beta }_k\left(t\right)\mathrm{rand}\left(\mathrm{}\right)\mathrm{Step}(X_{\mathrm{jk}}-X_{\mathrm{ik}})/\left|\right|X_j-X_i\left|\right|,Y_j>Y_i---\left(2\right)$式中：X_i(k+1)为人工鱼下一步的移动位置；X_i为人工鱼当前位置，即已服务的客户位置；X_j为在其感知范围内随机选择的另一个位置；X_jk和X_ik分别表示第k辆车访问节点i，j的位置；rand()表示[0，1]间的随机数，Step为进化代数；步骤4.聚群行为：将车辆剩余装载能力引入到人工鱼群算法的启发信息中，用人工鱼当前状态为X_i表示车辆访问过节点i后的装载量，X_ck表示整个人工鱼群的中心位置，X_i(k+1)为人工鱼下一步的移动位置，X_ik为人工鱼当前位置；Y_i＝F(X_i(t))表示为人工鱼当前所在位置的食物浓度，即车辆要访问的下一个节点以及后续节点集的装载量，如果Yc/δ＞Y_i表明伙伴中心位置有较多食物且不太拥挤，Yc表示人工鱼群中心位置的食物浓度，δ表示拥挤度因子δ＞1，则按(3)式向服务中心节点位置移动，如果Yc/δ≤Y_i则执行觅食行为；$X_{i(k+1)}=X_{\mathrm{ik}}+\mathrm{rand}\left(\mathrm{}\right)\mathrm{Step}\frac{X_{\mathrm{ck}}-X_{\mathrm{ik}}}{\left|\right|X_{\mathrm{ck}}-X_{\mathrm{ik}}\left|\right|}---\left(3\right)$步骤5.追尾行为：设人工鱼群当前邻域内伙伴X_max的位置最优，X_i(k+1)为人工鱼下一步的移动位置，X_ik为人工鱼当前位置，最优值如果Y_max＞Y_i，表明伙伴X_max具有较高的食物浓度并且不太拥挤，则按(4)式向伙伴X_max前进一步，如果Y_max≤Y_i则执行觅食行为；$X_{i(k+1)}=X_{\mathrm{ik}}+\mathrm{rand}\left(\mathrm{}\right)\mathrm{Step}\frac{X_{\max }-X_{\mathrm{ik}}}{\left|\right|X_{\max }-X_{\mathrm{ik}}\left|\right|}---\left(4\right)$步骤6.车辆服务k个节点后其总运载量为车辆剩余运载能力q_k＝C-D′_k，即q_k是一个三角模糊数，q_2k和q_3k表示车辆分别服务一个随机节点后的剩余运载能力，C为每辆车的运输能力，d_2，k+1和d_1，k+1表示下一节点k+1的顾客模糊需求量，下一节点需求量小于车辆剩余容量的可能性表示为P_k+1，$P_{k+1}=\mathrm{pos}\{D_{k+1}\le q_k\}=\left\{\begin{array}{c}1,d_{2,k+1}\le q_{2k}\\ \frac{q_{3k}-d_{1,k+1}}{(q_{3k}-q_{2k})+(d_{2,k+1}-d_{1,k+1})},d_{2,k+1}\ge q_{2k},d_{1,k+1}\le q_{3k}\\ 0,d_{1,k+1}>q_{3k}\end{array}\right.---\left(5\right)$通过对比自身剩余空间q_k和待服务节点k+1的需求D_k+1，得出k点的置信水平，来确定该车辆是否有能力继续服务；P_k+1值越大该车能够完成下一任务的可能性越大；当P_k+1≥P^*时，该车继续完成下一运输任务，若P_k+1＜P^*，该车返回车场，新派车完成剩余运输任务，P^*(P^*∈[0，1])表示决策者主观偏好值；根据决策者主观偏好值P^*动态调整T时刻人工鱼的步长和感知范围公式(6)；$\left\{\begin{array}{c}\mathrm{Step}=\mathrm{Step}\times P^{*}+{\mathrm{Step}}_{\min }\\ \mathrm{Visual}=\mathrm{Visual}\times P^{*}+{\mathrm{Visual}}_{\min }\end{array}\right.---\left(6\right)$步骤7.局部最优逃逸策略；如果车辆的容量达到其限制水平，则回到服务中心恢复其正常容量后进行再服务；通过采用邻域搜索策略，以当前新的客户点(x_add，y_add)为圆心，以其到车场的距离为半径在圆形范围内寻找能对新客户点进行服务的在途车辆，即满足：$\sqrt{{(x_k-x_{\mathrm{add}})}^2+{(y_k-y_{\mathrm{add}})}^2}\le \sqrt{{(x_0-x_{\mathrm{add}})}^2+{(y_0-y_{\mathrm{add}})}^2}---\left(7\right)$式中，(x_k，y_k)为干扰发生时刻车辆k所在的位置，(x₀，y₀)为车场的位置，从而得到能服务新客户点的在途车辆集合；当所有在途车辆均无法为新客户点服务时，则需从车场中增派车辆为其服务。