B题：送货线路设计问题答卷

12013201320132013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西安财经学院参赛队员(打印并签名)：1.李云2.李鑫3.刘莎莎指导教师或指导教师组负责人(打印并签名)：张娟日期：2013年7月8日赛区评阅编号（由赛区组委会评阅前进行编号）：22013201320132013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：3送货路线设计问题摘要本文是有关送货员送货路线优化问题，即在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限，确定业务员的最佳运行路线策略可以转化为在遍历所有要送达货物节点的前提下，使总路程最小。并总结出一些在这类图中求解近似最优回路的有效法则.问题一：将1~30号货物送到指定地点并返回，用Floyd算法迭代出任意两点最短路的距离矩阵，并将原来的图构造成完全图，利用floyd算法和用二边逐次修正法求解Hamilton圈，构造最优Hamilton回路，设计出最快完成路线与方式，得出结果。问题二：基于问题一的求解，再考虑时间优先的原则，将所有货物送达点进行分块分组，即优先送达时间要求紧的货物，利用穷举法列举出每一块中货物送达点的任意排列顺序，求最快送货路线，且按照送货时间的顺序，将前一个区域送完的最后一处位置作为后一个区域的起始位置来求解。求出其中耗时最短的路线即为所需结果。问题三：考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。由于货物重量和体积的限制，送货员需中途取货。我们利用excel和spss数据分析，对数据的聚散进行分析后，对运输地点进行分区，分为三个区后利用floyd算法和用二边逐次修正法构造最优Hamilton回路。关键字：关键字：关键字：关键字：FloydFloydFloydFloyd算法算法算法算法最优最优最优最优HamiltonHamiltonHamiltonHamilton回路回路回路回路穷举法穷举法穷举法穷举法TSPTSPTSPTSP模型模型模型模型4一．问题重述在物流行业中，送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方。现有一快递公司，一送货员要按图1中的路径需将货物送至城市内多处，要求设计送货方案，使所用时间最少。假定送货员只能沿图中那些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。每件货物交接花费3分钟，并假定，同一地点有多件货物按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。不考虑中午休息时间。二．问题分析对于送货员从快递公司库房O点出发将货物送到城市内制定地点问题，可以转换为图论中的最短路径求解问题，我们将城市内的各送货地点看做是图中的顶点，各地点之间送货所需的时间看做是该边上的权值，由题目表3所给的各地点之间的联通性构建无向图。对于问题一，要求送货员以最快的方式将1~30货物送达指定的地点并返回。因此，可以构造最优Hamilton回路进行求解。对于问题二，要求送货员从早上8点出发，将货物在指定的时间内以最快的方式送达目的地，由题目已知可以根据时间将1~30号货物所对应的地点分为4块，即8：00至9:00、9:00至9:30、9:30至10:15、10:15至12：00四个时间段。再对每个时间段内的送货地点进行穷举，得到最佳路径，评价各个时间段的结果。对于问题三，在不考虑送货时间限制的情况下，将体积与重量两个因素考虑在内，允许送货员可以往返取货，要求送货员以最快的方式将货物送达指定地点5并返回。由于所有物体的总重量是148公斤，总体积为2.98立方米，送货员的最大载货量为50公斤，最大载货体积为1立方米，所以送货员会往返三次取货，因此可以将所有的送货地点分为三块。人为的分块，直至达到送货员的最大载货量；得出分析结果。三．模型假设1．假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；2．在连通线路中业务员可以任意选择路线；3．假设送货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；4．假设送货员的速度保持匀速，即保持24公里/小时，不考虑堵车，发生意外等现象；四．符号说明Wi第i个货物的重量（xi，yi）i的送货点的坐标Vi第i个货物的体积C送货路线总路程t送货所用总时间G=(V,E)赋权连通图GiG=(V,E)的第i个子图iL子图iG中的最佳回路()eω边e的边权()vω点v的点权iliL的各边权之和ieiL的各点权之和dij最短路径的权为叙述方便起见，我们在文中不加说明地使用上述变量和符号的变形形式，6它们的含义可以通过上下文确定.五．模型的建立与求解1.问题一模型的建立与求解5.1.1模型一的建立：把快递公司送货地点示意图抽象为一赋权连通图G=(V,E)，在权图G中，Vi∈V(G)对应示意图中的快递公司地点及货物送达点，v0表示快递公司所在地，je∈E(G)对应示意图中路径.边权()jeω∈对应示意图中的路径长度.建立的数学模型如下：{}0(),(),(G),(),eEGeNvVvTVvVωω∀∈∃∈∃∈∃∈×∈求G中回路L1,L2,...Lk(k1)使得满足：（1）0(),1,2,,;ivVLik∈=⋯（2）1()();kiiVLVG==∪（3）1()()min(inieELeω=∈=∑∑目标为总距离最短）或1()()max()()min(iijkeELeVLevωω≤≤∈∈⎧⎫⎪⎪+=⎨⎬⎪⎪⎩⎭∑∑目标为时间最短为了讨论方便，先给出图论中相关的一些定义.定义1经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton圈.定义2在加权图G=(V,E)中(1)权最小的哈米顿圈称为最优Hamilton圈；(2)经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找TSP回路的问题.TSP回路的问题可转化为最佳Hamilton圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’)，E′中每条边(,)xy的权等于顶点x与y在图中最短路径的权，即111min{,}mmmmijimmjijdddd−−−=+7在图论中有以下定理：定理1加权图G的送货员回来的权和G′的最佳Hamilton圈的权相同；定理2在加权完备图中求最佳Hamilton圈的问题是NPC问题.在解决问题的过程中，我们用到以下算法：1.算法一（Floyd算法）：令Dn表示一个NN×矩阵，它的(,)ij元素是mijd．（1）将图中各顶点编为1,2,,N⋯．确定矩阵D0，其中(,)ij元素等于从顶点i到顶点j最短弧的长度(如果有最短弧的话)．如果没有这样的弧，则令0ijd=∞．对于i，令00ijd=．（2）对m=1,2,...N，依次由Dm-1的元素确定Dm的元素，应用递归公式111min{,}mmmmijimmjijdddd−−−=+．每当确定一个元素时，就记下它所表示的路．在算法终止时，矩阵Dn的元素(i,j)就表示从顶点i到顶点j最短路的长度．2.算法二：求加权图G=(V,E)的TSP问题回路的近似算法：（1）用算法一（Floyd算法）求出G=(V,E)中任意两个顶点间的最短路，构造出完备图G=(V,E)，(,),(,)min(,)GxyExydxyω′∀∈=；（2）输入图G′的一个初始Hamilton圈；（3）用对角线完全算法产生一个初始Hamilton圈；（4）随机搜索出G=(V,E)中若干个Hamilton圈，例如2000个；（5）对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；（6）在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.5.1.2模型一的求解：（1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下：8各点位置与连通情况图（2）根据已知各点坐标，由两点间距离公式221212()()dxxyy=−+−求得图中相邻连通点间的距离如下表1（见附表）。问题一要求将1—30号货物送到指定地点并返回，不考虑各货物的送达时间，考虑到30048.550iiW==∑，且3000.881iiV==∑，故不用考虑重量、体积对送货次数的影响，即只需一次送货，无需中途返回取货.方法：Floyd算法+二次逐项修边法（1）由表1中的数据，做出图G(V,E)的邻接矩阵A(0)，根据Floyd算法，求得任意两点间的最短距离A(50);（2）经过分析，发现运送1~30号货物只涉及22个点（含v0），由于其中21个送货点中有5个含2货物，2个含3货物；（3）将这22个顶点令为点集Xi={(ai,bi)，i=0,1,2,...,21}令矩阵B为仅含有Xi点的最短距离方阵，构成加权图完备图G’=(V,E’);905296509474933621218217975395470913923997292967075254467762155777688597518833786011722529608456110638916311470921069157146688628552171200375428489100268065917313562126451167115534509484560260821965342329739708806548980937026528293506177771498731098111250103339359132227493110632608038727950569620981120578889675942534101175074715933114541338094698552106531144136218916219638720580318241775733340166620555330867877470456108400950891468229788711118218231145342795058030397975773884357431712104888944285375691349516059104499531855812420179770923297569618243979035985509219247973