（管理科学与工程专业论文）基于双层规划的多目标校车路径优化研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着我国政府对教育的大力推广，校车运输在交通运输行业里开始扮演 越来越重要的角色。校车运输问题一旦解决不合理，不仅会造成学校资源的 浪费，而且也会对家长和学生的学习生活带来不便，同时还会增加整个交通 运输系统的负担。因此，对校车路径优化问题( s c h o o lb u sr o u t i n g p r o b l e m ，s b r p ) 进行研究具有重要的理论和现实意义。 本论文在对相关文献分析的基础上对校车路径优化问题进行了较为系 统的研究，不仅从校方角度考虑如何进行停车站点和行驶路径的安排，而且 引入了学生对乘车站点的一种自主选择行为，综合考虑了学校和学生两方面 的决策影响。主要进行了以下几方面的工作： 第一章明确提出了校车的基本定义和校车路径优化的问题描述。在对 相关文献进行总结的基础上，回顾了国内外关于选址一路线安排问题 ( l o c a t i o n - - - r o u t i n gp r o b l e m ，l r p ) 和校车路径优化问题的研究成果，总结 了目前校车路径优化研究的特点，并对校车路径优化问题的研究意义和本论 文的基本框架进行了介绍。 第二章对本论文问题研究的理论基础进行了探讨，分别介绍了双层规 划和遗传算法的基本理论。 。第三章研究了单校车路径优化问题。首先对本论文所研究的单校车问 题进行了描述，在充分考虑学生乘车站点的选择对学校路径决策的影响下构 建了双层规划模型，并进行了遗传算法的设计和对算例的求解。 第四章研究了多校车路径优化问题。在第三章研究基础上，将校车数 量由一辆增至多辆，提出了多校车路径优化问题的双层规划模型，并设计了 算法和算例。 最后，在论文结论部分对研究工作进行了总结，给出了论文的主要研 究成果，并对研究中存在的局限及未来研究工作进行了展望。 关键词：校车路径优化；双层规划；遗传算法 西南交通大学硕士研究生学位论文第页 a b s t r a c t w i t ht h e q u i c k l yd e v e l o p m e n t o fe d u c a t i o ni no u rc o u n t r y , s c h o o l t r a n s p o r t a t i o nh a sp l a ya l li m p o r t a n tr o l ei nt r a n s p o r t a t i o ni n d u s t r y o n c et h e s c h o o lb u sp r o b l e mw e r es o l v e di m m o d e r a t e l y , i tw o u l dn o to n l yw a s t et h e r e s o u r c eo fs c h o o l ，b u ta l s ob r i n gl o t so fi n c o n v e n i e n c ef o rs t u d e n t sa n dt h e i r p a r e n t s s o af u r t h e rr e s e a r c ho ns c h o o lb u sr o u t i n gp r o b l e mi so fg r e a t i m p o r t a n c et h e o r e t i c a l l ya n dr e a l i s t i c a l l y t h i sd i s s e r t a t i o na n a l y z e sr e l a t e dl i t e r a t u r e sa n di ta s s u m e st h a tas e to f p o t e n t i a ls t o p sa g eg i v e n ，a sw e l la sas e to fs t u d e n t st h a tc a nw a l kt oo n eo rm o r e o ft h e s ep o t e n t i a ls t o p s t h e r e f o r e ，w en o tj u s tt od e c i d et h el o c a t i o no fs c h o o l b u ss t o p sa n dt h er o u t i n go nt h es i d eo fs c h o o l ，b u ta l s ot a k ei n t oa c c o u n tt h e c h o i c e so fs t u d e n t s o b v i o u s l y , t h eb u ss t o p sc h o i c e so fs t u d e n t sw i l lh a v ea n i n f l u e n c eo nt h ed e c i s i o n - m a k i n go ft h es c h 0 0 1 n em a i nc o n t e n t so ft h i s d i s s e r t a t i o na r ea sf o l l o w e d ： i nc h a p t e r1 ，w ei n t r o d u c et h ed e f i n i e n so fs c h o o lb u sa n ds b r p b a s e do n t h es u m m a r yo fr e l a t i v er e f e r e n c e ，w e r e t r o s p e c t ed o m e s t i ca n df o r e i g n r e s e a r c h e r so nt h ea c a d e m i cc o n t e n to fl r pa n ds b r et h e n ，w ep o i n to u tt h e i m p o r t a n c eo f t h er e s e a r c ho ns b r pa n di n t r o d u c et h ef r a m eo ft h ep a p e rs i m p l y i nc h a p t e r2 ，t h et h e o r yo fr e s e a r c hi sd i s c u s s e d b e s i d e s ，t h et h e o r yo f b i l e v e lp r o g r a m m i n ga n dg e n e t i ca l g o r i t h mi sa l s oi n t r o d u c e dr e s p e c t i v e l y i nc h a p t e r3 ，t h es c h o o lb u sr o u t i n gp r o b l e mw h i c hh a so n l yo n eb u si s d i s c u s s e d t a k i n gi n t oc o n s i d e r a t i o no ft w od e c i s i o n - m a k i n go ft h es c h o o la n d t h es t u d e n t sa tt h es a m et i m e , w ep r o p o s eab i l e v e lp r o g r a m m i n gm o d e la n ds o l v e t h ep r o b l e m u s i n gt h eg e n e t i ca l g o r i t h m i nc h a p t e r4 ，t h es c h o o lb u sr o u t i n gp r o b l e mw h i c hh a sm o r et h a no n eb u si s d i s c u s s e d w ea l s od e v e l o pab i l e v e lp r o g r a m m i n gm o d e la n ds o l v ei tu s i n gt h e g e n e t i ca l g o r i t h ma st h ec h a p t e r3 i nt h ec o n c l u s i o n , t h em a i ni n n o v a t i o no ft h ed i s s e r t a t i o na n dt h ep e r s p e c t i v e f o rt h ef u t u r er e s e a r c ha r ep o i n t e do u t k e y w o rd s ：s c h o o lb u sr o u t i n gp r o b l e m ，b i l e v e lp r o g r a m m i n g ，g e n e t i ca l g o r i t h m 西南交通大学囱南父逋大字 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文， 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密西使用本授权书。 ( 请在以上方框内打“”) 学位做作者签名缌荡 指导老师始玄军 日期：窍占- 日期：对占y 西南交通大学囱南父逋大罕 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本论文的研究做出贡献的个人 和集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由 本人承担。 本学位论文的创新点如下： 1 通过对成都公交站点进行实际考察，将所搜集的样本进行统计分析， 得到了车辆单位人数上车时间与总上车人数的非线性函数表达式。 2 充分考虑了学校在站点选址和路径安排决策与学生在乘车站点选择 决策时的互相影响机制，引入了学生上车时间函数和学生站点选择的偏好， 分别针对单校车和多校车情况构建了双层规划模型，反映了学生乘车站点选 择对学校站点和路径决策的影响。 学位论文作者签名：琅蛮 日期：谤年莎月z , z e t 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 。1 问题提出及研究意义 交通运输行业是国家经济发展的一个重要指标，它与人民的生活息息相 关。随着我国政府对教育的不断重视，特别是九年义务教育政策的推广，校 车运输行业也得到了相应的发展。据相关资料预计嗍，在本世纪初期，全国 小学数量将达到4 6 5 万所，在校生1 4 0 0 0 万人左右；全国初中学校将达到 7 万所，在校生6 8 0 0 万人左右；全国幼儿园将达到1 3 万所，在园幼儿( 包 括学前班) 3 0 0 0 万人左右。在我国大部分地区，尤其是大中城市，大批中 小学生和幼儿园的学生在上学和放学时，都是乘坐学校组织开行的校车。事 实上，校车的日常运行与维护在学校整个教育花费中占了相当重要的比重。 国外有关资料表明，校车的投入费用同样非常巨大。根据b r a c a 等的研 究报道，2 0 世纪9 0 年代中期，纽约约有8 3 0 0 0 名学生乘坐由教育委员会租 用的校车。当时每学年接送所有这些学生需要租用约1 1 5 0 辆汽车，该市租 用一辆汽车及其司机的年费用约为8 万美元。因此，该项费用的年度总预算 接近1 亿美元。而在加拿大安大略的达拉谟，约有i 3 的学生乘坐由教育委 员会组织开行的校车，该项运输服务的年花费为九百万加【婀。 如果校车问题不能得到合理的解决，一种情况可能使得学校的校车投入 数量多于实际需要，或者使校车的行驶站点和路径不尽合理，从而导致支出 增加，造成了一定程度的浪费；另一种情况则可能使得学生所花费的乘车时 间较多，造成了学生家长的抱怨。除了校车所涉及的这两个直接利益相关者 以外，由于校车的行驶时间一般是城市上下班的高峰时期，校车问题也必然 对高峰时期的交通运输造成影响。因此，对校车问题进行科学合理的优化调 度就显得十分必要。 概括起来，对校车优化问题的研究，主要有以下几点意义： 1 通过对校车路径优化问题进行研究分析，得到较合理的校车路径，一 方面可以减少学校投入校车数量，节约成本；另一方面可以缩短学生等待时 间和校车总行驶时间，提高服务质量；除此以外，通过减少校车路径的数量， 避开交通易堵塞的路线，有助于城市交通的发展。 西南交通大学硕士研究生学位论文第2 页 2 对于校车路径优化问题的研究能为其他企业职工通勤车、公交车调 度、物流企业车辆线路优化等提供相关的理论指导和方法，起到一定的借鉴 作用。 3 作为车辆路径问题的一个重要分支，对于校车路径优化问题的研究将 有助于车辆路径理论的进一步发展与完善。 1 2 校车路径优化问题概述 1 2 1 校车路径优化问题基本定义 机动车运行安全技术条件( g b7 2 5 8 2 0 0 4 ) 新标准首次给出了校车 的明确定义：用于运送不少于5 名幼儿园、小学、中学等教育机构的学生 及其照管人员上下学的客车和乘用车。 校车路径优化问题( s b r p ) 是车辆路径问题中典型的混合服务问题，主 要研究如何有效的利用校车车队在上学前到各站点将学生接到学校，以及放 学后将学生从学校运送往各站点。问题一般定义为：对一系列已经确定或待 确定的停车站点，确定合适的校车数量，安排学生的乘车站点，组织适当的 行车路线，在满足一定的约束条件下( 如车辆运载能力限制和送达时间限制 等) ，使运输总成本与服务水平质量之间达到满意的均衡。 1 2 2 校车路径优化问题分类 按照不同的标准，校车路径优化问题综合起来大致可以分为以下几种t 按车辆对车场的所属关系，有车辆开放问题和车辆封闭问题；按学校( 车场) 数目，有单学校( 车场) 问题和多学校( 车场) 问题；按路途长远，有城市 问题和乡村问题；按每辆车所装载的学生所属学校，有混装问题( 同一时间 同一校车上可以装载不同学校的学生) 和不混装问题( 同一校车上只装载一 所学校的学生) ：按校车路径的优化目标个数，有单目标校车路径问题和多 目标校车路径问题。 西南交通大学硕士研究生学位论文第3 页 1 2 3 校车路径优化问题与车辆路径问题特点比较 校车路径优化问题( s c h o o lb u sr o u t i n gp r o b l e m ，s b r p ) 可以看作是 一类特殊的车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，妒) 。v r p 由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出。该问题一般定义为：对一系列发货点和 或收货点组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束 条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、 时间限制等) 下，达到一定的目标( 如行程最短、费用极小、时间尽量少、 使用车辆数尽量少等) 嗍。 由上述两个问题的定义可以看出，校车路径问题与v r p 有着紧密的联 系，两者均是在一定约束条件下主要通过行驶路径的安排来达到一定的目 标。但是，校车路径问题由于其实际的应用背景，又与传统v r p 存在着不同： 首先，两者在服务对象上有所差异。校车的服务对象是学生，学生具有一般 货物所不具备的主观判断性和选择性，其作出的判断和选择可能会影响学校 对站点和路径的整个决策结果；其次，校车路径问题每天的出车时刻、频率 以及行驶路径相对固定。因此，每一次的优化决策结果都具有长期的应用价 值；再次，由于学校每天的上下课时间都有统一规定，校车路径问题通常比 传统v r p ( 如，典型的邮递员和旅行商问题) 有更加严格的时间要求。 1 3 国内外研究现状述评 1 3 1 校车路径问题研究现状 1 关于多目标校车优化问题的研究 针对一所学校的情况，b e n n e t ta n dg a z i s ( 1 9 7 2 ) 首先提出了在车辆载 重量约束条件下最小化学生总旅行时间的单目标单约束校车问题。随着研究 的不断深入，校车问题由开始的单目标向多目标转化。现阶段研究以多目标 研究为主，并且优化目标越来越接近实际应用环境。根据校车问题类型，按 照目标函数和约束条件对校车路径问题重要的研究发展进行了如下表1 - 1 的总结。 西南交通大学硕士研究生学位论文第4 页 表1 - 1 多目标校车优化研究发展 年份问题研究 1 9 7 0n e w t o na n dt h o m a s ( 1 9 7 4 ) 【1 7 】提出了在车辆载重量约束和学生行驶时 间约束条件下最小化总行驶时间和路径数目的多目标多约束校车问 题。 1 9 8 0d u l a ce ta l ( 1 9 8 8 ) 1 1 7 就单学校提出了在车辆载重量约束、站点约束 和路径长度约束条件下总行驶距离与路径总数乘积最小的校车问 题。 1 9 9 0b r a c ae ta l ( 1 9 9 4 ) 嘲为解决纽约市五个区的校车调度问题，在考虑 允许同车混装情况下，引入了接送学生的最早时间，同时还对每条 路线所接送的最小学生人数进行了约束，并采用c - w 节约算法对模 型进行了求解。 ， r b o w e r m a n ，b h a l l ，p c a l a m a i ( 1 9 9 5 ) p 】提出了在车辆载重量 约束、每条路径行驶时间约束和总旅行时间约束条件下考虑了每个 学生到可选站点的最长行走距离，并将学生总的行走距离最小化作 为一个目标函数处理。 2 0 0 0 a c o r b e r a n ，ef e r n a n d e z ，ml a g u n a rm a r t i ( 2 0 0 2 ) 【1 】以最d 、化 学校运行时间和运输成本为目标，按照两条初始路径的最短旅行时 间建立候选清单( c a n d i d a t el i s t ) ，在满足所有约束条件的前提下， 根据清单将旅行时间增量最小的一对路径合并。 郎茂祥，胡思继( 2 0 0 4 ) 鲫基于将客户直接排列的解表示方法，构造 了一种求解多目标车辆路径问题的新的禁忌搜索算法，寻优性能得 到有效提高。 jp a c h e c o rm a r t i ( 2 0 0 6 ) 【1 6 j 以最小化车辆数量和学生最长行驶时 间为目标，首先利用节约算法得到初始解，在此基础上，保持初始 路径数目不变，使用禁忌搜索使学生的最大行驶时间尽可能小。 s p a d a m ，b i e r l a i r e m l i e b l i n g ( 2 0 0 5 ) 鲫在固定车辆数目的情 况下寻求学生服务质量，定义了延迟时间和等待时间作为学生服务 的量化标准。在无车辆数目约束条件下，根据路径长度增量最小化 原则每车的初始行驶路径，再重复使用增量最小化原则完成路径的 合并。 西南交通大学硕士研究生学位论文第5 页 郭强，郭耀煌( 2 0 0 6 ) 【3 4 】以社区儿童接送服务车辆的路线优化问题为 研究对象，针对多车场校车问题建立了多目标非线性整数规划模型， 并设计了构造最小生成树的启发式算法对模型进行了有效求解。 h u e y - k u oc h e n ( 2 0 0 6 ) 等【1 4 】针对实时v 】妞将车辆路径和出发时间作 为决策变量，构建了混合整数规划模型。 n i c o l a sj o z e f o w i e z ( 2 0 0 8 ) 等 2 0 1 从实际应用和问题目标两个方面对 多目标v r p 进行了分类评述，指出目前存在的重复研究和解决策略 比较单一等问题。 2 关于带时间窗的路径优化问题的研究 s o l o m o n 和d e s r o s i e r s 等最早对带时间窗的车辆路径优化问题进行了 研究，将时间约束加入到一般的车辆路径问题中；d e s r o c h e r s 进一步对用 于求解该问题的各种优化方法做了简明的总结概括嗍。b r i a nk a l l e h a u g e ( 5 】 则主要对过去近三十年来解决带时间窗的车辆路径优化问题的精确算法进 行了总结。 在硬时间窗方面，l y o1 i 和zf u 1 7 】对带装载能力约束的硬时间窗校车 问题进行了详细研究，构建了多目标数学模型并设计了一种以k 短路为基础 的两阶段启发式算法。n a b i l aa z i 等( 1 9 1 针对易腐品硬时间窗多路径运输问 题提出了一种两阶段精确算法。该算法第一阶段基于无约束最短路求得可行 路径，第二阶段加入约束在可行路径中得到满意解。彭国勇和吴升【档】使用了 插入法与遗传模拟退火相结合的启发式算法对带有硬时间窗约束车辆路径 问题进行了求解。 在软时间窗方面，y i n g j i ez h o n g ，m i c h a e lh c o l e m 9 l 设计一种局部搜 索启发式算法，解决了带软时间窗的回程车辆路径优化问题。h e r m i n i ai c a l v e t e 等【1 2 】针对带软时间窗的中小型运输问题，提出了一种列举优化启 发式算法。g b a l v a r e n g a 1 0 】以总旅行时间为目标函数，为带软时间窗的车 辆路径问题设计了一种两阶段混合遗传算法。阎庆和邰蕾掣明用一种新的交 叉算子保证已经达到最优化的子路径不被破坏，并且在判断可行解时采用了 模拟退火法的一些技术，构成一种混合遗传算法实现了对有时间窗约束的车 辆路径规划问题的求解，这种混合遗传算法对软时间窗和硬时间窗均具有可 行性。 3 关于校车定位一运输路线安排问题的研究 西南交通大学硕士研究生学位论文第6 页 r o b e r tb o w e r m a n m 介绍了校车定位一运输路线安排问题( s c h o o lb u s l o c a t i o n r o u t i n gp r o b l e m s ，s b l r p ) 的特点，并对目前解决s l r p s 的两种 主要启发式算法思路：l a r ( 1 0 c a t i o n a l l o c a t i o n r o u t i n g ) 和 a r l ( a 1 1 0 c a t i o n r o u t i n g l o c a t i o n ) 分别进行了概述，同时分析了两者的优 缺点。l u cc h a p l e a u 1 8 l 等针对城市密集区学生分布集中的情况，使用a r l 启 发式算法对问题进行了求解。p a t r i c ks c h i t t e k a t ，m a r cs e v a u x ，k e n n e t h s i r e n s e n m 针对学生可以选择二个及多个站点乘车的情况，在校车总行驶路 程最小的目标下，构建了整数规划模型确定每辆校车的行驶路径以及每个学 生的的乘车站点，并设计一种基于i p 公式法( i pf o r m u l a t i o n ) 的精确算法 对模型进行求解。 4 相关综述性研究 s p a d a m 【韧等从问题分解、模型构建和算法设计三个方面对校车优化研 究成果进行了简单介绍。l y ol i ，zf u 1 7 】从问题类型、目标函数和约束条件 对校车路径优化问题进行了列表总结。m l f i s h e r m l 】把车辆路径优化问题的 研究方法总结为三个阶段，并详细介绍了各阶段的起始时间和特点。 c h a i y a r a t a n a ，n a l z a l a ，a m s t 6 从算法理论和算法应用两方面，对遗传 算法的在当时的发展作了回顾。 1 3 2 选址一路线安排问题研究现状 对于选址一路线安排问题的研究，早在2 0 世纪6 0 年代，已经有类似的 概念被提出。c o o p e r 在7 0 年代把选址问题与运输问题结合起来，正式提出 了选址一路线安排问题( l o c a t i o n r o u t i n gp r o b l e m ，l r p ) 。 l r p 可以表述为：给定与实际问题相符的一系列客户点和一系列潜在的 设施点，在这些潜在的点中确定出一系列的设施位置，同时确定出一套从各 个设施到各个客户点的运输路线，确定的依据是满足问题的目标( 通常是总 费用最小) 。客户点的位置和客户的需求量是已知的或可估算的，货物由多 个设施供应，每个客户只接收来自一个设施的货物，潜在设施点位置已知， 问题是把哪些潜在的设施建立起来，以满足目标蚓。与经典的v r p 研究相比 较，l r p 不仅考虑了车辆在各个客户点间巡回访问的路线问题，它同时寻求 对设施选址和车辆路径选择的优化，因此该问题比v r p 更加复杂。 西南交通大学硕士研究生学位论文第7 页 1 关于配送中心定位运输路线安排问题的研究 解决配送中心l r p 的方法通常采用多阶段法，即把原来的问题分解为两 个或多个小问题分别逐一加以解决。t a i - h s iw u ，c h i n y a ol o w ，j i u n n w e i b a i 勰l 将物流系统配送中心多站点l r p 问题分解为l a p 和v r p 两子问题并分 别利用模拟退火算法进行了求解。j a c o b s e n ，m a d s e n 以报纸配送系统为研 究背景，引入了三种启发式算法来解决三层系统的l r p 问题。在此基础上， s r i v a s t a v a 通过加入一些环境因素对研究问题进行了完善。张潜 e l 等针对 集成化物流系统中配送中心的l r p ，提出一类基于假设前提的特殊l r p 问题 的模型及两阶段启发式求解方法。第一阶段采用启发式规则将客户进行最小 包络聚类分析为若干子类，确定设施及每个设施所要提供服务的客户群；第 二阶段采用改进遗传算法求解同一客户子类中的优化运输路线。 随着研究的发展深入，一些研究者也开始设计出各种将l r p 作为一个整 体进行求解的启发式算法。c h i e n 试图利用向题的空间特征，采用两个不同 的估计值来预计每条配送路线上的运输成本，以此来解决无约束的实际l r p 问题【吲。p e r l 和d a s k i n 第一次系统的描述了仓库定位运输路线安排问 题( w a r e h o u s e1 0 c a t i o n r o u t i n gp r o b l e m , w l r p ) ，提出了一种以连续的方 式求解修正1 l r p ( m o d i f i e dw l r p ) 的方法呻l 。p h h a n s e n ，b h e g e d a h l 等 【2 1 l 在此基础上，针对修正w l r p 提出了一种更加有效且更加与实际相符的启 发式算法，并对算法进行了实现。张长星和党延忠即l 提出了一种求解l r p 的 改进遗传算法，该算法没有基于分阶段求解的思路，而是将l r p 的解看作一 个整体，从而减小了在进化过程中停滞于局部最优解的概率，提高了遗传算 法的计算效率和计算速度。 2 相关综述性研究 林岩等【柏1 从l r p 的发展历程、分类和解决方法几个方面对物流系统中的 l r p 研究现状进行了全面的评述。h o k e ym i n a 等【1 3 1 对过去近三十年来l r p 的 相关文献进行了非常详实的回顾和比较，并通过对l r p 的分类反映出目前研 究的缺陷和不足，同时对未来更加有现实意义的研究方向给予了展望。 1 3 3 研究现状小结 从已有的文献可以看出，相对于v r p ，校车优化问题的研究还比较有限。 西南交通大学硕士研究生学位论文第8 页 概括起来，目前国内对校车问题的研究侧重于管理制度的规范制订，涉及对 校车路径的优化研究的文献较有限。国外对校车问题的研究主要呈以下几个 特点： 1 针对站点已经确定的情况下进行路径和学生乘车站点分配的校车路 径问题，已经提出了一些有效的模型和算法，其重点是在以往的研究成果上 进行目标函数和约束条件的完善，或者是算法的设计和改进。 2 在对校车路径问题研究中，对上车时间的衡量一般是基于单位人数上 车时间相同的假设。而在实际应用环境中，单位人数的上车时间是与上车总 人数等因素相关的。 3 对于s b v r p 的研究，多数学者侧重于从学校角度来进行站点和路径的 决策，虽然也通过引入最小化学生总乘车时间，最小化学生总步行距离等目 标函数或者约束条件来提高整个校车的服务水平，但是依然忽略了学生乘车 站点的自主行为对学校决策过程的影响。 1 4 论文研究框架 1 4 1 研究目标 本论文利用车辆路径优化等相关理论，充分考虑了学校站点和路径决策 与学生对乘车站点自主选择决策的互相影响，通过引入学生偏好和由实际考 察统计得出的上车时间函数，分别针对单校车和多校车路径优化问题构建了 双层规划模型，并设计了遗传算法和算例。通过确定合理的站点和路径，一 方面降低学校校车运输成本，另一方面提高学生乘坐校车的满意度。 1 4 2 研究内容 本论文的研究内容主要包括以下几个方面： 1 校车路径优化问题研究现状分析 校车路径优化问题一直以来得到了许多学者的关注，因此有必要在进行 正式的模型和算法分析之前对国内外关于选址一路线安排问题以及校车路 径优化问题的研究成果进行较为详实的介绍。 西南交通大学硕士研究生学位论文第9 页 2 单校车路径优化问题研究 单校车情况在许多中小规模的私属幼儿园比较普遍。通过综合考虑学生 对乘车站点的选择所导致的学校站点和路径决策的修正，建立了双层规划模 型，引入了由实际考察所得的学生上车时间函数和学生在进行乘车站点选择 时的偏好，结合模型特点设计了遗传算法，并通过随机生成数据对双层规划 模型和一般混合整数规划模型进行了比较，同时对算例进行了求解。 3 多校车路径优化问题研究 多校车情况一般集中出现在提供校车运输服务的中小学校。由于校车数 量不止一辆，因此学校除了需要作出基本的停车站点和行驶路径决策以外， 还需要就每辆车的行驶路径确定其在各个站点的上车人数。在单校车双层规 划模型基础上，针对多校车的不同特点，重新构建了多校车的双层规划模型， 并提出了算法和算例。 西南交通大学硕士研究生学位论文第1 0 页 第2 章校车路径优化研究相关理论 2 1 校车路径优化研究因素描述 校车服务的日常运营过程一般如下：早晨，校车从学校出发，分别开往 各线路的第一个上车点，并沿着预定的路径行驶，将沿途各站点的学生接上 车，然后在上课时间前把他们准时送往学校。学生需在规定的时间内到达站 点等候班车。下午放学时，校车在学校接上学生，沿着预定的路线，将学生 分别送往他们早晨上车的站点，然后返回到学校。 由校车路径优化的基本定义和其一般运营过程可以看出，校车路径优化 问题的主要决策变量包括校车总数量的确定、停车站点的选择、行驶这些站 点的顺序以及学生乘车站点的安排。 2 1 1 对学生乘车站点选择行为的描述 1 3 3 节中已经简单提到，在以往的校车优化问题中，研究者主要是从 学校的角度来进行这些变量的决策。虽然随着研究的不断深入，目标函数或 约束条件中加入了学生的乘车时间或最大步行距离等。但是，所研究的优化 问题依然是从学校的角度来安排规定学生应在哪个站点乘车，学生的乘车时 间最小化或者步行距离最小化的优先级一般是低于学校运输成本最小的优 先级。而在实际生活中，学生虽然无法直接确定校车的停车站点和行驶路径， 但是学生对自己的乘车站点是具有选择权的，即学生通常会根据校车的行驶 站点和路径来综合判断，最后选择合适的站点乘车。而学生的这种选择行为 事实上经常是超出学校的控制范围，并且学生对乘车站点的选择将间接影响 学校的运输成本控制和服务质量，从而影响学校对站点和路径的决策。本论 文将根据实际情况充分赋予学生对自己乘车站点的选择权利，并通过双层规 划模型考虑学校与学生之间决策的互相影响，使两者达到满意。 考虑到学生在进行乘车站点选择时，一方面会考虑步行时间的长短，另 一方面也会对校车到达站点的时间保持关注。当站点一旦选定时，学生在早 上出行时通常会选择步行时间尽量短并且校车所到达的时间尽可能靠后的 西南交通大学硕士研究生学位论文第1 1 页 站点，所以本论文将学生群乘车站点的选择函数g 盥定义为：g 豇= 仇c 口一 ( 卜聃) d ；。这里的学生群是指由学生的居住地址所确定的集合，每个学 生群中的学生其居住地域相同或相邻，且每个学生群的人数小于单车容量。 其中，气表示学生群z 到站点i 的步行时间；d i 表示校车从第一个站点沿既 定路径到达站点i 所花费的行驶时间，d i = d ；( y ；，知) 表示也是站点选择 变量y ；和路径变量气的函数，当停车站点和行驶路径确定以后，d ；就成为 已知参数；，7 j ( o s 叼，1 ) 表示学生在进行站点选择时的偏好概率。由站点 选择函数g 。可以看出，学生群将选择函数g 口值最小( n - t 为负) 的站点作为 其乘车站点。 2 1 2 对学生乘车站点选择偏好的描述 学生在进行乘车站点选择的时候，会对影响其作出决策的一些因素( 如， 步行时间，对站点本身的喜恶以及车辆到达站点的时间等) 有所衡量。而不 同的学生可能会对这些因素有不同的偏好，在不同的偏好选择下乘车站点的 最终结果可能也会不同。 本论文通过引入学生站点偏好概率仇( o s ，7 ，s1 ) 从步行时间和校车到 达站点的时间两方面对学生群的站点选择偏好进行研究。，7 ，的值越大，说明 学生群在进行站点选择时越重视步行时间，而对车辆到达时间的关注程度较 小。反之，说明学生群比较关注车辆的到达时间而对步行时间的关注次之。 不同学生群在站点选择时对于步行时间和校车到达站点的时间偏好往往是 不同的。因此，7 ，一般会随着学生群的不同而有所差异。 西南交通大学硕士研究生学位论文第1 2 页 2 1 3 对单位人数上车时间的描述 以往路径优化问题都是在假设单位乘客上车时间相同的情况下进行车 辆总运行时间的计算。但是，在实际的运行过程中，乘客的上车时间与站点 乘坐该车的总候车人数是相关的。为此，作者选择了对成都九里堤站点，香 榭里站点和交大路西站点进行实际考察。将这三个站点作为考察对象，主要 是因为九里堤站点是始发站点，车辆行驶到这三个站点时一般都还没有满 载，这与校车不能超载的情况相符。通过对所收集的约2 0 0 个样本进行整理 分析，如果不考虑车型( 如单扇门，双扇门) 差异和刷卡投币系统故障等意 外情况，发现单位乘客的上车的确与同一站点的乘坐该车的总候车人数成一 定的函数关系。将车辆在站点i 总上车人数所消耗的停滞时间定义为t 一， 通过拟合得出，i n t 一与上车总人数的对数大致存在着如图2 一l 的函数关系： i n t 二= a ，c l n 善嘞c ，+ b j 贝i j r = e 4 。1 n 荟工口c i + 6 。 图2 - 1 上车停滞时间与上车总人数的对数函数关系 西南交通大学硕士研究生学位论文第1 3 页 2 2 双层规划基本理论 双层规划( b il e v e lp r o g r a m m i n g ) 是在研究非平衡经济市场竞争时首先 提出的。b r a c k e n 和m c g i l l 在1 9 7 3 年提出了双层规划数学模型。1 9 7 7 年， 在c a n d l e r 和n o n t o n 的科学报告中，正式出现了双层规划和多层规划名词。 从2 0 世纪8 0 年代起，双层规划开始引起大家的关注。双层规划的研究在数 学规划领域里有了迅速的发展，现在已经成为一个新的运筹学分支。 2 2 1 双层规划问题特点 双层规划问题一般描述为；上层先给定一个决策，下层各子系统则以这 个决策为参量，根据自己的目标在可能的范围内选定一个最优决策，并将自 己的最佳反应反馈给上层，上层再在下层的最佳反应的基础上，在可能的范 围内作出整体的最优决策。 双层规划研究的是两个各具目标函数的决策者之间按有序和非合作方 式进行的相互作用，上层决策者优先作出决策，下层决策者在上层决策信息 下按自己的利益作出反应，由于一方的行为影响另一方的的策略选择和目标 的实现，并且任何一方又不能完全控制另- - 方的选择行为，因此上层决策者 要根据下层的反应做出符合自身利益的最终决策【6 1 】。 双层规划问题的一个重要特点是可以应用在双层决策问题中，在两个层 次上的决策者都有其各自的目标函数，在某种程度上，本层的决策空间是由 另一层决定的。此外，本层上的决策者通过特定的方法和手段影响另一层的 决策制定，从而达到优化其自身目标函数的目的。双层规划问题的另一个重 要特点是决策变量的控制权分别属于各层的决策者，而在传统的单层规划 中，决策者同时控制所有的决策变量。但在很多的实际决策过程中，对决策 变量的控制和处理并不是同时进行的，而是采用自上而下的双层决策方法。 在双层规划中，以优化自己的目标函数为目的的决策者在高层决策者事先确 定决策变量值之后，对自己能控制的决策变量进行优化，以达到最优目的。 双层规划比单层规划具有优势，包括能够明确建模表示顺序决策过程的能 力，能够明确表示不同层次优化过程或不同决策系统之间的相互作用的能力 【钥。 西南交通大学硕士研究生学位论文第1 4 页 2 2 2 双层规划模型数学描述 在双层规划模型中，不同的决策者控制着相应的决策变量，并优化各自 的目标函数。一般来说，双层规划模型可用如下的数学关系进行描述【4 4 j ： 上层规划模型为( u ) 目标函数：m i n f ( x ，y ) 约束条件：g ( x ，y ) s0 其中y = y ( x ) 由下层规划模型求得 下层规划模型为( l ) 目标函数：m i n f ( x ，y ) 约束条件：g ( x ，y ) 墨0 由上可知，双层规划模型由上层规划模型( u ) 和下层规划模型( l ) 组 成。f 是上层规划所确定的目标函数，x 为上层规划的决策变量，关系式 g ( x ，y ) s0 是对变量x 的约束：f 为下层规划所确定的目标函数，y 为下层规 划的决策变量，关系式g ( x ，y ) 墨0 是对变量y 的约束。 在双层规划模型的上层规划模型中，上层决策者通过设置的值影响下层 决策者，因此限制了下层决策者的可行约束集，而下层决策者的行为反过来 又会通过y 的值影响上层的决策。因此下层决策变量y 是上层决策变量x 的函数，即y = y ( x ) ，这个函数一般被称为反应函数。一个好的决策很大程 度上取决于这个反应函数。 2 2 3 双层规划应用概述 双层规划方法与传统的单层规划方法相比具有比较显著的优势，具体表 现在：首先，双层规划可以同时分析决策过程中两个不同的、相互矛盾的目 标；其次，双层规划多价值准则的决策方法更接近实际情况；另外，借助双 层规划可以明确表示上级决策部门和公众的相互作用凹。 从2 0 世纪8 0 年代起，国内外学者开始将双层规划应用在实际问题中， 使双层规划得到了快速的推广。概括来说，目前双层规划已经应用到交通领 域的网络设计、旅行商需求估计、交通控制，管理领域的资源分配、定价和 供应链管理。除此以外，双层规划在工程设计方面也有所应用。单连龙，高 西南交通大学硕士研究生学位论文第1 5 页 自友【3 2 】根据城市公交网络的具体特点建立了上层为标准公交网络设计模型、 下层为平衡配流模型的双层规划模型，并针对所提出的模型，设计了基于灵 敏度分析的求解算法。崔广彬，李一军p 1 1 使用双层规划法建立了供应链二级 分销网络中的设施选址、车辆运输路线安排、库存控制的集成优化模型，解 决了在给定的多个潜在设施点中选出一系列设施的位置，并确定巡回运输路 线，以及巡回运输路线上客户的最佳订货量的问题。刘志刚，申金升1 4 2 按照 区域公交调度模式，建立了公交调度系统中时刻表生成和车辆调度之间的双 层规划模型。 2 3 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是模拟生物在自然环境中的遗传和 进化过程而形成的一种自适应全局优化概率搜索算法，目前己经成为解决复 杂问题的一种有效的启发式方法。启发式算法是指一种基于对过去经验的归 纳推理以及实验分析来构造的算法，目标是在可接受的花费( 计算时间、占 用空间等) 下得出待解决问题的满意解，而不一定是最优解。启发式算法一 般流程如下图2 - 1 r 靳 。 西南交通大学硕士研究生学位论文第1 6 页 图2 - 1 启发式算法一般流程 2 3 1 遗传算法的基本流程 遗传算法把问题的解表示成染色体，在算法中即以二进制编码或自然数 编码的串。首先在执行遗传算法之前，给出一群染色体，即假设解。然后， 把这些假设置于问题的“环境中，并按适者生存的原则，从中选择出较适 应环境的“染色体力进行复制，再通过交叉，变异过程产生更适应环境的新 一代染色体群。这样，一代一代地进化，最后就会收敛到最适应环境的一个 染色体上，即问题的最优解。 遗传算法_ 般流程如图2 2 f 6 1 】所示。 西南交通大学硕士研究生学位论文第1 7 页 图2 - 2 遗传算法算法一般流程 2 3 2 遗传算法的特点 遗传算法基于自然选择和基因遗传学原理，将适者生存这一基本进化 理论引入串结构。伴随算法运行优良基因被逐渐保留并加以组合，从而不断 产生出更好的个体，使整个群体向前发展。归纳起来，遗传算法主要有以下 几个方面的特点0 0 ： 。 西南交通大学硕士研究生学位论文第1 8 页 1 遗传算法同时对搜索空间中的多个解进行评估，具有较好的全局搜 索性能，有效防止搜索过程收敛于局部最优解； 2 遗传算法的处理对象不是参数本身，而是对参数集进行