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