数学建模——邮件送递问题

1、邮件送递问题【摘要】本文的主要思想，是将邮件送递问题转化为图论中的旅行商问题，求最佳哈密尔顿回路，在此基础上，结合重量、体积、时间这三个约束条件，对送递路线进行调整，找到最佳的送递路线。问题一，用Floyd算法计算51个地点任意两点之间的最短距离，然后采用二边逐次修正法求21个送达地点构成的最佳H圈。为减小二次逐边修正法对初始圈的敏感，每次随机搜索1000个初始圈。为提高计算速度；我们采用在MATLAB环境中，用矩阵翻转的方法来实现二边逐次修正的过程。最终我们求得序号分别为3和150的两条总路程最短的送递路径。两条路径的总长度均为54.708km，总时间3.149小时。问题二，在第一问的基础上

2、，我们对1000条近似最短路径进行时间检验，计算每条路径上每一点邮件送达的时间是否早于要求的时间，从而判断该路径是否符合时间要求。我们从1000条近似最短路径中筛选出48条符合时间要求的路径，再从中找出总长度最短的路径，得到序号为150的路径为本问题的最佳方案。问题三，本问题相比第一问，增加了分组的问题。由于邮件重量和体积的约束，100个邮件需分批次送递，我们制定了衡量分组优劣的标准均衡度，以此为准则，我们对Prim算法求出的50点最小生成树做适当调整，并结合重量、体积两个约束条件，确定分组。完成分组后，求解每一组地点的送递路径，与第一问相同。最终我们得到均衡度为0.026的分组方案及各组的送

3、递路径，并求出送完所有邮件的最短时间为6.728h。问题四针对第一小问，在第一问基础上增加检验邮递员到达每一地点的重量和体积，我们求出分2组的送递路径。针对第二小问，在第一小问基础上增加检验邮递员到达每一地点的实际时间，提出以准点率为标准衡量路径优劣，求出准点率为76.2%的最佳路径。针对第三小问，由于邮件增多带来的重量、体积的上升，分组数目相应增加，最终我们求出分6组，准点率为72.0%的送递路径。 【关键词】 最优圈，二边逐次修正法，矩阵翻转，最小生成树，均衡度一、问题的提出现有一邮局在图1中的O点，一邮递员需将邮件送至城市内多处。该地形图的示意图，各点连通信息，各件货物的相关信息，50个

4、位置点的坐标已在附录中给出。邮递员要将100件邮件送到50个地点。假设邮递员的最大载重是50公斤，所带货物的最大体积为1立方米，邮递员的路上平均速度为30公里/小时，每件货物交接花费2.5分钟。在不同的情况和要求下，邮递员需要以最快的速度及时将邮件送达指定地点。我们的任务是，在以下几个问题的特定要求下，给出具体的邮递员送邮件的具体路线，使其消耗的时间最少。问题一： 将130号邮件送到指定地点并返回。我们将设计出最快完成路线与方式，给出结果，标出送货线路。问题二：该邮递员从早上8点上班开始送邮件，要将130号邮件的送达时间不能超过指定时间。我们将设计出最快完成路线与方式并标出送货线路。问题三：

5、不考虑所有邮件送达时间限制(包括前30件货物)，现在要将100件邮件全部送到指定地点并返回。我们将设计出最快完成路线与方式，标出送货线路，给出送完所有邮件的时间。由于受重量和体积限制，邮递员可中途返回取货。可不考虑中午休息时间。问题四：如果邮递员送邮件的同时，还负责将各地需要寄送的邮件带回邮局，各地点需要带回邮局寄送的邮件的信息如表3，按照此条件重新解答以上三个问题。二、符号说明：赋权图；：赋权图的权矩阵；D ： 两点最短路径距离矩阵；: 两点最短路径的走法参考举证； ： 某条路径上第i个送达地点，收到邮件的实际时间； ： 某条路径上第i个送达地点，要求的送达时间；： 某条路径上第i-1个送达

6、地点，到第i个送达地点的距离；： 某条路径上第i-1个送达地点，到第i个送达地点的路上花费的时间；v ： 邮递员在路上的平均速度；： 表示每件货物的交接时间。： 表示最短距离矩阵： 表示要求第i个送达地点对应的地点序号三、模型的假设 1、假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米； 2、假设送货员的路上平均速度为30公里/小时，不会出现意外现象； 3、每件货物交接花费2.5分钟，同一地点有多件货物也简单按照每件2.5分钟交接计算，不会出现特殊情况而延误时间；4、送货员只沿示意图连线路径行走；5、假设快递公司地点O为第51个位置点；6、假设送货员回到出发点O后取货时间不计。四、

7、模型的建立与求解4.1 数据的预处理在给出的50个点中，我们已经知道了各点的坐标，通过代入两点间距离公式，我们可以得到50个点中可以两两直接到达的点之间的距离，即相邻的点的距离，如表1所示，详见附录。表 1序号位置点1位置点2位置点1坐标位置点2坐标两点间距离L113（9185，500）（7270，570）1916.3218（9185，500）（7160，2525）2863.83220（1445，560）（780，8355）7823.3424（1445，560）（3735，670）2292.6538（7270，570）（7160，2525）1958.1634（7270，570）（3735，67

8、0）3536.4742（3735，670）（1445，560）2292.6794942（11575，15160）（13265，14145）1971.4805040（8010，15325）（8345，12300）3043.5815118（11000，8250）（8825，8075）2182825121（11000，8250）（12770，8560）1796.9835126（11000，8250）（10860，9635）1392.14.2 任两点之间的最短路径下面我们采用Floyd法来计算50个点中任意两点之间的距离。设， 是一个有51个顶点和83条边的图。若将图G的每一条边e都对应一个实数， 则

9、称为该边的权，并称图G为赋权图(网络)，记为。设为赋权图的权矩阵，表示从到点的距离，表示从到点的最短路中前一个点的编号。算法步骤： 步骤一：赋初值。对所有， 转向步骤二。 步骤二： 更新。 对所有， 若，则令 , 转向步骤三; 步骤三：终止判断。 若k = n终止；否则令k = k + 1, 转向步骤二。 于是，最短路线可由得到。算法流程图：图 1由表1各地点的距离可构造示意图的带权邻接矩阵。由已知可知共有83条边，表示相邻点到的距离，不相邻的点之间的距离为无穷大。用Matlab编程得D(51)=（Dij）51×51，其中D(i,j)即为两点最短路径距离。表 2dij12345678

10、910111213145110774519165453899812941968286459734028603846216077865410068 2774505829229312539040971477871371811773109629544110011640016296 319165829035367082321138851958788959445133371551721057110467 4545322933536035466747742154951142694808669725187081410714004 589981253708235460102931096790401497113

11、026112289810112671765316563 612949040321167471029303263415872675322733359157372994911363 71968971438857421109673263048324005205980066589804666868100 82864778719585495904041584832088376891317417573214115188509 9597313718788911426149717267400588370194612011105941096926817775 10402811773594494801302653

12、222059689119460100668648902346278092 1160381096251338669112287333800631741201110066014181670101256965 124621954437157251981059156589175710594864814180145799126752 13607711001517287081126773728046321410969902316701457084565295 5110068 16296 10467 14004 16563 11363 8100 8509 7775 8092 6965 6752 5295 5

13、094 0同时，根据得到的R矩阵（见附录）求出插入点矩阵以便得到两点间的最短路径。例如，我们通过查询R矩阵来找到121的最短路径。首先，找到路径的第一个点，即为点7；再次寻找721最短路径的第一个点；再次找到1021最短路径的第一个点；最后找到5121最短路径的第一个点。于是121的最短路径为：。同理，可得的最短路径为：；的最短路径为：。图 24.3 过固定几个点的最短回路（问题一）对于问题一，需要送达的1-30号邮件的坐标共有21个，这21个点组成的集合为V，V=（13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49），

14、我们的任务是设计一条路线，从O（51）点出发，经过以上21点，并返回至O点的最短路径。4.3.1模型的建立设G=(V,E)是连通无向图，经过G的每个顶点正好一次的圈，称为G的一条哈密尔顿圈，简称H圈；含H圈的图成为哈密尔顿图或H图。那么我们要做的是找到最小哈密顿回路。在加权图G=(V，E，F)中，权最小的哈密尔顿圈称为最佳H圈；判定一个加权图G=(V，E)是否存在哈密尔顿圈是一个NP问题，而它的完备加权图（中的每条边（x,y）的权等于顶点x与y在图G中最短路径的权）中一定存在哈密尔顿圈，所以在完备图G'=(V,E')中寻找最佳H圈。该过程可采用二边逐次修正法并利用矩阵翻转实现。

15、二边逐次修正法的算法过程： 1任取初始H圈: 2. 对所有的，若,则在C0中删去边和而加入边和，形成新的H圈C，即3. 对C重复步骤（），直到条件不满足为止，最终得到的C即为所求。矩阵翻转 在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以第i行（列）和j行（列的）中心位置为转轴，旋转180度，这样：第i行（列）和第j行（列）的位置互换，第i+1行（列）和第j-1行（列）位置互换，4.3.2 模型的应用：根据51个点间的最短距离矩阵D，可以得到起始点O（51）和V中21点，共22点的完备加权图，这22个点即为：51，13,14,16,17,18,21,23,24,26,27,31,32,3

16、4,36,38,39,40,42,43,45,49的。将完备加权图用距离矩阵表示，假设这初始圈为。使所选的初始圈为矩阵的主对角线的上方元素对应的顶点，于是权邻接矩阵为初始圈所走距离为主对角线的上方元素之和，其经过的权为=11958。如果所选初始H圈不是c0，可通过交换距离矩阵H的行和列，使矩阵的主对角线的上方元素对应的顶点为所选的初始H圈。为了能看到翻转效果和更直观确定优化后H圈所走的路线，在第一行和最后一行给距离矩阵加上了一个点的排列顺序的框，与此同时为了使矩阵仍然保持为方阵，在第一列和最后一列加上2个0列(或者在距离矩阵第一行、列和最后一行、列同时加上一个点的排列顺序的框)： 调用求最佳H

17、圈的函数，把得出的结果矩阵再次调用这个函数，即为近似最佳H圈。此过程即是模型中的二边逐次修正法的算法过程的第2和第3步，以及矩阵翻转的过程。得到最后的距离矩阵： 的第一行的第二列到倒数第二列即为最佳H圈的路径。起点的确定：，对应于集合V中的，即出发点O（51）；第一步点的确定：，对应于集合V中的，即点21；第二步点的确定：，对应于集合V中的，即点14；第三步点的确定：，对应于集合V中的，即点26；如此下去，根据最优H矩阵找到对应点第二十二步点的确定：，对应于集合V中的，即点27；最后回到O点。则此近似最佳H圈的总权为=56980，邮递员30公里每小时，那么，邮递员花在路途中的时间为：；共交接了

18、30分邮件，每件邮件的交接时间为2.5分钟，则邮递员用于交接邮件的时间为：；总时间即为3.149小时。由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较优的计算结果，我们用MATLAB编程时，随机搜索出1000个初始H圈，每个初始H圈都可以通过上面类似的步骤找到所对应的近似最佳H圈。在这1000个近似最佳H圈中，我们再找出权最小的一个，即邮递员走的路程最短。1000近似最佳H圈的路径和所走距离见附录，下面我们给出了这1000条近似最佳H圈中权重最小的5条：表 3路线序号消耗总时间S所 走 路 线133.0736547085126211714162332383643424

19、9454034312739241318511503.07365470851181324312739344045424943363832231614172126511323.10685570551211714162332383643494245403439273124131826518273.109155772512639273124131834404542494336383223161417215143.11645599151131831242739344045494243363832231614172126511003.118056041512621171416233238434249454

20、0343127363924131851可见，路线13和路线150是路程相等，方向相反的两条路，它们的权值相同。其具体走法如图：图 34.4 问题二在第一问中，我们已经得到了1000条近似最佳路径，这一千条路径，总长度接近最短。但是第一问中并没有考虑每份邮件送达目的地的时间要求，在本问题中，我们试图从以上1000条近似最佳路径中，搜寻出符合时间要求，并且总长度最短的路径。因此，我们需考虑的两个约束条件分别是：1.时间要求；2.总长度最短4.4.1 判断路径是否符合时间要求判断一条路径是否符合时间要求，需要判断该路径上每一站邮件送到的时间均符合要求的时间，即 表示某一路径上，第i个送达地点收到邮件

21、的时间，表示第i个送达地点要求不超过的时间，i表示某一路径上第i个送达地点，而非原来的送达地点序号。例如，某一送递路径为O5121141716233236273924313440454249433813182651O，序号21的送达地点i=1，序号14的送达地点i=2，以此类推，序号26的送达地点i=21。所有的值题目已经给出，接下来我们需要计算值，第i个送达地点的收件时间，由上一个点（即第i-1个送达地点）的收件时间、路上花费的时间、货物交接时间三部分组成，即指邮件送至第i个送达地点时的时间点；指邮件送达第i-1个地点（即前一个地点）时的时间点；值表示从第i-1个地点到第i个地点，在路上花费

22、的时间；表示每件货物交接的时间。由题目知，邮递员8点从邮局出发，因此=8.00。为方便运算，下文在涉及时间时，均用小数表示，例如8时表示为8.00，9：30表示为9.50。值由第i-1个送达地点和第i个送达之间的距离、邮递员路上的平均速度决定，即值表示从第i-1个地点到第i个地点，在路上花费的时间；表示第i-1个送达地点与第i个送达地点之间的最短距离；邮递员路上的平均速度题目已经给出。第i-1个送达地点与第i个送达地点之间的最短距离，可从最短距离矩阵得到，即表示第i个送达地点，其对应的送达地点序号，以路线O/5121141716233236273924313440454249433813182

23、651/O为例，若i=3，i-1=2，。分别将对应的送达地点序号、作为最短距离矩阵的行、列，找到对应的两地间最短距离。例如，综合以上所述，我们可以得出，某一路径上，每一个送达地点收到邮件时间的计算公式：需要说明的是，我们认为，只有当邮件交付客户手中并完成交接手续之后，邮件才是真正意义上的送达，因此，在计算第一个送达地点的收件时间时，仍然需要加上交接时间项。通过i=1:n的迭代，可以计算出某一路径上，所有的送达地点收到邮件的时间，当路径上所有的送达地点收到邮件的时间均满足时，说明该路径符合时间要求。按此方法可批量检验路径是否符合时间要求。4.4.2 计算实现我们在MATLAB7.6环境中，将上述

24、的检验过程实现，具体的算法示意图如下：第一步：初始化，载入待检验的路径矩阵,该矩阵的的每一列表示一条路径，送达地点为21个，起点和终点均为O/51点，因此，矩阵行数为23，共有1000条待检验的路径，因此矩阵列数为1000。第二步：赋初值，令k=1,i=1执行k=1:1000,i=1:23的循环。小循环检验一条路径内23个送达地点时候据满足时间要求，大循环用于检验1000条路径中有多少条路径符合时间要求。第三步：输出结果，Total值代表符合时间要求的路径数目，矩阵SL1×total 表示符合时间要求的路径序号。4.4.3 计算结果程序执行结果，从1000条路径中得到48条符合时间要

25、求的路径，表1为部分符合路线举例。表 4路线S所 走 路 线455990.6151131831242739344045494243363832231614172126512755771.5451263927312413183440454249433638322316141721517456689.95511813243134403927364542494338322316141721265111056979.97511813243134404542494327393638322316141721265114556075.8451181324312739344049424345363832231

26、6141721265115054707.645118132431273934404542494336383223161417212651表 5路径13路径150路径132路径132反路径送达点到达时刻要求时刻送达点到达时刻要求时刻送达点到达时刻要求时刻送达点到达时刻要求时刻tiTitiTitiTitiTi518518518518268.09 12:00188.11 9:00218.10 12:00268.09 12:00218.20 12:00138.26 9:00178.20 12:00188.25 9:00178.31 12:00248.49 9:00148.32 12:00138.39

27、9:00148.42 12:00318.59 9:30168.45 12:00248.63 9:00168.55 12:00278.67 12:00238.56 12:00318.73 9:30238.66 12:00398.77 12:00328.64 12:00278.80 12:00328.75 12:00348.99 9:30388.77 10:15398.91 12:00388.87 10:15409.08 9:30368.86 12:00349.12 9:30368.96 12:00459.23 9:30439.04 10:15409.22 9:30439.14 10:15429.

28、35 10:15499.18 10:15459.36 9:30429.22 10:15499.46 10:15429.29 10:15429.48 10:15499.32 10:15439.60 10:15459.41 9:30499.59 10:15459.51 9:30369.78 12:00409.56 9:30439.73 10:15409.66 9:30389.87 10:15349.65 9:30369.91 12:00349.75 9:30329.99 12:00399.87 12:003810.00 10:15319.87 12:002310.08 12:00279.97 12

29、:003210.13 12:00279.95 12:001610.19 12:003110.05 9:302310.21 12:003910.05 9:301410.32 12:002410.15 9:001610.33 12:002410.25 9:001710.43 12:001310.38 9:001410.45 12:001310.48 9:002110.54 12:001810.52 9:001710.57 12:001810.63 9:002610.65 12:002610.69 12:002110.67 12:005110.74 5110.74 5110.77 5110.73 在

30、表5 中，路径13、路径132中有部分送达地点（以斜体加粗表示）的收件时间晚于要求时间，因此这类路径不符合时间要求；而在路径150和路径132的反路径中，所有送达地点的收件时间均早于要求的时间，因此这类路径符合时间要求。符合时间要求的路径共有48条，我们再从中找出总长度最小的路径，为路径150，得到符合时间要求的最快完成路径。表 6路径序号消耗总时间S所 走 路 线1503.0736547085118132431273934404542494336383223161417212651在第一问的求解中，我们得到总长度最短的两条路径，路径13和路径150，这两条路径所遍历点的顺序恰好相反，总长度相

31、等。在第一问中，两条路径均满足要求，但是在第二问中，路径13不符合时间要求，路径150满足。因此，路径150为本问题的理想方案。4.5 问题三对于单环路径的最短路径已经在问题一中解决，我们在此问中要解决的问题是对图中50个点的分组情况。一旦分组问题解决，每一组的路径可以根据问题一的模型求解最优H圈，进而解决。由于邮递员的最大载重是50公斤，所带货物的最大体积为1立方米，因此分组要满足这两个条件。经过数据统计，邮件的总重量为148公斤，总体积为2.8立方米。可见邮递员至少分3次运送邮件。分组的形成:我们考虑将所有邮件分为组。此问题是多个售货员的最佳旅行售货员问题，即在加权图G中求定点集的划分，将

32、G分成k个子圈，使得：（1） 定点（2）（3） ，其中为的导出子图中的最佳邮递员回路，为的权，。其中为该分组的实际均衡度，为最大容许均衡度。越小说明分组的均衡度越好。（4） 为所有分组中的最小值图中的节点数较多，有51个，我们只能去寻求一种较为合理的划分准则，对节点进行粗步划分后，利用问题一中的模型求出每个划分最佳H圈，再根据邮递员的实际情况进一步进行调整。我们首先用prim法生成最小生成树，观察干支和分支的情况：图 4从起始点51出发，共有两条干支，分成两组显然超过了邮递员的每次的送邮件限度。最小生成树的总权值可以通过将各支的权值相加，得到权值为91287。由图可见，点17和点31为两条干支

33、上的明显分支点，且各分支上的点较多。各分叉支的最远点主要有点5，点13，点15，点16，点33，点48，点39，点50，点45。若将所有点分成三组，尽量是值小，均衡度就越高。首先，我们将最远的几个叉点分为三组，将距离较近的点分在一起。为方便计算，我们将同一地点需要送达的几封邮件看为同一封邮件，即把它们合并起来。在这个假设条件下我们来计算各组的总质量和总体积。当最远叉点组合为，时表 7分法1地点序号路径走法总时间t总质量M总体积Va组1 2 3 4 5 6 78 9 10 11 1213 14 17 18 215121171491071642538121113185145237.532.2236

34、.230.7579b组15 19 20 22 24 2528 29 30 33 37 4041 44 46 4851403741444846332830152220292519245145616.552.1943.280.7828c组16 23 26 27 31 3234 35 36 38 39 4243 45 47 49 505126392731344750494243453638353216235148159.292.3168.491.2593此法虽然=已经很小，说明该分法的平衡度非常好。邮递员走的总路程为139012m，总花时6.72h。但是c组邮递员所送的邮件M=69.49>50

35、,V=1.2593>1，超过了邮递员的送件能力。调整最远叉点组合为，并调整a，b，c组的组成地点序号。表 8分法2地点序号路径走法总时间t总质量M总体积Va组1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 21 2351211723161491071632548121113185149521.642.4447.730.9575b组15 19 20 22 24 25 27 28 29 30 33 37 39 40 41 44 46 48512739241925292022153028334648444137405151311.92.4652.030.95

36、5c组26 31 32 34 35 36 38 42 43 45 47 49 5051263134474550494243383235365138205.131.8248.240.8875邮递员走的总路程为139037m，总花时间为6.728h。=。此法虽然b组总质量超过了最大质量的4.06%，但相对于分法1，已经较符合要求。4.6 问题四4.6.1 有寄回邮件情况下问题一的解答对于1-30号邮件，邮递员除了送件以外，还要将各地需要寄送的邮件带回邮局。我们首先对1-30号邮件的送往点集合V中地点需要带回的邮件进行统计，V=13,14,16,17,18,21,23,24,26,27,31,32,

37、34,36,38,39,40,42,43,45,49表 9邮件号地点V送件质量送件体积回件质量回件体积1132.50.0316006141.720.015.280.4330161.20.04292.70.07827171.380.01090.150.042180.50.03544.420.2865212.150.0305008,29234.310.09131.620.01920242.930.0421.80.034,23263.130.0560.60.0219,22274.70.0463003,21311.980.03482.20.259,17,28321.470.09130.50.15243

38、42.80.01032.50.0718361.790.01840.450.0610381.330.02191.520.40613392.560.05950025401.140.01553.270.3515422.850.0191.080.04912,16432.650.1010.80.0211,14,26454.060.0970.450.1227491.350.014400总计48.50.8829.342.3782在第一问中，我们已经求得这21个点与起点构成的近似最佳H圈为：5126211714162332383643424945403431273924131851或：511813243127

39、3934404542494336383223161417212651 现在在需要带回待发邮件的要求下，我们对上面两条路径进行检验。过程5126，邮递员所载的邮件质量为48.5公斤，体积为0.88立方米； 过程2621，邮递员所载的邮件质量为45.97公斤，体积为0.844立方米；过程2117，邮递员所载的邮件质量为43.82公斤，体积为0.8135立方米； 过程1714，邮递员所载的邮件质量为42.4509公斤，体积为0.8488立方米； 过程1416，邮递员所载的邮件质量为46.0109公斤，体积为1.2688立方米；体积过大。对于另外一条近似最佳H圈，过程5118，邮递员所载的邮件质量为4

40、8.5公斤，体积为0.88立方米；18点后邮递员载重为52.42，超过最大载重量。因此我们对这段路的进行调整，即稍微多走点路，将另邮件送到另一点减负，路线可以调整为 5113过程中邮递员于18点处将邮件送出，其所带的邮件质量变为48公斤，体积变为0.8495立方米；达到点13后邮递员又将邮件送出，且此点无须带回的邮件，于是邮递员在1318过程中邮件质量变为45.5公斤，体积为0.5335立方米。回到点18将须带回的邮件带上，于是邮递员在1831途中的邮件质量为49.92公斤，体积为0.8195立方米。312739，邮递员第一次到点27时也同样从先送邮件，回来过程中再取，这样邮件体积不会超过最大

41、体积限制。由于须带回的邮件总体积为2.3782，若分三组则太浪费时间。我们考虑将邮件分为两组，虽然体积超过了限制，但超得不多，约为0.37/2=0.19立方米左右,但是可以大大的减少时间。我们根据第一问的路线和最小生成树的分支情况，将这21点分为2组；第一组分支的得出已如上陈述。第一组：51131831344024273936212651，此过程中邮件质量没有超过最大负重，所载最大体积为1.066立方米，仅仅超过了最大体积的6.6%。第二组中邮递员须送邮件号为6，7，8，9，11，12，14，16，17， 25， 26，28，27，29，30的邮件，出发时邮递员负重23.46公斤，须带回的邮件

42、质量为17.37公斤，因此路途中邮递员绝对不会出现所载邮件超重的现象。那么只要考虑邮件体积的情况，出发时邮件体积为0.9013立方米，须带回邮件体积为1.3122，超过标准0.3122立方米，但比起再次分组送件，大大减少了所花的时间。将这10个点与原点利用第一问中的近似最优H圈解法，可以给出路径为：51261714162332384342494551。这两组路线的走法如图5：图 5 4.6.2 有寄回邮件情况下问题二的解答问题二中加入了时间的要求，邮件须尽量按时送到且按时带回。个别点既有须送到的邮件时间的要求又有须带回的邮件的要求，我们将这样的点取其最早的时间要求点。例如点16须送到的邮件的最

43、晚时间要求为12：00，须带回的邮件的最早时间为13：00。集合V的21个点中既有须送到的邮件时间的要求又有须带回的邮件的点有15个，记作，图中即用圆圈出。图 6在用二次逐边修正法确定了两组的近似最佳H圈后，我们可以计算到达各点的时刻。邮递员无论先走第一组路线，还是先走第二组路线，走的总路径距离相同，花的总时间按也都相同，为3.12小时。但是由于个地点对邮件寄到的时间按要求不同，先走第一组和先走第二组对客户的满足度不同。在下表中分别给出了两种走法和达到各点的时间情况。表 10走法1到达时间要求时间超时时间走法2到达时间要求时间超时时间第二组178.16 12准时第一组138.22 9准时148

44、.28 12准时188.36 9准时168.41 12准时318.48 9.5准时238.52 12准时348.59 9.5准时328.60 12准时408.69 9.5准时388.73 10.25准时248.92 9准时438.86 10.25准时279.06 12准时428.93 10.25准时399.16 12准时499.04 10.25准时369.34 12准时459.22 9.5准时219.47 12准时519.48 /准时269.59 12准时第一组139.70 90.70 519.63 /准时189.85 90.85 第二组179.80 12准时319.96 9.50.46 14

45、9.91 12准时3410.08 9.50.58 1610.04 12准时4010.18 9.50.68 2310.15 12准时2410.41 91.41 3210.24 12准时2710.54 12准时3810.36 10.250.11 3910.65 12准时4310.49 10.250.24 3610.82 12准时4210.56 10.250.31 2110.96 12准时4910.67 10.250.42 2611.07 12准时4510.86 9.51.36 5111.12 /5111.12 /先走第二组，再走第一组4.68 先走第一组，再走第二组2.45 对于走法1，21个点中

46、有6个点超过了时间的要求，准点率为71.4%，总超时为4.68小时。对于走法2，21个点中有5各点超过了时间的要求，准点率为76.2%，总超时为2.45小时。相对于走法1，走法二更为合理。4.6.3 有寄回邮件情况下问题三的解答对于100号邮件，邮递员除了送件以外，还要将各地需要寄送的邮件带回邮局。我们首先对51个地点需要带回的邮件进行统计。需要带回邮局的邮件的总重量为75.52公斤，总体积为6.1192立方米。邮递员所带货物的最大体积为1立方米，但若邮递员至少分7次送邮件则浪费了大量的人力和物力。我们将送件分为6次，体积总超限度量最多为0.1192立方米，平均每次超出的体积仅仅约为0.019立方米，基本可以接受。分组应符合问题三中（1）（2）（3）的条件，且邮件送递过程中邮递员所带的邮件量不超过邮递员的能力限制。类似问题三的分组方法，找到最小生成树叉支上较远的几个点，对其