送货线路设计问题标准答案

14送货路线设计问题的答案1、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。15要求标出送货线路。3若不需要考虑所有货物送达时间限制包括前30件货物，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。2、问题分析送货路线问题可以理解为已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。3、模型假设与符号说明1631、模型的假设（1）、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物（2）、要求达到不超过的时间不包括此次在该点交易的时间。（3）、所用的距离数据都精确到米而时间则精确到00001H（4）、同一地点有多件货物也简单按照每件3分钟交接计算。32、符号说明其中I，J1、2、350并且M50KGV134、模型的建立及求解模型一模型二模型三模型四最短路径模型图的遍历模型多区域最短路多阶段最短路17模型一11模型的建立我们为了求出各个点的之间的最短的路径，使用DIJSTRA算法求解。DIJKSTRA算法是图论中非常有名的一个算法。图采用邻接矩阵的形式描述，W（I,J）表示结点I到结点J间的最短距离，如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据代替（如MATLAB中的INF）。但DIJKSTRA算法只能求出从结点I到其它各结点的最短路径。算法引入这样两个集合S和T，S是那些已经确定了到I结点的最短路径的结点，T为全集U和S的差集，即那些还未确定最短路径的结点。而且S的初值是I，T的初值是UI。另外再引入一个标记数组DN，其中在某一步DK表示当前从I到K的较短路径，DK的初值为W（I，K）。整个算法过程如下、在T中选择一个DK最小的结点K，将K并入S，并从任意两点之间的最短路距离由起始点遍历路径回到原点多区域无返回起点的最短路多阶段有返回起点的最短路18T中去掉，如果T为则转到；、用K结点和T中其余结点进行一遍比较，如果DIDKMKI，则用DKMKI取代原来的DI，重复；、算法结束，此时DK中保存的就是从I到K结点的最短路径。算法就以这样非常简单的形式完成了求解，时间复杂度是ON2，确定了从I到其余各结点的最短路径。12模型的求解根据算法和相邻的点的距离可以用DIJKSTRA求出任意两点的最短路径。19图1相邻的点的距离使用循环的结构求出150各个点之间的最短距离。程序1见附录21可以求出W和AA为最短路径是的所过的的地点如从O开始到其余50个点的A0074831511812141813131821122321024220291731190313025222623283138214036273437433841364140464240要从O点到16点则要先到23即02316要从O点到23点则要先到17即0172316要从O点到17点则要先到21即021172316而O可以直接到21所以从0到16的最优路径是021172316最短的距离是W（0,16）7493M模型二对于问题一的求解21模型的建立由前30件货物可以到达的地点可以知道I，J13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。20图2需要达到的点（红点标注的）其中共经过21个点，运送30件货物该30件货物473KG1，到45点时必须在9点半之前到达而1741215故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。目标函数V0约束条件是T到个点的时间最大值32模型的求解25图44个阶段的圈图对四个阶段分别求出到达的时间，由程序4（附录24）可知分4个阶段1从0出发经过13、18到24。满足TLUWU,ILILUWU,IZIUENDENDENDENDLLLFORI1NFORJ1KIFISJLLILLIELSELLIINFENDENDENDLVINFFORI1NIFLLI50|V1BREAKENDNIXXT1DISPT1,M,VA,TINFENDSUMSUMVP,1DISP顺序为DISPX,0DISP总路程是64DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP第二阶段P1X0M0V0A,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKENDNN1PTXXT1DISPT1,M,VA,TINF65ENDDISP顺序为DISPX,0DISP总路程是DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP第三阶段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKEND66PTXXT1DISPT1,M,VA,TINFNN1ENDSUMSUMVP,1DISP顺序为DISPX,0DISP总路程是DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP第四阶段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,267VVWT1,3SUMSUMSIFM50|V1BREAKENDPTXXT1A,TINFNN1ENDSUMSUMVP,1DISP顺序为DISPX,0DISP总距离是DISPSUMTSUM/1000/243I/60DISP总时间是DISPT26、问题三的优化CLCCLEARALLLOADWTXTAWLOADXTXTWX68P1X0M0V0SUM0VAA,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSPTIFM50|V1BREAKENDNIXXT1DISPT1,M,VA,TINFENDSUMSUMVP,1DISP顺序为69DISPX,0DISP总路程是DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP第二阶段P1X0M0V0A,PINFFORI150S,TMINAP,MMWT1,2VVWT1,3SUMSUMSIFM50|V1BREAKENDNN1PTXXT170DISPT1,M,VA,TINFENDSUMSUMVP,116304SUMSUMVP,1DISP顺序为DISPX,0DISP总路程是DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP第三阶段P1X0M0V0A,PINFFORI150NS,TMINAP,MMWT1,2VVWT1,3SUMSUMS71IFM50|V1BREAKENDPTXXT1DISPT1,M,VA,TINFNN1IFT46BREAKENDENDSUMSUMVP,1SUMSUMVP,1DISP顺序为DISPX,0DISP总路程是DISPSUMTSUM/1000/243I/60DISP所用时间是DISPTDISP