（管理科学与工程专业论文）基于公交ic卡调查数据的公交调度优化研究.pdf

大连理工大学硕士学位论文 摘要 当前我国城市交通问题日益凸现，主要表现为交通拥堵现象极为普遍、城市交通污 染曰益严重等等。大力发展公共交通、提高公交在居民出行中的比例是有效的解决手段 之一。而公交调度是公交企业运营管理的核心内容，实现公交调度智能化和调度方案的 最优化是提高运营调度水平、增强公交吸引力的关键。 公交客流数据是制定和优化公交调度的前提和基础。本文分析了既往公交i c 卡数 据的规律和特点，取得了公交i c 卡的历史数据得到客流曲线，采用f i s h e r 有序聚类算法 划分公交峰值区间，从而建立了不同峰值情况下公交i c 卡数据预测时段客流的回归方 程，为公交调度提供基础数据。 公交车辆的线路调度是公交调度的基本模式。本文提出了以乘客满意率和企业满意 率加权平均值最大作为目标，考虑最大和最小发车间隔、满载率等约束，以发车时间为 变量的公交车辆优化调度模型。该模型能够计算出优化的公交车辆全天发车时刻表，同 时可以利用公交i c 卡数据的高效性和实时性，应对客流变化快速对时刻表做出有效调 整，从而实现智能化的目标。 公交车辆优化调度模型的求解是解决公交调度实际问题的关键。由于该模型是多变 量的非线性问题，用传统方法难以求解，为此本文将免疫算法引入到模型求解中，给出 了免疫算法应用于求解公交车辆优化调度问题的基本步骤和具体计算过程。 本文最后将公交优化调度模型具体应用于大连市4 0 6 公交线路，得出了优化的调度 方案。结果表明，该模型和算法得到的优化发车间隔满足客流增长趋势，并且相邻峰值 区间发车也很平均，优化了现有的调度方案并具有快速智能化反应能力。 关键词：公交i c 卡；公交调度；公交客流；免疫算法；数据处理 基于公交犯卡调查数据的公交调度优化研究 o p t i m i z a t i o no f b u ss c h e d u l i n gb a s e do ni n t e g a t e dc i r c u i t ( i c ) c a r d s u r v e y i n gd a t a a b s t r a c t u r b a nt r a n s p o r tp r o b l e m sa r em o r ea n dm o r es e r i o t i si no u rc o u n t r y i ts h o w sa sf o l l o w s ： 仃a 舶cc o n g e s t i o na n dt r a f f i cp o l l u t i o n n 峙e f f i c i e n tw a yt os o l v et h e mi sd e v e l o p i n gp u b l i c t r a n s p o r tg r e a t l ya n dr a i s i n gt h ep r o p o r t i o no ft r i pb yb u s f o rt h eb u ss c h e d u l i n gi sv i t a lf o r p u b l i ct r a n s p o r tm a n a g e m e n t ，w ec a r lc o n c l u d et h a ti m p l e m e mo nt h ei n t e l l i g e n tp u b l i c t r a n s p o r t a t i o na n dr e s e a r c ho nb u ss c h e d u l i n go p t i m i z a t i o nm e t h o d si sv e r yi m p o r t a n tt o i m p r o v et h eq u a l i t yo fb u ss c h e d u l i n gm a n a g e m e n ta n d t oe n h a n c et h ea t t r a c t i o no ft r i pb y b u s n l ep a s s e n g e rd a t ai st h eb a s eo fb u ss c h e d u l i n g t i l i sa r t i c l eh a sa n a l y z e dt h e c h a r a c t e r i s t i co fi cc a r dd a t a t h ec u r v eo ft h ep 髂啪g 盯f l o wv o l u m ei so b t a i n e du s i n gi c c a r dh i s t o r i c a ld a t aa n di so p t i m i z e do nb o t ho ft h en u m b e ra n di n t e r v a lo ft r a n s i tp e a kv a l u e c l t r v eu s i n gf i s h e r ss e q u e i l c ec l u s t e r i n gm e t h o d t h e n ，t h er e g r e s s i o ne q u a t i o n so f p r e d i c t i n g t h ep a s s e n g e rf l o wv o l u m eb yi cc a r dd a t aa r ee s t a b l i s h e di no r d e rt op r o v i d et h eb a s ed a t a f o rb u ss c h e d u l i n g v e h i c l el i n es c h e d u l i n gi st h eb a s em o d ei nb u ss c h e d u l i n g n l i sp a p e rp r e s e n t sab u s s c h e d u l i n go p t i m i s t i cm o d e lw i t hs c h e d u l i n gt i m e a sv a r i a b l e t h em o d e la i m s 缸t h e m a x i m u mo f s a t i s f a c t i o no f p u s s e n g e rw a i t i n gt i m ea n db u sc o m p a n yi n c o m e ，a n ds u b j e c t st o t h em a x i m u ma n dm i n i m u ms c h e a u l i n gi n t e r v a l ，t h ef u l l - i o a dr a t e i nt h em o d e i ，t i m e t a b l e c a nb eo b t a i n e da n da d j u s t e da c c o r d i n gt op a s s e n g e rf l o wv o l u m et h r o u g ht h ee f f i c i e n ta n d c o n v e n i e n ti cc a r dd a t ai nas h o r tt i m e b u ss c h e d u l i n go p t i m i s t i cm o d e li sam u t i - v a r i a b l ea n dn o n l i n e a rp r o b l e ma n dc a nn o t b es o l v e db yt r a d i t i o n a lm e t h o d s t l l i sp a p e r1 1 s e st h ei n n n u n ea l g o r i t h mt os o l v et h em o d e l a n dp r e s e n t st h ep r o c e s so f a l g o r i t h mo nb u ss c h e d u l i n g i nt h ee n d ，t h em o d e la n da l g o r i t h mi sv a l i d a t e db yt h es c h e d u l i n gd a t ao f n o 4 0 6 ，t h e b u sd e m o n s t r a t i o nr o u t eo f d a l i a n k e yw o r d s ：i n t e l l i g e n tc a r d ；b u ss c h e d u l i n g ；p a s s e n g e rd a t a ；i n l m n n ea l g o r i t h m ：d a t a p r o c e s s i n g i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 ，删) 磊 作者签名：熏三叁 日期：鱼墅呈! 兰 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 缸茏 上吐年月4 日 大连理工大学硕士学位论文 1绪论 1 1 研究背景与意义 1 1 1 研究背景 随着国民经济的迅猛发展和城市化、机动化进程的加快，城市规模不断扩大，机动 车保有量急剧增加，道路交通流量日趋饱和，特别是大城市，交通问题日益突出。面对 出现的这些交通问题，直接的解决办法是通过修建更多的道路来提高路网的通行能力， 但是由于城市中可供修建道路的空间有限，交通设施建设的步伐远远跟不上交通需求的 增长速度，交通拥挤现象仍然非常严重。国内外对城市交通开展了多年研究，研究经验 表明，发展城市公共交通，努力提高城市交通的信息化水平，建立先进的公共交通系统 a p t s ( a d v a n c e dp u b l i et r a n f f i cs y s t e m ) ，提高公交运营部门的管理水平，实现公交调 度智能化，是解决城市交通问题的有效途径【l d l 。 公共交通是指维持社会上多数市民的日常生活和活动，可以公用，而且具有平等性 的交通服务。视其服务内容可划分为：公共客运交通、公共货运交通、社会服务交通； 按交通方式可区分为；轨道交通、公共汽车交通、行人传送带交通等。而在城市里公共 汽车交通中起主要作用通常是客运交通。它与人们的生活息息相关，为广大的城市居民 提供基本的出行保障。公共交通系统具有运量大、运送效率高、能源消耗低、相对污染 少、运输成本低等优点。 公交车辆的运营调度工作是公交企业的核心基础工作。它是根据客流的变化和具体 营运条件及其它条件，安排不同车型的车辆和行车的组织方案。改善公交运营调度水平 就是改善公交服务水平。公交运营调度工作的好坏直接影响公交企业的形象和经济效 益。可以说改善公交运营调度工作是公交企业永恒的主题。 目前，我国的公共交通事业发展还比较落后，公交智能化水平还比较低，绝大部分 是旧的运营体制。现行的公交企业运营调度管理工作有很多问题：调度管理主要依靠人 力，运营计划主要依靠调度管理人员凭经验制定，总体方法落后。此外，传统公交调度 数据往往依靠城市居民出行调查，公交线路随车调查，站点换乘调查等。调查方法已经 较成熟，完善，只是耗费巨大人力、物力，取得数据的成本过高，且数据处理工作量大、 周期长、不精确，导致规划结果与实际情况出入过大，不利于实施。正是由于上面提到 的原因，导致了公交运营效率低、服务质量差，从而使乘客选择公交出行方式的比例不 高。克服上述问题的关键，就是建立切实可行的公交优先发展体系，实现公交调度管理 的智能化，而这些都离不开相应理论的研究和技术的支持。 基于公交i c 卡调查数据的公交调度优化研究 本论文结合大连市交通局科技项目“大连市智能公共交通系统专项规划”，提 出了利用公交i c 卡数据进行公交车辆的调度，从数据处理、线路调度优化模型及求解 算法等方面进行了研究，为公交企业进行科学的运营决策提供理论依据和技术支持，保 障城市交通的协调、有序和高效发展。 1 1 2 研究意义 应用公交i c 卡数据进行公交优化调度的意义有如下几个方面： ( 1 ) 增强调度的时效性，使公交企业更及时准确的进行公交车辆调度满足乘客需求， 实现公交调度智能化。公交i c 卡的数据每天从数据库中采集，较传统数据更加便捷迅 速，且不受天气等因素的影响，可以更客观地反映乘客乘车情况。而传统的调查数据存 在很大的时间局限性，往往经过几个月调查得到的数据，经过一段时间如城市人口结构、 生活水平、社会的经济政治发生比较大的变化后便无法客观的反映出公交乘客的需求变 化，无法继续应用于公交调度。 ( 2 ) 节约调度数据的调查费用成本。传统的公交调查，往往需要耗费大量的人力和 财力。例如，为了得到某一条线路的客流情况，往往需要在每个月连续几天内的不同时 段安排多名随车人员，跟随车辆统计每一站的上下车人数。对于问卷调查还需要对调查 员进行相关知识的培训。如果是对交通区域或者城市内的多条公交线路规划和调度，累 加起来的调查费用非常昂贵。相比之下，公交i c 卡数据的采集要简单的多，只需要从 数据库中提取需要的数据经过处理，代入优化模型求解，结果就可以在以后的调度中使 用。 ( 3 1 制定更加合理、科学的公交车辆调度安排，有效地节约公交公司的运营成本， 同时满足乘客公交出行的需求，节省乘客的候车时间及降低公交车辆高峰时段的拥挤 度，增加乘客的舒适性。 1 2 国内外研究现状 国内外有许多学者致力于城市公共交通调度方法的研究。 国外对于公交调度的研究起步较早，在理论和应用上都很深入。f u r t h 和w i l s o n 在 1 9 8 1 年就提出了利用数学规划的方法确定发车的频率和行车时间表。文章中目标函数考 虑的因素有网络社会效益和乘客等待时间，并将公交补贴，车辆型号，乘客特点作为约 束条件加以考虑【4 】。此后，k o u t s o p o u l s 等人将模型扩展，加入了乘客拥挤度的概念，同 时考虑了公交调度中时间的相关性。并将非线性规划近似表示成线性规划加以求解狰l 。 大连理工大学硕士学位论文 c e d c r 和t a l 等人采用混合整数规划来构造可换乘公交网络的发车时间表。模型以 满足车辆在换乘站点最大程度时间同步为目标，节约乘客等待时间，并利用启发式程序 求解模型1 6 。 随着对问题研究的不断深入，人们将公交调度中的复杂情况考虑在内。p a r t h a c h k r o b o r t y 建立了基于候车时间和换乘时间之和最小的公交调度模型。作者将一个换乘 站点的公交车调度问题归结为一个数学规划问题，指出这是一个非线性的n - p 问题，并 采用遗传算法对公交调度问题进行求解 7 1 。 随着技术的不断进步，学者们提出了更多的研究方法。d e s s o u k y 等人将公共交通采 用的通讯、跟踪、乘客计数等技术与公交站点内信息收集技术做了比较，并提出了一种 预测公交车辆到达时问的新方法，该方法可以准确地预测长发车间隔时间情况下的公交 车辆到达信剧“。 o m a rm e k k a o u i 等人提出了“乘客期望到达时间”这一概念，解决了给定发车时刻 表条件下的单条公交线路的发车频率优化问题【9 l 。 在国内，近年来也有很多相关研究成果出现。西安交通大学孙芙灵根据西安市公交 公司客流调查数据，引入时段配车数的概念，探讨了不同客流状态下确定时段配车数和 发车间隔的方法【1 0 】。东南大学程杰等人针对目前已有发车间隔计算模型计算过于复杂， 无法反映公交服务水平等，在充分分析时段内的公交线路客流规律的基础上，得出了 基于期望满足概率的公交车发车间隔计算模型 i l l 。西安电子科技大学薄立军等人建立的 模型基于随机服务系统，主要利用了g y m n 排队系统的平均队长及平均等待时间等基 本公式。但单交通线上的公交车具有串联服务的性质，这与g i m n 系统不大符合【l z j 。 四川大学傅昌建等以公司利益作为目标函数，以概率描述的乘客利益作为约束条件，建 立了完整的理论模型【l “。 通过对国内外文献的收集，可以看到研究多集中在对车辆的静态调度方面。采用的 方法多是数学解析法、模拟仿真方法、数学规划( 分支定界法、割平面法、动态规划少、 概率方法以及经验模型等) 。随着问题计算复杂性及问题规模的扩大，传统方法遇到了 很大的困难，而且得不到精确的解。目前正采用运用一些非数值并行搜索方法一遗传算 法o a ( g e n e t i ca l g o r i t h m ) ，禁忌搜索t v ( t a b us e a r c h ) 和模拟退火s a ( s i m u l a t e d a n n e a l i n g ) 等进行调度优化问题的研究。武汉理工大学朱金寿等应用遗传算法进行公交 调度的求解，并在仿真过程中，设计了杂交和变异算子，得到了较优的结果1 1 4 j 。另外， 随着对公交智能化要求的提高，开始考虑动态实时调度。清华大学胡坚明和吉林大学杨 兆升等将实时调度形式的确定理解为一种模式识别问题，基于逐步回归分析的方法预测 公交站点客流集散量，其次提出广义回归神经网络方法预测站点间运行时间并给出基于 基于公交i c 卡调查数据的公交调度优化研究 b p 神经网络的公交车辆实时调度形式的确定方法1 ”。这些研究都处于探索阶段，需要 进一步的深化。 1 3 研究内容与框架 1 3 1 研究内容 虽然公交i c 卡数据中包含很多有用的公交信息，例如刷卡时间信息、车辆信息、 线路信息等等，但是也存在局限，比如数据中不包含乘客的刷卡站点、乘客的下车站点 等对于调度非常重要的客流信息，这使得通常的公交调度模型无法直接利用公交i c 卡 数据库的数据。因此，本文建立了基于时段客流的公交车辆调度优化模型。首先，利用 公交i c 卡的刷卡数据结合线路调查得到时段客流数据，然后使用免疫算法对优化模型 求解得到线路的发车时刻表。本文的主要工作有以下几点： ( 1 ) 客流峰值区间确定及预测客流回归方程建立 峰值区间的确定对于公交调度非常重要，不同的客流高峰平峰区间采用不同的调度 方案。本文提出了利用公交i c 卡的历史数据得到客流曲线，并采用f i s h e r 有序聚类算 法划分公交峰值区间，建立了不同峰值情况下公交i c 卡数据预测时段客流的回归方程， 为调度优化模型提供数据。另外，通过聚类可以在具有典型特征的峰值区间内有针对性 的进行调查，得到更加有效的样本，减少调查的时间和投入的人力。 ( 2 ) 基于公交i c 卡数据的公交优化调度模型 本文建立以发车时间为变量的公交车辆优化调度模型。该模型提出了以乘客满意率 和企业满意率加权平均值最大作为目标，考虑最大和最小发车间隔、满载率等约束。该 模型能够计算出优化的公交车辆全天发车时刻表，同时可以利用公交i c 卡数据的高效 性和实时性，应对客流变化快速对时刻表做出有效调整，从而实现智能化的目标。 ( 3 ) 利用免疫算法求解模型 由于车辆优化调度属于n p 问题，直接求解非常困难。在求解车辆调度问题时，传 统的理论方法多采用数学解析法、模拟仿真方法、数学规划( 分支定界法、割平面法、 动态规划少、概率方法以及经验模型等) 。随着问题计算复杂性及问题规模的扩大，传 统方法遇到了很大的困难，而且得不到精确的解。而免疫算法在求解类似问题时，可以 很好的克服上述的一些缺点。因此。本文建立了基于免疫算法的公交优化模型求解算法， 得到了问题的优化解。 大连理工大学硕士学位论文 1 3 2 论文框架 各章内容安排如下： 第一章绪论 介绍本文的研究背景及研究意义，分析国内外公交优化调度的研究现状，引出了本 文的研究主题和研究内容。 第二章公交数据采集分析 介绍公交i c 卡数据的特点，公交调查数据的采集分析。建立公交i c 卡数据预测时 段上车和在车客流的回归方程。 第三章公交车辆调度优化模型。 介绍公交车辆调度的相关概念，并建立公交车辆发车间隔优化模型。该模型可以采 用公交i c 卡数据预测得到的时段客流数据，求出各个时段的发车间隔，进而求出全天 的发车时刻表。 第四章基于免疫算法的优化模型求解： 将优化模型化为免疫算法可求解的框架，定义亲和力函数和解浓度函数；定义遗传 算子，如交叉、变异等准则等。针对大连市4 0 6 公交线路实例求解，得到了全天的发车 时刻表，并对结果进行分析评价，论证了模型算法的有效性。 最后总结了论文的主要工作和结论，对将来的研究工作进行展望，提出了进一步的 研究方向。 基于公交1 c 卡调查数据的公交调度优化研究 2 公交数据的采集分析 公交客流信息作为城市公共交通规划方案和运营决策的依据，规划者和管理者一直 致力于获取准确反映公交运营状况的客流信息。公交乘客是公共交通客流组成的基本要 素，公交i c 卡数据库记录了每一个公交乘客任何一次刷卡的相关信息，从这些信息中 挖掘出的反映公交运营状况的数据是可行的。公交i c 卡在国内许多城市都有应用，很 多大中城市持卡乘客比例达到4 0 以上。公交i c 卡信息量所反映的居民公交出行的数 量及分布完全达到调查样本数量和特征的要求，与人工调查方法相比，公交i c 卡信息 不容易受人为因素的影响，数据准确真实时效性强，更加经济，得到的客流结果更能 真实反映城市公交运营情况和居民公交出行特征。在本章将对公交i c 卡数据特点进行 介绍和分析，并提出具体的方法对公交i c 卡数据处理，建立预测时段客流的回归方程。 2 1 公交i c 卡数据分析处理 2 1 1 公交l c 卡系统组成 ( 1 ) 公交i c 卡的结构 公交l c 卡又称智能卡。它将大规模集成电路封装在外观3 4 0 x 2 5 0 r a m 的塑料卡内， 具有反复存取加密数据的功能。卡内天线能够为卡内的集成电路芯片获取足够电能，完 成相关数据的无线发送和接收【。 集成电路芯片能够按指令发送和接收数据；能够对数据进行加密、解密，进行运算、 存储。集成电路能将天线接收的能量转化为供芯片本身使用的稳定电能，而无需电池维 持工作。 塑料卡将天线、集成电路芯片封装，起到保护作用。非接触式i c 卡可以反复充值， 重复使用。使用寿命高达1 0 万次，本文研究的是大连明珠智能公交i c 卡，见图2 1 。 6 - 大连理t 大学硕士学位论文 图2 i 公交i c 卡图片 f i g 2 1 t r a n s i tl cc a r dp h o t o g r a p h ( 2 1 公交i c 卡系统组成 公交i c 卡系统包括车载收费机、数据采集盒、充值机、服务器、工作站等设备。 下面仅对车载收费机和数据采集盒做简要介绍。 车载收费机：车载收费机放置在公交车内，固定在公交车入口的栏杆上。主要作用 是：识别i c 卡；按照预定车票价格扣除1 c 卡中预存金额；存储相应的i c 卡交易数据。 数据采集盒：由公交公司的管理人员保管，它是车载收费机与数据采集分中心进行 数据交换的存储设备。主要有以下作用： 将车载收费机的数据采集出来，并转移到计算机系统中。 将系统发布的“禁止交易清单”( 即：黑名单) 传入车载收费机。 每个数据采集盒大约可以采集3 0 台车载收费机的数据。采集数据时，管理人员将 数据采集盒插入车载收费机后，数据采集盒将自动进行工作，采集时间约l o 分钟。车 载收费机盒数据采集盒如图2 2 所示l l ”。 基于公交l c 卡调查数据的公交调度优化研究 图2 2 车载收费机盒、数据采集盒 f i g 2 2 t o l lc o l l e c t o r0 i ib o a r da n dd a t ac o l l e c t o r ( 3 ) 公交i c 数据采集流程 为获得收费系统内每台车载收费机每天的实际收入，并向每台车载收费机传送“禁 止交易清单”，公交i c 卡管理中心要求各个数据采集中心每天都要将各个车载收费机 当天发生的交易记录传递到公交i c 卡管理中心，进行相应的数据更新。i c 卡记录由车 载收费机产生，最终汇总到i c 卡管理中心。整个公交i c 卡数据采集流程，如图2 3 所 示； i c 卡记录的产生。乘客进入公共汽车后，划卡缴费；车载收费机将在划卡的短 暂时间内，完成i c 卡身份识别、对i c 进行减法操作，同时记录该卡卡号和划卡时间。 数据传递过程。工作人员通过数据采集盒，将公交i c 卡记录导入到数据采集盒 内，再将其导出到数据采集分中心的计算机中。 公交i c 卡数据的接收。数据采集分中心将公交i c 卡数据以数据通信方式，传 送到i c 卡管理中心，同时下载i c 卡管理中心传送来的“禁止交易清单”等数据。对于 “禁止交易清单”所列出的i c 卡号，公交车上的车载收费机将不与它执行交易。 一8 一 大连理工大学硕士学位论文 图2 3 公交i c 卡数据采集流程 f i g 2 3 t r a n s i ti cc a r dd a t ac o l l e c t i n gf l o wd i a g r a m ( 4 ) 公交i c 卡的数据结构 大连明珠公交i c 卡内乘客一条刷卡记录包含如下信息：结算中心代码、用户卡号 码、线路代码、车载机代码、车辆代码、用户卡类型、消费日期、消费时间、交易金额、 司机卡代码。表2 1 列出一些刷卡记录。 由于数据量较大，只需对论文需要的数据字段，乘客卡号、上车日期、上车时间、 线路号、司机卡号提取，放入数据库中。在提取过程中，需要对一些再刷卡过程中产生 的破损、冗余记录进行清除。 最后，得到如表2 2 的数据表。 基于公交i c 卡调查数据的公交调度优化研究 8 6 0 0 0 0 1 1 6 0 0 1 0 0 0 0 2 5 0 92 6 8 6 0 0 0 0 1 1 6 0 0 1 0 0 9 f 9 a 8 71 3 8 6 0 0 0 0 1 1 6 0 0 1 0 0 9 9 2 d 3 66 0 2 8 6 0 0 0 0 1 1 6 0 0 1 0 0 0 7 d d 3 92 4 8 6 0 0 0 0 11 6 0 0 1 0 0 0 7 d d 3 9 2 4 1 0 9 6 1 2 5 8 】2 4 4 1 5 5 6 1 5 5 6 o 1 1 1 2 3 8 0 7 3 9 1 7 0 9 3 2 0 6 1 9 1 8 0 0 1 9 1 8 0 2 4 3 6 5 6 1 6 3 4 9 0 7 5 0 9 5 5 0 9 5 oo 2 1 2 公交i c 卡乘客出行时间分布 如果能够获得不同时间段的居民需求变化的具体值，公交公司的调度人员就能充分 利用现有的公共运输资源，最大程度地满足区域内的居民出行需求。 为了显示居民对某条公交线路需求的分时段变化，以大连市公交4 0 6 路车为研究对 象，通过对该线路全天发生的公交i c 卡记录进行整理。仍以公交i c 卡记录发生时间为 横坐标( 单位3 0 分钟) ，以刷卡人数为纵坐标( 单位人) ，得到全天的持卡居民公交 出行分布图，见图2 6 和图2 7 。 图2 6 表示2 0 0 6 年3 月份工作日的平均客流情况，公交4 0 6 线路的持卡乘客高峰 有两个：2 4 2 7 人( 7 ：0 0 8 ：0 0 ) 和1 9 8 0 人( 1 6 ：3 0 1 7 ：3 0 ) 。这两个时段分别是上 o o o o 0鲫姗瑚抛枷瑚 大连理工大学硕士学位论文 班时段和下班时段。从9 ：0 0 1 6 ：o o ，为持卡乘客平峰时段，客流量在1 0 0 0 人左右。 从图中可以注意到早晨和晚上客流的趋势有明显的不同，早晨客流增加较快，而晚间高 峰过后，客流量逐渐的减少，这主要是因为人们在早晨主要出行目的是上班，时间较短， 比较集中。而人们在下班后还会有一些其它的活动，比如购物、娱乐、访友等等，并不 会立刻呆在家中不再出行。 图2 7 表示2 0 0 6 年3 月份非工作日的平均客流情况，图中没有明显的高峰时段， 从7 ：3 0 之后持卡乘客开始增加，高峰出现在1 0 ：0 0 ，达到1 2 0 3 人。并在一天的大部 分时段保持稳定，直到晚上的2 0 ：0 0 之后逐渐减少。 从工作日和非工作日客流的对比可以得到如下结论： ( 1 ) 客流高峰时间差异较大。工作日在早晨上班时间形成和下班时间形成高峰时段。 而非工作日，由于一周的劳累，以及商店开业时间较迟，所以客流高峰时段产生较晚， 并且不明显。 ( 2 ) 客流量变化，非工作日客流量比工作日流量有较大幅度减少。 ( 3 ) 非工作日客流全天变化缓慢，客流较分散，不会出现工作日那样集中的客流。 3 0 0 0 2 5 0 0 2 0 薹，啪 1 0 0 0 5 0 矿，矿，歹，矿矿矿矿 图2 6 大连市4 0 6 路公交车工作日公交i c 卡客流 f i g 2 6 p 嬲s e l l g e rf l o wo f t r a n s i ti cc a r do f b u s4 0 6i nw e e k d a yo f d a l i 卸 基于公交i c 卡调查数据的公交调度优化研究 嚣 之 图2 7 大连市4 0 6 路公交车非工作日公交i c 卡客流 f i g 2 7p a s s e n g e rf l o wo f t r a n s i ti cc a r do f b u s4 0 6i nw e e k e n do f d a l i a n 2 2 客流峰值聚类分析 公交线路上不同时段公交客流有高有低，客流量较高的时段被称为高峰时段。有效 的划分不同峰值时段对于车辆的优化调度有重要的意义。线路调度人员在制定线路配车 计划时，最为重要的依据是线路客流的每日时段分布曲线。调度人员在制定计划时往往 根据经验将其划分为若干峰值区间，例如早高峰、高峰、平峰等。所谓平峰是指在早、 晚两个高峰之间客流较为平稳的时段。然后调度人员根据各峰值区间的客流配置车辆。 调度人员进行这样的峰值划分主要基于以下2 个原因： 对于客流大小相似而且相邻的时段配置相同的运力； 划分为若干峰值区间，便于进行驾乘人员的班次安排【l 观。 本文的工作是利用以往的公交i c 卡数据分析客流特点，通过聚类算法划分客流峰 值区间。基本思路：从数据库中提取计划调查同期的公交i c 卡刷卡记录，绘制全天的 线路公交上车客流曲线分布图。利用聚类算法对全天的不同时段客流划分归类，得到若 干峰值区间。根据峰值区间，一方面可以确定调查的时间段和跟车安排，节省调查的人 力和时间消耗，得到较好的调查效果。另一方面，由于公交线路上出行有一定的规律性。 反映在不同的时段上，就是客流量有一定的规律变化，且公交i c 卡乘客量与总的乘客 量存在一定的相应关系。通过确定峰值区间，在利用回归分析的方法，找到区间内公交 i c 卡乘客量与总的客流量的数学表达式，从而在日后利用公交i c 卡数据库获取公交i c 卡时段客流，预测该时段内的总的客流量，达到客流量实时预测的目的。 大连理工大学硕士学位论文 2 2 1 公交客流峰值聚类提出 公交峰值优化的过程是根据一定的规则，将客流相似的相邻时段进行归并，从而得 到不同的峰值区间，这一过程实际上是有序样本的聚类问题。 所谓有序样品是指，样品按照一定的要求排成序，分类时不能打破这种次序设x 。， x 2 ，x n 表示一组有序的样品，则每一类必须呈 & ，x i + l ，。玛 ( i j ) 形态。n 个有 序样品分成k 类的一切可能分法有础种。这个数比饼要小得多。因此在某种损失函 数下，有可能求得最优解。 本文对公交峰值区间的划分可以采用f i s h e r 算法。f i s h e r 算法( 即最优分割法) ，这 种算法考虑了分割方案的整体最优性，从数据拟合的角度讲，f i s h e r 方法实质上是对所 给数据用样本的剩余平方和定义类直径，通过使拟合精度达到最高确定最优分段【l 蚍n 。 2 2 。2 公交客流量峰值区间划分模型的建立 设时间点值依次为x i ，x 2 ，x n ，不同时段客流量依次是y l ，y 2 ，y n ，其中 x i x 2 x n 。 某种分法下峰值区间中的每一段表示为。 在进行车辆调度时，调度员要根据时段客流安排车辆，因此可以定义各段客流量样 本点到平均客流量的距离为类直径。 用d ( i ，j ) 表示段g , j = f ，f + l ，力的类直径，如下定义： 图在正文中的格式示例如图2 1 所示。 d ( j ，d = 窆幻一一y v y ( 2 1 ) 其中，歹2 7 三百喜，a j = i ，i + l 时，d ( i ，j 户钆 定义误差函数：设n 个时间点分成k 个区间段，设某一种分法是 p ( n ，k 产 i l ，i 1 + 1 ，i 2 1 ) ， i 2 ，i 3 - 1 ) ， i k ，n 其中分点1 = i z t “= 拧。 定义该分段方案的误差函数为 e p ( n ，七) 】= d ( i ，一1 ) ( 2 2 ) j = l e p ( n ，2 ) 】= d ( 1 ，j 1 ) + d ( j ，n ) ( 2 3 ) e p ( n ，七) 】= e p ( j 1 ，k 1 ) 1 + d ( j ，h ) ( 2 4 ) 基于公交i c 卡调查数据的公交调度优化研究 求最优k 分段：对给定的分段数k ，我们在所有可能的分段方案p ( n ，k ) 中找出使 e p ( n ，k ) 】达到极小者作为最优k 分段，记为矿( n ，k ) 。 欲分成k 段时，先找j k 使( 2 4 ) 达到极小，即 e i p + ( 栉，七) 】= m ! n e p + ( 五一1 ，k 一1 ) + d ( ，胛) ) ， 】， 于是得到第k 类q = 以， + 1 ，栉 。然后找j 使它满足 e p + ( 五一l ，k - 1 ) 1 = e t p 4 魄1 1 ，_ | 一2 ) 1 + d ( 1 ，j k 一1 ) 得到第k - 1 类g i 。= z m a x 。因为z m a x 为所求的调度总效用最大，即 目标函数的最优解，有z m a x l ，所以z 的值可以取1 。z i 是模型的目标值，当z i 与z 越接近，亲和力越大，表明对应的鼹越好。 计算初始群体的与抗原的亲和力，按照降序排列。将前n 1 个与记忆库中的个体比较， 将亲和力低的个体从记忆库移出，并将高亲和力个体放入记忆库储存，保证记忆库中始 终有最高亲和力的n 1 个个体。 抗体与抗体的亲和力：用于表明两抗体之间的相似度。本文采用上一节介绍的基于 信息熵的抗体间亲和力表示方法。 a 一删6 叻。t 而鬲 ( 4 脚) 其中，h ( 2 ) 表示抗体i 和j 的信息熵，也可理解为不相似度，值越大抗体间的亲和 力aa n t i b o d y l j 就越小。 解的浓度表示： c 。= 谚z ( 4 2 i ) 其中，咖钒= 话当a 一絮沪，仇为预先确定的抗体亲和力阈值。阈 值是免疫算法基于比率选择操作的个重要参数，它与变异率配合，有效的保证群体的 多样性，防止过程陷入个别极值。对于阌值的选取，不宜过大，太大该阈值的限制作用 失效，则搜索过程容易陷入几个适应较大的峰值；当然值也不宜过小，太小将使抗体与 抗原间亲和力对期望繁殖率的作用削弱。导致搜索过程难以找到最优。本文的阈值参考 文【5 3 并经过计算取o 7 。 抗体的期望繁殖率： e j = 1 2 + a a n t i g e n i + ( 1 - 口) ( 1 - c i ) ( 4 2 2 ) 其中，a 为一个比例系数o a 1 。在计算最优解之前，对a 分别取0 1 到0 ，9 九个数值，通过较少迭代步数观察收敛情况。最后，确定q = o 5 算法收敛效果最好。 将初始群体按照期望繁殖率e i 的大小采用降序排列，取前n 个个体构成父代群体。 这表明了高亲和力抗体受到促进，而高浓度抗体受到抑制。 4 2 4 群体更新操作及结果控制 ( 1 ) 选择操作 基于公交i c 卡调查数据的公交调度优化研究 选择是以群体中的每个个体的期望繁殖率的大小分配繁殖机会，期望繁殖率大的个 体，繁殖机会高，期望繁殖率小的个体受到抑制甚至被淘汰。这里采用基于排序的期望 繁殖率分配和轮盘选择法。分为两步：第一步是计算选择概率，选择概率计算方法的基 本思路是把种群中的个体按照目标值升序排列。假设某个个体期望繁殖率的序位为i ， 则被选取的概率由( 4 2 3 ) 计算，其中s i z e 是参加选择的个体数量 z = 三l( 4 2 3 ) q j 1 1 第二步是选择的方法，选择方法采用轮盘法，随机确定被选个体。具体步骤如下： s t e p l ；对每个抗体体i 。利用( 4 2 3 ) 计算其期望繁殖率概率毛； s t e p 2 ：对每个抗体i 计算，利用( 4 2 4 ) 计算其累积适应概率 f q = 乃 ( 4 2 4 ) 1 - 1 s t e p 3 ：从区间( o ，l 】中产生随机数r ； s t e p 4 ：若q i 1 r q ，则选择第i 个抗体，( 1 i s i z e ) ； s n 弹5 ：重复s t e p 3 和s t e p 4 共s i z e 次，这样就可以得到s i z e 个抗体。 ( 2 ) 交叉操作 交叉算子根据交叉率p e r o s s 将种群中的两个个体随机地交换某些基因，能够产生新 的基因组合，期望将有益基因组合在一起。常用的交叉算子有单点交叉、两点交叉、多 点交叉和均匀交叉等，这里选用单点交叉。 交叉后产生的新个体同样要进行检验，看是否满足约束条件一，满足进入下一代种 群，不满足则重新进行交叉操作，在一定次数要求内达到了约束条件的要求，进入下 代种群，否则原来的两个抗体进入下一代种群。 交叉操作还有个交叉率的选取问题，交叉率的选取决定了交叉操作的频率越高，可 以越快的收敛到最有希望的最优解区域，因此一般选取较大的交叉率，但是太高的交叉 率可能导致过早的收敛，一般取值0 禾o 9 。这里取为0 6 ，即p a c r o s s = ) 6 。 对于交叉后产生的新抗体，根据一组发车间隔排序，与时段对应。另外，调整后计 算是否满足约束条件，如果不满足重新交叉，当交叉次数大于1 0 次时取交叉前抗体作 为结果。 ( 3 ) 变异操作 大连理工大学硕士学位论文 变异算子是以一定的变异率p m u t a t i o n 从群体中选取个体，对于选中的个体进行翻 转变异和交换变异，以增加抗体的多样性。同样变异后产生的新个体也要接受约束条件 的检验。这里变异算子选为翻转变异。 同样，变异操作也存在一个变异率的选取问题。变异率的选取一般受种群大小、抗 体长度等因素的影响，通常选取很小的值，一般取0 0 0 1 0 1 。这里选取p m u t a t i o n = o 0 1 。 对于变异后产生的新抗体，根据一组发车间隔排序，与时段对应。另外，调整后计 算是否满足约束条件，如果不满足重新变异，当变异次数大于1 0 次时取变异前抗体作 为结果。 “) 终止条件 终止条件是采用固定的迭代次数。对于最优解的判定采用将程序运行2 0 次，在2 0 次中最大解重复出现次数达到2 0 ，就说明最优解的有效性。比如：程序运行2 0 次， 最大的值是0 8 1 2 2 。这个解重复出现了4 次，就说明这个解是最优解。 ( 5 ) 结果输出 得到操作终止时的最优抗体。 最优发车间隔 最优发车阗隔t k 由最优抗体解码得到，其中对应关系如下：发车间隔用3 位二进制 数表示，抗体的长度3 k ，每3 位二进制数对应一个时段的发车问隔缸。得到最优抗体 后，利用公式( 4 1 6 ) ，( 4 1 7 ) 可以计算最优发车间隔。 最优发车时刻表 最优发车时刻表由各时段的起止时间和最优发车间隔得到。 各时段配车 根据发车时刻表可以确定各时段的配车数量。 4 2 5 免疫算法程序框架 s t e p 0 初始化； s t e p l ：根据编码规则，随机产生n 个抗体，并从记忆库中提取m 个个体构成初始 群体； s t e p 2 ；对上述群体中抗体计算抗原的亲和力，并按照降序排列，取前m 个与记忆 库中抗体比较，将亲和力大的个体放入记忆库，将亲和力小的个体从记忆库中剔出； s t e p 3 ：对群体根据期望繁殖率进行评价，将初始种群按照e i 的降序排列，取前1 1 个个体构成父代群体。 s t e p 4 ：判断是否满足结束条件，是，则结束；否，则继续下一步； 基于公交i c 卡调查数据的公交调度优化研究 s t e p 5 ：新群体的产生：基于第3 步的计算结果对抗体群体按轮盘法选择，经过选 择的个体进行交叉，最后再按照一定变异率变异。得到新的群体。从记忆库中取出记忆 的个体，共同构成新一代的群体； s t e p 6 ：转去s t e p 2 。 4 3 实例验证 4 3 1 输入数据 ( 1 ) 客流数据 模型数据需要的客流数据来自