带回程取货车辆路径问题的人工鱼群算法研究

柳 毅

(杭州电子科技大学管理科学与信息工程研究所,浙江杭州310018)

0 引 言

带回程取货车辆路径问题(Vehicle Routing Problem with Backhaul,VRPB)是VRP问题的衍生,能够将送货取货过程结合起来,实现在送货的同时取货[1]。文献2,3分别应用遗传算法和启发式算法解决这类问题,但遗传算法的计算量大、收敛速度较慢;启发式算法缺乏鲁棒性。人工鱼群算法是模拟鱼群的觅食、聚群和追尾行为的优化算法,从构造单条鱼的底层行为做起,通过鱼群各个体的局部寻优,达到全局最优值在群体中突现的目的,具有克服局部极值的能力[4]。因此,本文提出用人工鱼算法来求解带回程取货车辆路径问题。

1 带回程取货车辆路径问题的数学模型

式1是求运输成本最小的目标函数;式2表明保证每个节点只被一辆车服务一次;式3表明客户节点只可以被一辆车访问,而初始节点被所有车辆访问;式4-7表明车辆任何时间所载货物不能超过其最大能力;式8为各个决策变量取值约束。V={i}为所有客户节点i的需求集合;M={k}为所有车辆的集合;Qk是车辆k的能力;C={Cij}是各节点间的距离矩阵;Pi是客户i的取货需求量;di是客户i的送货需求量;Xijk决定车辆从节点i到达节点j后,是否由车辆k服务;Yijk是从节点i到达节点j时车辆k上的送货辆;Zijk表示从节点i到达节点j时车辆k上的取货辆;Uik表示节点i是否由车辆k服务。

2 求解VRPB问题的人工鱼群算法

对于VRPB问题需要将人工鱼的初始位置放在起点和终点节点上,因为车辆只有从起点出发到达终点,或者从终点出发到达起点才是一个有效解。

(2)觅食行为。人工鱼当前状态为Xi,人工鱼下一步状态向量Xinext,Random()表示[0,Step]间的随机数,当Xj食物浓度(FCj)大于Xi食物浓度(FCi)时,则向该方向前进一步;否则重新随机选择状态Xj进行判断。

(3)人工鱼个体在t时期能量函数Vs(t)：

式中,Vs(t)为时期t人工鱼个体Xs(t)的能量,λ为大于0的常数。初始时Vs(0)=λ Ys(Xs(0)),人工鱼个体Xs(t)从低浓度食物区游到高浓度食物区进食,即Ys(Xs(t+1))>Ys(Xs(t)),则该人工鱼能量增加;人工鱼个体Xs(t)从高浓度食物区游到低浓度食物区,即Ys(Xs(t+1))≤Ys(Xs(t)),则该人工鱼消耗能量。

(4)聚群行为。人工鱼当前状态为Xi,搜索当前邻域内的伙伴数目nf及计算中心位置Xck：

式中,Xck表示中心位置状态向量Xc的第k个元素;Xjk表示伙伴Xj的第k个元素。计算该中心位置的食物浓度值FCc：

式12表明伙伴中心位置有较多的食物并且不太拥挤,朝伙伴的中心位置方向前进一步;否则人工鱼执行觅食行为。

(5)追尾行为。设人工鱼当前状态为Xi,探索当前邻域内(即(di,j≤Visual)的伙伴中Y为最大的伙伴Xmax,如果FCmax>FCi,表明伙伴Xmax具有较高的食物浓度并且不太拥挤,则朝伙伴Xmax的方向前进;否则执行觅食行为。

式中,Xmaxk表示状态向量Xmax的第k个元素。若人工鱼当前可见域内没有其它伙伴,也执行觅食行为。

(6)行为评价。根据所要解决问题的性质,对人工鱼当前所处的环境进行评价,设立公告板记录最优个体状态及该个体位置的食物浓度值,每条人工鱼行动一次后就将自身当前状态与公告板进行比较,如果优于公告板则用自身状态取代公告板状态,从而选择一种合适的行为。

(7)新增服务的邻域搜索。当动态产生新的客户需要服务时,采用基于距离原则的邻域搜索策略。以当前新的客户点(xadd,yadd)为圆心,其到车场的距离为半径的圆形范围内寻找在途车辆,即满足：

式中,(yk,yk)为干扰发生时刻车辆k所在位置,(x0,y0)为车场的位置,从而得到能服务新客户点的在途车辆集合。当所有在途车辆均无法为新客户点服务时,则需从车场增派车辆为其服务。

(8)判断中止条件。判断是否达到最大迭代次数MAXG,若是则输出公告板的计算结果;否则,G=G+1转步骤4继续进行觅食行为。

3 仿真算例分析

为验证人工鱼群算法求解VRPB问题的有效性,采用文献5中的实验数据,将Solomon精确车辆路径问题的实例R101、R102改造成为25、50个节点VRPB问题(将3的倍数节点改造为取货需求节点,取货量为原送货量),计算时人工鱼的个数为50,移动步长为10,视野范围为50,启发式算法和人工鱼群算法的仿真优化结果如表1所示。

表1 启发式算法与人工鱼群算法仿真结果比较

实验结果表明在车辆使用数基本相同的前提下,人工鱼群算法所得车辆行驶距离明显小于启发式算法所得行驶距离。在最小化车辆使用数与车辆行驶距离的目标函数情况下,人工鱼群算法的收敛情况明显优于启发式算法。

4 结束语

人工鱼群算法具有简单易实现,对初值与参数选择不敏感等优点,本文采用人工鱼群算法求解带回程取货车辆路径问题,仿真结果表明该算法具有较好的全局优化能力,可以取得令人较为满意的效果。

[1] Guo F,Long Y.Genetic algorithms for improved vehicle routing problems with backhauls[C].Beijing：Proceedings of the 12th International Conference on Industrial Engineering and Engineering Management,2006：606-610.

[2] Baker BM,Ayechew M A.A genetic algorithm for the vehicle routing problem[J].Computers&Operations Research,2003,30(5)：787-801.

[3] Fisher M L.Optimal solutionof vehicle routing problems using minimum K-trees[J].Operations Research,1994,42(4)：626-643.

[4] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践,2002,22(11)：32-38.

[5] Toth P,Vigo D.A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls[J].European Journal of Operational Research,1999,11(3)：528-544.