1、交通运输邮政运输网络中的邮路规划和邮车调度优化研究（交通运输）邮政运输网络中的邮路规划和邮车调度优化研究邮政运输网络中的邮路规划和邮车调度问题1 问题重述 古往今来，邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展，邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况，本文提出了关于如何合理规划邮路的问题，具体内容如下：对一片有特定道路相连且有行政划分的地区进行邮路规划，有以下的问题需要解决：(1) 以县局X1及其所辖的16个支局Z1, Z2, , Z16(下文简称为1，2，)为研究对象。假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1
2、再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，在不超载的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的。(2) 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本的邮路规划。(3) 当县局可以跨县投寄时的邮路规划。(4) 选择最合适的县局地点，并重新规划邮路，使得运行的成本最低。2 模型假设1所有的邮车在邮路上均按照平均时速匀速行驶。2县局对市局送来邮件的集中处理时间(1小时)既包括区级邮车的装卸时间10分钟，也包括县级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸区级邮车的工作；而县级邮车的装卸工作最早在集中处
3、理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。3县局对将要送到市局的邮件的集中处理时间(1小时)既包括县级邮车的装卸时间10分钟，也包括区级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸县级邮车的工作；而区级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。4两班次的区级邮车行驶路线完全相同，若路线为环形则运行方向必须一致。如：D615853X5525960D与D605952X5535861D两种行车路线即为不同的两条路线。5问题4中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。3 符号说明：市级邮局：县级邮局：表示县级邮局的集
4、合：赋权邻接矩阵：Floyd算法中点到的距离。：Floyd算法中到之间的插入点。：Floyd算法中用插入顶点的方法依次构造出的距离矩阵。：Floyd算法中用插入顶点的方法依次构造出的路由矩阵。：表示无向图。：支局停留时间：县局停留时间：区级邮车时速：县局邮件集中处理时间：县级邮车时速：区级邮车完成寄送县局工作后返回市局所需要的时间：县级邮车在县内走完第条邮路所需要的时间：开往县的第一班次区级邮车开出市局与第二班次区级邮车到达市局所需要的时间。：在各点设立服务设施的最大服务距离4 模型建立与求解4.1 问题1的解决4.1.1 模型的建立根据题意，问题一可以归纳为如下数学模型。其中：表示邮路方案；
5、表示空置损失费；表示方案的总路径；P表示邮路方案集。4.1.2 方案的比较与确定根据题目要求，需要在限定的时间内完成投送邮件的工作。首先，很自然地想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。4.1.2.1 Floyd算法Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵，使最后得到的矩阵成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。此算法的主要程序流程如下：Step 1：输入赋权邻接矩阵，Step 2：赋初值：对所有，。更新，：对所有，若，则： Step 3：若，停止，输出、；否则，重复Step 1。依照题目所给定数据得
6、到的Floyd算法需要的赋权邻接矩阵如下：0274417112742infinfinf202521211827inf270312749infinfinfinfinfinfinf522141infinf4431019inf2732infinfinf47infinfinf50infinf172719014infinfinfinfinf30infinfinf31infinf1149inf1401320infinf2815infinfinf15253027inf27inf130921inf2626infinfinf2829inf42inf32inf209013inf32infinfinfinfinf3
7、3infinfinfinfinfinf2113019infinfinfinfinfinfinfinfinfinfinfinfinfinfinf1901120infinfinfinf3321infinfinfinf282632inf1101020infinf29141320inf47301526infinf2010018infinf1492025infinfinfinfinfinfinfinf2018023infinf14inf2152infinfinfinfinfinfinfinfinf2302722infinf2121infinfinfinfinfinfinfinfinfinf270infi
8、nfinf184150311528infinfinf2914inf22inf011inf27infinfinf252933inf3314914infinf1109infinfinfinf30infinfinf211320infinfinfinf90（注：此矩阵中的inf表示邮局间无直达公路） 具体程序见附件之程序一4.1.2.2 TSP算法本文需要求解的每路邮车路线（区级或县级），若用顶点表示邮车经过的邮局（市局、县局或支局），边表示连接两邮局的公路，边上的权表示距离。实际我们的问题就是在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。定义：在加权图中；(1)权最小的哈密顿圈称为最佳H圈
9、。 (2)经过每个顶点至少一次的权的闭通路称为最佳邮车路线。最佳邮车路线问题可转化为最佳H圈问题，也称为TSP问题。方法是由给顶的图构造一个以V为顶点集的完备图,的每条边的权等于顶点与在图中最短路的权,即： 定理：加权图的最佳邮车路线的权与的最佳H圈的权相同。算法：求加权图的最佳邮路的近似算法：1用Floyd算法求出G中任意两点间的最短路，构造出完备图；2输入图的一个出始圈；3用算法产生一个初始H圈；4随机搜索出中若干个H圈，例如20000个；5对第2、3、4步所得的每个H圈，用二次逐次修正算法进行优化，得到近似最佳H圈；6在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解
10、。具体程序见附件之程序二。4.1.2.3 最少车辆的确定根据题目的要求，寄达县局Z1的邮件量为176袋，而收寄的邮件量为170袋，同时每一辆县级邮车最多容纳65袋邮件，因此至少需要出动3车次才能够完成这样的投送量。同时，当区级第一班次邮车08:00到达县局X1之后需要有1个小时的时间对邮件进行集中处理；而当第二班次邮车16:00从县局X1出发返回地市局D之前同样需要1个小时对邮件进行集中处理，因此县级邮车工作的时间为9:00到15:00之间的6个小时。以下分情况讨论各种出车方案：1方案一：1辆车出动3次。利用上面的Floyd算法和TSP算法联合求解，可以得到其最短里程数为279公里。以县级邮车
11、平均时速30公里计算，1辆车至少需要9个多小时才可以完成，不满足6小时时限的条件。因此此本方案不可行。2方案二：2辆车各出动2次。由算法得到本方案的最短里程为334公里，共需668分钟；再加上16个支局的装卸时间为80分钟，以及2辆车在县局的装卸时间20分钟，总共768分钟。因此平均每辆车耗时384分钟，超过了6小时时限。因此本方案也不可行。3方案三：2辆车，其中1辆车出动一次，另1辆车出动2次。运用以上同样的方法可以得到其最短里程数为313公里，根据最高时速30公里的限制，可得需要626分钟；再加上16个支局的装卸时间为80分钟，以及其中一辆车在县局的装卸时间10分钟，共716分钟。因此平均
12、每辆车耗时358分钟，恰好满足时间的限制。再考虑2辆车要送16个支局的因素，则至少有一辆车需要送8个支局。通过运行分组判断程序（程序三）可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的。因此这种方案也不予考虑。4方案四：3辆车各出动1次。由于出动的车次相同，本方案与方案二所需的最短里程数同为313公里，总共需时716分钟，平均每辆车耗时不到239分钟。由于有3辆车，则至少有一辆车需要投送6个支局。再运行分组判断程序则可以知道这样的邮路是存在的。因此本方案可行。4.1.3 最佳邮路的选定方案4.1.3.1 最佳邮路的确定显然，本问题被转化为将16个支局分为3组，使得3辆从县局出发的
13、车辆可以在6小时内到达自己组里的所有的支局并及时返回，同时在邮车运行过程中运载的邮包不超过65袋且经济损失最小。对于运行过程中邮包的变化如表1所示：表1：各支局邮件量及变化情况Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达局为Z i的邮件量（袋）101569136114131711211211314支局Z i收寄的邮件量（袋）9145109101391596713151016过支局Z i邮件量的变化（袋）-1-1-11-44252-8-552-6-32根据题目所给的限制条件，引入贪心算法的概念。也就是尽量让邮车“吃饱”，即让空车率损失保持在较低的水平。最后结
14、合Floyd算法重新编制改进型贪心算法（具体程序见附件程序四），其主要程序流程如下：Step 1：将所有结点分为三组，并判断其运送的邮包量是否超过65。如超过则重新分组，不超过则进入下一步。Step 2：计算出3条遍历各分组节点的路径，并记录邮车每经过1个支局时总共损失的金额以及当时运载邮件的数量。判断运载邮件量是否超过65，若超过则重复本步骤，不超过则进入下一步。Step 3：判断得到的路径是否满足6小时的时间限制，若超过6小时则重复Step 2，不超过则记录下损失金额并进入下一步。Step 4：记录下3条路径的走法及损失的金额，并计算出路径总里程和总损失金额。Step 5：重复执行Step
15、 2。若总损失金额大于先前所得，则重新执行Step 2；若总损失金额小于先前所得，则覆盖原数据后重新执行Step 2；若总损失金额等于先前所得，则判断总里程数，若小于先前所得则覆盖原数据重新执行Step 2，否则直接重新执行Step 2Step 6：重新执行Step 1，直到找到最小值。利用以上的改进型贪心算法，得到邮路规划如表2所示：表2：空车损失最小的邮路规划邮路耗时(分钟)里程(公里)损失(元)X115(不装卸)1615(不装卸)56234X13481595.108X11213114(不装卸)1514X132515019.292X110(不装卸)9878(不装卸) 9(不装卸)1110X
16、132114822.615457(总计)47.02(总计)4.1.3.2 对最佳邮路的改进建议以上方法得到的经济损失的数值固然最小，但是里程数与理论值313差距较大，特别是在邮车接近满载时程序会选择较长的路线，因为此时空车率极低（甚至为0），所以即使路线较长但损失却不会过大。不过与现实生活中，运行里程也是要列入成本核算的，所以对上述的改进型贪心算法稍作修改：在Step 5中不再将所得数据与先前数据相比较，而是设定一个阈值（这里选定的是85），于是可以得到相对较短的3条邮路如表3：表3：更符合实际的改进邮路邮路耗时(分钟)里程(公里)损失(元)X110(不装卸)9161514X11828110.
17、49X11087654X124010519.11X1111213123X135616351.97349(总计)81.57(总计)4.1.4 问题1的小结综上所述，经过建摸、编程、计算、求解等过程，我们得出至少需要3辆邮车才能满足该县的邮件运输需求。为了降低空车率从而达到提高邮政运输效益的目的，根据题意给出具体的3条邮路规划如下：（具体的线路示意图见图1）1X115(不装卸)1615(不装卸)56234X12X11213114(不装卸)1514X13X110(不装卸)9878(不装卸) 9(不装卸)1110X1 这样的规划路线可使空车损失金额达到最小的47.01元，总里程为457公里。同时，从实
18、际出发，进一步给出一种兼顾空车损失金额和总里程数两方面因素的邮路规划如下：（具体的线路示意图见图2）1X110(不装卸)9161514X12X11087654X13X1111213123X1这样的规划路线可使总里程数降为349公里，空车损失金额为81.57元，。图1：空车损失最小的路线示意图图2：兼顾两方面因素的路线示意图4.2 问题2的解决4.2.1 总体方案的选定及模型建立要选择里程最短的路线首先应当考虑对整个区域采用环形邮路进行规划，但是由于有一整套严格的规定，这种方法显然是不可取的。而若采用辐射形邮路，根据题目所提供的信息便可以知道这种方法虽然能够满足时限要求，但所得路径的里程却很长。
19、因此，混合形邮路就成了必然的选择。问题二的数学模型如下： 车辆集满足时间约束其中：表示区级及县级邮车集；。：表示区级及县级支局集；。，分别表示区级及县局集。；,表示车辆从结点到结点。；,表示车辆服务于第结点。显然,此问题包括四个方面：第一、对各个邮局点进行合理分组；第二、在每组中求出最短回路；第三、判断是否满足时间约束；第四、选择总里程较短的线路方式。4.2.2 具体方案的实施4.2.2.1 以最小生成树为根据的邮路初步划分由于单辆邮车的最佳路线问题不存在多项式时间内的精确算法，而图中节点数较多（总共为79个），且区级和县级邮车所覆盖的路线范围及路上所消耗时间还有诸多限制，因此我们只能去寻求一
20、种较合理的划分准则对整个区域进行初步划分。首先，分别列出从D点到X1、X2、X3、X4、X5各支局的最短路，这些最短路构成一棵从D点出发的数枝，称为干枝。又因为各区级支局只能由区级邮车运送邮件，所以在此最小生成树图上需要加上所有的区级支局，并标示其到D点的最短路（见图3）。图3：市局到各县局的最小生成树结构图从图中可以看出，从点出发到5个支局共有5条干枝，根据实际工作的经验及上述的分析，在分组时应遵循以下原则：1尽量将同一干枝上及其分枝上的节点分在同一组；2尽量将邻近并连通的节点分在同一组。3应让短的干枝和尽量多的与其邻近的节点分在同一组，而长的干枝和较少的与之接近的节点分在同一组。对于剩下的
21、各县级支局来说，根据其与市局及本县县局的关联程度，分别给它们赋予权值。最后依据上述分组原则，再使用SPSS软件求出以下的一种分组情况（见表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：区级邮车的行
22、驶路线路线里程数(公里)耗时(分钟)到县局的耗时(分钟)经停D62161511X114109862D226259105县局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，72D615853X5525960D267286
23、133县局X5；支局61，58，53，52，59，60（注：表中耗时依据假设1算定。）4.2.2.2 以改进的TSP算法确定的邮路最终划分接下来将原来的TSP算法程序稍加改动，为其加上时间限制条件。根据假设2可知县级邮车需在第一班次区级邮车到达县局之后60分钟后出发，但有10分钟可包含在这个60分钟内，因此对总消耗时间的影响为50分钟；根据假设3可知县级邮车需在第二班次区级邮车离开县局之前60分钟返回；又根据假设4规定的相同路线可知第一班次区级邮车到达县局所需的时间与第二班次区级邮车从县局返回市局所需的时间之和即为区级邮车完成寄送县局i工作后返回市局所需要的时间Ti。据此可以得到区级邮车最少总
24、耗时。改进的TSP算法程序主要流程如下（具体程序见附件程序五）：Step 1：求出县中剩余支局间的最短路径，并解出、和。若大于300，则重新执行Step 1。Step 2：判断是否大于720。若小于720，则计算下一个县；若大于720，则将上述支局分为2组，重新计算。判断是否满足要求，若不满足则重新分组。如此循环Step 3：若分2组不能满足要求就进一步将其分为3组，以此类推。Step 4：按上述步骤将所有县级的邮路计算完毕。各县内的具体邮路规划如表6：表6：各县级邮车的行驶路线路线里程(公里)耗时(分钟)经停X111312X196207支局1，13，12X1457623X1126282支局4
25、，5，7，6，2，3X21719X276162支局17，19X221222324252620X2148331支局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小时后出
26、发。Step 3：最后一辆县级邮车回到县局的时间之后1小时就是第二班次区级邮车从该县局的发车时间，若此县无需县级邮车或县级邮车回县局时间较早，发车时间可相应延后。Step 4：由第二班次区级邮车于各县局的发车时刻可倒推出区级邮车到达县局的时刻以及由市局出发的时刻，并检验此出发时刻是否晚于第一班次 区级邮车回到市局的时刻，若不相符合则调后第二班次区级邮车的发车时刻。Step 5：根据以上的时刻信息计算出第二班次区级邮车返回到达市局的时刻，并检验是否超过18:00，若超过18:00则重新调整。最后得到邮车调度时刻表（见表7）如下：表7：邮车调度时刻表邮车路线出发时间到达目的地时间返回时间返回到达时
27、间X1（第一班）D62161511X114109862D06:0007:4507:5510:19X1（第二班）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:0008:1308:2310:46X5（第二班）13:0015:1315:23(14:22)17:46X1-1X111312X108
