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

-1-邮政运输网络中的邮路规划和邮车调度问题1问题重述古往今来，邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展，邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况，本文提出了关于如何合理规划邮路的问题，具体内容如下：对一片有特定道路相连且有行政划分的地区进行邮路规划，有以下的问题需要解决：(1)以县局X1及其所辖的16个支局Z1,Z2,……,Z16(下文简称为1，2，……)为研究对象。假设区级第一班次邮车08:00到达县局X1，区级第二班次邮车16:00从县局X1再出发返回地市局D，若每辆县级邮车最多容纳65袋邮件，在不超载的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的。(2)采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入，从而显著降低全区邮政运输网的总运行成本的邮路规划。(3)当县局可以跨县投寄时的邮路规划。(4)选择最合适的县局地点，并重新规划邮路，使得运行的成本最低。2模型假设1．所有的邮车在邮路上均按照平均时速匀速行驶。2．县局对市局送来邮件的集中处理时间(1小时)既包括区级邮车的装卸时间10分钟，也包括县级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸区级邮车的工作；而县级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。3．县局对将要送到市局的邮件的集中处理时间(1小时)既包括县级邮车的装卸时间10分钟，也包括区级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行装卸县级邮车的工作；而区级邮车的装卸工作最早在集中处理工作结束前10分钟进行，也可以在集中处理工作结束之后进行。4．两班次的区级邮车行驶路线完全相同，若路线为环形则运行方向必须一致。如：D→61→58→53→X5→52→59→60→D与D→60→59→52→X5→53→58→61→D两种行车路线即为不同的两条路线。5．问题4中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。-2-3符号说明D：市级邮局iX：县级邮局12345,,,,XXXXXX：表示县级邮局的集合(,)Wij：赋权邻接矩阵(,)Lij：Floyd算法中点i到j的距离。(,)Rij：Floyd算法中i到j之间的插入点。(.)lij：Floyd算法中用插入顶点的方法依次构造出的距离矩阵。(,)rij：Floyd算法中用插入顶点的方法依次构造出的路由矩阵。(,)GVE：表示无向图。zt：支局停留时间Xt：县局停留时间qs：区级邮车时速clt：县局邮件集中处理时间xs：县级邮车时速iT：区级邮车完成寄送县局i工作后返回市局所需要的时间ijt：县级邮车在县iX内走完第j条邮路所需要的时间iTime：开往县iX的第一班次区级邮车开出市局与第二班次区级邮车到达市局所需要的时间。iSv：在各点iv设立服务设施的最大服务距离-3-4模型建立与求解4.1问题1的解决4.1.1模型的建立根据题意，问题一可以归纳为如下数学模型。121212min(,,,)min(,,,)..(,,,)kkkCPPPLgPPPstPPPP其中：12(,,,)kPPP表示邮路方案；12(,,,)kCPPP表示空置损失费；12(,,,)kLgPPP表示方案的总路径；P表示邮路方案集。4.1.2方案的比较与确定根据题目要求，需要在限定的时间内完成投送邮件的工作。首先，很自然地想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。4.1.2.1Floyd算法Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵(1)(2)()vLLL、、、，使最后得到的矩阵()vL成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。此算法的主要程序流程如下：Step1：输入赋权邻接矩阵(,)Wij，Step2：赋初值：对所有i，j，(,)(,)lijWij，(,)rijj，1k。更新(,)lij，(,)rij：对所有i，j，若(,)(,)(,)liklkjlij，则：(,)(,)(,),(,)lijliklkjrijkStep3：若kv，停止，输出(,)(,)Lijlij、(,)(,)Rijrij；否则1kk，重复Step1。-4-依照题目所给定数据得到的Floyd算法需要的赋权邻接矩阵如下：0274417112742infinfinf202521211827inf270312749infinfinfinfinfinfinf522141infinf4431019inf2732infinfinf47infinfinf50infinf172719014infinfinfinfinf30infinfinf31infinf1149inf1401320infinf2815infinfinf15253027inf27inf130921inf2626infinfinf2829inf42inf32inf209013inf32infinfinfinfinf33infinfinfinfinfinf2113019infinfinfinfinfinfinfinfinfinfinfinfinfinfinf1901120infinfinfinf3321infinfinfinf282632inf1101020infinf29141320inf47301526infinf2010018infinf1492025infinfinfinfinfinfinfinf2018023infinf14inf2152infinfinfinfinfinfinfinfinf2302722infinf2121infinfinfinfinfinfinfinfinfinf270infinfinf184150311528infinfinf2914inf22inf011inf27infinfinf252933inf3314914infinf1109infinfinfinf30infinfinf211320infinfinfinf90（注：此矩阵中的inf表示邮局间无直达公路）具体程序见附件之程序一4.1.2.2TSP算法本文需要求解的每路邮车路线（区级或县级），若用顶点表示邮车经过的邮局（市局、县局或支局），边表示连接两邮局的公路，边上的权表示距离。实际我们的问题就是在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。定义：在加权图(,)GVE中；(1)权最小的哈密顿圈称为最佳H圈。(2)经过每个顶点至少一次的权的闭通路称为最佳邮车路线。最佳邮车路线问题可转化为最佳H圈问题，也称为TSP问题。方法是由给顶的图(,)GVE构造一个以V为顶点集的完备图'(,')GVE,'E的每条边(,)xy的权等于顶点x与y在图中最短路的权,即：,',(,)min(,)GxyExydxy定理：加权图G的最佳邮车路线的权与'G的最佳H圈的权相同。算法：求加权图(,)GVE的最佳邮路的近似算法：1．用Floyd算法求出G中任意两点间的最短路，构造出完备图'(,')GVE；2．输入图'G的一个出始圈；3．用算法产生一个初始H圈；4．随机搜索出'G中若干个H圈，例如20000个；-5-5．对第2、3、4步所得的每个H圈，用二次逐次修正算法进行优化，得到近似最佳H圈；6．在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。具体程序见附件之程序二。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公里。以县级邮车平均时速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分钟。因此平均每辆车耗时358分钟，恰好满足时间的限制。再考虑2辆车要送16个支局的因素，则至少有一辆车需要送8个支局。通过运行分组判断程序（程序三）可以得到的结论是：在6个小时的时间限制下，这样的邮路是不存在的。因此这种方案也不予考虑。4．方案四：3辆车各出动1次。由于出动的车次相同，本方案与方案二所需的最短里程数同为313公里，总共需时716分钟，平均每辆车耗时不到239分钟。由于有3辆车，则至少有一辆车需要投送6个支局。再运行分组判断程序则可以知道这样的邮路是存在的。因此本方案可行。4.1.3最佳邮路的选定方案4.1.3.1最佳邮路的确定显然，本问题被转化为将16个支局分为3组，使得3辆从县局出发的车辆可以在6小时内到达自己组里的所有的支局并及时返回，同时在邮车运行过程中运载-6-的邮包不超过65袋且经济损失最小。对于运行过程中邮包的变化如表1所示：表1：各支局邮件量及变化情况Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄达局为Zi的邮件量（袋）101569136114131711211211314支局Zi收寄的邮件量（袋）9145109101391596713151016过支局Zi邮件量的变化（袋）-1-1-11-44252-8-552-6-32根据题目所给的限制条件，引入贪心算法的概念。也就是尽量让邮车“吃饱”，即让空车率损失保持在较低的水平。最后结合Floyd算法重新编制改进型贪心算法（具体程序见附件程序四），其主要程序流程如下：Step1：将所有结点分为三组，并判断其运送的邮包量是否超过65。如超过则重新分组，不超过则进入下一步。Step2：计算出3条遍历各分组节点的路径，并记录邮车每经过1个支局时总共损失的金额以及当时运载邮件的数量。判断运载邮件量是否超过65，若超过则重复本步骤，不超过则进入下一步。Step3：判断得到的路径是否满足6小时的时间限制，若超过6小时则重复Step2，不超过则记录下损失金额并进入下一步。Step4：记录下3条路径的走法及损失的金额，并计算出路径总里程和总损失金额。Step5：重复执行Step2。若总损失金额大于先前所得，则重新执行Step2；若总损失金额小于先前所得，则覆盖原数据后重新执行Step2；若总损失金额等于先前所得，则判断总里程数，若小于先前所得则覆盖原数据重新执行Step2，否则直接重新执行Step2Step6：重新执行Step1，直到找到最小值。利用以上的改进型贪心算法，得到邮路规划如表2所示：表2：空车损失最小的邮路规划邮路耗时(分钟)里程(公里)损失(元)X1→15(不装卸)→16→15(不装卸)→5→6→2→3→4→X13481595.108X1→12→13→1→14(不装卸)→15→14→X132515019.292X1→10(不装卸)→9→8→7→8(不装卸)→9(不装卸)→11→10→X132114822.615457(总计)47.02(总计)4.1.3.2对最佳邮路的改进建议以上方法得到的经济损失的数值固然最小，但是里程数与理论值313差距较大，