最短路径模型

订-线第十一届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目(B)题密封号2010年5月4日剪切线密封号2010年5月4日机电工程学院第队队员1队员2队员3姓名叶鑫林冯士恒李栋班级040831640408311504083018送货路线设计问题提纲：1提出问题；模型分析和简单摘要；模型假设；符号设定；模型建立和求解；模型评价和建议；7附录：程序以及结果。1. 提出问题|：现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的0点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制（包括前30件货物），现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。以上各问尽可能给出模型与算法。我们的核心算法就是迪杰斯特拉算法，我们自己基于javascript编写的。2. 模型分析和摘要：本文将货点实体间的线路选择抽象为图论最短路模型采用0-1整数规划表述。建立直达数据库C作为数据基库，根据用户需求建立不同目标的0-1规划模型运用蚁群算法与迪杰斯特拉算法分别求解，最终方案即通过多限制条件下用javascript编程得到最优效果输出。第一问属于典型VR问题，在数据处理阶段发现载重和体积均符合要求，总量不多于五十公斤，体积不大于单位1,不用考虑这两方面限制条件，所以可以解决但是实际生活中可能出现有限制的条件，所以为了严谨我们考虑了限制条件。先建立站点至站点直达数据库Q来描述两两可直达站点的所有线路，用到时，系统首先查询Q,得到所有直达方案。由于三问都是类似条件下的VRPT问题，所以我们之间利条件最强的模型，针对各问对约束条件的弱化和强化程度分别调用。建立模型，用迪杰斯特拉算法的衍生算法为核心来做，结合多个限制条件选出最优解。对于各个小函数及用途在后面说明。为了能够为用户提供多种备选方案，我们首先使用基于迪杰斯特拉算法求解，得到不同目标下的多种优化方案；然后用限制条件求得全局最优解；两种方法求解步骤见后文，其中解决方案为解决方案如下：送货路线：0=18=13=19=24=27=34=40=45=42=49=42=43=38=35=32=23=17=14=2仁36=3仁27=26=0=总路程（单位：米）：53567花费时间（单位：分钟）：223两种求解方法的优劣在后文中给出了详细评价。第二问考虑有了时间限制，新的限制条件在模型一中，所以可以继续用模型以来求解，而模型一中的时间限制为软限制，既符合实际条件，也符合题目中的要求。结合实际，提出了本文的研究问题一有时间窗的送货员路径问题（VRPTW，建立了以送货员容量和客户需求等为约束条件，以配送运输成本为目标函数的VRPT数学模型。在软限制条件下的求解，因为实际情况下很难让所有人都满意，所以决策上只能找最优解，可以根据客户的重要程度权衡可以允许的延误程度，在服务成本及客户满意度之间找到一个较为理想的平衡点。有软时间窗的VR允许发生延误，但对延误发生的程度和频率有一定限制，这主要通过对延误的惩罚程度来体现的。在建模时表现为目标函数增加了一项惩罚项，造成目标函数值的增加。第二问答案为：解决方案如下：送货路线：0=18=13=19=24=27=34=40=45=42=49=42=43=38=36=3仁39=3仁36=38=35=32=23=17=14=2仁26=0总路程（单位：米）：61459第三问因为时间有限，程序过于复杂且难于调试，故没有求出最优方案。Pi(Si):惩罚函数。若送货员在Eti前到达i，或送货员在LTi之后到达，则服务延误，需支付一定的罚金，因此p*(Si)；设定如公式(3一8)所示Pi(Si)=ai(Eti-Si),SiETiPi(Si)=0,EtiSiLtiai,bi为惩罚系数，对某些重要的顾客或者对时间要求比较苛刻的顾客可能很大。第三问完全符合模型一，只是少了时间窗，即要求最大可能满足(体积和重量必须严格满足)的情况下路程最短。对于惩罚堵措施，由于时间关系没做出来程序，但我们觉得这个很有必要，对公司的信誉度以及顾客的满意程度都有很大的作用。最后我们给出了送货员路径问题的一些想法和建议，并提出了改进方案。3. 关键字：货物运送蚁群算法迪杰斯特拉算法送货员路径问题VRPTWjavascript模型假设：1. 送货员的服务质量一直相同；2. 城市的交通没有负担，不会在路上耽误时间；3. 被配送的物资可混装，不能混装需单独处理；4. 流通中心有足够的物资可配送；5. 满足所有任务点的品种、数量、规格需求；6. 各配送路线的货物量不得超过送货员容积和载重量，否则将会受罚；7. 接货点不会耽误送货员的时间；8. 送货员中途不会发生意外或者突发事件；9. 每一个客户的时间不是特别严格，允许出现一定概率的突发事件；10. 送货员在选好目的点之后会按照选出的最短路径走；4. 顾客不会因为提前货物到达而责怪送货员，是送货员的信誉度降低；符号的约定：(1)对于蚁群算法变量和参数符号按如下定义：令G-(V，E)为一无向图，V表示顶点集，E为边集，顶点V1，V2,V3，,Vn为客户，V)吃饭吃菜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，否则，其值为05. Eti,Lti:ETi，LTi为客户i的时间窗口，其中，Eti是客户要求到货时间段的始点，Lti是客户要求到货时间段的终点；模型建立和模型求解:（1）数据分析:1.通过对货物点坐标的分析，所有的货物点坐标都在X坐标（0-16000）和丫坐标（0-16000），且都在以O点为坐标的圆中；2每一个货物的重量都小于五公斤，且体积都小于单位一；3.位置关系表都明确，且两点之间均可到达；由以上分析，建立本文所要解决的目标函数：约束条件：minZ二刀刀CXj刀(di刀Xij)qaiwSiwbi刀Xij=1(i刀X0j=1刀Xih-(i=1,2,3.nnj=1,2,3.n)(hn,i(j=1,2,3Xhj=0VRPTW数学模型如下：,.n;j=1,2,3,n)(3-2)(3-3).n)(3-4)(3-5)j=1,2,3n,i=1,2,3,.n)(3-7)(I,jn)n)(3-8)(3-9)要是车载，用户并且送货员不能超过送货员的最大容量（3一3），除此之外，每个用户只能也仅只被一个送货员所服务一5）一（3一7）确保每个过程都从节点服务完用户i后仍然有时间赶上用户j（2）模型求解：1.问题一：本问题主要讨论迪杰斯特拉算法在时间窗的开始时间和最晚时间。VRPTWfi个可行解要服务于所有的2）或者是送货员的时间限制（3（3一4），等式（30开始，截止于节点N+l;（38）表示在每次送货员都是从0点开始走。VRPTWS应用，综合以最远点为核心的最(3-6)刀Xi,n+1=1Sj+tij-K（1-xij）wSjXj（0,1）（i,j问题的目标是求总的送货员路径路程的最小值（3一1），约束条件主短路径法，多限制条件下的最优解法，在载重。体积和时间限制下的最短路径,然后综合蚁群算法对以上算法进行比较O路径最短且最优，行程载重和体积携带量最合适；。惩罚度措施合适；O求得最优解；基于此，问题共分为四个部分：数据处理，将每个货物的质量体积和时间窗以及货物点是否直达用表格给出；对于具体的数据进行分扇区处理，角度寻求最优解，然后在每一个扇区中寻找最远点，然后在时间窗优先的条件下，对重量和体积进行筛选；1. 所有路径点确定之后，用迪杰斯特拉算法寻找最优路径；2. 综合蚁群算法进行比较迪杰斯特拉的算法。1.数据处理：因为给的是货物运送点以及目的地的坐标位置，以及目的地之间是否直达，所以制成表格之后在附录中附有。通过在程序中建立关系对应表，把位置点和对应的坐标写出来。2具体分析：由于三个问题具有统一特征，所以我们只建立了一个模型，只是在这个模型中条件被要求的多少不同，既可以对某些条件弱化或者不考虑，综上，所以将各个小函数的用途先表示出来：(1.)首先对图中所有的坐标进行距离筛选，根据坐标由二次关系比较求出图中最远的点，然后将这个点的地址传出去，思想即为以此点和O点为中心线，建立扇区(扇区的确定在下个函数中体现)，然后进行筛选。1./算两点,两点(忽略是否联通)返回之间距离，否则返回-1functiondistance(a,b)varmydistancea-=1b-=1;mydistance=Math.sqrt(aima._x-aimb._x)*(aima._x-aimb._x)+(aima._y-aimb._y)*(aima._y-aimb._y);return(mydistance);2. /最远点函数functionfarest(mygoods)varmygoods2varmyreturnmygoods2=mygoods.split(|)varmyfu=distance(mygoods20,0);varmysi=0;varmyreturn;for(vari=0;i=myfu)myfu=distance(mygoods2i,0);mysi=i;myreturn=mygoods2mysireturn(myreturn);/将地址传出去(3)首先将最远点在没有筛选条件下有(1)程序得到，然后有两点即可以和等待帅选点求出筛选点距中心线的角度，和三十度角(六十度的二分之一)进行比较，可以求出是否在规定扇区内。如若在既可以考虑此点，进行下一步。i为等待筛选点，b为最远点，出发点已定，来确定i和出发点的夹角。functionangel(i,b)varmya=distance(i,b);varmyb=distance(0,i);varmyc=distance(0,b);varmys=(myb*myb+myc*myc-mya*mya)/(2*myb*myc);varangel=Math.acos(mys);return(angel)(4)根据角度函数筛选出来扇形区域内的所有点，扇形角度暂定为60度，然后将扇区内所有否合要求的点找出来，这些点即为合理点，然后对这些点在下一步进行条件限制。/根据角度函数筛选出来扇形区域内的合理点，扇形角度暂定为60度functionmychoice(b)varmysi;varmycho;varmylast;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)/筛选合适的点；functionfit(mycho)varstring2;varmystring;varmystring1;myb=sortvolumn(mycho);varmyb1=myb.split(|);varmyweight=goodsmyb1.weight;for(vari=0;imyb1.length;i+)if(mysum=1)mysum=mysum+myvolumni;mynum=i;/将满足体积条件的点传送到myvolumn1,点的个数即为mynum;myvolumn1i=myvolumni;for(varj=0;jmyvolumn1.length;j+)if(mysum1=50)mysum1=myweightj+mysum1;mynum1=j;/将超出限制的最重点逐一删除；while(mynum1mynum)for(varj=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,开始加入点；varmysum3=0;varmysum2=0;varmyweight3;varmyvolumn3;for(varj=0;jstring2.length;j+)myweight3j=goodsstring2i.weight;myvolumn3j=goodsstring2i.volumn;/算出总的体积和重量；for(vari=0;istring2;i+)mysum3=mysum3+myweight3i;mysum2=mysum2+myvolumni;/将string2转化成字符串mycho=mycho.substr(0,mycho.length-1);；varstring3;for(varj=0;jstring2.length;j+)string3+=Stringstring2j+|;string3=string3.substr(0,mycho.length-1);string3string3.length-1=;vark=0;while(mysum3+goodsk.weight=1&mysum2+goodsk=50)for(varm=0;mstring2.length;m+)if(k=stringm)break;string3=string3+k;returnfit(string3);(6)下面的了两个小函数是对体积和重量的限制条件的筛选，由于后面的主函数要调用，先给出两个函数的程序均在主构架函数中返还数值。/排列体积，传出体积由小到大的货物号的字符串！functionsortvolumn(mycho)varmycho2=mycho.split(|);varmyreal;varmysortedv;varmysortedv1;for(varj=0;jmycho2.length;j+)myrealj=goodsmycho2j.volumn;myrealmys=1./让myreal的数组长度加一，目的是循环语句中myreal.length+=1;varmys=myreal.length-1;varmyone=1;for(vark=0;kmyreal.length-1;k+)myrealmys=1;for(vari=0;imyreal.length-1;i+)if(myrealimyone)myone=myreali;mys=i;/将货物标号传递给数组mysorted中；mysortedvk=mys;mysortedv1=mysortedv.join(|);return(mysortedv1);/该函数返回最重的货物的编号functionheaviest(myweight)varmyweight1;varmyweight2;varmyzero=0;varmyaddress;for(vari=0;ilength.myweight;i+)myweight1i=goodsmyweighti.weight;/引用sort.numericvarmyweight2=myweight2.sort(sortNumber);myaddress=myweight2myweight2.length-1;return(myaddress)(7.)时间控制，此条件是在需要时间要求的条件下进行求解的/时间排序函数functionchooseline_1(string3)varmytime2=string3.split(|);for(vari=0;istring3.length;i+)mytime2i=goodsstring3i.time;for(varj=0;jstring3.length;j+)if(mytime2j=0)mytime2i=Number.MAX_VALUE；varmyreal;varmysortedv;varmysortedv1;for(varj=0;jmytime2.length;j+)myrealj=goodsmycho2j.time;/让myreal的数组长度加一,目的是循环语句中myreal.length+=1;varmys=myreal.length-1;varmyone=50;for(vark=0;kmyreal.length-1;k+)myrealmys=1;for(vari=0;imyreal.length-1;i+)if(myreali;while(n!=0)for(vari=0;in;i+)linesi=linedistance(start,goodsnumi);varminmvarmindis=lines0for(vari=0;in;i+)if(linesi;elsemychoose+=String(mystart);return(mychoose);(9)迪杰斯特拉算法：/离a最近的直接联通的点,s是不能包括的点，该函数服务于“迪杰斯特拉算法”functionnearestgoods(a,s)varmym=newArray(4);vars2=s.split(|)/离a点距离最短的点的游标hvarm=0;varmymin;II先给mymin赋值(不能是S里面的数，也不能是自己本身)for(varj=0;j=aimnum;j+)II表示S中是否已有该点varexistornot=not;for(vari=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;判断是否存在最小值varnearby=no;if(mymin!=null)II找出最小值for(varj=0;j=aimnum;j+)II表示S中是否已有该点existornot=not;for(vari=0;is2.length;i+)if(s2i=j)existornot=yes;break;如果存在跳出本次J的循环if(existornot=yes)continue;if(passaj=1&a!=j)nearby=yesif(distance(a,j)+String(b);elselinere0=re3;while(re0!=b)re=nearestgoods(a,s);if(re0!=null)linere0=re3;s+=|+String(s2mins2minsign);if(re2=no)/去S中的值做循环s2=s.split(|);vars2min=newArray();for(varj=0;js2.length;j+)II开始=求s2j点到哪个点距离最小(要求S中不存在)varm=0;varmymin;for(varj4=0;j4=aimnum;j4+)if(pass(s2j,j4)=1&s2j!=j4)mymin=distance(s2j,j4);if(mymin!=null)for(varj2=0;j2=aimnum;j2+)I表示S中是否已有该点varexistornot=not;for(varj3=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);vars2minsign=0;vars2minmin=s2mindis0;for(vari=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的最短距离varmystar=null;varmyend=bmyfastway=String(b)+/翻转开始(原来的myfastway是倒叙的，现在翻转字符串)myfastway2=myfastway.split(=)varmyfastway3=newArray(myfastway2.length);varmymax=myfastway2.length-1;for(vari=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;1有时间限制/架构函数sendgoods为需要配送的货物，limit为决策条件：0无时间限制，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. 寻找最优解：（1）迪杰斯特拉算法简介：首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D3=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为竝显然，长度为Dj=MinD|viV的路径就是从v出发的长度最短的一条最短路径。此路径为（v,vj）。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是（v,vk），或者是（v,vj,vk）。它的长度或者是从v到vk的弧上的权值，或者是Dj和从vj到vk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧（v,x），或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是Dj=MinD|viV-S其中，D或者是弧（v,vi）上的权值，或者是Dk（vkS）和弧（vk,vi）上的权值之和。迪杰斯特拉算法描述如下：1）arcs表示弧上的权值。若不存在，则置arcs为在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcsLocateVex(G,v),iviV2)选择vj,使得Dj=MinD|viV-S3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。(2)最优解的获得：通过各问对货物运送问题限制条件的强弱不同，调用不同的小函数来对条件进行限制，以求得最优解4对算法进行比较迪杰斯特拉算法的原理已经在上面说明，优越度也是很明显的，对于蚁群算法，来源于对蚂蚁群体搜索行为的追踪研究，其基于信息索的正反馈特性有助于快速找到最优解，但蚁群算法也有不足之处，主要表现在当问题和规模较大时，容易陷入局部最优化而导致算法过早停滞。所以各有优点。6. 模型检验和评价:物流配送中，送货员的服务质量取决于用户的满意程度，基于迪杰斯特拉算法的寻求最优解问题是在重量体积综合限制条件下的解决方法。有时间窗的VRP问题简称为VRPTW(vihicleRoutingProblemwithTimewindows)，它是在VRP的基础上提出的，一般可定义为：:对于一系列货物需求点(或称客户)，己知每个客户的需求量及位置，用多个送货员从配送中心到达这批客户。要求必须在其时间窗内为每个客户服务，如果送货员提前到了客户所在地，也必须等待，直到被允许为该客户服务为止或者向本题中的软时间限制，只要在要求时间前到达就行了。每个送货员的载重量一定，每条线路不超过该车的载重量送货员。每个客户的需求必须且只能由送货员来提供。目标是使总的送货员行走距离和所需的送货员数目最小。这里，将货员行走距离作为第一目标，货员为第二目标。对于本题而言送货员限制不存在，即只要一名。基于上面的方法，在各种筛选条件中选出最优解。在物流问题中应用最广的还是蚁群算法，但通过我们研究认为对于多目标的配送问题，更适合于用迪杰斯特拉来寻找短径的最优解。这对实践生活有很大的意义和帮助。附录：附录sorlvolumnjsJScriptScript立丄牛695字节mychiotejJScriptScript文件505字节Imedhtance.jsJScriptSeript文井326宇节heaviestjsJScriptScript文畔mso字书fJScriptScript丈悴t.ggkbJScriptScript文件3.94KBchoo&eline_l.j5JScriptScript交逬卿字节baoremovejsJSenptScript立件1S6李帀farestjaJScriptScript立件3S4宇节dijkstrdjsJScriptScript文彳牛4.20KBdistarcejsJSei；ptScript艾J吐2B1字节data3.j$JScriptScript文件1.43KBchoo5eline_0.jsJScriptScript丈I二&91字节angeljsJScriptScript立件238枣话datal.jsJScriptScript文萍4.76K6j-纶吐启JScriptScript文件4M字节index.htmtChromeHTMLDocument3.57KB1.文件安排格局解决方案如下；送货路线：0=13=13=19=24=27=34=40=45=42=49=42=43=38=35=32=23=17=14=21=36=31=总路程（单位.米八53567花费时间（单也分钟）：223点击查看M决方案第一题第二题第三题2.第一题运行截图解决珈下1送货路线:0=18=13=19=24=27=34=40=45=42=49=42=43=38=36=31-39=31=36=38=35=32-总程单位.米:61459花费时间(单毎分钟厂303点击査看解决方案：第一题第二题第三超3.第二题运行截图附录二：l.datal.jsvargoods=newArray(101);MyStruct=function(n,a,w,v,t)this.n=n;this.aim=a;this.weight=w;this.volumn=v;this.time=t;functionInputdata(n,a,w,v,t)goodsn=newMyStruct(n,a,w,v,t);Inputdata(1.0000,13.0000,2.5000,0.0316,9.0000);Inputdata(2.0000,18.0000,0.5000,0.0354,9.0000);Inputdata(3.0000,31.0000,1.1800,0.0240,9.5000);Inputdata(4.0000,26.0000,1.5600,0.0350,12.0000);Inputdata(5.0000,21.0000,2.1500,0.0305,12.0000);Inputdata(6.0000,14.0000,1.7200,0.0100,12.0000);Inputdata(7.0000,17.0000,1.3800,0.0109,12.0000);Inputdata(8.0000,23.0000,1.4000,0.0426,12.0000);Inputdata(9.0000,32.0000,0.7000,0.0481,12.0000);Inputdata(10.0000,38.0000,1.3300,0.0219,10.2500);Inputdata(11.0000,45.0000,1.1000,0.0287,9.5000);Inputdata(12.0000,43.0000,0.9500,0.0228,10.2500);Inputdata(13.0000,39.0000,2.5600,0.0595,12.0000);Inputdata(14.0000,45.0000,2.2800,0.0301,9.5000);Inputdata(15.0000,42.0000,2.8500,0.0190,10.2500);Inputdata(16.0000,43.0000,1.7000,0.0782,10.2500);Inputdata(17.0000,32.0000,0.2500,0.0412,12.0000);Inputdata(18.0000,36.0000,1.7900,0.0184,12.0000);Inputdata(19.0000,27.0000,2.4500,0.0445,12.0000);Inputdata(20.0000,24.0000,2.9300,0.0420,9.0000);Inputdata(21.0000,31.0000,0.8000,0.0108,9.5000);Inputdata(22.0000,27.0000,2.2500,0.0018,12.0000);Inputdata(23.0000,26.0000,1.5700,0.0210,12.0000);Inputdata(24.0000,34.0000,2.8000,0.0103,9.5000);Inputdata(25.0000,40.0000,1.1400,0.0155,9.5000);Inputdata(26.0000,45.0000,0.6800,0.0382,9.5000);Inputdata(27.0000,49.0000,1.3500,0.0144,10.2500);Inputdata(28.0000,32.0000,0.5200,0.0020,12.0000);Inputdata(29.0000,23.0000,2.9100,0.0487,12.0000);Inputdata(30.0000,16.0000,1.2000,0.0429,12.0000);Inputdata(31.0000,1.0000,1.2600,0.0250,0);Inputdata(32.0000,2.0000,1.1500,0.0501,0);Inputdata(33.0000,3.0000,1.6300,0.0483,0);Inputdata(34.0000,4.0000,1.2300,0.0006,0);Inputdata(35.0000,5.0000,1.4100,0.0387,0);Inputdata(36.0000,6.0000,0.5400,0.0067,0);Inputdata(37.0000,7.0000,0.7000,0.0129,0);Inputdata(38.0000,8.0000,0.7600,0.0346,0);Inputdata(39.0000,9.0000,2.1400,0.0087,0);Inputdata(40.0000,10.0000,1.0700,0.0124,0);Inputdata(41.0000,11.0000,1.3700,0.