第19卷建模专辑 工程数学学报 Vol 19 Supp. 2002年02月 JOURNAL OF ENGINEERING MATHEMATICS Feb.2002 文章编号:1005-3085(2002)05-005908 公交车调度问题的研究 董强,刘超慧,马熠 指导教师:吴孟达 (国防科技大学,长沙410073) 编者按:该论文建立了两个多目标规划模型,尤其是选择运力与运量的平衡作为目标函数有新意。寻找最小车辆数的方 法正确。单车场模型作为双车场模型的补充,虽然简单,也有自身特点。运行发车时刻表切实可行,接近最优解 摘要:本题为带软时间窗的单线路单车型的公交调度问题,针对其多目标、多变量的动态特点,我们为满足不同的实际需 求建立两个多目标规划模型:双车场模型和单车杨模型。双车场模型的主要目标是使运客能力与运输需求(实际客 运量)达到最优匹配,单车场模型的主要目标是使乘客的平均不方便程度和公交公司的成本达最小,其目的都是为 了兼顾乘客与公司双方的利益。两个模型的主体都是采用时间步长法,模拟实际的运营过程,从面得出符合实际要 求的调度方案:静态调度和动态调度方案。 关键词:公交车调度;软时间窗;满载率;时间步长法 分类号:AMS(2000)90c08 中图分类号:TB114.1 文献标识码:A 1问题分析 我们分析该问题为一带软时间窗的单车型运输问题。由已知条件无法确定是单车场问题 还是多车场问题,故我们分别建立两个模型:双车场模型和单车场模型。其中,双车场模型认为 车站A13和车站A0分别有车场A和B存车,即均可作为始发站和终点站,上行和下行路线独 立运行;单车场模型认为A0车站有转运能力但没有存车能力,这样实际上可将单车场方式理 解为环线行驶。 2模型假设(略) 3模型的建立与求解 )双车场模型 1)模块一:发车时刻表的确定 依据前面的分析,兼顾乘客与公交公司双方的利益,分别对单程的上行路线和下行路线建 立如下的多目标规划模型 标函数:I供求的最优匹配 mn2(Q1×A1-V)2 Ⅱ各时段的发车车次均最小minN2 约束条件:①各时段的平均满载率限制0.5≤月≤1.2 ②供求匹配比限制 a≤k
第19卷 1.1符号说明: N第i时段发车次数 A第i时段的平均满载率 月=R:/(c×N)R4为第i时段的总上车人数,c=100人/车次 供求匹配比a=(∑v)∑Q) k控制参数 Q;第i时段运客能力(人×公里) Q=第i时段发车次数N2×每辆车标准载客量c×单程(上行或下行)总运行距离 L。其中,上行时,L=14.58公里;下行时,L=14.61公里 V;第i时段的需要运客量(人×公里 V=∑(xry)L1j∈(13,12…,1,0),上行方向∈(0,2,3,…13),下行方 向 其中,x为第i时段内A站的上车人数;y为第i时段内A站的下车人数 L为A站距该单程方向上终点站的距离。 1.2目标函数说明 目标函数I使第i时段的运客能力Q与运输需求(实际客运量)vi达到最优匹配,B反 映满载率高低的影响。 目标函数Ⅱ使各时段所需的最大发车次,在满足约束条件下尽可能少,以使总车辆数较 少 1.3约束条件说明 条件①是限制满载率满足运营调度要求,是考虑了乘客的利益。 条件②是限制供求匹配比a小于常数k。我们根据参数k的变动量分别进行模拟,从而筛 选最恰当的k值。 补充约束条件:为使始发站车场的每天起始时刻的车辆数保持不变,需使总发车次数与总收车 次数相等,即必须使单程车次总数达到匹配(N1=N2),而N1不能减少(受满 载率限制),因此我们在求解下行方向的N时增加约束∑N2;=N1.在增添 约束条件∑N2=N1之后,用二次规划求得各时段发车次数N1和N2;。 2)模块二:运营过程的模拟 在这部分,我们采用时间步长法,根据假设一个时段内发车间隔时间t1相等,则t1可由N 确定,从而得到发车时刻表。按此发车时刻表模拟实际运行过程,目标是确定满足时刻表的最 小车辆数n,统计各项运营指标,搜索最优调度方案解 2.1模拟子程序一:确定最小车辆数目n 根据“按流发车”和“先进先出”的原则,对起点站,在发车时刻应至少有一辆车可以发出 (处于等待发车状态)。若有多辆车,则先进站者先发车,其余车辆“排队”等候;若无车可发,则 出现“间断”。完整的运营过程应保证车辆严格按时刻表发车,不发生间断。 设A13站和A0站分别有车场A和B,从车场中不断有车发出,同时接受车进场,则车场 中的车的数目是随时间变化的状态量。用Na和Nb来描述车场A和车场B中要满足车流不间 断所需的最小数目,分别搜索其在运行过程中的最大值,则所需最小车量数目n=Na+Nb 2.2模拟子程序二:统计各项运营指标
建模专辑 公交车调度问题的研究 确定各项运营指标,采用模拟统计的计算方法,对不同的运营指标进行定量计算,主要功 能是通过定量分析运营指标来检验方案的可行性,以确定方案调整。 由于车次与发车时刻一一对应,而车辆的队列顺序是不发生改变,因而对所需车辆进行统 一编号,则对每一车次,与其对应的车辆编号是确定的,故我们直接对第k次车进行考察。 我们统计的指标及其定义如下: 平均满载率上行方向1=(2∑(k,1)/(N1·J1) 下行方向=(2∑R(k,j2)/(N2·2) 满载率分布可以由B(k,j)确定。 平均候车时间上行方向T1=(∑∑T(k,1)/(N1·J) 下行方向T2=(2∑T(k,2)/(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,-1)+D(k,j)+C(k 1,j)-C(k,j) T(k,)为第k次车离开第j站时站台上滞留者的滞留时间;T(k,j)=C(k,j)·t B(k,j)为第k次车离开第j站时的满载率,B(k,j)=B(k,)100 N1,N2为一天单程所发的车次总数;1,J2为单程站台总数 2.3模拟结果及统计指标分析 我们选取参数k=0.8,0.85,0,9进行模拟运行,所得结论如表10(表中只给出上行方向 表1模拟上行方向所得营运指标值 参数k平均满载率A0平均候车时间T所需总车辆n总发车次数N1 0.8 68.7% 3.88 270 0.85 72.8% 76,4% 4.24 62 243 80.4% 7.23 综合考虑以上参数,当k=0.9时,各项指标比较适当,平均满载率较高,平均候车时间较 短,所需车辆与总发车次数适中,所以我们选取k=0.9。 下面我们给出k=0.9时的具体模拟结果及统计指标。 结果 (1)各时段内单程发车次数(见表2) 总车次N1=N2=243
工程数学学报 第19卷 表2k=0.9时各时段中的发车次数 时段5-66-77-88-99-1010-11|11-12|12-1313-14 13 行 9919 85 102 时段14-15115-1616-1717-1818-1919-2020-2121-22122-23 24 5 (2)各时段单程发车时间间隔 由于一个时段内的发车间隔已假设为等距,所以由所得的车次很容易确定发车时间间隔。 (3)单程发车时刻表(数据量太大,故略) (4)总车辆数n=62,其中场A存车57辆,场B存车5辆。 统计指标: (1)平均满载率上行方向1=76.4%下行方向a2 =70,9% (2)平均候车时间上行方向T1=4.24分下行方向 48分 3)调度方案 我们由不同的理解得到两种调度方案,其共同点是都必须形成完整的运营过程,使车流不 间断。 3.1静态调度方案 认为在该路线上运行的总车数固定不变,形成序贯流动的车流,依照“按流开车”和“先进 先出”的原则,按发车时刻表发车 所需总车辆数为62,其中从A13站的车场A始发的车数为57,从A0站的车场B始发的 车数为5。 3.2动态调度方案 考虑高峰期与低谷期实际需要的车辆数目不同,为了满足高峰期而求得的车辆数目必然 大与其他时间需要的车辆数,即62辆车只在高峰期得到充分利用,造成资源浪费。我们认为公 交公司可进行车辆动态调度,让一些车辆可以在特殊原因下进行修理调整,并节约运营成本。 由此我们在保证车流不间断的条件下,计算得出各个时段内实际所需的最小车辆数。如表3所 示:(同时给出A、B车场的存车状态,可以自由支配的车辆数目) 表3动态调度中各时段的车辆数 时段 5~66 7-88-99-1010-1111-1212-1313-14 所需车数 20 1918 A场状态 B场状态20414 03 段14=1515-1616-1717-1818-1919-2020-2121-22122-23 所需车数17 10 A场状态910 B场状态 由上表我们得出:在总车辆数目可变动的情况下,所需的最大车辆数为7:008:00间的56 辆,在非高峰期时所需车辆数目都较小,A车场和B车场都有较多车辆库存着,可以根据实际 情况挪作它用。公交公司只需按表中所给的每个时段的所需车辆数进行调度,按发车时刻表发
建模专辑 公交车调度问题的研究 车即可。 (单车场模型 1)模型的建立 根据问题分析,公交营运方式按单车场组织后我们建立如下带软时间窗口的单车型运输 问题多目标优化模型: 目标函数:Iy1=minn Ⅱy2=min∑N y3=mn(∑∑∑P(T)/(R,K,M) 约束条件:①平均满载率限制50%≤B≤120% 0i为早高峰期时 ②发车间隔时间限制t1≤5+5k; k= 1i为非早高峰期时。 ③t;∈|1,2,3…} 1.1目标函数说明:目标函数I使总车辆数目最小,即使公司的投资成本达到最小。 0目标函数Ⅱ使总车次数最小,即使公司的运营成本达到最小 目标函数Ⅲ是使所有顾客的平均不方便程度达到最小。 1.2约束条件说明:条件③主要是考虑到可操作性,发车间隔划分到秒一级,公交司机是没 法把握的,故最小只能划分到分一级,那么发车间隔就应是1分的整数 倍 2)模型的求解 本模型是多目标、多约束的优化模型,很难求出全局最优解,所以我们先将多目标规化简, 再仿真模拟运营过程求解。求解思路如下 给出初始发车时刻表 模拟 客运数据 营一计指标→固论←仄工分析 客流分布(平均分布】一数据 2.1模型化简 化简多目标问题,我们可以有三个出发点:①分析各目标之间相关联的数学关系,减少目 标函数数目或约束条件数目。②依限定条件,针对具体数据挖掘隐含信息以降低求解难度。③ 分析各目标权重,去掉影响很小的目标函数,从而达到简化目的。 分析目标Ⅱ与Ⅲ存在数学关联,发现总车次越多,乘客不方便程度越小。因此y2与y3不 能同时取最小值。我们认为Ⅲ为主要目标,故主要考虑目标函数Ⅲ。从具体数据可知,在上行 方向7:00~8:00,A13站上车人数达3626人,平均每分钟到达60人,A12站上车634人而下 车仅205人,为客流量最大的时段,发车间隔时间至少需要2分钟。由平均速度20公里/小时 及环行距离,可得到此时至少需45辆车。 由以上分析将原模型简化为 目标函数:y1=min(∑∑∑P(T)/(R·K·M) y2= min M 约束条件:同上