（交通信息工程及控制专业论文）基于信息平台的车辆调度研究与仿真.pdf

摘要 车辆调度问题一直是智能交通运输系统研究的热点，关于车辆调度的研究对 改善城市道路利用率，推动智能交通运输发展是非常有意义的。研究车辆调度模 型和优化算法对于车辆调度系统的应用，改善交通运输的智能化水平更是具有重 要的理论意义和实际价值。 论文针对给定任务下的车辆调度和给定线路下的车辆调度两种情况分别做 了研究，本文的主要工作有： 在给定任务下的车辆调度方面，针对物流配送中的车辆调度问题，建立了考 虑城市路网交通状况和客户时间限制的车辆调度模型，模型中用路阻函数中的 b p r 函数来真实反映交通状况对车辆调度的影响。 设计了混合粒子群优化算法来优化计算给定任务下的车辆调度问题，目前在 粒子群的约束优化问题j 二面研究较少，文中利用了粒子群简洁容易实现和模拟退 火在组合优化中的优势，对给定任务下的车辆调度问题进行优化计算。 在给定线路下的车辆调度方面，钳刘公交车辆调度问题，建立了考虑公交公 司利益和乘客利益的车辆调度模型，模型中用加权系数将多目标优化问题转化为 单目标优化问题。 设计了一套遗传算法的求解方案来求解给定线路f 的车辆调度问题。此算法 的适应度函数为经过转换的公交车辆优化问题的f 1 标函数：在选择时主体使用比 例选择；交叉时采用双点交叉；变异时采用倒位操作，并运用了保留精英策略保 征算法收敛性。对优化模型进行编程、优化计算与分析。 最后，给山了车辆调度系统的设计思想和实现方案，并将研究的车辆捌度模 耻和优化算法，应用在西安市的一物流配送中的车辆调度和西安市2 9 蹄公交年 辆调度中，进行了结果分析，并给出了调度方案。 关键词：车辆调度，优化，粒子群算法，模拟退火，遗传算法 a b s t r a c t v e h i c l er o u t i n gp r o b l e mi st h ef o c t u s i n g r e s e a r c ho ft h e i 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 ( i t s ) d e v e l o p i n ga n dc o n s t r u c t i n g v e h i c l eo p t i m i z i n g r o u t i n gs y s t e mi sas o r to fs c i e n t i f i ca p p r o a c ho fl o w e r i n gt r a n s p o r t a t i o nc o s ta n d p r o m o t i n gt h ed e v e l o p m e n to ft h ei t s t h e r e s e a r c ho nt h em o d e la n dt h e o p t i m i z a t i o na l g o r i t h m so fv e h i c l er o u t i n gp r o b l e ma l s oh a si m p o r t a n ts i g n i f i c a n c e a n dp r a c t i c a lv a l u et oe n h a n c et h ei n t e l l i g e n e eo f t r a n s p o r t a t i o ns y s t e m t h i st h e s i sm a k e sr e s e a r c ho nv e h i c l er o u t i n gp r o b l e mw i t ht h ek n o w n a s s i g n m e n t sa n dv e h i c l er o u t i n gp r o b l e mw i t ht h ek n o w nr o u t e s t h em a i nw o r ki s a st b 1 0 w s ： f i r s t l y o nt h eb a c k g r o u n do fl o g i s t i c sa ni m p r o v e dm o d e lo fv i h i c l er o u t i n g p r o b l e mw i t l lt h ek n o w na s s i g n m e n t si si n t r o d u c e d t h em e d e lt a k e si n t oa c c o u n tt h e t r a f f i cs t a t u sa n dt h et i m er e q u e s t e db yc l i e n t s t h ei m p e d a n c ef u n c t i o ni su s e dt o r e f l e c tt h ea c t u a li r a m cs t a t u s ， s e c o n d l y t h e r ei sal i t t l er e s e a r c ho nt h ep a r t i c l es w a r ma l g o r i t l _ l i n b u ti t i s e a s i e r 幻r e a l i z et h a nt h eo t h e ri n t e l l i g e n ta l g o r i t h m s t h es i m u l a t e da n n e a l i n g a l g o r i t h mh a sa d v a n t a g e si ns o l v i n gc o m b i n a t i o no p t i m i z a t i o n s oah y b r i dp a r t i c l e s w a r ma l g o r i t h m w h i c hi sc o m b i n e dt h ep a r t i c l es w a r ma l g o r i t h ma n dt h e s i m u l a t e da n n e a l i n ga l g o r i t h m i sp r o p o s e dt os o l v et h ev e h i c l er o u t i n gp r o b l e m w i t ht h ek n o w na s s i g n m e n t s t h em o d e la n dt h ea l g o r i t h ma r ec a l c u l a t e da n d s i m t d a t e dt h r o u g hp r o g r a m m i n g 7 t h er e s u l to fs i m u l a t i o ns h o w st h ev a l i d i t yo ft h i s m e t h o d t h i r d l y , o nt h eb a c k g r o u n do fp u b l i ct r a n s p o r t a t i o na ni m p r o v e dm o d e io f v e h i c t er o u t i n gp r o b l e mw i t ht h ek n o w nr o u t e si si n t r o d u c e d t h em o d e lt a k e si n t o a c c o u n tt h eb e n e f i to f t h ep u b l i ct r a n s p o r t a t i o nc o m p a n ya n dt h eb e n e f i to f p a s s e n g e r s l h ew e i g h t i n gm e t h o di su s e dt ot r a n s l a t et h em u l t i o b j e c t i v eo p t i m i z a t i o ni n t ot h e s i n g l e - o b j e c t i v eo p t i m i z a t i o n f o u r t h l y , t h es c h e m eb a s e do ng e n e t i ca l g o r i t h mi sd e s i g n e da i ma tt h em o d e lo f v e h i c l er o u t i n gp r o b l e mw i t ht h ek n o w nr o u t e s i t sf i t n e s sf u n c t i o ni st h eo b j e c t i v e f u n c t i o nt r a n s 岛r m e d s e l e c t i o no p e r a t o ri sp r o p o r t i o n a lm o d e l c r o s s o v e ro p e r a t o r i st w o p o i n tc r o s s o v e rm u t a t i o no p e r a t o ri si n v e r s em u t a t i o n e l i t i s tm o d e l i su s e d 抽t h eg a 。p r o g r a ms i m u l a t e st h em o d e ia n dt h eg a 。t h eo p t i m i z a t i o nr e s u l ti s a n a l y z e d l a s t l y , t h ed e s i g ni d e aa n dt h er e a l i z a t i o ns c h e m eo fv i h i c l eo p t i m i z i n gr o u t i n g s y s t e mi sg i v e n + b a s e do nt h er e a lt r a m ci n v e s t i g a t i o nd a t ao f x i a nc i t y , t h em o d e l s a n dt h eo p t i m i z a t i o na l g o r i t h m sr e s e a r c h e di nt h ef r o n tc h a p t e r sa r ea p p l i e dt ot h e r o u t i n go ft h el o g i s t i cd e l i v e r ya n dt h es c h e d u l i n go f 2 9r o u t ep u b l i ct r a n s p o r t a t i o no f x i a nc i t y i h eo p t i m i z a t i o nr e s u l ti sa n a l y z e da n dt h es c h e d u l i n gs c h e m ei sg i v e n ， k e y w o r d s ：v e h i c l er o u t i n gp r o b l e m ，o p t i m i z a t i o n ，p a r t i c l es w a r ma l g o r i t h m s i m u l a t e da n n e a l i n g ，g e n e t i ca l g o r i t h m u 两北t 业大学硕1 ：学位论文第一章绪沧 1 1 选题意义和背景 第一章绪论 交通运输系统是社会结构的一个基本构成，它是一个动态系统。交通运输、i t 的发展本乎怒国家兴旺发达约重要标志之一。交通运蝓业的高速发展，促进了物 资交流和人们的来往，大大缩短了出行时间，提高了工作的效率。但是，由于许 多原因，交通运输的高速发展使有限的道路不堪重负、塞车常见，这些现象越来 越严重地困_ 拢着越界各鬻的大城市。资料表明，美匿从1 9 7 6 年至1 9 9 7 年，车辆 公里数以7 7 速度一j ：7 t + ，可是同期道路建设里程的增长数却仅为2 ，由于交通 拥挤，人们每天消耗在上下班的时间比平时平均多了1 5 小时，同时导敛商业车 辆的延误，增加了运输成本。因此，建立智能运输系统( i n t e l l i g c n t f r a n s p o r t a t i e n s y s t e m ，简称i t s ) 是交遂运输系统实现现代化的一顼重要举措，它能够促进社 会经济环境的进一步优化，是i u i = 界经济发展的必然要求l i l 。 智能运输系统( i 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 s ，简称i t s ) ，是将先进的计 算机技术，信怠技术，数据通信传输技术，自动控制技术，人工智能及电予技 术等有效缝综台运用予交通运输镎理体系中，建立一种在大范圉内，全方位发 挥作用的准时、准确、高效的交通运输管理体系。i t s 是2 0 h ：纪6 0 年代末， 由美国率先进行研究的，随后，日本和西欧等发达国家在此领域也投入大鼙的 人力和资金。1 9 9 5 年3 月美国交遂部首次磊式颁布了国家智能交通系统项目 援划， ! ；i l 确规定了智糍交通系统的7 大领域手 | 2 9 个= ；| i 户服务功能，并确定_ 到2 0 0 5 年的年度开发计划。其r 斗 17 大领域包括：出行和交通管理系统、出行需 求管理系统、公共交通运营系统、商用车辆运营系统、电子收费系统、应急管 理系统、先进的车辆控制和安全系统。我国交遂方谣的专家黍i 学者在上照纪9 。 年代，在全碰研究国外i t s 发展的基础 ：，结合我姻酬馈和具体实际情况， 提出了适合我困交通发展的全新的i t s 。其中主要包括：先进的交通管理系统、 先进的公共交通系统、交通信怠服务系统、电视临控系统、车辆安仓系统、物 流管理系统等f 2 3 1 4 1 。由此可见，无沦是翻外还是潮内，# | l i 调度朗题一壹部是 智能交通系统的重要内容。 车辆优化调度的实质是最大限度地刹用公路运输能力向运输车辅提供行驶 o t i 1 l ：i ：业大学硕j ：学位论文第一章绪论 前和行驶中的车辆行驶路径信息，及时提供各种交通信息，保汪运输任务的离 效率顺利完成。有以下几个原冈促使我们需要研究车辆优化谰度问题* ，7 ，8 9 】： 1 过去城市砉冕模小，城市公路交通状况简单，车辆少，整个交通状况处于闲疆 状态。现今魃着城市的规模趋向于大规摸，超大规模发展。城市交通就逐灏 变得庞大复杂。对于很多行业( 例如：运输公司、公交公司、出租车公司、 1 l o 报警、1 1 9 火警以及医疗救护系统等) 已经面临着一个很重要问题：“怎 样在庞大复杂的城市交遥嘲，以及繁忙笳路面交遥状况中寻找合理的车辆路 径以满足需要”；， 2 物流业的蓬勃发展，特别是电予商务的发展、第三方物流公司的出现，这使 人们越来越关注运输环节的工作效率，减少交通拥挤和事故，来更好的获得 “第三利翻源”，强化国甄竞争力。 3 。当前，车辆渊度问题中路径优化在动态信息处理这方砸还不是很及时、完善， 而目其模型、算法策略与现实车辆调度问题还有一段距离，这使人们对车辆 闯趣有了更大的研究空问。 4 由于地资源和资金有限，唯靠道路建设解决交通问题有限度，必须考虑有 限设施的最有效利用，这使人们不得不研究车辆调度问题。 车辆优化调度作为智能交通系统的一个重要组成部分，其研究的好坏直接影 响了系统能甭真正有效圭l | l 解决交通离题。随着汁算机技术、信息技术、遥讯技术、 g p s 、和g i s 技术等 勺高速发展，这些技术成为目裁实现车妫优化调度的关键技 术。通过这些技术，能实时获取车茸l i l j 位鬣信息、道路状况、客户信息，实时的进 行车辆行驶路径优化，这对提高车辆效率，缓解交通拥挤有蘑要意义。通过车辆 恍化润发，可以方便交通管理人员获敢各种交通信息，捉裹e 作效率；可以大大 提商城市交通管理决策的有效性和正确性，提高交通管理决策效率，进一步提高 交通管理的现代化水平；可以提供一种新型交通信息管理与辅助决策的模式：可 以解决城市交通稍挤、能源短缺、大气污染等闷题，保证交通资源合理配置与利 羽。因此骥究车孝| l i | 渊度是缀有意义的。 1 2 国内外研究现状及问题分析 车辆优化调度翊题最早楚由学者d a n t z 堙和r a m s e r - v1 9 5 9 年首次提出的 0 1 。 圈外一般称之为v e h i c l er o u t i n gp r o b l e m 或v e h i c l es c h e d u l i n gp r o b l e m ，大多数 文献习惯用v r p 表述车辆凋度问题。v r p 被提出后，国内外各学科的学者从不 同角度，不嗣方向对它避行了各种磷究+ 并备裔按不同的标准对v r p 进行了分 类，但总体的两大方向是给定任务下的车辆调度和绘定线路下的车辆调度。 两z i e k 大学硕士学位论文 第一章绪论 1 2 1 国内外研究现状 1 给定任务下的车辆调度 绘定任务下的车辆调度有以下几种情况 1 t , 1 2 a 3 , 1 4 1 ： 任务目标不同：有纯装问题或纯卸问题( p u r ep i c k u po r p u r ed e l i v e r y ，车辆在 所有任务点装货或卸货，即集货或送货问题) 及装卸混合问题( c o m b i n e dp i c k u pa n dd e l i v e r y ，每顼饪务有不同豹装货点窃卸货点，朝集货、送货一体亿闽 题) 。 车辆载货状况不同：有满载问题( 货运量不小于车辆容量，完成一一项任务需 要不只辆车) 和非满载问题( 货运量小于车辆容量，一辆车可完成多项任 务) 。 车场数嗣不同：有单车场问题和多车场问题。 车辆类型不同：有单车测问题( 所有车辆类裂和容量相同) 和多车型问题( 执 行任务的各车辆的类型和容蘩不完全和同) 。 车辆对车场豹所属关系不弼：有车辆开敞问题( 车辆可以不返涸其发车场) 和 车辆封闭问题( 车辆必须返回其发车场) 。 v r p 中各项任务是否有时问限制：有一般车辆优化调度问题和带时问窗的车 辆饯化调度润题。其中时闻窗又可分为矮时间窗和软时闯窗，硬时闻窗( h t w ) 是指任务必须在给定的时问范疆陡完成，否则褥到的缌视为不可彳= j ；：孵：软时 间窗( s t w ) 指如果任务不能在给定的时间范围内完成，则同时给予+ 一定的惩 罚。 绦定任务下的车辆涧度一一般定义为：对一系列发货点或枝货点，组织适当驰 行车路线，使车辆有序地通过它 f ，在满足一定姻约求条件( 互n 货物需求撼、发 送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定 的磊标( 翔路程竣短、费用极小、时闷尽量少、使用车辆数尽鬃少等) 。它经历 了如下的砑究进程： 二十世纪5 0 年代：d a n t z i n g 和r a m s e r 于1 9 5 9 年刹用整数规划模式来处理车 辆调度问题： 二十世纪6 0 年代：c i a r k e 和w r 汁g h t 于1 9 6 4 年掇出了一种启发式节约求建 立车队配送路线；c h r i s t o f i d e s 和e i l o n 于1 9 6 9 年应照2 - o p t l l 5 懒3 - o p t l l 叫 方法来处理车队配送路线； 二h 琏纪7 0 年代：1 9 7 0 年提出了两阶段启发式算法来求解车辆凋度问题， g i l l e t t 和m i l i e r 于1 9 7 4 年键出的扫描法印属于先路径再分缝的方法、 c h r is t o f i d e s 等人于1 9 7 8 年则提出先分组再路径豹方法。此时学谨g oj t i e r , 、 两北工业太学硕士学位论文 第章绪论 m a g n a n t i 和n g u y e n 于1 9 7 7 年指出虽然两阶段启发式算法可处理较大型问 题，但其涉及运算效率是相当重要的问题 1 5 , 1 6 , 1 7 l ； = 二= 十赶纪8 0 年代：f i s h e r 和j a i k u m a r 于1 9 8 l 提融良数学瓶划为主的簸优 化方法米处理包含大约5 0 个顾客点的阅题，同样其运算效率是一个亟待解 决的问题【1 8 1 。另外，o u l l e n ，j a r v i s 和r a t li f f 于1 9 8 1 年建立一种人机互动 的启发式方法； 二十世纪9 0 年代：f i s h e r 予1 9 9 5 年对优纯算法加以改善，已经可以释决较 多顾客点的车辆渊度问题，同一时期，有不少学者利用扇发式算法来解决车 辆调度n 题，包括模拟退火算法、确定性退火法、遗传算法、神经网络算法 和禁忌搜索算法。如r o b u s t e ，d a g a n z o 和s o u l e y r t t e ( 1 9 9 0 ) 以及a l f a 、 t i e r a g u ( 1 9 9 1 ) 郯利用模拟退火算法求解车辆调凄问题；s e m e n t 积t a i l l a r d ( 1 9 9 3 ) 、g e n d r 。e a u 、h e r z 和l a p o r t e ( 1 9 9 4 ) 、r o c h a t 和t a i l l a r d ( 1 9 9 5 ) 以及x u 和k e l l y ( 1 9 9 6 ) 都利用禁忌搜索算法求解车辆调度问题 1 9 ；2 0 , 2 1 , 2 2 , 2 3 , 2 4 ，2 5 , 2 6 , 2 7 1 。 2 ，给定线路下的车辅调度 给定线路f 的车辆调度有以下几科”隋况： 公交车辆的调度，它是在公交公司制定了固定线路下对公交车辆进行调度。 公爨客运中出一城亩到另一城市圈定线路上的车辆豹 | 2 l 度。 给定路线下的车辆调度一般定义为：对固定路线上豹车辆，组织合适的发车 时问，在满足。一定的约束条件( 车辆数的限制、发车间隔的限制等) ，达到一定 的目标( 如费用极小、时问尽量少等) 。近年来国内外学者在此方面取褥了知f 研究成暴： 文献 2 8 1 研究了实时空车趟站行驶问题，建立确定放空车辆的发车时刻和最 小化系统巾乘客总耗时的越站行驶车站数的模型；文献【3 0 】提出公交实时调度模 型及其算法，作为i t s 中公交智能调度的理沦基础；文献【3 l 】对公交调皮中发车 n q 弼| ：；| 勺确定方法进行了研究：文献 3 2 ，3 3 ，3 4 1 主要研究了在智能交通系统( 1 r s ) 应 用背景f ，基于遗传算法和b p 神经网络的动态或者实时渊度方法，文献 3 5 ，3 6 1 提出了以企、j t 满意程度、乘客满意程度为目标函数的发车频率优化模型；文献 3 7 1 提出了在隧秘条件”f 建立时刻表控翻策略使换乘时闯最小化，对随移i 延误给出了 期望值模型，并对些数学性质进行了讨论；文献| 3 8 1 分析了在一定的公交车辆 和单一线路的条件下，当乘客的计划出行时问与公交车由于时刻表提前或延误的 实际走行时问不一致时的优化方法，构造了在连续时间内最小化乘客的憨时刻表 延误模型。文献 3 9 】通过枫会约束援划1 2 9 】研究公交溺度闯题，苞珏究在公交走露时 削的不确定性、乘客需求的不确定性、以及乘客等待时间限制筹这些因索的影响 4 p q 北i 业人学硕士学位论文第章绪论 f ，企q k s t 益如何在定的旨信水平下最大化。 目前针对车辆优化调度问题的求解算法可以说是相当丰富，根据对这些算法 本质豹分类研究，基本上可以分为糖确簿法和启发式算法掰大类 【4 0 0 1 , 4 2 , 4 3 , 4 4 , 4 5 , 4 6 , 4 7 , 4 8 , 4 9 5 0 ，5 1 ，5 2 , 5 3 1 。 精确算法 精确算法指可求出最优解的箨法，主要有：分校界定法( b r a n c ha n db o u n d a p r o a c h ) ，割乎西法( c u t in gp l a n e sa p p r o a c h ) ，网终流算法( n e t w o r kf l o w a p p t o a e h ) ，动态规化法( d y n a m i cp r o g r a n u n i n ga p p r o a c h ) 。精确算法的计算量 一般随问题规模的增大而呈指数增长，所以多用于规模较小的问题中。 稿发式算法 启发式算法( h e u r i s t i c s ) 是指一秘基于瞧观或经验构造的算法，锺标是在可 接受的花费( 计算时间、占用空间等) 下得出待解决问题的满意解，而不是最优解。 大部分学者都是在构造简效率、商质量的启发式算法来解决车辆调度问题。这是 潮为v r p 是强n p 难题闻题，有时不存在严格意义的最优解，两启发式方法能够 比较炔地得到满意解。目前已提出的启发式算法主要有：构造算法( c or l s t r u c t i v e a l g o r i t h i n ) 、两阶段法( t w o p h a s ea l g o r i t h r n ) 、不完全优化算法( n c o m p l e t e o p t i m i z a t i o na l g o i t h m ) 、改避饶化算法( i m p r o v e m e n to p t i m i z a t i o nm e t t r o d s ) 。 1 22 问题分析 在给定任务车辆调度方丽，车辆调度计划的制定需要基于一些确定信息，如 订货点( 送货点) 位置、车辆位置、货物数量( 重量) 、时间要求等等。当车辆行驶 在交通路阐中，影响车辆调度的因素也是很多，例如遴路的交通状况，交通事故 等等。随蓑城毒交通f ；：| 益繁忙，要姆车辆调度阉题应用予实际当中，就必需考虑 这些因攀，现阶段考虑道路交通状况通常用路权来表示。在车辆调度咔，圈时1 孝 枵大多通过定义系数来表示路权，但这种方法有时不能真实地反映路刚交通状 况。因此有必要寻我一个能够反应交通状况对车辆调度所产i 影响的确效途径。 在给定线路车辆调度的公交车辆调度方灏，两方鄹家已经将一螳调度算法成 熟地运用在公交车辆调度系统中，其中的超启发式算法能够问时解次3 0 0 辆公交 车的计划时f i _ j j 编制。与发达陶家相比，我国的公交调度管理主要依靠人，j 制定 运营谤划主蝥依靠经验，缺乏秘学性与合理性，运营调度管理实羽性镁差。这些 因素制约着调度 二作 | 勺优化，给我国大、中城市的公交系统带来很多问题。以她 安市为例，公交线阀主要存在线网结构啦一、 交运行速度低、换乘不方便、车辆满载率高 5 线恻密度低、线路分布不均衡、公 不满足舒适性要求、部分车 i i 【j 行： 两l t1 监火学硕士学佼论文第誊绪论 时刻表没有依据客流规律等方面的问题。因此有必要从公交公司利益和乘客利益 出发，依据客流信息对公交车辆调度避幸亍研究。 通过对车辆调度问题国内外研究工霓状的分析，论文在研究过程中针对车辆酾 度现有的一些问题做了一些硪窥。 1 3 论文的主要工作及章节安排 论文是以锂能运输系统中车辆优化调度为背景，对运输系统的车辆调度方法 进行了研究。车辆调度问题直以来怒比较复杂的优化问题，往往匿i 为考虑的因 素的不霹丽不同，本文藏分别对两种滔况的车辆调度蜘题敞了研究，主要研究内 容有： 1 建立了给定任务1 = 的车辆调度模型。建立模型时考虑运送成本最低，交通路 网的交通状况的影响以及服务时间的限制等。成本最低就是使车辆所走总路 程消耗的成本鼓低：交通状况通过路阻函数来反映，使运用路i 羁函数得寒的 车辆行驶辩耀最短：服务瓣阉通过惩罚瞒数来反映，翔不在要求时阔内，绘 予一定惩罚成本。这样使模型具有很强的实用性和现实意义。 2 设计了混合粒子群算法求解绘定任务下的车辆调度问题。混台粒予群算法是 被子群算法与摸拟退火算法的结合。粒子群算法是类较新颖的优 七算法， 校拟退火算法在组合优化阀题中有很好的效果。因此在车瓤溺度阉题中使它 们发样各自优势，对优化模墅进行编程、优化计算与分析。 3 建立了给定线路下的车辆调度问题中灼公交车辆调度模型。建立公交车辆调 度模型扶公交公司利益嗣乘客乖l 益蹬发，使公交公司运餐成本最低，经乘客 等车时删最短。同时运用加权系数将多g 标优化蛔题转化为单目标优化问 题。 4 设i = 卜了套遗传算法求解公交车辆调度闽题。此箕法l _ ) 适应度暖数为经过转 换的舞标氆数；在选择时主体使用比例选挥；交叉孵采翻双点交叉算予；变 异科采用倒位变异算子；同时运用傈留精英策略。对优化模型进行编程、优 化汁算与分桥。 5 车辆稍度系统的设诗及应用实例。给出了车辆调瘦系统的改再思巷，系统框 架，系统流程。爿二将所研究的车辆调度模型邱优化鲤法，应用盔西安审车瓠 稠度中，对西安市蹄网中一给定任务下的物流配送问题和西安j 悟2 9 路公交 车的勰度闯题，制定了车辆调度方案。 沦文的结构安排鞫所做的一作相对应，各章的具体安摊如下： 第- 章：绪论。介绍了论文的选题意义鄱背景，阐述了智能运输系统。 i 车葺| i 凋度 晒北工业大。硕士学位论文第一章绪论 的研究意义和国内外研究发展情况，指出其中存在的问题，对全文的主 要工作和论文的组织结构予以简单介绍。 第二章：数学理论基础。介绍了论文中用到的一些数学理论知识，包括规划知i u 介绍和i 智能优化算法介绍。规i , j i 识。 j 介绍了线性规划、整数规划、细 合优化和算法复杂性以及非线性规划。智能优化算法中介绍丁粒子群算 法、模拟退火算法以及遗传算法。 第三章：给定任务下的车辆调度问题。给出了给定任务下的车辆渊度模，对模 型进行了分析与讨论。设i i 了混合粒子群优化算法，对算法进行了详尽 的描述。最后进行了仿真试验和结果分析。 第四章：给定线路下的车辆调度问题。给出了给定路线下的车辆训度问题中公交 车辆调度的模型，对模型进行了分析与时沦。设计了一套遗传算法，对 算法进行了详尽的描述。最后进行了仿真试验和结果分析。 第五章：车辆调度系统设；t + 及应用实例。给出了车辆调度系统的设计思想以及系 统整体框架和流程。并对两安市路网中一给定任务。f f ( , j 物流配送问题和 西安市2 9 路公交车的调度问题，制定了车辆调度方案。 第六章：结论与展望。简要回顾并总结了论文的j i 作，同时对论文的研究工作提 出了有可能改进的方i 勾。最后给出了未来的主要研究工作。 第二章基础知识 2 1 规划知识介绍 2 1 1 线性规划 第二章基础知识 线性舰划是运筹学的一个重要分支，其相关理论随着单纯形法的提出( 1 9 d 7 年美国学者d a n t z i g ) 已日趋成熟，因此在实际中的应用相当j “。泛。特别是在交 通运输领域的研究中，线性规划已成为重要的研究手段之一。 线性规划问题的一般形式为： r a i n z = c i x i + + c n x 。 j f a 。l x l + a ，2 x 2 + + d x 。= b ，i = l ，p d ，i 石i + a i 2 x 2 + 十a l n x ，b ，i = p 十1 ( 2 - 1 ) x ，0 ，j = l ，q x ， o ) ，j = q + j r ，” jr ：i lz 。i = 1 ，”，为待定的决策变量，已知的系数d 。组成的矩阡 臼i ia i2a l n 日2 la 2 2 a 2 h ( 2 2 ) 称为约束矩阡。al 1 9 歹 j 向量记为a ，j = 1 ， ：a 的行向量记为a ，7 i = i ，月7 。 如果原问题足求f i 标函数c ，x ，的最大值，可等价地转换为( 一c ，x ，) 的最小 ，一1 i = 1 值。 线性规划其它的定义、性质祠i 求解方法者f l7 l i 参魁1 1 天文献 5 5 , 5 6 1 等，这r l t - v 再 赘述。 阳北r 业大学硕士学位论文 第二章基础知识 2 1 2 整数规划 本文给定任务下的车辆调度问题属于整数规划问题，因此很有必要对整数规 划的相关知识、方法进行阐述。 部分或全部决策变量必须取为整数的数学规划问题叫整数规划 5 5 】，仅仅不 考虑整数约束条件时，余下的约束条件和原目标函数构成的规划问题称为该整数 规划的松弛问题，相应地，该整数规划被称为其松弛问题的原问题。如果该整数 规划的松弛问题是一个线性规划，则其同时又称为整数线性规划。整数线性规划 的标准形式为： r a i n ( o rm a x ) z = c 7 ( 2 - 3 ) f 肚兰( 吖= ，吖) 6 。 f t = ( x l ，x 2 ，x 。) 。0 ( 2 - 4 ) i x ，r ：，工。z 按照对决策变量的不同要求，整数线性规划可分为以下几科一类型： 全整数线性规划：约束矩阵和资源向量的各个分量都是整数的整数线性规划； 混合整数线性规划：决策变量中有一部分可以不取为整数的整数线性规划： 0 1 整数线性规划：决策变量只是取0 或1 的整数线性规划。 根据以上定义，本文中的给定任务下的车辆调度问题是o - 1 整数线性规划 ( 对于约束条件中的含有非整系数或常数的情形，都可经过简单处理化为令整数 线性规划) ，都属于整数线性规划。 2 1 3 组合优化问题和计算复杂性 本文给定任务下的车辆调度问题属于强n p 组合优化难题问题，这里有必要 介绍一下组合优化问题和计算复杂性 5 7 1 的相关知识。 1 组合优化问题定义 组合优化问题又称离散优化问题，是一类重要的优化问题。随着计算机科学、 管理科学和现代化生产技术等得日益发展，这类问题与| 1 俱增，越来越受到运筹 学、应用数学、计算机科学及管理科学等诸多科学的高度重视、虽然某些组合优 化问题有悠久的历时渊源，被费马( f e r m a t ) 、欧拉( e u l e r ) 等众多著名数学家 研究过，但作为运筹学的一个独立分支而发展壮大起来还是近几十年的事。它是 一门新兴的学科分支。 整数线性规划问题在很多时候是很繁的，一r 作景大，且没有一个普遍“有效” 心北一l 业大学硕士学位论文第二章基础知识 的解法，这里的“有效”指的是较快的得到最优解。困难的关键是要求变量取整， 或为o 一1 变量，也就是说变量是离散取值。这就给我们提出一个问题：是否可 以具体问题具体分析，从问题本身出发，利用问题的特性寻找解决办法呢? 组合 优化问题的研究就是这样的。下面给出组合优化问题的定义： 组合优化问题是在给定的约束条件下，求目标函数最优值( 最小值或最大值) 的问题。组合优化问题的一个实例可以表示为一个对偶( s ，厂) ，其中解空间s 为 可行解，目标函数厂是一个映射，定义为 r ：s 呻r 求目标函数最小的问题称为最小化问题，记为 m i n f ( i ) ，i s 求目标函数最大值的问题称为最大化问题，记为 m a x f ( i ) , i s 显然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转换。 使目标函数取最优值的解称为最优解( 整体最优解) ，定义为： 设 ，。) 是组合优化问题的个实例，i 。，s 。称i ，为最小化问题 m i n f ( i ) , i s 的最优解，若 f ( i 。) 兰厂( f ) 对所有i s 成立。 2 计算复杂性 算法或问题的复杂性一般是问题规模n 的函数，时问复杂性记为r ) ，空问 复杂性记为s ( n ) 。问题的时间复杂性是指求解该问题的所有算法中时f n j 复杂性最 小的算法的时间复杂性。类似地，可以定义问题的空间复杂性。 在算法分析和设计巾，沿用实用性的复杂性概念，即把求解问题的关键操作， 如加法、乘法、比较等运算指定为摹本操作，然后把算法执行基本操作的次数定 义为算法的时 u 复杂性：算法执行期问占用的存贮单元则定义为算法的空削复杂 一眭。在组合优化问题中，比较和搜索常被指定为基本操作。基本操作的执行次数 随问题规模的增长以一定方式增 吏。 在分析复杂性时，可以求出算法的复杂性函数厂( n ) ，也可以方便地用复杂性 函数主要项的阶o ( j 0 ”表示。若算法4 的时间复杂性是乃( ”) = o 如o ) ) ，p ( n ) 是 n 的多项式函数，则称算法a 为多项式时问算法。 按照计算复杂性理论研究问题求解的难易性，可把问题分为p 类、n p 类和 瞬北 业大学硕士学位论文 第二章基础知识 n p 完全类。问题复杂性的形式定义可用图灵机( t u r i n g m a c h i n e ) 计算模型给出。 如果一个问题有解它的多项式时间d t m ( 确定性图灵机) 程序，则称该问题属 于p 类。p 类阔题是指其有多项式辩阔算法的闯蘧。如果一个问题有解它的多顼 式时闻n t m ( 确定型图灵机) 程序，则称该闽题属于n p 类。n p 类问题是指 可在多项式时问里检验的问题类，至今尚未找到多项式时间算法。n p 完全问题 是n p 类中最难的问题。 求n p 完全阀题的最优解，需要阎题规摸的指数阶时翊，褒翔题规模增大时， 往往由于时间的限制而丧失可行性。用近似算法如贪心法求解n p l h 题，在多项 式的时间里，只能给出近似最优解。 2 1 4a # 线性规划 本文的给定线路下的车辆凋度属于非线性规划问题，这里介绍一下非线性规 划1 58 | 的相关知识。 非线性规划属于静态优化( s t a t i co p t i m i z a t i o n ) 或有限维优化( f i n i t e d i m e n s i o n a lo p t i m i z a t i o n ) 的范畴。在应用领域内提出的许多最优化 ( o p t i m i z a t i o n ) 闯题中。有一些所对应的数学模型1 5 8 1 具有如下结构： 第“是最优化翅题的变量，印所考察的瓣题可归结为优选若予个拣为参数或 者变量的量x ，x ：，x 。这些变量都取实数值，可用中的n 维向量 x = ( 一，x ，) 简记，这罩，r ”表示普通的n 维e u c l i d 空问，记号“t ”表示 矩阵运算转髯。 第二二是媛优化问题的约束，设问题中对变量墨，托，k 所煳l ! l 勺限铡或约束 可以用这些变量满足的如下等式和不等式表示出来： g ，( x 1 ，x 2 ，x 。) 0 ，i = 1 , 2 ，一，m ， ( 2 - 5 ) 。( x 1 ，x 2 ，- ，x 。) = 0 ，= 1 , 2 ，- 一，p( 2 - 6 ) 第三是最优化问题目标，设璇优化问题的目的是在约束限制下确定变量 一，x ：，一，r 。的取值，使得某n 个实函数f ( x 。，z ：，x 。) 取得极大值或极小俄( 最 大谴或最小值) 。f ( x ，f ：，# 。) 称为这一最优化澜题中豹鳐搽函数，最优佬就是 优选变量x 使厂( x ) 极大化( m a x i m i z e ) 或极小化( m i n i m i z e ) 。 注意到极大化f ( x ，x ：，x 。) 相当于极小化一( x ，x ：，x 。) ，我们只讨论如 下形式的数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) ： ( m p ) m i n f ( x ) 曲北 ：业大学硕士学位论文第二章基础知识 “僦盛篆j p ， 其中，g ，( 1 i m ) ，hs ( 1 j p ) 定义于某个r l 维区域d cr ”，记号r a i n 为m i n i m i z e ，含义为极小化，s t 是s u b j e c tt o 的缩写，其意为“受限制于”或“受 约束于”。 当目标函数、约束函数中至少有一个不是x 的线性函数h , j ，数学规划( m p ) 便称为j ：线性规划。 非线性规划的一般形式也可记为： ( n p ) r a i n f ( x ) i g ，( x ) 0 , 1 i 蔓卅：h ( x ) = 0 , 1 ，p ( 2 - 8 ) 其中厂，g ，( 1 i ) ，h ，( 1 p ) 不全为x 的线性函数。 2 2 智能优化算法介绍 2 21 粒子群算法 粒予群算法简称为p s o 算法，是一类基于群智能( s w a r mi n t e l l i g e n c e ) 的 随机优化算法【5 ”。p s o 的基本概念源于对鸟群捕食行为的研究，它可以形象地 描述为：假设一群吗在随机搜索食物，在这个区域罩只有一块食物。所有的鸟都 小知道食物在那里，但是它们知道当前的位置离食物还有多远，那么找到食物的 最优策略是彳f 么昵? 最简币有效的就是搜寻目前离食物最近的鸟的周围区域。 在p s o 中，每个优化问题的解都是馊索空问中的一只l 马，被称之为“粒子”。 所有的粒子都有一个由被优化的函数决定的适应值( f i t n e s sv a l u e ) ，每个粒子还有 一个速度决定他们b 翔的方向和距离。然厉粒子们就追随当前的最优粒子在解空 m 。t i 搜索。 p s o 初始化为一群随机粒子( 随机解) ，然后通过迭代找到