邮政运输网络中的邮路规划和邮车调度优化研究(2).doc

: .
邮政运输网络中的邮路规划和邮车调度问题
1问题重述
古往今来，邮政在人们的生活中都扮演着不可或缺的角色。 随着时代的发展，
邮件投送的时限和成本成了邮政运输问题的关键因素。根据题目给出的实际情 况，本文提出了关于如何合理规划邮路的问题，具体内容如下：
对一片有特定道路相连且有行政划分的地区进行邮路规划， 有以下的问题需
要解决：
(1) 以县局X1及其所辖的16个支局Zi, Z2,……,Z16(下文简称为1,2,……) 为研究对象。假设区级第一班次邮车08:00到达县局％,区级第二班次邮车16:00 从县局X再出发返回地市局D,若每辆县级邮车最多容纳 65袋邮件，在不超载 的情况下，利用最少的车辆和最短的邮路，达到减少空车损失的目的。
(2) 采用尽可能少、尽可能短的邮路可以减少邮政部门车辆和人员等的投 入，从而显著降低全区邮政运输网的总运行成本的邮路规划。
(3) 当县局可以跨县投寄时的邮路规划。
(4) 选择最合适的县局地点，并重新规划邮路，使得运行的成本最低。
2模型假设
1 •所有的邮车在邮路上均按照平均时速匀速行驶。
2 •县局对市局送来邮件的集中处理时间(1小时)既包括区级邮车的装卸时间10
分钟，也包括县级邮车的装卸时间10分钟。且在这1个小时的起始阶段进行 装卸区级邮车的工作；而县级邮车的装卸工作最早在集中处理工作结束前 10
分钟进行，也可以在集中处理工作结束之后进行。
3•县局对将要送到市局的邮件的集中处理时间 (1小时)既包括县级邮车的装卸 时间10分钟，也包括区级邮车的装卸时间 10分钟。且在这1个小时的起始 阶段进行装卸县级邮车的工作；而区级邮车的装卸工作最早在集中处理工作 结束前10分钟进行，也可以在集中处理工作结束之后进行。
4. 两班次的区级邮车行驶路线完全相同，若路线为环形则运行方向必须一致。
女口： D^61f 58f 53fX5f 52f 59f 60f D和 D^60f 59f 52^53f 58f 61 f D两种行车路线即为不同的两条路线。
5. 问题4中选定县局后，县级邮车不得打破行政区划限制而跨县投寄。
3符号说明
D :市级邮局
Xi :县级邮局
X =「X1,X2,X3,X4,X5l :表示县级邮局的集合
W(i,j):赋权邻接矩阵
L(i, j) : Floyd算法中点i到j的距离。
R(i, j) : Floyd算法中i到j之间的插入点。
l(): Floyd算法中用插入顶点的方法依次构造出的距离矩阵。
r(i, j): Floyd算法中用插入顶点的方法依次构造出的路由矩阵。
G =(V,E):表示无向图。
tz :支局停留时间
tx :县局停留时间
qs :区级邮车时速
tcl :县局邮件集中处理时间
xs :县级邮车时速
Ti :区级邮车完成寄送县局i工作后返回市局所需要的时间
ty：县级邮车在县Xi内走完第j条邮路所需要的时间
Time：:开往县Xj的第一班次区级邮车开出市局和第二班次区级邮车到达市局所 需要的时间。
Sv :在各点v设立服务设施的最大服务距离
4模型建立和求解

模型的建立
根据题意，问题一可以归纳为如下数学模型。
|minC(R,P2,「PJ
min Lg(R,P2, ,&)
( PR「Pk)^ P
其中：(R,P2,…,&)表示邮路方案；C(R,巳，…,Pk)表示空置损失费;
Lg(R, P2,…,PJ表示方案的总路径；P表示邮路方案集。
方案的比较和确定
根据题目要求，需要在限定的时间内完成投送邮件的工作。 首先，很自然地
想到求出能够遍历这些点的最短路径，从理论上初步判断需要的车辆数。
Floyd 算法
Floyd算法的基本思想就是直接在图的带权邻接矩阵中用插入顶点的方法
依次构造出v个矩阵L⑴、L⑵、…、L(v)，使最后得到的矩阵L(v)成为图的距离矩阵， 同时也求出插入点矩阵以便得到两点间的最短路径。
此算法的主要程序流程如下：
Step 1 :输入赋权邻接矩阵W(i,j)，
Step 2 :赋初值：对所有 i， j , l(i,j)・ W(i,j)，r(i,j)- j，1。
更新 l(i, j)，r(i, j):对所有 i，j，若 l(i,k) l(k, jh l(i, j)，贝U:
l(i,j)「l(i,k) l(k,j),r(i,j)・ k
Step 3:若 k 二v,停止，输出 L(i