同时取送货车辆路径问题的改进人工鱼群算法.pdf

《同时取送货车辆路径问题的改进人工鱼群算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第34卷第3期杭州电子科技大学学报V01．34．No．32014年5月JournalofHangzhouDianziUniversityMav．2014doi：10．3969／j．issn．1001—9146．2014．03—008同时取送货车辆路径问题的改进人工鱼群算法柳毅，余福茂，俞武扬(杭州电子科技大学管理科学与信息工程研究所，浙江杭州310018)摘要：该文在建立同时送取货车辆路径问题数学模型基础上，针对车辆负载波动性的特点，构造相应的人工鱼群算法的四元个体模型；利用动态设置视野范围、邻域搜索方法改进人工鱼群算法的觅食和追尾操作行为，仿真算例证明改进人工鱼群算法能

2、快速收敛得到较优解，具有较强工程应用价值。关键词：可同时取送货车辆路径问题；人工鱼群算法；邻域搜索中图分类号：TP301．6文献标识码：A文章编号：1001—9146(2014)03—0034—040引言同时取送货车辆路径问题(VehicleRoutingProblemwithSimultaneousDeliveryandPickup，VRPSDP)是逆向物流管理领域里重要的优化问题。文献[1]从逆向物流的角度分析建立VRPSDP问题的数学模型，并提出4种不同标准的插入式启发算法；文献[2]在建立VRPSDP问题数学模型的基础上，提出两种局域搜索启发式算法求解具有车辆行程

3、约束的VRPSDP问题；文献[3]提出一种自适应混合遗传算法求解以集成方式处理取货和送货操作的可同时取送货车辆路径问题。启发式算法一般能够在较短的时间内求出VRPSDP问题的近似解，但随着问题规模增大，其解空间的搜索能力有限。文献[4]提出一种通过模拟鱼类觅食、聚集和追尾行为获得全局最优值的人工鱼群优化算法(ArtificialFishSwarmAlgorithm，AFSA)。为此，本文根据物流配送车辆实际情况，以总行驶距离最短为优化目标建立该问题的整数规划模型，结合人工鱼的动态搜索和寻食策略，提出一种求解VRPSDP问题的改进人工鱼群算法。1VRPSDP问题的建模描述V

4、RPSDP问题可描述为：有n个客户节点(1，2，⋯，n)，第i个客户节点的取货需求量为Pi，送货需求量为qi。配送中心安排载重量为Q的k辆车为客户送货并收集客户物品，每个客户位置及取送货需求量已知，且客户只接受一次服务，在车辆安排满足客户需求前提下，求车辆总行程长度最短。MinZ=∑Jy∑diJ‘J—(1)i=0J=0k：1nitls．t∑∑Xijk=11≤j≤n(2)1=Uk=lYijk≤xijkQk0≤i≤n，1≤j≤n+1，1≤k≤m(3)∑ydijxIjk≤Lk：1，2，⋯，m(4)收稿Et期：2013—06—26基金项目：教育部人文社会科学青年基金资助项目(12

5、YJC630130)，浙江省自然科学基金资助项目(LY12G01003)作者简介：柳毅(1978一)，男，辽宁沈阳人，副教授，物流系统优化．第3期柳毅等：同时取送货车辆路径问题的改进人工鱼群算法35∑Y。ik=∑qj∑x．jk1≤k≤m(5)∑yjk=∑Yijk+(pi—qj)∑xk1≤j≤n+1，1≤k≤m(6)xiIjjk：I10其翌它k从i访问j0u≤i≤n，1≤j≤n+1，1≤k≤m(7)，y．ik／>00≤i≤n，1≤j≤n+1，1≤k≤in(8)式(1)表示车辆总运行距离最短，式(2)表示每个客户节点都要被访问且仅服务一次；式(3)表明当车辆k经过弧(i，j)

6、的载重量Yijk不能超过车辆容量Q，如果车辆k不经过弧(i，j)则其载重y=0；式(4)表示最大行驶距离约束；式(5)表示车辆完成各顾客节点服务任务后回到配送中心时其载货量为本次配送路线中各客户取货需求量之和；式(6)表示车辆在任意点的载货量满足在该点取货需求量与送货需求量代数求和的恒等关系；式(7)表示决策变量的性质；式(8)表示车辆k行驶在弧(i，j)上的载重量。2改进人工鱼群算法设计2．1构造人工鱼个体模型人工鱼个体模型为一个四元组Xi=，其中参数G为物流配送中需要服务的客户节点组成的二维坐标点集合，目标函数值Y=

7、f(X；)表示人工鱼当前食物浓度值，由送货需i求量qi、取货需求量P配与车辆剩余空间(Q—P一∑q)构成；VisualScope表示人工鱼的感知范围，s=1Direct表示人工鱼群运动方向，受此刻车辆可载货物容量支配。2．2动态设置人工鱼群搜索视野改进人工鱼群算法搜索视野r的值非常重要，r值设置过大不易获得人工鱼群中的最优个体，太小算法容易早熟一获得局部极值点。为此，根据文献[5]增加人工鱼感知范围动态设置鱼群搜索视野，dij=distance(Xi，Xj)表示人工鱼x和xi之间的距离，人工鱼xi的搜索视野为VisualSco