（控制理论与控制工程专业论文）模糊多目标规划在公交优化调度中的应用.pdf

摘要 模糊多目标规划是一种重要的优化方法，可以有效地解决众多复杂的实际问题。本 文在模糊多目标规划的建模、求解及其在公交优化调度的应用中都做了一定的研究。 公共交通是城市交通的重要组成部分。城市要进行现代化，尤其完善城市功能，离 不开城市交通的优化和提高。合理的公交调度，可以有效地缓解运力和运量的矛盾，最 大限度地平衡乘客和公交公司之间的利益。公交调度优化可以降低乘客的出行成本，改 善市民的环境，另一方面也可以增加公交车辆的运行效率，提高公交公司的经济效益和 社会效益。 提高公共交通服务的质量，使得有限的资源能够得到充分的利用，考虑到公交调度 问题的多目标性和不确定性，本文采用模糊多目标规划的方法来处理这个复杂的实际问 题。本文从我国城市公交系统的特征出发，利用模糊多目标规划技术，建立能够模拟公 交运行的多目标规划模型，介绍模糊多目标优化模型的求解方法，选取具体的实例进行 计算，对建立模型的有效性进行验证，最后将所得的优化方案进行排序。本文研究的主 要内容如下： 1 准确、合理的客流数据是进行公交车辆优化调度的前提和基础。本文介绍了公 交客流数据的调查内容和方法，并根据客流在时间、空间的分布特征，对数据进行分析， 为公交优化调度提供依据。 2 建立能够模拟公交运行的模糊多目标非线性规划模型。多目标包括乘客利益、 公交公司效益，其中乘客利益又包括乘客等车费用和乘客车内费用两个目标，然后针对 所建立的模型介绍模糊多目标非线性规划的处理方法和求解步骤。 3 在建立起来的多目标规划模型的基础上，提出模糊多目标规划模型，使用两种 方法对其进行求解，一个是模糊规划方法，另一个是基于遗传算法的“模糊最优解 方 法。用m a t l a b 软件实现相关的算法，运用相关的模型和算法对具体的一路公交车进 行实例分析 4 本文介绍了模糊综合评判的方法，对得到优化方案进行综合评判，由此可以得 到这些方案的优劣顺序。 关键词：模糊规划，多目标非线性规划，公交优化调度，遗传算法 t h e a p p l i c a t i o no ff u z z ym u l t i o b j e c t i v ep r o g r a m m i n g i np u b l i ct r a n s i to p t i m a la l l o c a t i o n w ub i n ( c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g ) d i r e c t e db yp r o f l is h u r o n g a b s t r a c t f u z z ym u l t i o b j e c t i v ep r o g r a m m i n g ( f m o p ) i sa l li m p o r t a n to p t i m i z a t i o nw a yt os o l v e m a n yc o m p l i c a t e db u tp r a c t i c a lp r o b l e m s t h i sp a p e rp r e s e n t st h em o d e l i n ga n dt h es o l u t i o n o ff m o p , a n di t sa p p l i c a t i o ni np u b l i ct r a n s i to p t i m a la l l o c a t i o n p u b l i c t r a n s p o r t a t i o n i sa n i m p o r t a n tc o m p o n e n to fu r b a nt r a n s p o r t a t i o n u r b a n m o d e r n i z a t i o n , e s p e c i a l l yt h ei m p r o v e m e n to fu r b a nf u n c t i o n s ，i si n s e p a r a b l ef r o mu r b a n t r a f f i co p t i m i z a t i o na n di m p r o v e m e n t ar e a s o n a b l ep u b l i ct r a n s p o r t a t i o nc a l le f f e c t i v e l ye a s e t h ec o n t r a d i c t i o nb e t w e e nt h ec a p a c i t ya n dt r a f f i c ，k e 印t h ei n t e r e s tb a l a n c eb e t w e e n p a s s e n g e r sa n db u sc o m p a n i e s ，r e d u c ep a s s e n g e r s t r a v e lc o s t sa n di m p r o v et h ee n v i r o n m e n t a sw e l l f u r t h e r m o r e ，i tc a ni n c r e a s et h ee f f i c i e n c yo fv e h i c l e s ，a n di m p r o v et h ee c o n o m i c b e n e f i t sa n ds o c i a le f f e c t so ft h eb u sc o m p a n y g i v e nt h em u l t i p l eo b j e c t i v e sa n du n c e r t a i n t yw h e nd e a l i n gw i t ht h ep r o b l e m si nb u s a l l o c a t i o n , t h ea u t h o ra d o p t sf m o pt ow o r kt h e s ep r o b l e m so u ti no r d e rt om a k et h eb e s tu s e o fb u s e s t h i sp a p e rs h o w st h ec h a r a c t e r i s t i c so ft r a n s p o r ts y s t e mi nc h i n a , f o l l o w e db ya m o d e lm u l t i - o b j e c t i v ep r o g r a m m i n gm o d e lt h a tc a ns i m u l a t et h eb u sd r i v i n gw i t ht h eh e l po f f m o pt e c h n i q u e ，a n dg i v e ss o l u t i o n f i n a l l y , t h ea u t h o rs e l e c ts o m ec a s e st ot e s t i f yt h e v a l i d i t yo ft h i sm o d e l t h em a i nc o n t e n t so ft h i sp a p e ra r ea sf o l l o w s 1 a c c u r a t ea n dl o g i c a ld a t aa r ep r e r e q u i s i t ea n db a s i sf o rd i s p a t c h i n gb u s e s t h i sa r t i c l e d e s c r i b e st h ed e t a i l sa n dw a y so fi n v e s t i g a t i o nt ot h e s ed a t a , a n a l y z e sd a t ab a s e do nt h e d i s t r i b u t i v ec h a r a c t e r i s t i c so fp a s s e n g e rf l o wi nt i m ea n ds p a c e ，w h i c hp r o v i d e sar e a s o n a b l e b a s i sf o rd i s p a t c h i n gb u s e s 2 t h ep u b l i ct r a n s i tf u z z ym u l t i o b j e c t i v el i n e a rp r o g r a m m i n g ( p t f m o l p ) m o d e li s e s t a b l i s h e d t h em u l t i p l eo b j e c t i v e si n c l u d et h ep a s s a g e r s i n t e r e s t sw h i c hi sm a d eo ft h ec o s t o f w a i t i n gab u sa n dt h ec o s tp a i di nb u sa n dt h ep r o f i t so ft h eb u sc o m p a n y t h e nw i t ht h i s m o d e l ，t h ea u t h o ri n t r o d u c e ss o m ea p p r o a c h e sa n ds o l u t i o n so fp t f m o l p 3 b a s e do nt h ep t f m o l pm o d e l ，t h i sp a p e ra p p l i e st w oa p p r o a c h e st os o l v et h ep r o b l e m ： t h ef u z z yp r o g r a m m i n ga p p r o a c ha n dt h e f u z z yo p t i m a ls o l u t i o n a p p r o a c hb a s e d0 1 1g e n e t i c a l g o r i t h m t ou s em a t l a bt of i n i s hr e l a t e dc a l c u l a t i o n sa n da b o v e m e n t i o n e dm o d e l st o a n a l y z es o m es p e c i f i cb u s 4 。t h i sp a p e rs h o w st h ef u z z yc o m p r e h e n s i v ee v a l u a t i o nm e t h o da n dm a k e sar e m a r ko n o p t i m a lp r o g r a m f i n a l l y , t h er e a d e r sc a ng e tt h eo r d e r so f e x c e l l e n c eo ft h e s ep r o g r a m m s k e y w o r d s ：f u z z yp r o g r a m m i n g ，m u l t i o b j e c t i v el i n e a rp r o g r a m m i n g ，p u b l i ct r a n s i t o p t i m a la l l o c a t i o n ，g e n e t i ca l g o r i t h m 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位敝作者虢试盐日期：州夕年f 月z 舌日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 日期：d 年f 月z 多日 日期：叫碑 月辑 中国石油大学( 华东) 硕士学位论文 1 1 课题研究的背景 第1 章绪论 城市公共交通是指城市的公交汽车、公共电车等供公众出行乘用的、经济方便的各 种客运交通方式的总称【l 】。它的任务是在一定的时间内利用有限的运输资源，通过优质 的服务满足不同乘客的出行需求，它是城市交通的一个重要组成部分，城市要进行现代 化，完善城市功能，就需要对城市交通进行优化和提高。近些年来，随着我国经济的发 展和城市居民收入水平的提高，私家车在城市交通中逐渐发挥了一定的作用，但这并不 会削弱和取代城市公共交通的作用。城市公共交通相对于私人交通工具具有运量大、效 率高、耗能少、污染少、道路利用率高等特点，因此优良的公共交通服务对于减少城市 的交通拥挤程度、环境污染、提高交通资源的配置效益等方面都能够起到积极的作用。 在我国，随着城市规模的扩大和城市交通量的迅速增加，城市交通拥挤和阻塞现象 已经越来越严重，影响了城市居民的生活，制约了经济的快速发展。优先发展城市公共 交通，以此来缓解交通拥挤，已经成为人们的共识。目前，我国城市公共交通问题主要 表现在： ( 1 ) 城市人口的快速增长以及人们对公共交通的需求的不均衡性，使得现有的公 共交通系统不能满足人们出行的需求； ( 2 ) 公交线网布设的不合理就会导致乘客到公交站点的步行时间较长，换乘公交 车的次数较多；发车间隔的设置不合理就会导致乘客在站点等车的时间较长，尤其在上 下班高峰期，不但车上较为拥挤，且常常会因为交通堵塞而延误时间，难以保证准时到 达目的地； ( 3 ) 公交车大多运行速度较慢，在上下班和出行高峰期通常都有超载现象，远不 能满足人们对出行舒适度的要求。 因此，如何科学地管理城市公共交通系统，提高公共交通系统的运营效率，已成为 亟待解决的城市问题【2 1 。而当前公交调度管理的技术含量较低，主要靠人工实现，使公 交服务水平低，因此，只有依靠现代科技，建立合理的公交车辆调度系统，才能从根本 上解决问题。 第1 章绪论 1 2 课题研究的目的和意义 公共交通调度是一个复杂的问题，现有的研究基本上将问题划分为四个部分：公交 线网设计及优化、时刻表的编制、公交车辆调度以及驾驶人员调度，并且前问题的解 决是解决后一问题的前提和基础。公交时刻表是公交企业组织公交运营的具体作业计 划，它指导着公交线路运营的全过程1 3 1 ，因此公交时刻表的编制是公交企业管理的重要 工作。 通过本文的研究和现场应用，为东营市某一特定线路设计一个便于操作的全天( 工 作日) 的公交车调度方案，包括起点站的发车时刻表，使得下列参数： ( 1 ) 所有乘客的等车费用总和； ( 2 ) 所有乘车乘客的车内费用总和； ( 3 ) 公交公司的运营收益总和； 其中前两项构成了乘客总费用取到极小，后一项是公交公司的运营收益取到极大， 以此达到公交运营社会总效益最优的目的。 1 3 国内外研究现状 发达国家的公共交通运输建设起步较早，且对调度优化的研究也相对较早，而且已 经有大量的研究成果应用于实际，并取得了显著成果。 在公交行车计划编制方面，1 9 8 6 年a v i s h a ic e d e r 建立了公交车辆调度模型，阐述 了公交线路设计模型与算法，根据乘客的不同要求计算相应的评价目标，制定不同的发 车方案1 4 1 。1 9 9 4 年z h uw 在考虑“终端排队约束 的条件下，建立了一个以发车间隔 为决策变量，能够模拟公交车运行的非线性整数规划模型，并使用启发式算法对其求解 1 5 】；1 9 9 5 年x uj 研究了动态调度中发车间隔对公交服务水平的影响，通过对发车间隔 的控制，使公共车能够按照发车时刻表来运行，从而提高公共交通的服务质量【6 】。在计 算机仿真方面，1 9 9 6 年m a r q u e s 等研发了一个能够动态编制公交时刻表的计算机软件 系统【7 】，即s u p e r b u s 系统。2 0 世纪以来，相关的成果有：2 0 0 1 年a n d r ed ep a l m a 等 研究了在公交公司固有资源给定的条件下，针对乘客对出行成本有不同的期望值，给出 了某一线路的发车时刻表【8 1 ；2 0 0 1 年，以色列学者a c e d e r 等研究了在给定的公交线网 中，公交车同步性最大化的发车时刻表的制定问题，使乘客能够在最短的等待时间内实 现换剩9 1 。2 0 0 2 年，a l ih a g h a n i 等研究了带有时间窗的多车场车辆调度问题，建立了 2 中国石油大学( 华东) 硕士学位论文 相应的模型，并给出了该模型的启发式算法【l o 】。 我国对公交优化调度的研究和应用起步相对比较晚，公交调度的优化理论和系统尚 处于探索阶段。相关成果有：上世纪8 0 年代，蒋光震、何显慈等介绍了基于客流分布 的公共交通线路组合调度模型【1 1 1 ，9 0 年代，孙芙灵依据西安市公交公司统计得到的客 流调查数据，探讨了几种在不同情况下确定发车间隔的方法f 1 2 1 ；山东科技大学任传祥等 通过对公交运营调度的分析，建立了以乘客等车时间和公交公司运营费用为优化目标的 调度模型，将模拟退火算法引入遗传算法组成混合遗传模拟退火算法，针对所建立的公 交调度模型进行了算法设计和仿真f 1 3 】；青岛科技大学的童刚以乘客和公交公司总效益最 大为调度目标，建立了公交运营参数优化模型，并且求出了均匀的发车间隔【1 4 】：国防科 技大学的董强等探讨了带软时间窗的单线路单车型的公交调度问题，针对其多目标、多 变量的动态特点，为满足不同的实际需求建立了两个多目标规划模型：双车场模型和单 车场模型1 1 5 j 。 分析国内外学术界在公交调度方面的研究成果，在现有的公交优化模型中，存在以 下的问题：一是目标单一，大多数模型是公交公司经济利益最大化，兼顾到乘客利益等 多个目标的模型比较少；二是即使是多目标模型绝大多数也为确定性，对公交优化调度 中的模糊因素没有考虑。在模糊模型求解方面，单目标模型的求解方法已相对比较成熟， 但是对多目标的求解方法研究相对较少。针对上述问题，本课题建立了公交优化调度的 模糊多目标非线性规划模型，与确定性优化相比，模糊目标规划更符合实际情况，主要 是因为它只需要确定目标的模糊期望值，也就是一个取值范围。 1 4 主要研究内容 本文正文共分六章，主要研究内容如下： 第1 章介绍公交调度研究的背景，公交优化调度的发展历史与研究现状。 第2 章介绍本文相关的数学理论和方法。 第3 章首先介绍公共交通线路营运理论，然后对客流数据进行收集，并对相关数据 进行分析和处理。公交原始数据必须通过调查采集获得，只有通过对这些原始数据的分 析处理，才能得到客流分布的状态和规律，这些数据和规律是研究公交优化调度的依据。 第4 章建立了能够模拟公交车运行的模型。该模型是一个模糊多目标非线性规划模 型，至少有两个方面要考虑：一个是反映乘客利益的车内和等车费用，另一个是反映公 3 第l 章绪论 交公司利益的运营成本。利用模糊多目标规划对于选定的公交线路借助于m a t l a b 软 件进行求解，得到优化方案。 第5 章阐述模糊最优解的相关定义和性质，并用基于遗传算法的“模糊最优解 方 法求解相应的模型，根据不同的准则得到不同的优化方案。 第6 章介绍模糊综合评判理论，对得到的优化方案进行综合评判，在给定固定选样 的前提下，给出方案的优劣排序。 本文创新性如下： 将模糊多目标非线性规划的方法应用于公交优化调度，对相应的求解算法做了研 究，着重研究模糊多目标非线性规划模型的求解方法，并用基于“模糊最优解 的遗传 算法求解公交优化多目标非线性规划模型，选取东营市某一特定的线路使用上述算法进 行优化和仿真。 4 中国石油大学( 华东) 硕士学位论文 2 1 模糊优化基础 2 1 1 模糊数学基本概念 第2 章预备知识 1 模糊集的基本概念 模糊集合是模糊数学的基础，模糊数学是研究和处理模糊性现象的数学方法，是表 述客观世界的有力工具【1 6 1 。 设u 是论域，称映射 约珂州o ：1 】、( 2 - 1 ) x i g a ( x ) 【o ，1 】 确定了一个u 上的模糊子集4 。映射约称为4 的隶属函数，约( x ) 称为元素x 对4 的隶 属程度，使, u a ( x ) = o 5 的点x 称为4 的过渡点，这个点x 是最具有模糊性的。 当, u a 的值域为 0 , 1 时，模糊子集4 就是经典子集，鳓是它的特征函数。由此可以 看出，经典子集是模糊子集的特殊情况。 例如，由于人种、地理环境等条件的不同，人们对高个子的理解也是各不相同的。 设论域u = 一( 1 4 0 ) ，x , 0 5 0 ) ，x 3 ( 1 6 0 ) ，- ( 1 7 0 ) ，( 1 8 0 ) ，( 2 0 0 ) ) ( 单位：e r a ) 表示人的 身高，那么“高个子 ( 4 ) 就是u 上的一个模糊集。 a ( 高个子) ：五i 一4 ( 墨) = o ，恐l 一4 ( 也) = o 1 ，黾l 寸4 ( 黾) = o 4 ，以l 一4 ( _ ) = o 5 ， 黾i 斗4 ( 黾) = 0 7 ，i 专4 ( ) = l 。 上例中论域u 为有限集合。如果4 的论域为实数域的某个子集e ，隶属函数( z ) 是 互上的连续函数，若以论域的元素为横坐标，以元素对应的隶属度值为纵坐标，这样就 可以用图形直观地描述出这个模糊集合。 例如：正态分布型隶属函数为 ( 力- - e 一七( 一) z ( 2 2 ) 它的图形表示如图2 1 所示： 5 第2 章预备知识 图2 - 1 正态分布型隶属函数 2 模糊集的表不法 设论域u 是有限集。u = 而，而，x n ) ，u 上的任意一模糊集4 ，其隶属函数为 4 ( 薯) ( i = l ，2 ，刀) 。 ( 1 ) z a d e h 表示法： 4 ：剑+ 剑+ + 剑( 2 - 3 ) x2 毛 这里兰笋不是分数，它表示点薯对模糊集4 的隶属度4 ( 薯) ，“+ ”不表示求和，只有符号 意义。 ( 2 ) 序偶表示法： 4 = ( 毛，4 ( 而) ) ，( 而，4 ( 而) ) ，( 矗，4 ( 矗) ) ( 2 - 4 ) ( 3 ) 向量表示法： 4 = 4 ( 毛) ，4 ( 而) ，4 ( 瓦) ( 2 5 ) 3 模糊集合的运算 设4 ，b 为u 上的模糊集合，隶属函数分别为心 ) ，鳓 ) ，定义4 ，b 的运算 如下： r ( 1 ) 4 与量的并集记为aus ，即 心岣( “) = 约( “) v 鳓( “) = m a x 心( 甜) ，心( 材) ) ( 2 6 ) ( 2 ) 4 与尽的交集记为4 n 量，即 心n 阜( 甜) 2 心( 甜) 人心( “) = i i l i n 心( 材) ，心( 甜) ( 2 - 7 ) ( ”a 。的补集记为4 c ，且有： 以c ( 甜) = 1 一心( ”) ( 2 8 ) 6 中国石油大学( 华东) 硕士学位论文 其中，“v 为“取大运算符，“ 为“取小运算符。 4 五一截集 设4 ，( u ) ，对见【o ，1 】，记 ( 4 ) 。：以全 z 14 ( u4 ( x ) 允 ( 2 一- 9 一)( 4 ) 五= 以= z ) 允 ) 称以为模糊集合4 的旯一截集，其中旯【o ，1 】称为阈值或置信水平。以正态分布型的隶 属函数为例，它的五水平截集4 如图2 2 所示： 口 图2 2 水平截集 模糊集合4 的五一截集以是一个经典集合，由隶属度不小于见的元素构成，它的特 征函数为： 砒= ：；，锶三三 像 五越小，4 包含的元素越多，反之亦然。 2 1 2 模糊优化概述 一般的优化问题可以表示成以下形式： 幽y 亍 0 ，则称为优越支集： 厨= u 鸠 ( 2 1 4 ) 埘0 。1 1 m = um 五 ( 2 1 5 ) 2 e o ，l 】 对于决策变量x m ，它可能会属于不同的鸠，在这其中必有一个兄的最大值， 把这个五值作为x 的隶属度，这样就可以得到一个新的模糊子集g ，它的隶属函数为： 啪，h 叱瞄； 协 称之为厂( x ) 在g 上的模糊优越集，它是目标函数的模糊极值点，不但能给出最优解_ ) c ， 而且也能给出最优解满足的程度。将模糊极值点分别代入厂( x ) ，就可以得到目标函数 的模糊优越值二= 厂( g ，) ，它是函数值空间的模糊子集，不但给出了厂( 工) 的最优值， 而且也给出了该值满足约束的程度。 2 1 3 模糊非线性规划问题的分类 目前对于模糊非线性规划问题的研究，从问题的表述、分类以及求解等还有许多不 足，模糊非线性规划问题的分类可以从非线性和模糊性这两方面来考虑【1 7 1 。 非线性主要体现在目标函数或约束条件是非线性函数，或者模糊目标和系统约束是 用非线性隶属函数表示的；而模糊性主要体现在目标的非精确定义，或具有模糊关系( 模 糊等式或不等式) 的系统约束，或者是具有模糊参数的目标函数或系统约束。 模糊非线性规划问题一般分为清晰型系数和模糊型系数的模糊非线性规划问题，其 中前一类问题可以通过容差法将其描述为对称模型或非对称模型进行求解，后一类问题 的求解相对比较复杂，可以通过对模糊参数的描述，将其转化为多目标规划问题进行求 解。 中国石油大学( 华东) 硕士学位论文 关于模糊非线性规划问题的模型和求解方法的研究，主要成果有：t r a p p e y 探讨了 模糊非线性规划( 刷z p ) 问题，系统的模糊目标和约束用线性隶属函数表示，并把求解 得到的精确最优解作为用忆尸问题的最优解1 引。唐加福、汪定伟【1 9 】【2 0 1 等研究了基于“遗 传算法的模糊最优解方法，这种方法基于扩展原理，借助于隶属函数，在遗传自救的 思想下提出了模糊环境下求解非线性规划的模糊最优解方法。 2 2 数学规划基本方法 2 2 1 约束条件下非线性规划问题的求解 本文在求解公交优化调度规划模型中采用了惩罚函数法和遗传算法这两种方法。 1 惩罚函数法 考虑优化问题 i m i n 厂( x ) r 烈h i ( 功x ) 美箕嚣二 协 l = o ， = 1 ，2 ，p “7 【x x c e ”，x = ( 五，而，吒) r 惩罚函数法的基本思想是把约束问题( 2 1 7 ) 转化为一个或一系列无约束问题，然 后利用无约束优化方法来求解，逐渐逼近约束问题的最优解，该方法又称为序列无约束 极小化技术【2 1 1 。 惩罚函数的构造：对问题( 2 1 7 ) 定义惩罚函数 f ( x ，m ) = 厂( x ) + m p ( 力 ( 2 - 1 8 ) 其中m 0 为常数，称为惩罚因子，p ( x ) 是惩罚项，它满足： ( 1 ) p ( x ) 是连续的， ( 2 ) 对任意x e ”，有p ( x ) 0 ， ( 3 ) 当且仅当时z s 时，p ( x ) = 0 ，而s 是问题( 2 - 1 3 ) 的可行集，即 s = x l ( x ) o ，f = l ，2 ，m ；h j ( x ) = 0 ，j = 1 ，2 ，p ，x x ) 对等式约束，定义 g ；( x ) = ( ，( x ) ) 2 ， = 1 ，2 ，p ( 2 1 9 ) 对不等式约束，定义 9 第2 章预备知识 g ：p c x ，= 苌户耋2 窨三：i = 1 , 2 , - - , m ( 2 2 。， 令三= p + m ，于是惩罚函数为 工 f ( x ，坂) = ( x ) + 心g t ( x ) j = l 其中心 0 ，且m 鸠 尥 0 ，c 2 ，初始点x 们，令k = 1 ； s t e p 2 ：以x ( k - i ) 为初始点，求解无约束优化问题 f ( x ，尥) = ( z ) + 心酊( x ) ( 2 - 2 2 ) 设其最优解为x = x ( m i ) ) ： s t e p 3 ：令气2 磷 l 穗( x 量) i ) ，铲m 腑a s x 。 g ，( x ( ) ，f = r n a x r , ，吃 s t e p 4 ：若f o 和g 0 。则h o o k e - j e e v e s 方 法的计算步骤如下： s t e p l 令y 1 = ，k = = 1 ： s t e p 2 若厂( 户+ 嵋) 厂( y d ) ，则试验成功，令y 卜1 1 = ，7 + 呜，转s t e p 3 ：否则， 若f ( y o ) + 心) ( y 1 ：则试验失败，此时，若f ( y u ) 一屯) ( y 7 ) ，令 户枷= ，d 一鸩，转s t e p 3 ；若厂( 少d 一呜) ( 少) ，令，螂= 少力，转s t e p 3 ； s t e p 3 若j n ，令j f 矿1 ，返回s t e p 2 ；否则，= r t ，若( y ( 肿1 ) 厂 ) ，转s t e p 5 ； 1 0 中国石油大学( 华东) 硕士学位论文 若( 少( 川) f ( x ) ，则转s t e p 4 。 s t e p 4 令x 七+ 1 = y 川，夕1 = x + 口( x 一，) ，k = 七+ 1 ，再令卢l ，返回s t e p 2 。 s t e p 5 若d 占，则计算结束，取x x ；否则令d = d 2 ，y 1 - - - x ，x m - x n ， k = k + l ，再令_ ，= l ，返回s t e p 2 。 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 是由美国m i c h i g a n 大学的h l l l a n d 教授于1 9 7 5 年首次 提出，它的基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学，即生物的遗传和变异 在生物的进化过程起着重要作用，它使得生物在保持自身固有特性的同时还能够不断改 变自身以适应新的生存环境。遗传算法是基于群体进化的一种启发式算法，它通过群体 的个体之间繁殖、变异、竞争等方法进行信息的优胜劣汰，从而逐步逼近问题的最优解。 对个体的遗传操作主要是通过选择、交叉和变异这三个基本的遗传算子来实现1 2 2 1 。 遗传算法的运算对象是群体，在进行操作之前要首先对群体中的个体进行编码，遗 传算法有二进制型、实数型、序列型及动态编码等多种编码方式，分别适用于不同的工 程优化问题。目前，实数编码的遗传算法【2 3 1 由于没有编码和解码的资源开支，对于复杂 的优化问题，计算速度与二进制编码相比具有明显优势。 设优化问题为： 僦f ( x ) _ 厂( 一，而) ( 2 - 2 3 ) 【 a j 而岛 f = 1 ，2 ， 约束条件为g i ( x ) o ，i 釜1 ，2 ，m 实数编码的遗传算法原理： ( 1 ) 编码 取向量x = x x 2 而作为群体中的个体。 ( 2 ) 杂交算子 对于实数编码的杂交算子，与二进制不同。设x 和y 为父代个体，彳和，为子代 个体。 父代：x = 五屯而，y = 咒咒咒， 子代：x = 爿砭舛，r = 删 ， 杂交方式有以下两种方式： a ) 简单杂交 第2 章预备知识 类似于二进制编码的单点杂交，产生一个随机整数，【1 ，1 - 1 】，按式( 2 - 2 4 ) 和( 2 - 2 5 ) 进行杂交。 = 授乩2 ， 亿2 4 ) = 像蚤乩2 ， 亿2 5 ， b ) 算术杂交 产生一个随机数，( 0 , 1 ) ，按式( 2 2 6 ) 和( 2 2 7 ) 进行杂交。 = 伟+ ( 卜，) 以，i = 1 ，2 ，z ( 2 2 6 ) = 供+ ( 1 ，) 薯，i = 1 ，2 ， ( 2 2 7 ) ( 3 ) 变异算子 实数编码的遗传算法的变异操作对象是实数，可以按照以下两种方式进行变异。 a ) 边界变异 产生一个随机整数，【1 ，一1 】，随机实数p ( 0 , 1 ) ，按式( 2 - 2 8 ) 进行变异。 巧：三鬈慧 协2 8 ， h ，其他 b ) 均匀变异 产生随机整数，【1 , l - 1 ，随机实数p ( o ，1 ) ，按式( 2 2 9 ) 进行变异。 ：jq + p ( 6 i 一口f ) ，1 2 r ( 2 2 9 ) 实数编码遗传算法的步骤： s t e p l 群体初始化：使用随机初始化，产生一个0 - - 1 之间的随机数，按照式( 2 3 0 ) 转化为上下界为h ，岛】内的实数。 而= 嚷+ 厂( 龟一q ) i = l ，2 ，z ( 2 3 0 ) s t e p 2 父代群体的适应度评价：在遗传算法中，适应度函数要求为正值，对最大化 问题，按( 2 3 1 ) 构造适应度函数： 他) _ 。 嚣卜。 协3 ， 1 2 中国石油大学( 华东) 硕士学位论文 其中f ( x 1 是目标函数值。 s t e p 3 选择：采用随机联赛选择法，从群体中随机选择一定数目个体进行适应度大 小的比较，其中适应度高的个体可以被保存下来，作为父代个体，它们将有机会繁殖后 代。如此反复，直到选满指定的群体数目为止。 s t e p 4 配对：将随机选择的个体进行配对。 s t e p 5 杂交：将杂交算子作用于群体，杂交算子采用混合杂交，即当配对的个体参 与杂交的概率小于给定杂交概率只时，就进行杂交操作。 s t e p 6 变异：将变异算子作用于群体，变异算子采用混合变异，即当个体变异概率 小于给定变异概率巴时，就进行变异操作。 s t e p 7 终止条件判断：常用的终止条件有两种，一是将最优个体的目标值f ( k ) 和 各代群体的平均目标值芦做差，所得的差值若小于给定的精度就停止进化；另一种可以 规定最大的进化代数，如果达到最大进化代数就判断进化结束，若不满足终止条件，则 返回s t e p 2 继续进行操作。 综上所述，遗传算法的基本流程如图2 1 所示。 开始 l l 编码、生成初始群体 0 对群体中的个体进行适应度评价 + y s 垂 了n 终止进 选择 化计 上 算，输 出最优 交叉个体并 1 l 解码。 变异 山 结束 i 图2 - 1 遗传算法基本流程图 1 3 第2 章预各知识 2 2 2 多目标规划问题的求解 1 多目标最优化的模型 多目标优化问题的目标函数通常表示 矿一m i n f ( x ) = 石( x ) ，正( x ) ，厶( 彳) r ( 2 3 2 ) 其中，x = h ，五，】。因此，多目标最优化问题一般可以表示为： v - m i n f ( x ) 珐粥笺 q 。3 3 其中不等式约束函数g ( x ) = 蜀( x ) ，9 2 ( x ) ，岛( x ) 2 ， 等式约束函数 | l ( x ) = 陬( x ) ，如( x ) ，壤( x ) 2 。多目标最优化问题实际上是向量函数的最优化问 题。 2 评价函数法 多目标最优化问题的解法中比较重要和常见的是评价函数法【2 2 j 。评价函数的基本思 想是：借助于构造某种恰当的评价函数，将多目标规划问题转化为单目标规划问题来求 解。 评价函数求解多目标规划问题的一般步骤是：首先构造恰当的评价函数厅( 厂( x ) ) ， 然后解单目标规划问题r a 舶i 。n 乃( ( x ) ) 。最后对得到的解x 进行评价，必要时加以修正。 由于评价函数可以是多种多样的，因而方法也就不同。常见的方法有：理想点法、 平方和加权法、极小一极大法、乘除法和线性加权和法。本课题主要用线性加权和法， 其基本原理是：根据各目标函数的重要程度构造评价函数： 矗( 厂( x ) ) = 哆z ( x ) ( 2 - 3 4 ) 册 其中哆为加权系数，满足哆o , v i = i ，2 ，m r 哆= 1 ，然后求解 f = i 泓厅( 厂( x ) ) 2 赔i = iq 彳( x ) ( 2 - 3 5 ) 1 4 中国石油大学( 华东) 硕士学位论文 第3 章公共交通线路营运调度及其客流数据采集与分析处理 3 1 公共交通线路营运调度 公共交通线路调度分两种【2 4 1 ： ( 1 ) 原始调度，在始发站根据公交公司的固有资源和掌握的客流数据制定发车时 刻表，称之为静态调度； ( 2 ) 由于路况信息或某种突发事件，使得原始调度必须做出修改、更新，称之为 动态调度。 定线式公共交通行车时刻表，是指在既定的公交线网下，公交企业根据现有的运输 资源、乘客的出行需求及客流变化规律所制定的具体作业计划，它能指导线路上各个车 组运营的全过程，它为公交企业的各基层单位的运营管理提供依据，它为给乘客提供优 质的公交服务提供了前提条件。 发车时刻表根据不同标准可以有多种分类【2 5 】： ( 1 ) 根据一年中客流的季节性波形，可分为春夏秋冬和高温季节等五种发车时刻 表。这主要是因为城市居民在不同季节里生活习惯及其工作制度不同，乘客在时间和空 间上的分布也随之不同。 ( 2 ) 按照客流的日间波动性，可分为节假日和平日行车时刻表等。这主要是由于 乘客在平日和节假日出行目的和时间不同，从而导致客运服务区域内的客流量分布在时 间和空间的变化。 静态调度与动态调度之间的关系式：公交公司首先对客流数据进行调查分析，在得 到客流分布规律的基础上，制定科学合理发车时刻表，根据发车时刻表对发车进行静态 调度，在具体运营过程中若出现突发情况，可根据现代通信技术及时获得这些信息，调 整性地进行动态调度。本文主要考虑静态调度，即发车时刻表的制定。 3 2 客流数据调查 客流是指把公交车辆作为出行工具的乘客群，乘客群流动的数量简称为客流量【2 6 1 。 公交客流数据调查是指对城市居民乘车需求情况的调查，包括对客流在线路、时间、方 向和断面上的动态分布所进行的经常、定期、全面或抽样的调查并分析的过程【2 7 1 。公交 客流调查的主要研究内容包括客流调查的内容和方法。 1 5 第3 章公共交通线路营运及其客流数据采集与分析处理 3 2 1 客流调查内容 要进行公交调度就必须对公交客流数据进行全面的调查，公交客流调查主要包括城 市状况、公交线路、公交车辆情况及乘客分布的状况等【2 踟，具体地，公交客流调查内容 如表3 1 所示： 表3 - 1 客流调查内容 序 项目主要内容 号 城市的面积、人口、经济发展水平、就业人口以及工业区、商业区和居 l 城市状况 民区的分布 线路的方向、线路站点数目、线路总长、站点间的距离、线路数量、公 2 线路数据 交线网的密度、直达系数 乘客在各站点上下车的数量、上下车所需要的时间、乘客出行的起、讫 3乘客数据 点、换乘点以及乘车前后需要的步行距离 公交车辆类型、车辆的标准载客人数、固定线路的配车数和公交公司所 4 车辆情况 拥有的总车辆数、公交车辆运营的同定成本和可变成本 载客里程= 线路总长度线路上下行的车次 里程 运营里程= 载客里程+ 车辆进出停车场行驶的里程 全日通过量= 运客人次平均乘站 通过量 高峰小时通过量= 器时间不均衡系数 满载率 线路全日平均满载率= 车翥毳次x 1 0 0 5 运营指标 工时利用率 工时利用率= 纛鬟妻圭筹。 单程行驶时间指运营车辆在线路的起点站发车到终 单程行驶时间点站进站的车辆单向行走时间，不包括首末站停车时间； 停站时间停站时间是运营车辆在线路起始点( 或终点站) 的待 发时间( 或停留时间) 以上这些指标是进行公交优化调度的基本数据，其中有些数据不会经常变动，相对 比较稳定，例如线路数据，而有一些数据是动态变化的，需要经常经常进行调查，例如 乘客数据，这样才能够获得实时动态的数据。在客流调查中，根据调查内容和要求的不 同，选择其中不同的内容进行调查收集【2 9 】。 1 6 中国石油大学( 华东) 硕士学位论文 3 2 2 客流调查方法 我国调查客流数据主要采用人工调查方法，这种方法需要耗费一定的人力，但可以 获得较全面的数据。主要方法有随车调查法、站点调查法和问询调查法【3 0 1 ，这三种方法 具体介绍如下： 1 随车调查法 在线路上按车门数安排2 3 名专门的调查人员，记录车辆达到沿线各站点的时刻、 在每个车站上下车的人数以及在站点上等车的人数。这种调查方法可以获取不同时间的 客流量、各断面通过量、车辆满载率，以及平均运距、乘客密度、不均衡系数等数据。 该方法的优点是客流调查的数据全面，准确率相对较高，适用于定期调查。 2 站点调查法 根据车辆行车间隔、停站时间等情况，在每个站点设置一定数量的调查人员，依次 记录上下车乘客数、公交车内的人数、留站的等车人数和通