校车调度问题(数学建模)
卷19造型相册
2002年2月
工程数学杂志
工程数学杂志
第19卷补编。
二零零二年二月
货号:100523085(2002)0520059208
公交车调度问题的研究
董强、刘朝晖、马毅
指导老师:吴孟达
(国防科技大学长沙410073)
编者按:本文建立了两个多目标规划模型，特别是选择运输能力与交通量的平衡作为目标函数具有创新性。找到最小数量的车辆
方法是正确的。作为双停车场模式的补充，单停车场模式简单且有自己的特点。运行发车时刻表是可行的，接近最优解。
摘要:本课题是具有软时间窗的单线单车辆公交调度问题。根据其多目标、多变量的动态特性，以满足不同的实际需要。
建立了两个多目标规划模型:双停车场模型和单停车场模型。双停车场模型的主要目标是使旅客运输能力和运输需求(实际旅客
交通量)达到最优匹配，单车场模型的主要目标是最小化乘客的平均不便和公交公司的成本，其目的是
为了兼顾乘客和公司双方的利益。两个模型主体采用时间步长法模拟实际操作过程，从而得出符合实际需要的结论
调度方案:静态调度和动态调度。
关键词:公交调度；软时间窗；全负荷率；时间步长法
分类编号:AMS(2000) 90C08中国图书馆分类法编号:TB114。1证件识别码:a。
1问题分析
我们把这个问题作为带软时间窗的单车运输问题来分析。从已知条件不能确定是单个停车场问题。
这仍然是一个多停车问题，所以我们建立了两个模型:双停车模型和单停车模型。其中，两码模型认为
A 13站和A 0站分别设有停车场A和B，可作为始发站和终点站，上下行线路独立。
垂直操作；单车场模式认为A 0站有转运能力但没有停车能力，实际上可以管理单车场模式。
解决方案是环路驱动。
2模型假设(略)
模型3的建立和求解
双停车场模型
1)模块1:出发时刻表的确定
根据前面的分析，考虑到乘客和公交公司双方的利益，分别建设单向上行线路和下行线路。
建立以下多目标规划模型:
目标函数:I供需最优匹配min ∑( Qi ×βi-V i) 2。
Ⅱ.每个周期中的行程次数是最小值{ Ni}
约束条件:①每期平均全负荷率限定为015 ≤βi ≤112。
②供需匹配比限制在α≤ K。
1.1符号描述:
倪第一期离职人数
βi
第一阶段的平均全负荷率
βi
= Ri/(c ×Ni) Ri为第I周期上车总人数，c = 100人/车次。
供需匹配率α = (∑V i)/(∑Qi)
k控制参数
一期齐客运能力(人×公里)
Qi =第I期发车次数Ni ×每辆车标准载客量c ×单程(上行或下行)总运行距离。
l .其中，上行时，L = 14.58km；下降时，L = 14。61公里。
五、一、第一时段所需客运能力(人×公里)
V i = ∑j
(x纪
2yji) L j j ∈(13，12？，1，0)，向上方向；j ∈ (0，2，3，？13)，下行
敬。
其中，x ji为第I个周期内某j站上车人数；Yji是第一时间段内j站下车人数。
L j是单向方向上j站和终点站之间的距离。
112目标函数描述:
目标函数I使第I次客运能力Qi与运输需求(实际客运量)V i达到最优匹配，βi则相反。
全负荷利率的影响。
目标函数ⅱ在约束条件下使每个周期所需的最大出行次数尽可能少，从而使车辆总数更小
更少。
113约束描述:
条件①是限制全负荷率以满足运营调度要求，并考虑乘客利益。
条件②是将供需匹配比α限制在常数k以下，根据参数k的变化，我们分别进行模拟，从而进行筛选
选择最合适的k值。
补充约束:为了保持每天始发站场发车时刻的车辆数不变，需要使总发车数和总收车数一致。
次数相等，即单程车次总数必须匹配(N1 = N2)，N1不能减(满)
负荷率限制)，所以我们在下游方向求解Ni时增加了约束∑N2 i = N1。
在约束条件∑N2 i = N1后，通过二次规划得到每个时间段的出发次数N1 i和N2 i。
2)模块2:操作过程模拟
在这一部分，我们采用时间步长法。根据一段时间内发车间隔t i相等的假设，t i可由Ni确定。
确定，从而得到出发时刻表。根据这个时刻表，模拟实际操作过程，目标是确定最满意的时刻表。
小车数为n，统计运行指标，搜索最优调度解。
211模拟子程序1:确定最小车辆数n
按照“按流发车”和“先进先出”的原则，起点至少要有一辆车可用。
(等待出发)。如果有多辆车，第一辆先启动，其他车辆排队等候。如果没有车送，那么
存在“不连续性”。完整的操作流程应确保车辆严格按照时刻表启动，不得中断。
假设a站13和A 0分别有停车场A和停车场B，不断有车从停车场开过来，同时接受停车场。
汽车中的汽车数量是一个随时间变化的状态变量。Na和Nb用于描述货场A和货场b之间没有交通流量。
所需最小车数破万，分别搜索运行过程中的最大值，则所需最小车数为n = Na+Nb。
2.2模拟子程序2:统计各种运行指标
60工程数学学报19卷
确定各项运营指标，利用模拟统计的计算方法，定量计算不同的运营指标。主要工作如下
可以通过量化分析运营指标来检验方案的可行性，以确定方案调整。
因为车次与发车时间一一对应，车辆排队顺序不变，所需车辆统一
编号一给，每列火车就确定了对应的车号，所以我们直接考察K列。
我们的统计指标及其定义如下:
平均全负荷速率向上方向β01 = (∑k
∑j
1
β( k，j1) / ( N1 J1)
下游方向β02 = (∑k
∑j
2
β( k，J2)/(N2·J2)
全负荷速率的分布可以由β( k，j)决定。
上行方向平均等待时间T1 = (∑k
∑j
1
T ( k，j1) / ( N1 J1)
下游方向T2 = (∑k
∑j
2
T ( k，J2)/(N2·J2)
符号描述:
D (k，J)第K次列车到达第J个车站时上下车人数之差；(已知)
C( k，J)K次列车离开J站时滞留在站台上的人数；C( k，j) = C( k - 1，j) + D ( k，j) -
(120 B(k，j - 1)
B (k，J)K次列车离开J站时的人数；B ( k，j) = B ( k，j - 1) + D ( k，j) + C( k -
1，j) - C( k，j)
T (k，j)是第k次列车驶离第j个车站时，掉队者在站台上的滞留时间；T ( k，j) = C( k，j) t i
β( k，j)是第k次列车驶离第j个车站时的全负荷率，β( k，j) = B (k，j)/100；
N1，N2是一天单程总车次；J1，J2为单向平台总数；
2.3模拟结果和统计指标分析
我们选取参数K = 018，0185，019进行模拟运算，结论如表1所示。(表中只给出了向上的方向。
值):
表1模拟上游方向得到的运行指标值
参数k，平均全负荷率β0，平均等待时间T，总车辆数N，总发车数N1
018 6817 % 3188 63 270
0185 7218 % 3188 63 255
019 7614 % 4124 62 243
0195 8014 % 7123 62 231
综合考虑以上参数，当k = 019时，各项指标都合适，平均全负荷率高，平均等待时间短。
短，所需车辆和总车次适中，所以我们选择k = 019。
下面我们给出k = 019时的具体仿真结果和统计指标。
结果:
(1)各时段单程发车次数(见表2)。
总车次N1 = N2 = 243。
相册公交调度问题61建模研究
表2k = 0时各时期的出发次数。9
期5 ~ 66 ~ 77 ~ 88 ~ 99 ~ 10 ~ 11112 13 65438。
上行7 28 41 23 13 1 13 11 1。
下行3 12 21 26 16 11 10 9 10。
时间段14 ~ 15 15 ~ 16 ~ 17 17 ~ 18 18 18 ~ 19。
上行链路9 9 19 24 8 5 5 4 2
下行1131930191111985
⑵各时段的单程发车时间间隔
由于一段时间内的发车间隔被假定为等距，因此很容易根据获得的列车数量确定发车间隔。
(3)单程发车时刻表(数据量太大，省略)
(4)车辆总数n = 62，其中A场57辆，B场5辆..
统计指标:
(1)平均全负荷率为β01 = 76。向上为4%，向下为β02 = 7019%。
⑵平均等待时间为T1 = 4。向上方向24分钟，向下方向T2 = 3148分钟。
3)调度方案
我们从不同的理解中得到了两种调度方案，它们的相似之处在于必须形成一个完整的作业流程，这样交通流才不会
间断的
3.1静态调度方案:
认为在这条路线上行驶的车辆总数是固定的，按照“按流行驶”和“先进”的原则，形成一个有序的交通流
先进先出"的原则，根据出发时间表。
所需车辆总数为62辆，其中a站A场13始发车辆数为57辆，a站B场始发车辆数为0辆。
汽车的数量是5辆。
3.2动态调度方案:
考虑到高峰期和低谷期实际需要的车辆数量不同，为了满足高峰期而获取的车辆数量是必然的。
与其他时间所需车辆数相比，即仅在高峰期就充分利用了62辆，造成了资源的浪费。我们认为公众
配送公司可以动态调度车辆，使部分车辆在特殊原因下得到维修和调整，节省运营成本。
由此，在保证交通流量不中断的情况下，我们可以计算出每个时段实际需要的最小车辆数。如表3所示
说明:(同时给出停车场A、B的停车状态和可自由控制的车辆数量)
表3动态调度各时段车辆数
期5 ~ 66 ~ 77 ~ 88 ~ 99 ~ 10 ~ 11112 13 65438。
所需汽车数量9 34 56 48 38 22 20 19 18
a场状态51 28 200 1 1 1 21 9。
b场状态2 0 4 14 24 29 30 32 35
时间段14 ~ 15 15 ~ 16 ~ 17 17 ~ 18 18 18 ~ 19。
所需车辆数量为17 20 29 42 41 25 17 14 10。
a现场状态9 10 9 5 6 25 37 43 48
b实地状况36 32 24 15 15 12 854
从上表可以得出以下结论:在车辆总数可以改变的情况下，7 :008 :00之间所需车辆最多为56辆。
汽车，在非高峰期，所需车辆数量少，A车场和B车场库存车辆较多，可根据实际情况
把这种情况用于其他目的。公交公司只需要根据表格中给出的每个时间段所需车辆数量进行调度，按照发车时间表发送即可。
工程数学学报62卷19
汽车也可以。
双自行车场模型
1)模型建立
根据问题分析，在公交运营模式按单车场组织后，我们建立如下带软时间窗的单车运输。
问题的多目标优化模型；
目标函数:IY1 = min {n}
ⅱy2 = min∑Ni
ⅲy3 = min(∑j
∑k
∑r
P( Ti) ) / ( R K M)
约束条件:①平均全负荷率限制在50% ≤β ≤120%。
②发车间隔t1≤5+5k的时限；k =
0 i是前期高峰期；
1 i不在前期高峰期的时候。
③ t i ∈{ 1，2，3？}
1.1目标函数描述:目标函数I使车辆总数最小，即使公司投资成本最小。
目标函数ⅱ最小化车辆总数，即使公司的运营成本最小化。
目标函数ⅲ是最小化所有顾客的平均不便。
112约束条件描述:条件③主要考虑可操作性，发车间隔以秒为单位，公交车司机不是。
方法，所以最低只能分次级别，那么发车间隔应该是1分的整数。
两倍
2)求解模型
该模型是一个多目标多约束的优化模型，很难找到全局最优解，所以我们先对多目标规划进行简化。
重新模拟，模拟操作过程。解决思路如下:
给出最初的出发时间表。
客运数据
客流分布(平均分布)
v
v
v
模仿
奔跑
数据
五.统计指数五.结论w .手工分析
2.1模型简化
简化多目标问题，可以有三个出发点:(1)分析目标之间的数学关系，减少目标数量。
目标函数或约束的数量。(2)根据有限的条件，挖掘特定数据的隐藏信息，降低求解的难度。③
分析每个目标的权重，去掉影响不大的目标函数，达到简化的目的。
目标ⅱ和目标ⅲ之间存在数学相关性，发现列车总量越多，乘客的不便越少。因此，y2和y3不
可以同时取最小值。我们考虑以III为主要目标，所以主要考虑目标函数III。从具体数据可以看出，在上行链路中
7:00-8:00，A13站上车人数达3626人，平均每分钟60人，A 12站上下车634人。
车上只有205人，是客流量最大的时候，发车间隔至少需要2分钟。从20公里/小时的平均速度
和圈距，可以得出此时至少需要45辆车。
根据以上分析，原模型简化为:
目标函数:y1 = min (∑j
∑k
∑r
P( Ti) ) / ( R K M)
y2 =最小M
约束条件:同上
建模专辑63公交调度问题研究
2.2操作过程模拟
(1)生成初始时刻表的方法
原则上可以随机生成初始时刻表，然后通过模拟判断搜索最优解，但搜索量太大又很小
很难保证收敛结果。因此，我们采用人机交互的方式。首先，我们分析数据，得到一个更合理的出发时间。
区间的近似值，产生初始时刻表(见表4)，然后搜索其附近的局部最优解。
表4初始出发时间表
期5 ~ 66 ~ 77 ~ 88 ~ 99 ~ 10 ~ 11112 13 65438。
Ti(分钟)10 3 2 3 8 8 8 8
时间段14 ~ 15 15 ~ 16 ~ 17 17 ~ 18 18 18 ~ 19。
Ti(点数)8 32 3 10 10 10 10 10 10
⑵模拟操作过程，统计指标，寻找最优解。
因为模拟的操作过程和两码模型差不多，这里就不细说了。
2.3结果和统计分析
通过模拟生成的多组发车时刻表，得到Y = 516的最低分，我们把这组解作为me。
局部最优解(其中用统计指标来描述我们对双方利益的照顾程度)的结果如下:
(1)车辆总数
平均速度的理想理解可以得到，所需车辆总数为45辆，加上2辆应急车，为47辆；
考虑到高峰车速小于20km/ h，而高峰时段人流量大是导致高峰车速略低于20 km/h的主要原因。
所以7:00-8:00的速度可以通过人流量和20 km/h的数据粗略估算为18km/ h左右这样一个高峰期
车辆总数最少为45辆，应修改为50辆，两辆应急车最终为52辆。
(2)全天总车次为M = 253 ×2 = 506。
(3)发车时刻表见表5(各时间段发车间隔简述)。
表5单货场模型的最优发车时刻表
期5 ~ 66 ~ 77 ~ 88 ~ 99 ~ 10 ~ 11112 13 65438。
Ti(分钟)10 2 2 2 4 6 6 8
时间段14 ~ 15 15 ~ 16 ~ 17 17 ~ 18 18 18 ~ 19。
Ti(点数)8 6 3 2 3 7 10 10 10
注:5 :00-6 :00只是统计划分，首班车可以在5 :00之前，也可以在5 :00之后。当然不是。
当你知道其他原理的时候，你可以假设第一辆车是5点。单停车场下行5 :45的亲们数据。
关闭。5:00-6:00，上行855人上车；下线***50人。一个可能的原因是上行链路在下午5:
00到6点有车要数；下行其实只能统计5: 45到6: 00的车。
统计指标:(1)乘客平均等待时间y3 = 516分钟。
⑵平均全负荷率β0 = 66。4%.
结论分析:从上面两张图表可以看出，我们的排班方案基本可以满足旅客候车时间的限制，高峰时段成倍增长。
乘客在5分钟内等车的概率为9219%，非高峰乘客在10分钟内等车的概率为
8917 %。
调度方案:(见表6)
64工程数学学报19卷
表6单站场动态调度方案
期5 ~ 66 ~ 77 ~ 88 ~ 99 ~ 10 ~ 11112 13 65438。
所需车辆数量为10 46 52 46 24 16 16 16 16 14。
时间段14 ~ 15 15 ~ 16 ~ 17 17 ~ 18 18 18 ~ 19。
所需车辆数量为14 16 30 46 30 14 10 10 8。
对4模型的进一步讨论
1)关于收集运行数据的讨论
因为我们假设乘客在一段时间内到达车站，服从均匀分布，实际上乘客不可能一直到达车站。
来自均匀分布。特别是在高峰时段，乘客到达时间的不均匀分布会使模型结论误差变小。
很大。我们建议采用以下方法来改进收集模式:
(1)取不等统计的区间。
在高峰时段，为了减弱旅客到达时间分布不均匀带来的影响，可以适当减小统计间隔。
时间但统计时间加密应该有一定的限制。对于客流量很小的时段，可以适当加大统计的间隔。
(2)增加能够反映滞留人数的统计数据。
(3)根据到站人数相等区分时间段统计。
方法是统计到站人数达到一定水平的时间点，其优点是能准确反映客流的变化。
条件，有利于车辆根据其分布密度进行调度，以便更好地满足乘客的需求。
2)单堆场调度方案和双堆场调度方案的选择
从结果分析可以看出，单堆场调度方案降低了公司的前期投资成本；双停车场调度方案的运行
成本小，更好地兼顾了乘客和公司双方的利益。我们建议在有双停车场的情况下，选择双停车场调度。
这个计划更好。需要规划路线，选择单停车场或双停车场时，建议根据实际费用选择边。
凯斯。
5模型的评价
本文的优点如下:
1)模型主体是用时间步长法模拟生成的发车时刻表的实际运行过程，精度高。
容量大，逻辑严密，计算速度快，说服力和适应性强。
2)定义一个统计指标，可以定量衡量我们的调度方案对乘客和公交公司双方利益的满意度。
马克。
3)在计算最小车辆数时，将两个停车场视为两个排放源，并核实两个停车场的停车状况
时间模拟，形成一个不间断的作业过程，从而获得所需的车辆数量。
这篇论文的缺点是:
1)只是对运行数据的收集方式给出了一些原则和思路，没有经过仿真验证。
2)对于到站旅客的分布，直接假设为均匀分布，其他分布不讨论。
建模专辑65的公交调度问题研究
参考资料:
[1]钱奎。运筹学[M]。北京科学出版社2000
[2]萧炎，傅卓，李玉安。带软时间窗的车辆路径问题及其应用前景[J].中国物流学会第六届学术交流会论文
集，第二卷，634-638
排序问题的研究
董强，刘朝辉，马毅
指导老师:吴梦2da
(国防科技大学，长沙410073)
文摘:由于这是一个带软时间窗的车辆调度问题，我们建立了两个多目标规划模型
els满足不同的实际情况:双2停车场模式和单2停车场模式。前者的主要目标
是使乘客容量与实际需求相匹配，而实际需求的目标是使平均值最小化
乘客的不便和公交公司的成本。这两种模式都考虑到了乘客和
公司。采用2步乘2步时间的方法，模拟实际过程，绘制了两种调度方案:静态调度方案
调度和动态调度。
关键词:排班；step 2 by 2 step time；调度计划
66工程数学学报19卷