文档介绍：..页眉.. 页脚.. 邮政运输网络中的邮路规划和邮车调度问题 1 问题重述古往今来,邮政在人们的生活中都扮演着不可或缺的角色。随着时代的发展, 邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情况,本文提出了关于如何合理规划邮路的问题,具体内容如下: 对一片有特定道路相连且有行政划分的地区进行邮路规划,有以下的问题需要解决: (1) 以县局X 1及其所辖的16个支局Z 1,Z 2,……,Z 16(下文简称为1,2,……) 为研究对象。假设区级第一班次邮车08:0 0到达县局X 1,区级第二班次邮车16:0 0 从县局 X 1 再出发返回地市局 D ,若每辆县级邮车最多容纳 65 袋邮件, 在不超载的情况下,利用最少的车辆和最短的邮路,达到减少空车损失的目的。(2) 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投入,从而显著降低全区邮政运输网的总运行成本的邮路规划。(3) 当县局可以跨县投寄时的邮路规划。(4) 选择最合适的县局地点,并重新规划邮路,使得运行的成本最低。 2 模型假设 。 (1小时)既包括区级邮车的装卸时间 10 分钟,也包括县级邮车的装卸时间 10分钟。且在这 1个小时的起始阶段进行装卸区级邮车的工作;而县级邮车的装卸工作最早在集中处理工作结束前 10 分钟进行,也可以在集中处理工作结束之后进行。 3 .县局对将要送到市局的邮件的集中处理时间(1 小时) 既包括县级邮车的装卸时间 10 分钟,也包括区级邮车的装卸时间 10 分钟。且在这 1 个小时的起始阶段进行装卸县级邮车的工作;而区级邮车的装卸工作最早在集中处理工作结束前 10分钟进行,也可以在集中处理工作结束之后进行。 4 .两班次的区级邮车行驶路线完全相同,若路线为环形则运行方向必须一致。如:D→61→58→53→X 5→52→59→60→D与D→60→59→52→X 5→53→58→61 →D两种行车路线即为不同的两条路线。 4中选定县局后,县级邮车不得打破行政区划限制而跨县投寄。..页眉.. 页脚.. 3 符号说明 D :市级邮局 iX :县级邮局?? 1 2 3 4 5 , , , , X X X X X X ?:表示县级邮局的集合( , ) W i j :赋权邻接矩阵( , ) L i j :Floyd 算法中点 i 到j 的距离。( , ) R i j :Floyd 算法中 i 到j 之间的插入点。( . ) l i j :Floyd 算法中用插入顶点的方法依次构造出的距离矩阵。( , ) r i j :Floyd 算法中用插入顶点的方法依次构造出的路由矩阵。( , ) G V E ?:表示无向图。 zt :支局停留时间 Xt :县局停留时间 qs :区级邮车时速 clt :县局邮件集中处理时间 xs :县级邮车时速 iT :区级邮车完成寄送县局 i 工作后返回市局所需要的时间 i jt ?:县级邮车在县 iX 内走完第 j 条邮路所需要的时间 i Time :开往县 iX 的第一班次区级邮车开出市局与第二班次区级邮车到达市局所需要的时间。?? i S v :在各点 iv 设立服务设施的最大服务距离..页眉.. 页脚.. 4 模型建立与求解 问题 1 的解决 模型的建立根据题意,问题一可以归纳为如下数学模型。 1 2 1 2 1 2 min ( , , , ) min ( , , , ) . .( , , , ) kkk C P P P Lg P P P s t P P P P ???????????? ?其中: 1 2 ( , , , ) k P P P ???表示邮路方案; 1 2 ( , , , ) k C P P P ???表示空置损失费; 1 2 ( , , , ) k Lg P P P ???表示方案的总路径; P表示邮路方案集。 方案的比较与确定根据题目要求,需要在限定的时间内完成投送邮件的工作。首先,很自然地想到求出能够遍历这些点的最短路径,从理论上初步判断需要的车辆数。 Floyd 算法 Floyd 算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵(1) (2) ( ) v L L L ???、、、,使最后得到的矩阵( ) vL 成为图的距离矩阵, 同时也求出插入点矩阵以便得到两点间的最短路径。此算法的主要程序流程如下: Step 1:输入赋权邻接矩阵( , ) W i j , Step 2:赋初值:对所有 i ,j , ( ,