（应用数学专业论文）公交调度排队系统研究.pdf

公交调度排队系统研究 摘要 本文结合大连市实际公交线网优化，研究了目前在交通管理规划中比较流行的调度问题。 我用排队论有关的知识，构建了调度数学模型。分别考查了线车、两线车的调度时刻表，以 及调度员的可选择决策：如发车时间决策、车型选择、各种可能起点、终点间的发车间隔的选 择。在给定的两线车调度时刻表中，讨论了寻求换乘乘客的最小换乘时间，把该问题描述成一 个线性极小化问题来求解。根据目前大部分调度系统是开环控制系统的实际隋况，在各车站徘 队人数经验分布基础上，结合交通实际数据对网络进行了研究，大部分结果与实际隋况比较吻 合。 简要介绍排队论_ 殷| 生理论及公交调度的基础上，重点对线、两线公交车的调度优化数 学模型进行了深入的探讨，并且密切结合大连市某线路的实际数据，通过分析研究，具体构建 了车辆调度的数学模型，并以此为依据，计算出调度时刻表g 给出两线车在缩短换乘时间的前 提下，对车辆调度时刻表进行修正，这些结果被某公交公司调度员在实际中所试用。 关键词：排队论、公交调度、正态分布、指数分布、换乘时间、j a c k s o n 网络 2 公交调度排队系统研究 a b s t r a c t i nt h i sp a p e rt h et h ep u b u cw a m p o r t a t i o nh a n d so v e rt h eli n en e tt h ee x c e l l e n tt u r n i n g r e l a t e dt od a l i a n ，s t u d y i n gt oa d j u s tap r o b l e mm o r ep o p u l a r l yi nt r a n s p o r t a t i o nn m n a g e p r o g r a m m i n gn o w iu s et ol i n eu pt h ek n o w l e d g eo fq u c u 衄t h e o r y ，s e t t i n gu pt oa d j u s t t h en u m b e ro fd e g r e e sl e a r nt h em o d e l i n v e s t i g a t e dag l i m m e ro fc a rr e s p e c t i v e l y ，t w o l i n ec a r sa d j u s tas c h e d u l e ，a n dt h ee l i g i b i l i t yt h a ta d j u s ta m e m b e rc h o o s e st h ed e c i s i o n ， s u c ha sh a i rc a rt i m ed e c i s i o n ，c a rt y p ec h o i c e ，e v e r yk i n do fp o s s i b l ep o i n to fd e p a r t u r e ， t e r m i n a lp o i n tac h o i c ef o ro fe v e r yc a rp a r t i t i o n a tg i v et os e t t l eo ft w ol i n ec a r s a d j u s tal e a s tf o ri nt h es c h e d u l e ，d i s c u s s i n gt ol o o kf o rt oc h a n g et ot h ep a s s e n g e r c h a n g e st ot i m e ，d e s c r i b i n gt h a tp r o b l e mal i n et u r n st h ep r o b l e mt ob e gt h es o l u t i o n s m a l l e s t a d j u s t i n ga c c o r d i n gt ot h ec u r r e n tb i gp a r tas y s t e mi se 1 2a c t u a lc i r c u m r t a n c e t oo p e n st h ew r e a t hc o n t r o ls y s t e m ，i ne a c hs t a t i o nli n i n gu pn u m b e re x p e r i e n c e d i s t r i b u t i n gt h ef o u n d a t i o n ，t h ea c t u a ld a t ai nt r a n s p o r t a t i o ni nc o m b i n a t i o np r o c e e d e d t h er e s e a r c ht ot h en e t w o r k ，b i ga n dp a r t so fr e s u l t sc o m p a r e sw i t ha c t u a lc i r c u m s t a n c e t of itt o g e t h e r t h i sp a p e ri n t r o d u c e st h eb a s e dq u e u e i n gt h e o r ya n d t h ep u b l i ct r a n s p o r t a t i o n d i s p a t c h i n g ，im a k ef o c a lp o i n t so nd i s c u s s i n gt h ed i s p a t c h i n gm o d e lo fo n eb u sl i n e o rt w ob u sl i n e s ，a n dg i v et h e mt h es p e c i f i cm o d e lb ya n a l y z i n gt h ep u b l i ct r a n s p o r t a t i o n d a t ao fd al i a nc i t y ，a n dd r a wu pad i s p a t c h i n gp r o g r a m m e ir e v i s e st h ed i s p a t c h i n g p r o g r a r m eb ys h o r t e n i n ge x c h a n g i n gt i m eo ft w ob u sl i n e s a n ds o m er e s u l t sh a sb e e n a p p l i e di nt h eu r b a nt r a n s p o r t a t i o np l a no fd al i a nt h ep a p e rh a ss o m ed i s a d v a n t a g e s t h e s em o d e l sa r er e q u i r e dt oi m p r o v e k e yw o r d s ：q u e u e i n gt h e r o y ，p u b li o d i s p a t c h i n g n o m ld i s t ri b u t i o n ， e x p o n e n tiai dis t rib u tio n e x c h a n g in gti m ，d c a k s o nn e t w o r k 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 保密囹，在二二年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“”) 作者签名：丑翌 指导导师签名： 墨叁羞 夕! 丝碰月上日 公交调度排队系统研究 l , m 1 1 m 日i j吾 本文研究了目前在交通管理规划中比较流行的调度问题，结合实际规划课题对该模型魁行 了应用与研究，发现大部分的结果与实际情况比较吻合，僵也有不尽如入意的地方。本文用排 队论的有关知识与交通实际数据相结合，构建了调度数学模型。主要考察了线车、两线车的 调度时刻表，通过调度时刻表调度员可以进行多种交通决策：包括发车时间决策、车型选择、 各种可能起点、终点间的发车间隔等的选择。在给定的两线车调度时刻表，寻求换乘乘客的最 小换乘时间。解决换乘问题的基本方法是把该问题描述成一个线性极小化问题来求解。在研究 过程中，采用了排队论以及概率论的相关知识，最后对网络问题我采用了开环排队网络的有关 知识，对网络进行研究。本文按如下方式组织： 第一部分，介绍公共交通的般背景，公交调度简介及排队论的相关知识。 第二部分，给出线公交车的调度时刻表。以典型的一个工作日两个运行方向各站上下车 的乘客数量统计为依据，建立优化调度模型，计算发车间隔，求出发车班次，合理安排出车时 间，对此简要分析居民满意程度和公交公司的经济效益。( 建立公交公司的经济效益和公益性结 合满意程度模型) 第三部分，给出有换乘站的两线公交车调度时刻表。在始发时间给定、线路确定的前提下， 根据换乘点的数目，研究如何发车，使两线车在需要抉乘的站点有合理的衔接，方便公交出行 的居民。 第四部分，我仅从理论上对类特殊的多线公交车组成的开环排队网络的调度进行分析， 解出一些排队指标结果。 4 公交调度排队系统研究 1 城市道路交通及排队论基本理论简介 1 1城市交通的背景 城市交通规划是与世界城市化进程的加快同步发展的。特别是第二次世界大战之后，随着 世界城市人口的急剧增长，交通问题同益突出，极大的推动了交通规划的发展。经过4 0 年的 研究和实践，在城市交通规划领域，积累了丰富的规划经验和无数的数据、资料，进行了大量 的规划实践。总括这些成就，可以归纳为以下几个方面：( 1 ) 形成了完整的交通调查技术和方 法。从1 9 5 3 年底特律的都市圈交通调查到1 9 6 8 年日本广岛交通调查，从1 9 8 2 年的中国天津市 交通调查到1 9 9 4 年如奎市交通调查，世界范围内有数百个城市进行了较大规模的交通调查。这 些调查，揭示了土地利用和交通生成的关系，揭示了人的交通行为的各方面特征，揭示了经济 发展和交通量的关系。( 2 ) 形成了公认的交通规划预测方法。随着数据和资料的积累、统计分 析，交通规划的四阶段模式为各国普遍接受。围绕交通的生成、分布、道路分配和交通方式划 分，产生了大量的模型，并归结为重力模型、熵模型、机会模型等主要分布模型，平衡模型和 动态平衡模型等分配模型，l o g i t 模型等方式选择模型，这些模型已经被世界各国普遍采用。 ( 3 ) 广泛采用最先进的技术。在大规模数据处理和城市规划资料的存储中，各国普遍采用计算 机手段，建立详细完备的城市规划数据库，对城市的人口、建筑、管网等进行科学管理。在道 路交通管理中，大量使用电子技术，对交通流进行监控疏导，发展智能交通系统。可以说，交 通的规划管理水平，同样反映国家的经济和科技水平。交通规划在城市建设中巨大的成就举世 公认，但是交通规划的方法却五花八门。方法的杂乱正是理论的匮乏，丰富的实践正孕育着超 越社会制度和经济发展水平的更深刻的交通规划理论。 我国2 0 年的改革开放，城市已近1 0 0 0 座，大中城市的交通问题日益严重。这种紧张状况 日趋发展，已成为大城市突出的社会问题之一，也是国民经济进一步发展的瓶颈问题。在学习 国外交通规划的理论和方怯中，也有几十座捌沛进行了较为系统的交通规划，但是，总的看我 国交通规划的研究水平还处于初级阶段。其主要问题是：缺乏全国性的交通调查标准和方法， 已有的数据和资料积累还很不够；交通调度的预测还十分粗糙，对国际流行的预测模型缺少深 入细致的研究；主要使用的还是国外交通调度软件：大部分中小城市没有进行系统的交通管理 7 公交调度排队系统研究 规划；交通管理规划的法规还远不能说完备。 1 2 城市公交调度简介 公交规划同时c l l 包括公交管理规划，它包括车辆的调度、车型的选用等等。对于城市公共 交通运输问题而言，公交企业的运营调度管理主要包括两个内容，一是运营调度计划的制定， 二是运营调度计划的执行和监控。调度是其关键的中间环节，车辆运营调度问题就是针对一项 可分解的运输任务，在一定的约束条件下，如何合理安排其组织部分( 操作) 所占用资源、运 作时间及先后顺序，以获得运输成本或时间最优化。在理论研究中，车辆调度问题可看作排序 问题或者资源分配问题。在实际工作中，车辆运营调度就是运输车辆作业计划和管理公交车辆。 运营调度通常包含两层含义：1 原始调度，车辆计划安排，称为静态调度；2 由于某种路况信息 或突发事件，使得原始调度必须做修改、更新，称为动态调度或者重调度。运营调度计划的制 定必须对公交线路客流进行预测，在实际的运营调度管理中，因为缺乏定量的分析预测手段， 公交运营调度这大多依靠经验和直觉来判断客流的变化。依靠经验和直觉进行客流预测是种 切实可行的方法，但其存在两个缺点：预测结果的准确性和稳定性较差。预测结果的准确与否， 同运营调度管理者的经验有关。纵然经验丰富的调度管理人员可以做出较为准确的客流估计， 但其不能保证其每次预测的稳定性。由此可见，进行公交客流预测需要有种定量化的、稳定 的、可靠度高的预测模型。大多数城市公交车调度，基本上沿用“定点发车、两头卡点 的手 工作业方式，由于信息不灵，调度失控，车辆经常出现“串车”、“大间隔”现象，导致全线运 行秩序混乱，严重影响了公共客运交通眼务质量和社会信誉。运营调度计划的制定即制定车辆 运行时刻表( 或发车时刻表) ，它是公共交通管理系统中一份重要的计划表，是调度员工作以及 车辆正常运行的最基本依据。因为其中的变量太多，所以编制车辆运行时刻表成为项冗长而 复杂的工作。在实践中，只有经验丰富，熟悉路线情况的老调度员才能编制出一套较实用的车 辆运行时刻表。而编制车辆运行时刻表关键问题是确定发车间隔，进而确定配车数。 大连公交公司正开展公交系统分析，降低| 茂本提高服务质量。其中个远景规划是利用基 于地理信息系统( g i s ) 实时数据指挥公交车辆，通过数据分析制定行之有效的调度方案，提 高车辆的利用率。地理信息系统( g i s ) 是随着计算机技术、制图技术和摄影测量学发展于2 0 公交调度排队系统研究 世纪6 0 年代才出现的一种相对现代的技术，它是在计算机软件、硬件支持下进行空间数据的输 入、存贮、检索、运算的综合分析和应用以及产品更新和输出的技术系统，由于g i s 允许不同 源数据的复合，如地图、遥感数据和表列数据等，它几乎渗透到了空间数据处理的各个方面， g i s 在公共交通管理中的应用- - r 概括为公交车辆实时调度、车辆运行时刻表等，它在公共交通 管理中的应用，代表了当代电于技术与公交结合的最新的发展趋势。g i s 有g p s 无法比拟的优 越性，g p s 仅有汽车的位置信息，无法表达汽车周围的地物，更谈不e 对运行汽车特征与车上 信息的查询，因此g i s 更适合在公交车辆上的使用。且大连公交公司现在春q 用g i s 已经实现了 对公交车辆运行中实时的定位速度监测每站上下乘客统计自动报站。并实现了计算机数据的通 讯和汇总等功能，并达到了国内先进水平。但是如何将采集的数据与公交调度指挥有机结合起 来，充分发挥大批实时数据的作用，利用计算机编制出合理车辆调度计划，是件十分迫切的 而重要的工作。本论文以该课题为背景，期望在基于g i s 数据采集的基础上，建立公交调度指 挥的数学模型，丰富和发展国内公交调度方法研究。但是使用g p s 、g i s 的成本太高，严重制 约了它们在公交系统中的使用，大连到目前为止仍然在一线公交车上试用g i s 。 1 3 国内外公交运营调度优化技术发展及应用 公交企业的运营调度管理同企业的经营模式相关。最近1 0 多年在北京、上海、杭州、长春、 西安等城市进行了公交运营调度系统和优化技术的研究。但研究的深度和广度都有限。少数几 个成功的例子还不具备普遍的意义，因为这些城市的公交企业调度优化系统的建设得到了国家 的大力资助和支持。 ( 1 )北京市 北京是我国系统地进行公交运营调度系统研究和建设的重要城市，该市引入了国外的些 先进技术取得了较好的效果。1 9 9 7 年国家科学技术委员会同欧盟在北京召开了第一次中欧智能 交通系统研讨会，时任国务委员、国家科学技术委员会主任宋健与欧盟伯克曼委员会联合签署 了中欧合作发展“i t s 应用与公交系统的示范工程”，并建议在北京公交总公司进行实施。北京 公共交通智能化管理第一期工程以建成北京公交调度指挥中心为目标，是将公交运营调度、车 辆维修、g p s 系统、i c 卡票证服务、计算机中心融为一体的智能化发通系统工程。北京公交i t s 9 公交调度排队系统研究 示范工程于1 9 9 9 年投入运行，首次投入运行的装有先进的车载卫星定位系统和无线电通谓装置 的车辆约为3 0 0 多辆。 ( 2 )上海市 1 9 9 9 年7 月，上海市第一条应用g p s 技术进行调度管理的公交线路9 8 l 路在浦东投入运 行。该系统选用了无线电数传通讯技术来传送定位信息。该系统的车载设备，用液晶显示和语 音提示相结合的方式提示驾驶员集中精力，安全驾驶车辆。该系统的监控软件提供了车辆i 行彼 速度预警，预测车辆到达站点时间，具有较为完善的电子地图显示功能。 ( 3 ) 杭州市 杭州市是我国第个将g p s 定位技棚到公交车辆的调度管理中的城市。系统具备一定 的车辆监控管理和查询功能。系统还具备在电子地图显示车辆运行状态的能力，并且有报警以 及运行车辆到达时刻站台显示等功能。但是系统只在杭州市部分公交线路上应用，而且系统传 递信息的方式是单向的，调度室可以获得驾驶员发来的信息，但不能对驾驶员的操作发布实时 的指令。 发达国家对于公交调度研究很重视，而且开始研究的时间较早，已经有大量的研究成果和 应用实例。发达国家在公交运营调度上的研究大致可以归纳为两个方面：( 1 ) 系统设计和集成； ( 2 ) 优化方法的研究。系统设计和集成相当于运营调度管理系统的“硬件”建设，各发达国家 在系统设计和集成方面的思路是通过大量的应用通讯、控制等领域的新技术手段，使得调度管 理者能获得充分得实时信息，保证管理者与被调度管理者之间的信息交流畅通。优化方法研究 是运营调度管理者做出正确的决策。美国是当今世界各国中在智能交通领域投入最大的国家， 它在智能公共交通系统方面的研究处于领先地位。下面主要以美国为例，介绍发达国家在公交 运营调度领域的进展。 美国智能公交系统主体是车队管理( f l e 田m a n g 唧) ，还有地理信息系统( g i s ) 、乘客 自动记数系统( a u t o m a t i cp a s s e n g e rc o u n t e r s ) 、路标技术( s i g n p o s ta n do d o m e t e r ) ，全球 定位系统( g p s ) 等。美国提出了公交管理软件的概念，公交管理软件的硎刘目的通过软件的设 计，最大程度的发挥上述各种技术的作用。通过公交管理软件系统可以实现多种公交方式和多 种公交运输功能的自动化、流水化和体化管理，例如：计算机辅助调度服务、监控管理控制 l o 公交调度排队系统研究 和数据采集等。借助于公交管理软件，管理部门可以对线路上发生的事件做出快速的反应。在 美国公交管理软件是综合交通管理系统的重要部分，其实实施的执行部门是各地的公交管理中 心。国内外较为流行用动态平衡原理建立各种模型选择道路，有线形模型，有非线形模型。求 解算法也千差万别，有基于姒t l a b 计算求解，有运用变分差分方程理论求解等，最终目标是使 出行费用趋于最小，道路选择趋于最短路，调度实施及时，车辆运行更合理。 详见文献2 进入2 1 世纪，人类文明以前所未有的高速度发展。衣、食、住、行等各个方面都发生了日 新月异的变化。我国在加入w t o 后，切会逐渐与国际接轨，人民的物质文化生活水平不断提 高，私人小汽车将越来越多的进入到家庭，我国是世界上人口最多的国家，所以城市交通规划和 管理是城市建设的项带有全局性的任务。城市交通网络的分布直接影响城市各项基础设施( 例 如，上下水管道，煤气管网和输电线路的设置) 。个现代化的城市，首先就必须具有现代化的 城市交通。因此城市交通规划管理，必然也是城市规划的最基本的内容之一。城市交通规划管理 的目的在于协调各种运输方式之间的关系，在可能的资金、资源条件下，对交通系统的建设、布 局以及运营作出最佳安排，使交通供给发挥最大作用，以便尽可能地满足交通需求，从而适应社 会政治、经济发展的需要。调度方案的实施，是系列循环往复的过程，是个不断滚动发展的 过程，在每个滚动阶段，可能都需要从头开始进行再循环。总之，要全面的来认识交通规划管理 的综合性和复杂性，客观的审视数学模型的价值和含义，使之更加符合城市交通的发展规律。 1 4 城市交通若干模型 经过多年的积累，城市交通模型有了很大的发展，研究方法也越来越多样化。一般可以分 为：平衡模型、动态分配、计算机模拟、变分法、最优控制理论等分支，交通与其它学科进行 融洽，互为促进，开辟了许多新的领域，也引起了众多学者们的关注。下面从中举出几个，向 大家介绍以下模型发展的动态。 m e r c h a n t - - - n e m h a u s e r 于1 9 7 8 建立如下动态模型： = m i n t h o 。( 死。) 公交调度排队系统研究 s t 对于t = 0 , 1 ，丁一1 x 口h 1 = x 口f g 口( x 口f ) + 扰口f 丁 “扩s 幻+ g 口( x 讲) a e a ( k )口b ( 七) x 口o = r 口0 “口f ，x 口f 0 v 口a ( 路段状态方程) ( 节点平衡方程) ( 初始条件) 其中，h 删( x 讲) 为路段a 时段t 上的交通负荷所引起的总出行费用：为t 时段路段a 上的流向终点的交通负荷；为t 时段路段a 上的流入量；g 口( ) 为t 时段路段a 上的流入 量函数：s 缸为t 时段节点k 产生的出行量；a ( k ) 为有向路段起点是k 的路段集合：b ( k ) 为有 向路段终点是k 的路段集合。 多模式的均衡配流模型 四兵锋、高自友于1 9 9 9 年3 月提出多模式的均衡配流模型： 见文献1 1 、1 2 m i n ( x 1 ，x 2x 3 q 1q 2q3 ) = 莓 莓( w ) 咖+ 三f r s ( g 抛：一g 三) z 船呼o q 三) s t 爿坩= g ： 血 斤坩= q 三 七 刀玎= g 志 七 g 二+ q 二+ g 二= q 甩 苌s 。f ：s 。f i 2 0 1 2 v r ，s v r ，j v r ，s v r ，s v k ，r ，s 公交调度排队系统研究 模型考虑的是城市交通中机动车、自行车、公交车的混合出行模型，表示o d 对r s 之 间第k 条路径上的第n 中交通方式的交通流量：g 三表示从r 到s 的第n 中交通方式的交通需 求量；石：表示在路段a 上的第n 中交通方式的交通流量；f ：表示在路段a 上的第n 中交通方 式的阻抗；矽疗表示第n 种交通方式的吸引度；r 为模型校正参数。 二级公路交通的m l a r k o v 模型 李俊峰、刘崇丽、吴大为于2 0 0 0 年8 月提出1 蟆型，它使用状态转移矩阵来衡量公路服 务水平。 模型认为公路上形势的车辆有三种状态：快速状态、正常状态、慢速状态，并且每一车辆 都处于状态变化中。其转化关系如下： 慢速状态二快速状态 随后给出规则确定车辆的状态及状态的转移，我们就得到了分车种的步转移概率矩阵 f ，p - t 尸= ip 2 l l p ，。 巴表示第i 种状态转化为第j 种状态的概率。根据遍历性定理，求l i mp ”= o 就可得到 疗 一个不依赖于初始状态的、车辆在公路上行使状态的稳定概率矩阵q 。 通过算例，我们知道车辆的状态概率基本上不随着数据的变化而发生剧烈的变化。所以我 们可以用状态矩阵q 来描述公路的服务水平。 公交调度排队系统研究 1 5 公交调度相关文献 居民出行时间是随机的，公交车辆的行使由调度调配，基于地理信息系统( g i s ) 实时数 据的公交调度指挥研究就是在乘客与公交车的配车数之间进行调配，权衡决策，使其达到合理 的平衡状态，这显然是个随机过程的排队论问题。排队论解决系统最优与最优控制的一门科 学。排队论自20 世纪初丹麦电话工程师a k e r l a n g 开创性论文“概率论和电话通话”发 表以来，其应用领域不断扩大。国外起步早，理论工具充足，算法较完善。i s r a e l i ( 1 996 ) 在 一篇论文中讨论了“公交车只要不连续发车，出行者或早或晚出行都会引发调度延误 的种 情况。现在论文主要用直接出行选择模型讨论时间表的若干问题。l a r s o n ( 1 9 8 1 ) 讨论与时间 表有关的中值( p - m e d i a n ) 问题，选取若干个服务站点，建立目标函数使乘客到服务设施用时 最少。在交通时间表中车辆是工具，使用者是出行人，可以及时测量他们的距离，而不是地理 上的位置。将交通时间表与中值问题比较有三点不同：( 1 ) 使用者和工具被放在一些孤立的点 上，出行者可随时离开，建立时间函数，车辆也可随时调度；( 2 ) 对于出行者的调度延误费用， 因提前或延后而异，例如，参加重要会议的人提前或迟到十分钟，代价是不样的，因此时间表 问题不能简单用距离度量来表示，同样距离各方向的价值是不一样的。( 3 ) 延误费用随出行目 的而变化，调度时间表是基于般或平均“出行 行为而制定的。在日常线路运营中，公共交 通的服务具有不规则性，因为它受许多难以意料的不定因素的影响，例如乘客分布的随机| 生、 车辆速度、交通事故及气候因素等，同时在各种开发的模型中必须考虑数目庞大的路段、线路、 道路等作为变量及各种限制条件，实际上公交调度是非常复杂的。我们可通过不断更新的计算 机技术弥补“经验调度所带来的损失。公交网络调度问题属于一般类型车辆调度问题，是n p 问题，即计算量是按变量的指数增长。这类问题描述为从个或多个车场出发，遍历服务站点， 再回到出发点。通常采用启发式算法。调度需要考虑的有客观函数、开发条件、特殊约束，因 地而异，但都要考虑以下几个方面：( 1 ) 优化某给定的；( 2 ) 车辆的始发站、终点站是固定 的；( 3 ) 每个车场有最大停车数；( 4 ) 满足所有开发条件、约束。g a v i s h 和s h i f t e r ( 1 9 r 7 8 ) 将车辆调度作为大都市公交公司开发项目。当时对几千个相当短的线路进行车辆调度，时刻表 优化了各种交通需求和计划。目标函数在满足开发条件的。前提下，降f 氐运营成本。他们提出一 1 4 公交调度排队系统研究 种算法解决此问题。假设单一车场车辆服务n 条线路。每一条线路都有起点终点始发时间末车 时间，目标函数的解就是用最少的车辆服务所有线路。用网络表述此问题：路段用节点表示， 如果在道路i 的结束时间加上在道路i 的终点与道路j 的始点行驶的时间小于道路j 的起始时间， 称路段( i = i ) 流通。问题就变为寻找最少路段遍历所有点，路段是从个车场出发又回这个车 场的规划好道路，归结为最小费用流问题。有时在目标函数中考虑免费时间，用两步程序解决。 b a d i n 和g l d e n ( 1 9 8 1 ) 提出建议性的程序解决此问题。总之，单一车场问题较容易解决。带 有更现实的约束条件，如路段时间限制等，这又成了n p 问题，大多数这类问题仅能通过启发 式算法来解决。 详见文献1 7 、1 8 、1 9 、2 0 、2 l 】 国内计算发车间隔时间方面的研究尚属起步阶段，使用的方法比较直观，仅为编制车辆运 行时刻表做了个大致的框架，具体的时刻表的编制工作内容远不i 匕这些。已发表的论文有： 孙芙灵( 1 9 9 7 ) 公交调度中发车间隔的确定方法的探讨，她在这篇论文中根据调查资料给出 发车间隔的四种方法，力求达到的四个目标是：根据乘客需求确定个可供选择的发车间隔： 当车辆供给受到约束时，相应地改变发车间隔：在相邻的时间段使用平滑法调节发车间隔；在 个发车时刻表中综合利用不同的间隔的设置法。特别是利用“平滑法确定相邻时间段的间隔” 值得我们借鉴，而有些论文对相邻时间段的发车仅作跳跃式配车。陈强( 2 0 0 2 ) 公交车调度优 化模型主要是建立公交车调度的优化模型，并给出了两个起点站的发车时刻表。既考虑了乘 客的利益又兼顾了公交公司的利益。在对乘客的利益作考虑时，得出乘客的等待时间的长短是 衡量乘客利益大小的合理指标；在对公司的利益作考虑时，得出公司所用车辆的数量是衡量公 司利益大小的直接指标。建立起关于发车时间间隔的动态模型，并且根据实际睛况，制定出了 一个便于操作的全大公交车调度方案，即起点站发车时刻表。为了设计更好的调度方案，也给 出了一些收集数据的建议。根据数据考虑峰值分布及上下班规律，将上下车人数看成正态分布， 这种做法是否合适，有待在实践中进一步验证。 为了设计个具有实际应用的公交车辆智能调度系统，就有必要采用智能化算法来求解车 辆运营调度优化问题，以提高典陕逮i 生，满足实际| 立用需求。因此快速、有效地得到个合理 的最优解，算法的选择是关键。公交调度指挥的算法主要有多目标规划、遗传算法、启发式算 法等；朱金寿( 2 0 0 2 ) 公交车调度方案的研究建立了个双目标规划模型，利用已给数据对 公交调度排队系统研究 模型求解，并设计了个求公交车在不同时间段内的发车时间间隔算法。李军( 1 9 9 9 ) 车辆调 度问题的分派启发式算法对有时间窗的车辆调度问题进行了分析，提出了以分派为基础的启 发式算法。算法中讨论了如何完成任务所需要的车辆数，定义了两种分派费用，设计了在分派 过程中安排线路的方法。 本文用排队论的知识解决在制定公共交通调度时间表时如何将公司的效益性和公益i 生有机 结合起来。着重讨论根据理论计算发车间隔时间，制定较为合理的车辆调度时间表。对两线车 需要改善在换乘站的车辆衔接时间。对公交网络或多线车提出优化算法。优化公交调度就是增 强公交车辆的机动性，防止“跑空车”，进而提高公交公司的服务水平和经济效益。 1 6 排队论基本知识介绍 最早有关排队论的著作般人公认的是1 9 0 1 年= 丹麦数学家e r l a n g 所发表的论文，他服务 于丹麦哥本哈根电话公司，该论文研究的主题是电话交换机的使用状况，他的主要的著作成于 1 9 0 9 年到1 9 2 0 年间，有关他的生平与作品可参阅布鲁克迈尔( e b r o c k m e y e r ) 等人的文章。 e r l a n g 之后从事排队论研究的先驱人物有法国数学家勃拉彻( e p o e l a c 7 e k ) 和前苏联数学 家金勤( a k h i n t c h i n e ) ，他们在这方面的研究课题都在三十年代完成并载于f 电1 门后来撰写的著 作罩。第二次世界大战之后应用概率论，运筹学得到了广泛而深入的发展，排队论的论述已十 分普及了，五十年代初期英国人堪道( d g k e n d a l l ) 有系统地阐述了排队问题，并且利用嵌入 马尔可夫链的方法推动了排队论的进步发展，堪道的两篇重要论文分别发表于1 9 5 1 年和1 9 5 3 年。排队论与纯量理论，水库问题等的联系开始于五十年代末到六十年代初，这其间先后问世 的重要著作有优先排队问题网络队列问题。六十年代排队论研究的课题日趋复杂，因而开始了 近似法的探讨与队列上下限问题的研究，在应用方面排队论进入了生产线、交通线。排队论在 计算机、计算机网络，通讯方面的应用主要开始于七十年代。由于排队问题多呈网络出现计算 上的繁琐使得研究范围扩及到计算方法上面，同时有关模拟法的研究继五十年代之后再度成为 科研工作者的注意对象。排队论的发展推广起自于实际应用的需要，同时由于近代计算工具的 精密、快速以及排队问题本身趋于复杂的倾向决定了排队论研究的方向。 要说明个排队问题，必须了解顾客到达的过程、服务时间、排队规则以及服务系统的结 1 6 公交调度排队系统研究 构。到达过程可用两个连续到达时刻的间隔，或简称为“到达间隔 来表示，单位时间内平均 到达的个数称做“到达率”，其值等于平均到达间隔的倒数。到达过程的形式可以是下列任何 种：l 、规则到达。也就是每隔一固定的时间就有一个顾客到达，这类到达间隔在实际问题上 并不常见，在自动化生产线上，有时进料问题可以是这种形式的到达过程。2 、完全随机到达。 有成p i o s s o n 到达过程，到达间隔为指数分布，各个间隔为相同分布而相互独立的随机变数， 这种形式具有的特性往往使得数学推演极为简单，同时在应用方面也颇符合实际，因此也是最 为普遍采用的形式，完全随机的假设是基于在任何时刻个到达发生的机会完全相同，而两个 或两个以上的到达同时发生的可能性极低。3 、_ 般相同而独立的到达。或称更新到达过程，这 类形式比之第二类较具一殷| 生，各个到达间隔为相互独立相同分布的随机变量，但是不一定是 指数分布，在正常隋形下机器的故障发生常常用这类假设，连续两次故障间隔即为一次到达间 隔。4 、前述三类到达都是先假设一次只有个顾客到达服务系统，在实际中却不乏成批到达的 情形。工厂、商店进货通常是一次到达许多件，有时虽然一次仅有灏客到达，但是在极短 的时间内有多个到达时也可以成批到达视之。至于到达的批量可以为常数，也可以是随机变量。 5 、非平稳性到达。在某些隋形下，到达频率可以因时而异。最常见的实例是通讯问题，上下班 时车辆拥挤，而上班时间电话使用频率也较高，在数学模型里这类问题都假设为到达率是时间 的函数。还有：依态到达、连续到达等。【详见文献1 3 】 服务时间的类别也有多种，通常是以服务时间长度的分布来表示。平均服务时间的倒数称 作“服务率”，也可视作服务台在被占用期间，单位时间内可以完成服务的平均次数，到达率与 服务率之间的关系是度量系统负荷量的重要指标，服务时间的分布有；1 、指数分布。2 、e r l a n g 分布。3 、超指数分布等。 不同的排队规则：1 、先到先占。这是最常见的一种排队规则，先到服务台的顾客有优先占 用服务台的权利，除非特别声明，般问题都是先到先占的排队规则。2 、后到先占。多用于存 货系统的盘存以及在某些隋形下计算机内部的调度，在般排队问题上极为少见。后到先占的 安排尚可进一步分为抢占与非抢占两种，前者是指后来者可以即刻占用服务台，而后种隋形 后来者却必须等到目f i f 占用者完成服务离开服务台后才能占用。3 、优先占用。到达服务台的顾 客可以分成数类，每类都有不同的占用权，优先权高者先占用服务台，和后到先占相同的是， 1 7 公交调度排队系统研究 也可分为抢占与非抢占，在允许抢占的情形下，被抢占的顾客再度占用服务台时，通常假设服 务由上次中断处继续下去这种情形称作“续接”，但有时却得重新开始，这时称作“重复”，重 新丌始的服务时间可以与上次相同，也可以不同，由于重复抢占的实际例子不多，一般文献对 此也较少讨论。优先占用在排队问题上有个重要的应用，往往通过优先权的安排可以使得服 务系统操作成本降低，如港口码头设施有限时，可以安排泊于港外船只以不同优先进港次序， 以减少泊船费用，般来说，费用高而使用码头时间短的，应给予较高的优先权。其它规则有： 循环占用、共同占用、占而不用等。 最后介绍服务系统的结构。排队问题依其服务台数依其队列的组成来区分，有下列几种：l 、 单服务台系统。这个系统仅有个服务台。2 、多道服务台系统。数个完全相同的服务台，到 达的顾客可以使用其中任何一个服务台。如果到达者只排个队列，那么在服务台全被占满时， 该服务系统的排队情形就近似于单- n 务台以服务率为甩的随机行为。假设到达者被依次安 排去不同的服务台，那么服务系统就有力个队列，每个队列的随机行为相同，整个服务系统就 如同以个单- - 月f l 务台系统，如果到达率为a ，则每个单一服务台的到达率就是a 疗。倘若每个 服务台有自己的队列，同时顾客可以自由移换到较短的队列上，那么就队列长度的变化而言， 这种排队方式与单一队列没有什么区别。3 、纵列系统。由以个子系统组成，子系统可为单一或 多道服务台系统，到达的顾客依次进入第一、第二，第n 个子系统，然而，在进入某子 系统之前必须完成前面各个子系统上的服务要求，这种问题最常见于流水生产线，被加工的物 件是依次置于不同的机器上进行的。 排队模型的分类。堪道在1 9 5 3 年提出一个分类方法，按照各部分特征中最主要的、影响最 大的三个，即l 、相继顾客到达间隔时间的分布；2 、服务时间的分布；3 、服务台数个数。按 照这三个特征分类，并用一定符号表示。1 9 7 1 年一次关于排队论符号标准化会议上决定用 y z a b c 表示排队论模型特征。其中x 处填写表示相继到达间隔时间的分布；y 处填 写表示服务时间的分布；z 处填写并列服务的服务台数的数目：a 处填写系统容量限带i jn ：b 处填写顾客源数目m ：c 处填写服务规则，如先到先服务，后到后服务。 主要模型有：m m l 、必m1 1 1n 、m m m 、m m1 1 1 0 0 k 等。 肘m l 系统是指：输入过程顾客源是无限的，顾客的到达是个p o i s s o n 过程，这 1 8 公交调度排队系统研究 是第一个“m ”的含义；排队规贝| 卜- 毒骘暂寺制，先到先服务，对队长没有限制；服务机构一 各顾客的服务时间是相互独立的，服从相同的负指数分布，这是第二个“m ”的含义。以此类 推mim fin 系统容量为n ，即排队等待的顾客最多为n 一1 ，在某顾客到达时，如果系统中 已有n 个顾客，那么这个顾客就被拒绝进入系统。m m 脚系统特征与m i m i i 相同，不同 的是有聊个服务台每个服务台的工作相互独立，平均服务率相同，于是整个服务机构的平均服 ， 务率为，似，令p = l ，仍称p 为该服务系统的服务强度。显然只有当p o ， 故假设乘客到站服从p o i s s o n 分布。用p o i s s o n 分布来描述乘客到站的概率时，只要知道单位时 间内乘客到达的平均数五，就可知道同时段内乘客到达数目的概率分布。单位时间内到达n 个 乘客的概率为：p 量阻( ，) = ，z 】= g p 一山，捌，2 ，3 ，。 由于假设乘砌闭系统中不流失， 公交高峰是由上下班人造成的，由此可以推断：天内在上下行方向上各站的上下车人数对应 增减情况基本相同，下面着重分析正向的情况，反向情况类似 2 4 2 符号说明 p = - o ) = h i ：掣p m 州，2 ，3 ，p o i s s o n 过程 g ( t ) = 2 e ，兄 0负指数乡沛 九表示第f 时段第j 站的平均输入率 n j ，为第i 时段第j 站乘客到站总数 n 表示车辆最大载客量 t n i j 表示第i 时段第j 站车辆服务时间 表示车上人数 公交调度排队系统研究 表示第i 时段第j 站车辆进出站时间之和 e ( l 打) 第f 时段在车站等车平均乘客数 也，。) 第f 时段在车站等车平均乘客数 g ( w o q ) 第f 时段在乘客候车时间的期望值 e ( w 扣) 表示第i 小时第j 站所有乘客逗留时间的期望值 f ，为离开第j 站时车上的乘客数 ，g ) 第i 小时下车人数的正态分布密度函数 ：g ) 第i 小时上车人数的正态分布密度函数 从第i 小时第j 站平均下车人数 彳) - i ，j ( j - 1 ) 站到第j 站的站间距 t 川 第( n - 1 ) 辆车的发车时间 2 4 3 模型的建立 1 ) 乘客上车模型的建立与求解 非始发站乘客等车模型 经分析此问题为m m 1 模型。乘客到车站过程可以认为服从p 0iss o n 过程。乘客到车站 的过程满足( a ) 平衡性( b ) 独立增量| 生( c ) 有限性( d ) 普通性。时间t 到达人数a ( t ) 的概 率满足， p = 口( ，) = 门】= 譬p m 域2 ，3 ，( 2 1 ) p o i s s o n 分布参数厶= 6 0 ， ( 2 2 ) 乙= 万1 蚋等 包3 ， 公交调度排队系统研究 乘客般都能等到车来，现在的公交服务也不会让乘客等很长时间，2 0 0 2 年的公交调查， 居民9 0 以上乘公交车远途出行，出现候车时间大于1 5 分钟的情况小于0 1 ，可忽略离去的， 即发车间隔a t 1 5 ( m i n ) 。已知到达规律服从参数是名的p o i s s o n 分布，服务时间服从参数是 的负指数分布，任意时刻t 的状态为r l 的概率p 。o ) 在时刻( t + a t ) 系统中有个n 乘客( n o ) 存在两种晴况( 不考虑到达2 个人以上的情形) ，为了书写方便暂时省略下标： 情 况 在时刻t 乘客数在区间( t ，t + a t )在时刻t + ，乘客数 到达离去 an n bn - io n 0 表示发生，x 表示没发生 p ，( t + a t ) = p 。o ) ( 1 - 力a t 一t ) + p ，i ( t ) 五a t + o ( a t ) 盟等盟= 嘏( ，) 一o + ) p o ( 0