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

《邮政运输网络中的邮路规划和邮车调度优化研究hljn.docx》由会员分享，可在线阅读，更多相关《邮政运输网络中的邮路规划和邮车调度优化研究hljn.docx（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、邮政运输输网络中中的邮路路规划和邮邮车调度度问题1问题重重述 古往今今来，邮邮政在人人们的生生活中都都扮演着着不可或或缺的角角色。随随着时代代的发展展，邮件件投送的的时限和和成本成成了邮政政运输问问题的关关键因素素。根据据题目给给出的实实际情况况，本文文提出了了关于如如何合理理规划邮邮路的问问题，具具体内容容如下：对一片有有特定道道路相连连且有行行政划分分的地区区进行邮邮路规划划，有以以下的问问题需要要解决：(1) 以县局局X1及其所所辖的116个支支局Z1, ZZ2, , ZZ16(下文简简称为11，2，)为研究对象。假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县

2、局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，在不超载的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的。(2) 采用尽尽可能少少、尽可可能短的的邮路可可以减少少邮政部部门车辆辆和人员员等的投投入，从从而显著著降低全全区邮政政运输网网的总运运行成本本的邮路路规划。(3) 当县局局可以跨跨县投寄寄时的邮邮路规划划。(4) 选择最最合适的的县局地地点，并并重新规规划邮路路，使得得运行的的成本最最低。2 模型型假设1所有有的邮车车在邮路路上均按按照平均均时速匀匀速行驶驶。2县局局对市局局送来邮邮件的集集中处理理时间(1小时时)既包包括区级级邮车的的装卸时时间100分钟，也也包

3、括县县级邮车车的装卸卸时间110分钟钟。且在在这1个个小时的的起始阶阶段进行行装卸区区级邮车车的工作作；而县县级邮车车的装卸卸工作最最早在集集中处理理工作结结束前110分钟钟进行，也也可以在在集中处处理工作作结束之之后进行行。3县局局对将要要送到市市局的邮邮件的集集中处理理时间(1小时时)既包包括县级级邮车的的装卸时时间100分钟，也也包括区区级邮车车的装卸卸时间110分钟钟。且在在这1个个小时的的起始阶阶段进行行装卸县县级邮车车的工作作；而区区级邮车车的装卸卸工作最最早在集集中处理理工作结结束前110分钟钟进行，也也可以在在集中处处理工作作结束之之后进行行。4两班班次的区区级邮车车行驶路路线

4、完全全相同，若若路线为为环形则则运行方方向必须须一致。如如：D615853X5525960D与D605952X5535861D两种行行车路线线即为不不同的两两条路线线。5问题题4中选选定县局局后，县县级邮车车不得打打破行政政区划限限制而跨跨县投寄寄。3 符号号说明：市级邮邮局：县级邮邮局：表示县县级邮局局的集合合：赋权邻邻接矩阵阵：Flooyd算算法中点点到的距离离。：Flooyd算算法中到到之间的的插入点点。：Flooyd算算法中用用插入顶顶点的方方法依次次构造出出的距离离矩阵。：Flooyd算算法中用用插入顶顶点的方方法依次次构造出出的路由由矩阵。：表示无无向图。：支局停停留时间间：县局停

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

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

7、p 11。依照题目目所给定定数据得得到的FFloyyd算法法需要的的赋权邻邻接矩阵阵如下：0274417112742infinfinf202521211827inf270312749infinfinfinfinfinfinf522141infinf4431019inf2732infinfinf47infinfinf50infinf172719014infinfinfinfinf30infinfinf31infinf1149inf1401320infinf2815infinfinf15253027inf27inf130921inf2626infinfinf2829inf42inf32inf209

8、013inf32infinfinfinfinf33infinfinfinfinfinf2113019infinfinfinfinfinfinfinfinfinfinfinfinfinfinf1901120infinfinfinf3321infinfinfinf282632inf1101020infinf29141320inf47301526infinf2010018infinf1492025infinfinfinfinfinfinfinf2018023infinf14inf2152infinfinfinfinfinfinfinfinf2302722infinf2121infinfinfinfi

9、nfinfinfinfinfinf270infinfinf184150311528infinfinf2914inf22inf011inf27infinfinf252933inf3314914infinf1109infinfinfinf30infinfinf211320infinfinfinf90（注：此此矩阵中中的innf表示示邮局间间无直达达公路） 具具体程序序见附件件之程序序一4.1.2.22 TTSP算算法本文需要要求解的的每路邮邮车路线线（区级级或县级级），若若用顶点点表示邮邮车经过过的邮局局（市局局、县局局或支局局），边边表示连连接两邮邮局的公公路，边边上的权权表示距距离。实实际我们

10、们的问题题就是在在加权图图中寻找找一条经经过每个个顶点至至少一次次的最短短闭通路路问题。定义：在在加权图图中；(1)权权最小的的哈密顿顿圈称为为最佳HH圈。 (2)经过每每个顶点点至少一一次的权权的闭通通路称为为最佳邮邮车路线线。最佳邮车车路线问问题可转转化为最最佳H圈圈问题，也也称为TTSP问问题。方法是由由给顶的的图构造造一个以以V为顶顶点集的的完备图图,的每条条边的权权等于顶顶点与在图中中最短路路的权,即：定理：加加权图的的最佳邮邮车路线线的权与与的最佳佳H圈的的权相同同。算法：求求加权图图的最佳佳邮路的的近似算算法：1用FFloyyd算法法求出GG中任意意两点间间的最短短路，构构造出完

11、完备图；2输入入图的一一个出始始圈；3用算算法产生生一个初初始H圈圈；4随机机搜索出出中若干干个H圈圈，例如如200000个个；5对第第2、33、4步步所得的的每个HH圈，用用二次逐逐次修正正算法进进行优化化，得到到近似最最佳H圈圈；6在第第5步求求出的所所有H圈圈中，找找出权最最小的一一个，此此即要找找的最佳佳H圈的的近似解解。具体程序序见附件件之程序序二。4.1.2.33 最最少车辆辆的确定定根据题目目的要求求，寄达达县局ZZ1的邮件件量为1176袋袋，而收收寄的邮邮件量为为1700袋，同同时每一一辆县级级邮车最最多容纳纳65袋袋邮件，因因此至少少需要出出动3车车次才能能够完成成这样的的投

12、送量量。同时时，当区区级第一一班次邮邮车088:000到达县县局X1之后需需要有11个小时时的时间间对邮件件进行集集中处理理；而当当第二班班次邮车车16:00从从县局XX1出发返返回地市市局D之前同同样需要要1个小小时对邮邮件进行行集中处处理，因因此县级级邮车工工作的时时间为99:00到到15:00之之间的66个小时时。以下分情情况讨论论各种出出车方案案：1方案案一：11辆车出出动3次次。利用上面面的Flloydd算法和和TSPP算法联联合求解解，可以以得到其其最短里里程数为为2799公里。以以县级邮邮车平均均时速330公里里计算，11辆车至至少需要要9个多多小时才才可以完完成，不不满足66小

13、时时时限的条条件。因因此此本本方案不不可行。2方案案二：22辆车各各出动22次。由算法得得到本方方案的最最短里程程为3334公里里，共需需6688分钟；再加上上16个个支局的的装卸时时间为880分钟钟，以及及2辆车车在县局局的装卸卸时间220分钟钟，总共共7688分钟。因因此平均均每辆车车耗时3384分分钟，超超过了66小时时时限。因因此本方方案也不不可行。3方案案三：22辆车，其其中1辆辆车出动动一次，另另1辆车车出动22次。运用以上上同样的的方法可可以得到到其最短短里程数数为3113公里里，根据据最高时时速300公里的的限制，可可得需要要6266分钟；再加上上16个个支局的的装卸时时间为8

14、80分钟钟，以及及其中一一辆车在在县局的的装卸时时间100分钟，共共7166分钟。因因此平均均每辆车车耗时3358分分钟，恰恰好满足足时间的的限制。再再考虑22辆车要要送166个支局局的因素素，则至至少有一一辆车需需要送88个支局局。通过过运行分分组判断断程序（程程序三）可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的。因此这种方案也不予考虑。4方案案四：33辆车各各出动11次。由于出动动的车次次相同，本本方案与与方案二二所需的的最短里里程数同同为3113公里里，总共共需时7716分分钟，平平均每辆辆车耗时时不到2239分分钟。由由于有33辆车，则则至少有有一辆车车需要投投送6个

15、个支局。再再运行分分组判断断程序则则可以知知道这样样的邮路路是存在在的。因因此本方方案可行行。4.1.3 最佳邮邮路的选选定方案案4.1.3.11 最最佳邮路路的确定定显然，本本问题被被转化为为将166个支局局分为33组，使使得3辆辆从县局局出发的的车辆可可以在66小时内内到达自自己组里里的所有有的支局局并及时时返回，同同时在邮邮车运行行过程中中运载的的邮包不不超过665袋且且经济损损失最小小。对于于运行过过程中邮邮包的变变化如表表1所示示：表1：各各支局邮邮件量及及变化情情况支局邮件量Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达局为为Z i的邮邮件量（袋

16、袋）101569136114131711211211314支局Z i收寄寄的邮件件量（袋袋）9145109101391596713151016过支局ZZ i邮件件量的变变化（袋袋）-1-1-11-44252-8-552-6-32根据题目目所给的的限制条条件，引引入贪心心算法的的概念。也也就是尽尽量让邮邮车“吃饱”，即让让空车率率损失保保持在较较低的水水平。最最后结合合Flooyd算算法重新新编制改改进型贪心算算法（具具体程序序见附件件程序四四），其其主要程程序流程程如下：Stepp 1：将所有有结点分分为三组组，并判判断其运运送的邮邮包量是是否超过过65。如如超过则则重新分分组，不不超过则则进

17、入下下一步。Stepp 2：计算出出3条遍遍历各分分组节点点的路径径，并记记录邮车车每经过过1个支支局时总总共损失失的金额额以及当当时运载载邮件的的数量。判判断运载载邮件量量是否超超过655，若超超过则重重复本步步骤，不不超过则则进入下下一步。Stepp 3：判断得得到的路路径是否否满足66小时的的时间限限制，若若超过66小时则则重复SStepp 2，不不超过则则记录下下损失金金额并进进入下一一步。Stepp 4：记录下下3条路路径的走走法及损损失的金金额，并并计算出出路径总总里程和和总损失失金额。Stepp 5：重复执执行Sttep 2。若若总损失失金额大大于先前前所得，则则重新执执行Stt

18、ep 2；若若总损失失金额小小于先前前所得，则则覆盖原原数据后后重新执执行Sttep 2；若若总损失失金额等等于先前前所得，则则判断总总里程数数，若小小于先前前所得则则覆盖原原数据重重新执行行Steep 22，否则则直接重重新执行行Steep 22Stepp 6：重新执执行Sttep 1，直直到找到到最小值值。利用以上上的改进进型贪心心算法，得得到邮路路规划如如表2所所示：表2：空空车损失失最小的的邮路规规划邮路耗时(分分钟)里程(公公里)损失(元元)X1115(不不装卸)1615(不装卸卸)56234X13481595.1008X111213114(不不装卸)1514X132515019.2

19、292X1110(不不装卸)9878(不装装卸)9(不装装卸)1110X132114822.6615457(总计)47.002(总总计)4.1.3.22 对对最佳邮邮路的改改进建议议以上方法法得到的的经济损损失的数数值固然然最小，但但是里程程数与理理论值3313差差距较大大，特别别是在邮邮车接近近满载时时程序会会选择较较长的路路线，因因为此时时空车率率极低（甚甚至为00），所所以即使使路线较较长但损损失却不不会过大大。不过过与现实实生活中中，运行行里程也也是要列列入成本本核算的的，所以以对上述述的改进进型贪心心算法稍稍作修改改：在SStepp 5中中不再将将所得数数据与先先前数据据相比较较，而

20、是是设定一一个阈值值（这里里选定的的是855），于于是可以以得到相相对较短短的3条条邮路如如表3：表3：更更符合实实际的改改进邮路路邮路耗时(分分钟)里程(公公里)损失(元元)X1110(不不装卸)9161514X11828110.449X111087654X124010519.111X11111213123X135616351.997349(总计)81.557(总总计)4.1.4 问问题1的的小结综上所述述，经过过建摸、编编程、计计算、求求解等过过程，我我们得出出至少需需要3辆辆邮车才才能满足足该县的的邮件运运输需求求。为了降低低空车率率从而达达到提高高邮政运运输效益益的目的的，根据据题意给

21、给出具体体的3条条邮路规规划如下下：（具具体的线线路示意意图见图图1）1X1115(不不装卸)1615(不装卸卸)56234X12X111213114(不不装卸)1514X13X1110(不不装卸)9878(不装装卸)9(不装装卸)1110X1 这样的的规划路路线可使使空车损损失金额额达到最最小的447.001元，总总里程为为4577公里。同时，从从实际出出发，进进一步给给出一种种兼顾空空车损失失金额和和总里程程数两方方面因素素的邮路路规划如如下：（具体的线路示意图见图2）1X1110(不装卸卸)9161514X12X111087654X13X11111213123X1这样的规规划路线线可使总

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

23、间约束其中：表示区区级及县县级邮车车集；。：表示区区级及县县级支局局集；。，分别表表示区级级及县局局集。；,表示示车辆从从结点到到结点。；,表示示车辆服服务于第第结点。显然,此此问题包包括四个个方面：第一、对对各个邮邮局点进进行合理理分组；第二、在在每组中中求出最最短回路路；第三三、判断断是否满满足时间间约束；第四、选选择总里里程较短短的线路路方式。4.2.2 具体方方案的实实施4.2.2.11 以以最小生生成树为为根据的的邮路初初步划分分由于单辆辆邮车的的最佳路路线问题题不存在在多项式式时间内内的精确确算法，而而图中节节点数较较多（总总共为779个），且且区级和和县级邮邮车所覆覆盖的路路线范

24、围围及路上上所消耗耗时间还还有诸多多限制，因因此我们们只能去去寻求一一种较合合理的划划分准则则对整个个区域进进行初步步划分。首先，分分别列出出从D点点到X11、X2、X3、X4、X5各支局局的最短短路，这这些最短短路构成成一棵从从D点出出发的数数枝，称称为干枝枝。又因因为各区区级支局局只能由由区级邮邮车运送送邮件，所所以在此此最小生生成树图图上需要要加上所所有的区区级支局局，并标标示其到到D点的的最短路路（见图图3）。图3：市市局到各各县局的的最小生生成树结结构图从图中可可以看出出，从点点出发到到5个支支局共有有5条干干枝，根根据实际际工作的的经验及及上述的的分析，在在分组时时应遵循循以下原原

25、则：1尽量量将同一一干枝上上及其分分枝上的的节点分分在同一一组；2尽量量将邻近近并连通通的节点点分在同同一组。3应让让短的干干枝和尽尽量多的的与其邻邻近的节节点分在在同一组组，而长长的干枝枝和较少少的与之之接近的的节点分分在同一一组。对于剩下下的各县县级支局局来说，根根据其与与市局及及本县县县局的关关联程度度，分别别给它们们赋予权权值。最最后依据据上述分分组原则则，再使使用SPPSS软软件求出出以下的的一种分分组情况况（见表表4）：表4：区区级邮车车到各县县局所需需要经过过的支局局第一组D，8，99，100，111，144，155，166，622，X1第二组D，188，277，633，644，

26、655，666，677，X2第三组D，288，299，300，311，322，333，344，355，688，699，700，X3第四组D，366，400，411，422，433，444，711，722，733，X4第五组D，522，533，588，599，600，611，X5根据以上上分组，使使用先前前的TSSP算法法程序可可以分别别得出每每辆区级级邮车运运行的最最佳路线线。（见见表5）表5：区区级邮车车的行驶驶路线路线里程数(公里)耗时(分分钟)到县局的的耗时(分钟)经停D622161511X114109862D226259105县局X11；支局局62，116，115，111，114，11

27、0，99，8D666636418X2276567D232259125县局X22；支局局66，663，664，118，227，665，667D6882933X32831303234357069D249295114县局X33；支局局68，229，333，228，331，330，332，334，335，770，669D7113641X4404344427372D24828484县局X44；支局局71，336，441，440，443，444，442，773，772D6115853X5525960D267286133县局X55；支局局61，558，553，552，559，660（注：表表中耗时时依据假假

28、设1算算定。）4.2.2.22 以以改进的的TSPP算法确确定的邮邮路最终终划分接下来将将原来的的TSPP算法程程序稍加加改动，为为其加上上时间限限制条件件。根据据假设22可知县县级邮车车需在第第一班次次区级邮邮车到达达县局之之后600分钟后后出发，但但有100分钟可可包含在在这个660分钟钟内，因因此对总总消耗时时间的影影响为550分钟钟；根据据假设33可知县县级邮车车需在第第二班次次区级邮邮车离开开县局之之前600分钟返返回；又又根据假假设4规规定的相相同路线线可知第第一班次次区级邮邮车到达达县局所所需的时时间与第第二班次次区级邮邮车从县县局返回回市局所所需的时时间之和和即为区区级邮车车完

29、成寄寄送县局局i工作作后返回回市局所所需要的的时间TTi。据此此可以得得到区级级邮车最最少总耗耗时。改改进的TTSP算算法程序序主要流流程如下下（具体体程序见见附件程程序五）：Stepp 1：求出县县中剩余余支局间间的最短短路径，并并解出、和。若大于于3000，则重重新执行行Steep 11。Stepp 2：判断是是否大于于7200。若小小于7220，则则计算下下一个县县；若大大于7220，则则将上述述支局分分为2组组，重新新计算。判判断是否否满足要要求，若若不满足足则重新新分组。如如此循环环Stepp 3：若分22组不能能满足要要求就进进一步将将其分为为3组，以以此类推推。Stepp 4：按

30、上述述步骤将将所有县县级的邮邮路计算算完毕。各县内的的具体邮邮路规划划如表66：表6：各各县级邮邮车的行行驶路线线路线里程(公公里)耗时(分分钟)经停X1111312X196207支局1，113，112X14457623X1126282支局4，55，7，66，2，33X211719X276162支局177，199X2221222324252620X2148331支局211，222，233，244，255，266， 220X43373839X492199支局377，388，399X555457565554(不装卸卸)X5132284支局544，577，566，555X55504948474546

31、51X5137309支局500，499，488，477，455，466，5114.2.2.22 具具体的邮邮车调度度方案根据题意意，可按按以下步步骤进行行邮车调调度：Stepp 1：第一班班次区级级邮车早早上066:000同时从从市局出出发开往往县局。Stepp 2：第一班班次区级级邮车到到达各县县局之后后10分分钟返回回，县级级邮车在在区级邮邮车到达达1小时时后出发发。Stepp 3：最后一一辆县级级邮车回回到县局局的时间间之后11小时就就是第二二班次区区级邮车车从该县县局的发发车时间间，若此此县无需需县级邮邮车或县县级邮车车回县局局时间较较早，发发车时间间可相应应延后。Stepp 4：由第

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

33、2D06:00007:44507:55510:119X1（第第二班）13:33015:11515:225(113:227)17:449X2（第第一班）D666636418X2276567D06:00008:00508:11510:119X2（第第二班）13:22115:22615:336(114:336)17:440X3（第第一班）D6882933X32831303234357069D06:00007:55408:00410:555X3（第第二班）13:00014:55415:004(无无)17:555X4（第第一班）D7113641X4404344427372D06:00007:22407:

34、33410:444X4（第第二班）13:00014:22414:334(111:443)17:444X5（第第一班）D6115853X5525960D06:00008:11308:22310:446X5（第第二班）13:00015:11315:223(114:222)17:446X1-11X1111312X108:44512:112X1-22X14457623X108:44513:227X2-11X211719X209:00512:114X2-22X2221222324252620X209:00514:336X4-11X43373839X408:22411:443X5-11X555049484

35、7454651X509:11314:222X5-22X555457565554(不装卸卸)X509:11313:557（注：表表中第二二班次区区级邮车车返回时时间栏中中括号内内的数值值为该县县县级邮邮车最晚晚的返回回时间。）4.2.3 问题22的小结结为了得到到符合题题目所提提出的全全部条件件的路线线规划结结果，我我们在这这里以最最小生成成树为依依据，先先对邮路路进行初初步的划划分，之之后使用用改进的的TSPP算法找找出其余余的线路路。本线线路规划划方案规规划邮路路12条条，需要要区级邮邮车5辆辆，县级级邮车77辆，共共计122辆邮车车；线路路总里程程20229公里里，全区区邮路运运行成本本6

36、0887元。为了使本本方案划划分出的的邮路得得到更直直观的表表现，我我们又制制作了分分县邮路路表（表表8）和和邮路示示意图（图图4）。表8：分分县邮路路表区内区级邮车车路线里程数(公里)县内县级邮车车路线里程数(公里)X1D622161511X114109862D226X1-11X1111312X196X1-22X14457623X1126X2D666636418X2276567D232X2-11X211719X276X2-22X2221222324252620X2148X3D6882933X32831303234357069D249无X4D7113641X4404344427372D248X

37、4-11X43373839X492X5D6115853X5525960D267X5-11X5550494847454651X5137X5-22X555457565554(不装卸卸)X5132图4：全全区邮路路示意图图4.3 问题题3的解解决4.3.1 解决方方案的确确定对于打破破行政区区划的邮邮件投送送，只需需考虑部部分县与与县交界界地带的的支局到到底由哪哪个支局局进行投投送即可可。本文文通过将将这些支支局分别别放入相相邻的两两个县并并计算最最佳哈密密顿圈（最最佳H圈圈）的方方法来确确定支局局的归属属。即将将此县级级支局并并入最佳佳哈密顿顿圈小的的那个县县。4.3.2 具体方方案的实实施4.3

38、.2.11 并并入邻县县邮路支支局的选选择根据问题题2所得得到的路路线图，334支局局、355支局和和44支支局都已已经并入入了邻县县的邮路路（由区区级邮车车完成投投寄任务务），只只有177支局和和27支支局有并并入邻县县邮路的的可能。先考虑117支局局的归属属，当其其没有并并入相邻邻县局XX1的邮车车运送范范围时，县县局X22加支局局1726的的最小哈哈密顿圈圈是2227公里里，县局局X1加支局局1116的最最小哈密密顿圈是是6233；如果果17支支局并入入相邻县县局X11的邮路路时，县县局X22加支局局1826的的最小哈哈密顿圈圈是1998，县县局X11加支局局1117的最最小哈密密顿圈是

39、是6300。（计计算最小小哈密顿顿圈的程程序见附附件之程程序六。）再再通过简简单的计计算有：2277+62231198+6300。可见见，单从从总里程程数的减减少上来来说，117支局局可以划划入X11邮车的的运送范范围。但但是，进进一步运运用改进进的TSSP算法法进行计计算后发发现，当当有时间间限制条条件时所所生成的的邮路里里程要大大于原先先的里程程，因此此把177支局划划入X11内不可可行。再考虑227支局局的归属属，当其其没有并并入相邻邻县局XX2的邮车车运送范范围时，县县局X33加支局局2733的的最小哈哈密顿圈圈是1776公里里，县局局X2加支局局1726的的最小哈哈密顿圈圈是2227

40、；如如果277支局并并入相邻邻县局XX2时 ，县县局X33加支局局2833的的最小哈哈密顿圈圈是1334，县县局X22加支局局1727的的最小哈哈密顿圈圈是2441。再再通过简简单的计计算有：1766+22271134+2411。很明明显，将将27支支局划入入X2邮车的的运送范范围能减减少里程程数，进进一步运运用改进进的TSSP算法法进行计计算后可可以得到到新的邮邮路规划划方案使使得里程程数有所所减少，因因此把227支局局划入XX2内是是可行的的。4.3.2.22 相相关邮路路的重新新规划通过以上上程序的的计算，可可以得到到新的邮邮路规划划。即将将原来DD到X22的路径径D66636418X2

41、276567D改为D666318X2646567D，新邮邮路经停停县局XX2和支局局66，663，664，118，665，667，里里程1999公里里，耗时时2244分钟，到到X2耗时997分钟钟。另外外，将原原先的邮邮路X221222324252620X2改为X22721222324252620X2，经停支支局277，211，222，233，244，266，255，200，里程程1699公里，耗耗时3778分钟钟。新的邮路路规划方方案还是是需要55辆区级级邮车和和7辆县县级邮车车，共112辆车车。总里里程降低低为20017公公里，运运行总成成本为660511元。4.3.3 问题33的小结结本方案通通过对比比最小哈哈密顿圈圈来确定定将支局局27划划归邻县县X2的邮路路以达到到减少总总里程数数并降低低成本的的目的。相相较于问问题2的的结果，总总里程数数降低了了12公公里，成成本下降降了366元。为了使本本方案划划分出的的邮路得得到更直直观的表表现，我我们又制制作了邮邮车调度度时刻表表（表99）和邮邮路示意意图（图图5）。表9：邮邮车调度度时刻表表邮车路线里程数(公里)出发时间间到达目的的地时间间返回时间间返回到达达时间X1（第第一班）D622161511X114109862D22606:00007:44507:55510:119X1（第第二班）13:3