邮政运输网络中的邮路规划和邮车调度优化研究

《邮政运输网络中的邮路规划和邮车调度优化研究》由会员分享，可在线阅读，更多相关《邮政运输网络中的邮路规划和邮车调度优化研究（33页珍藏版）》请在装配图网上搜索。

1、1 问题重述- 1 -2 模型假设- 2 -3 符号说明- 2 -4 模型建立与求解- 3 -4.1 问题1的解决- 3 -4.1.1 模型的建立- 3 -4.1.2 方案的比较与确定- 3 -4.1.2.2 TSP算法- 4 -4.1.2.3 最少车辆的确定- 5 -4.1.3 最佳邮路的选定方案- 6 -4.1.3.1 最佳邮路的确定- 6 -4.1.3.2 对最佳邮路的改进建议- 7 -4.1.4 问题1的小结- 7 -4.2 问题2的解决104.2.1 总体方案的选定及模型建立104.2.2 具体方案的实施114.2.2.1 以最小生成树为根据的邮路初步划分114.2.2.2 以改进的

2、TSP算法确定的邮路最终划分124.2.2.2 具体的邮车调度方案134.2.3 问题2的小结154.3 问题3的解决174.3.1 解决方案的确定174.3.2 具体方案的实施174.3.2.1 并入邻县邮路支局的选择174.3.2.2 相关邮路的重新规划174.3.3 问题3的小结184.4 问题4的解决204.4.1 解决方案的确定204.4.2 方案的具体实施204.4.2.1 各县级邮局选址的确定204.4.2.2 重新调整部分县局位置后的邮路划分204.4.3 关于上报省局网运处的书面材料224.4.4 问题4的小结22参考文献：25附件:26邮政运输网络中的邮路规划和邮车调度问题

3、1 问题重述 古往今来，邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展，邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况，本文提出了关于如何合理规划邮路的问题，具体内容如下：对一片有特定道路相连且有行政划分的地区进行邮路规划，有以下的问题需要解决：(1) 以县局X1及其所辖的16(18)个支局Z1, Z2, , Z16(下文简称为1，2，)为研究对象。假设区级第一班次邮车08:00(6:00)到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，在不超载的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的

4、。(2) 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本的邮路规划。(3) 当县局可以跨县投寄时的邮路规划。(4) 选择最合适的县局地点，并重新规划邮路，使得运行的成本最低。2 模型假设1所有的邮车在邮路上均按照平均时速匀速行驶。2县局对市局送来邮件的集中处理时间(1小时)既包括区级邮车的装卸时间10分钟，也包括县级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸区级邮车的工作；而县级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。3县局对将要送到市局的邮件的集中处理时间(1小时)既包括县级邮

5、车的装卸时间10分钟，也包括区级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸县级邮车的工作；而区级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。4两班次的区级邮车行驶路线完全相同，若路线为环形则运行方向必须一致。如：D615853X5525960D与D605952X5535861D两种行车路线即为不同的两条路线。5问题4中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。3 符号说明：市级邮局：县级邮局：表示县级邮局的集合：赋权邻接矩阵：Floyd算法中点到的距离。：Floyd算法中到之间的插入点。：Floyd算法中用插入顶点的方法依次构造

6、出的距离矩阵。：Floyd算法中用插入顶点的方法依次构造出的路由矩阵。：表示无向图。：支局停留时间：县局停留时间：区级邮车时速：县局邮件集中处理时间：县级邮车时速：区级邮车完成寄送县局工作后返回市局所需要的时间：县级邮车在县内走完第条邮路所需要的时间：开往县的第一班次区级邮车开出市局与第二班次区级邮车到达市局所需要的时间。：在各点设立服务设施的最大服务距离4 模型建立与求解4.1 问题1的解决4.1.1 模型的建立根据题意，问题一可以归纳为如下数学模型。其中：表示邮路方案；表示空置损失费；表示方案的总路径；P表示邮路方案集。4.1.2 方案的比较与确定根据题目要求，需要在限定的时间内完成投送邮

7、件的工作。首先，很自然地想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。4.1.2.1 Floyd算法Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵，使最后得到的矩阵成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。此算法的主要程序流程如下：Step 1：输入赋权邻接矩阵，Step 2：赋初值：对所有，。更新，：对所有，若，则： Step 3：若，停止，输出、；否则，重复Step 1。依照题目所给定数据得到的Floyd算法需要的赋权邻接矩阵如下：0274417112742infinfinf202521211827inf270

8、312749infinfinfinfinfinfinf522141infinf4431019inf2732infinfinf47infinfinf50infinf172719014infinfinfinfinf30infinfinf31infinf1149inf1401320infinf2815infinfinf15253027inf27inf130921inf2626infinfinf2829inf42inf32inf209013inf32infinfinfinfinf33infinfinfinfinfinf2113019infinfinfinfinfinfinfinfinfinfinfin

9、finfinfinf1901120infinfinfinf3321infinfinfinf282632inf1101020infinf29141320inf47301526infinf2010018infinf1492025infinfinfinfinfinfinfinf2018023infinf14inf2152infinfinfinfinfinfinfinfinf2302722infinf2121infinfinfinfinfinfinfinfinfinf270infinfinf184150311528infinfinf2914inf22inf011inf27infinfinf252933

10、inf3314914infinf1109infinfinfinf30infinfinf211320infinfinfinf90（注：此矩阵中的inf表示邮局间无直达公路） 具体程序见附件之程序一4.1.2.2 TSP算法本文需要求解的每路邮车路线（区级或县级），若用顶点表示邮车经过的邮局（市局、县局或支局），边表示连接两邮局的公路，边上的权表示距离。实际我们的问题就是在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。定义：在加权图中；(1)权最小的哈密顿圈称为最佳H圈。 (2)经过每个顶点至少一次的权的闭通路称为最佳邮车路线。最佳邮车路线问题可转化为最佳H圈问题，也称为TSP问题。方法是

11、由给顶的图构造一个以V为顶点集的完备图,的每条边的权等于顶点与在图中最短路的权,即： 定理：加权图的最佳邮车路线的权与的最佳H圈的权相同。算法：求加权图的最佳邮路的近似算法：1用Floyd算法求出G中任意两点间的最短路，构造出完备图；2输入图的一个出始圈；3用算法产生一个初始H圈；4随机搜索出中若干个H圈，例如20000个；5对第2、3、4步所得的每个H圈，用二次逐次修正算法进行优化，得到近似最佳H圈；6在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。具体程序见附件之程序二。4.1.2.3 最少车辆的确定根据题目的要求，寄达县局Z1的邮件量为176袋，而收寄的邮件量为1

12、70袋，同时每一辆县级邮车最多容纳65袋邮件，因此至少需要出动3车次才能够完成这样的投送量。同时，当区级第一班次邮车08:00到达县局X1之后需要有1个小时的时间对邮件进行集中处理；而当第二班次邮车16:00从县局X1出发返回地市局D之前同样需要1个小时对邮件进行集中处理，因此县级邮车工作的时间为9:00到15:00之间的6个小时。以下分情况讨论各种出车方案：1方案一：1辆车出动3次。利用上面的Floyd算法和TSP算法联合求解，可以得到其最短里程数为279公里。以县级邮车平均时速30公里计算，1辆车至少需要9个多小时才可以完成，不满足6小时时限的条件。因此此本方案不可行。2方案二：2辆车各出

13、动2次。由算法得到本方案的最短里程为334公里，共需668分钟；再加上16个支局的装卸时间为80分钟，以及2辆车在县局的装卸时间20分钟，总共768分钟。因此平均每辆车耗时384分钟，超过了6小时时限。因此本方案也不可行。3方案三：2辆车，其中1辆车出动一次，另1辆车出动2次。运用以上同样的方法可以得到其最短里程数为313公里，根据最高时速30公里的限制，可得需要626分钟；再加上16个支局的装卸时间为80分钟，以及其中一辆车在县局的装卸时间10分钟，共716分钟。因此平均每辆车耗时358分钟，恰好满足时间的限制。再考虑2辆车要送16个支局的因素，则至少有一辆车需要送8个支局。通过运行分组判断

14、程序（程序三）可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的。因此这种方案也不予考虑。4方案四：3辆车各出动1次。由于出动的车次相同，本方案与方案二所需的最短里程数同为313公里，总共需时716分钟，平均每辆车耗时不到239分钟。由于有3辆车，则至少有一辆车需要投送6个支局。再运行分组判断程序则可以知道这样的邮路是存在的。因此本方案可行。4.1.3 最佳邮路的选定方案4.1.3.1 最佳邮路的确定显然，本问题被转化为将16个支局分为3组，使得3辆从县局出发的车辆可以在6小时内到达自己组里的所有的支局并及时返回，同时在邮车运行过程中运载的邮包不超过65袋且经济损失最小。对于运行过

15、程中邮包的变化如表1所示：表1：各支局邮件量及变化情况支局邮件量Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达局为Z i的邮件量（袋）101569136114131711211211314支局Z i收寄的邮件量（袋）9145109101391596713151016过支局Z i邮件量的变化（袋）-1-1-11-44252-8-552-6-32根据题目所给的限制条件，引入贪心算法的概念。也就是尽量让邮车“吃饱”，即让空车率损失保持在较低的水平。最后结合Floyd算法重新编制改进型贪心算法（具体程序见附件程序四），其主要程序流程如下：Step 1：将所有结点分为

16、三组，并判断其运送的邮包量是否超过65。如超过则重新分组，不超过则进入下一步。Step 2：计算出3条遍历各分组节点的路径，并记录邮车每经过1个支局时总共损失的金额以及当时运载邮件的数量。判断运载邮件量是否超过65，若超过则重复本步骤，不超过则进入下一步。Step 3：判断得到的路径是否满足6小时的时间限制，若超过6小时则重复Step 2，不超过则记录下损失金额并进入下一步。Step 4：记录下3条路径的走法及损失的金额，并计算出路径总里程和总损失金额。Step 5：重复执行Step 2。若总损失金额大于先前所得，则重新执行Step 2；若总损失金额小于先前所得，则覆盖原数据后重新执行Step

17、 2；若总损失金额等于先前所得，则判断总里程数，若小于先前所得则覆盖原数据重新执行Step 2，否则直接重新执行Step 2Step 6：重新执行Step 1，直到找到最小值。利用以上的改进型贪心算法，得到邮路规划如表2所示：表2：空车损失最小的邮路规划邮路耗时(分钟)里程(公里)损失(元)X115(不装卸)1615(不装卸)56234X13481595.108X11213114(不装卸)1514X132515019.292X110(不装卸)9878(不装卸) 9(不装卸)1110X132114822.615457(总计)47.02(总计)4.1.3.2 对最佳邮路的改进建议以上方法得到的经济

18、损失的数值固然最小，但是里程数与理论值313差距较大，特别是在邮车接近满载时程序会选择较长的路线，因为此时空车率极低（甚至为0），所以即使路线较长但损失却不会过大。不过与现实生活中，运行里程也是要列入成本核算的，所以对上述的改进型贪心算法稍作修改：在Step 5中不再将所得数据与先前数据相比较，而是设定一个阈值（这里选定的是85），于是可以得到相对较短的3条邮路如表3：表3：更符合实际的改进邮路邮路耗时(分钟)里程(公里)损失(元)X110(不装卸)9161514X11828110.49X11087654X124010519.11X1111213123X135616351.97349(总计)8

19、1.57(总计)4.1.4 问题1的小结综上所述，经过建摸、编程、计算、求解等过程，我们得出至少需要3辆邮车才能满足该县的邮件运输需求。为了降低空车率从而达到提高邮政运输效益的目的，根据题意给出具体的3条邮路规划如下：（具体的线路示意图见图1）1X115(不装卸)1615(不装卸)56234X12X11213114(不装卸)1514X13X110(不装卸)9878(不装卸) 9(不装卸)1110X1 这样的规划路线可使空车损失金额达到最小的47.01元，总里程为457公里。同时，从实际出发，进一步给出一种兼顾空车损失金额和总里程数两方面因素的邮路规划如下：（具体的线路示意图见图2）1X110(

20、不装卸)9161514X12X11087654X13X1111213123X1这样的规划路线可使总里程数降为349公里，空车损失金额为81.57元，。33图1：空车损失最小的路线示意图图2：兼顾两方面因素的路线示意图4.2 问题2的解决4.2.1 总体方案的选定及模型建立要选择里程最短的路线首先应当考虑对整个区域采用环形邮路进行规划，但是由于有一整套严格的规定，这种方法显然是不可取的。而若采用辐射形邮路，根据题目所提供的信息便可以知道这种方法虽然能够满足时限要求，但所得路径的里程却很长。因此，混合形邮路就成了必然的选择。问题二的数学模型如下： 车辆集满足时间约束其中：表示区级及县级邮车集；。：

21、表示区级及县级支局集；。，分别表示区级及县局集。；,表示车辆从结点到结点。；,表示车辆服务于第结点。显然,此问题包括四个方面：第一、对各个邮局点进行合理分组；第二、在每组中求出最短回路；第三、判断是否满足时间约束；第四、选择总里程较短的线路方式。4.2.2 具体方案的实施4.2.2.1 以最小生成树为根据的邮路初步划分由于单辆邮车的最佳路线问题不存在多项式时间内的精确算法，而图中节点数较多（总共为79个），且区级和县级邮车所覆盖的路线范围及路上所消耗时间还有诸多限制，因此我们只能去寻求一种较合理的划分准则对整个区域进行初步划分。首先，分别列出从D点到X1、X2、X3、X4、X5各支局的最短路，

22、这些最短路构成一棵从D点出发的数枝，称为干枝。又因为各区级支局只能由区级邮车运送邮件，所以在此最小生成树图上需要加上所有的区级支局，并标示其到D点的最短路（见图3）。图3：市局到各县局的最小生成树结构图从图中可以看出，从点出发到5个支局共有5条干枝，根据实际工作的经验及上述的分析，在分组时应遵循以下原则：1尽量将同一干枝上及其分枝上的节点分在同一组；2尽量将邻近并连通的节点分在同一组。3应让短的干枝和尽量多的与其邻近的节点分在同一组，而长的干枝和较少的与之接近的节点分在同一组。对于剩下的各县级支局来说，根据其与市局及本县县局的关联程度，分别给它们赋予权值。最后依据上述分组原则，再使用SPSS软

23、件求出以下的一种分组情况（见表4）：表4：区级邮车到各县局所需要经过的支局第一组D，8，9，10，11，14，15，16，62，X1第二组D，18，27，63，64，65，66，67，X2第三组D，28，29，30，31，32，33，34，35，68，69，70，X3第四组D，36，40，41，42，43，44，71，72，73，X4第五组D，52，53，58，59，60，61，X5根据以上分组，使用先前的TSP算法程序可以分别得出每辆区级邮车运行的最佳路线。（见表5）表5：区级邮车的行驶路线路线里程数(公里)耗时(分钟)到县局的耗时(分钟)经停D62161511X114109862D2262

24、59105县局X1；支局62，16，15，11，14，10，9，8D66636418X2276567D232259125县局X2；支局66，63，64，18，27，65，67D682933X32831303234357069D249295114县局X3；支局68，29，33，28，31，30，32，34，35，70，69D713641X4404344427372D24828484县局X4；支局71，36，41，40，43，44，42，73，72D615853X5525960D267286133县局X5；支局61，58，53，52，59，60（注：表中耗时依据假设1算定。）4.2.2.2 以改进

25、的TSP算法确定的邮路最终划分接下来将原来的TSP算法程序稍加改动，为其加上时间限制条件。根据假设2可知县级邮车需在第一班次区级邮车到达县局之后60分钟后出发，但有10分钟可包含在这个60分钟内，因此对总消耗时间的影响为50分钟；根据假设3可知县级邮车需在第二班次区级邮车离开县局之前60分钟返回；又根据假设4规定的相同路线可知第一班次区级邮车到达县局所需的时间与第二班次区级邮车从县局返回市局所需的时间之和即为区级邮车完成寄送县局i工作后返回市局所需要的时间Ti。据此可以得到区级邮车最少总耗时。改进的TSP算法程序主要流程如下（具体程序见附件程序五）：Step 1：求出县中剩余支局间的最短路径，

26、并解出、和。若大于300，则重新执行Step 1。Step 2：判断是否大于720。若小于720，则计算下一个县；若大于720，则将上述支局分为2组，重新计算。判断是否满足要求，若不满足则重新分组。如此循环Step 3：若分2组不能满足要求就进一步将其分为3组，以此类推。Step 4：按上述步骤将所有县级的邮路计算完毕。各县内的具体邮路规划如表6：表6：各县级邮车的行驶路线路线里程(公里)耗时(分钟)经停X111312X196207支局1，13，12X1457623X1126282支局4，5，7，6，2，3X21719X276162支局17，19X221222324252620X2148331

27、支局21，22，23，24，25，26， 20X4373839X492199支局37，38，39X55457565554(不装卸)X5132284支局54，57，56，55X550494847454651X5137309支局50，49，48，47，45，46，514.2.2.2 具体的邮车调度方案根据题意，可按以下步骤进行邮车调度：Step 1：第一班次区级邮车早上06:00同时从市局出发开往县局。Step 2：第一班次区级邮车到达各县局之后10分钟返回，县级邮车在区级邮车到达1小时后出发。Step 3：最后一辆县级邮车回到县局的时间之后1小时就是第二班次区级邮车从该县局的发车时间，若此县无需

28、县级邮车或县级邮车回县局时间较早，发车时间可相应延后。Step 4：由第二班次区级邮车于各县局的发车时刻可倒推出区级邮车到达县局的时刻以及由市局出发的时刻，并检验此出发时刻是否晚于第一班次 区级邮车回到市局的时刻，若不相符合则调后第二班次区级邮车的发车时刻。Step 5：根据以上的时刻信息计算出第二班次区级邮车返回到达市局的时刻，并检验是否超过18:00，若超过18:00则重新调整。最后得到邮车调度时刻表（见表7）如下：表7：邮车调度时刻表邮车路线出发时间到达目的地时间返回时间返回到达时间X1（第一班）D62161511X114109862D06:0007:4507:5510:19X1（第二班

29、）13:3015:1515:25(13:27)17:49X2（第一班）D66636418X2276567D06:0008:0508:1510:19X2（第二班）13:2115:2615:36(14:36)17:40X3（第一班）D682933X32831303234357069D06:0007:5408:0410:55X3（第二班）13:0014:5415:04(无)17:55X4（第一班）D713641X4404344427372D06:0007:2407:3410:44X4（第二班）13:0014:2414:34(11:43)17:44X5（第一班）D615853X5525960D06:0

30、008:1308:2310:46X5（第二班）13:0015:1315:23(14:22)17:46X1-1X111312X108:4512:12X1-2X1457623X108:4513:27X2-1X21719X209:0512:14X2-2X221222324252620X209:0514:36X4-1X4373839X408:2411:43X5-1X550494847454651X509:1314:22X5-2X55457565554(不装卸)X509:1313:57（注：表中第二班次区级邮车返回时间栏中括号内的数值为该县县级邮车最晚的返回时间。）4.2.3 问题2的小结为了得到符合题

31、目所提出的全部条件的路线规划结果，我们在这里以最小生成树为依据，先对邮路进行初步的划分，之后使用改进的TSP算法找出其余的线路。本线路规划方案规划邮路12条，需要区级邮车5辆，县级邮车7辆，共计12辆邮车；线路总里程2029公里，全区邮路运行成本6087元。为了使本方案划分出的邮路得到更直观的表现，我们又制作了分县邮路表（表8）和邮路示意图（图4）。表8：分县邮路表区内区级邮车路线里程数(公里)县内县级邮车路线里程数(公里)X1D62161511X114109862D226X1-1X111312X196X1-2X1457623X1126X2D66636418X2276567D232X2-1X2

32、1719X276X2-2X221222324252620X2148X3D682933X32831303234357069D249无X4D713641X4404344427372D248X4-1X4373839X492X5D615853X5525960D267X5-1X550494847454651X5137X5-2X55457565554(不装卸)X5132图4：全区邮路示意图4.3 问题3的解决4.3.1 解决方案的确定对于打破行政区划的邮件投送，只需考虑部分县与县交界地带的支局到底由哪个支局进行投送即可。本文通过将这些支局分别放入相邻的两个县并计算最佳哈密顿圈（最佳H圈）的方法来确定支局的

33、归属。即将此县级支局并入最佳哈密顿圈小的那个县。4.3.2 具体方案的实施4.3.2.1 并入邻县邮路支局的选择根据问题2所得到的路线图，34支局、35支局和44支局都已经并入了邻县的邮路（由区级邮车完成投寄任务），只有17支局和27支局有并入邻县邮路的可能。先考虑17支局的归属，当其没有并入相邻县局X1的邮车运送范围时，县局X2加支局1726的最小哈密顿圈是227公里，县局X1加支局116的最小哈密顿圈是623；如果17支局并入相邻县局X1的邮路时，县局X2加支局1826的最小哈密顿圈是198，县局X1加支局117的最小哈密顿圈是630。（计算最小哈密顿圈的程序见附件之程序六。）再通过简单的

34、计算有：227+623198+630。可见，单从总里程数的减少上来说，17支局可以划入X1邮车的运送范围。但是，进一步运用改进的TSP算法进行计算后发现，当有时间限制条件时所生成的邮路里程要大于原先的里程，因此把17支局划入X1内不可行。再考虑27支局的归属，当其没有并入相邻县局X2的邮车运送范围时，县局X3加支局2733的最小哈密顿圈是176公里，县局X2加支局1726的最小哈密顿圈是227；如果27支局并入相邻县局X2时 ，县局X3加支局2833的最小哈密顿圈是134，县局X2加支局1727的最小哈密顿圈是241。再通过简单的计算有：176+227134+241。很明显，将27支局划入X2

35、邮车的运送范围能减少里程数，进一步运用改进的TSP算法进行计算后可以得到新的邮路规划方案使得里程数有所减少，因此把27支局划入X2内是可行的。4.3.2.2 相关邮路的重新规划通过以上程序的计算，可以得到新的邮路规划。即将原来D到X2的路径D66636418X2276567D改为D666318X2646567D，新邮路经停县局X2和支局66，63，64，18，65，67，里程199公里，耗时224分钟，到X2耗时97分钟。另外，将原先的邮路X221222324252620X2改为X22721222324252620X2，经停支局27，21，22，23，24，26，25，20，里程169公里，耗

36、时378分钟。新的邮路规划方案还是需要5辆区级邮车和7辆县级邮车，共12辆车。总里程降低为2017公里，运行总成本为6051元。4.3.3 问题3的小结本方案通过对比最小哈密顿圈来确定将支局27划归邻县X2的邮路以达到减少总里程数并降低成本的目的。相较于问题2的结果，总里程数降低了12公里，成本下降了36元。为了使本方案划分出的邮路得到更直观的表现，我们又制作了邮车调度时刻表（表9）和邮路示意图（图5）。表9：邮车调度时刻表邮车路线里程数(公里)出发时间到达目的地时间返回时间返回到达时间X1（第一班）D62161511X114109862D22606:0007:4507:5510:19X1（第

37、二班）13:3015:1515:2517:49X2（第一班）D666318X2646567D19906:0007:3707:4709:44X2（第二班）14:0815:4515:5517:52X3（第一班）D682933X32831303234357069D24906:0007:5408:0410:55X3（第二班）13:0014:5415:0417:55X4（第一班）D713641X4404344427372D24806:0007:2407:3410:44X4（第二班）13:0014:2414:3417:44X5（第一班）D615853X5525960D26706:0008:1308:231

38、0:46X5（第二班）13:0015:1315:2317:46X1-1X111312X19608:4512:12X1-2X1457623X112608:4513:27X2-1X21719X27608:3711:19X2-2X22721222324252620X216908:3714:55X4-1X4373839X49208:2411:43X5-1X55457565554X5513209:1314:05X5-2X550494847454651X513709:1314:22图5：邮路示意图4.4 问题4的解决4.4.1 解决方案的确定很显然，本问题的关键在于县局地址选择的问题，县局地址一旦确定，根

39、据原有的改进TSP算法就可以得到邮路的规划方案。为了解决县局选址的问题，下面提出最短路覆盖中心算法（程序七），即要求网络中最边远的被服务点于提供公共服务的设施之间的距离尽可能小。具体的算法步骤如下：Step 1：用Floyd算法求出距离矩阵；Step 2：计算在各点设立服务设施的最大服务距离： Step 3：求出顶点，使，则技术要求的建立中心点的地点4.4.2 方案的具体实施4.4.2.1 各县级邮局选址的确定利用上面提出的最短路覆盖中心算法，得到各县局的新位置如表10所示：表10：新县局位置县别县局新X19X221X328X4X4X552显然，X4无需调整。对于其它新的县局地址的调整，依照假

40、设5的限制条件，再调用改进的TSP算法进行演算，判断其可行性。最后得到以下结论：X1、X5调整后可减少里程，并符合时间限制，因此有调整的必要；X3调整后的邮路与原先一致，所以没有调整的必要；X2调整后虽然可以减少里程数，但不符合时间限制，因此也没有调整的必要。4.4.2.2 重新调整部分县局位置后的邮路划分通过上述的程序解得的与X1有关的新邮路如下：1. D62169(new X1) 1662D停县局9(new X1)，停支局62，16共124公里，耗时135分钟，到X5耗时58分钟29(new X1)1043256789(new X1)停支局10，2，3，4，5，6，7，8共137公里，耗时

41、314分钟39(new X5)1112131X1(old)14159(new X1)停支局11，12，13，1，X5(old)，14，15共161公里，耗时357分钟同时得到与X5有关的新邮路如下：1D615852(new X5)5960D停县局52(new X5)，停支局61，58，59，60共201公里，耗时216分钟，到X5耗时96分钟252(new X5)5049484745465152(new X5)停支局50，49，48，47，45，46，51共133公里，耗时301分钟352(new X5)53X5(old)5455565752(new X5)停支局53，X5(old)，54，5

42、5，56，57共164公里，耗时358分钟为了更直观地了解新邮路的分布情况，在此列出分县邮路表（见表11）：表11：分县邮路表邮车区级邮车路线里程数(公里)邮车县级邮车路线里程数(公里)X1D62169(new X1) 1662D124X1-19(new X1)1043256789(new X1)137X1-29(new X5)1112131X1(old)14159(new X1)161X2D66636418X2276567D232X2-1X21719X276X2-2X221222324252620X2148X3D682933X32831303234357069D249无X4D713641X4

43、404344427372D248X4-1X4373839X492X5D615852(new X5)5960D201X5-152(new X5)5049484745465152(new X5)133X5-252(new X5)53X5(old)5455565752(new X5)164经过调整X1、X5的县局位置，并重新规划邮路之后，得到的总里程数为1965公里，总成本为5895元。这个结果相对于问题2的结果，里程减少64公里，节约成本192元。4.4.3 关于上报省局网运处的书面材料尊敬的省局网运处领导：为了全面贯彻中央关于全面建设和谐社会的方针；努力将邮政总局关于加强深化改革，保持平稳协调健

44、康发展的措施落到实处；并结合本市的实际情况，提出关于本市邮政网络调整的一点建议，主要的理由如下：1本市邮政网络已运营多年，跟不上社会的发展和人民群众的需求，亟待调整和改革。2经测算，进行邮政网路调整可加快邮件投递速度并减少运营成本。例如，将县局X1迁至现在支局9的位置，同时将县局X5迁至现在支局52的位置，这样可减少运行里程64公里，并节约资金192元。以上建议请批复，不周之处，敬请指正。市局网运处2007年10月22日4.4.4 问题4的小结通过使用最短路覆盖中心算法，首先将需要调整的县局迁移到合适的位置。运用原有程序得出邮路调整后的运行总里程数为1965公里，较问题2减少64公里；运行成本

45、为5895元，较问题2减少支出192元。为了更直观地展示调整后的邮路，在此编制邮车调度时刻表（表12）和邮路示意图（图6）。表12：邮车调度时刻表邮车路线里程数(公里)出发时间到达目的地时间返回时间返回到达时间X1（第一班）D62169(new X1) 1662D12406:0006:5807:0808:15X1（第二班）15:3016:2816:3817:45X2（第一班）D66636418X2276567D23206:0008:0508:1510:19X2（第二班）13:2115:2615:3617:40X3（第一班）D682933X32831303234357069D24906:0007

46、:5408:0410:55X3（第二班）13:0014:5415:0417:55X4（第一班）D713641X4404344427372D24806:0007:2407:3410:44X4（第二班）13:0014:2414:3417:44X5（第一班）D615852(new X5)5960D20106:0007:3607:4609:36X5（第二班）13:4815:2415:3417:24X1-19(new X1)1043256789(new X1)13707:5813:12X1-29(new X5)1112131X1(old)14159(new X1)16107:5813:55X2-1X21

47、719X27609:0512:14X2-2X221222324252620X214809:0514:36X4-1X4373839X49208:2411:43X5-152(new X5)5049484745465152(new X5)13308:3613:37X5-252(new X5)53X5(old)5455565752(new X5)16408:3614:34图6：邮路示意图参考文献：1 管梅谷.奇偶点图上作业法J.数学学报,1990,10:263266.2 田丰,马仲蕃.图与网络流理论M。北京:科学出版社,2000.3 吴振奎,刘舒强.运筹学概论M。第二版.北京:中国经济出版社,2000

48、.4 Edmonds J, Johnson E L. Matching, Eulertouss and Chiness postmanJ. Math. Programming, 1973, 5: 88124.5 陈国良,等.遗传算法及其应用M.北京:人民邮电出版社,1999.4160.6 戴一奇,等.图论与数据结构M.北京:清华大学出版社,1998.254309.7 杨弼亮.汽车运输企业管理基础M.北京:人民交通出版社,1992.123225.8 胡运权.运筹学教程.北京:清华大学出版社,1998.225228,129136,241242.9 Robert V Binder著.华庆一等译.面向

49、对象系统的测试M.北京:人民邮电出版社,2001.10 C Bourhr,R Dssouli,E M Aboulhamid.Automatic test generation for EFSM-based systemsM.Publication departementale 1043,Departement IRO,Universite de Montreal,1996-08.11 cavalla A R,Favreau J-P,Philippou M.Formal Methods in Conformance Testing:Results and PerspectivesC.In:Pro

50、cedings of Protocol Test Systems VI,IFIP,1994:317.12 A V Aho,A T Dahbura,D Lee et al.An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman toursJ.IEEE trans Commum,1991,39(11):16041615.13 G Prem Kumar,P Venkataram.Protocol Test Sequence G

51、eneration Using MUIOS Based on TSP Problem C.In:National Conference on Computer Networks,Architecture and Applications,Madras,1994-12:657414 王治平,李雪耀.遗传算法求解有向中国邮局问题J.哈尔滨工程大学学报,1998;19(2).15 Syam Siddhartha S.A model and methodologies for the location problem with logistical componentsJ.Computers & Op

52、erations Research,2002,29:11731193.16 Kaj Holmberg.Exact solution methods for uncapacitated location problems with convex transportation costsJ.European Journal of Operationl Research,1999,114:127140.附件:程序一function WT1_floyd%Floyd算法得出的最短距离矩阵和路径矩阵，可求任意几点或所有点。D=ones(79,79)*inf;%赋权邻接矩阵for i=1:79 D(i,i)

53、=0;endfid=fopen(sysj1.txt);tline = fscanf(fid,%5d);fclose(fid);L,CM=size(tline);for i=1:L/3 %i a=tline(3*(i-1)+1); b=tline(3*(i-1)+2); c=tline(3*i); if a7 x=a; elseif a20 x=a-10+6; else x=a-100+6; end if b7 y=b; elseif b20 y=b-10+6; else y=b-100+6; end D(x,y)=c; end for i=2:79 for j=1:(i-1) D(i,j)=D(j,i); end end %求任意几点% a=2+6,3+6,4+6,5+6,6+6,7+6;% n=length(a);% W1=zeros(n,n); %for i=1:n % for j=1:n % W1(i,j)=D(a(i),a(j); % end %end d,r=Floyd(D); %d %d,r=Floyd(W1);程序二sets: cities/1.3/:u; link(cities,