6 第19卷 2.2运营过程模拟 (1)初始时刻表的产生方法 原则上初始时刻表可以随机产生,然后模拟判断搜索出较优解,但这样搜索量太大,且很 难保证有一个收敛结果。因此我们采用人机交互的方式,首先分析数据得出比较合理的发车时 间间隔的近似值,产生初始时刻表(见表4),然后在其附近搜索局部最优解。 表4初始发车时刻表 时段 5-66-77-88-99-1010-1111-1212-1313-14 t2(分) 2 8 时段14-1515-1616-1717-1818~19|19~2020~2121-2222-23 4(分)8 3 (2)模拟运营过程,统计各指标,搜索最优解 由于模拟运营过程与双车场模型大同小异,故我们在此不再详述。 2.3结果及统计分析 对仿真产生的多组发车时刻表进行模拟获得最小的Y=5.6分,我们把这一组解做为我 们的局部最优解,其结果(其中统计指标用来描述我们以怎样的程度照顾双方利益)如下: (1)总车数 理想的理解平均速度可得所需总车数为45辆,加2辆应急,为47辆; 考虑高峰期车速小于20km/h,高峰期人流量大是造成高峰期速度稍低于20km/h的主 因,那么通过人流量数据和20km/h就可大致推算7:00-8:00速度约为18km/h。这样高峰期 的最小总车数45辆,应修正为50辆,加2辆应急最终为52辆。 (2)全天总车次M=253×2=506次 (3)发车时刻表见表5(用各时段发车间隔时间简述) 表5单车场模型最优发车时刻表 时段 5-66~77~88~99-1010-1111-1212-1313-14 t1(分)10 2 时段14-1515-1616-1717-1818-19|19-2020~2121 22~23 t1(分)8 63 注: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中可实际统计到车。 统计指标:(1)乘客平均候车时间y3=5.6分 (2)平均满载率 0=66.4% 结论分析:由上面两个图表可见我们的调度方案基本上能满足乘客候车时间的限制,高峰期乘 客在5分钟内等到车的概率为929%,非高峰期乘客在10分钟内等到车的概率为 89.7%。 调度方案:(见表6)
建模专辑 公交车调度问题的研究 表6单车场动态调度方案 时段 6-77-88-99-1010-1111-1212-1313-14 所需车辆数1046 16 14 时段14-1515-1616-1717-1818-1919-2020-2121-22|22-2 所需车辆数14 10 10 8 4模型的进一步讨论 1)关于采集运营数据的讨论 由于我们假设在一个时段内乘客到站服从均匀分布,而实际中乘客到站时间不可能都服 从均匀分布。特别是在高峰期的情况下,乘客到站时间的不均匀分布就会使模型结论误差较 大。我们建议以下几种改进采集方式的方法 (1)采取不等的统计人数的间隔时间 在高峰期的情况下,为削弱乘客到站时间不均匀分布带来的影响,可适当减小统计的间隔 时间但统计时间加密应有一定限度。对客流量很小的时段,我们可适当增大统计的间隔时间 (2)增加能反应有关滞留人数的统计数据。 (3)按相等到站人数来区分时间段的统计 方法是统计达到一定到站人数时的时间点,其优点是能较为准确地反映客流量的变化情 况,有利于按其分布的疏密进行车辆调度,以更好的满足乘客的需要。 2)单车场调度方案与双车场调度方案的选用 由结果分析可知单车场调度方案减少了公司的前期投资成本;双车场调度方案的运营成 本小,更好的兼顾到乘客与公司双方的利益。我们建议,在有双车场的条件下选取双车场调度 方案更好。当需进行路线规划,需要选取单车场或双车场时,建议根据实际所需成本来选取方 案 5模型的评价 本文的优点如下 1)模型的主体是采用时间步长法,模拟生成的发车时刻表的实际运行过程,准确性高 容量大,逻辑性严格,计算速度快,具有较强的说服力和适应能力。 2)定义了能定量衡量我们的调度方案对乘客和公交公司双方利益满足程度的统计指 标。 3)在求最少车辆数时,将两个车场看作两个发射源,通过对两个车场的存车状态的实 时模拟,形成不间断的运营过程,从而求得所需车辆数目。 本文的缺点是 1)对于运营数据的采集方式,只给出了一些原则和想法,没有经过仿真验证。 2)对于乘客到站的分布,直接假设为均匀分布,没有对其他分布的情况再作讨论
数学学报 第19卷 参考文献 [1]钱湔,运筹学[M]北京:科学出版社,2000 [2]肖雁,符卓,李育安,带软时间窗口的车辆路径问题及其应用前景探讨[刀中国运筹学会第六届学术交流会论文 集,下卷,634-638 Study on the Scheduling Problem DONG Qiang, LIU Chao-hui, MA Yi Instructor: WU Meng-da National University of Defence Technology, ChangSha 410073) bstract: As it's a vehicle-scheduling problem with soft time windows, we established two multiple objective programming mod els to satisfy different practical conditions: double- parking-lot model and single- parking-lot model. The main objective of the former ras to match the capacity of passengers holding with the real demand, while the objective of the latter was to minimize the average inconvenience of passengers and the cost of transit companies. Both of the two models considered for benefits of both passengers and companies. By using the method of step-by-step time, we simulated the practical procedure and drew two dispatching plans: static patching and dynamic dispatching Key words: scheduling: step-by-step time; dispatching plans
第19卷建模专辑 工程数学学报 Vol 19 Supp 2002年02月 JOURNAL OF ENGINEERING MATHEMATICS Feb.2002 文章编号:1005-3085(2002)05-006708 公交车调度的规划数学模型 薄立军,要尉鵬,王艳辉 指导老师:刘红卫宽两交 (西安电子科技大学,西安710071) 编者按:本文建立了两种优化模型来研究公交车调度问题。第一种模型中使用 Fisher聚类算法对客流分布进行了优化分 类,这使得客流时间段的划分更为合理。第二种模型基于随机服务系统,主要利用了GM/排队系统的平均队 长及平均等待时间等基本公式。因城市交通客流是随机的,利用排队理论来研究公交车调度问题更能刻划问题的 实质。但单交通线上的公交车具有串联服务的性质,这与GIM/系统不大符合。第二种模型有明显的不足 摘要:本文根据有序样本聚类的 Fisher算法,给出一种峰值曲线的优化方法通过该方法我们得出了上行客流峰值为5 个,其峰值区间为:5:006:00,6:009:00,9:0016:00,16:00-18:00,18:0023:00;下行客流峰值为5个,其峰值 区间为:5:00-7:00,7:009:00,9:00-16:00,16:0019:00,19:00-23:00。 然后,依据峰值区间建立确定发车间隔的算法I模型和算法Ⅱ模型,对两种算法模型计算结果进行比较分析 得出结论:两个间隔高峰类时间段用算法I进行求解,其余3个类时间段用算法Ⅱ进行求解。在各个时间段结合 处用光滑法进行优化处理,并以处理后的数据为基础制定出两个起点站的发车时刻表,并求出全线共需要47辆 车,乘客对方案的满意程度为98.2%,公交公司的满意程度为76.23% 最后,运用随机服务系统的相关理论建立随机规划模型,给出概率灵敏度和误差分析,进而得出采集运营数据 的较好方案。 关键词:有序样本聚类;客流;峰值;车次;平滑法;随机服务 分类号:AMS(2000)9008 中图分类号:TB114.1 文献标识码:A 1问题重述(略) 2基本假设 1)公交车在该线路行进中以20公里小时的速度匀速运行,即不考虑启动和停车,每 一站停车延迟及其他因素的影响 2)公交车按发车时刻表顺次发车,准时到达每个站点 3)乘客候车时间一般不超过10分钟,早高峰时一般不超过5分钟 4)满载率不要超过120%,一般也不应低于50% 3符号说明 P:i时段内的配车数(时段配车数)(车次);p:i时段内的期望满载率; H:i时段内的小时最高断面的通过量(人);N2:i时段内的期望占用量(人); C:车容量(C=车型定员+最大允许站人数)(人);L:路线长度(km);
工程数学学报 第19卷 Q1:i时段内的乘客周转量(人km); ;:i时段内乘客的满意率; 8:乘客的平均满意率; W:i时段内乘客的平均等待时间 7:公交公司的平均满意率; 4问题(1)模型的分析、建立及求解 下面我们逐步以两种不同的方法对公交调度方案进行讨论,第一种方法对公交调度峰值 曲线进行优化,第二种方法对公交调度发车间隔进行确定,进而制定出公交调度方案。最后, 依据制定方案过程中的相关参数的随机特性,抽象出明确完整的随机规划模型。 方法I优化公交调度峰值曲线 公交调度人员在制定线路配车计划时,最为重要的依据是线路客流的每日时段分布曲 线。调度人员进行这样的峰值划分主要依据以下两个原因:①对于客流大小相似而且相邻的 时段配置相同的运力;②划分为若干峰值区间,便于进行驾乘人员的班次安排。(明确一点: 公交调度峰值曲线中峰值代表一个区间,而不是一个点)。 公交调度峰值曲线的优化过程实际上是有序样品的聚类问题。 所谓有序样品是指,样品按照一定的要求排成序,分类时不能打破这种次序。设x1, xn表示一组有序的样品,则每一类必须呈{x,x1+1,…,x(i<j形态。n个有序样 分成k类的一切可能的分法有C-种,这个数比c要小得多。因此在某种损失函数下,有 可能求得最优解。费歇( Fisher)发展了一个有序样品的聚类算法,它可保证求得最优解。 下面给出费歇( Fisher)聚类算法 ①基础算法 首先定义D(i,j表示类{i,+1,…,的直径。类的直径D(i,j)这里采用该类的值与 类均值差的平方和来表示直径的大小。 用bnk表示n个样本分成k类的一种分法,即 bn,k:li1=1,i1+1,…,i2-1,{i2,i2+1,…,i3-1},…,|i,i+1,…,n 其中,i1=1<i2…<i<n 定义bn,k分类下的损失函数为: L(bn,)=∑D(i,i+1-1) 其中,i+1=n 损失函数值越小,分类越合理。设b.为使式(1)达到极小的解 费歇( Fisher)的计算方法使用下面两个递推公式 L(b2)=mD(1,-1)+D(j,n)1 L(b:)=mL(b11)+D(,n) 在k=2时,bn2:11,2,…,-1},,+1,…,n,2≤j≤n。 由式(1)得L(bn,2)=D(1,j-1)+D(j,n) 最优的分法是上式对j(2≤j≤n)求极小,得到式(2)。为证式(3),只需注意到n个有序 样品分成k类,这等价于将它们先分成两部分:1,2,…,j-1},,j+1,…,n 其中1,2,…,j-1将分成k-1类,而j,j+1,…,n}独成一类,显然k≤j≤n,于得 到式(3)