文档介绍：该【送货路线设计方案论文 】是由【1781111****】上传分享，文档一共【32】页，该文档可以免费在线阅读，需要了解更多关于【送货路线设计方案论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..摘要本文是关于快递公司送货策略的优化设计问题,即在给定送货地点和给定设计规范的条件下,确定业务员的运行线路,总的运行路程数,以及时间最省的策略。根据设计要求,制定了从静态规划到动态规划的解题思路;建立了以送货时间最省、所走路程最短等为目的的优化模型,给出的不同优化目标和约束下的优化送货策略,即送货路径。本文主要完成的工作有:Ⅰ根据所给的数据,使用Dijstra算法,循环n(n为总的点个数)次。求出各点之间的最短路程,并存入二维数组dist[i][j]中。Ⅱ对问题一,在送货员遵循送货路线的要求前提下,以所用的时间最短为目标函数,遍历全部的个点并回到点,在此条件下,利用动态规划得到了一条最短路径的优化设计。Ⅲ对问题二,为考虑送货时间限制,需采用多次分区域的优先时间模型,而每个区域的路径优化设计可利用问题一的模型,同时遍历完一区域后,利用其最后一点找到与它距离最短的下一区域的点,若无连通的,则找次短的。这样重复下去,直到所有的区域都遍历完。最后,从最后一点返回起始点。如此得到的路径即为我们所需的优先时间的优化设计路径。Ⅳ对问题三,其约束条件是送货员所能承受的货物的重量和体积的限制,在此前提下,则可利用多阶段送货模型,进行路线得优化设计。并且,如何实现分阶段需要进行客观实际的分析,在把握使误差最小和灵敏度最高的情况下来进行分阶段,各阶段的最优路径设计与问题二中个区域的路径设计是大同小异的,故如何分阶段,分几个阶段对解决问题三的极其重要的,也是关键的一步。关键字:路径规划,最优化,图模型,多目标动态规划,送货员送货,分区域,分阶段:..,网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且他们往往一人送多个地方,请设计方案使其耗时最少。现有一快递公司,库房在图中的O点,一送货员需将货物送至城市内多处,请设计送货方案,使所用时间最少。该地形图的示意图见图,各点连通信息见表,假定送货员只能沿这些连通线路行走,而不能走其它任何路线。各件货物的相关信息见表,个位置点的坐标见表。假定送货员最大载重公斤,所带货物最大体积立方米。送货员的平均速度为公里/小时。假定每件货物交接花费分钟,为简化起见,同一地点有多件货物也简单按照每件分钟交接计算。现在送货员要将件货物送到个地点。请完成以下问题。.若将~号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。.假定该送货员从早上点上班开始送货,要将~号货物的送达时间不能超过指定时间,请设计最快完成路线与方式。要求标出送货线路。.若不需要考虑所有货物送达时间限制(包括前件货物),现在要将件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路,给出送完所有快件的时间。由于受重量和体积限制,送货员可中途返回取货。可不考虑中午休息时间。:..快递公司送货地点示意图O点为快递公司地点,O点坐标(,),单位:米注:表“各货物号信息表”、表“个位置点的坐标”、表“相互到达信息”:已知起点和终点的图的遍历问题的合理优化的路线设计图的遍历问题的指标:路程和到达的时间,货物的质量和体积,以及最大可以负载的重量和体积。在路线的安排问题中,考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间要求是否满足题意即采用多次分区域的假设模型,从而找出最优的解。对于问题三则要考虑到体积和重量的双重影响,每次到达后找到最大的体积和重量的点然后返回,再依次分析各个步骤中可能存在的不合理因素,达到模型的进一步合理优化,得到最合理的解。二、模型假设根据题意,可以进行如下假设:、同一地点有多件货物也简单按照每件货物分钟交接时间计算、所用的距离数据都精确到米,、要求达到不超过的时间不包括此次在该店交易的时间、到同一地点的货物要依次拿上,即不考虑在以后经过时再带一些货物、无塞车现象,即业务员送快递途中不受任何外界因素影响、货物可进行任意拆分三、符号说明符号符号说明i,j货物点的标号A个点的坐标矩阵a各点的连通关系矩阵w点的权值(距离)矩阵v送货员的平均速度l从o点到i区域所用的最短时间m到达i区域可以带的最多的货物的质量iv到达i区域可以带的最多的货物的体积iM一次可以携带的最多的货物的总质量V一次可以携带的最多的货物的总体积:..i、j=、、...,且M=kg,V=三、模型的建立与求解本文模型的整体框架如下:,使用Floyd算法,即在Dijstra算法上循环n(n为总的点个数)次。.模型的求解根据算法和相邻点的距离可以用Dijstra算法求出任意两点的最短距离。图采用权值矩阵的形式描述,w(i,j)表示i点到j点的距离。如果没有直接连通,则为无穷大,即用Matlab中的inf表示。Dijstra算法只能求出结点i到其余各点的距离。算法引入这样的两个集合s和t,s是确定了的到结点i最短距离的点,t为全集u和s的差集即那些还未确定最短路径的结点。而且s的初值是{i},t的初值是u-{i}。另外在引入一个标记数组dist[n],其中在某一步中dist[k]表示当前i到:..dist[k]的初值是w(i,k)。整个算法过程如下:、在t中悬着一个d[k]最小的节点k,将k并入s,并从t中去掉,若果t为{},则转到;、用k结点和t中其余的结点进行一遍比较,如果dist[i]>dist[k]+w[k][i],则用dist[i]=dist[k]+w[k][i]取代原来的d[i],重复;、算法结束,此时dist[k]中保存的就是从i到k结点的最短路径。算法就是以这样非常简单的形式完成了求解,时间复杂度是o(n^)确定了从i点到其余各结点的最短路径。图相邻点的距离使用循环的结构求出~各个点之间的最短距离。程序见附录.。可求出最短距离的权值矩阵di。模型二——,i,j=。:..需要到达的点(用红色表示)其中共经过个点,送运件货物因该件货物=.kg<kg,?v=.m<m,故可以一次把货物携带进运送。由t与l的关系可知,要使所用的时间最小即所走的路程最小。即目标函数是:t?l?v?t?约束条件是:必须全部遍历并回到点即从点出发全部遍历这图的个点并回到点的最短距离。要距离最短则每一步都要最短,即从点开始找最短的点到达后,继续找未遍历的最短的点,则可求出最短的距离。本题要求回到点,则是两个开始最短遍历的点在某点重合。.:顺序为:Columnsthrough:..+返回路程为:.e+总的路程为:.e+总的时间为:.(h)模型三——,先把时间分成三个阶段,其个目的点分布如下(用红色标注):图考虑时间点的位置注:红色表示第一个时间段:~:的点:..:~:的点蓝色表示第三个时间段~::、第一个时间段顺序为:第一个时间段路程为:.e+、第二个时间段顺序为:第二个时间段路程为:.e+、第三个时间段顺序及路程为:第三个时间段路程为:.e+返回路程为:.e+总的路程为:.e+总的时间为:.(h)模型四——,但由于M=kg,V=.,而m<kg,v<m,故因应该以总总m<kg,v<m的标准到达最远点后返回。目标函数:ll?w(i,j)约束条件:m<kg,v<,再找出离该点最近的点,直到不满足约束条件。程序见附录.:..分阶段遍历点的位置注:第一阶段用红色标注第二阶段用黑色标注第三阶段用蓝色标注第四阶段用紫红色标注其结果如下:、第一阶段顺序为:路程为:.e+、第一阶段顺序为:ColumnsthroughColumnsthrough路程为:.e+、第一阶段:..ColumnsthroughColumn路程为:.e+、第一阶段顺序为:路程为:.e+总的路程为:.e+总的时间为:.(h)五、模型的分析●误差分析对于模型一是使用了精确的Floyd算法,即Dijstra算法故误差可以忽略不计。对于模型二,虽存在断开的点会出现一定的误差,但对断开的点进行的优化处理,故该模型可以用。对于模型三,因分区域的方法存在很多,故不可避免的会产生一些误差。有由于分的区域越多,走的路程也就越多,这样可以大大地消除一些误差,故此模型可以用。对于模型四,该模型有较大的误差,因未考虑货物的拆分对现实会有一定的影响,同时阶段的不同划分也是会存在一些不确定的误差。虽然准确性由一定的挑战性,但相对于其他的划分又有一定的优越性,故该模型适合此问题的求解。●灵敏度分析对于模型一、二、三,灵敏度很好,模型的准确性很高。对于模型四,由于质量和体积的限制,其灵敏度不是很好,但准确性还是很高,因此模型可以使用。六、模型的评价、:·充分的利用了已知数据来建立模型,使其具有很高的准确性和可行性·使用的准确的算法和适当的假设,使模型的准确性和实用性达到统一:..Matlab工具使数据处理误差达到最小缺点:·由于数据太多,没法使用工具进行模型的检验,,可以考虑到不同的地点送的货物进行拆分,、参考文献[]:姜启源、谢金星、叶俊编,数学模型-版,北京,高等教育出版社,.[]:吴建国、汪名杰、李虎军、刘仁云编,数学建模案例精编-版,北京,中国水利水电出版社,.[]:唐焕文、贺明峰编,数学模型引论-版,北京,高等教育出版社,.[]:图论任韩[]:图论第三版德迪斯特尔著:..附录:(公斤)体积(立方米)不超过时间..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..:..............:........................................................................................:...........................................位置点X坐标(米)Y坐标(米):...序号位置点位置点:..:..OOO:(Floyd)算法求解算法l=;fori=:dist(i)=ww(,i);parent(i)=location(i);f(i)=;endf()=;:..i=:cost=inf;k=;forj=:ifdist(j)<cost&&f(j)==cost=dist(j);k=j;endendifk>f(k)=;fort=:iff(t)==ifdist(t)>dist(k)+ww(k,t)dist(t)=dist(k)+ww(k,t);parent(t)=location(k);l=l+dist(t)-dist(k);endendendendend%Floydfori=:forj=:di(i,j)=ww(i,j);dian(i,j)=i;endendfork=:fori=:forj=:ifk~=i&&k~=j&&i~=jifdi(i,j)>di(i,k)+di(k,j)di(i,j)=di(i,k)+di(k,j);dian(i,j)=location(k);endend:..=xlsread('');fori=:forj=:t=A(i,:)-A(j,:);c(i,j)=sqrt(t()^+t()^);%两点之间的距离endenda=[;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;];%通路表b=zeros();fori=:b(a(i,)+,a(i,)+)=;b(a(i,)+,a(i,)+)=;enda=b.*c;fori=:forj=:ifa(i,j)==a(i,j)=inf;end;ifi==ja(i,j)=;endendendw=a;location=[];fori=::..endfori=:aa(i,)=A(location(i),);aa(i,)=A(location(i),);endplot(A(:,),A(:,),'g*',aa(:,),aa(:,),'r*')title('?个点用红色表示')xlabel('横坐标')ylabel('纵坐标')holdonfori=:forj=:ifa(i,j)~=&&a(i,j)~=infx=A(i,)::A(j,);y=(x-A(i,))*(A(j,)-A(i,))/(A(j,)-A(i,))+A(i,);plot(x,y,'b')endendendholdonfori=:forj=:ww(i,j)=w(location(i),location(j));ww(j,i)=ww(i,j);endend%求送货路线l=;fori=:dist(i)=ww(,i);parent(i)=location(i);f(i)=;endf()=;fori=:cost=inf;k=;forj=:ifdist(j)<cost&&f(j)==cost=dist(j);k=j;endend:..ifk>f(k)=;fort=:iff(t)==ifdist(t)>dist(k)+ww(k,t)dist(t)=dist(k)+ww(k,t);parent(t)=location(k);l=l+dist(t)-dist(k);endendendendend%Floyd求返回路线fori=:forj=:di(i,j)=ww(i,j);dian(i,j)=i;endendfork=:fori=:forj=:ifk~=i&&k~=j&&i~=jifdi(i,j)>di(i,k)+di(k,j)di(i,j)=di(i,k)+di(k,j);dian(i,j)=location(k);endendendendenddi(,)di(,)l=l+di(,)parentlll=l*./:...location=[];fori=:location(i)=location(i)+;endfori=:aa(i,)=A(location(i),);aa(i,)=A(location(i),);endplot(A(:,),A(:,),'g*',aa(:,),aa(:,),'r*')text(A(:,)+.,A(:,),numcell(:));title('个点在图中的分布?个点用红色表示')xlabel('横坐标')ylabel('纵坐标')holdonfori=:forj=:ifa(i,j)~=&&a(i,j)~=infx=A(i,):.:A(j,);y=(x-A(i,))*(A(j,)-A(i,))/(A(j,)-A(i,))+A(i,);plot(x,y,'K')endendendholdonlocation=[];fori=:location(i)=location(i)+;endfori=:aa(i,)=A(location(i),);aa(i,)=A(location(i),);endplot(aa(:,),aa(:,),'Ko')location=[];fori=:location(i)=location(i)+;endfori=::..aa(i,)=A(location(i),);endplot(aa(:,),aa(:,),'C+')%个位置fori=:forj=:ww(i,j)=w(location(i),location(j));endendl=;fori=:dist(i)=ww(,i);parent(i)=location(i);f(i)=;endf()=;fori=:cost=inf;k=-;forj=:ifdist(j)<cost&&f(j)==cost=dist(j);k=j;endendifk>f(k)=;fort=:iff(t)==ifdist(t)>dist(k)+ww(k,t)dist(t)=dist(k)+ww(k,t);parent(t)=location(t);l=l+dist(t)-dist(k);endendendendend:..l=l%个位置location=[parent()-];fori=:location(i)=location(i)+;endfori=:aa(i,)=A(location(i),);aa(i,)=A(location(i),);endfori=:forj=:ww(i,j)=w(location(i),location(j));ww(j,i)=ww(i,j);endendl=;fori=:dist(i)=ww(,i);parent(i)=location(i);f(i)=;endf()=;fori=:cost=inf;k=-;forj=:ifdist(j)<cost&&f(j)==cost=dist(j);k=j;endendifk>f(k)=;fort=:iff(t)==ifdist(t)>dist(k)+ww(k,t)dist(t)=dist(k)+ww(k,t);parent(t)=location(t);:..endendendendendparentl=l%location=[parent()-];fori=:location(i)