邮政运输网络中的邮路规划和邮车调度问题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 中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。3 符号说明：市级邮局：县级邮局：表示县级邮局的集合：赋权邻接矩阵：Floyd 算法中点 到的距离。：Floyd 算法中 到之间的插入点。：Floyd 算法中用插入顶点的方法依次构造出的距离矩阵。：Floyd 算法中用插入顶点的方法依次构造出的路由矩阵。：表示无向图。：支局停留时间：县局停留时间：区级邮车时速：县局邮件集中处理时间：县级邮车时速：区级邮车完成...
