古蔺城区邮递配送路线优化分析.docx

《古蔺城区邮递配送路线优化分析.docx》由会员分享，可在线阅读，更多相关《古蔺城区邮递配送路线优化分析.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、四川农业大学本科毕业论文（设计）（2019届）题 目： 古蔺城区邮递配送路线优化分析 学 院： 理学院 专 业： 信息与计算科学 学生姓名： 夏波 学号： 20155370 导 师： 程莉 职称： 副教授 完成日期： 2019年 4 月 30 日目 录摘要1关键字1Abstract1Keywords11 引言12 原理与方法22.1权值、路径、最短路径22. 2赋权图的带权邻接矩阵22.3 变异系数赋权法32.3.1 计算指标的权重32.3.2 计算路线的权值32.4 蚁群算法32.4.1 蚁群算法的起源32.4.2 蚂蚁算法实现步骤33 实例分析63.1 变异系数法计算权值73.2 通过蚁群

2、算法找出的最短路径94 总结11参考文献12致谢13附录14古蔺县城区邮递配送路线优化分析信息与计算科学专业 夏波导师：程莉摘要：随着电子商务的飞速发展，物流也变得越来越重要。本文使用变异系数法对配送路线的影响因素进行预处理，从而消除指标之间的量纲差异。再用加权平均法对各条路线重新进行赋权并简化路线，最后使用蚁群算法找出从配送中心出发途经各个需求点再回到出发点的最优配送的路线。 关键字：线路优化；变异系数法；蚁群算法；最短路线Optimizing Analysis of Post Distribution Route in Gulin CountyBo XiaAbstract：With the

3、 rapid development of e-commerce, logistics has become more and more important. In this paper, the coefficient of variation method is used to pre-process the influencing factors of the distribution route, thus eliminating the dimensional difference between the indicators. Then, the weighted average

4、method is used to re-weight each route and simplify the route. Finally, the ant colony algorithm is used to find the route of the optimal distribution from the distribution center through each demand point and back to the starting point.Keywords:Path optimization;Model of variation coefficient; Ant

5、Colony Algorithm;Shortest path1 引言运输问题1,2由来已久是社会生活和军事活动中比较常见的问题。从古代快马加鞭的军情快报以及粮草押运到近代的书信沟通再到如今蓬勃发展的快递服务业。信息数据化技术的发展为现代物流产业的发展带来了巨大的推进作用。从物流的发展简史可以发现，物流的飞速发展是经济发展向更高层次迈进的结果。物流配送变得越来越重要，它不但仅关乎着一个行业的发展，同时也关乎着一个地区的经济发展3。我国的物流行业起步比较晚，1979年物流这个概念才从国外引进到国内4。尽管我国对物流的研究在世界范围内起步比较晚，但是近年来，我国的学者对物流方面的研究逐渐增多。李阳在

6、文献5中通过构建多目标多车场路径优化模型，来解决城市的共同配送问题。彭湖在文献6中建立区域物流模型，对云南省物流需求量进行预测，并提高了区域物流的需求预测精度。罗俊在文献7中通过建立配送网络权重模型研究最优路径的选择。马红军在文献8中对在电子商务背景下农村物流市场的分析，提出了利用微电脑技术和网络技术开展农村市场商务活动。同时指出农村的物流具有点多，线长的特点并且农村物流系统发展不是很完善。生力军在文献9中运用粒子群算法计算并找出最佳的配送中心和路线。为促进现代物流的健康发展和推进快递下乡服务。本文在利用变异系数法对各条路径进行预处理之后，利用基本蚁群算法10找出了古蔺地区圆通快递从配送中心出

7、发历经各个需求点后再返回到出发点的配送路线。因它提供了一种比较科学的能够解决本文中所面临问题的方法。所以本文采用蚁群算法。2 原理与方法 2.1权值、路径、最短路径权值：图的边具有与它相关的数，记为，称为权值。这些权值可以体现从一个顶点到另一个顶点的距离，所需的时间等等因素。在图中，若果从顶点出发，沿着并经过顶点，最终到达顶点，则称顶点序列（）为从顶点到顶点的一条路径，或称为通路，其中为图的边。最短路径：若从图中找出一条从点出发到收点的通路，使得沿着这条通路的路径长度最小。这条通路就称为该图的最短路径（Shortest path）。2. 2赋权图的带权邻接矩阵设为图的带权邻接矩阵，图的顶点集为

8、，其中图是阶无向的简单赋权图，。若顶点和顶点之间存在可行边，其权值为，则；若顶点和顶点之间不存在可行边，则其权值，那么；若顶点（同一个顶点），则其权值，那么由定义可知，并且矩阵为对称矩阵。2.3 变异系数赋权法2.3.1 计算指标的权重为了消除指标因量纲差异的影响,就要用各项指标的变异系数11,12来衡量指标取值的差异程度。变异系数公式： (2.1)式中：是第项指标的变异系数；是第项指标的标准差；是第项指标的平均值。指标权重为: (2.2)2.3.2 计算路线的权值通过上述方法计算得出的权重值和原始数据通过加权平均法计算出各指标因素的具体权值。 (2.3)式中：是第项指标的各条路线总权值；是第

9、项指标因素的原始数据。2.4 蚁群算法 2.4.1 蚁群算法的起源蚁群算法13,14，是一种模拟蚂蚁寻找食物行为的仿生优化算法，是用来在图中寻找最优路径的一种算法。于1992年由意大利学者Dorigo M提出。他的“双桥”实验证明蚂蚁在搜寻搬运食物时总是会选择距离食物源较短的路线。蚂蚁会在所走路线上留下信息素，并且倾向于走浓度高的方向。在经过相同的一段时间后蚂蚁在较短路径上留下来的信息素浓度就会较高。由于这种影响，慢慢的选择较短路径的蚂蚁的数量也随之增多。最终绝大部分蚂蚁个体就通过这种信息交流机制来搬运食物，选择最短路线。2.4.2 蚂蚁算法实现步骤在运用蚂蚁算法15中，每只蚂蚁都需要遵循以下

10、几个规则：第一，蚂蚁都会在它经过的路径上留下信息素，并且一部分信息素会随时间挥发。当每一只蚂蚁走完一圈后或每走完一段路径之后，就要对路径上的信息素浓度进行更新；第二，依据两点之间距离和这两点之间路径上的信息素浓度为变量，每只蚂蚁都按照某一概率进行转移到下一个结点；第三，限制蚂蚁下一步选择的结点，蚂蚁不可以走已经走过的结点，直到走完一圈。（1）引入表示时刻城市上的蚂蚁数量，为蚂蚁的总量。蚂蚁在时刻从由结点运动到结点在运动过程中在状态转移概率为：表示时刻在结点和结点之间边上的信息素残留值。为启发函数，表示结点到结点的期望程度。，越小结点间的距离越短那么蚂蚁下一步往该结点转移的概率就越大。是蚂蚁下一

11、步可以访问的结点的集合。为信息素启发因子，体现信息素对蚂蚁运动的影响作用。为期望的启发因子，体现蚂蚁的能见度的重要性，如果它的值越大那么蚂蚁选择离它较近的结点的可能性就越大。所以不能过大。一般取值为，比较合适。表用来记录蚂蚁所走过的结点，用来对蚂蚁的后续要走的路线做调整（2）为避免过多的信息素对启发信息造成较大的影响，当蚂蚁走完一段路径后，就对路径上的信息素浓度进行更新。时刻路径的信息素更新如下： 为信息素挥发系数，；运动后留下的信息素的增量。为第只蚂蚁通过这次循环在路径上留下的信息素。为每只蚂蚁的信息素总量。为循环所走的路径总长度。（3）初始化：设定最大的循环次数，当达到最大循环次数或所有蚂

12、蚁都选择同一条路线时结束。第一步：设定,并令每条路径上的并且，将这只蚂蚁随机投放到个节点上；第二步：令，（是表得下标） 将第只蚂蚁的初始结点存放到中；第三步： 一直向下走直到走完所有的结点，并更新可行的结点表中的数据；第四步： 计算第只蚂蚁所走的路径的总长度，并更新找到的最短路线； 更新这条路径上的信息素浓度：第五步：对每一条边 第六步：并且（不是所有的蚂蚁都选择同一路线）然后清空表中的所有数据， 最后输出最短路径，结束程序3 实例分析以圆通快递从网点地址古蔺镇第一小学附近（以该点为配送点编号为）只考虑到文中7个需求点的运输路线为例，经过的需求点及对应的编号分别为中城中学（）、教育局（）、蔺阳

13、中学（）、古蔺镇中学（）、古蔺职高（）、古蔺镇第二小学（）、古蔺中学（）。从中国公路地图及古蔺城区地图可知配送中心及各个需求点两两间的多条路线。古蔺城区地图和需求点如下图1：图1 古蔺城区地图配送中心以及需求点的分布及路径间的数据关系简略图如下无向图2：图2 配送点及需求点间分布关系图3.1 变异系数法计算权值第一步：计算每各指标的平均数及标准差：第二步：通过公式（2.1）计算指标的变异系数：第三步：利用公式（2.2）计算各个指标的权重：最后利用公式（2.3）计算出个各条路径的权值大小。本文中通过excel计算的各条路径的结果如下表1：表1路径及对应路线权值指标因素 路径路径长度（m）红路灯或

14、路口个数路线权值（v5,v6)3000.0001.0001177.798（v1,v6)3000.0002.0001178.406（v2,v6)2800.0002.0001099.927（v2,v5)1600.0001.000628.443（v1,v2)1200.0001.000471.484（v1,v2)1300.0001.000510.724（v1,v5)726.0000.000284.880（v1,v4)771.0000.000302.538（v1,v3)497.0000.000195.021（v2,v3)1400.0001.000549.963（v2,v7)1700.0001.00066

15、7.682（v7,v8)825.0001.000324.335（v3,v8)1800.0001.000706.922（v3,v8)1500.0001.000589.203（v3,v4)1200.0000.000470.876（v3,v4)1000.0000.000392.397总数24319.00013.000平均数1519.9380.813标准差791.4460.655变异系数0.5210.806权重0.3920.608通过计算后重新对图2中的各条路线进行赋值并简化两两需求点之间的路线得到如下所示的带权无向图3：图3配送点及需求点之间的带权无向图3.2 通过蚁群算法找出的最短路径根据无向赋权

16、图的带权邻阶矩阵的定义可计算出简化后的带权无向图3的带权邻阶矩阵，其中对于结点间没有通路的边用一个无穷大的数表示，得到的带权邻阶矩阵如下：将矩阵输入到由MATLAB设计的算法程序中并配置好各项参数的值。对于文中的问题，程序中参数的取值分别为；。经过matlab计算得到的结果截图如下：图4最优路线及最短距离图5最短距离变化值由图5最短距离变化值我们可以看出在一次次的循环后，这蚂蚁每走一次循环后只蚂蚁所走完的平均距离长度逐渐向最短距离靠近。并且最短距离的值逐渐稳定趋于一常数值。也就是说此时绝大部分蚂蚁都走在最短的路径上，那么我们可以认为这绝大部分蚂蚁所走的这条路线就时我们所要寻找的最优路线。再由图

17、4最优路线及最短距离可知，在经过100次迭代后得到最短路线为：或者利用最短路线的结果画出对应图3中的路线图的最优路线如下图6所示：图6最优路线图并且由图4可知道最短路线的结果最短路径对应的最小权值为：4 总结本文在综合考虑了交通状况（主要是红路灯和路口个数）和交通路线的情况下，利用变异系数法对每条路径重新进行赋权。最后再利用基本的蚁群算法，找出了从配送点出发历经各个需求点后再返回到出发点的最优路线。进而制定邮递的配送路线以及在运送时的装车方案（按照路线相反的方向依次装货）。对圆通快递制定在古蔺城区的邮递配送路线具有一定的指导意义。对于古蔺城区其它的更多的需求点也可运用此方法找到最佳的配送路线。

18、然而，就目前而言蚁群算法本就存在一些不足之处。当结点的个数增加到一定的量后蚁群算法的时间复杂度就会剧增，同时在解决某些问题时，如果对应的参数调的不恰当容易陷入局部最优。就目前而言对于这种旅行商问题还未找到一套精确有效的算法，本文中所使用到的蚁群算法也只是找出了旅行商问题的最优解的近似解，当然对于文中结点较少比较容易验证出通过算法找到的那条线路就是最优路线。但是，当结点数增加到50甚至更多的时候就不容易验证出，它到底是不是最优路线。参考文献1 Anushree Dutta,Dipak Kumar Jana. Expectations of the reductions for type-2 tr

19、apezoidal fuzzy variables and its application to a multi-objective solid transportation problem via goalprogramming techniqueJ. Journal of Uncertainty Analysis and Applications,2017,5(1):10-31.2 Sharmistha Halder (Jana), Barun Das, Goutam Panigrahi, Manoranjan Maiti. Some special fixed charge solid

20、transportation problems of substitute and breakable items in crisp and fuzzy environmentsJ. Computers & Industrial Engineering,2017,111:19-40. 3 丁俊发. 改革开放40年中国物流业发展与展望J.中国流通经济, 2018(04):3-17.4 贺登才.中国物流业发展十大趋势N.国际商报, 2008.5 李阳.多目标多车场的城市共同配送路径优化研究D.浙江工商大学, 2018:4-15.6 彭湖.基于组合预测的区域物流需求预测研究D.昆明理工大学, 200

21、9.7 罗俊.基于行为分析的货物运输方式选择模型研究D.武汉理工大学,2012:30-56.8 马红军.电子商务背景下农村市场物流配送分析J.现代营销(信息版),2019(03):54-55.9 生力军.基于量子粒子群算法的物流配送中心选址J.科学技术与工程,2019(11):183-187.10 李安颖,陈群,宋荷.基于蚁群算法的带有时间约束旅行商问题求解J.自动化仪表,2019,40(04):95-98.11 孙仲英.基于变异系数法的灰色关联分析模型及其应用J.西部皮革,2017,39(08):298.12 储莎,陈来.基于变异系数法的安徽省节能减排评价研究J.中国人口.资源与环境,201

22、1,21(S1): 512-516.13 冯志雨,游晓明,刘升.分层递进的改进聚类蚁群算法解决TSP问题J/OL.计算机科学与探索:1-182019-05-09.14 赵艳东,张申申.基于改进蚁群算法的智能交通路径规划J.工业仪表与自动化装置,2019(02):30-32.15 汪海森,林耿,卓彩娥.中国邮递员问题的匹配算法J.长江大学学报(自科版),2013,10(25):10-11.致谢首先，感谢生我养我。并且在我漫长的求学之路上给予我的关心和支持。他们给了我无私的爱，我深知他们为我的求学所作出的巨大牺牲和努力。我想如果没有父母的支持我也无法走到今天，无法走进四川农业大学，更别说在这里求学

23、。其次，在此衷心感谢程莉老师在论文设计过程中的悉心指导和在论文写作时给予帮助，同时也感谢大学四年中给予我无私教诲的所有老师，为我打下了深厚的专业基础。也感谢这四年中陪伴和支持我的同学们。同时也感谢给予我关爱的长辈们和默默支持我的朋友们，祝你们幸福、安康！最后，衷心地感谢在百忙之中抽出您宝贵的时间审来审阅本论文的各位老师!附录：蚁群算法解决旅行商问题matlab算法代码如下：%蚁群算法解决旅行商问题%-clear all; %清除所有变量close all; %清图clc ; %清屏m=20; % m 蚂蚁个数Alpha=2; % Alpha 表征信息素重要程度的参数Beta=4; % Beta

24、 表征启发式因子重要程度的参数Rho=0.25; % Rho 信息素蒸发系数NC_max=100; %最大迭代次数Q=80; %信息素增加强度系数 M=10000 %当两个结点没有通路时用一个比较大的数表示 D=0 471.484 195.021 302.538 284.880 1178.406 M M;471.484 0 549.963 M 628.443 1099.927 667.682 M;195.021 549.963 0 392.397 M M M 589.203;302.538 M 392.397 0 M M M M;284.880 628.443 M M 0 1177.798 M

25、 M;1178.406 1099.927 M M 1177.798 0 M M;M 667.682 M M M M 0 324.335;M M 589.203 M M M 324.335 0%D表示结点完全图的赋权邻接矩阵%-% 主要符号说明% NC_max 最大迭代次数% m 蚂蚁的数量% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% Rho 信息素蒸发系数% Q 信息素增加强度系数% R_best 各代最佳路线% L_best 各代最佳路线的长度%=%第一步：变量初始化n=size(D,1)%n表示问题的规模（结点的个数）Eta=1./D; %Eta为启

26、发因子，这里设为距离的倒数Tau=ones(n,n); %Tau为信息素矩阵Tabu=zeros(m,n); %存储并记录路径的生成NC=1; %迭代计数器，记录迭代次数R_best=zeros(NC_max,n) ; %各代最佳路线L_best=inf.*ones(NC_max,1); %各代最佳路线的长度L_ave=zeros(NC_max,1); %各代路线的平均长度while NC=rand); %若计算的概率大于原来的就选择这条路线 to_visit=J(Select(1); Tabu(i,j)=to_visit; end end if NC=2 Tabu(1,:)=R_best(N

27、C-1,:); end %第四步：记录本次迭代最佳路线 L=zeros(m,1); %开始距离为0，m*1的列向量 for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); %原来的距离加上第j个结点到第j+1个结点的距离 end L(i)=L(i)+D(R(1),R(n); %一轮下来后走过的距离 end L_best(NC)=min(L); %最佳距离取最小 pos=find(L=L_best(NC); R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线 L_ave(NC)=mean(L); %

28、此轮迭代后的平均距离 NC=NC+1 %迭代计数器加一，继续迭代 %第五步：更新信息素 Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵 for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); %此次循环在路径（i，j）上的信息素增量 end Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i); %此次循环在整个路径上的信息素增量 end Tau=(1-

29、Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素 %第六步：禁忌表清零 Tabu=zeros(m,n); %直到最大迭代次数end%第七步：输出结果Pos=find(L_best=min(L_best); %找到最佳路径（非0为真）Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径Shortest_Length=L_best(Pos(1) %最大迭代次数后最短距离figure subplot(1,2,1)plot(L_best)xlabel(迭代次数)ylabel(目标函数值)title(函数值变化曲线)subplot(1,2,2)plot(L_ave,g)hold onplot(L_best)title(平均距离和最短距离) %标题18