（运筹学与控制论专业论文）快速公交调度算法与研究.pdf

：己匕0 上 ：i 川i l ll li lli i ii ii iii llll ；y 18 4 2 8 5 7 at h e s i sf o rt h ed e g r e eo fm a s t e ri no p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s a l g o r i t h ma n d r e s e a r c ho nb u sr a p i dt r a n s i t b y l iy a n s u p e r v i s o r ：v i c e p r o f e s s o rz h a n gx i u h u a n o r t h e a s t e r nu n i v e r s i t y j u l y2 0 0 8 ti f 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二f l 思0 学位论文作者签名：物 日 期：硎孑雩7 目 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： i j 半年口一年刚一年半口两年口 学位论文作者签名：棼移 签字日期：缈艿辟7 日 j 导师躲澎 签字日期：刃分 ，鼍1孓 ，卜，t 。 东北大学硕士学位论文摘要 快速公交调度算法与研究 摘要 随着我国城市化进程的发展，城市交通问题同益严重和普遍，已经影响了城市的生 产和生活。如何解决交通问题已经成为人们关注的焦点。在这种情况下，智能交通系统 ( i n t e l l i g e n tt r a n s p o r ts y s t e m s ，i t s ) 便成为解决这个问题的重要途径之一。我国i t s 技 术的快速发展，特别是近些年国内若干城市先进公交系统示范工程的建设与实施，支持 智能公交调度决策的信息采集、发布技术趋于成熟，公交优先运行环境得到很好的改善。 先进的公共交通系统a p t s ( a d v a n c e dp u b l i ct r a n s p o r t a t i o ns y s t e m ) 是i t s 的重要的 子系统之一。a p t s 系统一般由公共交通管理调度系统、公交运行信息系统、快速公交 系统( b r t ) ：先进安全公交车辆组成。b r t ( b u sr a p i dt r a n s i t ) 是a p t s 的重要组成部分。 自2 0 0 5 年起，北京、杭州、昆明、合肥、济南、深圳、大连、常州和厦门等市已建成 和正在建设b r t 项目，并且大大缓解了城市的交通压力。 公交调度是影响公交系统运行效率和服务水平的主要方面，是智能公交系统研究的 核心内容。本论文是在研究i t s 的基础上，认真学习了蚁群优化算法和遗传算法的基 本知识，用混合蚁群优化算法的遗传算法解决快速公交车辆发车调度问题。公交车辆发 车调度是公交调度的基本模式，本文以乘客等车时间成本最小和公交企业收益最大为目 标，考虑最大和最小发车间隔、两个相邻的发车间隔以及满载率约束，以发车时刻为变 量建立数学模型。 本文在算法设计上，将遗传算法和蚁群优化算法混合使用。在遗传算法每次交叉运 算后，从当前群体中找出最优染色体，可将其视为较优解，用蚁群算法来对其基因进行 变异寻找更优秀的染色体。每个蚂蚁按选择概率函数选择路径，产生出一个新的染色体。 如果新的染色体比原来较优的染色体适应度好，则保留：反之，不保留。当寻找到的较 好的染色体数量达到群体规模时，停止寻找。这样，用蚁群优化算法指导遗传算法的变 异运算，增强了变异运算的智能性。并以大连市快速公交为例，求得整个调度时期内的 不均匀发车时刻表。如按得到的结果进行车辆调度，可以比目前实际采用的调度减少发 车数量，节省成本，丽不会影响乘客的出行。 关键词：遗传算法、蚁群优化算法、智能交通系统、公交调度、快速公交 一l 卜一 p：， ， i t j 东北大学硕士学位论文a b s t r a c t a l g o r i t h ma n dr e s e a r c ho nb u sr a p i dt r a n s i t a bs t r a c t w i t ht h ed e v e l o p m e n to fc h i n a su r b a n i z a t i o n , t r a f f i cp r o b l e m so fu r b a n sh a v eb e c o m e i n c r e a s i n g l ys e r i o u sa n dw i d e s p r e a d ，w h i c hh a sa f f e c t e dt h ec i t y sp r o d u c t i o na n do u rd a i l yl i f e h o wt os o l v et r a f f i cp r o b l e m sh a sb e c o m et h ef o c u so fe o m n l e nc o n c e r n u n d e rt h i s c i r c u m s t a n c e ，t h ei n t e l l i g e n tt r a n s p o r ts y s t e m s ( i t s ) w i l lb e c o m ea ni m p o r t a n tw a yt os o l v e t h e s ep r o b l e m s w i t ht h er a p i dd e v e l o p m e n to fc h i n a si t st e c h n o l o g y ，e s p e c i a l l y , an u m b e ro f d o m e s t i cc i t i e sh a v ec o n s t r u c t e da n di m p l e m e n t e ds o m ed e m o n s t r a t i o np r o j e c t si na d v a n c e d p u b l i ct r a n s p o r t a t i o ns y s t e mi nr e c e n ty e a r s t h et e c h n o l o g yo fi n f o r m a t i o nc o l l e c t i o na n d p u b l i s h i n g ，w h i c hs u p p o r tt h ed e c i s i o n - m a k i n go fb u ss c h e d u l i n g i sm a t u r e a n dt h e e n v i r o n m e n to f p r i o r i t y - o p e r a t i n go f p u b l i ct r a n s p o r ti sw e l li m p r o v e d a d v a n c e dp u b l i ct r a n s p o r t a t i o ns y s t e m ( a p t s ) i so n eo ft h em a j o rs u b s y s t e m so fi t s i ng e n e r a l ，a p t si n c l u d e ：t h e p u b l i ct r a n s p o r ts c h e d u l i n gm a n a g e m e n ts y s t e m ，t h eb u s i n f o r m a t i o no fo p e r a t i o n s y s t e m ，b u sr a p i dt r a n s i ts y s t e m ( b r t ) ，t h ea d v a n c e ds e c u r i t yo f p u b l i ct r a n s p o r tv e h i c l e s b r ti sa ni m p o r t a n tp a r to fa p t s s i n c e2 0 0 5 ，al o to fb r tp r o j e c t s h a v eb e e nb u i l ta n da r eb u i l d i n gi nb e i j i n g ，h a n g z h o u ，k u n m i n g ，h e f e i ，j i n a n ， s h e n z h e n , d a l i a n ，x i a m e na n dc h a n g z h o u , w h i c hg r e a t l yr e d u c et h ec i t i e s t r a f f i cp r e s s u r e b u ss c h e d u l ei so n eo ft h em a i na s p e c t s ，w h i c ha f f e c tt h eo p e r a t i n ge f f i c i e n c yo fp u b l i c t r a n s p o r t a t i o ns y s t e m a n ds e r v i c e l e v e l ，a n db e c o m et h ec o r ec o n t e n to fi n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m t h i sp a p e ri so nt h eb a s i so fi t s ，谢也c o n s c i e n t i o u s l ys t u d yt h eb a s i c k n o w l e d g eo fa n tc o l o n yo p t i m i z a t i o na l g o r i t h m sa n dg e n e t i ca l g o r i t h m ，u s i n gm i x e da n t c o l o n yo p t i m i z a t i o ng e n e t i ca l g o r i t h mt os o l v et h es c h e d u l ep r o b l e mo fb r t s c h e d u l i n g 酣d i st h eb a s i cm o d eo fp u b l i ct r a n s p o r t t h eg o a li st om a k et h et i m ep a s s e n g e r sw a i t i n gf o r b u s e sm j _ r i n u ma n dt h ei n c o m eo fp u b l i ct r a n s p o r t e n t e r p r i s e sm a x i m u m ，a sw e l la s c o n s i d e r i n gt h el o n g e s ta n dt h es h o r t e s tg r i ds p a c i n g ，t h eg r i ds p a c i n go ft w oa d j a c e n tb u s e s a n dt h el o a df a c t o r u s i n gt h es t a r tt i m ea sv a r i a b l e st oe s t a b l i s hm a t h e m a t i c a lm o d e l i nt h i sp a p e r , w em i x e d - u s eg e n e t i ca l g o r i t h m sa n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m a f t e re a c hc r o s s o p e r a t o r , w ec h o o s et h eo p t i m a lc h r o m o s o m e si nc u r r e n tg r o u pa st h e o p t i m u ms o l u t i o n , t h e nu s i n ga n t st of i n dt h e i rg e n em u t a t i o nw h i c hi sb e t t e r a c c o r d i n gt o p r o b a b i l i t yf u n c t i o n , e a c ha n tc h o o s et h ep a t h s ，t h e np r o d u c ean e wc h r o m o s o m e i ft h en e w h 1 一 东北大学硕士学位论文 a b s t r a c t c h r o m o s o m ei sb e t t e rt h a nt h eo r i g i n a lc h r o m o s o m ea c c o r d i n gt of i t n e s s ，t h e nr e t a i nt h e c o n t r a r y ；o t h e r w i s ea d a n d o ni t i ft h en u m b e ro fb e t t e rc h r o m o s o m eg r o u p si su pt ot h e i r p o p u l a t i o n , w es t o pl o o k i n gf o ri t i nt h i sw a y , u s i n ga n tc o l o n yo p t i m i z a t i o na l g o r i t h ma st h e g u i d a n c eo fv a r i a n c ei ng e n e t i ca l g o r i t h m s ，w em a k et h ev a r i a t i o nm o r ei n t e l l i g e n t u s i n g b u sr a p i dt r a n s i ti nd a l i a na sa l le x a m p l et os e e kf o rs t a r tt i m e sd u r i n gt h ee n t i r es c h e d u l i n g p e r i o d i fw eu s et h er e s u l t so b t a i n e di nb u ss c h e d u l i n g ，t h en u m b e ro fg r i da n dc o s tc a nb e g r e a t l yr e d u c e db u tn o ta f f e c tp a s s e n g e r s t r a v e l k e yw o r d s ：g e n e t i ca l g o r i t h m , a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，i n t e l l i g e n tt r a n s p o r t s y s t e m s ，p u b l i ct r a n s p o r ts c h e d u l i n g ，b u sr a p i dt r a n s i t 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 智能交通系统的基本概念1 1 1 1 智能交通系统的产生1 1 1 2 智能交通系统的组成1 1 2a p t s 的基本概念2 1 3 快速公交系统( b r t ) 概述2 1 3 1b r t 系统的组成2 1 3 2b r t 系统的特点3 1 3 3b r t 建设现状4 1 3 4 发展b r t 系统的必要性5 1 4 快速公交车辆调度6 1 4 1 国外公交调度研究7 1 4 2 国内公交调度研究8 第2 章遗传算法基础知识1 1 2 1 遗传算法简介1 l 2 1 1 遗传算法的产生与发展1 1 2 1 2 遗传算法的基本思想1 1 2 1 3 遗传算法的特点1 2 2 1 4 遗传算法应用及今后研究的主要方面1 3 2 2 遗传算法的基本实施步骤1 3 2 2 1 遗传算法中的基本概念1 3 2 2 2 遗传算法的基本步骤1 4 2 2 3 遗传算法的应用关键1 6 第3 章蚁群算法基础知识1 9 3 1 蚁群算法基本原理1 9 3 1 1 引言1 9 3 1 2 真实蚂蚁的集体行为1 9 3 1 3 人工蚂蚁2 2 3 2 图理论2 2 3 3 蚁群优化算法2 4 3 3 1 蚁群算法描述2 4 3 3 2 蚁群算法基本模型的特点2 6 第4 章算法实现与结果分析2 7 4 1b r t 车辆调度模型的建立2 7 4 1 1b r t 下车辆调度优化数学模型基本假设2 7 4 1 2 模型目标函数：2 7 4 1 3 模型约束条件3 0 4 1 4 发车时刻模型3 0 东北大学硕士学位论文目录 4 2 算法设计3 1 4 3 实例应用3 4 第5 章实时调度策略研究3 7 5 1 实时调度策略概述3 7 5 1 1 实时调度策略研究现状3 7 5 1 2 实时调度策略3 8 5 2 快速公交实时调度4 0 5 2 1 模型建立4 l 第6 章总结和展望4 5 参考文献4 7 致谢5 l v 卜一 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 智能交通系统的基本概念 智能交通系统( i n t e l l i g e n tt r a n s p o r ts y s t e m s ，简称i t s ) 早期曾被称为智能车辆与 道路系统( i v h s ) ，就是将先进的信息技术、传感器技术、数据通讯技术、自动控制技 术、运筹学、图像分析技术、计算机网络和人工智能等有效地综合运用于整个交通管理 体系。 1 1 1 智能交通系统的产生 智能交通系统的提出具有深刻的时代背景。第一，汽车化社会带来的诸如交通阻塞、 事故增多、能源浪费和环境污染等社会问题同趋恶化，难以实现可持续交通运输发展的 目标。第二，人类环境可持续化。 从上个世纪八十年代，随着经济与技术的发展，面对越来越拥挤的交通，受城市空 间的限制，在城市晕持续的大量修路将变得越来越困难。经过长期和广泛的研究，许多 国家逐渐转移到用高新技术尤其是信息技术来改造现有的道路运输系统其管理体系。从 而大大提高了路网的通行能力和服务质量。科学家们在利用电子信息技术研究这一问题 的过程中发现不但能解决交通拥挤的问题，而且对交通安全、交通事故的处理与救援、 客货运输管理、高速公路收费系统等方面都会产生巨大的影响，因此他们不断扩大研究、 开发和实验的范围，上世纪九十年代初期i t s 应运而生。 1 1 2 智能交通系统的组成 i t s 可认为由下述几大部分组成1 1 - 2 1 ：信息管理中心、路边系统、车内系统、需求 管理系统、交通管理控制系统。其中信息管理中心是核心，为实现交通信息的共享提供 基础。路边系统的任务是实时监测路况和行车情况，包括路面参数和车离路面标志线的 距离等，也包括测量车辆速度的雷达、交通路口的信号灯和电子收费装置。车内系统包 括动态实时导航系统、视频音频输出导航信息提示等。需求管理系统占有很重要的地位， 对有需求的用户进行需求分析，以便管理控制系统制定高效的服务策略，实时提供给用 户，包括重载行驶的和预定车辆旅行的用户。交通管理控制系统是i t s 的决策中心。 东北大学硕士学位论文第1 章绪论 1 2a p t s 的基本概念 基于智能交通系统( i t s ) 的先进公共交通系统( a d v a n c e dp u b l i ct r a n s p o r t a t i o n s y s t e m ，a p t s ) 是i t s 的重要的子系统之一。通过综合利用信息技术、计算机技术、控 制技术、传感器技术，使先进公交系统具有了以下特点：高效的公交客运组织模式、快 速灵活的应变能力、完善的乘客信息服务，从而在信息、价格、速度、效率、舒适性等 方面提高公交吸引力。a p t s 主要应该包括常规公共交通( 公共汽车、电车) 系统和快速 r 轨道交通系统。常规公交a p t s 系统由公共交通管理调度系统、公交运行信息系统、快 速公交系统( b r t ) 、先进安全公交车辆组成。 t a p t s 具有如下功能：运用车载数据采集技术实现对运营车辆的监控；运用有效策 略使晚点车辆恢复正常运营；运用历史的或当前的操作数据及其他数据来源编制运营管 理计划；为乘客提供个人出行信息服务；提供安全协调监控与紧急求援服务系统的接口； 综合运用历史数据及其他因素规定司售人员的活动；编制运营车辆的维修计划并为修理 人员进行工作分配：可实现车内收费或路边收费和为乘客提供车辆运营信息( 即可到达 的车辆信息) 。 a p t s 系统结构由软、硬件结合，主要包括应用系统、技术支持系统、传输处理平 台三部分。其中应用系统主要包括：运营管理系统、区域运营调度系统、枢纽站运营调 度系统、乘客信息服务系统、公交求援调度系统。技术支持系统主要包括：车辆定位系 统、客流信息采集系统、地理信息系统、数据库系统；传输处理平台主要包括：无线电 通信系统、网络通信系统。 1 3 快速公交系统( b r t ) 概述 快速公交系统( b u sr a p i dt r a n s i t ，b r t ) 是一种介于轨道交通与常规公交之间的新型 运营系统。主要是指具有专有路权、封闭运行、水平登降、大容量车辆等一系列特征的 地面公共汽车系统。它利用现代公交技术配合智能交通的运营管理，使传统的公交系统 基本达到轨道交通的服务水平。 1 3 1b r t 系统的组成 ( 1 ) 专用车道与其他车辆在空间进行分离的道路空间进行运营，使其能够不受其他 车辆的影响，快速行驶。一般来说，专用车道采用如下形式1 新建专用道路；在已有道 路上，采用小型的物理隔离设施或标志标线隔离出专用车道；建设高架桥或地下通道开 辟专用车道。 ( 2 ) b r t 车辆 一2 一 东北大学硕士学位论文第1 章绪论 b r t 系统采用大容量、耗能少、污染小的改良型公交车辆。与常规公交车辆相比， b r t 车辆的车身长度、车体宽度、车门数都有所增加：独特的内部设计增加乘坐的舒适 性；清洁车辆的使用，节约能源、降低环境污染。 ( 3 ) 水平登降 b r t 系统中通过修建与b r t 车辆地板等高的候车台，或采用低地板的公交车辆， 不仅节约了时间，还便利乘客上下车，尤其是老、弱、幼及带行李的人上下车。 ( 4 ) 车外检售票系统 b r t 系统将售票系统置于候车站台内或站台外，并在公交车辆进站前完成收费，广 ， 泛使用现金或代用币，这样提高了上下车速度，节省了公交车辆的等候时间。 ( 5 ) 交叉路口优先系统 b r t 系统通过信号优先系统或高架桥、地下通道，使b r t 车辆在交叉路口优先通 行，减少了公交车辆在路口的停车延误和加减速时间，提高行车速度，减少了运行时间， 增加了行驶可靠性。 ( 6 ) 乘客信息系统 b r t 系统的乘客信息系统包括公共汽车站标志、路线、系统地图、时间表、运价表， 以及一些动态信息，如报告路线上车辆运行情况的自动汽车定位系统等。 1 3 2b r t 系统的特点 b r t 系统独特的技术特征，使其与其它交通方式相比，具有以下一些特点： ( 1 ) 投资少。b r t 系统由于是一种车辆路面运行系统，不需要修建轨道交通必需的 隧道或高架桥，仅需对现有路面进行改造或扩建，故其投资少。据有关资料显示，城市 轻轨交通每公里造价约1 2 0 0 3 4 0 0 万美元，地铁每公里造价约1 2 1 8 亿美元，而b r t 系统每公里仅为6 0 0 - - - 1 5 0 0 力美元，可见，建设l k m 地铁所需资金可建成1 0 2 0 k m b r t 线路。 ( 2 ) 速度快。由于b r t 系统具有专有路权、信号优先等技术特征，使得b r t 车辆 可以不受其他车辆干扰，快速运行。而水平登降、车外检售票技术的采用，使得b r t 车 辆停靠站的时间大大减少，进一步减少了运行时间。一般来说，b r t 车辆的运营速度 可达到2 0 k m h 以上，在某些系统完备路段，甚至可以达到4 0 5 0 k m h ，运营速度接近 轨道交通水平。 ( 3 ) 容量大。b r t 系统采用改良型车辆，其车身长度和宽度均比常规公交车辆有所 增加，大大增加了其单车载客量。如巴西库罩蒂巴市采用的出沃尔沃公司研制的双铰接 式公交车辆，使得其单车载客能力达到2 7 0 人。 东北大学硕士学位论文第1 章绪论 ( 4 ) 乘坐舒适、方便。b r t 车辆独特的内部设计，极大地增大了乘坐的舒适度；水 平登降系统的采用，便利乘客上下车：乘客信息系统的使用，便利乘客出行。 ( 5 ) 建设和使用灵活。b r t 系统的道路建设可以根据城市的财政情况分阶段进行， 各种技术设备也可逐步采用，并且可以实施一段运营一段。此外，b r t 系统投人运营 后，其线路可以根据不同时段及不同客流需求进行适当调配。 ( 6 ) 污染小。b r t 系统一般采用电车、清洁柴油公交车、天然气动力公交车等耗能 低、排放少的清洁公交车辆；同时，运行时加减速的有效减少，进一步减少了废气的排 放，从而使对环境的影响减到最低。 ( 7 ) 建设周期短。据有关资料显示，轨道交通网络的建成一般需要2 3 年的时间。 而b r t 系统一般仅需1 5 2 年的时间，所以b r t 系统可在短期内形成网络、发挥作用。 1 3 3b r t 建设现状 建设部大力推进公交优先战略，认真贯彻国务院( 2 0 0 5 ) 4 6 号“关于优先发展城市 公共交通的意见”文件，发展大容量快速公共汽车交通系统。建设部领导在全国城市公 共交通工作会议上要求各大城市要建设1 1 条b r t 线。建设b r t ，不但能够更好地发 展城市交通，而且能更好地节约能源和道路资源，减少环境污染。这是民生工程和民心 工程，得到了有关城市政府的重视和支持。 自2 0 0 5 年起，北京、杭州、昆明、合肥、济南、深圳、大连、常州和厦门已建成 和正在建设b r t 项目的基本情况如下。 ( 1 ) 北京市 2 0 0 5 年1 2 月3 0 日，北京市建成我国第一条b r t 线，全长1 6 k m ，为两侧有物理隔 离设施的全封闭式专用道，配备车长1 8 m ，发动机后置的低入口铰接式公共汽车9 0 辆， 线路日客运量现为1 3 万人次，最高时实破2 2 万人次。2 0 0 6 年共运送乘客3 3 1 3 8 万人 次，实现了相当2 6 0 辆公交车的客流量，降低了运营成本，减少了汽车排放与燃油消耗， 缓解了交通拥堵【3 1 。 ( 2 ) 杭州市 2 0 0 6 年4 月2 6 同，杭州市建成全长2 8 k m ，半封闭式( 采用划线和分道器隔离，必 要时公交车辆和社会车辆可互相借道通行) 专用道。配备车长1 8 m 、发动机后置低地板 铰接公共汽车4 8 辆，晟高峰时配车达7 5 辆( 其中2 7 辆为车长1 2 m 低地板公交车) ，r 客流量最高为7 3 万人次，全年客运量达1 6 0 6 万人次。 ( 3 ) 昆明市 在1 9 9 9 年丌通了国内第一条公交专用道的基础上，于2 0 0 6 年、2 0 0 7 年相继建成2 卜 ， 东北大学硕士学位论文第1 章绪论 条快速公交线，全长2 2 7 k m ，全封闭式专用道，现配备4 辆车长1 2 m 和1 8 m 的车进行 试运行。 ( 4 ) 合肥市 2 0 0 7 年4 月已有5 辆车长1 8 m ，发动机后置的低入口铰接公交车在快速公交线上试 运行。 ( 5 ) 济南市 计划在2 0 0 7 年l o 月建成全长1 1 5 5 k m 的复合式( 一部分为全封闭式和一部分为公 交专用道相结合) 专用道，配备2 0 辆1 2 m 和5 辆1 8 m ，发动机后置的低入口公交车。 ( 6 ) 国内其它城市 深圳市在建设2 2 5 k m 的b r t 线，配备1 1 8 辆特大型公交车，其中l g m 铰接车7 2 辆，1 3 7 m 特大型公交车4 6 辆，均为低地板公交车。大连市建成2 5 k m 的b r t 线。配 备6 4 辆公交车，其中l g m 绞接公交车3 2 辆，1 2 m 公交车3 2 辆，均为低地板公交车。 常州市现正建设约2 0 k m 的b r t 线。配备6 0 辆1 8 m 绞接公交车。厦门市现正建设3 4 k m 的b r t l 号线，配备4 2 辆1 8 m 低地板公交车【4 1 。 1 3 4 发展b r t 系统的必要性 ( 1 ) 解决城市交通拥堵 随着我国国民经济的迅速发展，机动车保有量迅猛增长，交通拥挤逐渐成为人们广 泛关注的问题。近几年，私人小汽车的迅速增加，进一步刺激了交通运输需求的增长， 给城市交通带来了极大的压力，交通拥挤成为制约城市发展的“瓶颈问题。虽然很多 城市对此问题采取了各种各样的措施，如增修道路、立交桥、人行天桥等，对城市交通 拥挤起到了一定的缓解，但这种缓解是短期的。因为道路的增修等只会迸一步刺激小汽 车的增长，而道路的建设又不可能与车辆的增长保持同步，从而进一步加剧了交通需求 与道路供给之间的矛盾。 ( 2 ) 降低财政投人 公共交通包括轨道交通和b r t 系统，两种交通方式相比，各有优势。轨道交通速 度快、容量大，据资料显示，地铁运送速度可达3 0 - - 4 0 k m h ，客运能力可达4 “万人l l ， 但是其投资额非常大，我国城市地铁的平均造价为每公罩2 7 亿元人民币；b r t 系统虽 然与轨道交通相比，速度和容量方面稍有逊色，但比起常规公交来说，已有很大提高， 其运送速度一般为2 0 k m h 以上，客运能力可达0 3 2 4 万人l l ，最重要的是其造价低廉， 据初步预算，b r t 系统的平均造价为每公里2 7 千力人民币，是地铁的1 1 0 。 而且b r t 系统投入运营后一般不需要财政补贴，而世界上绝大部分轨道交通的运 东北大学硕士学位论文第1 章绪论 营需要财政进行一定的补贴。北京5 5 k i n 的地铁，2 0 0 2 年的政府财政补贴就达4 亿元。 而b r t 系统由于运营成本低，票价适中，能够吸引大量客流，一般可以满足收支平衡， 无须财政补贴。b r t 系统以较低的资金投入获得较好的社会效益，是实现城市可持续发 展的有利保证。 ( 3 ) 减少环境污染 机动车保有量的迅速增长，极大地增加了车辆的尾气排放，对城市环境造成了极大 的污染。而b r t 系统一般采用电车、混合动力公交车、清洁柴油公交车、天然气动力 公交车、燃料电池公交车等清洁公交车辆，这些新型的公交车辆可实现低能耗、低排放， 对环境影响比较小；同时公交专用车道的使用，避免了交通拥堵时反复的加减速，可有 效地减少废气排放。 ( 4 ) 以人为本 b r t 系统充分体现了“以人为本 的思想，公交专用车道和交叉路1 ：3 优先通行系统 的使用，使大部分人的出行得到了优先( 一辆公交车辆的载客量是一辆小汽车的十几倍 至几十倍) ；水平登降系统的引用，便利了乘客上下车，尤其是方便了那些行动不便的 人；乘客信息系统的使用，使乘客更好的了解交通状况及出行情况，便利乘客出行。 1 4 快速公交车辆调度 公交调度是影响公交系统运行效率和服务水平的主要方面，是智能公交系统研究的 核心内容。公交调度问题通常可分为两类，即常规状态调度和异常状态调度【5 1 。前者基 于规律性的常态客流需求和基本的车辆使用条件，以实现公交车辆实际运行的时空轨迹 与时刻表规定的运行图轨迹偏差最小为主要目标，其调度手段不影响既定的行车计划。 后者面向非规律性的客流强烈波动、交通状况改变和车辆故障等情况，以及时恢复正常 运营秩序为主要目标，通常需要调整既定的行车计划。以往的研究多侧重于发挥公交调 度对异常事件的快速应对能力，较少关注用于提升公交车辆实际运行质量的常态调度策 略。应当指出：常态运营是公交营运过程中的主体，是影响整体服务水平和营运绩效的 关键，有必要重点研究。 。 车辆调度算法设计与实现是b r t 系统车辆智能管理的重要核心技术之，长期以 来一直受到学术界和产业界的广泛关注【6 j 。近年来，随着计算机硬件性能的提高，不少 学者提出遗传算法、禁忌算法、模拟退火算法以及神经网络等智能算法，将以上算法应 用于车辆调度问题的研究，成为了一个重要的研究方向。 卜 东北大学硕士学位论文第1 章绪论 1 4 1 国外公交调度研究 ( 1 ) 公交时刻表编制问题 公交时刻表编制是公交调度中的一项关键性工作，历来是公交调度研究工作中的热 点问题，它既关系到乘客对公交的满意度，也关系到公交公司的运营效益。对于公交时 刻表编制的研究，目的就是编制出满足乘客需求，同时也能使得公交公司运营效益最大 的时刻表。公交时刻表是由公交发车频率或者是发车时间间隔来确定的。 从上个世纪八十年代开始，就有众多国外学者，用数学规划方法研究如何确定发车 ， 频率。f t t r t h 和w i l s o n ( 1 9 8 1 ) 1 7 】采用了在总的成本，公交运力和载客率确定的约束条件之 下，使得乘客等待时间最少，社会效益最大的数学模型来确定公交发车频率。 c e d e r ( 1 9 8 4 ) t 8 】给出了四种不同发车频率确定方式，其中有两种方式是基于在某个站点某 个时间段统计得到的乘客到达数量来确定，用客流量最大的那个时间段的某个站点乘客 到达的数量除以所期望的公交载客量就得到发车频率。另外两种方式是基于某个时间段 内，整个线路乘客的周转量来确定，用线路通过的乘客周转量除以所期望的载客量得到 发车频率。c e d e r 和s t e m ( 1 9 8 4 ) t 9 】对于该问题，建立了一种整数规划模型，使用启发式 算法，借助计算机程序，实现了模型的求解过程。k o u t s o p o u l o s ，o d o n i 和w i l s o n ( 1 9 8 5 ) d j 在f u r t h 模型的目标函数之中，加入了刻画乘客舒适度的一种量化成本值，区分了在不 同时间段的不同的需求，得到了一个非线性优化模型，并且改进了该模型得到了一个线 性模型，从而简化了模型的求解过程。c e d e r ( 1 9 8 6 ) ! l l 】研究了基于不同类型的发车时间间 隔和不同方式所确定的发车频率以及特殊情况下的发车需求来编制公交时刻表编制的 三种不同方式：a d e b i s ，o 和x uj 【旺j 研究了行车间隔对公交服务水平的影响，如何通过间 隔控制来改善公交服务的可靠性，维护行车时刻表的正常执行。l e e k k t 和 s h o u f e l d p m ( 1 9 9 4 ) 1 1 3 】研究了公交起点站和终点站实时调度控制中，对即将发出的公交车 实行屯车策略，确定优化的行车问隔。 区域调度中的公交时刻表的编制与单线调度相比，一个重要的不同之处，就是调度 中心在确定各条线路的发车频率或间隔之后，还要考虑乘客在区域内换乘的方便性，从 而编制出能够最大限度地减少乘客在不同线路交叉点处换乘等待时间的公交时刻表。 c e d e r 和t a l ( 1 9 9 9 ) 研究了在发车频率确定，公交车数量和运力有限的情况下，使得不同 线路的车辆在交叉点，相遇的车辆数最大的发车时刻表。采用的是混合整数规划和启发 式算法。 ( 2 ) 车辆调度问题 当公交时刻表确定之后，剩下的问题就是为时刻表中确定的每个班次安排车辆。每 东北大学硕士学位论文第1 章绪论 条线路上的客流量随着时间的变化而变化的，因而发车频率在不同的时间段也有变化， 那么在不同的时间段一条线路对车的数量需求是不一样的。区域调度与单线调度最大的 不同之处就在于车辆安排在几条线路上运行，从比较直观的角度来看，当某条线路处在 高峰时段，就可以从处在低峰时段的线路抽调车辆。因此，车辆调度问题在区域调度中， 就是在满足给定时刻表中所确定的车次需求，使得车辆的总数量最小。 g a v i s h 和s h i f t e r ( 1 9 7 8 ) t 1 4 】将调度问题转化成了在满足行车班次需求约束条件下，使 得车辆数量以及车辆在运行过程中空驶时白j 最小的数学模型，并且给出了模型的求解算 法。在这个模型中，假定在同一个区域内的运行的公交车辆停放在同一个站场。b o d i n 和g o l d e n ( 1 9 8 1 ) m l 采用两阶段法对该问题( s i n g l ed e p o tv e h i c l es c h e d u l i n g ，s d v s ) 进行 了求解。而当在模型中加入其它约束时，例如线路对于行驶时间的约束，该问题就变成 了n p 难题( 不确定多项式问题) ，只能通过启发式算法进行求解。b e r t o s s i i l 6 1 等人研究 了区域内有多个停车站场情况下的车辆调度问题( m u l t i p l ed e p o tv e h i c l es c h e d u l i n g ， m d v s ) 。建立了在满足发车班次需求的条件下，使得车辆数量最少和每辆车停放在恰当 地点从而减少运行成本的数学模型。并且证明该问题也是一个n p 难题。m d v s 问题为 多线调度的实现提供了可能。l a m a t s c h ( 1 9 9 0 ) 2 7 】将m d v s 问题转化成为一个多种货物 从不同的源点( o r i g i n s ) 运往不同的目的地( d e s t i n a t i o n ) 的网络流量问题，并且给出了2 5 0 个班次，2 个站场以及2 0 0 个班次，3 个站场的车辆调度方案。m e s q u i t a 和p a i x a o ( 1 9 9 7 ) t l s 】 将模型进行了简化，使用分枝定界法进行求解。在解决m d v s 问题中，最成功的是 l o b e l ( 1 9 9 7 ) 。他采用一种称为拉格朗同定价( l a g r a n g e a np r i c i n g ) 的特定列生成法，解决 一个非常复杂的实际问题。他的模型中没有考虑线路运行时间的约束，他的模型与 f o r b e se ta 1 ( 1 9 9 4 ) 的模型十分类似。h a g h a n i 和b a n i h a s h e m i ( 2 0 0 2 ) l 憎j 给出了有线路运行时 间约束的m d v s 问题的0 1 规划模型和算法。在他们的模型中，将车次根据发车时间 的不同分成三个集合：上午班次( m o r n i n gt r i p s ) ，中午班次( m i