2010 年西安电子科技大学《数学模型》
结课论文
—校车安排问题
选作题题号: B
所在学院:
电子工程学院
任课老师姓名: 穆学文
姓名
学号
做题比例
摘
要
本论文主要根据对某市某一高校校车的老校区各区的距离和教师人数的调查资料,对现
实中学校安排校车接送教职工,校车站点建在哪些区域进行了分析研究,并建立了数学模型。
论文中,,依据建立的停车站的位置及个数的不同而造成不同的满意程度,制定建立停车站
的位置及数目,最后,我们对学校校车安排提出了几点建议。
模型一:最短距离模型。考虑到每个区按距离车站的远近选择车站,通过对已知的两个
不同区的距离,运用matlab对矩阵的强大操作能力,根据Dijkstra算法算出各个区之间的最
短距离。得到需要的分析数据。
模型二:多源最短距离。考虑到各区人数的不同,通过模型一中得到的数据,用多源最短
路径算法,求出建立不同个数的停车站时的最短路径。再次考虑人的满意程度,求出最大满
意度。
模型三:多目标最优规划。通过以模型二的满意程度和最小数量的车为双目标,建立设
有3个乘车站时的最优化解法。
[关键词]
停车站;Dijkstra算法;满意度;matlab;多目标目标;最优解法
1、问题重述
B 题 校车安排问题
许多学校都建有新校区,常常需要将老校区的教师和工作人员用校车送到新校区。由于
每天到新校区的教师和工作人员很多,往往需要安排许多车辆。如何有效的安排车辆及让教
师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。
假设老校区的教师和工作人员分布在 50 个区,各区的距离见表 1。各区人员分布见表 2。
问题 1:如要建立 个乘车点,为使各区人员到最近乘车点的距离最小,该将校车乘车点应
建立在哪 个点。建立一般模型,并给出 时的结果。
问题 2:若考虑每个区的乘车人数,为使教师和工作人员满意度最大,该将校车乘车点应建
立在哪 个点。建立一般模型,并给出 时的结果。
问题 3:若建立 3 个乘车点,为使教师和工作人员尽量满意,至少需要安排多少辆车?给出
每个乘车点的位置和车辆数。设每辆车最多载客 47 人。
问题 4:关于校车安排问题,你还有什么好的建议和考虑。可以提高乘车人员的满意度,又
可节省运行成本
2、模型假设
(1)假设每个人的的满意程度只与距离有关。
(2)假设原数据没告诉的两个区之间没有道路,即只有经过其它的区往返。
(3)假设总的满意度是所有人的满意度之和。
(4)假设每个人都很聪明,即只会选择最近的路径去停车站。
(5)假设每次出发所有人一起走,即没有次序的先后(校车高峰期)。
(6)假设车的数量的决策权比人的满意度的决策权高,可为正比于它的平方,立方甚至更
高。
(7) 假设车只在起始点载人,即使人没载满,在中途也不停车。
3、模型建立及求解
模型一最短路径模型
模型二多源最短路径
模型三多目标最优规划
3.1.模型一——最短路径问题
我们为了求出各个区的之间的最短的路径,用 Dijstra 算法求解。
Dijkstra 算法是图论中非常有名的一个算法。是典型的单源最短路径算法,用于
计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,
直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法,在很多专业课程
中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra 一般的
表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN, CLOSE 表的方
式.
图采用邻接矩阵的形式描述,m[i][j]表示结点 i 到结点 j 间的代价,如果没有直接因
果关系,则为无穷大,计算机中可以用一个很大的数据代替(如 Matlab 中的 inf)。
但 Dijkstra 算法只能求出从结点 i 到其它各结点的最短路径。算法引入这样两个集合
s 和 t,s 是那些已经确定了到 i 结点的最短路径的结点,t 为全集 u 和 s 的差集,即那些还
未确定最短路径的结点。而且 s 的初值是{i},t 的初值是 u-{i}。另外再引入一个标记数组
d[n],其中在某一步 d[k]表示当前从 i 到 k 的较短路径,d[k]的初值为 m[i][k]。
整个算法过程如下:
1、 在 t 中选择一个 d[k]最小的结点 k,将 k 并入 s,并从 t 中去掉,如果 t 为{}
则转到3;
2、 用 k 结点和 t 中其余结点进行一遍比较,如果 d[i]>d[k]+m[k][i],则用
d[k]+m[k][i]取代原来的 d[i],重复1;
3、 算法结束,此时 d[k]中保存的就是从I到 k 结点的最短路径。
算法就以这样非常简单的形式完成了求解,时间复杂度是 O(n^2),确定了从I到其余
各结点的最短路径。
由下表可以建立原始矩阵 w。
表 1 各区距离表
区域号
1
1
2
2
2
3
4
4
5
5
6
6
7
7
8
区域号
2
3
4
21
47
4
5
19
6
7
7
8
8
18
9
距离(m)
400
450
300
230
140
600
210
310
230
200
320
340
170
160
200
8
9
10
10
11
11
12
13
14
14
15
15
16
16
17
18
18
19
19
20
20
21
21
21
22
22
22
23
23
23
23
24
24
26
26
27
28
29
30
30
15
10
11
15
12
14
13
34
15
26
16
17
17
18
27
19
25
20
24
21
24
22
23
47
44
45
48
24
29
30
44
25
28
27
34
28
29
31
31
42
285
180
150
160
140
130
200
400
190
190
170
250
140
130
240
204
180
140
175
180
190
300
270
350
160
270
180
240
210
290
150
170
130
140
320
190
260
190
240
130
30
31
31
31
32
32
32
33
35
36
36
37
38
39
40
40
42
43
43
45
46
48
43
32
36
50
33
35
36
34
37
39
40
38
39
41
41
50
50
44
45
46
48
49
210
230
260
210
190
140
240
210
160
180
190
135
130
310
140
190
200
260
210
240
280
200
可以使用MATLAB中的for循环分别算出从1开始到49到各个点的最短距离。
用 matlab 求任意两个校区的最短距离的程序如下:
%Dijstra 算法求解
w=[0,400,450,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf;400,0,inf,300,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,230,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,140,inf,
inf,inf;450,inf,0,600,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf;inf,300,600,0,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,310,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf;inf,inf,inf,210,0,230,200,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf;inf,inf,inf,inf,230,0,320,340,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf;inf,inf,inf,inf,200,320,0,170,inf,inf,inf,inf,inf,
inf,inf,inf,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf;inf,inf,inf,inf,inf,340,170,0,200,inf,inf,inf,i
nf,inf,285,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,200,0,180,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,180,0,150,i
nf,inf,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,150,0,
140,inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
140,0,200,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,200,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,400,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,130,inf,inf,0,190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,285,in
f,160,inf,inf,inf,190,0,170,250,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,170,0,140,130,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,250,140,0,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,240,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,160,
inf,inf,inf,inf,inf,inf,inf,inf,130,inf,0,204,inf,inf,inf,inf,inf,
180,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,310,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,204,0,140,inf,inf,inf,1
75,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,140,0,180,inf,inf,
190,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,230,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,0,300,2
70,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,350,inf,inf,inf;inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,300,0,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,160,270,inf,inf,180,inf,inf;inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,270,
inf,0,240,inf,inf,inf,inf,210,290,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,150,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,175,190,in
f,inf,240,0,170,inf,inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,inf,inf,
inf,inf,inf,170,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,0,140,inf,inf,inf,inf,inf,inf,320,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,240,inf,inf,
inf,inf,inf,inf,inf,inf,140,0,190,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,130,inf,inf,190,0,260,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,210,inf,inf,inf,inf,260,0,inf,190,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf;inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,290,inf,inf,inf,inf,inf,inf,0,240,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,130,210,inf,inf,inf,inf,inf,inf,inf;in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,240,0,230,inf,inf,
inf,260,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210;i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,230,0,190,i
nf,140,240,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,190,0,
210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,400,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,320,inf,inf,inf,inf,inf,inf,
210,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,14
0,inf,inf,0,inf,160,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,260,
240,inf,inf,inf,0,inf,inf,180,190,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,160,inf,0,135,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,135,0,130,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,180,inf,130,0,inf,310,inf,inf,inf,inf,inf,i
nf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,190,inf,inf,inf,0,140,inf,inf,inf,inf,inf,
inf,inf,inf,190;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,310,140,0,inf,inf,inf,inf,i
nf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,
inf,inf,inf,inf,200;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,260,2
10,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,160,150,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,260,0,
inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,270,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,210,
inf,0,240,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,240,0,inf,280,inf,inf;inf,140,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,350,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,0,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,inf,
inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,180,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,280,inf,0,200,inf;inf,inf,inf,inf,inf,inf,inf,inf,i
nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in
f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,