《送货路线设计问题(优秀论文)》由会员分享，可在线阅读，更多相关《送货路线设计问题(优秀论文)（33页珍藏版）》请在金锄头文库上搜索。
1、14送货路线设计问题送货路线设计问题1、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛， 每个送货员需要以最快的速度及时将货物送达，而且他们往往一人 送多个地方，请设计方案使其耗时最少。 现有一快递公司， 库房在图 1 中的 O 点， 一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少。该地形图的示意图见图 1，各点连通信息见 表 3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物 的相关信息见表 1，50 个位置点的坐标见表 2。 假定送货员最大载重 50 公斤，所带货物最大体积 1 立方米。送货员的平均 速度为 24
2、公里/小时。假定每件货物交接花费 3 分钟，为简化起见，同一地点有 多件货物也简单按照每件 3 分钟交接计算。 现在送货员要将 100 件货物送到 50 个地点。请完成以下问题。 1. 若将 130 号货物送到指定地点并返回。设计最快完成路线与方式。给出 结果。要求标出送货线路。 2. 假定该送货员从早上 8 点上班开始送货，要将 130 号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前 30 件货物)，现在要将 100 件货物全部送到指定地点并返回。 设计最快完成路线与方式。 要求标出送货线路， 给出送完所有快件
3、的时间。由于受重量和体积限制，送货员可中途返回取货。 可 不考虑中午休息时间。2、问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路 线设计。 图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可 以负载的质量和体积。 在路线的安排问题中，考虑所走的路程的最短即为最合理 的优化指标。 对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区 域的假设模型从而找出最优的解 对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的 体积和质量的点然后返回， 再依次分析各个步骤中可能存在的不合理因素达到模 型的进一步合理优化得到最合理的解。15
4、3、模型假设与符号说明3.1、模型的假设（1） 、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物 （2） 、要求达到不超过的时间不包括此次在该点交易的时间。 （3） 、所用的距离数据都精确到米而时间则精确到 0.0001h （4） 、同一地点有多件货物也简单按照每件 3 分钟交接计算。3.2、符号说明其中 i，j=1、2、350并且M=50kgV=14、模型的建立及求解模型一模型二模型三模型四最 短 路 径模型任 意 两 点 之 间 的 最 短路距离图 的 遍 历模型由 起 始 点 遍 历 路 径 回到原点多 区 域 最短路多 区 域 无 返 回 起 点 的最短路多 阶 段 最短
5、路多 阶 段 有 返 回 起 点 的最短路16模型一模型一模型一模型一1.11.1 模型的建立模型的建立 我们为了求出各个点的之间的最短的路径，使用 Dijstra 算法求解。 Dijkstra 算法是图论中非常有名的一个算法。 图采用邻接矩阵的形式描述，w（i,j）表示结点 i 到结点 j 间的最短距离，如 果没有直接连通， 则为无穷大， 计算机中可以用一个很大的数据代替 （如 matlab 中的 inf） 。 但 dijkstra 算法只能求出从结点 i 到其它各结点的最短路径。 算法引入这样两 个集合 s 和 t，s 是那些已经确定了到 i 结点的最短路径的结点，t 为全集 u 和 s
6、的差集，即那些还未确定最短路径的结点。而且 s 的初值是i，t 的初值是 u-i。 另外再引入一个标记数组 dn， 其中在某一步 dk表示当前从 i 到 k 的较短路径， dk的初值为 w（i，k） 。 整个算法过程如下： 、 在 t 中选择一个 dk最小的结点 k，将 k 并入 s，并从 t 中去掉，如果 t 为则转到； 、 用 k 结点和 t 中其余结点进行一遍比较，如果 didk+mki，则用 dk+mki取代原来的 di，重复； 、 算法结束，此时 dk中保存的就是从 i 到 k 结点的最短路径。 算法就以这样非常简单的形式完成了求解，时间复杂度是 O(n2)，确定了从17i 到其余各
7、结点的最短路径。 1.21.2 模型的求解模型的求解 根据算法和相邻的点的距离可以用 dijkstra 求出任意两点的最短路径。图 1 相邻的点的距离 使用循环的结构求出 1-50 各个点之间的最短距离。程序 1 见附录 2.1 可以求出 w 和 a a 为最短路径是的所过的的地点 如从 O 开始到其余 50 个点的 a(0)= 0 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 36 27 34 37 43 38 41 36 41 40
8、 46 42 40 要从 O 点到 16 点则要先到 23 即 0-23-16 要从 O 点到 23 点则要先到 17 即 0-17-23-16 要从 o 点到 17 点则要先到 21 即 0-21-17-23-16 而 O 可以直接到 21 所以从 0 到 16 的最优路径是 0-21-17-23-16 最短的距离是 w（0,16）=7493m模型二模型二模型二模型二对于问题一的求解2.12.1 模型的建立模型的建立 由前 30 件货物可以到达的地点可以知道 i，j= 13、14、16、17、18、21、 23、24、26、27、31、32、34、36、38、39、40、42、43、45、4
9、9。18图 2 需要达到的点（红点标注的）其中共经过 21 个点，运送 30 件货物该 30 件货物=47.3kg1， 到45点时必须在9点半之前到达而1.74121.5 故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。 目标函数： =v+21约束条件是：T T 到个点的时间最大值到个点的时间最大值3.2 模型的求解图 4.4 个阶段的圈图对四个阶段分别求出到达的时间，由程序 4（附录 2.4）可知 分 4 个阶段 1.从 0 出发经过 13、18 到 24。 满足 tl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendend
10、ll=l;for i=1:nfor j=1:kif i=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;for i=1:nif ll(i)50)|(V1)break;endn=i;x=x;t-1;%disp(t-1,M,V)a(:,t)=inf;endsum=sum+v(p,1);42disp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;disp(所用时间是：) disp(T)disp(第二阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50s,t=m
11、in(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M50)|(V1)break;endn=n+1;p=t;x=x;t-1;%disp(t-1,M,V)a(:,t)=inf;enddisp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;disp(所用时间是：) disp(T)disp(第三阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M
12、50)|(V1)43break;endp=t;x=x;t-1;%disp(t-1,M,V)a(:,t)=inf;n=n+1;endsum=sum+v(p,1);disp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;disp(所用时间是：) disp(T)disp(第四阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M50)|(V1)break;endp=t;x=x;t-1;a(:,
13、t)=inf;n=n+1;endsum=sum+v(p,1);disp(顺序为：) disp(x,0)disp(总距离是：);disp(sum)T=sum/1000/24+3*i/60;disp(总时间是：);disp(T) 2.62.62.62.6、问题三的优化、问题三的优化 clcclear allload w.txt44a=w;load x.txtw=x;p=1;x=0;M=0;V=0;sum=0;v=a;a(:,p)=inf;for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;p=t;if(M50)|(V1)brea
14、k;endn=i;x=x;t-1;disp(t-1,M,V)a(:,t)=inf;endsum=sum+v(p,1);disp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;disp(所用时间是：) disp(T)disp(第二阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M50)|(V1)break;end45n=n+1;p=t;x=x;t-1;disp(t-1,M,V)a(:,t)
15、=inf;endsum=sum+v(p,1)-1630.4;sum=sum+v(p,1);disp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;disp(所用时间是：) disp(T)disp(第三阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M50)|(V1)break;endp=t;x=x;t-1;disp(t-1,M,V)a(:,t)=inf;n=n+1;if t=46break;endendsum=sum+v(p,1);sum=sum+v(p,1);disp(顺序为：) disp(x,0)disp(总路程是：) disp(sum)T=sum/1000/24+3*i/60;46disp(所用时间是：) disp(T)disp(第四阶段) p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if(M50)|(V1)break;endp=t;x=x;t-1;disp(t-1,M,V)a(:,t)=inf;n=n+1;endsu
