浅析物流配送最短路径选择方法

浅析物流配送最短路径选择方法--蚁群算法翁凌云浙江工业大学计算机学院、网络工程，浙江杭州310000摘要：据中研普华《2013-2017年物流行业全景调研与投资策略研究咨询报告》显示，2012年我国物流业实现平稳适度增长，但物流要素成本也在全面上涨，物流企业生存空间进一步压缩⑴。运输服务作为物流组成中的重要环节，是降低运输成本、提高运输质量和效率成为加快物流发展的有效途径，亦是运输服务优化中的核心问题。它通过对货物的运输线路进行优化，在满足客户需求的前提下，尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题(VehicleRoutingProblem，简称VRP)得到了广泛的关注和研究，并取得了丰富的研究成果。本文针对这类问题的构成、分类以及求解算法中的蚁群算法在这方面的运用等进行了归纳和概括。关键词：物流；最短路径；算法；引言美国物流管理学会(CouncilofLogisticsManagement,CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。车辆路径问题的定义车辆路线问题(VRP)最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物,组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的［2］。车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。设有一场站(depot),共有M辆货车，车辆容量为Q,有N位顾客(customer),每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站,要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点,总的运输成本实现最小。车辆路线问题可以描述如下(如图1)：物流配送路径问题，实际上是旅行商(TravelingSales一manProblem，TSP)的问题，对TSP的问题描述如下：一个货郎要走访N个城市，每个城市必须经过一次且只能经过一次，最后回到出发的城市，就算是完成了一次旅行，找到一条最短的路径。其相应数学描述如下：设有一城市集合C二企£2匕•.…c｝，每对城市Cj，CiuC间的距离为d(c，c.)eZ+。1 2 3 n J ij求一条经过C中每个城市正好一次的最短路径。车辆路径问题的重要研究方法——蚁群算法车辆路径问题(VRP)的研究方法主要有精确优化算法、启发式优化算法和仿生优化算法三大类别［3］仿生优化算法是近几年来在求解组合优化问题方面发展较快的一个方向。其中蚁群算法是一种对自然界中生物觅食行为进行计算机模拟的算法，该算法具有并行性、突现性、进化性和稳健性的特点，现已成为解决配送路径问题的重要方法。蚁群算法(antcolonyoptimization,ACO),又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质，具有一种新的模拟进化优化方法的有效性和应用价值。3.1蚁群算法的基本原理蚁群算法的基本原理可以通过引用M.Dofigo所举的例子具体来说明。图2是蚁群系统原理示意图设A是巢穴，F是食物源，CD为一障碍物。由于障碍物存在，蚂蚁只能经C或D由A到达F,或由F到达A,各点之间的距离如图2所示。设每个时间单位有M只蚂蚁由A到达B,有M只蚂蚁由F到达E点，蚂蚁过后留下的激素物质量（以下称之为信息素）为L，（为方便说明）设该信息素在路径上的停留时间为to在初始时刻，由于路径BC、BD、CE、DE上均无信息素存在，位于B和E的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BC、BD、EC、ED。经过一个时间单位后，在路径BCE上的信息素是路径BDE上信息素的二倍。在t=0时刻，将有mO=M/2只蚂蚁由B和E到达C,有m0只蚂蚁由B和E到达D。在t=1时刻，将有ml只蚂蚁由B和E到达C,有m2=M-ml（m2vml）只蚂蚁由B和E到达D。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BCE，并最终完全选择路径BCE，从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息素交换是一个完整的正反馈过程[4]•F♦At二0时刻

DD•A21时刻图2蚁群算法原理示意图3.2数学模型构架Tij初始时计算出位置i和j之间路径长度，形成无向图G(N,E),其中N是客户数，ETij户之间的连通边的集合，Bi(t)表示t时刻位置i的车辆个数，车辆总数m仝B(t),ii=1表示t时刻在边e(i,j)上残留的信息量，初始时刻各条路径上信息量相等，t(0)=C，Cij为常数，车辆k(k=1，2…，m)在运输过程中，根据每条路径上的信息量决定转移的方向,Pkt时刻车辆k由i转移到j的概率［5］为巧，PkijTaPkijTa•耳卩(t)ij ij2Ta•耳卩(t),

ijijshallowed0,otherseallowedk(i)其中，tabu(k=1,2,…,m)表示车辆k已经过的位置，随运动过程动态调整，kallowed={0,1,…,n-1}-tabu表示车辆k下一步允许选择的位置，耳为由i转移到j的k k ij期望程度，Q为信息量T(t)对选择该路径的启发因子，反映车辆在运输过程中积累的信息ij量，0为期望度耳(t)的影响因子。ij信息素更新⑹mt(t+n)=p・T(t)+(1-p)2Atk(t)ij ij ij (2)k=1其中P(0<P<1)为常数，1-P表示信息消逝程度，Atk为车辆k留在路径上的信息,(/Atk=Atk=v(/Q 车辆k经过路径e(i,j)Lk0,(3)others其中Q为常数，L表示车辆k在本次循环中所走过的路径长，L=Yd,n为车辆k

k k iji=1,j=1在本次循环中所漫游的客户数(n<N),d为i到j的距离。(/a a通过不同规模的多次实验发现，当0的值过大或过小，搜索的结果都不理想：0过大时,算法迅速收敛；当0=0,只有信息素的放大系起作用，没有任何与道路有关的期望信息,a若此时a>1，算法将会很快陷入局部最优解；过小时，将会陷入纯粹的、无休止的随机搜索中，很难找到最优解；a=0时，则靠近i的位置将很可能被选出来［7］为此进行我们对参数的改进：设初始值a参数的改进：设初始值a卩；如果两代最优解与上次变化不大,0则令a=0a0=£p,(0<0<1,£>1),5,y均为常数；大量的实验数据表明，改t+1 t+1t+1 t进后的参数即保证了算法很强的随机性，又保证了算法快速收敛。3.3算法步骤步骤一：设置初始信息，a0=1，00=2，每条边上的信息素量、=0-11，每条边上的信息素量Atj=0,配送中心车辆的载重量load=0,设置迭代次数NC=0,将allowedk的初始值设置为true，表示客户未被访问，均可被访问。步骤二：车辆的初始点放到tubuk中，表示此节点已被访问，不能再被访问。对于每个车辆k通过(1)式选择下一个访问j,如果该节点的需求量没有超过车辆的载重量，则选择该客户j,否则重新选择客点j。转移到客户点j后，将其放人tubu中，并将客户点的载重量加k入load中，即load=load+demand［j］；判断load是否超过车辆的最大载重量，如果未超过则继续选择下一个客户点，否则返回配送中心。步骤三：判断汕吓叫中是否还有未被访问的客户点，如果还有其它尚未访问的客户点则设置从配送中心出发，转到步骤二；若allowed中的客户点已全部访问完毕，则进行步k骤四。步骤四：从tubuk中计算车辆k的解集中所经过的路径长度length。步骤五：根据各辆车经过的路径利用局部信息素通过式(2)更新所经过的路径的信息素量。步骤六：求所有车辆所经过的路径长度得出最短路径。步骤七：从每次迭代的最短路径中出目前最优的路径，根据全局信息素更新机制更新目前最优路径的信息素。步骤八：参数值a，0改进；步骤九：当NC>NC时，输出可行解。max结束语通过分析可知蚁群算法是一种较好的解决VRP问题的仿生算法，该算法具有本质并行、正反馈、较强的稳定性等特点，但若参数选取不当容易出现早熟停滞现象，通过设置启发因子参数动态变化后，操作简单，减少了循环次数，收敛效果好，保证了在较短时间内较高收敛率地得到全局最优解。此外，还有一些其它的参数设定仍待进一步研究和考虑其他客户配送要求等因素对交通行车的影响，重新选择最优配送路径，将会使得该问题更加接近于现实生活，在现实社会中发挥最大作用。参考文献：2012年中国物流业发展现状及趋势分析报告中国行业研究网/news/20130217/170729936.htmlPAOLOTOTH，DANIELEVIGO.THEVEHICLEROUTINGPROBLEM[M].SocietyforIndustrialandAppliedMathematicsphiladephia.2002ZAKIMJ.SPADE：Anefficientalgorithmforminingfrequentsequences[J].MachineLearning，2001，42(1-2)：31-60.易荣贵，罗大庸•基于遗传算法的物流配送路径优化问题研究[J].计算机技术与发展，2008,18(6)：13-15，19.COLOMIA，DORIGOM，MANIEZZOV.DistributedOptimizationbyAntColonies[C].ParisProcofEuropeanConferenceofArtificialLife.199,11342一1354.DORIGOM，BONABEAUE，THERAULAZG.AntAlgorithmandStigmergy[J].FutureGenerationComputerSystems.2000,16(6)：851一871.M.DorigoandT.Stutzle,AntColonyOptimizat