最短路径模型.doc

装 订 线第十一届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目(B)题密封号2010年5月4日剪 切 线密封号2010年5月4日 机电工程 学院 第 队队员1队员2队员3姓名 叶鑫林冯士恒李栋班级040831640408311504083018送货路线设计问题提纲：1.提出问题；2.模型分析和简单摘要；3.模型假设；4.符号设定；5.模型建立和求解；6.模型评价和建议；7.附录：程序以及结果。1.提出问题：现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。以上各问尽可能给出模型与算法。我们的核心算法就是迪杰斯特拉算法，我们自己基于java script编写的。2.模型分析和摘要：本文将货点实体间的线路选择抽象为图论最短路模型采用0-1 整数规划表述。建立直达数据库Q作为数据基库，根据用户需求建立不同目标的0-1 规划模型运用蚁群算法与迪杰斯特拉算法分别求解，最终方案即通过多限制条件下用java script编程得到最优效果输出。第一问属于典型VRP问题，在数据处理阶段发现载重和体积均符合要求，总量不多于五十公斤，体积不大于单位1，不用考虑这两方面限制条件，所以可以解决但是实际生活中可能出现有限制的条件，所以为了严谨我们考虑了限制条件。先建立站点至站点直达数据库Q 来描述两两可直达站点的所有线路，用到时，系统首先查询Q，得到所有直达方案。由于三问都是类似条件下的VRPTW问题，所以我们之间利条件最强的模型，针对各问对约束条件的弱化和强化程度分别调用。建立模型，用迪杰斯特拉算法的衍生算法为核心来做，结合多个限制条件选出最优解。对于各个小函数及用途在后面说明。为了能够为用户提供多种备选方案，我们首先使用基于迪杰斯特拉算法求解，得到不同目标下的多种优化方案；然后用限制条件求得全局最优解；两种方法求解步骤见后文，其中解决方案为解决方案如下：送货路线：0=18=13=19=24=27=34=40=45=42=49=42=43=38=35=32=23=17=14=21=36=31=27=26=0=总路程（单位：米）：53567花费时间（单位：分钟）：223两种求解方法的优劣在后文中给出了详细评价。第二问考虑有了时间限制，新的限制条件在模型一中，所以可以继续用模型以来求解，而模型一中的时间限制为软限制，既符合实际条件，也符合题目中的要求。结合实际，提出了本文的研究问题有时间窗的送货员路径问题(VRPTW)，建立了以送货员容量和客户需求等为约束条件，以配送运输成本为目标函数的VRPTW数学模型。在软限制条件下的求解，因为实际情况下很难让所有人都满意，所以决策上只能找最优解，可以根据客户的重要程度权衡可以允许的延误程度，在服务成本及客户满意度之间找到一个较为理想的平衡点。有软时间窗的VRP允许发生延误，但对延误发生的程度和频率有一定限制，这主要通过对延误的惩罚程度来体现的。在建模时表现为目标函数增加了一项惩罚项，造成目标函数值的增加。第二问答案为：解决方案如下：送货路线：0=18=13=19=24=27=34=40=45=42=49=42=43=38=36=31=39=31=36=38=35=32=23=17=14=21=26=0总路程（单位：米）：61459花费时间（单位：分钟）：303 第三问因为时间有限，程序过于复杂且难于调试，故没有求出最优方案。Pi(Si):惩罚函数。若送货员在Eti前到达i，或送货员在LTi之后到达，则服务延误，需支付一定的罚金，因此p*(Si)；设定如公式(3一8)所示Pi(Si)=ai(Eti-Si),SiLtiai,bi为惩罚系数，对某些重要的顾客或者对时间要求比较苛刻的顾客可能很大。第三问完全符合模型一，只是少了时间窗，即要求最大可能满足（体积和重量必须严格满足）的情况下路程最短。对于惩罚堵措施，由于时间关系没做出来程序，但我们觉得这个很有必要，对公司的信誉度以及顾客的满意程度都有很大的作用。最后我们给出了送货员路径问题的一些想法和建议，并提出了改进方案。关键字：货物运送 蚁群算法 迪杰斯特拉算法 送货员路径问题 VRPTW java script3.模型假设：1.送货员的服务质量一直相同；2.城市的交通没有负担，不会在路上耽误时间；3.被配送的物资可混装，不能混装需单独处理;4.流通中心有足够的物资可配送；5.满足所有任务点的品种、数量、规格需求；6.各配送路线的货物量不得超过送货员容积和载重量，否则将会受罚；7.接货点不会耽误送货员的时间；8.送货员中途不会发生意外或者突发事件；9.每一个客户的时间不是特别严格，允许出现一定概率的突发事件；10.送货员在选好目的点之后会按照选出的最短路径走；11.顾客不会因为提前货物到达而责怪送货员，是送货员的信誉度降低；4.符号的约定：（1）对于蚁群算法变量和参数符号按如下定义:令G一(V，E)为一无向图，V表示顶点集，E为边集，顶点V1，V2，V3，Vn为客户，V0吃饭吃菜vcvvvcvcvcvvccv 为配货中心；K:k个送货员，k；Cij:从i到j的运输成本；qi:客户i的需求量；dij:从i到j的距离；W:送货员的装载能力；C:最大体积；tij:送货员从i到j的行驶时间；Si:送货员到达vi的时间；Ti:送货员在vi处的卸货时间；Xij:决策变量，表示车是否从i出发后开向j，如果是，Xij值为1，否则，其值为0Eti,Lti：ETi，LTi为客户i的时间窗口，其中，Eti是客户要求到货时间段的始点，Lti是客户要求到货时间段的终点；5.模型建立和模型求解：（1）数据分析：1.通过对货物点坐标的分析，所有的货物点坐标都在X坐标（0-16000）和Y坐标（0-16000），且都在以O点为坐标的圆中；2每一个货物的重量都小于五公斤，且体积都小于单位一；3.位置关系表都明确，且两点之间均可到达；由以上分析，建立本文所要解决的VRPTW数学模型如下:目标函数：minZ=CijXij (i=1,2,3,.n;j=1,2,3n)约束条件：(dixij)q （3-2）aisibi in （3-3）xij=1 (in j=1,2,3.n) （3-4）x0j=1 (j=1,2,3.n) （3-5）xih-xhj=0 (hn, j=1,2,3.n, i=1,2,3,.n) （3-6）xi,n+1=1 （3-7）Sij+tij-K(1-xij)sj (I,jn) （3-8）Xij(0,1) (i,jn) （3-9）问题的目标是求总的送货员路径路程的最小值(3一1)，约束条件主要是车载，时间窗的开始时间和最晚时间。VRPTW的一个可行解要服务于所有的用户并且送货员不能超过送货员的最大容量(3一2)或者是送货员的时间限制(3一3)，除此之外，每个用户只能也仅只被一个送货员所服务(3一4)，等式(3一5)一(3一7)确保每个过程都从节点0开始，截止于节点N+l;(3一8)表示在服务完用户i后仍然有时间赶上用户j。每次送货员都是从0点开始走。（2）模型求解：1.问题一：本问题主要讨论迪杰斯特拉算法在VRPTW的应用，综合以最远点为核心的最短路径法，多限制条件下的最优解法，在载重。体积和时间限制下的最短路径，然后综合蚁群算法对以上算法进行比较路径最短且最优，行程载重和体积携带量最合适；惩罚度措施合适；求得最优解；基于此，问题共分为四个部分：1.数据处理，将每个货物的质量体积和时间窗以及货物点是否直达用表格给出；2.对于具体的数据进行分扇区处理，角度寻求最优解，然后在每一个扇区中寻找最远点，然后在时间窗优先的条件下，对重量和体积进行筛选；3.所有路径点确定之后，用迪杰斯特拉算法寻找最优路径；4.综合蚁群算法进行比较迪杰斯特拉的算法。1.数据处理：因为给的是货物运送点以及目的地的坐标位置，以及目的地之间是否直达，所以制成表格之后在附录中附有。通过在程序中建立关系对应表，把位置点和对应的坐标写出来。2具体分析：由于三个问题具有统一特征，所以我们只建立了一个模型，只是在这个模型中条件被要求的多少不同，既可以对某些条件弱化或者不考虑，综上，所以将各个小函数的用途先表示出来：（1.）首先对图中所有的坐标进行距离筛选，根据坐标由二次关系比较求出图中最远的点，然后将这个点的地址传出去，思想即为以此点和O点为中心线，建立扇区（扇区的确定在下个函数中体现），然后进行筛选。1./算两点,两点(忽略是否联通)返回之间距离，否则返回-1function distance(a,b) var mydistance a-=1 b-=1; mydistance=Math.sqrt(aima._x - aimb._x)*(aima._x - aimb._x)+(aima._y - aimb._y)*(aima._y - aimb._y); return(mydistance);2./最远点函数function farest(mygoods)var mygoods2var myreturnmygoods2=mygoods.split(|)var myfu=distance(mygoods20,0);var mysi=0;var myreturn;for(var i=0;i=myfu) myfu=distance(mygoods2i,0);mysi=i; myreturn=mygoods2mysi return(myreturn);/将地址传出去（3）首先将最远点在没有筛选条件下有（1）程序得到，然后有两点即可以和等待帅选点求出筛选点距中心线的角度，和三十度角（六十度的二分之一）进行比较，可以求出是否在规定扇区内。如若在既可以考虑此点，进行下一步。/i为等待筛选点，b为最远点，出发点已定，来确定i和出发点的夹角。function angel(i,b)var mya=distance(i,b); var myb=distance(0,i);var myc=distance(0,b);var mys=(myb*myb+myc*myc-mya*mya)/(2*myb*myc);var angel=Math.acos(mys); return(angel)（4）根据角度函数筛选出来扇形区域内的所有点，扇形角度暂定为60度，然后将扇区内所有否合要求的点找出来，这些点即为合理点，然后对这些点在下一步进行条件限制。/根据角度函数筛选出来扇形区域内的合理点，扇形角度暂定为60度function mychoice(b) var mysi; var mycho;var mylast; for(i=0;i+;i=50) if(angel(i,b)=bigangle/2) mysi=i;/加入分隔符，但最后一个数还是”|“ mycho+=String(mysi)+|; mycho=mycho.substr(0,mycho.length-1);/来去除最后个分隔符，用length函数来判断长度 mychomycho.length-1=;/这是筛选出的字符串。 return(mycho);（5）/筛选合适的点；function fit(mycho) var string2; var mystring; var mystring1; myb=sortvolumn(mycho); var myb1=myb.split(|); var myweight=goodsmyb1.weight; for(var i=0;imyb1.length;i+) if(mysum=1) mysum=mysum+myvolumni; mynum=i; /将满足体积条件的点传送到myvolumn1,点的个数即为mynum; myvolumn1i=myvolumni; for(var j=0;jmyvolumn1.length;j+) if(mysum1=50) mysum1=myweightj+mysum1; mynum1=j;/将超出限制的最重点逐一删除；while(mynum1mynum) for(var j=0;jmyvolumn1.length;j+)if(mysum1=50) mysum1=myweightj+mysum1; mynum1=j;myweight1j=myweightj; mydot=heaviest(myweight1);/用最重的函数，和baoremove来剔除掉限制条件外的点； string2=myvolumn1.baoremove(mydot); myum1=string2.length; /将超出限制的点剔除后，得到数组string2,开始加入点； var mysum3=0;var mysum2=0;var myweight3;var myvolumn3;for (var j=0;jstring2.length;j+) myweight3j=goodsstring2i.weight; myvolumn3j=goodsstring2i.volumn;/算出总的体积和重量； for(var i=0;istring2;i+) mysum3=mysum3+myweight3i; mysum2=mysum2+myvolumni; /将string2转化成字符串mycho=mycho.substr(0,mycho.length-1);； var string3;for(var j=0;jstring2.length;j+) string3+=Stringstring2j+|;string3=string3.substr(0,mycho.length-1);string3string3.length-1=;var k=0;while(mysum3+goodsk.weight=1&mysum2+goodsk=50) for(var m=0;mstring2.length;m+) if(k=stringm) break; string3=string3+k; return fit(string3);（6）下面的了两个小函数是对体积和重量的限制条件的筛选，由于后面的主函数要调用，先给出两个函数的程序。均在主构架函数中返还数值。/排列体积，传出体积由小到大的货物号的字符串！function sortvolumn(mycho) var mycho2=mycho.split(|); var myreal; var mysortedv; var mysortedv1; for(var j=0;jmycho2.length;j+) myrealj=goodsmycho2j.volumn; /让myreal的数组长度加一，目的是循环语句中myrealmys=1. myreal.length+=1; var mys=myreal.length-1; var myone=1;for(var k=0;kmyreal.length-1;k+) myrealmys=1; for(var i=0;imyreal.length-1;i+) if(myrealimyone) myone=myreali; mys=i; /将货物标号传递给数组mysorted中； mysortedvk=mys;mysortedv1=mysortedv.join(|);return(mysortedv1);/ 该函数返回最重的货物的编号function heaviest(myweight) var myweight1; var myweight2; var myzero=0; var myaddress; for(var i=0;ilength.myweight;i+) myweight1i=goodsmyweighti.weight; /引用sort.numeric var myweight2=myweight2.sort(sortNumber); myaddress=myweight2myweight2.length-1;return(myaddress)（7.）时间控制，此条件是在需要时间要求的条件下进行求解的。/时间排序函数function chooseline_1(string3)var mytime2=string3.split(|);for(var i=0;istring3.length;i+)mytime2i=goodsstring3i.time; for(var j=0;jstring3.length;j+) if(mytime2j=0) mytime2i=Number.MAX_VALUE； var myreal; var mysortedv; var mysortedv1; for(var j=0;jmytime2.length;j+) myrealj=goodsmycho2j.time; /让myreal的数组长度加一,目的是循环语句中 myreal.length+=1; var mys=myreal.length-1; var myone=50;for(var k=0;kmyreal.length-1;k+) myrealmys=1; for(var i=0;imyreal.length-1;i+) if(myreali;while(n!=0)for(var i=0;in;i+)linesi=linedistance(start,goodsnumi);var minmvar mindis=lines0for(var i=0;in;i+)if(linesi;else mychoose+=String(mystart);return(mychoose);（9）迪杰斯特拉算法： /离a最近的直接联通的点,s是不能包括的点，该函数服务于“迪杰斯特拉算法”function nearestgoods(a,s) var mym = new Array(4);var s2=s.split(|) /离a点距离最短的点的游标hvar m=0;var mymin;/先给mymin赋值（不能是S里面的数，也不能是自己本身）for(var j=0;j=aimnum;j+)/表示S中是否已有该点var existornot=not; for(var i=0;is2.length;i+)if(s2i=j) existornot=yes; break; /如果存在跳出本次J的循环 if(existornot=yes) continue; if(passaj=1 & a != j) mymin=distance(a,j); m=j; break; /判断是否存在最小值var nearby=no; if( mymin!=null) /找出最小值for(var j=0;j=aimnum;j+) /表示S中是否已有该点existornot=not; for(var i=0;is2.length;i+)if(s2i=j) existornot=yes; break;/如果存在跳出本次J的循环 if(existornot=yes) continue; if(passaj=1 & a!=j)nearby=yes if(distance(a,j)+String(b); else linere0=re3; while(re0!=b) re=nearestgoods(a,s); if(re0!=null) linere0=re3;s+=|+String(s2mins2minsign); if(re2=no) /去S中的值做循环 s2=s.split(|); var s2min = new Array(); for(var j=0;js2.length;j+) /开始=求s2j点到哪个点距离最小（要求S中不存在）var m=0;var mymin;for(var j4=0;j4=aimnum;j4+) if(pass(s2j,j4)=1 & s2j!= j4) mymin=distance(s2j,j4); if(mymin!=null)for(var j2=0;j2=aimnum;j2+) /表示S中是否已有该点 var existornot=not; for(var j3=0;j3s2.length;j3+) if(s2j3=j2) existornot=yes; break; /求该点最短距离 if(pass(s2j,j2)=1 & j2!=s2j & existornot=not) if(distance(j2,s2j)=mymin) mymin=distance(j2,s2j); m=j2; /结束=求s2j到哪个点距离最小/取得记录S2J的发散点中最短距离s2minj=m;s2mindisj=distance(m,s2j); var s2minsign=0; var s2minmin=s2mindis0; for(var i=0;is2.length;i+) if(s2mindisis2minmin) s2minmin=s2mindisi; s2minsign=i; s+=String(s2mins2minsign)+|; s=s.substr(0,s.length-1); re0=s2mins2minsign; lines2mins2minsign=s2minsign; /从B点出发，用LINE数组往回寻找A，从而得出B到A的最短距离var mystar = null;var myend=bmyfastway=String(b)+/翻转开始 （原来的myfastway是倒叙的，现在翻转字符串）myfastway2=myfastway.split(=)var myfastway3 = new Array(myfastway2.length);var mymax=myfastway2.length-1;for(var i=0;imyfastway2.length;i+) myfastway3i=myfastway2mymax; mymax=mymax-1; myfastway=null;for(i=0;i/翻转结束 return(myfastway);（10.）架构函数，利用以上的小函数根据不同的限制条件，调用不同的函数进行求解。（index.html的代码）2010年数学建模题B/定义目的地的个数varaimnum=50;/定义扇形角度大小varbigangel=60;/货物员行驶速度（米/小时）varspeed=24*1000;/架构函数sendgoods为需要配送的货物，limit为决策条件：0无时间限制，1有时间限制functionindex(sendgoods,limit)/重要变量/需要发送的全部物品varallsendgoods;/货物的目的地集合varallaim/剩余的货物的目的varrestaim/最远点varfarestpoint;/需要发送的物品中，按照最远点和扇形原则，选择点varmychiocestr;/该扇形中可以一次带走的点varsendnow;/物品的发送路线varsendline;/路线具体行走方法varlinedetail;/路线长度varlinelength=0;/路线时间花费时间varlinetime;/定义扇区个数varhowmany=0;/辅助变量/物品的发送路线的数组varsendline2;/路线具体行走方法的数组varlinedetail2;/初始化allsendgoods=sendgoods;restsendgoods=allsendgoods;/需要发送的货物中需要经过的目的集集合restaim=chooseaim(restsendgoods)document.write(解决方案如下：);while(restaim.length!=0)howmany+=1farestpoint=farest(restaim);mychiocestr=mychoice(farestpoint,allsendgoods);sendnow=fit(mychiocestr);restaim=rest(restaim,sendnow);/判断决策条件if(limit=0)sendline=chooseline_0(mygoods);elseif(limit=1)sendline=chooseline_1(mygoods);sendline2=sendline.split(=)for(vari=1;i;linedetail=linedetail.substr(0,myb2.length-2);linedetail2=linedetail.split(|);for(vari=1;ilinedetail2.length;i+)linelength+=distance(linedetail2i-1+linedetail2i);document.write(送货路线：+String(linedetail)+);document.write(总路程（单位：米）：+String(round(linelength)+);document.write(总时间（单位：分钟）：+String(round(mytime(linelength)+);return(false); 点击查看解决方案：3.寻找最优解：（