数学建模---车辆调度问题论文设计

2024年1月5日发(作者：中考台州数学试卷真题及答案)

标准

2012年西南财经大学数学建模竞赛赛题

车辆调度问题

说明：

1、竞赛于5月2日12:00结束，各参赛队必须在此时间之前提交打印论文及上传论文电子文档，

2、请认真阅读“西南财经大学数学建模竞赛章程”、“西南财经大学数学建模竞赛论文格式规范”，并遵照执行，

3、打印论文交给经济数学学院办公室（通博楼B302），电子文档发至邮箱gdsxkj@

4、选拔参加建模培训的本科参赛队必须提交一份解夏令营问题的论文，各本科参赛队根据自己的校赛状况，提前做好准备，校赛成绩公布后提交：夏令营问题地址

5、由于本题目计算量比较大，竞赛期间如果计算不完，也可以提交部分成果。

某校有A、B两个校区，因为工作、学习、生活的需要，师生在两校区之间有乘车需求。

1、在某次会议上，学校租车往返接送参会人员从A校区到B校区。参会人员数量、车辆类型及费用等已确定（见附录1）。

（1）最省的租车费用为多少？

（2）最省费用下，有几种租车方式？

2、两校区交通网路及车辆运行速度见数据文件（见附录2）。试确定两校区车辆的最佳行驶路线及平均行驶时间。

3、学校目前有运输公司经营两校区间日常公共交通，现已收集了近期交通车队的运行数据（见附录3）。

（1）试分析运行数据有哪些规律，

（2）运输公司调度方案是根据教师的乘车时间与人数来制定的，若各工作日教师每日乘车的需求是固定的（见附录4），请你根据运行数据确定教师在工作日每个班次的乘车人数，以供运输公司在制定以后数月调度方案时使用。

4、学校准备购买客车，组建交通车队以满足教师两校区间交通需求。假设：

（1）欲购买的车型已确定（见附录5），

（2）各工作日教师每日乘车的需求是固定的（见附录4），

（3）两校区间车辆运行时间固定为平均行驶时间（见附录2）

若不考虑运营成本，请你确定购买方案，使总购价最省。

5、若学校使用8辆客车用于满足教师两校区间交通需求。假设：

（1）8辆客车的车型及相关数据已确定（见附录6），

（2）各工作日教师每日乘车的需求是固定的（见附录4），

（3）两校区间车辆运行时间固定为平均行驶时间（见附录2），

（4）车库设在A校区，客车收班后须停靠在车库内。

请你确定最佳调度方案，在满足教师乘车要求条件下，使该车队运营成本最低。

6、事实上，教师及学生每日乘车的需求是随机的，车辆运行时间是随机的。如果学校文案

考虑是否组建交通车队满足教师两校区间交通需求。请你分析：

（1）应考虑哪些因素？收集哪些数据？

（2）建立合理决策模型，结合相关数据（附录3，附录7），并参考问题4、5的结论，估算模型的解，从而得到合理的解决方案。

附录：

附录1 参会人员数量、车辆类型及费用表

租车报价

可选车型

座位数

租用半天费用（元）

租用全天费用（元）

优惠

参会人员

主席团人员27人 其他人员195人

注：主席团人员与只参加上午会议 20 22

其他人员可共同参会时间

乘坐一辆车（Ⅰ、全天 7 173

Ⅱ型）

可选车型 Ⅰ、Ⅱ Ⅰ、Ⅱ、Ⅲ、Ⅳ

附录2 数据文件：两校区交通网路及车辆运行速度表.xls

附录3 数据文件：两校区交通运行调查数据表.xls

附录4 教师乘车固定需求表

A

发车时间

校区

乘车人数

7:30

88

8:15

100

9:25 11:45 13:05 15:00 17:15 19:30

24 46 4 44 73 5

Ⅰ

4

400

800

Ⅱ

7

500

1000

Ⅲ

34

1000

2000

Ⅳ

47

1200

2400

注：包括驾驶员座位

租Ⅰ型车3辆及以上：Ⅰ型车租金全部8折（租半天算0.5辆）

租Ⅱ型车3辆及以上：Ⅱ型车租金全部8折（租半天算0.5辆）

B

发车时间 10:30 11:30 12:25 13:00 16:00 17:15 17:30 17:45 20:30 21:25

校区

乘车人数 40 10 20 40 33 109 14 26 62 30

附录5 客车报价表

车型

座位数

购车价格

Ⅰ

16

18

Ⅱ

31

30

Ⅲ

35

33

Ⅳ

36

38

Ⅴ

39

45

Ⅵ

47

48

注：座位数包括驾驶员座位

购车应考虑购置税

附录6 8辆客车的车型及相关数据表

车型

座位数（座）

耗油量（升）

数量（辆）

驾驶员费用（元/1个来回）

车型

座位数（座）

Ⅰ

16

15

1

13

Ⅰ

16

1

Ⅱ

31

19

Ⅱ

31

Ⅲ

35

20

6

15

Ⅲ

35

Ⅳ

36

20

Ⅳ

36

Ⅴ

39

21

Ⅴ

39

Ⅵ

47

24

1

17

Ⅵ

47

附录7 部分客车的车型及相关数据表

购车价格（万元）

耗油量（升）

驾驶员费用（元/1个来回）

车辆养护与保险（万元/年）

票价（元/人）

驾驶员基础工资（元/月）

18

15

13

1

30

19

15

1.6

33

20

15

1.7

38

20

15

1.9

45

21

15

2.0

48

24

17

2.3

5

1200

2

2012年西南财经大学数学建模竞赛

论文题目 车辆调度问题

姓名 学号 专业

10级金融学

联系方式

任磊 41004233

张耀城 40925041 10级金融服务与管理实验班

张英博 41021075 10级金融工程

3

车辆调度问题

【摘要】面临日益拥堵的交通现状，如何更合理的安排校车的调度，对于方便广大师生的学习和生活、保证教学活动的顺利进行具有重要意义。本文通过收集相关资料，处理题中所给数据，并建立相关数学规划模型解决题中所给的六个问题。

首先，对于如何合理安排多车型的车辆调度问题使得联合运输的费用最小的问题,我们通过建立整数规划模型，利用lingo软件求解出最省的租车费用为13000元。然后根据题目条件，在既定最低租车费用为13000元的情况下，利用C++程序定步长全局模拟出所有的可行解，得到112种租车方案。

其次，我们将最佳行驶路线定义为车辆运行时间最短的路线，将图论中经典的Dijstra算法进行改进，以结点之间的时间作为权数，得到最佳路径。利用matlab编程求解得到最短运行时间为35分钟，路程总长为36.2km。

然后，我们依据附录3对A、B校区师生乘车需求人数进行了描述性统计，从乘车人数的均值、方差、峰度以及正态性四个角度对样本进行检测，特别发现教师乘车需求在某些时段较为集中，从而利用SPSS软件对数据进行聚类分析，找到相关的分布规律与结论，即教师每日在各时段中的乘车人数分布相似。随后，我们以anova方差检验、组内与组间均值比较以及标准误差分析为手段，进一步验证了所得结论的准确性，使之能够可靠的用来推测未来每天乘车的教师人数的依据，为以后的分析和建模做好准备。

再次，面对第四题中不考虑运营成本的较为理想化的整数规划模型，我们采用类似贪婪算法，将全局约束以发车时间划分为几个高峰时段，用lingo软件在各高峰时段约束中寻找局部最优，并将各个局部最优解对比淘汰，得到全局最优解。即满足所有约束的最小购车成本为257.2564万，具体购车方案为买2辆Ⅰ车、4辆Ⅱ车、1辆Ⅲ车和1辆Ⅵ车。

随后，根据附录4与第二问所求得的最短运行时间，我们仍然建立较为复杂的数学规划模型，在定步长搜索与深度优先算法的基础上，利用matlab与C++编程，最终求解出满足教师乘车需求条件下的最优调度方案，并达到每天的最小运营成本1659.96元

最后，我们根据以上求解的答案与题目提供的材料，对学校是否应该组建校车队进行实际讨论，我们从经济成本、时间成本、能否满足正常教学活动及教师舒适度等角度考虑，利用层次分析法，在多种可选方案中得出决策：学校应该组建校车队，以满足教师和同学们的乘车需求。紧接着，我们利用第三问所得数据规律来确定各发车时刻点的需求人数，建立较为复杂的规划模型，利用matlab与C++软件，采用定步长搜索，找出组建校车队的各种可行解及其最低成本，最后在所有最低成本中选取全局最优解，得出最佳的购车方案与调车安排，并最终

4

预测出组建校车队平均每天所需的成本2787元，预估平均每天获利1460元。

此外，在分析了上面所建立模型的优缺点后，我们认为该模型设计较为理想，但也忽略了一些现实因素。因此在此基础上我们进一步收集关于学生乘车需求的信息并提出模型的修正方向。

【关键词】数学规划 汽车调配 Dijstra算法 深度优先算法 定步长搜索 层次分析法

一、问题重述

1.1问题背景

随着我国政府对教育的大力推广，校车运输在交通运输行业里开始扮演越来越重要的角色。校园间交通日益成为城市交通的重要组成部分。面对各个校区之间师生的乘车需求，以及日益严重的交通道路拥堵现状，设计合理的校车交通运行机制对于方便师生、节约广大师生时间，保证教师正常的教学工作与学生的生活学习具有重要作用。同时也可以使运输公司提供更好的交通服务，提高运输公司的经济和社会效益。

1.2问题提出

某校有A、B两个校区，因为工作、学习、生活的需要，师生在两校区之间有乘车需求。在某次会议上，学校租车往返接送参会人员从A校区到B校区。已知参会人员数量、车辆类型及费用等，要求建立数学模型，求出最省的租车费用，并写出在最省费用下有多少中乘车方式。

根据已有的两校区交通网络图及车辆运行速度，确定两校区车辆的最佳行驶路线（用时最短的路线）和平均行驶时间。

根据已有的交通车队的运行数据，通过分析运行数据之间的存在的规律，为运输公司确定教师在工作日每个班次的乘车人数，以供运输公司在制定以后数月调度方案时使用。

学校面对教师和学生的乘车需求，决定根据已有的数据组织交通车队，试求如何使总购价成本最低。并确定最佳的调度方案，在求在满足教师乘车需求的基础上使得车队运营成本最低。

最后，在更为一般化的条件下，讨论建立交通车队以满足教师两校区间的交通需求的实际要素，收集数据，建立合理决策模型，估算合理的解决方案。

二、问题分析

车辆调度问题是一个数学规划问题,即在满足调度限制的解空间内, 寻找使调度选择中提出的目标函数都满意的优化解。校车优化调度是在掌握了大量学生和教师乘车需求数据并总结出规律之后, 通过把多种不同型号的车辆组织在规定的最优线路上,按照客流的数量、方向、时间等因素，从而制定有序的、 周而复始的行车计划。同时，由于运输公司存在可持续运营的问题，需要考虑一定的成本与收益的关系，要综合考虑教师学生的乘车需求和运输公司的盈利情况。

首先通过建立简单的整数规划模型，通过lingo求解出最低成本下的租车方

5

案；进而通过图论中经典的关于最短路的Dijstra算法求出最优路线与最短时间。我们通过一些合理的假设以及对附录数据的分析和处理 ,针对车辆调度问题建立了一般的规划模型，从而求解出最优构成方案和最佳调度方案。基于前面做的努力，我们可以得出在更为一般的条件下，学校最佳的组建方案中组建校车队所耗用的成本与获得的利润。

可以对上述问题作以下描述:有 A、B两个校区，从第 i个校区的教师乘车需求量为Gi ( i= 1 , 2),需将所有教师运往另一个校区, 由运输公司派出车型为 r ( r= 1 , 2 … n)、 载重量为Gn ( r= 1 , 2 , , n , 且假设 q1 < q2 < ……< qn )的客车来承运,已知Gi <

Gn (非满载 ), 求满足乘车需求的最短行车线路，与最佳车辆配置。

三、问题假设

1、假定路线不存在堵塞现象，不考虑路段拥挤、堵塞或车辆本身故障情况；

2、假定车辆在公路上行驶速度处处相等，车辆之间依次行进 ,不存在超车现象，都等于题目中给出的平均速度；

3、假定汽车租赁期间只考虑租赁费用，且汽车可以随意调用，不计成本；

4、假定从A校区到B校区单程只需要35分钟，不考虑教师和学生上下车的时间；

5、假定耗油量为每百公里的耗油量；

6、校车所用汽油为93#汽油，油价采用去年平均价格7.23元/升；

7、假定一年有365天；

8、假定车辆购置税为10%

9、假定校车都是准点发车，不存在延误现象；

10、假定校车的使用年限为10年；

11、题目中所给数据真实可靠；

四、符号表示

1、Xi,j：

表示第j类型车在第i个半天的需求量（i=1,2;j=1、2、3、4）；

2、Ci,j：

表示第j类型车在第i个半天的成本（i=1,2;j=1、2、3、4）；

3、w(i,j)：表示在最短时间下从道路点i到道路点j之间的距离；

4、l(v)： 表示从顶点u0到v的经过一条路所用时间的权；

5、z(v)： 表示最佳的路线，v的父亲点；

6

6、Xi：

表示第i辆车的购置数量；

7、Ci：

表示第i辆车的成本；

8、i：

表示第i辆车可以乘坐的人数；

9、di:

表示第i时间点需要乘车的人数（i=k）；

（Sli/100）P0，其中油价为10、P1i： 表示第i车的油耗花费，可以刻画为P1iP0l，i耗油量为每百公里的耗油量；

11、P2i:

表示第i车驾驶员费用；

12、PC,i： 表示每天车费实际的分摊成本；

13、PD,i： 表示第i车校车的折旧费用；

14、Pi:： 表示i车每运行一次的花费；

15、P： 表示车辆运行的所有的费用；

16、Ni,j： 表示第j个发车时点的调运i辆车；

17、ni,j: 表示第i类车购买j辆（i=1,2，3;j=1..8）；

五、模型建立与求解

问题一：

5.1.1 问题分析

根据题意，我们可知每种可以租用上半天和租用下半天，而且两辆车分别租用上半天和下半天其成本和效用同租一整天同类车是相同的。此外，我们还可知租车的成本只考虑租赁费用，同时在租用期间，汽车可以随意调用，且不计成本。主席团人员可以与其他人员共同乘坐一辆车（Ⅰ、Ⅱ类型车）。

5.1.2规划模型的建立

首先，由于租用半天的费用正好是租用一整天费用的一半，所以，从成本最小的角度出发，我们暂不考虑租用全天汽车的情况，即将全天利用两个半天代替。建立如下模型：

决策变量：

设Xi,j表示第i类型车在第j个半天的需求量（i=1,2;j=1、2、3、4）。引入 “0—1”变量y1与y2，分别为当Ⅰ、Ⅱ类型车大于等于3辆时取值为1；当Ⅰ、Ⅱ类

7

型车小于3辆时取值为0。

即：

1,当Ⅰ型车3辆时1,当Ⅱ型车3辆时，y2

y10,其他0,其他目标函数：

设租车的总的成本为Z,租车的成本为Ci,j，顾ZCi,jXi,j

i1j1,24约束条件：

1、保证主席团人员上午乘坐Ⅰ、Ⅱ类型车，即3X116X2127

2、保证所有人员在上午的乘车要求，即3X116X2133X3146X41222

3、保证下午参加会议的主席团人员的车位，即3X126X227

4、保证下午参加会议的人员（包括主席团人员）的乘车情况，即3X126X2233X3246X42180

5、考虑Ⅰ、Ⅱ类型车大于等于3辆时打折情况，即

(0.5(X11X12)3)y10(0.5(X21X22)3)y20非负约束：Xi,j0

综上可得：

4

maxZCi,jXi,ji1j1,23X116X21273X116X2133X3146X412223X126X227

s..t3X126X2233X3246X42180(0.5(XX)3)y011121(0.5(X21X22)3)y20Xi,j0

5.1.3模型求解

根据lingo软件，可编制程序求解，见附件9.2.1，得出最省的租车费用为13000元

5.1.4模型进一步讨论

通过第一个程序，可以求得全局最优解，又由于租用半天的费用正好是租用

8

一整天费用的一半，所以对于其他的最优解，只可以通过替换同等价位的车型，进而改变车型配置以使解不同。

（之所以是等价位车型间的替换，因为若高价替换，且满足约束条件，则目标函数会变大，目标函数不再是最优；若是用低价替换，又满足约束条件，则目标函数会变小，于是与原目标函数是最优矛盾。因此只能是等价位不同车型替换。）而在所有车型中，等价位车型，只有打折后的二类车和未打折的一类车价格是一样的，因此只能是这两种车型的替换。

这种结果可以根据具体数据分析：在第一个最优解中，共租用5辆上午的二类车型，共可载30名主席团成员，而实际主席团成员只有27人，因此有3个空座。因为一辆二类车型和一辆以类车型的座位差为3 个（6 -3=3），恰好等于3个空座。而且在第二个解中，二类车也已满足打折的条件，而一类车没有打折，以一类车和二类车价格是一样的，因此满足替换条件，进而通过替换求出其他最优解。

以上解都是不考虑全天租车问题的，即完全用上半天和下半天的租车方式代替全天的租车方式（因为假设5，俩类可以替代）

当考虑全天时候，我们可以通过，以一个上半天和一个下半天的同一类车来更换为一个全天的同类车，以求得其他最优解。

基于以上几种替换原理，我们利用C++程序全真模拟出共112种最优解。由于表格内容繁杂，因此租车方案见附录9.2.2；程序见9.2.3

问题二：

5.2.1最佳行驶路线模型的建立

两点间的最佳路径可能需要考虑的并非仅仅是空间距离的最短, 有时候人们往往会考虑到通行时间的问题。本文就此问题,对最短时间路径做了讨论，因此我们将两个校区车辆最佳行驶路线定义为：在所用时间最短的前提下，所经过的道路点。为了求出最短时间下各个点的之间的距离，我们使用了路径问题中Dijstra算法求解。

根据所学图论知识，我们将图采用邻接矩阵的形式描述，w(i,j)表示在最短时间下从道路点i到道路点j之间的距离，如果没有直接连通，则为无穷大，计算机可以用一个很大的数据代替（如matlab中的inf）。由于Dijkstra算法只能求从结点i到其他各结点的最短路径，对每个顶点，定义两个标记（其中: ：表从顶点u0到v的经过一条路所用时间的权。，），：v的父亲点，为用以确定最佳的路线。算法的过程就是在每一步改进这两个标记，使最终从顶点u0到v的最时间的权。输入:

G的带权邻接矩阵w(u,v)。

算法步骤：

（１）赋初值：令

S＝{},

vSVS,令==0

,=

9

（2）更新 则令

、=：

,,若=

>

（3）设是使取最小值的中的顶点，则令S=S∪{}，

（4） 若φ，转2，否则，停止。

用上述算法求出的就是到的最短时间的权，从的父亲标记z(v)追溯到, 就得到到的最佳路线。

算法流程图

利用Dijkstra算法算出各城市到乙城市的最短路径以及最小耗费

选择头节点

将节点放入优先队列

分析当前的下界,得出程序结果,并返回.

Y

队列为空

N

从优先队列中取出当前最优元素并算出当前这个可行解的路径长度和耗费并与最优解比较

Y

不如下界

N

将这个节点保存下来作为剪枝使用的下界

5.2.2模型的求解

根据算法和相邻的点的距离，我们可以用dijkstra求出两点之间的最佳路径。

使用for循环结构求出1—141个点之间的最短距离。（程序见附录9.3）可以求出所需最短时间以及最短时间所经过的路程

如从第13点（A校区）开始到第20点（B校区），最短时间需要34.998分（0.5833小时）。

10

顺次经过第13点、第22点、第21点、第14点、第16点、第38点、第39点、第4点、第62点、第85点、第20点，及从A校区到B校区的最优路径为13—22—21—14—16—38—39—4—62—85—20，路程总长度为36.2km.

问题三：

5.3.1数据分析并得出规律

对于学生和老师来说，每天乘车的人数为随机变量，因此为了探讨交通车队运行数据的规律，首先要对每天乘坐校车的老师和学生的人数的分布情况进行统计分析。

5.3.1.1对一周内学生乘车人数分布情况的分析

首先，对总体学生乘车人数的样本总体进行描述性分析，得到下表（表1）：

表1：描述性统计量

N 均值 标准差 极小值 极大值

乘车人数 56 241.95 107.983 43 471

为了更直观的了解分布情况，画出如下散点图（图1）：

图1

表1与图1表明，样本均值为241.95，标准差较大为107.983，且极差值为428，说明样本分布较为分散，学生乘车人数比较离散，规律性较差。

5.3.1.2对校区A和校区B学生乘车人数的独立样本检验，得到如下表2：

表2：独立样本检验

方差方程的Levene 检验

Sig.(双F

乘假设车方差

.017

Sig.

.897

t

-.283

df

54

侧)

.778

均值差值

-8.250

标准误差值

29.104

均值方程的 t 检验

差分的 95% 置信区间

-66.600 50.100

11

人方差数 不相等

-.283 53.972 .778 -8.250 29.104 -66.601 50.101

对学生班A、B校区乘车人数的独立样本T检验，分析结果中，显著性0.897>0.05，由此可以判断学生对于乘车的需求（即每天的乘车人数）在A,B校之间区别不大。

5.3.1.3 对工作日每个班次乘车的教师人数的描述统计量的分析与确定：

根据附录3教师班A、B校区数据中以各个发车时间点作为归类（如，将7:25,7:27,7:30的人数加总记为7:30发车段教师的乘车人数，以此类推）得到以下关于校区A的表格及描述统计量表4：

表4

极小

全距 值

统计量

7.30

8.15

9.15

11.45

13.05

15.00

17.15

19.30

38.00

20.00

4.00

9.00

22.00

8.00

11.00

6.00

统计量

82.00

91.00

22.00

42.00

3.00

41.00

66.00

1.00

统计量

120.00

111.00

26.00

51.00

25.00

49.00

77.00

7.00

统计量

89.9000

99.9000

24.2000

45.8500

4.5500

44.4000

72.4000

6.1765

标准误

1.88470

1.20939

.27720

.50406

1.08209

.48882

.67823

.34551

统计量

71.042

29.253

1.537

5.082

23.418

4.779

9.200

2.029

极大值 均值 方差 偏度

标准统计量 误

2.638

.114

-.236

.391

4.393

.738

-.778

-3.290

.512

.512

.512

.512

.512

.512

.512

.550

峰度

标准统计量 误

8.551

-.587

-.814

-.020

19.506

.255

.069

12.302

.992

.992

.992

.992

.992

.992

.992

1.063

根据描述统计量表4，可知组内标准差与标准误差较小，极差较小，可以推断按“周几”进行的归类统计可以更好的反映数据的趋势。

校区B的分析方法同校区A，如表5

表5：描述统计量

10,30

11.30

12.25

13.00

16.00

17.15

17.30

17.45

20.30

N 全距 极小值 极大值 均值 标准差 方差 偏度 峰度

统计量 统计量 统计量 统计量 统计量

20

20

20

20

20

标准误 统计量 统计量 统计量 标准误 统计量 标准误

.512 1.226

.512 .151

.992

.992

.992

.992

.992

.992

.992

.992

.992

7.00 38.00 45.00 40.1000 .40975 1.83246 3.358 1.148

3.00 8.00 11.00 9.5500 .15347 .68633 .471 -.198

.368 -.785 2.00 18.00 20.00 19.5000 .13572 .60698 .512 -.213

.512 -.893

.512 -1.298

.512 3.767

.512 -.570

.512 1.188

.512 -.054

4.00 38.00 42.00 40.2000 .28654 1.28145 1.642 -.080

4.00 31.00 35.00 33.4500 .29447 1.31689 1.734 -.187

20 30.00 102.00 132.00 110.2000 1.58380 7.08297 50.168 1.676

20

20

20

2.00 13.00 15.00 13.6000 .13377 .59824 .358 .393

.149 5.00 24.00 29.00 26.4000 .24495 1.09545 1.200

7.00 57.00 64.00 61.3000 .43589 1.94936 3.800 -.565

12

21.25 16 5.00 25.00 30.00 28.8125 .33190 1.32759 1.762 -1.759 .564 3.761 1.091

5.3.1.4对教师乘车人数的方差分析

根据”描述”表格（见附录9.4.1），可以看出，各个发车段，以周几作为分组标准进行的方差检验中，各组均值的标准差较小，极差较小，在均值的 95%

置信区间内的估计范围也只是在均值上下有小幅度加减，同时，从anova方差检验中的显著性看，除了7.30和19.30两项，其余的显著性都很大（明显大于>0.05），所以接受方差齐性的原假设。（而对于19.30项，之所以显著性大，是因为在周五是几乎没有这一班车的，顾周五的值属于特殊值。如果只考虑周一到周四，19.30这一班车教师的乘坐数，我们可以通过下面的19.30均值图看出，它也是满足方差齐性的。）顾可以推断，各组满足方差齐性，即不论周几，同一时间段的教师乘坐数是服从同一分布的。

同理对于附录3教师班B校区数据做同样的分析后结果是一样的（数据见附录9.4.2）。

5.3.1.5对教师乘车人数的正态分布假设检验

单样本 Kolmogorov-Smirnov 检验

VAR00001

N 20

正态参数均值 42.9560

a,b 标准差 30.82716

最极端差绝对值 .163

别 正 .163

负 -.106

Kolmogorov-Smirnov .727

Z

渐近显著性(双侧) .666

根据检验结果，发现显著性水平为0.666>0.05，接受原假设，说明教师乘车人数服从正态分布。

5.3.2教师在工作日每个班次的乘车人数的确定

根据3.1.3描述统计量与3.1.4的方差分析，可知教师乘坐校车的人数不随周几的变化而变化，所以我们可以通过对一天内不同时间段教师乘坐数的分析，来估测整个月份中每一天的教师乘坐客车人数分布。即每天的需求相类似，我们可以通过对一天内不同时间段教师乘坐数的分析，来估测整个月份中每一天的教师乘坐客车人数分布。

根据附录3，我们通过“描述”表格表4，我们可以看到各个组内的和组建的标准误差都较小，组内均值可以代表总体均值，所以综上所述，可以确定教师在工作日每个班次的乘车人数，为如下表6：

13

A校区

7：30

89.9

8：15

99.9

9：15

24.2

表6

11：45 13：05

45.85 4.55

15：00

44.4

17：15

72

19：30

5.25

B10:校30

区

40

11:12:30 25

9.5 19.5

13:00

40.2

16:00

33.45

17:15

110.2

17:30

13.6

17:45

26.4

20:30

61.3

21:25

28.81

可以通过以上表格可以估测每个工作日每个班次的教师乘车人数，与附录4吻合程度相当好。

问题四：

5.4.1问题分析

根据附录2与第二问问题的求解，我们可知，A、B两校区之间车辆运行时间固定为35分钟。根据附录4可知A、B两校区之间分别的发车时间，且不考虑运营成本，即当同校区相邻两个发车时间间隔超过70分钟，或在A,B两校区的相邻两个发车时间间隔超过35分钟时，发车站可以随意调配所有车辆。由此，我们可以将问题简化为，只需考虑A校区或者B两校区分别的发车时间在70分钟之内的情况，以及A、B校区之间相邻发车时间间隔小于35分钟的情况下，从而得出能够满足教师乘车需求的购车方案。思路图如下：

A: 7:30–––8:15––9:25–––––––––––––11:45––––––13:05 15:00 17:15

19:30

B： 10:40––––11:30 12:25––––––13:00 16:00 17:15 17:30

20:30 21:25

其中画×的部分由于上述原因，可以不予考虑，故现在只需对连通的时间段进行分析和求解

根据附录4，我们可以分出4个乘车人数的高峰时间段（7：30—8：15；11：30—12：25；12：25—13：00；17：15—17：45）。只需考虑校车运量能够满足这四个高峰期即可。

5.4.2模型的建立

决策变量：设Xi为第i辆车的购置数量

14

目标函数：设Ci为第i辆车的成本，Z为最小的购车成本，i和第i辆车可以乘坐的人数，di为第i时间点需要乘车的人数（i=1,2,…..k）

故得出目标函数为ZminCiXi

（i1,2,..k）i1k约束条件：满足每一个时刻点教师的乘车人数即可，即

（i1,2,..k）综上所述：

ZminCiXii1kXii1kidi

kiXidi

i1s..tXi0i1,2,..k）（

5.4.3模型的求解

根据模型，我们建立以上整数规划模型，利用lingo软件，编程序（程序见附录9.5）计算可知：

满足第一个运量高峰期（7：30—8：15）乘车需求的购车方案为：

Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ 成本（万）

车数（辆） 3 3 205.1538

满足第二个运量高峰期（11：30—12：25）乘车需求的购车方案为：

Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ 成本（万）

车数（辆） 1 1 1 104.2051

满足第三个运量高峰期（12：25—13：00）乘车需求的购车方案为：

Ⅰ Ⅱ Ⅲ Ⅵ Ⅴ Ⅵ 成本（万）

车数（辆） 2 2 104.2051

满足第四个运量高峰期（17：15—17：45）乘车需求的购车方案为：

Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ 成本（万）

车数（辆） 2 4 1 1 257.2564

由上表可知，当满足第四个高峰期时，可以满足全部的教师乘车需求，因而得出答案，购车最少成本为257.2564万元，构车方案为：

15

车数（辆）

Ⅰ

2

Ⅱ

4

Ⅲ

1

Ⅳ

Ⅴ

Ⅵ

1

成本（万）

257.2564

问题五：

5.5.1模型建立

在满足附录4所提供的教师固定乘车需求的前提下，根据附录6所提供的八辆客车的相关信息，以及通过第二问所求出的最佳行驶时间（35分钟）与最佳路程（36.2km），我们可以知道，在考虑运营成本的情况下，我们的最优调度方案。

根据假设，我们设油价为P0=7.23元/升，A、B两校区之间的距离为S。由题目可知耗油量为每百公里的耗油量，设为li。所以，油价的花费可以刻画为P（Sli/100）P0，同时，设驾驶员费用为P2i，所以校车每从A校区到B校区或1i从B到A运行一个单次的花费为：PiP1iP2i/2SliP0/100P2i/2，一个来回的费用可记为：PiSliP0/50P2i。

在考虑运营成本的情况下，分配车辆调度以使从成本最低，依然是一个较为标准的数学规划问题。

因而设决策变量：每个发车点的调运车辆，设为Ni,j

目标函数：设总运营成本为P，设Ⅰ、Ⅲ、Ⅵ三种车型为Xi，每种车可以搭载运输Ki个人

18318,Ni,j为偶数时）ii,j（当PNj1i1j1

minP318318PN,Ni,j为奇数时）ii,jPNii,18（当i1j1i1j1当Ni,j为奇数时，车辆要空跑一个单程，以满总的乘车需求。

j118约束条件：使调运的车数可以满足全部教师需要乘车的人数，设为di，即KNii13i,jdi

若i车在j时间不发车，则Ni,j0。

16

综上所述：可建立如下模型：

18318,Ni,j为偶数时）ii,j（当PNj1i1j1minP318318

PN,Ni,j为奇数时）ii,jPNii,18（当i1j1i1j1s..tKiNi,jdii13

5.5.2模型求解

对于此问题，我们可以利用lingo软件进行求解，但由于未知变量较多，lingo求解较为困难，面对众多的调度方案，我们选择利用C++的深度优先搜索算法求解出最优的方案，它的基本思想是当一个超链被选择后，被链接的文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着文件上的超链走到不能再深入为止，然后返回到某一个文件点，再继续选择该文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。如下示意图：（具体C++程序见附录9.6）

具体算法如下：

按照某种条件往前试探搜索，如果前进中遭到失败，则退回头另选通路继续搜索，直到找到条件的目标为止。

1）选取某一时间点Vi为出发点，访问并标记该顶点；

2）以Vi为当前顶点，依次搜索Vi的每个邻接时间点Vj，若Vj未被访问过，则访问和标记邻接点Vj，若Vj已被访问过，则搜索Vi的下一个邻接点；

3）以Vj为当前顶点，重复步骤2），直到图中和Vi有路径相通的顶点都被访问为止；

4）若图中尚有顶点未被访问过（非连通的情况下），则可任取图中的一个未被访问的顶点作为出发点，重复上述过程，直至图中所有顶点都被

17

访问。

5）从中选出最佳的调运方法

得出最优的校车调度方案，如下：

最优调度方案

A校区 B校区

7：30 调运Ⅰ、Ⅲ、Ⅵ型车 10：30 调运Ⅵ型车

8：15 调运Ⅲ、Ⅲ、Ⅲ型车 11：30 调运Ⅰ型车

9：25 调运Ⅲ型车 12：25 调运Ⅲ型车

11：45 调运Ⅵ型车 13：00 调运Ⅵ型车

13：05 调运Ⅰ型车 16：00 调运Ⅲ型车

15：00 调运Ⅵ型车 17：15 调运Ⅲ、Ⅲ、Ⅵ型车

17：15 调运Ⅲ、Ⅲ、Ⅲ型车 17：30 调运Ⅰ型车

19：30 调运Ⅰ型车 17：45 调运Ⅲ型车

20：30 调运Ⅲ、Ⅲ型车

21：25 调运Ⅲ型车

以及满足教师乘车需求下的每天最低运营成本1659.96元

问题六：

6.1关于决策是否组建车队的层次分析法

面对是否组建校车这一决策时，有建校车（P1）、公交车（P2）、私家车（P3）、出租车（P4）四种方案满足教师的乘车需求，从常识出发，我们应该重点从建校车的经济成本（省钱e）、总的时间成本（省时f）、能否保证正常的教学活动（是否准点g）、教师的舒适度（舒适度h）考虑，得出最满意度（）来综合考量，使(e,f,g,h)最大。基于以上考虑的因素，我们利用层次分析法，对学校是否要组建校车队给出比较、判断和决策。方法思路图如下：

目

标

层

准

则

层

方

是否组建校车队

满意度

花费e

省时f

准点率g

舒适度h

公交车P2

出租P3

18

私家车P4

案

层

校车P1

首先，目标层与准则层的分析

先确定这些考虑因素对于我们分析的问题占多大比重，根据我们的判断，将权重确定为gfhe，从而可以列出成对比较矩阵：

131A(c)mn，aij0，aij，

A22aji12

231413322334,

141141得到成对比较矩阵的特征值为：4；权向量()(2(2)为：0.3651 0.54770.7T3030.1826n4。由此可知,,,)CI0，根据1.82611.82611.82611.8261n13随机一致性指标RI的数值如下：可以确定RI为0.9

n 1 2 3 4 5 6 7 8 9 10 11

RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51

所以，对权向量的一致性检验，CRCI0.1,符合一致性检验，故而权重RI合理。

其次，分析方案层与准则层检验的组合权向量

（数据来源）

得到如下矩阵：

12695.9721555512695.971222；

B1595.972112612612651262195.9795.9795.97

19

34.527.1527.1513535353527.1527.15154.554.554.5；

B23554.51127.1527.153554.51127.1527.15101011016678870.71177116788；

B4B3780.811671780.888811776

由第3层的成对比较矩阵Bk，计算出权向量k(3)，最大特征值k，和一致性指标CIk

1

0.27844

k(3)

0.696063

0.011024

0.014473

4

k(3)

CIk(3)

6818

781k

2

0.236929

0.15216

0.305455

0.305455

4

0

3

0.303006

0.212124

0.242435

0.242435

4

0

4

0.272742

0.045429

0.318172

0.363657

4

0 0

(3)(3)(3),3,4)， 得到组合权向量Wk(3)(1(3),2进而由k(3)Wk(3)k(2)得到(3)(0.2862,0.2473,0.2361,0.2411)T，由上式可见，P1方案（组建校车方案）可使满意度最大，所以得出结论：学校应该选择组建校车队来满足教师的乘车需求。

最后，对组合权向量一致性检验

n4CIk(3)0,(k1,2,3,4)n13RIk(3)0.90

CR(3)kCIk(3)(3)00.1RIk所以，第三组的组合一致性检验通过，故而我们得到最终决策，学校应该建

20

立校车队，以满足教师的乘车需求

6.2组建校车队的可行方案集

在确定了学校要准备要组建校车队后，由于教师乘车人数是随机的，故我们假设附录3提供的信息为真实可用的数据，从而基于问题三中得出的统计规律，可以得出各发车时刻点的需求人数。

由于我们需要计算全局最优解，故而先求可行解的范围。

根据问题4，我们知道在不考虑运行成本的情况下，，最少的购车数量为8辆，即n8；另外，又由于多购买一辆车（以Ⅲ型车为例）来加强运输能力，每天的运行成本就会增加（我们假设所用车辆的使用年限为10年）：PP1P2((330000tip/10)17000)/3651200/30(1520S50)155.23，1.27100%，故而不会采1.17用多购买车的方案来减少每天的运营成本，即n8，所以可知，n8，即最佳的方案为购买8辆车。

确定每车的购买方案的初步范围并得出所有的可行解，由以上可知购车成本因素较大，故购车成本不会大于问题五所给出的平均成本。

所以可行解的范围可约束为：

，为tip(10.11.17)100%tip为购车比率（含税）38ni,j8i1j1

Kini,jmax(Di)itip(Cini,j)tip(181336481)ij其中，P2为买一辆Ⅲ型车每天所需成本，P1为Ⅲ型车多运行一次所需成本，tip为构车比率，S为两校区之间的距离，ni,j表示i车买j辆（i=1，2，3；j=1…8），Di表示为最大需求量（一辆车不可能在35分钟内用两次的情况下）

用C++编程求解（程序见附录9.7.1）可得构车方案的可行解集，见附录9.7.2：

6.3购车方案可行解的最优方案

设每个时间点的调运车辆数为Ni,j，（i=1..6；j=1..18）且由题意可知Ni,jni,j，若i车在j时间点不发车，则记为Ni,j0；P为所有花费，每百公里耗油量为li，所以，油价表示为：P1,iSliP0。驾驶员费用为P2,i，校车的折100

21

旧费用表示为PD,i，每天车费实际的分摊成本为PC,i。

则i车没运行一次的花费为PiP1iP2iSliP0P2i21002，Citip)PDi]S10PC,i；

36530得出模型：

[(PNii,jPC,i,(Ni,180)ij

PminPNii,jPNii,18PC,i,(Ni,180)jij约束条件：

Ni,jni,jt6

s..

KiNi,jdji1利用C++深度优先搜索（程序见附录9.7.3），我们可以得出最佳的购车方案和车辆调配方案，如下：

车辆购买分配方案：

Ⅰ型车 Ⅱ型车 Ⅲ型车 Ⅳ型车 Ⅴ型车 Ⅵ型车

车辆 1 3 1 0 1 1

车辆购买调配方案：

最优调度方案

A校区 B校区

7：30 调运Ⅰ、Ⅱ、Ⅵ型车各一辆 10：30 调运1辆Ⅵ型车

8：15 调运2辆Ⅱ型、1辆Ⅴ型车 11：30 调运1辆Ⅰ型车

9：25 调运1辆Ⅲ型车 12：25 调运1辆Ⅲ型车

11：45 调运1辆Ⅵ型车 13：00 调运1辆Ⅵ型车

13：05 调运1辆Ⅰ型车 16：00 调运1辆Ⅴ型车

15：00 调运1辆Ⅵ型车 17：15 调运2辆Ⅱ型、1辆Ⅵ型车

17：15 调运1辆Ⅲ型、1辆Ⅴ型车 17：30 调运1辆Ⅰ型车

19：30 调运1辆Ⅱ型车 17：45 调运1辆Ⅱ型车

20：30 调运1辆Ⅱ型、1辆Ⅲ型车

21：25 调运1辆Ⅴ型车

根据上述的购车方案和调车安排，可以最终得最优的组建校车队的成本为：2787元/天，每天的收益为4247.55元，所以，组建车队可以每天获利1460元。

六、结果分析与检验

6.1对模型六的灵敏度分析

22

由于在对是否决策组建校车队的层次分析法中权数的设定存在较大的人为主观性太强，因此，我们试图通过调整权数，用来检测模型的稳定性及灵敏度。

将权重确定为gfeh，从而可以列出调整后的成对比较矩阵：

11331A44322313441241232，

421得到成对比较矩阵的最大特征值为：4；权向量)(2(0.1000,0.2999,0T，进而由.0.400k(3)0,W0k(3).19k(2)9，并进行类似于9)上述的层次分析可得：k(3)(0.9371,0.6681,0.8869,0.9175)T。从而得出结论：仍然是选择校车为最优决策，说明模型稳定性较好。

七、模型评价与改进

7.1模型评价

我们通过一些合理的假设 ,针对车辆调度问题建立了一般模型。先对模型进行了合理的简化 ,采用由简单到复杂 ,逐步深入的方法 , 建立了针对车辆调度问题的一般规划模型，然后充分利用C++、SPSS、matlab与lingo等软件，并应用Dijstra算法和深度优先算法进行求解与优化,从而得到一个整体最优解以及最佳车辆调配方案。

我们通过对校车路径优化问题进行研究分析，得到较合理的校车路径，一方面可以减少学校投入校车数量，节约成本;另一方面可以缩短学生等待时间和校车总行驶时间，提高服务质量;除此以外，通过减少校车路径的数量，避开交通易堵塞的路线，有助于城市交通的发展。对于校车路径优化问题的研究能为其他企业职工通勤车、公交车调度、物流企业车辆线路优化等提供相关的理论指导和方法，起到一定的推广与借鉴作用。

7.2模型改进

(l)从模型构造角度来看，本文虽然尝试性的进行了数学规划模型的构建，但是只考虑了在一定假设条件下的一所学校的站点选择和路径安排问题。

由于实际情况中，客车的发车时间是关于期望准点tj发车的正态分布F0(tj)，对应的时点概率为Pk(tj)；在各个时间点上来乘车的人数也是随机的，经过重新

23

F1(tj),高峰期数据搜集，并运用聚类分析等统计工具，将人数的分布分为F2(tj)，平常期，所F3(tj)，低峰期以，第j个时间点可载人数SjdjF0(tj)Pk(tj)

进而目标函数可修正为：

PNiijPci,(Ni,180)ijfo(g(nij))min18minPNiijPNisPci,(Ni,180)s1iijnij8ij

kinijmax(Di)is..ttip(Cinij)tip(181336481)ijkNSdF(t)P(t)iijjj0jkjiNijnij实际问题可能会涉及到更多的随机因素，如时间窗的引入，以及学生、车辆、路况等不确定信息的考虑，这些问题将有待于今后进一步研究。

(2)从算法设计角度来看，本文针对所构建模型进行了深度优先算法的设计。但是优化问题还有许多高质量的启发式算法可以尝试，如神经网络等只能优化方法。寻找设计出一种更加有效的算法也是今后需要进一步研究的课题。

（3）在设计车辆调度方案时 ,并未充分考虑学生的乘车需求 ,在进行模型改进时 ,可以试着想其它办法找到一些更好的规则来进行对比与评价 ,从而得到更加优化的方案 ,使各方利益达到充分均衡 ,这也是模型改进的方向。

八、参考文献

[1] 陈婷、何中元，线性规划算法在车辆调度中的应用，《计算机工程与科学》2005

[2] 经怀明、张立军，多车型车辆调度问题的建模与仿真，《计算机仿真》2006

[3]姜启源，数学模型（第三版），北京：高等教育出版社，2003

[4]

徐淮涓，关于组合优化中的车辆调度问题，《淮阴师范学院学报》2002

24