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

《邮政运输网络中邮路规划和邮车调度优化应用的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、.1问题重述-1-2模型假设-2-3符号说明-2-4模型建立与求解-3-4.1问题1的解决-3-4.1.1模型的建立-3-4.1.2方案的比较与确定-3-4.1.2.2TSP算法-4-4.1.2.3最少车辆的确定-5-4.1.3最佳邮路的选定方案-6-4.1.3.1最佳邮路的确定-6-4.1.3.2对最佳邮路的改进建议-7-4.1.4问题1的小结-7-4.2问题2的解决104.2.1总体方案的选定及模型建立104.2.2具体方案的实施114.2.2.1以最小生成树为根据的邮路初步划分114.2.2.2以改进的TSP算法确定的邮路最

2、终划分124.2.2.2具体的邮车调度方案134.2.3问题2的小结154.3问题3的解决174.3.1解决方案的确定174.3.2具体方案的实施174.3.2.1并入邻县邮路支局的选择174.3.2.2相关邮路的重新规划174.3.3问题3的小结184.4问题4的解决204.4.1解决方案的确定204.4.2方案的具体实施204.4.2.1各县级邮局选址的确定204.4.2.2重新调整部分县局位置后的邮路划分204.4.3关于上报省局网运处的书面材料224.4.4问题4的小结22参考文献：25附件:26..邮政运输网络中的邮路规

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

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

5、作最早在集中处理工作结束前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两种行车路线即为不同的两条路线

6、。5．问题4中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。3符号说明：市级邮局：县级邮局..：表示县级邮局的集合：赋权邻接矩阵：Floyd算法中点到的距离。：Floyd算法中到之间的插入点。：Floyd算法中用插入顶点的方法依次构造出的距离矩阵。：Floyd算法中用插入顶点的方法依次构造出的路由矩阵。：表示无向图。：支局停留时间：县局停留时间：区级邮车时速：县局邮件集中处理时间：县级邮车时速：区级邮车完成寄送县局工作后返回市局所需要的时间：县级邮车在县内走完第条邮路所需要的时间：开往县的第一班次区级邮车开出市局与第二班次区

7、级邮车到达市局所需要的时间。：在各点设立服务设施的最大服务距离4模型建立与求解4.1问题1的解决4.1.1模型的建立根据题意，问题一可以归纳为如下数学模型。..其中：表示邮路方案；表示空置损失费；表示方案的总路径；P表示邮路方案集。4.1.2方案的比较与确定根据题目要求，需要在限定的时间内完成投送邮件的工作。首先，很自然地想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。4.1.2.1Floyd算法Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵，使最后得到的矩阵成为图的距离矩阵

8、，同时也求出插入点矩阵以便得到两点间的最短路径。此算法的主要程序流程如下：Step1：输入赋权邻接矩阵，Step2：赋初值：对所有，，，，。更新，：对所有，，若，则：Step3：若，停止，输出、；否则，重复Step1。依照题目所给定数据得到的Flo