现代物流中车辆路由问题的研究

《现代物流中车辆路由问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要对于‘物流’这个概念，最朴素的理解就是实物的流动。现代物流学是在50年代新发展起来的一门实践性很强的综合性交义学科，研究的主要目的是为了降低商品生产和流通的成本。本文的研究对象为现代物流体系中的车辆路由问题，研究了儿个路由问题的数学模型，并在此基础上进行了算法研究。现阶段，车辆路由问题的数学模型主要有TSP(TravelingSalesmanProblem)VRPTW(VehicleRoutingProblemwithtimewindows),PDP(PickupandDeliveryProblem)。本文

2、主要对TSP和VRPTWIu7题进行研究，使用的算法模型有ACO(AntColonyOptimization),PSO(ParticleSwarmOptimization).车辆路由问题的数学模型描述如下:TSP问题的描述:给定n个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最短路线。其图论描述为:给定图G=(;A)，其中V为顶点集，A为各顶点相互连接组成的弧集，己知各顶点间连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点一次且仅一次的最短回路·设dil为城市I与l之间的距离，即弧

3、(Ij)的长度。引入决策变量若旅行商访问城市i后访问城atij(1)否则(2)则TSP的目标函数为:minZ一、勤‘““VRPTW问题的描述设配送中心(或仓库)有m辆车V={k},k=1,2........m，其中m可为待定车辆数，车辆的承载能力均为9:为n个客户服务，客户集为C={I},1=0,1,.0...,n,1=。时为配送中心;客户I的需求量为d=d0=0;且客户I的时间窗口为[ai,bi];从客户I到客户i的费用为eil，行驶时间为ty}:设Sik为车辆k到达客户I的时间，则S.E[ai,b,l·如何确定

4、车辆数m和规划运输路线，使总费用最少。算法概述:摘要蚂蚁算法问题模型自然界中的蚂蚁在觅食过程中沿途散播一种化学物质，称为信息素(pheromone)，信息素中记录了食物源的远近与食物量的多少，而其它蚂蚁通过触角能够检测识别到这种信息素，井跟踪之，从而最终找到食物源。而当大量蚂蚁不断地从蚁穴通往食物源，沿途不断地识别原有信息素，并同时散播新的信息素，使得越短的路线上的信息素浓度越高，将最终找到一条最短的路线，此后所有的蚂蚁都将走这条最短路径到达食物源。多男1CPI始必J:初始时，设定最大代数iv1AXGEN，蚂蚁数m

5、，GEN=Oo多男2CR,*AJ:将m只蚂蚁分别随机地置于各顶点处，即每个蚂蚁过程随机地给予一个起始点。多男3C稼耸拥):每个蚂蚁按照状态变化规则一步一步地构造一个解，即生成一条线路。生成路径的时候根据候选边中的信息素的浓度来选择下一条边，信息素浓度越高的边被选中的可能性越大。步牙46胃淑冤濒腻会清踢即:应用局部信息素更新规则来改变信息素浓度。需要减少选择边上的信息浓度，类似于信息素的挥发，防止过快陷入局部最优解。多男5:若所有的m个蚂蚁都构造完解，则转步骤6;否则转步骤30多牙‘C全周更澎徐窟清店即:应用全局信息

6、素更新规则来改变信息素值。对属于己求出的最好路径中的边，需要增加边上的信息素的浓度。PSO问题棋型PSO算法是对简化的社会行为的模拟，它是源于对鸟群觅食行为的研究。群体中的个体(称作粒子)在一个n维的解空间里移动，每个位置表示问题的一个解。每个粒子都能记忆白己曾经达到过的最好解，在一个群体中的所有粒子共享这个群体中搜索的最好解的信息。算法的描述为:V,d=W'Vid+nI*rand()"(Pid-Xid)+R2`rand()`(PW-Xid)(1)Xid=Xid+Vid(Z)其中，Xm表示粒子所在的位置，既问题的一

7、个解，Vid表示‘速度’，Pid表示当前摘要粒子所搜索到的最好解，Pga表示当前群体所搜索到的最好解本文主要}_作在原有蚂蚁算法的基础上提出了儿个具体的改进1.将3-叩t方法混入蚂蚁算法求解过程中，对每代最优解进行改进，这样，在第2部分的求解步骤5与步骤6之间加入步骤5'二步男5'对本代最优解使用3-opt算法进行改进当所有m个蚂蚁生成了m个解，其中有一条最短路线是本代最优解S设W为路线S中经过顶点的有序排列，r=r2,r3是从W中随机地选择的二个顶点，N为没有任何改进的最大循环次数。则3-opt算法的步骤如卜步0

8、5'-l勿贻化夕:循环次数变量t=1，当前最优解S*=S，其长度为以S*).步#/r`5=2(e津男):在W中随机选择三个顶点::，r2,r3-步'S'-3(ifeW):将这三条顶点排序得到S.的六个相邻解SI,S2,'二，SR，比较这六个相邻解的路线{'c度4Sr),4SI),‘二，以助，选L，二。*14S1),1(SO，二、以S6)),其对应的解为5’。