公交车调度问题的研究

第 19卷 建模专辑 2002年 02月 工 程 数 学 学 报 JOuRNAL oF ENGINEERING MATHEMATICS VoI 19 Supp Peb 2002 文章编号 ：1005—3085(2002)05—0059—08 公交车调度问的研究 董 强 ． 刘超慧． 马 熠 指导教师 ： 吴孟达 (国防科技大学 ，长沙 410073) 编者按 ： 谈建立了两个多目标规划摸型 ，尤其是选择运力与运量的平衡作为 目标 函数有新意。寻找最小车辆教的方 法正确。单车场模型作为双车场模型的补充 ，虽然简单 ，也有 自身特点。运行发车时刻表切实可行 ．接近最忧解 摘 要 ：本增为带鞋 时间窗的单线路单车型 的公交调度问增，针对其多 目标 、多变量的动态特点 我们为满足不辫的宴际并 求建立两个 多目标规划模型 ：双车场摸型和单车场模基。双车场模型的主要 目标是使运窨能力与运输需求(宴际客 运量)选到最优匹配 ，单车场模型的主要 目标是使乘客的平均不方便程度和公变公司的成本达最小 其目的都是为 了兼顾乘客与公司双方的利益。两个摸型的主体都是采用时阃步长法，模拟实际的运营过程 ，从而得出符合实际要 求的调壤 ：静态调度和动态调度方案。 *■词：公变车调度 {软时间窗 ；满载率 j时间步长法 分娄号 ：AMS(2000)90C08 中田劳娄号 翻 ¨ 立m擦识玛：A 1 问题分析 我们分析该问题为一带软时问窗的单车型运输问题。由已知条件无法确定是单车场问题 还是多车场问题 ，故我们分别建立两个模型：双车场模型和单车场模型。其中．双车场模型认为 车站 A13和车站 A0分别有车场 A和B存车 ，即均可作为始发站和终点站，上行和下行路线独 立运行；单车场模型认为 A0车站有转运能力但没有存车能力 ，这样实际上可将单车场方式理 解为环线行驶。 2 模型假设(略) 3 模型的建立与求解 ㈠ 双车场模型 1) 模块一：发车时刻表的确定 依据前面的分析 ，兼顾乘客与公交公司双方的利益．分别对单程 的上行路线和下行路线建 立如下的多 目标规划模型 ： 目标 函数 ：I 供求的最优匹配 min (口 × 一 ) Ⅱ 各时段的发车车次均最小 minf N，i 约束条件 ：① 各时段的平均满载率限制 0．5≤ 晟≤ 1．2 ② 供求匹配比限制 a≤ k 维普资讯 http://www.cqvip.com 60 T 程 数 学 学 报 第 19卷 1．1 符号说 明 ： N 第 时段发车次数 且 第 i时段 的平均满载率 =R ／(c×N ) R 为第 时段的总上车人数 ． c=100人 ／车次 供求匹配比 n=(∑V )／(∑Q ) k 控制参数 Q 第 时段运客能力(人 ×公里) Q =第 时段发车次数 N ×每辆车载客量 c×单程(上行或下行)总运行距离 L。其中，上行时 ，L = lg．58公里 ；下行时 ，L = 14 61公里 第 i时段的需要运客量(人 ×公里) = ( 一 )LJ ∈ (13，12⋯，1．0)，上行方向； ∈ (0，2．3，⋯13)，下行方 J 向。 其中．刁 为第 f时段 内A 站的上车人数 ； 为第 i时段 内Aj站的下车人数 L，为A，站距该单程方 向上终点站的距离。 1．2 目标 函数说明 ： 目标函数 I使第 时段的运客能力 Qz与运输需求(实际客运量)Ⅵ 达到最优匹配， 反 映满载率高低的影响。 目标函数 Ⅱ使各时段所需的最大发车次 ，在满足约束条件下尽可能少 ．以使总车辆数较 少 。 1．3 约束条件说明 ： 条件 ① 是限制满载率满足运营调度要求 ，是考虑了乘客的利益。 条件 ② 是限制供求 匹配比 小于常数k。我们根据参数 k的变动量分别进行模拟，从而筛 选最恰当的 k值 。 补充约束条件 ：为使始发站车场的每天起始时刻的车辆数保持不变 ，需使总发车次数与总收车 次数相等，即必须使单程车次总数达到匹配(N1=N2)，而 N1不能减少(受满 载率限制)，因此我们在求解下行方向的N 时增加约束 ：N2 =N1 在增添 约束条件∑ N2 =N1之后，用二次规划求得各时段发车次数 N1 和N2 。 2】 模块 二 ：运营过 程 的模拟 在这部分，我们采用时间步长法 根据假设一个时段内发车间隔时间 t 相等 则 可由N 确定 ．从而得到发车时刻表。按此发车时刻表模拟实际运行过程 ，目标是确定满足时刻表的最 小车辆数 ．统计各项运营指标 搜索最优调度方案解。 2．1 模拟子程序一 ：确定最小车辆数 目 根据“按流发车 和“先进先出 的原则，对起点站．在发车时刻应至少有一辆车可以发 出 (处于等待发车状态)。若有多辆车．则先进站者先发车 其余车辆“排队 等候 ；若无车可发 ，则 出现“间断”。完整的运营过程应保证车辆严格按时刻表发车 ，不发生间断 。 设 A13站和 AO站分别有车场 A和B，从车场中不断有车发 出，同时接受车进场 ，则车场 中的车的数 目是随时间变化的状态量 。用 Na和Nb来描述车场A 和车场B中要满足车流不间 断所需的最小数 目，分别搜索其在运行过程中的最大值 ，则所需最小车量数 目 = Na+Nb。 2．2 模拟子 程序二 ：统计 各项运营指标 维普资讯 http://www.cqvip.com 建模专辑 公交车调度问题的研究 6l 确定各项运营指标 ，采用模拟统计的计算 ，对不同的运营指标进行定量计算 ，主 要功 能是通过定量分析运营指标来检验方案的可行性 ，以确定方案调整。 由于车次与发车时刻一一对应 ，而车辆的队列顺序是不发生改变，因而对所需车辆进行统 ～ 编号，则对每一车次 ，与其对应的车辆编号是确定的，故我们直接对第 次车进行考察。 我们统计的指标及其定义如下 ： 平均满载率 上行方向 岛 满载率分布 平均候 车时 间 (∑ ∑ ( ， 1)／(N1．J1) 下行方向口。 =(∑∑ ( 可以由 ( ， )确定。 上行方向 T1 下行方向 T2 符号说明： D( ，J)第 次车到第j站时上车与下车的人数之差；(已知) C( ，j)第 次车离开第j站时站台上的滞 留人数 ；c( ， )=C( 一1，J)+D( ，J)一 (120一 B( ，J一1) B( ， )第 次车离开第J站时车上的人数；B( ， )=B( ， 一1)+D( ，j)+c( 一 1，j)一 C( ，j) T(矗， )为第 愚次车离开第 站时站台上滞 留者的滞留时间；丁(愚， )= c；N． IlI 3=rain(∑ ∑ ∑P(L))／(月·K-⋯ 约束条件 ：① 平均满载率限制 50％ ≤ 口≤ 120％ ②发车间隔时间限制 ≤s+s ； ={： 睾 嚣 。 ③ ∈ f1，2，3⋯ f 1．1目标函数说 明： 目标函数 I使总车辆数 目最小，即使公司的投资成本达到最小。 目标函数 叮 使总车次数最小，即使公司的运营成本达到最小。 目标函数 Ⅲ 是使所有顾客的平均不方便程度达到最小。 1．2约束条件说 明： 条件 ③ 主要是考虑到可操作性，发车间隔划分到秒一级 ，公交司机是投 法把握的，故最小只能划分到分一级，那么发车间隔就应是 1分的整数 倍 2) 模 型的 求解 本模型是多目标、多约束 的优化模型，很难求出全局最优解，所以我们先将多 目标规化简， 再仿真模拟运营过程求解。求解思路如下： 匿圈 一圈 +-区 化简多 目标问题 ，我们可以有三个出发点：① 分析各目标之间相关联的数学关系 ，减少 目 标函数数目或约束条件数目。② 依限定条件 ，针对具体数据挖掘隐含信息以降低求解难度 。③ 分析各 目标权重，去掉影响很小的目标函数，从而达到简化 目的。 分析 目标 Ⅱ与 Ⅲ存在数学关联，发现总车次越多，乘客不方便程度越小。因此 y2与 3不 能同时取最小值。我们认为 Ⅲ 为主要 目标，故主要考虑 目标函数 Ⅲ。从具体数据可知，在上行 方向7：∞ ～ 8：D0，Al3站上车人数达 3626人，平均每分钟到达 60人，A12站上车 634人而下 车仅 205人，为客流量最大的时段 ，发车间隔时间至少需要 2分钟。由平均速度 20公里 ／小时 及环行距离 ，可得到此时至少需 45辆车。 由以上分析将原模型简化为： 目标函数： y1=rain(∑ ∑ ∑P( ))／(R-K-M) ^ y2 = rain M 约束条件 ： 同上 圈 一 一 一 2 维普资讯 http://www.cqvip.com 工 程 数 学 学 报 第 19卷 2．2 运营过程模拟 (1) 初始时刻表的产生方法 原则上初始时刻表可以随机产生 ，然后模拟判断搜索出较优解 ，但这样搜索量太大 ，且很 难保证有一个收敛结果。因此我们采用人机交互的方式 ，首先分析数据得出比较合理的发车时 间问隔的近似值 ，产生初始时刻表(见表 4)，然后在其附近搜索局部最优解 。 表 4 初 始发 车 时刻 表 时段 5～ 6 6～ 7 7～ 8 8～ 9 9～ 10 10～ 11 1 L～ L2 12～ 13 13～ L4 ．(分) L0 3 2 3 8 8 8 8 8 时段 14～ 15 15～ 16 16～ I7 L7～ 18 18～ 19 19～ 20 20～ 2L 21～ 22 22～ 23 ，(分) 8 8 3 2 3 lo IO Io IO (2) 模拟运营过程 ，统计各指标，搜索最优解 由于模拟运营过程与双车场模型大同小异 ，故我们在此不再详述。 2．3 结果及 统计分 析 对仿真产生的多组发车时刻表进行模拟获得最小的 y = 5．6分 ，我们把这一组解做为我 们的局部最优解，其结果(其中统计指标用来描述我们以怎样的程度照顾双方利益 )如下 ： (1) 总车数 理想的理解平均速度可得所需总车数为 45辆，加 2辆应急，为 47辆； 考虑高峰期车速小于 20km／h，高峰期人流量大是造成高峰期速度稍低于 20km／h的主 因 ，那么通过人流量数据和 20km／h就可大致推算7：00—8：O0速度约为 18km／h。这样高峰期 的最小总车数 45辆 ，应修正为 50辆 ，加 2辆应急最终为 52辆。 (2) 全天总车次 M =253×2=506次 (3) 发车时刻表见表 5(用各时段发车间隔时间简述 ) 表 5 单车场模型最优发车时刻表 时段 5～ 6 6～ 7 7～ 8 8～ 9 9～ 10 1O～ 1 L 1 L～ L2 12～ 13 L3～ 14 ，(分) 10 2 2 2 4 6 6 6 8 时段 I4～ 15 15～ 16 16～ 17 17～ 18 18～ 19 19～ 20 20～ 21 21～ 22 22～ 23 f．(分) 8 6 3 2 3 7 10 10 10 注 ：5：O0—6：O0只是 一种 统计 划分 ，首 发车可 以在 5：O0之前 ，也 可在 5：O0之 后 。当然 当不 知道其它原则时可以假设首发车为 5：O0发。对单车场下行线始发为 5：45与数据相吻 合。5：O0～6：O0上行线共 855人上车 ；下行线共 50人 。其可能原因之一就是上行在 5： O0—6：O0都有车可统计 ；而下行只在 5：45—6：O0中可实际统计到车。 统计指标：(1)乘客平均候车时间 y3=5 6分 (2)平均满载率 = 66 4 结论分析：由上面两个图表可见我们的调度方案基本上能满足乘客候车时间的限制 ，高峰期乘 客在 5分钟内等到车的概率为 92．9％，非高峰期乘客在 10分钟内等到车的概率为 89．7％ 调度方案 ：(见表 6) 维普资讯 http://www.cqvip.com 建模专辑 公交车调度问题 的研究 表 6 单车场动态调度方案 时段 5～ 6 6～ 7 7～ 8 8～ 9 9～ l0 10～ 儿 1l～ 12 12～ l3 13～ 14 所需 车辆数 10 46 52 46 24 16 16 16 14 时 段 14～ 15 15～ 16 16～ 17 17～ l8 18～ 19 19～ 20 20～ 21 21～ 22 22～ 23 所需车辆数 14 16 30 46 30 14 10 10 8 4 模型的进一步讨论 1) 关于采 集运营数 据的讨论 由于我们假设在一个时段内乘客到站服从均匀分布，而实际 中乘客到站时间不可能都服 从均匀分布 。特别是在高峰期 的情况下 ，乘客到站时问的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法： (1) 采取不等的统计人数的间隔时问 在高峰期的情况下 ，为削弱乘客到站时问不均匀分布带来的影响，可适当减小统计的间隔 时问但统计时间加密应有一定限度 。对客流量很小的时段 ，我们可适当增大统计的间隔时间。 (2) 增加能反应有关滞留人数的统计数据。 (3) 按相等到站人数来区分时间段的统计 方法是统计达到一定到站人数时的时间点 ，其优点是能较为准确地反映客流量的变化情 况 ，有利于按其分布的疏密进行车辆调度 ，以更好的满足乘客的需要。 2) 单 车场 调度方 案与双 车场调度方 案的选 用 由结果分析可知单车场调度方案减少了公司的前期投资成本 ；双车场调度方案 的运营成 本小 ，更好的兼顾到乘客与公司双方的利益。我们建议 ，在有双车场的条件下选取双车场调度 方案更好 。当需进行路线规划 ，需要选取单车场或双车场时，建议根据实际所需成本来选取方 案 。 5 模型的评价 本文的优点如下： 1) 模型的主体是采用时阔步长法 ，模拟生成的发车时刻表的实 际运行过程 ，准确性高， 容量大 ，逻辑性严格 ，计算速度快 ，具有较强的说服力和适应能力。 2) 定义了能定量衡量我们的调度方案对乘客和公交公司双方 利益满足程度 的统计指 标 。 3) 在求最少车辆数时 ，将两个车场看作两个发射源 ，通过对两个 车场 的存车状态的实 时模拟 ，形成不问断的运营过程 ，从而求得所需车辆数 目。 本文的缺点是 ： 1) 对于运营数据 的采集方式 ，只给出了一些原则和想法 ，没有经过仿真验证。 2) 对于乘客到站的分布 ，直接假设为均匀分布 ，没有对其他分布的情况再作讨论。 维普资讯 http://www.cqvip.com 工 程 敫 学 学 报 第 19卷 参 考 文献 ： [1] 钱 漕 运筹学 [M]北京 ：科学出版杜 ，2000 [2] 肖 雁 ，符 卓 ．李育安 带软时间窗口的车辆路径问题及其应用前景探讨[J]．中国运筹学会第六届学术变流会论文 集 ．下卷，634—638 Study on the Scheduling Problem DONG Qiang． LIU Chao-hui． MA Yi In~tructor W U M eng—da (National University of Defence Technology，ChangSha 410073) Abstra~： As it’a a vehlclv~heduting proh Lem with soft time windows．we estah[ished two multiple oh／~dve programming mod els to sarisfv differ~ t practical conditions：do uh[vp~rking lot a~del and elng~一p~king —bt model The main ohjeetive the foy er w to match the capacity of passengem holding with the real dem~d．while the ohjectlve of the Latter wa5 tO mimmize the average inconvenience of immeng em and the co,~t of tr~ slt compa nies Both of the【wo mod els oo r~sldemd for benefits of b。 passe~gers atld companies BvtL~ing themethod n印 hy—steptime．weelmu[atedthe practieel procedure and drew PA,o dispatching plans：static dispatching and dyrmmie dispatching Key words：scheduling；step- -step time；dispatching plans 维普资讯 http://www.cqvip.com