摘要: 基于德胜快速路由于红绿灯太多导致的“快速路不快”的问题, 我们小组主要研究了城市交通网络中信号灯的实时控制的优化问题。通过给出0-1 整数规划的模型, 定量研究了交通网络中路口信号相位之间的关系, 并建立了交通信号控制适时优化模型对其进行优化。针对一组具有不同信号周期的路口信号灯, 假设每个路口的相序已知, 任意两个路口的相位差未知, 综合考虑绿信比和相位差, 寻找最优控制策略。
针对第一题，我们假设车流量是按照泊松
关键词: 0-1整数规划 交通网络 信号控制 排队算法 蚂蚁算法 退火运算 粒子群优化
本文给出了0- 1 线性规划模型对实时交通信号进行优化。 模型中假定交通网络路口具有不同的信号周期和相位差预先 未知, 在各路口信号周期的最小公倍数的时间段内, 通过决定 信号灯在任意的时间段内的状态来最小化总的车辆延迟时间。 问题中涉及大量的0- 1 变量, 但是通过有效约束可使其计算量 大大减少
主干道绿波工程研究
周期：是指同一路口信号灯颜色由绿变黄再变红，如此循环变化一次，所需的时间，也称周期长，即红、
黄、绿灯时间之和．
相位：即信号相位，是指一个路口在一个周期时间内按需求人为设定的，同时取得通行权的一个或几
个交通流的序列组．
相位差：具有相同周期长的相邻路口，在同方向上的两个相关相位的启动时间差称为相位差．
绿信比：是指在一个周期内交叉路El 的各个相位不同方向中某个方向出现绿灯的时间与周期长之比．
到达率：交叉路1：3非饱和情况下到达率为进El 道的流量．
饱和流量：是衡量一个路口交通流施放能力的重要参数，通常是指一个绿灯时间内的连续通过路El 的
最大车流量(单位：车／秒) ．
流量系数(流量比) ：是实际流量与饱和流量的比值．既是计算信号配时的重要参数，又是衡量路口阻
万方数据
16期朱道元：第五届全国研究生数学建模竞赛5
塞程度的一个尺度．
进口道通行能力：等于进口道饱和流量与该流向所在相位的绿信比之积．
交叉口的饱和度：流量与进口道通行能力之比．
绿灯间隔时间：是指从上一个获得通行权的绿灯变黄开始。到下一个得到通行权的相位绿灯开始的一
段时间(即是黄灯时间和红灯时间之和) ．
有效绿灯时间：是指被有效利用的实际车辆通行时间．它等于绿灯时间与黄灯时间之和减去头车启动
(因为红灯时头车速为零) 的损失时间．
延误：是指交通冲突或信号控制设施的限制给车辆带来的时间损失．它是计算信号配时和衡量路口通
行效果的一个重要参数，也常作为确定信号控制系统性能的重要参量．
公路通行能力：是指在给定的道路和交通条件下，公路上的某个最小或最困难的断面或某个规定的路
段上单位时间内平均能够通过的最大车辆数，一般采用小时为单位，故通行能力一般以每小时能够通过的
最大车辆数计．
附3交通流分布规律(仅供参考，不受此限)
泊松分布
5 模型的评价
本文的优点如下:
1) 模型的主体是采用时间步长法, 模拟生成的发车时刻表的实际运行过程, 准确性高, 容量大, 逻辑性严格, 计算速度快, 具有较强的说服力和适应能力。
2) 定义了能定量衡量我们的调度方案对乘客和公交公司双方利益满足程度的统计指 标。
3) 在求最少车辆数时, 将两个车场看作两个发射源, 通过对两个车场的存车状态的实 时模拟, 形成不间断的运营过程, 从而求得所需车辆数目。
本文的缺点是:
1) 对于运营数据的采集方式, 只给出了一些原则和想法, 没有经过仿真验证。
2) 对于乘客到站的分布, 直接假设为均匀分布, 没有对其他分布的情况再作讨论。
4 模型的进一步讨论
1) 关于采集运营数据的讨论
由于我们假设在一个时段内乘客到站服从均匀分布, 而实际中乘客到站时间不可能都服 从均匀分布。特别是在高峰期的情况下, 乘客到站时间的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法:
⑴ 采取不等的统计人数的间隔时间
在高峰期的情况下, 为削弱乘客到站时间不均匀分布带来的影响, 可适当减小统计的间隔 时间但统计时间加密应有一定限度。对客流量很小的时段, 我们可适当增大统计的间隔时间。 ⑵ 增加能反应有关滞留人数的统计数据。
⑶ 按相等到站人数来区分时间段的统计
方法是统计达到一定到站人数时的时间点, 其优点是能较为准确地反映客流量的变化情 况, 有利于按其分布的疏密进行车辆调度, 以更好的满足乘客的需要。
2) 单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本; 双车场调度方案的运营成 本小, 更好的兼顾到乘客与公司双方的利益。我们建议, 在有双车场的条件下选取双车场调度 方案更好。当需进行路线规划, 需要选取单车场或双车场时, 建议根据实际所需成本来选取方 案。
5问题分析
我们分析该问题为一带软时间窗的单车型运输问题。由已知条件无法确定是单车场问题 还是多车场问题, 故我们分别建立两个模型:双车场模型和单车场模型。其中, 双车场模型认为 车站A 13 和车站A 0 分别有车场A 和B 存车, 即均可作为始发站和终点站, 上行和下行路线独 立运行; 单车场模型认为A 0 车站有转运能力但没有存车能力, 这样实际上可将单车场方式理 解为环线行驶。
2 模型假设(略)
3 模型的建立与求解
㈠ 双车场模型
1) 模块一:发车时刻表的确定
依据前面的分析, 兼顾乘客与公交公司双方的利益, 分别对单程的上行路线和下行路线建 立如下的多目标规划模型:
目标函数: Ⅰ 供求的最优匹配 min Σ( Qi ×βi - V i ) 2
Ⅱ 各时段的发车车次均最小min { Ni }
约束条件: ① 各时段的平均满载率限制015 ≤βi ≤112
② 供求匹配比限制α ≤ k
' 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
1. 1 符号说明:
N i 第i 时段发车次数
βi
第i 时段的平均满载率
βi
= Ri / ( c ×N i ) R i 为第i 时段的总上车人数, c = 100 人/ 车次
α 供求匹配比 α = ( ΣV i ) / ( ΣQ i )
k 控制参数
Q i 第i 时段运客能力(人×公里)
Q i = 第i 时段发车次数N i ×每辆车标准载客量c ×单程(上行或下行) 总运行距离 L 。其中, 上行时, L = 14. 58 公里; 下行时, L = 14. 61 公里
V i 第i 时段的需要运客量(人×公里)
V i =
( x ji Σj
2y ji ) L j j ∈(13 , 12 ⋯, 1 , 0) , 上行方向; j ∈ (0 , 2 , 3 , ⋯13) , 下行方
向。
其中, x ji 为第i 时段内A j 站的上车人数; yji 为第i 时段内A j 站的下车人数
L j 为A j 站距该单程方向上终点站的距离。
112 目标函数说明:
目标函数Ⅰ使第i 时段的运客能力Qi 与运输需求(实际客运量) V i 达到最优匹配, βi 反 映满载率高低的影响。
目标函数Ⅱ使各时段所需的最大发车次, 在满足约束条件下尽可能少, 以使总车辆数较 少。
113 约束条件说明:
条件①是限制满载率满足运营调度要求, 是考虑了乘客的利益。
条件②是限制供求匹配比α小于常数k 。我们根据参数k 的变动量分别进行模拟, 从而筛 选最恰当的k 值。
补充约束条件:为使始发站车场的每天起始时刻的车辆数保持不变, 需使总发车次数与总收车 次数相等, 即必须使单程车次总数达到匹配( N1 = N2) ,而N 1 不能减少(受满
载率限制) ,因此我们在求解下行方向的N i 时增加约束ΣN 2 i = N1. 在增添
约束条件ΣN 2 i = N1 之后, 用二次规划求得各时段发车次数N 1 i 和N 2 i 。
2) 模块二:运营过程的模拟
在这部分, 我们采用时间步长法, 根据假设一个时段内发车间隔时间t i 相等, 则t i 可由N i 确定, 从而得到发车时刻表。按此发车时刻表模拟实际运行过程, 目标是确定满足时刻表的最 小车辆数n ,统计各项运营指标, 搜索最优调度方案解。
211 模拟子程序一:确定最小车辆数目n
根据“按流发车”和“先进先出”的原则, 对起点站, 在发车时刻应至少有一辆车可以发出
(处于等待发车状态) 。若有多辆车, 则先进站者先发车, 其余车辆“排队”等候; 若无车可发, 则
出现“间断”。完整的运营过程应保证车辆严格按时刻表发车, 不发生间断。
设A 13 站和A 0 站分别有车场A 和B ,从车场中不断有车发出, 同时接受车进场, 则车场 中的车的数目是随时间变化的状态量。用Na 和Nb 来描述车场A 和车场B 中要满足车流不间 断所需的最小数目, 分别搜索其在运行过程中的最大值, 则所需最小车量数目n = Na + Nb。 2. 2 模拟子程序二:统计各项运营指标
60 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
确定各项运营指标, 采用模拟统计的计算方法, 对不同的运营指标进行定量计算, 主要功 能是通过定量分析运营指标来检验方案的可行性, 以确定方案调整。
由于车次与发车时刻一一对应, 而车辆的队列顺序是不发生改变, 因而对所需车辆进行统 一编号, 则对每一车次, 与其对应的车辆编号是确定的, 故我们直接对第k 次车进行考察。 我们统计的指标及其定义如下:
平均满载率 上行方向 β01 = ( Σk
Σ
1 j
β( k , j1) / ( N1 ·J 1)
下行方向β02 = ( Σk
Σ
2 j
β( k , j2) / ( N2 ·J 2)
满载率分布可以由β( k , j) 确定。
平均候车时间上行方向T 1 = ( Σk
Σ
1 j
T ( k , j1) / ( N1 ·J 1)
下行方向T 2 = ( Σk
Σ
2 j
T ( k , j2) / ( N2 ·J 2)
符号说明:
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 ;
N 1 , N2 为一天单程所发的车次总数; J1 , J2 为单程站台总数;
2. 3 模拟结果及统计指标分析
我们选取参数k = 018 , 0185 , 019 进行模拟运行, 所得结论如表1 。(表中只给出上行方向 值) :
表1 模拟上行方向所得营运指标值
参数k 平均满载率β0 平均候车时间T 所需总车辆n 总发车次数N 1
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 时的具体模拟结果及统计指标。
结果:
⑴ 各时段内单程发车次数(见表2)
总车次N 1 = N2 = 243 。
建模专辑 公交车调度问题的研究61
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
表2 k = 0. 9 时各时段中的发车次数
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
上行7 28 41 23 13 11 13 11 11
下行3 12 21 26 16 11 10 9 10
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 上行9 9 19 24 8 5 5 4 2
下行11 13 19 30 19 11 9 8 5
⑵ 各时段单程发车时间间隔
由于一个时段内的发车间隔已假设为等距, 所以由所得的车次很容易确定发车时间间隔。 ⑶ 单程发车时刻表(数据量太大, 故略)
⑷ 总车辆数n = 62 , 其中场A 存车57 辆, 场B 存车5 辆。
统计指标:
⑴ 平均满载率 上行方向 β01 = 76. 4 % 下行方向 β02 = 7019 % ⑵ 平均候车时间上行方向T 1 = 4. 24 分下行方向T 2 = 3148 分
3) 调度方案
我们由不同的理解得到两种调度方案, 其共同点是都必须形成完整的运营过程, 使车流不 间断。
3. 1 静态调度方案:
认为在该路线上运行的总车数固定不变, 形成序贯流动的车流, 依照“按流开车”和“先进 先出”的原则, 按发车时刻表发车。
所需总车辆数为62 , 其中从A 13 站的车场A 始发的车数为57 , 从A 0 站的车场B 始发的 车数为5 。
3. 2 动态调度方案:
考虑高峰期与低谷期实际需要的车辆数目不同, 为了满足高峰期而求得的车辆数目必然 大与其他时间需要的车辆数, 即62 辆车只在高峰期得到充分利用, 造成资源浪费。我们认为公 交公司可进行车辆动态调度, 让一些车辆可以在特殊原因下进行修理调整, 并节约运营成本。 由此我们在保证车流不间断的条件下, 计算得出各个时段内实际所需的最小车辆数。如表3 所
示: (同时给出A 、B 车场的存车状态, 可以自由支配的车辆数目)
表3 动态调度中各时段的车辆数
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需车数9 34 56 48 38 22 20 19 18
A 场状态51 28 2 0 0 11 12 11 9
B 场状态2 0 4 14 24 29 30 32 35
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 所需车数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 8 5 4
由上表我们得出:在总车辆数目可变动的情况下, 所需的最大车辆数为7 :008 :00 间的56 辆, 在非高峰期时所需车辆数目都较小, A 车场和B 车场都有较多车辆库存着, 可以根据实际 情况挪作它用。公交公司只需按表中所给的每个时段的所需车辆数进行调度, 按发车时刻表发
62 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
车即可。
㈡ 单车场模型
1) 模型的建立
根据问题分析, 公交营运方式按单车场组织后我们建立如下带软时间窗口的单车型运输 问题多目标优化模型:
目标函数: Ⅰ y 1 = min { n}
Ⅱ y 2 = min ΣN i
Ⅲ y 3 = min ( Σj
Σ
Σk r
P( Ti ) ) / ( R ·K ·M)
约束条件: ①平均满载率限制50 % ≤β ≤120 %
②发车间隔时间限制t i ≤5 + 5 k ; k =
0 i 为早高峰期时;
1 i 为非早高峰期时。
③ t i ∈{ 1 , 2 , 3 ⋯}
1. 1 目标函数说明: 目标函数Ⅰ使总车辆数目最小, 即使公司的投资成本达到最小。 目标函数Ⅱ使总车次数最小, 即使公司的运营成本达到最小。
目标函数Ⅲ是使所有顾客的平均不方便程度达到最小。
112 约束条件说明: 条件③主要是考虑到可操作性, 发车间隔划分到秒一级, 公交司机是没 法把握的, 故最小只能划分到分一级, 那么发车间隔就应是1 分的整数 倍
2) 模型的求解
本模型是多目标、多约束的优化模型, 很难求出全局最优解, 所以我们先将多目标规化简, 再仿真模拟运营过程求解。求解思路如下:
给出初始发车时刻表
客运数据
客流分布(平均分布)
v
v
v
模拟
运营
数据
v 统计指标v 结论w 人工分析
2. 1 模型化简
化简多目标问题, 我们可以有三个出发点: ①分析各目标之间相关联的数学关系, 减少目 标函数数目或约束条件数目。②依限定条件, 针对具体数据挖掘隐含信息以降低求解难度。③
分析各目标权重, 去掉影响很小的目标函数, 从而达到简化目的。
分析目标Ⅱ与Ⅲ存在数学关联, 发现总车次越多, 乘客不方便程度越小。因此y 2 与y 3 不 能同时取最小值。我们认为Ⅲ为主要目标, 故主要考虑目标函数Ⅲ。从具体数据可知, 在上行 方向7 :00 ～ 8 :00 , A 13 站上车人数达3626 人, 平均每分钟到达60 人, A 12 站上车634 人而下
车仅205 人, 为客流量最大的时段, 发车间隔时间至少需要2 分钟。由平均速度20 公里/ 小时 及环行距离, 可得到此时至少需45 辆车。
由以上分析将原模型简化为:
目标函数: y 1 = min ( Σj
Σ
Σk r
P( Ti ) ) / ( R ·K ·M)
y 2 = min M
约束条件: 同上
建模专辑 公交车调度问题的研究63
2. 2 运营过程模拟
⑴ 初始时刻表的产生方法
原则上初始时刻表可以随机产生, 然后模拟判断搜索出较优解, 但这样搜索量太大, 且很 难保证有一个收敛结果。因此我们采用人机交互的方式, 首先分析数据得出比较合理的发车时
间间隔的近似值, 产生初始时刻表(见表4) ,然后在其附近搜索局部最优解。 表4 初始发车时刻表
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
t i (分) 10 3 2 3 8 8 8 8 8
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 t i (分) 8 8 3 2 3 10 10 10 10
⑵ 模拟运营过程, 统计各指标, 搜索最优解
由于模拟运营过程与双车场模型大同小异, 故我们在此不再详述。
2. 3 结果及统计分析
对仿真产生的多组发车时刻表进行模拟获得最小的Y = 516 分, 我们把这一组解做为我 们的局部最优解, 其结果(其中统计指标用来描述我们以怎样的程度照顾双方利益) 如下: ⑴ 总车数
理想的理解平均速度可得所需总车数为45 辆, 加2 辆应急, 为47 辆;
考虑高峰期车速小于20km / h , 高峰期人流量大是造成高峰期速度稍低于20km / h 的主 因, 那么通过人流量数据和20km / h 就可大致推算7 :00 - 8 :00 速度约为18km / h 。这样高峰期 的最小总车数45 辆, 应修正为50 辆, 加2 辆应急最终为52 辆。
⑵ 全天总车次M = 253 ×2 = 506 次
⑶ 发车时刻表见表5 (用各时段发车间隔时间简述)
表5 单车场模型最优发车时刻表
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
t i (分) 10 2 2 2 4 6 6 6 8
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 t i (分) 8 6 3 2 3 7 10 10 10
注:5 :00 - 6 :00 只是一种统计划分, 首发车可以在5 :00 之前, 也可在5 :00 之后。当然当不 知道其它原则时可以假设首发车为5 :00 发。对单车场下行线始发为5 :45 与数据相吻 合。5 :00 - 6 :00 上行线共855 人上车; 下行线共50 人。其可能原因之一就是上行在5 : 00 - 6 :00 都有车可统计; 而下行只在5 :45 - 6 :00 中可实际统计到车。 统计指标: ⑴乘客平均候车时间 y 3 = 516 分
⑵平均满载率 β0 = 66. 4 %
结论分析:由上面两个图表可见我们的调度方案基本上能满足乘客候车时间的限制, 高峰期乘 客在5 分钟内等到车的概率为9219 % ,非高峰期乘客在10 分钟内等到车的概率为 8917 %。
调度方案: (见表6)
64 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
表6 单车场动态调度方案
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需车辆数10 46 52 46 24 16 16 16 14
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
所需车辆数14 16 30 46 30 14 10 10 8
4 模型的进一步讨论
1) 关于采集运营数据的讨论
由于我们假设在一个时段内乘客到站服从均匀分布, 而实际中乘客到站时间不可能都服 从均匀分布。特别是在高峰期的情况下, 乘客到站时间的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法:
⑴ 采取不等的统计人数的间隔时间
在高峰期的情况下, 为削弱乘客到站时间不均匀分布带来的影响, 可适当减小统计的间隔 时间但统计时间加密应有一定限度。对客流量很小的时段, 我们可适当增大统计的间隔时间。 ⑵ 增加能反应有关滞留人数的统计数据。
⑶ 按相等到站人数来区分时间段的统计
方法是统计达到一定到站人数时的时间点, 其优点是能较为准确地反映客流量的变化情 况, 有利于按其分布的疏密进行车辆调度, 以更好的满足乘客的需要。
2) 单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本; 双车场调度方案的运营成 本小, 更好的兼顾到乘客与公司双方的利益。我们建议, 在有双车场的条件下选取双车场调度 方案更好。当需进行路线规划, 需要选取单车场或双车场时, 建议根据实际所需成本来选取方 案。
5
（p66）
1 问题重述(略)
2 基本假设
1) 公交车在该线路行进中以20 公里/ 小时的速度匀速运行, 即不考虑启动和停车, 每 一站停车延迟及其他因素的影响
2) 公交车按发车时刻表顺次发车, 准时到达每个站点
3) 乘客候车时间一般不超过10 分钟, 早高峰时一般不超过5 分钟
4) 满载率不要超过120 % , 一般也不应低于50 %
3 符号说明
P i : i 时段内的配车数(时段配车数) (车次) ; ρi : i 时段内的期望满载率;
H i : i 时段内的小时最高断面的通过量(人) ; Ni : i 时段内的期望占用量(人) ;
C : 车容量( C = 车型定员+ 最大允许站人数) (人) ; L : 路线长度(km) ;
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
Q i : i 时段内的乘客周转量(人km) ; δi : i 时段内乘客的满意率;
δ -
: 乘客的平均满意率; Wi : i 时段内乘客的平均等待时间
η -
: 公交公司的平均满意率;
4 问题(1) 模型的分析、建立及求解
下面我们逐步以两种不同的方法对公交调度方案进
问题(2) 基本假设
1 模型假设
根据题目的要求, 并为了到达将实际情况进行抽象的目的, 在我们的模型中有如下假设:
1) 汽车的速度恒定为20km/ h ,且无特殊事件发生(如抛锚) 。
2) 以分钟作为最小的时间单位, 这对安排时刻表是合理的。
3) 汽车在站台的停留时间仅由该站的全天人流量决定, 而与时间无关, 上限为2 分钟、 下限为0 分钟。
4) 在车站等待的人绝大多数不会离去。
5) 汽车严格按照时刻表运行, 在基本模型中排除汽车中途调头的情况(如机动车) 。
6) 在基本模型中, 无论车程多少, 票价单一; 且绝大多数乘客自觉付费。
4 建模前的准备
1) 对问题的初步分析
我们考虑三组相关的因素:公共汽车, 汽车站与乘客对模型的影响。
i) 与公共汽车有关的因素:离开公共汽车总站的时间, 到达每一站的时间, 在每一站下 车的乘客数, 在每一站的停留时间, 载客总数, 行进速度等。
ii) 与车站有关的因素:线路上汽车的位置, 车站间距, 乘客到来的函数表示, 等车的乘客 数, 上一辆车离开车站过去的时间等。
iii) 与乘客有关的因素:到达某一车站的时间, 乘车距离(站数) ,侯车时间等。
2) 曲线的拟合
分析样本数据, 可知对于某车站全天的上(下) 车乘客数N ( t) 是时间t 的递增函数, N ( t) = N ( t - 1) + qt , 其中q t 为第t 时间内此站的上(下) 车人数, 我们可以由此来拟合其分
布函数。由样本数据知每一车站每天有两次波峰, 故根据最小二乘法将分布函数拟合为关于 t 的五次多项式。
5
摘要: 基于德胜快速路由于红绿灯太多导致的“快速路不快”的问题, 我们小组主要研究了城市交通网络中信号灯的实时控制的优化问题。通过给出0-1 整数规划的模型, 定量研究了交通网络中路口信号相位之间的关系, 并建立了交通信号控制适时优化模型对其进行优化。针对一组具有不同信号周期的路口信号灯, 假设每个路口的相序已知, 任意两个路口的相位差未知, 综合考虑绿信比和相位差, 寻找最优控制策略。
针对第一题，我们假设车流量是按照泊松
关键词: 0-1整数规划 交通网络 信号控制 排队算法 蚂蚁算法 退火运算 粒子群优化
本文给出了0- 1 线性规划模型对实时交通信号进行优化。 模型中假定交通网络路口具有不同的信号周期和相位差预先 未知, 在各路口信号周期的最小公倍数的时间段内, 通过决定 信号灯在任意的时间段内的状态来最小化总的车辆延迟时间。 问题中涉及大量的0- 1 变量, 但是通过有效约束可使其计算量 大大减少
主干道绿波工程研究
周期：是指同一路口信号灯颜色由绿变黄再变红，如此循环变化一次，所需的时间，也称周期长，即红、
黄、绿灯时间之和．
相位：即信号相位，是指一个路口在一个周期时间内按需求人为设定的，同时取得通行权的一个或几
个交通流的序列组．
相位差：具有相同周期长的相邻路口，在同方向上的两个相关相位的启动时间差称为相位差．
绿信比：是指在一个周期内交叉路El 的各个相位不同方向中某个方向出现绿灯的时间与周期长之比．
到达率：交叉路1：3非饱和情况下到达率为进El 道的流量．
饱和流量：是衡量一个路口交通流施放能力的重要参数，通常是指一个绿灯时间内的连续通过路El 的
最大车流量(单位：车／秒) ．
流量系数(流量比) ：是实际流量与饱和流量的比值．既是计算信号配时的重要参数，又是衡量路口阻
万方数据
16期朱道元：第五届全国研究生数学建模竞赛5
塞程度的一个尺度．
进口道通行能力：等于进口道饱和流量与该流向所在相位的绿信比之积．
交叉口的饱和度：流量与进口道通行能力之比．
绿灯间隔时间：是指从上一个获得通行权的绿灯变黄开始。到下一个得到通行权的相位绿灯开始的一
段时间(即是黄灯时间和红灯时间之和) ．
有效绿灯时间：是指被有效利用的实际车辆通行时间．它等于绿灯时间与黄灯时间之和减去头车启动
(因为红灯时头车速为零) 的损失时间．
延误：是指交通冲突或信号控制设施的限制给车辆带来的时间损失．它是计算信号配时和衡量路口通
行效果的一个重要参数，也常作为确定信号控制系统性能的重要参量．
公路通行能力：是指在给定的道路和交通条件下，公路上的某个最小或最困难的断面或某个规定的路
段上单位时间内平均能够通过的最大车辆数，一般采用小时为单位，故通行能力一般以每小时能够通过的
最大车辆数计．
附3交通流分布规律(仅供参考，不受此限)
泊松分布
5 模型的评价
本文的优点如下:
1) 模型的主体是采用时间步长法, 模拟生成的发车时刻表的实际运行过程, 准确性高, 容量大, 逻辑性严格, 计算速度快, 具有较强的说服力和适应能力。
2) 定义了能定量衡量我们的调度方案对乘客和公交公司双方利益满足程度的统计指 标。
3) 在求最少车辆数时, 将两个车场看作两个发射源, 通过对两个车场的存车状态的实 时模拟, 形成不间断的运营过程, 从而求得所需车辆数目。
本文的缺点是:
1) 对于运营数据的采集方式, 只给出了一些原则和想法, 没有经过仿真验证。
2) 对于乘客到站的分布, 直接假设为均匀分布, 没有对其他分布的情况再作讨论。
4 模型的进一步讨论
1) 关于采集运营数据的讨论
由于我们假设在一个时段内乘客到站服从均匀分布, 而实际中乘客到站时间不可能都服 从均匀分布。特别是在高峰期的情况下, 乘客到站时间的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法:
⑴ 采取不等的统计人数的间隔时间
在高峰期的情况下, 为削弱乘客到站时间不均匀分布带来的影响, 可适当减小统计的间隔 时间但统计时间加密应有一定限度。对客流量很小的时段, 我们可适当增大统计的间隔时间。 ⑵ 增加能反应有关滞留人数的统计数据。
⑶ 按相等到站人数来区分时间段的统计
方法是统计达到一定到站人数时的时间点, 其优点是能较为准确地反映客流量的变化情 况, 有利于按其分布的疏密进行车辆调度, 以更好的满足乘客的需要。
2) 单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本; 双车场调度方案的运营成 本小, 更好的兼顾到乘客与公司双方的利益。我们建议, 在有双车场的条件下选取双车场调度 方案更好。当需进行路线规划, 需要选取单车场或双车场时, 建议根据实际所需成本来选取方 案。
5问题分析
我们分析该问题为一带软时间窗的单车型运输问题。由已知条件无法确定是单车场问题 还是多车场问题, 故我们分别建立两个模型:双车场模型和单车场模型。其中, 双车场模型认为 车站A 13 和车站A 0 分别有车场A 和B 存车, 即均可作为始发站和终点站, 上行和下行路线独 立运行; 单车场模型认为A 0 车站有转运能力但没有存车能力, 这样实际上可将单车场方式理 解为环线行驶。
2 模型假设(略)
3 模型的建立与求解
㈠ 双车场模型
1) 模块一:发车时刻表的确定
依据前面的分析, 兼顾乘客与公交公司双方的利益, 分别对单程的上行路线和下行路线建 立如下的多目标规划模型:
目标函数: Ⅰ 供求的最优匹配 min Σ( Qi ×βi - V i ) 2
Ⅱ 各时段的发车车次均最小min { Ni }
约束条件: ① 各时段的平均满载率限制015 ≤βi ≤112
② 供求匹配比限制α ≤ k
' 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
1. 1 符号说明:
N i 第i 时段发车次数
βi
第i 时段的平均满载率
βi
= Ri / ( c ×N i ) R i 为第i 时段的总上车人数, c = 100 人/ 车次
α 供求匹配比 α = ( ΣV i ) / ( ΣQ i )
k 控制参数
Q i 第i 时段运客能力(人×公里)
Q i = 第i 时段发车次数N i ×每辆车标准载客量c ×单程(上行或下行) 总运行距离 L 。其中, 上行时, L = 14. 58 公里; 下行时, L = 14. 61 公里
V i 第i 时段的需要运客量(人×公里)
V i =
( x ji Σj
2y ji ) L j j ∈(13 , 12 ⋯, 1 , 0) , 上行方向; j ∈ (0 , 2 , 3 , ⋯13) , 下行方
向。
其中, x ji 为第i 时段内A j 站的上车人数; yji 为第i 时段内A j 站的下车人数
L j 为A j 站距该单程方向上终点站的距离。
112 目标函数说明:
目标函数Ⅰ使第i 时段的运客能力Qi 与运输需求(实际客运量) V i 达到最优匹配, βi 反 映满载率高低的影响。
目标函数Ⅱ使各时段所需的最大发车次, 在满足约束条件下尽可能少, 以使总车辆数较 少。
113 约束条件说明:
条件①是限制满载率满足运营调度要求, 是考虑了乘客的利益。
条件②是限制供求匹配比α小于常数k 。我们根据参数k 的变动量分别进行模拟, 从而筛 选最恰当的k 值。
补充约束条件:为使始发站车场的每天起始时刻的车辆数保持不变, 需使总发车次数与总收车 次数相等, 即必须使单程车次总数达到匹配( N1 = N2) ,而N 1 不能减少(受满
载率限制) ,因此我们在求解下行方向的N i 时增加约束ΣN 2 i = N1. 在增添
约束条件ΣN 2 i = N1 之后, 用二次规划求得各时段发车次数N 1 i 和N 2 i 。
2) 模块二:运营过程的模拟
在这部分, 我们采用时间步长法, 根据假设一个时段内发车间隔时间t i 相等, 则t i 可由N i 确定, 从而得到发车时刻表。按此发车时刻表模拟实际运行过程, 目标是确定满足时刻表的最 小车辆数n ,统计各项运营指标, 搜索最优调度方案解。
211 模拟子程序一:确定最小车辆数目n
根据“按流发车”和“先进先出”的原则, 对起点站, 在发车时刻应至少有一辆车可以发出
(处于等待发车状态) 。若有多辆车, 则先进站者先发车, 其余车辆“排队”等候; 若无车可发, 则
出现“间断”。完整的运营过程应保证车辆严格按时刻表发车, 不发生间断。
设A 13 站和A 0 站分别有车场A 和B ,从车场中不断有车发出, 同时接受车进场, 则车场 中的车的数目是随时间变化的状态量。用Na 和Nb 来描述车场A 和车场B 中要满足车流不间 断所需的最小数目, 分别搜索其在运行过程中的最大值, 则所需最小车量数目n = Na + Nb。 2. 2 模拟子程序二:统计各项运营指标
60 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
确定各项运营指标, 采用模拟统计的计算方法, 对不同的运营指标进行定量计算, 主要功 能是通过定量分析运营指标来检验方案的可行性, 以确定方案调整。
由于车次与发车时刻一一对应, 而车辆的队列顺序是不发生改变, 因而对所需车辆进行统 一编号, 则对每一车次, 与其对应的车辆编号是确定的, 故我们直接对第k 次车进行考察。 我们统计的指标及其定义如下:
平均满载率 上行方向 β01 = ( Σk
Σ
1 j
β( k , j1) / ( N1 ·J 1)
下行方向β02 = ( Σk
Σ
2 j
β( k , j2) / ( N2 ·J 2)
满载率分布可以由β( k , j) 确定。
平均候车时间上行方向T 1 = ( Σk
Σ
1 j
T ( k , j1) / ( N1 ·J 1)
下行方向T 2 = ( Σk
Σ
2 j
T ( k , j2) / ( N2 ·J 2)
符号说明:
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 ;
N 1 , N2 为一天单程所发的车次总数; J1 , J2 为单程站台总数;
2. 3 模拟结果及统计指标分析
我们选取参数k = 018 , 0185 , 019 进行模拟运行, 所得结论如表1 。(表中只给出上行方向 值) :
表1 模拟上行方向所得营运指标值
参数k 平均满载率β0 平均候车时间T 所需总车辆n 总发车次数N 1
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 时的具体模拟结果及统计指标。
结果:
⑴ 各时段内单程发车次数(见表2)
总车次N 1 = N2 = 243 。
建模专辑 公交车调度问题的研究61
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
表2 k = 0. 9 时各时段中的发车次数
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
上行7 28 41 23 13 11 13 11 11
下行3 12 21 26 16 11 10 9 10
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 上行9 9 19 24 8 5 5 4 2
下行11 13 19 30 19 11 9 8 5
⑵ 各时段单程发车时间间隔
由于一个时段内的发车间隔已假设为等距, 所以由所得的车次很容易确定发车时间间隔。 ⑶ 单程发车时刻表(数据量太大, 故略)
⑷ 总车辆数n = 62 , 其中场A 存车57 辆, 场B 存车5 辆。
统计指标:
⑴ 平均满载率 上行方向 β01 = 76. 4 % 下行方向 β02 = 7019 % ⑵ 平均候车时间上行方向T 1 = 4. 24 分下行方向T 2 = 3148 分
3) 调度方案
我们由不同的理解得到两种调度方案, 其共同点是都必须形成完整的运营过程, 使车流不 间断。
3. 1 静态调度方案:
认为在该路线上运行的总车数固定不变, 形成序贯流动的车流, 依照“按流开车”和“先进 先出”的原则, 按发车时刻表发车。
所需总车辆数为62 , 其中从A 13 站的车场A 始发的车数为57 , 从A 0 站的车场B 始发的 车数为5 。
3. 2 动态调度方案:
考虑高峰期与低谷期实际需要的车辆数目不同, 为了满足高峰期而求得的车辆数目必然 大与其他时间需要的车辆数, 即62 辆车只在高峰期得到充分利用, 造成资源浪费。我们认为公 交公司可进行车辆动态调度, 让一些车辆可以在特殊原因下进行修理调整, 并节约运营成本。 由此我们在保证车流不间断的条件下, 计算得出各个时段内实际所需的最小车辆数。如表3 所
示: (同时给出A 、B 车场的存车状态, 可以自由支配的车辆数目)
表3 动态调度中各时段的车辆数
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需车数9 34 56 48 38 22 20 19 18
A 场状态51 28 2 0 0 11 12 11 9
B 场状态2 0 4 14 24 29 30 32 35
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 所需车数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 8 5 4
由上表我们得出:在总车辆数目可变动的情况下, 所需的最大车辆数为7 :008 :00 间的56 辆, 在非高峰期时所需车辆数目都较小, A 车场和B 车场都有较多车辆库存着, 可以根据实际 情况挪作它用。公交公司只需按表中所给的每个时段的所需车辆数进行调度, 按发车时刻表发
62 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
车即可。
㈡ 单车场模型
1) 模型的建立
根据问题分析, 公交营运方式按单车场组织后我们建立如下带软时间窗口的单车型运输 问题多目标优化模型:
目标函数: Ⅰ y 1 = min { n}
Ⅱ y 2 = min ΣN i
Ⅲ y 3 = min ( Σj
Σ
Σk r
P( Ti ) ) / ( R ·K ·M)
约束条件: ①平均满载率限制50 % ≤β ≤120 %
②发车间隔时间限制t i ≤5 + 5 k ; k =
0 i 为早高峰期时;
1 i 为非早高峰期时。
③ t i ∈{ 1 , 2 , 3 ⋯}
1. 1 目标函数说明: 目标函数Ⅰ使总车辆数目最小, 即使公司的投资成本达到最小。 目标函数Ⅱ使总车次数最小, 即使公司的运营成本达到最小。
目标函数Ⅲ是使所有顾客的平均不方便程度达到最小。
112 约束条件说明: 条件③主要是考虑到可操作性, 发车间隔划分到秒一级, 公交司机是没 法把握的, 故最小只能划分到分一级, 那么发车间隔就应是1 分的整数 倍
2) 模型的求解
本模型是多目标、多约束的优化模型, 很难求出全局最优解, 所以我们先将多目标规化简, 再仿真模拟运营过程求解。求解思路如下:
给出初始发车时刻表
客运数据
客流分布(平均分布)
v
v
v
模拟
运营
数据
v 统计指标v 结论w 人工分析
2. 1 模型化简
化简多目标问题, 我们可以有三个出发点: ①分析各目标之间相关联的数学关系, 减少目 标函数数目或约束条件数目。②依限定条件, 针对具体数据挖掘隐含信息以降低求解难度。③
分析各目标权重, 去掉影响很小的目标函数, 从而达到简化目的。
分析目标Ⅱ与Ⅲ存在数学关联, 发现总车次越多, 乘客不方便程度越小。因此y 2 与y 3 不 能同时取最小值。我们认为Ⅲ为主要目标, 故主要考虑目标函数Ⅲ。从具体数据可知, 在上行 方向7 :00 ～ 8 :00 , A 13 站上车人数达3626 人, 平均每分钟到达60 人, A 12 站上车634 人而下
车仅205 人, 为客流量最大的时段, 发车间隔时间至少需要2 分钟。由平均速度20 公里/ 小时 及环行距离, 可得到此时至少需45 辆车。
由以上分析将原模型简化为:
目标函数: y 1 = min ( Σj
Σ
Σk r
P( Ti ) ) / ( R ·K ·M)
y 2 = min M
约束条件: 同上
建模专辑 公交车调度问题的研究63
2. 2 运营过程模拟
⑴ 初始时刻表的产生方法
原则上初始时刻表可以随机产生, 然后模拟判断搜索出较优解, 但这样搜索量太大, 且很 难保证有一个收敛结果。因此我们采用人机交互的方式, 首先分析数据得出比较合理的发车时
间间隔的近似值, 产生初始时刻表(见表4) ,然后在其附近搜索局部最优解。 表4 初始发车时刻表
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
t i (分) 10 3 2 3 8 8 8 8 8
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 t i (分) 8 8 3 2 3 10 10 10 10
⑵ 模拟运营过程, 统计各指标, 搜索最优解
由于模拟运营过程与双车场模型大同小异, 故我们在此不再详述。
2. 3 结果及统计分析
对仿真产生的多组发车时刻表进行模拟获得最小的Y = 516 分, 我们把这一组解做为我 们的局部最优解, 其结果(其中统计指标用来描述我们以怎样的程度照顾双方利益) 如下: ⑴ 总车数
理想的理解平均速度可得所需总车数为45 辆, 加2 辆应急, 为47 辆;
考虑高峰期车速小于20km / h , 高峰期人流量大是造成高峰期速度稍低于20km / h 的主 因, 那么通过人流量数据和20km / h 就可大致推算7 :00 - 8 :00 速度约为18km / h 。这样高峰期 的最小总车数45 辆, 应修正为50 辆, 加2 辆应急最终为52 辆。
⑵ 全天总车次M = 253 ×2 = 506 次
⑶ 发车时刻表见表5 (用各时段发车间隔时间简述)
表5 单车场模型最优发车时刻表
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
t i (分) 10 2 2 2 4 6 6 6 8
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23 t i (分) 8 6 3 2 3 7 10 10 10
注:5 :00 - 6 :00 只是一种统计划分, 首发车可以在5 :00 之前, 也可在5 :00 之后。当然当不 知道其它原则时可以假设首发车为5 :00 发。对单车场下行线始发为5 :45 与数据相吻 合。5 :00 - 6 :00 上行线共855 人上车; 下行线共50 人。其可能原因之一就是上行在5 : 00 - 6 :00 都有车可统计; 而下行只在5 :45 - 6 :00 中可实际统计到车。 统计指标: ⑴乘客平均候车时间 y 3 = 516 分
⑵平均满载率 β0 = 66. 4 %
结论分析:由上面两个图表可见我们的调度方案基本上能满足乘客候车时间的限制, 高峰期乘 客在5 分钟内等到车的概率为9219 % ,非高峰期乘客在10 分钟内等到车的概率为 8917 %。
调度方案: (见表6)
64 工 程 数 学 学 报 第19 卷
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
表6 单车场动态调度方案
时段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需车辆数10 46 52 46 24 16 16 16 14
时段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
所需车辆数14 16 30 46 30 14 10 10 8
4 模型的进一步讨论
1) 关于采集运营数据的讨论
由于我们假设在一个时段内乘客到站服从均匀分布, 而实际中乘客到站时间不可能都服 从均匀分布。特别是在高峰期的情况下, 乘客到站时间的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法:
⑴ 采取不等的统计人数的间隔时间
在高峰期的情况下, 为削弱乘客到站时间不均匀分布带来的影响, 可适当减小统计的间隔 时间但统计时间加密应有一定限度。对客流量很小的时段, 我们可适当增大统计的间隔时间。 ⑵ 增加能反应有关滞留人数的统计数据。
⑶ 按相等到站人数来区分时间段的统计
方法是统计达到一定到站人数时的时间点, 其优点是能较为准确地反映客流量的变化情 况, 有利于按其分布的疏密进行车辆调度, 以更好的满足乘客的需要。
2) 单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本; 双车场调度方案的运营成 本小, 更好的兼顾到乘客与公司双方的利益。我们建议, 在有双车场的条件下选取双车场调度 方案更好。当需进行路线规划, 需要选取单车场或双车场时, 建议根据实际所需成本来选取方 案。
5
（p66）
1 问题重述(略)
2 基本假设
1) 公交车在该线路行进中以20 公里/ 小时的速度匀速运行, 即不考虑启动和停车, 每 一站停车延迟及其他因素的影响
2) 公交车按发车时刻表顺次发车, 准时到达每个站点
3) 乘客候车时间一般不超过10 分钟, 早高峰时一般不超过5 分钟
4) 满载率不要超过120 % , 一般也不应低于50 %
3 符号说明
P i : i 时段内的配车数(时段配车数) (车次) ; ρi : i 时段内的期望满载率;
H i : i 时段内的小时最高断面的通过量(人) ; Ni : i 时段内的期望占用量(人) ;
C : 车容量( C = 车型定员+ 最大允许站人数) (人) ; L : 路线长度(km) ;
1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
Q i : i 时段内的乘客周转量(人km) ; δi : i 时段内乘客的满意率;
δ -
: 乘客的平均满意率; Wi : i 时段内乘客的平均等待时间
η -
: 公交公司的平均满意率;
4 问题(1) 模型的分析、建立及求解
下面我们逐步以两种不同的方法对公交调度方案进
问题(2) 基本假设
1 模型假设
根据题目的要求, 并为了到达将实际情况进行抽象的目的, 在我们的模型中有如下假设:
1) 汽车的速度恒定为20km/ h ,且无特殊事件发生(如抛锚) 。
2) 以分钟作为最小的时间单位, 这对安排时刻表是合理的。
3) 汽车在站台的停留时间仅由该站的全天人流量决定, 而与时间无关, 上限为2 分钟、 下限为0 分钟。
4) 在车站等待的人绝大多数不会离去。
5) 汽车严格按照时刻表运行, 在基本模型中排除汽车中途调头的情况(如机动车) 。
6) 在基本模型中, 无论车程多少, 票价单一; 且绝大多数乘客自觉付费。
4 建模前的准备
1) 对问题的初步分析
我们考虑三组相关的因素:公共汽车, 汽车站与乘客对模型的影响。
i) 与公共汽车有关的因素:离开公共汽车总站的时间, 到达每一站的时间, 在每一站下 车的乘客数, 在每一站的停留时间, 载客总数, 行进速度等。
ii) 与车站有关的因素:线路上汽车的位置, 车站间距, 乘客到来的函数表示, 等车的乘客 数, 上一辆车离开车站过去的时间等。
iii) 与乘客有关的因素:到达某一车站的时间, 乘车距离(站数) ,侯车时间等。
2) 曲线的拟合
分析样本数据, 可知对于某车站全天的上(下) 车乘客数N ( t) 是时间t 的递增函数, N ( t) = N ( t - 1) + qt , 其中q t 为第t 时间内此站的上(下) 车人数, 我们可以由此来拟合其分
布函数。由样本数据知每一车站每天有两次波峰, 故根据最小二乘法将分布函数拟合为关于 t 的五次多项式。
5