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

1 问题重述 - 1 - 2 模型假设 - 2 - 3 符号说明 - 2 - 4 模型建立与求解 - 3 - 4.1 问题1的解决 - 3 - 4.1.1 模型的建立 - 3 - 4.1.2 方案的比较与确定 - 3 - TSP算法 - 4 - 最少车辆的确定 - 5 - 4.1.3 最佳邮路的选定方案 - 6 - 最佳邮路的确定 - 6 - 对最佳邮路的改进建议 - 7 - 4.1.4 问题1的小结 - 7 - 4.2 问题2的解决 10 4.2.1 总体方案的选定及模型建立 10 4.2.2 具体方案的实施 11 以最小生成树为根据的邮路初步划分 11 以改进的TSP算法确定的邮路最终划分 12 具体的邮车调度方案 13 4.2.3 问题2的小结 15 4.3 问题3的解决 17 4.3.1 解决方案的确定 17 4.3.2 具体方案的实施 17 并入邻县邮路支局的选择 17 相关邮路的重新规划 17 4.3.3 问题3的小结 18 4.4 问题4的解决 20 4.4.1 解决方案的确定 20 4.4.2 方案的具体实施 20 各县级邮局选址的确定 20 重新调整部分县局位置后的邮路划分 20 4.4.3 关于上报省局网运处的书面材料 22 4.4.4 问题4的小结 22 参考文献： 25 附件: 26 邮政运输网络中的邮路规划和邮车调度问题 1 问题重述 古往今来，邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展，邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况，本文提出了关于如何合理规划邮路的问题，具体内容如下： 对一片有特定道路相连且有行政划分的地区进行邮路规划，有以下的问题需要解决： (1) 以县局X1及其所辖的16(18)个支局Z1, Z2, ……, Z16(下文简称为1，2，……)为研究对象。假设区级第一班次邮车08:00(6: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中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。 3 符号说明 ：市级邮局 ：县级邮局 ：表示县级邮局的集合 ：赋权邻接矩阵 ：Floyd算法中点到的距离。 ：Floyd算法中到之间的插入点。 ：Floyd算法中用插入顶点的方法依次构造出的距离矩阵。 ：Floyd算法中用插入顶点的方法依次构造出的路由矩阵。 ：表示无向图。 ：支局停留时间 ：县局停留时间 ：区级邮车时速 ：县局邮件集中处理时间 ：县级邮车时速 ：区级邮车完成寄送县局工作后返回市局所需要的时间 ：县级邮车在县内走完第条邮路所需要的时间 ：开往县的第一班次区级邮车开出市局与第二班次区级邮车到达市局所需要的时间。 ：在各点设立服务设施的最大服务距离 4 模型建立与求解 4.1 问题1的解决 4.1.1 模型的建立 根据题意，问题一可以归纳为如下数学模型。 其中：表示邮路方案；表示空置损失费； 表示方案的总路径；P表示邮路方案集。 4.1.2 方案的比较与确定 根据题目要求，需要在限定的时间内完成投送邮件的工作。首先，很自然地想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。 Floyd算法 Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法