城市定制公交线路设计研究 65页

学校代号10536学号13201060151分类号U49密级公开全日制专业学位硕士学位论文城市定制公交线路设计研究学位申请人姓名刘喜指导教师胡列格所在学院交通运输工程学院专业学位类别工程硕士专业学位领域交通运输工程（交通运输规划与管理）校内导师姓名及职称胡列格（教授）校外导师姓名及职称石兆（副教授）论文提交日期2015年04月07日 学校代号：10536学号：13201060151密级：公开长沙理工大学硕士学位论文城市定制公交线路设计研究学位申请人姓名刘喜指导教师胡列格所在学院交通运输工程学院专业学位领域交通运输工程（交通运输规划与管理）论文提交日期2015年04月07日论文答辩日期2015年5月24日答辩委员会主席符卓 TheResearchonTheRouteDesignofUrbanCustomizedShuttleBusbyLiuXiB.E.(ChengnanCollege,ChangshaUniversityofScience&Technology)2013AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinTrafficandTransportationEngineeringinChangshaUniversityofScience&TechnologySupervisorProfessorHuLieGeMay，2015 长沙理工大学学位论文原创性声明本人郑重声明：所丑交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加ｙ■标注引用的内容外，本论文不包含任何其他个人或集体已结发采或撰写的成巧作品。对本文的研究做出軍嬰贡献的个人巧集体，均己巧文中明确方式标明。本人完全意识到本卢明的法律巧果山木人承扭。＾＾作存籠名：曰卿：＾沒＾年＾月学位论文版权使用授权书本巧化论义作嘗亢全了解巧校軒关化廚、使用学化论文的规定，問窓学校保巧并向围家巧关部ｎ或机构送交论文的复印件和电子版，允许论文被巧阅和借阅。本人授化长沙珊工大学可Ｗ将本学化论文的全部或部分内容编入钉关数据库进巧检柴，Ｗ封采用搔印、缩印或描等复制乎段保巧和汇编本学化论义。问时授化中岡科学技术巧息硏究所将本论文收处到《中巧学位论文伞文数据库》，并砸过网络向社会公众提化信息服务。本学位论义始于１、保稱□，化年解密后适用本授仪１５。２、不保密团。。＂（巧在段上相应方枢内打Ｖ）化荐签名：Ｈ朋：年Ｖ月诚ｊＩ：巧师豁名［］期年月诚ｎ制賊為ｆ／ 摘要随着城市交通拥堵问题和居民通勤现状问题的凸显，发展和探索多元化公共交通服务模式已经成为城市交通发展的必然趋势。定制公交，作为在新形势下提出的多元化客运服务模式，既很好的解决了大部分上班族舒适、便捷的通勤需求，又有效提高道路利用效率、缓解了城市早晚高峰期的道路通行压力。本文对定制公交线路设计问题的研究，是整个定制公交运营发展的核心问题和重要环节，不仅对提高定制公交的实践价值具有很重要的作用，而且还有助于在VRP问题理论上的深度研究。文章分析了在大背景环境下，定制公交及其线路设计研究对于城市交通以及居民出行的理论意义及实际价值。其次，从早期关于“定制”服务模式的探索到现状定制公交的快速发展，得出定制公交发展的必要性和趋势。与此同时，在国内外对定制公交相关研究较少的情况下，分别从前期资源配置、票价机制、站点选址布局等方面进行了问题的归纳和解决，并以此为铺垫引出了本文的问题研究重点。通过对定制公交乘客需求特征和实际运营特点的深入思考，分析和解决了运营组织管理和资源配置问题，采用k-means算法来解决定制公交站点的选址与布局，得出了最优化站点的选址方法；建立了以最小化营运里程为优化目标的线路设计模型，并设计模拟退火算法进行求解，找出了符合定制公交运营特点的线路规划方法。此外，通过选取西安市高新国际作为定制公交问题实例进行分析，验证了定制公交线路设计模型和算法的可行性。综合看来，本文对线路设计问题的研究，对定制公交系统理论的丰富和发展具有一定的贡献，对其他城市开通通定制公交、解决交通拥堵问题有很好的借鉴意义，从而为我国的可持续发展作出积极贡献。关键词：定制公交；站点布局；线路设计；模拟退火算法Ⅰ AbstractWiththedeteriorationofurbantrafficjamaswellastheworseningcommutesituation,aninevitabletrendofurbantrafficsustainabledevelopmentliesinthedevelopmentandexplorationofadiversifiedcustomizedbusservicemode—customizedshuttlebussystem.Itcannotonlysatisfythemulti-levelanddiversifiedtraveldemandofthepassengers,butalsoenhancetheroadutilizationefficiencyandbenefitthecommutersbyalleviatingtrafficjamintherushhour.Thestudyontheroutedesignofcustomizedshuttlebusisservedasthecentralpartofwholeoperationsystem,whichisbothbeneficialtotheadvancementofitspracticalvalueandconducivetothefurtherresearchandtheoreticalstudyofVRP.Thisthesis,tobeginwith,analyzesthetheoreticalmeaningaswellaspracticalvalueofstudyoncustomizedshuttlebusanditsroutedesignforurbantransportationandpassengers’travel.Next,itwilldiscussthenecessityandtendencyofdevelopingcustomizedshuttlebusfromtheexplorationof“customization”servicemodeatearlystagetoitscurrentrapidgrowth.Meanwhile,asrelatedstudyiscomparativelyrarenow,thepaperwillreachaconclusionandsolutionfromresourceallocation,pricemechanism,andstationdistribution,etc..Thenitwillcometothesummitofthisstudy—theadoptingk-meansalgorithmforthebestchoiceofstationthroughthoroughconsiderationofitspassengercategoriesandoperationfeatures.Fourth,Itseeksoutanapplicableroutedesignmethodforcustomizedshuttlebusconstructionviaanoptimizationmodelonthebasisoftotaloperatingmileage,andadoptionofSA(simulatedannealingalgorithm).Finally,thepaperwillverifythepracticabilityofroutedesignthroughcomprehensiveresearchandstudyontheHigh-techZoneinXi’ancity.Ingeneral,Theoptimizationstudyontheroutedesigninthisthesiscanenrichanddevelopthecustomizedshuttlebussystemtoacertainextent,provideanapplicablesolutionandsolidexampleforthetrafficproblemsinothercities,andpresentanactivesupporttothesustainabledevelopmentofourcountry.KeyWords:customizedshuttlebus;stationdistribution;routedesign;SA(simulatedannealingalgorithm)II 目录摘要.....................................................................IAbstract.................................................................II第一章绪论..................................................11.1研究背景及意义.....................................................11.2研究综述...........................................................21.3主要内容及结构安排.................................................5第二章定制公交发展及相关理论分析..................................72.1定制公交起源及发展.................................................72.2定制公交的必要性分析..............................................102.3定制公交发展问题分析..............................................152.4相关理论分析......................................................172.5本章小结..........................................................23第三章定制公交配置问题与优化方法.................................243.1定制公交前期资源配置..............................................243.2定制公交票价机制..................................................283.3定制公交站点的优化布局............................................303.4定制公交线路设计..................................................323.5本章小结..........................................................34第四章定制公交线路设计模型与算法分析............................354.1问题的描述........................................................354.2定制公交线路设计模型构建..........................................354.3模型求解思路......................................................384.4算法设计..........................................................394.5本章小结..........................................................42第五章案例研究......................................................435.1背景..............................................................435.2通勤现状与需求分析................................................435.3线路设计方案......................................................465.4本章小结..........................................................50结论与展望.............................................................511本论文的主要结论...................................................512主要的创新点........................................................523有待进一步研究的问题................................................521 参考文献...............................................................54致谢....................................................................572 第一章绪论1.1研究背景及意义1.1.1研究背景近年来，随着城市化进程快速拓展，城市中心区域成为了集写字楼、酒店和商业为一体的综合中心，外围则聚集成为居住集中区域，导致了越来越多的城市居民职住分离的现象逐渐凸显严重。在此城市发展的背景下产生了如下的交通出行困境：居民上班出行的平均通勤距离增加，通勤时间过长，城市交通的日益拥堵不断降低了小汽车的快捷性与舒适性，持续低效的常规公共交通服务水平依旧不能提高居民出行对其的选择概率。尽管当前许多城市采取新增公交和地铁规模的方式来实现公共交通系统的规模化和提升其整体的服务水平。但是随着经济的发展和生活水平的提高，越来越多的城市居民在出行需求方面，开始呈现多样化、个性化的出行趋势，现状的城市公共交通骨干网络的覆盖范围、服务模式等已然无法很好的满足城市居民的多样化出行需求。因此，发展多元化公共交通的必要性和重要性逐渐进入到了人民的发展意识当中。为了迎合这些需求，“互联网+城市交通”新业态在中国快速发展，符合分享经济发展趋势的预约、合乘等车辆服务模式也逐渐兴起，客运市场产生了诸如定制公交、预约出租车、通勤班车、专车等新型客运模式。与传统客运模式相比，这些新型客运模式的显著特征就是为乘客量身定制，具体又表现在是否预约和是否合乘两个方面。具体如下表1.1所示。表1.1多元化客运服务模式示意表属性特征合成不合乘预约定制公交/预约合乘出租车专车/预约非合乘出租车不预约常规公交/轨道交通/BRT扬招出租车1.1.2研究意义在2013年7月30日召开的中央政治局会议当中，明确提出了“积极释放有效需求，推动居民消费升级”的要求。对于准点、舒适、便捷的通勤需求在当前交通出行者中还1 没有很好的被满足，大力发展多元化城市公共交通便成为了解决问题的方法和发展城市交通的必然趋势。中共中央政治局委员、国务院副总理马凯在2014年的一次调研视察中指出：目前北京公交集团推出的定制公交商务班车作为新型的客运服务模式，有效的缓解了首都交通拥堵、减少了私家车出行比重、降低了污染物的排放，可在今后的发展过程中，加大宣传和研究工作力度，积极扩大线路覆盖区域。本文研究的定制公交，在新形势的客运服务模式探索中，作为革命性创新的新概念被提出，既很好的解决了大部分上班族多样化、舒适、便捷的通勤需求，促进了居民消费的升级，又有效的降低了私家车的出行比重，缓解了城市早晚高峰期的道路通行压力。鉴于定制公交实际运营的特性，与普通公交运营方式相比，既有一定的联系，又有很大区别。因此，如何合理的将它融入到现有的客运服务模式当中，发挥其独有的优势和特点，需要从运营模式和线路布局方法等方面来不断完善和深入研究。定制公交路线设计问题是整个定制公交运营发展的最主要部分，既涉及到了停车站点的确定，又与前期资源配置问题密切相关。因此，合理的设计线路将各合乘站点的预约乘客接送到目的地，是定制公交的核心问题和重要环节。重点研究其路径优化问题，不仅对提高定制公交的实践价值具有很重要的作用，而且还有助于在VRP问题理论上的深度研究。同时，在研究该问题的过程中需同步考虑的运营组织管理和资源配置问题，对其他城市开通通勤商务班车有借鉴和指导的现实意义。1.2文献综述鉴于定制公交的大背景和研究意义分析，以下从定制公交所涉及到运营发展模式、站点选址布局、车辆路径以及公交线网优化等方面展开相关研究的分析和综述。（1）定制公交运营模式目前，我国在定制公交所涉及问题的研究深度和研究范围还处于起步阶段。但是随着城市交通问题的提出和多元化交通模式的发展，越来越多的学者开始致力于与其相关[1]的研究。其中，徐康明教授（2013），探讨了定制公交服务的概念，对定制公交的服务要素、开行条件、开通意义和优势等做了较为系统的分析和研究，并在文中指出未来[2]在其他城市多层次发展定制公交的现实意义和发展趋势。李震宇、胡欣竹（2014），探讨了定制公交服务的主要特点，分析了其在国内主要城市的发展情况，并进一步研讨了中国杭州等大城市的定制公交发展前景，为解决交通拥堵的提供了新思路。李彬（2013）2 [3]，调查探讨了大中城市居民出行方式的变化趋势带来的紧迫任务，通过北京定制公交的发展现状和开通定制公交所需要的必备流程和注意事项分析，得出了在部分大众城市[4]发展定制公交的可行性。程立勤（2014），巧妙的改进了节点重要度方法，将其运用到定制公交的站点选址布局当中，建立了基于节点重要度的选取模型，在点线面相结合的层次分析过程中研究了定制公交线网布局方法，为促进定制公交系统的快速发展提供[5]了理论依据。张露（2014），探讨了城市商务班车的运营模式，并提出了相关可行的建议，对其他城市开通通勤商务班车有一定借鉴意义。国外对于定制公交的研究主要集中在与其相关的通勤行为上。汉密尔顿(Hamil-ton)[6]（1982），首先提出了与通勤班车相关的“浪费通勤”概念。Seliaman（2001）在研究中指出如何有效的利用仿真方法来确定行车路线和中途停车站点，文章以平衡交通流为设计线路目的，对实际调查的数据进行分析处理，建立相关模型和采用仿真方式验证，得出了各线路相对平衡的结果。国内外对定制公交研究成果多是集中在发展模式以及与其相关的通勤行为特征等的探讨上。对定制公交进一步的理论研究和发展而言，运营模式的探讨是非常关键的一个因素，具有一定的实际意义。（2）站点的选址与布局定制公交在国内属于一种新兴起的多元化客运服务模式，对站点的选址布局问题方面的研究甚少，研究主要停留在常规公交或者其他公共交通方式的站点选址布局上。[7]叶英杰（2014），将选址布局抽象成聚类问题进行分析，把空间co-location模式挖掘技术应用在城市公交站点选址分布规律的研究当中，为公交站点布局的合理选择提[8]供了可行思路和参考依据。高选幸等（2013），以线路优化为研究对象，首先对分布分散在城市各个地点的教师接送站点，采用K‐means聚类算法进行区域划分，然后再将[9]改进的蚁群算法运用到对各区域运行线路设计模型的验证当中。王林等（2009），总结分析了常规公交站点的选址原则，从站点位置、对其他线路的影响以及站点交通大小等方面来阐述选址的影响因素，建立模糊评价方法来评价站点设置的优劣性。张富（2012）[10]，从站点安排和校车路线设计两方面综合考虑，建立了乘客到达站点的距离偏差最小与所有乘客到达站点的总的距离最小的双目标站点选址模型，并得到了很好的验证。吕[11]林（2006）在文献中，从站点位置、站点形式、站点数量及站点容量等几个方面展开分析和讨论，分别得出了响应的优化设计方法。3 与常规公交站点选址与布局不同的是，定制公交的站点的选址布局主要是基于预约乘客的出行需求，目的地需求完全一致的情况下设置的。（3）车辆路径问题研究定制公交线路设计所涉及到的车辆路径问题，是在乘客站点和目的站点之间存在一[12]致性需求的前提条件下提出的。类似于定制公交的路径优化问题，党兰学（2013），分析了校车路径中运营成本目标、服务质量目标、公平性服务目标三种优化目标和相关约束条件之间的关系，对求解方法进行了回顾和总结，在文献[13]中，以车辆数最小和营运里程最短为优化目标，建立了求解大规模混载校车路径规划问题的模型和相关优化算[14]法。赵冬玲（2014），针对车辆路径规划问题提出了一种新型蚁群算法，实现了车辆[15]路径规划中最短行驶里程和最小化车辆数的优化目标。洪联系（2012），将动态车辆路径规划问题分解成一系列延迟快照，建立动态规划模型，提出双缓冲区改进大领域的[16]搜索算法。余明珠等和李建等（2010），将记录更新法与禁忌或VNS结合，构造了[17]确定性模拟退火算法对车辆路径规划问题进行求解。王杰（2013），建立了连续多目标优化模型，灵活的结合了LK局部搜索和非支配领域免疫算法的优势特点，总结提出了模型求解的新算法。[18]国外在求解车辆路径问题的研究中，Kim（2012），在使用匈牙利算法生成车辆[19]调度顺序后，继续采用启发式算法进行改进。Euchi和Mraihi（2012），将蚁群算法与大邻域搜索算法（VNS）进行结合，提出了校车路径规划问题的混合算法。Groer等[20](2010),设计的VRP框架中实现了多种算子来改进路径，包括one-pointmove，two-pointmove，two-optmove，or-optmove，three-optmove，three-pointmove，crossexchangemove。[21]Bent和VanHentenryck（2006），首先将模拟退火算法应用到求解最小化车辆线路的模型当中，结合大领域搜索算法，最终将路线安排的总运输费用降低到最低。（4）公交线网优化国外许多学者早在20世纪60、70年代就着手研究公交线网优化问题。Valerie[22]Guihaire（2010）以换乘次数、间隔均匀度、车队数目和线路长度为优化目标，以停[23]靠时间和运行时间等为约束条件建立了公交线网优化模型。RalfBorndorfer（2010）构建了以运营成本和乘客出行时间为优化目标，直接连接能力和换乘次数为约束条件的[24,25]线网优化模型。国内研究方面，王炜（2006）是较早研究的学者之一，他先后提出了一种“逐条布设、优化成网”和“一路一线”的公交线网优化方法。王毅之（2014）4 [26]，分析对比了当前线网优化方法的利弊，充分的利用了节点度和节点介数的连接关系，[27]建立了对应的公交线网优化模型，在一定程度上保证了网络效率。魏华（2014）提出了换乘衔接空间布局优化模型与设计方法，研究了轨道交通与常规公交衔接优化问题。[28]俞洁（2014）研究了含特殊需求的接驳公交服务区域与路径优化问题，建立了一个同[29]时求解最优服务区域和车辆服务路径的双层混合整数线性规划模型。高健（2014）以最优化的公交线网和发车频率为优化目标,从时空协调的角度对城市公交线网进行优[30]化,达到居民出行顺畅、换乘便捷、交通供给和需求平衡的目的。姬海（2015）依靠现有地理信息系统和交通分析模型,从线网布局、站点选址以及运营管理等方面分别进[37]行分析，设计了实践性和针对性较强的智能公交线网优化系统。高健（2013）基于居民出行行为,建立了城市公交线网时空协调优化模型,并设计启发式算法求解模型。徐[38]笑梅等（2012）为了满足低碳出行的要求,从优化线网的角度建立了基于低碳理念的公交线网双层优化模型。针对建立的模型,给出了运用遗传算法求解公交线网双层优化模型的方法和步骤。并用算例说明了所建立模型与求解算法的合理性与可行性。经过多年的理论探索，学者们根据不同背景下的公交线网情况提出了各种优化方法，成果均是建立在不考虑预约服务的前提下。综合上述国内外相关研究综述，国内外针对定制公交运营模式以及与其相关的路径优化、线网布局以及站点选址布局问题展开的研究工作，为本文定制公交的研究积累了丰富的知识基础，提供了较为科学有利的依据。1.3主要内容及结构安排本文主要依托城市交通问题的大背景和定制公交的兴起和发展，根据预约乘客出行特点和出行分布情况，对定制公交运营组织、站点选址、线路设计理论及方法展开研究。具体内容的章节结构组织如下：第一章：绪论。本章是论文的基础，在当前城市快速发展的过程中，提出以城市交通拥堵问题、多元化发展城市公共交通和“互联网+城市交通”新业态在中国的快速发展为论文研究背景，得出本文研究定制公交意义以及重点研究线路设计问题的意义。其次，在分析与定制公交相关的理论研究基础上，提出了文章的主要内容及结构安排。第二章：定制公交发展及相关理论分析。结合早期对“定制”服务模式的探讨和国内部分城市定制公交发展现状的情况，分析我国相关城市的居民通勤的特征和公共交通5 存在的问题，提出了发展定制公交的必要性。其次，对定制公交所需要研究问题的相关基础理论进行抽象和提出，为之后研究提供了思路和方法。第三章：定制公交配置问题及优化方法。根据定制公交相关问题的抽象和提出，确定了定制公交线路设计研究所要涉及到的方面和重点研究方向。在相关理论的基础上，提出前期资源配置方法、票价机制的确定方法、站点选址和线路设计的优化方法。第四章：定制公交线路设计模型及算法分析。本文研究的重点是定制公交线路设计，从公司最运营成本和服务水平的角度出发，结合定制公交实际开通过程中需要满足的容量、距离、时间等约束条件，建立定制公交线路设计优化模型。其次，希望运用智能优化算法求解模型，得出定制公交最优化解和线路设计方案。第五章：案例研究。将通过在西安市高新区高新国际开通定制公交作为实例来分析研究，验证模型以及算法的可行性以和开通的实际操作性。结论及展望：归纳和总结了本文的主要研究结果，分析了本文研究的主要创新点，提出了在今后研究过程中需要进一步探讨研究的问题的方向。6 第二章定制公交发展及相关理论分析定制公交，也称通勤商务班车，主要包括广州“楼巴”、社区通勤快车等早期的特殊服务模式和现状运营的定制公交。主要是通过预约合乘的方式，为那些具有相同出行特征和出行需求的特定人群量身制定的一种客运服务模式，具有“定点、定时、定价、定人、定车”的特点。“定点”即设置预约合乘点；“定人”即服务对象仅限预约乘车；“定时”即车辆仅在预约时间范围内到达合乘预约站点；“定车”即预定舒适车型，保证一人一座，一站直达；“定价”即制定介于常规公交和出租车之间的收费标准。因此，本文将对定制公交系统的相关问题与基础理论进行总结与分析。2.1定制公交起源及发展2.1.1早期服务模式的探索对于“定制”这一特定说法，早期主要以“楼盘巴士”、“社区通勤快车”等特殊客运服务模的形式存在。这些多样化的定制服务模式的逐步探索，为后期“定制公交”服务模式的发展积累了丰富的经验。（1）广州“楼巴”自1994年起，广州部分地区的房地产开发商为了提升自身楼盘开发的价值，提高业主购买的吸引力，开通了楼盘巴士运营线路往返于郊区的居民住宅区与商业中心区之间。在小区未成形交付时，“楼巴”是为潜在购买业主看房时免费提供的一种便利出行服务方式。当小区正常成形使用后，“楼巴”作为一种有偿使用的交通工作成为了楼盘小区居民出行方式的一种有效选择。据了解，目前广州“楼巴”运营主要集中于番禺区内，共有约20个大型居住楼盘开通了运营巴士，配车240台左右，主要发车方向为广州市中心天河、越秀地区以及部接驳地铁站点。广州“楼巴”作为公共交通的重要补充，在公共客运体系中发挥了一定作用，但是在发展的过程中，运营管理上的问题也逐渐凸显出来。据现状调查分析，主要存在以下几点问题：1）“楼巴”的部分运营车辆车况较差、缺少公众监督和有效管理；7 2）缺乏正规运营停靠站点，随意上落客对周边的道路交通秩序造成了很大的干扰；3）主要针对楼盘小区中的居民服务运营，对象过于单一，导致了线路的服务范围过窄、上座率不足；4）由于上座率不足等问题的突出，楼巴运营商为降低经营成本，降低了楼巴发车频率，造成服务水平下降。乘客出行的便利性和合理的经济效益是“楼巴”持续发展下来的主要因素，但是随着其规模效应和运营成本的不断攀升，绝大部分“楼巴”运营都处于亏损状态。相关运营参与者迫于楼巴运营的成本压力，对开通楼巴的态度开始转变消极，希望通过完善公交服务，来逐步代替目前的楼巴运营。（2）北京“通勤快车”随着经济的增长和城市化进程的快速拓展，北京市大规模的郊区化和城市空间重构导致了职住分离的通勤问题越来越严重，“潮汐”通勤交通流现象也变得更加突出。为了应对职住分离严重和“潮汐”通勤交通流突出等交通通勤问题，北京公交集团于2013年3月尝试开通了四种特殊模式的客运通勤快车：采用普通公交车辆的“点对点”快速直达模式、采用普通公交车辆的“早高峰”特定公交模式、采用商务班车的专车专座通勤模式（专座通勤快车）、“单位通勤班车”的快速服务模式。目前北京开通了3条“专座通勤快车”线路，这种运行模式的特性主要体现在发车频率、站点布设、运营距离限制等方面。经过两年的实际运营经验，通勤快车为之后进一步提出的以市场为导向的“定制公交”积累了丰富的经验。2.1.2定制公交的发展现状随着当前客运市场所面临的新形势以及早期相关运营模式的探索经验积累，近年来，“定制公交”这一新型公交服务模式在国内逐步兴起，已经成为北京、青岛、大连、昆明、哈尔滨、天津等城市交通发展的新趋势。（1）北京定制公交北京定制公交（商务班车），是往返于居民小区与工作单位之间的一站式直达的交通服务模式。运营单位在开通线路之前，首先拟定需要开通定制公交的方向和区域，通过网络服务平台、电话、微信等形式收集乘客的预约出行需求。其次，按照前期过程中所调查和收集的数据信息，分析出乘客出行需求特征，设计定制公交线路。运营时间的8 安排主要根据乘客要求到达时间和途中可能花费的时间来确定，既保证了“一人一座”的舒适乘车环境，又避免了乘客的多次换乘和时间损耗。据相关调查统计,2013年9月至2014年4月，北京累计开通定制公交线路71条，日发车班次109个班次，日送乘客2600余人次，有效的缓解了北京市上下班高峰期的道路拥堵和写字楼集中地的停车压力，也为其他城市在定制公交的推广和发展上奠定了基础。（2）青岛定制公交类比于北京定制公交的运营模式，2013年8月，青岛市交运集团某旅游公司也率先开启了定制公交模式的运营，4个月时间的推广和发展，也逐渐形成了自己的定制公交运营模式，开通了4条定制公交线路。参考北京定制公交的运营模式，青岛定制公交是按照调查、处理、设计的思路进行线路设计。即首先通过构建定制公交网络服务平台的形式，收集潜在顾客的客流需求信息（包括乘车方向、站点、时间要求），后考虑当前城市道路的交通状况和乘客的出行特征情况，设计合适的定制公交线路为乘客提供定制公交服务。区别于北京定制公交的站点设置形式，青岛定制公交先是拟定了行车线路，后设置站点，既确保了以服务乘客为中心，又保证了线路设计不太受站点设置的影响。青岛定制公交有自己独特的管理体系和模式，采取全方位、全时段监测车辆运行轨迹和运行状况进行车辆监督管理，即确保了运营调度过程中的准时准点性，又保障了乘客乘坐定制公交的安全。图2.1定制公交车型图图2.2乘客凭票上车（3）其他城市继北京定制公交开通后，截至2014年4月，大连市通过团体订购以及学校订购的形式共开通6条定制公交线路，每条线路根据正常工作日安排运营时间，根据距离的长短安排票价（单程票价为10元左右），开通以来受到了广大上班族的强烈反响，每辆车运营的上座率都比较高。9 昆明市根据城市客运枢纽的结构布局，于2014年3月，开通了东部客运站至昆明火车站、东部客运站至西部客运站两条定制公交线路，成为了市区公共客运市场的一个很好补充，连接了重要的交通枢纽节点，在为乘客提供了快捷方便的同时也起到了交通枢纽客流快速集散作用，获得了公众的良好反响。在其他一部分城市定制公交逐步发展的前提下，哈尔滨市于2014年2月开通了2条定制公交路线，均可在公交专用道上行驶。相比于线路上的普通常规公交，行车时间节约一半，方便了乘客的日常出行。2.2定制公交的必要性分析当前，随着城市化进程的加快和向外拓展，一方面居民的平均通勤距离增加，通勤时间增长；另一方面公共交通持续低效的服务水平导致了人们的出行结构逐渐发生变化，私家车出行比重越来越大，两种情况的相互影响导致出现了更加严重的交通拥堵问题。因此，类似于定制公交模式的多元化公共交通方式，具有重要的发展现实意义。2.2.1城市通勤出行现状（1）职住分离，通勤距离长当前，相关企业由于政策因素、环保要求以及企业自身的运行成本控制等原因，于城市开发区或者郊区等距离城市中心区域较远的建成。其次，城市中心聚集成为商业、文化、政治、金融复合型中心，导致周围的房价得以快速增长，上班族普遍居住在距离中心地区较远的居住区。综合来看，城市中上班族职住分离现象严重、通勤距离增加。通勤距离主要是通过上下班往返时间过来体现，据相关调查数据显示，2013北京、上海、天津居民的平均通勤时间均超过1小时，分别为1.44、1.32、1.26小时，西安市二环以内的居民集中区，通勤往返的时间为1.14小时，如下图2.3所示。1.510.50北京上海天津西安图2.3部分城市上下班通勤时间分布示意图10 在城市居民正常的出行行为时间分布当中，早晚时间段的通勤出行占据了全天出行总量的绝大部分。2009年上海市的第四次综合交通调查数据显示，早晚出行集中在一天的7：00—8：00和16：00—18:00上，分别占全天出行总量22.5%和26.5%，如图2.4。30.00%16:00‐18:0025.00%7:00‐8:0020.00%15.00%12:00‐14:0010.00%8:00‐10:0014:00‐16:0018:00‐20:005.00%0:00‐7:0022:00‐24:00,10:00‐12:000.00%图2.4出行时间分布图（2）出行方式的变化趋势出行方式是指居民在出行前所选择的交通工具或手段，主要包括步行、自行车、小汽车（包括私家车和出租汽车）、常规地面公交、轨道交通等。经过多年的发展，我国很多城市在机动化发展的过程中，选择步行和自行车来出行的居民并没有过多的向公共交通转移，反而选择了购买私人小汽车来代替步行和自行车。尽管小汽车具备出行时间和目的的确定性，显得更为方便和快捷。但是，由于小汽车空间的有限性和交通管制的约束，导致了对城市道路资源的利用效率较低。汽车保有量越多的城市，交通拥堵问题也较为严重，降低了城市居民的出行效率。2012年，北京市居民在不含步行的各种交通方式出行构成中，选择小汽车出行的比例达到了32.5%，公共（电）汽车出行的比例达27.3%，轨道交通为16.8%，见表2.1。明显可以看出，小汽车出行在是所有出行方式当中所占比例最高，以5%以上的比例高于公共交通方式。该种比例选择形式表明：公共交通方式没有最大的发挥其功能和特性，运行效率不高。表2.12012年北京市通勤方式的比重通勤方式公共电汽车轨道交通小汽车自行车出租车其他所占比例（%）27.3%16.8%32.5%13.9%6.6%2.9%与2005年相比，杭州市在2010年的年度交通发展报告中调查指出，5年时间的对比，居民采取非机动车出行（含自行车、电动自行车）的比例下降了15.3%，采取大客、11 [32]摩托车作为出行方式选择的比重下降了50.4%，见表2.2。该调查报告中显示，相比于非机动车和大型客车摩托车的变化率，步行和出租车的出行比重变化趋势不明显；选择公交出行的比例依然不高。表2.2杭州市居民出行方式构成非机动车（含自行车通勤方式公交车出租车小汽车步行其他车、电动车）2005所占比例（%）33.5%21.4%0.8%7.7%32.5%4.1%2010所占比例（%）28.4%23.5%0.7%11.933.5%2.0%变化率-15.3%9.7%-12.5%54.2%2.9%-50.4%从近年来对北京、杭州等大城市的居民出行结构方式的调查来看，都具备一个共同点，即选择汽车作为出行方式的趋势越来越明显，公共交通依旧没能很好的发挥其分担的功能效应，城市交通拥堵问题也不断加重。2.2.2公共交通服务水平公共交通方式主要包括常规公交和轨道交通。对其服务水平的评价主要为出行费用、服务覆盖范围、车内拥挤程度、运营速度、候车时间、绕行距离、换乘次数等。具有代表性的一种观点是：尽管公共交通方式的票价较低，但是早晚高峰期乘坐地铁和BRT是“拥挤但快捷”，乘坐普通公交是“拥挤且缓慢”。总体来说，服务水平达不到人们选择的满意度。（1）常规公交我国大多数居民都以车内拥挤度太高来评价公共交通的特点。在国外，交通管理部门也是以车内的拥挤程度(负荷参数)作为一个重要指标来评价公共交通的服务特点，负荷参数即车内乘客数量与公共汽车中座位数量的比值。一般以A,B,C,D,E和F作为评价等级来评价公共交通车内的拥挤程度，各等级划分标准见表2.3。表2.3美国公共交通载客服务水平（LOS）服务水平公共汽车负荷参数备注A0.00~0.05座位剩余较多B0.51~0.75乘客有选择座位的空间C0.76~1.00保证了乘客的一人一座D1.01~1.25有宽松的站立空间E1.26~1.50最大的额载荷F൐1.51极限承载量12 从上表中我们可以清晰的看到，在美国，当车内总人数为座位数的1.5倍以上时，就达到了极限的承载量。区别于美国公交的拥挤度服务水平，我国大多数城市在通勤时段的荷载系数都处在F等级或更为拥挤。为了对我国一部分城市的公交拥挤水平进行验证，在早高晚通勤高峰时期对西安市某条常规公交的线路客流情况进行了实地的调查，如表2.4。数据显示，该线路早晚通勤高峰时期某个时段的车内客流量均超过了60个甚至更多。按照公交车内座位数为18，2车内可站立面积为7m来计算，该线路早晚高峰期公交车的负荷参数分别高达2.7和3.5，远远超过了美国定义的极限载重量。表2.4西安市306路公交早晚高峰期车内人数统计序号站点早高峰车内人数晚高峰车内人数1临潼东关7262华清池10293华清池20324骊山索道25375空辽路口26416路辽33457新疗路口34498西安科技大学临潼校区34519西安工程大学临潼校区445310十里铺495411王家坟435712胡家庙435713康复路北426214火车站3562（2）轨道交通由于轨道交通能快速的将大规模的乘客安全准时的运送到目的地点，不受道路交通拥堵情况的限制，因此很多人以为解决城市交通问题的有效举措是大力发展轨道交通。尽管大力发展轨道交通能有效的分担一定的居民出行比重，但是也会诱增更多的居民出行需求，造成整体的客运服务模式向着轨道交通倾斜，不符合均衡和谐发展的理念。与此同时，很大一部分城市的交通拥堵都体现在早晚高峰通勤时段，大力发展轨道交通在解决了居民出行需求的同时，同样不能解决“平峰时客流少，高峰时人满为患”的客流分布不均而造成的运营亏损问题。13 根据西安市地铁二号线几个站的实地调研，该列车额定车厢载客量为245人/节，最大车厢载客量为313人/节，据数据分析早晚高峰期车厢内最高人数达284人，如下表2.5表示。表2.5西安市地铁2号线早晚高峰期单节车厢人数统计站名检票口进入流量（人/min）检票出口流量（人/min）车厢人数统计北客站2.482.64114行政中心站3.642.11212钟楼站0.720.62242小寨站1.661.42284从上表相关指标的调查可知，其乘车情况大体与车站内客流相吻合。车辆人数大于额定载客人数，早晚高峰车厢内部相当拥挤。2.2.3定制公交发展的必要性面对当前城市居民的通勤出行以及公共交通服务水平的现状，大力发展多元化公共交通体系是解决交通问题的有效举措。因此，由于定制公交独特的运营优势，是公共交通方式的一种有效补充以及大力发展的重要环节。（1）发展多元化公共交通。在城市公共交通结构形式布局当中，轨道交通和常规公交线路一方面主要布设在客流需求较大的区域，服务覆盖范围受到了限制，导致了非主要客流走廊的部分需求无法满足。另一方面候车时间过长、绕行距离较远、换乘次数的增多也导致了其服务水平和吸引力不断下降。定制公交是多元化公共交通发展的特殊体现，既能够扩展公共交通的覆盖范围，弥补公交的空白区域，又在常规公交的基础上最大化的满足了居民出行的时效性和舒适性等需求。（2）促进私人小汽车转向多元化公共交通小汽车的保有量随着性能的改善和经济的发展逐渐增多，从而导致的道路交通状况持续恶化的问题削弱了小汽车自身的速度和灵活性的优势。同时，使用小汽车的出行和保养费用也逐渐增高，越来越多的人们也希望得到一种有效的交通出行方式来降低使用小汽车的概率。定制公交相对小汽车来说，以较为合适的经济价格为乘客提供相对的优质服务，对自驾一族具有较大的吸引力，能够促进利用私人小汽车或者出租车的出行群体转向多元化公共交通。（3）提高城市道路资源利用效率14 定制公交运营过程中的站点设置较少，甚至在某些线路中不需要站点停靠，一方面确保了定制公交的运营速度，节省了乘客的乘车时间；另一方面减少了车辆在接送过程中的停靠对周边交通秩序带来的干扰。此外，定制公交的开通主要是根据城市的道路交通状况而设定的，能够灵活的选择最快的运输线路在规定时间内达到乘客预定站点，既避开了城市的拥堵路段满足了乘客的乘车时间要求，又节省了乘客的出行时间，提高了道路资源的使用效率。（4）降低社会和个人的出行成本对社会而言，大力发展定制公交能有效减少使用私人小汽车带来的交通拥堵以及附带的一系列环境污染、场地占用等问题，很好的节约了能源成本和社会公共成本；其次，对接受定制服务的个人而言，既能够有效的节省使用小汽车的时间和经济成本，又享受了预期达到的服务，2.3定制公交发展问题分析根据对定制公交定义和发展的分析，定制公交作为一种新型客运服务模式在中国还处于发展起步阶段。尽管定制公交依据其独特的运营特性，很好的吸引了私家车主转向多元化公共交通，缓解了城市交通拥堵，但是要让一种新型的服务模式在全国范围推广并被接受，同样面临很多的挑战和问题。其次，定制公交在发展过程中，对原有的城市公交系统也会产生一定的影响和冲击。因此，定制公交的发展无论是在政策、机构组织、运营、行业管理等方面，还是在配置问题等问题上都需要进一步探讨和研究。2.3.1对常规公交系统的影响分析近些年来定制公交的快速发展对原有的城市公交系统造成了一定的影响和冲击，主要体现在客流分担和公共资源占领上。（1）客流的影响分析：“定制公交”是为特定的人群量身定制的一种交通服务方式，其“快速直达、干净舒适”的乘车环境对有车一族和收入较高的上班族具有较高的吸引力。“定制公交”的出现，使人们出行多了一种选择，对常规公交等既有出行方式有所影响。但是，人们的出行习惯不容易轻易改变，常规公交较低的票价优势无法取代，自驾的便利和身份象征也根深蒂固。因此，“定制公交”可能会对地铁、传统公交客流有所分散，但是所造成的影响不大。15 （2）公共资源的影响分析：定制公交属于公共交通系统的一个组成部分，会使用公交专用道行驶，而其专属于少数人群使用的特点违背了公共交通的普惠性，挤占了公共交通资源，对常规公交系统的行驶速度和特性都有一定的影响。2.3.2定制公交配置问题分析本文对定制公交在发展过程中的配置问题进行提取和归纳，主要体现在资源配置、线网布局和线路设计、站点选址等几个方面。（1）资源配置问题：定制公交在运营开通前，不仅要对开通运力进行合理配置，还要对开通定制公交所涉及到的前期调查和设施进行优化组合和管理，才能最大程度的发挥定制公交的效益。在运营过程中，所涉及到的客流调查、车辆的配置和选择、票价机制的确定、发车频率等方面的运营管理与组织得当与否，对选择定制公交服务的乘客都会产生一定影响，同时对运营定制公交企业的经济效益和运营成本都密切关联。（2）站点设置：定制公交乘客合乘站点的布局与选址是定制公交问题中十分重要的一步。乘客站点位置确定合理与否，既直接影响到定制公交线路设计的质量优劣，又与乘客的满意度直接挂钩。若乘客从出发点到达乘客站点距离较长，乘客所花费的时间成本较高，则很难保证高质量的路径优化成果；若乘客站点设置过多，上下车的服务时间较长，乘客损失的时间成本较多，既难以突显定制公交的特殊性，也很难让乘客个性化需求达到满足。（2）线路设计与线网布局：定制公交线路设计不但关系着运营公司的运营利益与乘客的满意度，还关乎着整个定制公交能否健康有序的发展，所以其线路设计是否合理显得尤其重要。合理的定制公交线路设计，不但可以有效提高资源利用效率，而且对减缓城市交通拥堵有一定的帮助。不合理的定制公交路线设计会给其他公共交通方式的运营（如常规公交、轨道交通、城市出租汽车等）带来影响，在降低定制公交服务水平的同时也会给运营企业带来一定的影响。因此，设计和优化效果较好的定制公交线路便成为了定制公交健康有序发展的重中之重。定制公交线网布局主要以定制公交站点的选址和线路的布线形式为基础，以满足乘客需求为目的，兼顾运营企业的效率和经济效益来进行布局调整。现有的线网布局方式主要有采用不换乘的独立线路布设形式和换乘的组合线网布局模式两种。在运营过程中，定制公交线网布局的模式直接影响到线路设计的方法，其合理与否对定制公交的服务水16 平和后期的持续发展都有着必要的关系和影响。2.4相关理论分析由于定制公交是在新时代背景下产生的一种特殊客运服务模式，是公共交通的一种特殊补充。在很多问题的研究方面，既与常规公共交通方式有很大的联系，又区别于常规公共交通方式。因此，可以将很多定制公交涉及到的问题抽象化、常规化，借鉴现有的相关基础理论，展开问题的研究与分析。本文研究的定制公交问题所主要包含前期资源的配置、站点的选址布局、线路设计以及线网布局等，研究的重点主要集中在了定制公交线路设计上。因此，本文的相关基础理论主要从与线路设计密切相关的站点选址布局和车辆路径问题展开，分析定制公交线路站点选址的常规方法和线路设计问题的抽象属性，为之后研究提供理论来源与科学依据。2.4.1聚类分析方法定制公交的站点选址布局是整个定制公交线路设计研究的考虑的关键因素，实质是在众多的乘客当中，将符合定制公交开通特定要求和标准的乘客集中到某一个规定站点上车，把众多某种需求属性相类似的乘客聚集到一起，需求属性差异较大的剔除或分到其他的乘客站点。因此，定制公交站点的选址布局可以抽象为聚类问题进行分析。（1）聚类分析法的描述[33]已有的文献，通过将选址布局问题看成是数据挖据中聚类分析的一种特殊体现形式。聚类分析实质是按照某一种特定的要求和标准，将需要聚类的对象分到不同的组，使得每个组中的对象与对象之间具有某种相近或者相类似的属性，而被聚类在不同组的对象元素之间的属性具有较大的差异性。采取这样的方式聚类起来的对象具有一定的现实应用价值，可以对划分出来的每一类进行深入的分析从而概括出每一类的特点。本节则是根据定制公交乘客站点在划分之前一定的参数和聚簇表示方法不同的实际特点，期望将不同乘客站点进行区域划分和聚类，主要包含有k-平均值（k-means）方法与K‐中心点（K-medoids）方法。（1）k‐平均值算法17 K-means算法是很典型的基于距离的聚类分析算法，在聚类过程当中，采用距离作为对象元素之间相似性的评价指标，即认为两个对象元素之间如果相距最近，其相似度也就越高。这样比较，就很好的把距离紧凑且独立的对象元素组成一个簇，再经过多次的迭代计算，最后按照某一规定的值达到函数收敛，得到最终目标。K-means算法主要分为三个步骤来实现：Step1：根据需要聚类的对象元素的规模和特点，从对象元素当中随机选出多个初始聚类中心。Step2：计算其余未被选中的对象到聚类中心的距离，并按照距离的远近将其纳入到最近的聚类簇中。Step3：计算每个聚类簇中各个对象之间的距离平均值，并将得出的平均值作为新的产生的聚类中心。Step4：按照Step2、Step3多次进行距离迭代计算，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止。下图展示对n个样本点进行k-means聚类的效果，选取k=2进行分析。（a）未聚类的初始点集；（b）随机选取待聚类的两个点作为初始的聚类中心；（c）计算剩余的每个点到初始聚类中心的距离，并聚类到离该点最近的聚类中去；（d）计算每个聚类中点的坐标平均值，并将这个平均值作为新的聚类中心；（e）重复（c），计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去；（f）重复（d），计算每个聚类中点的坐标平均值，将平均值作为新的聚类中心。18 图2.4算法步骤实现示意图该算法结构简单，灵活性强，用于处理大数据集时，具有相对较高的可伸缩性和高效性。但是其也存在一定的局限性，只有在簇的平均值被定义的情况下才能使用，不适用于分类属性的数据聚类。（2）k‐中心点算法k中心算法的基本策略是：首先随机选择一个代表对象作为初始聚类簇C୧，按照初始聚类簇中心与其余对象的远近距离，将距离簇中心最近的对象元素纳入到聚类簇中。完成这一步后，通过多次选定非代表对象来代替代表对象，改进聚类的结果质量。对聚类结果质量的估算方法是以对象与参照对象之间的平均相异度作为代价函数来体现。当一个中心点被某个非中心点替代时，除了未被替换的中心点外，其余各点被重新分配。具体的实现步骤如下：（a）随机选择初始簇的聚类中心数量，记为K；（b）在其余未被选择的对象中，挑出一个非中心对象0୰ୟ୬ୟ୫；（c）计算用0୰ୟ୬ୟ୫代替0୨的总代价S；（d）IFS＜0，then0୰ୟ୬ୟ୫替换0୨，形成新的k个中心点的集合；（e）Until不再发生变化；类比于K-means算法的特点，二者有着很多的相同点。不同之处在于，k-中心点方法没有采用平均值函数做作为聚类中心点的衡量准则，有效的避免了极端数据对于聚类19 结果造成的影响，但是并没有弥补K-means方法的其他弱点。因此，在存在“噪声”和孤立点数据分布的条件下，k-中心点方法比K-means方法更加具有优势和时间复杂度。2.4.2车辆路径问题理论分析（1）车辆路径问题的描述及分类车辆路径问题可以抽象描述为：对于从配送中心发出的车辆，确定合适的行车路线，有序地通过一系列给定的客户(送货点或取货点)，并在满足车辆载重量、客户需求量、时间窗限制等约束的条件下，达到使用车辆数最少、车辆行驶路程或时间最短的优化目[34]标。经过国内外多个学者对车辆路径问题的研究深入和开展，在许多现实问题当中得到了很好的验证和实践。在此基础上，更多与之相关的学术理论研究也得到了较多的延伸和拓展。其中，带容量约束的VRP(CVRP)就是最基本的一种车辆路径问题的拓展。随后的研究逐渐深入细化，现实中真实的目标和约束在问题模型中得以体现。在基本CVRP的基础上，产生了众多的分支，比如带距离和容量约束的VRP(DCVRP)、带回收问题的VRP(VRPB)、装卸一体化的VRP(PDP)、带时间窗约束的VRP(VRPTW)、带时间窗的VRPB(VRPBTW)、带时间窗的PDP(PDPTW)等。各个VRP分支之间的关系如图2.5所示[13]。图2.5VRP分支及其相互关系（2）定制公交路径规划问题定制公交路径规划问题的构成要素主要包括定制公交车辆，发车场站、预约乘客、行车线路、目标函数和约束条件等要素，可以将其抽象描述为：在乘客和开通定制公交运营企业之间存在供求关系的系统中，规划合理的路线和车辆数，将有需求的乘客从上车站点接到目的站点，达到某个目标函数最优化目的。定制公交车辆路径问题和VRP20 对比分析如下表2.6所示。表2.6定制公交车辆路径问题与VPR问题的对比分析名称定制公交路径规划问题VRP问题服务对象预定乘客（人）客户（人/货物）运载工具定制客车一般运输车辆目标函数服务目标、成本目标、公平目标主要考虑运输成本限制条件车辆容量、乘车时间、载客率距离约束、时间窗约束、容量约束综合表2.6所示，尽管定制公交属于一种新型客运服务模式，但是其线路设计所构成的要素是VRP问题的特殊化表现形式。因此，定制公交路径规划问题也属于车辆路径问题（VRP）的一种有效范畴和拓展。2.4.3相关优化算法近年来，在求解车辆路径问题的多种算法中，启发式算法被更多的应用到实际问题的求解当中。由于其主要的启发原理都来源于生活经验或者实际问题，不管问题怎么样变化，都与其实质内容有着密切的联系且能够取得意想不到的效果。在有的问题求解当中，即使得不到最优的结果，但是求解结果一般也都在可以接受的范围内。下面分别对具有代表性的模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法等几种通用启发式算法进行综述。（1）模拟退火算法Metropolis等人于1953年提出了模拟退火算法，是在基于热力学相关研究原理的基础上建立的随机搜索算法，很好的补充和改进了之前局部搜索方法的不足，以概率1收敛于全局最优解的方式被证明，是在局部搜索算法基础上拓展的全局优化算法。与其余启发式算法相比，选取符合自身和实际问题特点的初始温度、温度下降规则、温度迭代补偿和算法停止准则等要素，使得所求的解具有较好的质量。算法简单灵活、很少受初始条件的限制，在路径规划问题中已得到了很好的应用和实践[35]。（2）禁忌搜索算法禁忌搜索(TabuSearch,TS)也是在局部搜索算法基础上的一种推广新方法，主要包括有邻域结构、候选解集、禁忌对象、禁忌长度、藐视准则、终止准则等特殊表达因素，这些因素的确定以及选取是禁忌搜索算法能否搜索到最优解的关键。21 与局部搜索算法基本思想不一样的是，禁忌搜索算法并不十分依赖于初始解和候选解函数的得出，独特之处在于采用禁忌搜索技术，用禁忌表的形式来记录之前达到过的局部最优点，避免在下一次搜索过程中，不再或者有选择的搜索之前在禁忌搜索表中出现的点。这种搜索表达方式很好的弥补了局部搜索算法的不足，是一种全局逐步寻优算法[34]。相关研究表明，应用禁忌搜索算法来求解车辆路径规划问题，不仅能体现其全局寻优的搜索能力，更可以得到很好的路径优化效果。（3）遗传算法遗传算法是Holland于1975年借鉴生物界自然选择和自然遗传机制提出的一种模仿生物进化过程的全局随机搜索方法。在之后的研究过程中，Thangiah于1991年将遗传算法首次引入到解决车辆路径问题的实践过程当中。遗传算法主要按照“确定编码方案—确定适应度函数—确定选择策略—设计遗传算子—确定运行参数—确定终止准则—编程上机运行的”基本思路和步骤来实现最优解的得出，主要由解码、初始群体生成、适应度评估、选择、交叉、变异、运行参数等要素构成。该方法主要是模拟自然界中生物的繁衍规律，根据适者生存和不适者淘汰的生存法则，逐步操作，逐步优化而产生较好的种群的一个过程，最优解则是在整个过程中所出现的最好的个体。该方法所用的元素概念对应于生物遗传和进化的一些基础用语如下表2.7所示。表2.7生物遗传学概念与遗传算法对应分析表生物遗传学概念在遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能被留住个体研究问题的解染色体解的编码基因解中每一分量的特征值等位基因基因取值基因座基因在染色体中的位置基因型染色体的编码结构表现型染色体的解码结构适应性适应度函数值（表示解的质量的优劣）群体选定的一组解（表示解的个数为群体规模）种群根据适应度选取的一族用于遗传操作的解杂交通过交叉原则产生一组新解的过程变异编码的分量发生变化的过程22 （4）蚁群算法蚁群算法是近年来广泛应用于求解路径优化问题的代表性算法，是基于对蚂蚁觅食行为的理解进而进行现实模拟的一种仿生优化算法。蚁群算法在车辆路径规划应用过程中按照如下步骤进行问题的求解：“先对蚁群中的蚂蚁进行抽象，剔除与模型求解无关的因素，初始化所求解；然后按照实际问题的特点初始选择第一个客户或站点，计算在此站点选择下一个站点的概率；在蚂蚁完成一次搜索后，进行信息素的局部跟新；最后针对觅食路径进行抽象，引入启发因子，寻找出最好的蚂蚁路径”。大量的研究显示，蚁群算法具有许多其他算法所不具备的优良胜质，比如较强的智能搜索性和鲁棒优化性、全局优化以及分布式计算等特点，很多学者更是将蚁群算法与其余某种启发式算法结合起来，能够较快的发现优质解，有效的求解复杂[35]的组合优化问题。2.5本章小结本章主要根据定制公交含义的提出，既分析了早期关于“定制”服务模式的发展问题，又探讨总结了当前部分城市的定制公交发展现状。通过当前城市通勤出行现状和公共交通服务水平的问题分析，引出了发展定制公交的必要性。其次，归纳提取了当前及今后发展过程中所需要研究解决的问题，引出本文需要重点研究问题的思路和方向。最后，概括阐述了定制公交线路设计的相关基础理论分析，为文后研究做好必要的基础铺垫。23 第三章定制公交配置问题与优化方法定制公交在发展过程中配置问题主要内容包括前期资源配置、票价机制、站点的选址与布局以及线路的设计等四个方面，本章将结合定制公交的实际运营特性展开分析，总结出相应的优化方法。3.1定制公交前期资源配置期望享受去某地定制公交服务的乘客必须首先提出预约请求，预约请求信息必须包含出行起讫点、时间、人数和服务周期等，定制公交企业则根据这些预约请求，在线路设计开始之前，对前期所涉及到的问题资源进行一定的配置。在定制公交前期资源配置过程中，主要包括前期乘客招募、车型选择、车辆配置等方面。3.1.1前期乘客招募乘客招募的方法是确定定制公交线路开通可行性的主要前提条件之一，包括定制公交客流需求调查，构建网络平台、开通载客量率要求。（1）客流需求调查客流调查方法和调查内容的完善合理是确保定制公交客流来源和有序发展的基本依据。对于定制公交开通前期所涉及到的潜在客流需求特征主要满足以下几点基本原则：出行时间和目的地相对确定，不随外界影响而随机变动，具备一定的静态特性，例如早晚高峰的通勤客流成为了定制公交潜在客流的主力军。客流的出行时间需求相对集中，线路上的客流能达到一个稳定常态的规模，一定的经济收益确保定制公交的日常运营成本，在保证自身财务可行性的前提下，也能持续有效发展。因此，定制公交客流调查的主要采取调查问卷的方法，收集广大城市居民的特定通勤需求，调查问卷中的主要调查信息包括了被调查者的基本信息、固定需求的居住地点和工作地点、达到目的地的时间需求、预期的晚间乘车时间、预期的乘车环境以及时出行方式等几方面的内容。（2）构建网络平台公交运营企业在通过客流需求调查问卷确定有意向乘坐定制公交车辆的乘客了解24 了定制公交相关服务后，通过开通构建网络服务平台的方法来实行乘客的招募，网络平台构建主要包括定制公交专区以及出行需求选择等。在网络平台构建后，有意向乘坐定制公交的乘客填写自己的出行需求的相关信息，包括居民的基本居住、上班、时间信息和所期望得到的定制公交服务类型，在网络上进行查询和报名。公交公司则根据乘客提交的信息和报名人数，确定定制公交起始点，制定合适的运行线路。运营期间，市民对于现状的定制公交服务水平和其他相关建议，也可以通过网络服务平台的方式反馈给运营公司，达到公司和乘客之间友好互动，促进定制公交健康有序发展。（3）载客率要求定制公交实载率，指定制公交线路运营中，车辆运营一次所搭载的乘客人次的多少。从某种意义上说，优质服务的定制公交，载客率高，反之则低。因而上座率是衡量定制公交服务质量好坏的重要标准，也是表征公交资源的利用率和资源配置是否合理的关键因素。定制公交线路开通可行性的实载率范围表示为：Q୮γ൑γൌ൑γ（3.1）୫୧୬୮C୫ୟ୶୔其中，Q୮为线路的客流需求量，C୔为定制公交的容量，γ୫୧୬为最低的定制公交开通载客率,γ为线路最高的载客率。୫ୟ୶任意线路的载客率均要满足定制公交的上座率要求，公交公司才有运营该条定制公交线路的可行性和积极性。按照公式（3.1）的表述，定制公交开通的载客率处在一个最低和最高的范围之间，最大载客率γ一般为1，即满足车辆本身的容量限制。୫ୟ୶因此，总结关于定制公交线路开通之前，必须从以上三个方面进行问题的分析和解决，才能确保线路正常运营。如下表3.1所示。3.1定制公交前期运营可行性分析表方式名称客流调查方法招募方法载客率定制公交调查问卷法构建网络平台γ୫୧୬൑γ୮൑γ୫ୟ୶问卷调查、跟车调查、信常规公共交通乘客自行选择γ୮൑γ୫ୟ୶息化设备调查等25 3.1.2车辆选择定制公交车辆的选择主要是依据实际的客流情况和城市道路条件情况而定的，必须符合定制公交的实际功能定位和运营特点。（1）依据客流量选择公交车型在定制公交的车型确定过程中，主要的决定因素归结于线路上的乘客需求量。一般来说，在乘客需求规模较大，路幅宽度较宽，道路条件良好的情况下配置性能高、容量大的定制公交车辆；相反，则选择性能和容量相对较弱的定制公交车辆。与常规公交不同的是，定制公交车辆配置情况是根据特定的乘客出行需求和出行人数，按照“一人一座”的基本原则来选择的。因此，依据线路上的客流规模和道路情况，定制公交车型主要按照如下公式进行选择：MୟൈT୧C୔ൌ（3.2）γ୮ൈfሺxୡሻ式中，C୔表示为不同车型所应配置的载客容量；Mୟ为运营过程中的实际载客量；T୧表示为车辆线路的发车间隔，γ୮为线路的乘客载客率；xୡ为线路的平均重复系数；fሺxୡሻ为线路的重复影响系数。（2）依据运营特性选择公交车型定制公交主要以远高于普通公交车的票价为特定的人群服务。因此，乘客期望能享受到区别于常规公交的乘车环境，对定制公交车辆的配置和环境都有一定的要求。此外，公司在考虑乘客舒适度出行需求的同时，也要考虑车辆的日常运营成本车和安全措施要求，尽可能的降低存在的运营风险。车身配置遵循以下要求：1）内饰设计简洁大方定制公交车厢内部设计追求简洁大方为主，配置应有的服务设备即可，不宜过于复杂化。考虑到乘客中绝大部分都是从自驾车人群中吸引过来的顾客，尽管定制公交车辆达不到小汽车的灵活性与便捷性，但是在车内环境卫生和配置上可以向私人小汽车方向靠近，通过提高定制公交的服务水平来吸引更多的私家车主。2）配置前门和中门由于定制公交站点的设置特殊性，在起终点一般为大型的居住中心和商业中心，上下车客流较为集中。同时，定制公交在服务过程中均受到了站点停靠服务时间和道路资26 源空间的限制，需要在较短的时间内快速集散客流。因此，配置前门和中门既满足了快速上下客的要求，又方便了乘客在紧急情况下的安全疏散。因此，定制公交车辆的选择可以按照以上的两点来进行选择，根据目前市场的客车车型长度和座椅布置情况，可以采用车型长度分别为12米、10米和8米三个系列车型，具体情况如下表3.2所示。表3.2定制公交车型选择表车型长座椅布置配置适应情况度（m）数量（座）内饰设计简洁大方、车内容易清1255客流需求较大、道路条件宽阔扫，配有前门和中门内饰设计简洁大方、车内容易清1045道路相对宽阔狭、客流相对较少扫，配有前门和中门内饰设计简洁大方、车内容易清835车辆灵活，适合道路相对狭窄、客流较少扫，配有前门和中门3.1.3车辆配置合理的车辆配置是保证定制公交线路能正常运营的基本条件，主要包括合理的运力配置和车辆运营时间的安排。（1）运力配置受道路网络结构的布局以及乘客出行需求的分布等条件限制，合理的运力配置在运营过程中显得尤为重要，主要体现早晚高峰期的通勤车辆如何采取应对方法来面对复杂的道路网络和诸如天气变化、车辆故障等因素，包括运力规模和运力调度。运力规模：公共交通车辆一般采用单车运营的形式，在大多数的情况下，使用导向性的运营模式，将很多车辆集结成对，以获得更大的运载能力和更好的运营经济性。公交车辆无论是常规公交还是轨道列车，都以车队为一个运营整体。定制公交通常是以单独的车辆为乘客服务单元，以运营车队的形式结合线网运营模式进行运营，具有长期性和稳定性。因此，定制公交的运营车队规模K୤，包括线路上，正常运营所需车辆数K、备用所需车辆数K୰，以及维修中的车辆数K୫之和，即：K୤ൌK൅K୰൅K୫（3.3）27 运力调度：前期乘客招募后，根据预约乘客的出行需求量确定了乘客站点和路线设计后，需要对每条公交线路配备一定的车辆数来满足公交供给需求。发车频率是协调公交需求和公交供给的抓手，两者之间的协调程度是公交服务水平的主要体现。（2）车辆运营时间车辆运营时间是体现整个定制公交系统运营组织是否合理的关键指标之一，不仅是制定整个运营计划的基础，也与整个公交运行时刻表、行程计划和排版计划等其他日常调度工作密切相关。定制公交主要根据乘客的预约请求信息和实际的道路情况推算得出每辆车的发车时间和线路的行驶时间，主要以满足乘客的时间要求为主。行驶时间主要按照如下公式来确定：୬Tൌ෍（t୧୨൅t୧）（3.4）୧ୀଵ其中，t୧୨表示站点间的行驶时间；t୧表示站点的服务时间（上车消耗时间）。由于定制公交自身的运营特性，在车辆配置问题上与常规公交车辆配置有很多不同之处。对比常规公交在车辆运力配置和时间调度方面的原则和方式，定制公交有着自己的独特性。3.2定制公交票价机制定制公交作为一种新兴起的客运服务模式，是针对特定的人群量身制作的一种服务，虽然不具备普惠性，但是正常的运营开通后，既能提升常规公交系统的服务水平和竞争力，又能很好的推动整个城市交通的运转，带有一定的普惠性。因此，合理的票价制定和政府的政策支持能鼓励其健康发展。3.2.1基本原则（1）企业经济效益定制公交的票价制定，既需要提供便捷、高质量的服务来满足乘客的出行需求，同时也要顾及到运营企业自身的经济效益。只有在二者双赢的前提条件下，制定合理票价规则，控制运营企业的经营成本，降低出行产生的费用，保障定制公交的正常运营效率。28 （2）票价制定应考虑激烈的市场竞争作为一种新兴起的客运服务模式，票价的定制应考虑到与传统的交通出行方式的相互竞争，对市场进行可行性研究。特别是在多种客运服务模式共存的市场竞争条件下，轨道交通和快速公交以低价快速的优势占领着客运服务市场、出租车以便捷快速的形式存在。因此，在这种竞争复杂的客运市场的情况下，更应使得公交的定价决策合理可行，满足市场竞争。（3）考虑广大乘客的承受能力定制公交作为一种收费略高的出行可选性方式，制定的票价需要考虑到出行消费者的承受能力，才能保证吸引消费者参与到其中。对众多的潜在消费者来说，有着不同的收入水平和消费承受能力，他们对交通方式的选择以及服务质量、出行条件的需求都各不一样。3.2.2确定方法我国大多数城市都是采取“政府定价、个别地方实行政府指导价”的收费政策来对常规公交和出租车的定价方式加以约束。常规公交票价一般统一为普通公交一元票价，空调公交实行二元票价；城市出租汽车定价方式主要是按照起步价和里程价之和的方法来确定，里程价根据各城市的实际情况而不同。综合上述票价制定的原则以及相关线路的票价制定情况，定制公交作为一种介于常规公交和出租车之间的备高端水平的服务模式，票价制定需考虑到企业、乘客和经济水平的多方面的因素。因此，定制公交票价制定参照出租汽车和常规公交的票价情况而制定。采用成本加成定价法，具体公式可表示为：Pଵ൑P定ൌP୐ൈL൅R൑Pଶ（3.5）PൌP൫起步价൯൅P′൫里程基价൯ൈL′（营运里程）ଶ଴୐式中，Pଵ代表常规公交票价，一般为1元到2元，Pଶ表示出租车票价；P定代表定制公交票价，L表示里程（营运总里程），P୐表示定制公交乘距L下的基本运价，R表示其他费用，基本运价P୐主要由运输成本及合理利润构成。29 3.3定制公交站点的优化布局3.3.1布局原则乘客合乘站点的选址布局是定制公交线路设计的前提保障。由于预约乘客需求量的分布不同，定制公交站点的设置和线路的覆盖范围不可能满足所有乘客需求。公交企业根据众多预约请求信息做出响应：决定接受哪些请求，将哪些请求的客户安排到后续的线路招募中。这个过程是乘客与企业的博弈过程，本部分确定合乘站点要保证满足下面三项基本原则：一是合乘意愿趋同性原则，即从一个合乘站点上车的乘客具有大致相同的目的地和到达时间，到达的目的地和时间不宜过于分散；二是聚集距离适宜性原则，即每个预约请求到合乘站点的距离不宜太远；三是预约请求唯一性原则，即每个预约请求均对应唯一的合乘站点。3.3.2优化方法针对定制公交站点的布局原则，先后运用聚类分析方法和站点覆盖范围来确定。运用聚类分析方法将出行时间、地点集中，需求量大，服务周期长的预约乘客分别集中到相似度较高的类。然后，根据聚类的需求客流情况的大小，通过设定站点的服务范围来确定接受预约请求的乘客，将不满足服务范围的预约乘客划分到后期招募线路的预备乘客当中。（1）基于K-means聚类分析接受预约需求的乘客分布在一定区域内，以步行等方式聚集到不同合乘站点，再搭乘定制公交直达目的地。本部分采用基于划分的K-means聚类分析方法对预约需求的乘客进行聚类分析，具体的实现步骤如下：Step1：根据开通定制公交前期的客流数据调查的收集情况，明确乘客的出行需求和出行特征，可以清楚的明确开通线路预约请求乘客的居住地点，利用地图软件把乘客的居住地点标出来，得出每个乘客的坐标位置；Step2：假设调查中总共有m个乘客居住地点有开通到某地定制公交的需要，顾客全部包含在数据集X中；Step3：根据调查情况定制乘客分布情况与运营经验选取n个初始聚类中心Z୩，（kൌ1，30 2,3，⋯n），Step4：以Z୩为参照点，对剩余的每个对象，求其到各初始聚类中心的距离，将该样本归到距离最短的聚类中心所在的类；DIS൫X୧，Z୩൯ൌminDIS൫X୧，Z୨൯（3.6）如果X୧，Z୩满足上述条件，则说明X୧属于第k个聚类区域。Step5：更新得到每个聚类区域C୩中的样本点，将每个聚类区域中样本点的均值作为新的聚类中心Z୩′；Step6：按照平方误差准则，计算平方误差：୬Eൌ෍෍||pെZ′||ଶ（3.7）୩୧ୀଵ୮∈େౡ式中，P为聚类区域C୩中的样本点，Z୩′为聚类区域C୩的新聚类中心Step7：对E的值进行多次迭代计算，当E值变化不大时则结束运算，否则继续执行重复Step4、5、6步。（2）站点服务范围的确定利用聚类分析方法确定了聚类中心个数，将预约请求乘客进行多个聚类分类，也就是需要开通定制公交乘客站点的个数，假设第i个聚类中心中的第j个乘客的坐标为（r୧୨，c୧୨），站点的坐标为（x୧୴，y୧୴），考虑乘客到达站点能承受的最大距离（可根据实际情况给定）d，即：ଶଶට൫x୧୴െr୧୨൯െ൫y୧୴െc୧୨൯൑d（3.8）根据站点的服务范围则可确定每个聚类中心接受定制服务的乘客数和纳入到后期招募线路中的乘客数。他们之间的关系详见图3.1。31 图3.1站点选址布局步骤关系图3.4定制公交线路设计3.4.1线路设计原则定制公交站点位置确定后，线路设计需要服务到所有符合预约请求的站点乘客和目的站点。线路规划设计的合理与否不但关系着运营公司的运营利益与乘客的满意度，还关乎着整个定制公交能否健康有序的发展。因此，要保证线路规划设计达到最优效果，遵循以下几点基本原则：从乘客的角度，要节省时间和花费，线型减少迂回曲折，确定较好的方案；从企业的角度，线路要优化，减少较长的运行里程，合理配置资源。连接的合乘站点不宜过多或过少，避免所引起的延误制约预约公交的个性化服务。路径连接的合乘站点不宜过少，从而导致的资源浪费无法体现预约公交公益性优势。因此，在这个博弈过程中，既要处理好乘客和企业的相互利益，又要充分考虑合乘站点数量与合乘路径数量的问题，合理的线路设计方案就显得尤其重要。3.4.2影响因素定制公交路线设计是定制公交运营的重要环节，既要综合所涉及到前期资源配置、票价机制、乘客和目的站点等影响因素，又要从企业运营角度和乘客服务角度来全面考虑线路设计过程中需要达到的目标和需要满足的各类约束条件。本节在前期部分因素考32 虑的基础上，从定制公交线路设计中所要达到的优化目标和约束条件进行分析和总结。（1）优化目标由于定制公交与其他公共方式的特殊性，通常是以高于常规公交的票价享受“快速直达”的特殊服务，因此，在线路设计时所要考虑的因素也较多。一般从成本、质量、公平性三个方面来考虑线路设计所要达到的目标。1）运营成本目标运营成本主要是从公司的角度出发考虑，在定制公交线路设计问题中，所要达到的运营成本优化目标主要涉及到了使用车辆数，或者优化车辆的运营距离和时间，将目标定位最小化车辆数和最小化时间或距离成本。一般将成本函数定义为：ۓfଵൌMinK（3.9）୏运营成本目标۔fൌMin෍z୩c（3.10）ଶ୧୨୧୨ە୏ୀଵ函数f表示最小化车辆总数，函数f表示最小化运营成本，z୩为决策变量限制为0ଵଶ୧୨或者1，表示车辆是否经过站点i和站点j连接的路径；c୧୨表示两个乘客站点之间的距离成本或者是时间成本。2）服务质量目标定制公交服务质量水平体现在定制公交线路的最小化绕行距离和最小乘客损失时间两个方面，具体表示如下：୏ۓfଷൌMin෍lossሺZሻ（3.11）服务质量目标۔୏ୀଵfൌMin൫S୩െS൯（3.12）ەସ୧ሺ୬ାଵሻ୧ሺ୬ାଵሻ函数中用loss（z）表示一个乘客的损失时间，函数fଷ表示最小化所有乘客的损失时间；S୩表示第k辆车中，站点i到目的的行驶里程，S表示站点i直达目的地的୧ሺ୬ାଵሻ୧ሺ୬ାଵሻ行驶里程，函数fସ表示最小化乘客的绕行距离。3）公平性目标定制公交公平性目标体现在路线负载均衡和距离（时间）均衡。其中负载均衡主要通过平均的载客率来体现，路径间长度的均衡目标通过各条路径长度与平均长度差的平方和来衡量。目标函数定义为：33 ୩ۓ1୩fହൌmax෍γ（3.13）ۖۖk୩ୀଵଶ୏୬୬ାଵ୏୬୬ାଵ۔fൌmin෍ቌ෍෍dz୩െ෍෍෍dz୩൘Kቍ（3.14）ۖۖ଺୧୨୧୨୧୨୧୨ە୏ୀଵ୧ୀଵ୨ୀଵ୏ୀଵ୧ୀଵ୨ୀଵ式中，γ୩表示第车辆k上，乘客的载客率，函数f表征每辆车平均载客量最大；函ହ数f଺用各条路径长度与平均长度差的平方和最小来衡量。通过该目标函数来表征定制公交的利用率最大，公交资源配置最优。（2）约束条件定制公交在线路设计过程中，主要从车辆、时间、任务、变量等多个方面考虑约束条件，不同场景和情况下，定制公交所考虑的约束条件也不同。3.4.3优化方法定制公交路径规划所要解决的主要问题是如何在定制公交线路设计过程中，结合实际运营的特点，合理的考虑优化目标和相关约束条件之间的关系，达到线路设计的整体最优。本文希望构建线路设计优化模型并设计合理的模型求解算法，来解决定制公交路径规划的实际问题，验证线路设计的合理性和可操作性。该部分内容是本文研究的重点和主要方向，具体的设计模型和求解方法在第四章进行系统的研究和阐述。3.5本章小结本章主要从定制公交开通的前期资源配置、定制公交票价机制、定制公交站点的优化布局和线路设计等配置来展开分析。根据定制公交区别于常规公交等的特殊运营形式，得出前期乘客招募、车辆选择和配置等方面的特殊布置形式和方法，为定制公交健康有序的发展提供了相关的依据。其次，利用聚类分析和服务覆盖范围的方法，确定了符合定制公交线路开通条件的乘客和站点，为线路设计打好了关键的基础。最后，引出本文研究的关键和重点，分析定制公交线路设计的主要目标和相关约束条件，为之后的定制公交线路设计的建模求解提供了思路和方向。34 第四章定制公交线路设计模型与算法分析定制公交线路设计模型与算法设计是本文研究的重点和关键，在实际运营过程中，所涉及到的因素也较多。因此，本章首先将根据实际过程中定制公交线路设计问题的描述，构建符合实际的优化目标和约束条件的函数模型。其次，根据对模型的结构分析，设计适合求解定制公交路线设计问题的智能优化算法，希望得出整体最优化的路线设计方案。4.1问题的描述定制公交主要是用来接送绝大部分上班族上下班的专用车辆，将乘客从居住地（乘客站点）送到目的地或者从目的地送回。定制公交路线设计问题可以描述为：在早晚高峰通勤时段，对一系列已经确定或待确定的预约合乘站点，在满足一定的约束条件下，组织适当的行车车辆与行车路线，使得公司的运输总成本与服务水平之间达到满意的均衡。根据乘客站点和目的地的需求对应关系，又分“1对1”、“1对多”（或“多对1”）、“多对多”三种情形。“1对1”表示定制公交的两点直达；“1对多”（或“多对1”）表示单个的目的地对应多个需要服务的乘客站点，即单目的地的定制公交问题；“多对多”表示多个目的地对应多个乘客站点，即多个目的地混载的定制公交问题。本文研究的问题是单目的地的定制公交线路设计，属于第二种情形，在实际运营中，需要确保汇集到多个合乘站点的这些乘客前往的目的地是一致的。因此，定制公交线路设计问题是合乘站点与目的地之间存在“多对一”需求关系，属于多车辆路径规划问题。4.2定制公交线路设计模型构建4.2.1构建思路对于单目的地定制公交路径规划问题，构建定制公交路线优化模型的基本思想是：在满足定制公交实际运营特点的最低实载率和乘客对“快速直达”的要求下，安排合理的车辆数和行车线路，使得定制公交线路的服务水平和运营成本达到一定的均衡。因此，35 本次定制公交线路设计问题的模型构建主要是以运营总里程最小为目标函数，以乘客乘车绕行距离和车容量限制等为约束条件，使得定制公交的线路设计达到整体最优的效果。4.2.2模型构建基本假设在模型构建前，首先对所研究的定制公交线路设计问题所要考虑的主要因素做以下假设，使得模型建立变得简化。（1）假设定制公交在运营过程中的起点为某一站点，终点为目的站点，也就是开通定制公交服务的地方，定制公交目的站点和乘客站点位置和需求已知；（2）每个乘客站点有且仅有一辆车进行服务，所有乘客站点都必须服务到；（3）乘客站点的乘客需求量小于或等于车辆的最大容量；（4）我们以早高峰接乘客的问题为背景，下午晚高峰送乘客回到站点的问题类似，只需略做修改即可；（5）车辆车型相同，最大车容量相等，即单一的定制公交车型；（6）在定制公交接送乘客的服务过程中，道路状况确定，不考虑路段拥堵、车辆本身故障；（7）每条线路配备一台定制公交车辆，也就是车辆数和线路数相同。4.2.3数学模型综合考虑上述问题和因素，定制公交车辆路线设计符号说明和数学模型如下：（1）符号说明K——表示可用来开通定制公交的车辆数；n——表示n个定制公交乘客站点数，n൅1表示需要开通定制公交的中心站点，也就是目的站点。n୩——表示第k辆车所服务的乘客站点数；C୘୩——表示线路k采用的定制公交车型的车型容量，每条线路所采用的车型相同；q୧——表示在站点i的乘客数；q୧୩——表示车辆k服务的站点的上车乘客数；d୧୨——为车辆从乘车站点i行驶到j的行驶距离；γ୩——为车辆k的载客率；36 S୩——为车辆k中，站点i的乘客到达目的站点的行驶里程；୧ሺ୬ାଵሻS୧ሺ୬ାଵሻ——为站点i的乘客直接到达目的站点的行驶里程；1第k辆车经过路段ij，且从i行驶到j；z୩ቊ୧୨0否则；（2）数学模型本文模型以最小化行驶里程为目标函数，与模型有关的影响因素体现在其约束限制中，模型构建如下：୩୬୬ାଵZൌMin෍෍෍dz୩（4.1）୧୨୧୨୩ୀଵ୧ୀଵ୨ୀଵSt：୬ౡ෍q୧൑C୘୩（4.2）୧ୀଵS୩൑ωS（Kൌ1,2,⋯,K）（4.3）୧ሺ୬ାଵሻ୧ሺ୬ାଵሻγ൑γ୩൑1（Kൌ1,2,⋯,K）（4.4）୫୧୬୬1൏݇൑෍q୧൘Cγ୫୧୬∙୘୩，且K为整数（4.5）୧ୀଵ୩෍n୩ൌn（4.6）୩ୀଵ0൑n୩൑n（4.7）q୧ൌq୧୩（4.8）约束（4.2），表示车辆容量限制，保证每辆车的载客人数不超过车辆的容量；约束（4.3），表示服务水平约束，确保定制公交线路没有过多的绕行，限制每条线路的乘客的行驶里程不超过直达行驶里程的ω倍；约束（4.4）可行性限制和公平性约束，即保证定制公交的开通最低上座率，又确保了每辆车载客均匀的公平性；约束（4.5）确保了车辆数的范围，保证了服务的均匀性；约束（4.6）保证所有站点的乘客都必须有定制公交服务到；约束（4.7）表示每一辆车服务的乘客站点不超过总的乘客站点；约束（4.8）表示站点的所有乘客都必须上车，且只由一辆定制公交服务。37 4.3模型求解思路4.3.1模型解结构分析根据定制公交线路设计模型的结构分析，它是一个典型的组合优化问题。一个组合优化问题可用数学模型描述为：minfሺxሻ（4.9）s.tgሺxሻ൒0x∈D（4.10）对应组合优化问题的数学描述模型，定制公交路径优化问题模型是以总的行驶里程最短为优化目标函数f（x），以每个乘客站点的乘客需求量需要满足线路上车容量限制，线路行驶距离应该要满足乘客对距离的需求为约束函数g（x），以确定乘客站点为有限点组成的集合D。因此，定制公交路线设计问题是一个典型的组合优化问题，它的解主要由定制公交线路数量，每条线路的行车路径，每条线路的载客人数和总的行驶里程等四个部分构成。对于要使目标函数值达到最小的组合优化问题，由于受到了多个约束条件和模型本身决策变量的一种限制，很难得到满足多个条件的最优路径方案。因此，在算法设计过程中，需要对多个约束条件进行综合考虑，尽可能的让结果接近于最优方案。其次，算法需要具备很强的灵活性和交互能力，以便在特殊情形下路径方案设计人运用人工来辅助设计路线方案。4.3.2算法的比选（1）算法的比较显然，定制公交路径问题属于NP完全问题。一般来说，在组合优化问题的求解中，想要得到满足各种约束条件的全局最优解相对较难，更多的是集合问题的实际特点，利用启发式算法求得问题的近似最优解，主要代表算法有禁忌搜索、模拟退火算法、遗传算法、禁忌搜索算法、蚁群算法等。根据文章2.4节对这些典型算法的原理阐述，得出各种算法的主要特点和适应范围如下表4.1所示：38 表4.1启发式算法的比较算法优点缺点适用性名称模拟最优解寻找能力相对较差，描述简单，使用灵活，较少受适用于对己有路径的改造和退火运算时间较长，对初始解质初始条件限制新路径规划算法量要求不高遗传用适应度函数值作为搜索信运算时间较长、收敛计算速适用于复杂的多目标优化问算法息，多个搜索点同时进行度快，寻优效率低题，求解规模较小问题禁忌涉及复杂的领域结计，影响搜索搜索效率高，全局搜索能力强规模较大问题的求解求解速度算法鲁棒性强，对路径选择问题有蚁群变量需要不断的调整，搜索独特优势，有组织性及潜在并适用复杂的优化问题算法时间较长，易出现停滞现象行性特点（2）算法的选取根据表4-1所述，模拟退火算法相对于其他算法来说，独特之处在于其描述的原理较为简单，在问题中能灵活的使用且受初始条件的约束不高，能在短时间内快速收敛并找到全局最优解。而遗传算法受到其自身特点的限制，很容易在求解过程当中出现“早熟”现象，导致在问题的求解当中无法找到最优解。禁忌搜索算法尽管具有一定的搜索效率和搜索能力，但是在计算机运行过程中占用的储存量较大，收敛速度较为缓慢。综合比较，针对定制公交路径模型构建的特点，模拟退火算法在解决该问题的时候更具有可行性。4.4算法设计4.4.1算法策略采用模拟退火算法求解定制公交线路设计问题时，除了涉及到算法解的表示、解的评价、领域选点规则及终止准则等通用要素之外。与模拟退火算法特点相适应的初始温度的选取、温度下降的规则、每一温度的迭代步长和停止规则等因素的选取对算法的影39 响也非常关键。因此，在构造定制公交路线设计问题的模拟退火算法时，采用了以下算法策略：（1）解的表示方法：由于定制公交所涉及到的客户主要集中在相对应的合乘站点，因此本文采取站点直接排列的解的表示方法；（2）解的评价方法：采用公式EൌZ൅MൈP୵对解进行评价；（3）领域操作方法：由于领域选点方法也可以看成是对原始解实施的一种领域操作方法，本文定制公交涉及到的乘客站点之间，用两交换法实施领域操作；（4）降温方法：采用t୩ାଵൌa∙t୩形式的降温方法，即每一步以相同的比率下降；（5）每一迭代步长的确定：采用固定的迭代步长，即在每一温度迭代相同的步数，该步数根据问题的规模来确定；（6）终止准则：采用温度下降指定次数后停止计算的终止准则。4.4.2定制公交路径问题的算法实现在上述算法策略的确定下，运用模拟退火算法求解定制公交路径问题模型的步骤一般是按照：“从选定的初始解开始，在控制参数T逐渐递减的情况下，采用变化选点领域搜索方法和规定接受准则，重复进行“产生新解—计算目标函数差—判断是否接受新解—接受（或舍弃）新解”四项任务，多次进行迭代，达到目标函数最优”的执行过程来实现。具体实现步骤如下：（1）站点编号，根据单目的地的定制公交实际特点，将定制公交的乘客站点编号依次为vଵ,vଶ,vଷ,⋯v୬，目的站点编号为v୬ାଵ。（2）解的表示：采用站点直接排列的表示方法，该表示方法直接产生n个1~n间的互不重复的自然数的排列。则定制公交的解S可表示为ሼvଵ,vଶ,⋯v୬ሽ中的任何一个排列，该站点的排列就构成一个解，并对应一种定制公交的路径设计方案。（3）初始解的选定：令当前解的为初始解，表示为χ଴ሼvଵ,vଶ,⋯v୬ሽ，当前的迭代步数k=0，当前的温度t୩=t୫ୟ୶。（4）初始解的评价：判断初始解的可行性，首先将vଵ作为第1条线路的其实乘客站点，判断其是否满足约束条件，若：qଵqଵ൑C୩，γ୫୧୬൑ൗC൑1୩这时可将vଶ作为第1条线路的的第2个乘客站点，判断其是否满足定制公交车辆约40 束、实载率约束和绕行距离约束，即是否满足：q൅q൑C，γ൑qଵ൅qଶ୩൑ωS；若能满足这时可将vଵଶ୩୫୧୬ൗC൑1，Sଵሺ୬ାଵሻଵሺ୬ାଵሻଷ୩作为第1条线路的第3个乘客站点，若vଷ不能满足约束条件，由此可得第1条路径的为{vଵ→vଶ→v୬ାଵ}。然后则将vଷ纳入到第2条路径的起始点，依此类推，按上述方法可将解中的其他乘客站点也依此加入到其他路线当中。这种解的表示方法，保证了路线的数量小于安排的车辆数，在这搜索路径的过程当中，引入罚函数的方法来表示对不可行解的评价。即若排在最后的若干个站点不能纳入到定制公交线路当中，则说明该解为一个不可行解，设其对应的线路设计方案中的不可性路径为M（M=0表示该解为一个可行解），该线路方案的目标函数值为Z，并设对每条不可性路径的惩罚权重为P୵，则解的评价值E可用如下公式进行计算：EൌZ൅MൈP୵（5）新解的产生：从用2变换法从解中随机选择的2个元素，交换其在解中的位置可得到原解的邻居，如从领域解Nሼvଵ,v୳,v୳ାଵ⋯,v୴,v୬ሽ，随机选择一个邻居解，产生新解Nᇱሼv,v,v⋯,v,vሽ。ଵ୴୳ାଵ୳୬（6）代价函数差：对产生的新解，路径函数差可以表示为：∆fൌfሺNᇱሻെfሺNሻ其中fሺNሻ=Z+MൈP୵，Z表示解中路径的总长度，也就是目标函数。1∆f൏0（7）接受准则：Pൌቊ∆୤expቀെቁ∆f൒0୲ౡ∆୤如果∆f൏0，则接受新的解的路径方案，否则，以概率expቀെቁ接受新的路径，୲ౡ∆୤即若expቀെቁ大于0到1之间的随机数则接受。୲ౡ（8）选定利用的降温系数即t୩ାଵ←αt୩，0൑α൑1，进行降温处理得到新的温度。（9）用选定的终止迭代步数，判断退火过程是否结束，输出当前状态，得出最优的路径方案。4.4.3算法解的分析利用模拟退火算法求解定制公交线路设计的模型，结合定制公交路线设计问题的规模，确定合理的惩罚权重、初始温度、总降温次数、迭代步长、降温次数，得出定制公41 交线路的线路设计方案。路线的行车路线表示为{v୩ଵെv୩ଶെ⋯െv୩ሺ୬ାଵሻ}，路径的总里程为每条路径线路行驶长度的总和。4.5本章小结本章根据定制公交的实际运营特点，结合线路设计过程中所要达到的相关目标和满足的约束条件，建立了以最小化行驶里程为目标函数的线路规划模型。设计了符合线路设计模型的模拟退火求解算法，很好的将模拟退火算法与定制公交线路设计问题结合，从理论上，得出定制公交线路设计的求解方案和结果，为定制公交线路设计的实践研究提供了一定的科学依据。42 第五章案例研究为了验证本文所研究的定制公交问题主要内容和方法在实践问题中是否具有可操作性和实施性，选取了西安市高新区高新国际作为研究开通定制公交的案例进行研究。5.1背景近年来，西安市在高新区高新国际开通“定制公交”的可行性越来越明显突出，绝大多数就职于高新国际的上班族也为此而感到振奋，“定制公交”的一人一座、快捷到达、舒适便利的特殊运营模式也受到了很多人的很好反响。高新国际位于西安市的中央商务区，是办公、商业、住宅、写字楼密集区域，通勤人数较多。近年来，随着高新区的外向型经济发展呈现出良好的趋势，成为了层次高，功能齐全的商务综合区，原有的交通服务水平和道路网络条件不足导致了该区域人们的出行和停车困难。与此同时，随着越来越多知名企业的进驻，工作人员整体的收入水平和消费水平较高，能承受较高票价的支付能力，希望得到能区别原有交通服务水平的个性化交通服务来满足其便捷、舒适的交通出行，对定制公交的个性化服务接受性相对较好。因此，本文在高新区写字楼规模、地理位置、企业规模等方面的分析比较之后，高新国际开通定制公交的实施性较其他的相比更加具有代表性。5.2通勤现状与需求分析（1）通勤现状分析为了了解高新国际绝大部分上班族的出行方式以及定制公交需求，在高新国际写字楼和商业区展开了实地调查，共取得了300个调查样本。在调查的样本当中，被调查者绝大部分为该区域的上班族，出行时段主要集中在早晚高峰通勤时期。样本数据显示，选择通勤的工具主要为公共交通（包括地铁、常规公交）、出租车、自驾车和自行车等。其中调查选择公共交通和出租车作为通勤工具所占比例最高，达到59.4%，选择自驾小汽车作为通行工具的为20%，不同通勤方式所占的比例如下表5.1。而定制公交的开通，主要是为了吸引更多的自驾车主放弃小汽车而转移到多元化公共交通上，对于那些通勤距离较近而采用步行或者自行车方式出行的人群来说，吸引力不大。因此，由调查的数43 据来看，自驾车主所占的比例对于开通定制公交来说还是有一定的可行性。表5.1通勤方式的比重通勤方式人数有效百分比自驾车6020%公交车/地铁/出租17859.4%拼车206.6%自行车124%步行3010%合计300100%据调查，高新国际的绝大部分上班族大部都没有居住在上班地附近，这样的客观现象使得上班族们的通勤需求具有较多不便之处。在调查样本当中，约53%的上班族居住地离上班地点超过了10公里，约28%的上班族居住地离上班地点较近，可以通过自行车或者步行的方式快速到达。52%的分上班族上下班通常是通过多次换乘公交或者地铁而到达的，耗费时间较长。44%的上班族上下班总通勤时间超过2个小时，且还是以路况良好，没有堵车的现象为前提。具体详见图5.1和图5.2。图5.1通勤距离分布情况图5.2通勤时间分布情况（2）定制公交需求开通定制公交服务不仅能够大大方便一部分上班族的通勤需求，而且能够很好的缓解城市高峰时段交通拥堵的局面。定制公交运营公司构建定制公交网络服务平台，通过基本信息的收集以及预报名的处理。在信息收集以及预报名过程中，对于开通至高新国际定制公交服务有需求的上班族有约130人，以一个或者多个的乘客群的形式分散分布在各个地点，从地图上找出有定制公交需求服务乘客的居住地点，统计共有60个乘客群居住地点。为了便于数据处理，将60个乘客群,用编号为S1—S60的相对坐标位置来表示，用编号为S61代表目的站点位置，具体坐标位置和乘客数如下表5.2所示。44 表5.2各乘客坐标值乘客群序号横坐标纵坐标包含乘客数坐标序号横坐标纵坐标包含乘客数S14.618.42S312.45.22S23.815.62S322.25.52S33.615.42S332.45.13S43.915.63S34453S52.311.32S354.15.41S62.511.42S364.25.21S72.411.43S374.318.62S82.6112S388.412S91.24.22S398.11.81S101.44.63S408.81.22S116.415.61S418.51.13S126.315.82S426.41.52S136.615.82S436.41.22S143.610.13S446.51.12S153.810.43S456.21.32S161.34.73S46410.22S171.24.92S474.210.62S183.615.32S482.2112S193.815.22S49211.62S203.414.81S502.311.52S21714.21S514.218.53S227.215.63S524.218.42S236.815.83S534.117.82S2424.83S5491.23S252.452S554.310.42S264.15.41S566.81.43S274.452S579.21.42S28211.63S5891.63S292.2122S599.21.23S309.61.41S608.21.22S6113.412.8（3）车型选择按照“一人一座“的配置原则，依据调查需求分析为130人，依照最大上座率的要求以及公式（3.2）车型选择模型，结合实际的道路运输情况，确定定制公交车型为35座旅游商务班车。（4）运力配置考虑到定制公交的站点布置特性，仅会在起点一定范围内设少数站点，行驶途中几45 乎没有停靠点。因此，一般情况下，线路上每个站点之和的乘客数小于或等于车的最大容量，采取早高峰发车，晚高峰回车，其余时段不发车的发车频率模式，一条线路，发车次数两次，发车时段为早晚高峰时段。（5）运营时间安排根据实际线路设计的情况和乘客的特殊需求，合理安排早上的发班时间和晚上的收班时间，满足乘客的特殊时间需求以及保障定制公交的便捷、高效的运营特性。（6）定制公交票价机制在文章3.2节票价机制优化的前提下，按照政府监管的政策原则，为了维持定制公交客户群的稳定性和公司的经济效益，拟定采取月票的票制形式进行费用收取，在满足服务水品的前提下，根据线路运营的距离等级规定票价。5.3线路设计方案5.3.1合乘站点的布局根据调查的已知条件和各乘客群所在的坐标位置点，其单独的乘客分散较多，如果实现定制公交“门到门”的服务，则途中所需要耗费的时间和绕行的距离也较多。因此，为了保障定制公交的服务水平和快速直达的特性，本文采取K-means聚类分析的方法，将需求类似，距离相近的预约乘客集聚成为一类，再根据聚类的乘客之间的距离要素设置站点的服务范围半径，得出具体的站点布局方案。（1）k-means聚类分析的实现利用K-means算法对60个乘客群进行区域划分（不包括目的地高新国际），乘客群所在的位置坐标点൫w୫୧，w୫୨൯如上表5‐2所示。依据3.3所示k-means算法的实现步骤，利用计算机编程对所求的聚类中心区域所包含的乘客数和具体坐标位置进行求解，具体操作如下：Step1：根据所调查的情况，将60个乘客归纳为一个大的数据集，即m=60，数据集S中包含60个对象元素。Step2：定制公交线路一般对站点设置的数量有一定的限制，本文结合定制公交站点设置的形式和乘客需求数量的规模，拟定10个聚类中心，设置n=10。Step3：测量所有没被选择为聚类中心的顾客群到聚类中心的距离，根据其距离的平46 均值情况，按照最近原则，把顾客群分别归类到距离其最近的聚类当中。使得聚类中所包含对象的元素彼此之间具有一定的相似性，又区别与其他聚类中心所包含的对象元素。Step4：根据公式（3.6）对上述第三步聚类中心所包含的元素对象进行调整，得出新的聚类中心和所包含的对象。Step5：根据公式（3.7），进行多次迭代计算，当结果变化不大时则结束计算，输出结果，得出最终的聚类中心位置以及所包含的对象元素。通过k-means算法,最终获得的聚类中心为S2、S7、S1、S9、S23、S15、S32、S36、S40、S56。具体结果如下表5-3所示表5-3各聚类中心确定值编号聚类中心包含对象元素包含乘客数ZଵS2S2、S3、S4、S18、S19、S2012ZଶS7S5、S6、S7、S8、S28、S29、S48、S49、S5020ZଷS1S1、S37、S51、S52、S5311ZସS9S9、S10、S16、S1710ZହS23S11、S12、S13、S21、S22、S2312Z଺S15S14、S15、S46、S47、S5512Z଻S32S24、S25、S31、S32、S3312Z଼S36S26、S27、S34、S35、S368S38、S39、S40、S41、S54、S57、S58、S59、S60、ZଽS4022S30Zଵ଴S56S42、S43、S44、S45、S5611（2）站点服务范围的确定以聚类中心坐标为定制公交的乘客合乘站点的位置，设置服务半径d为500m，判ଶଶ断顾客群是否满足ට൫x୧୴െr୧୨൯െ൫y୧୴െc୧୨൯൑d，若满足则把其纳入到本次开通线路，若不满足则纳入到后期线路的招募当中。因此，根据公式得出，顾客群S20、S29、S53、S21、S39、S30、S60不满足站点服务范围的约束，因此，将这些顾客群纳入到后期招募的线路当中。（3）结果分析根据k-means聚类分析的实现和站点服务范围的确定，定制公交站点所服务的乘客人数为120人，则定制公交乘客合乘站点的布局结果如下表5-3所示：表5-3各乘客站点坐标值编号聚类中心包含对象元素横坐标纵坐标包含乘客数ZଵS2S2、S3、S4、S18、S193.815.61147 ZଶS7S5、S6、S7、S8、S28、S48、S49、S502.411.418ZଷS1S1、S37、S51、S524.618.49ZସS9S9、S10、S16、S171.24.210ZହS23S11、S12、S13、S22、S236.815.811Z଺S15S14、S15、S46、S47、S553.810.412Z଻S32S24、S25、S31、S32、S332.25.512Z଼S36S26、S27、S34、S35、S364.25.28ZଽS40S38、S40、S41、S54、S57、S58、S598.81.218Zଵ଴S56S42、S43、S44、S45、S566.81.4115.3.2定制公交的线路设计当乘客站点服务区域划分以及站点的位置确定结束后，把上述所求的10个乘客站点分别纳入到定制公交线路设计中，在线路设计数学模型的基础上，用模拟退火算法求解得出目标函数的最优解，得出路线设计方案。（1）已知条件已知公交公司用来开通定制公交的车辆数为6，车辆额定载客量为35人，在线路规划过程中必须达到γ୫୧୬ൌ75%的最低载客率，ω=1.3才有运行的可能性，在行驶的过程中以平均速度行驶。根据前期乘客的调查和站点之间的坐标，可以计算出各站点相互之间以及站点和目的点之间的距离和需求，具体如下表5.4：表5.4各乘客站点相互之间的距离以及需求量d୧୨VଵVଶVଷVସVହV଺V଻V଼VଽVଵ଴VଵଵVଵ04.42.911.735.210.210.415.214.512.5Vଶ4.407.37.36.21.75.96.51210.911.1Vଷ2.97.3014.63.4813.113.217.717.110.4Vସ11.77.314.6012.96.71.63.28.26.314.9Vହ36.23.412.906.211.310.914.714.47.2V଺5.21.786.76.205.25.210.59.59.9V଻10.25.913.11.611.35.2027.96.213.4V଼10.46.513.23.210.95.2206.14.611.9Vଽ15.21217.78.214.710.57.96.10212.5Vଵ଴14.510.917.16.314.49.56.24.611.9013.2Vଵଵ12.511.110.414.97.29.913.411.912.513.20q୧111891011121281811—（2）参数设定根据上述10个乘客站点的乘客需求量以及距离，在运用模拟退火算法对其求解过程当中，设定初始温度t଴为100，总的降温次数T为100，每次降温的迭代步长N为40，48 降温系数α为0.99。在计算机程序中输入已知条件d୧୨，n，q୧等，以及算法的运行参数初始温度t଴、总降温次数T、每个温度下的迭代步长N、降温系数α。结合已知的约束条件，按照4.3.3的算法设计步骤，运用计算机编程MATLAB实现目标函数的最优，程序实现模块，运用计算编程和上述4.4所涉及的算法求解。（3）求解结果把上述实例中的数据带入到模型程序当中，随机求解10次，得到的模型结果如下表5.5。表5.5模拟退火算法计算结果表计算次序12345678910平均使用车辆数44444444444配送总里程（km）56.158.564.662.455.160.858.464.462.958.360.2首次搜索到最终6653584842484650616453.6解的降温次数计算时间0.760.760.760.760.760.760.760.760.760.760.76根据上述表5.5可以看出，在10次对线路设计模型求解的过程中，所得到的解的构成元素，质量都相对较高。其中，服务车辆数的平均值为4，比已知条件平均节省2辆车。行驶的总距离的平均值为60.2km。在第5次的随机求解过程中，所得到的解的质量相对最优，其行驶总里程为55.1km，车辆数为4。因此，该最好解对应的4条路径方案为：路径1：V଴→Vଵ→Vଷ→Vହ→Vଵଵ；路径2：V଴→Vଶ→V଺→Vଵଵ；路径3：V଴→Vସ→V଻→V଼→Vଵଵ；路径4：V଴→Vଵ଴→Vଽ→Vଵଵ。（4）结果分析从模拟退火算法求解线路设计模型的10次随机求解过程来看，能以平均值为0.76s的计算效率快速的求出模型的解，而且首次搜索到最终解的平均迭代步数仅为53.6。可见，对于小规模的定制公交线路设计问题来说，模拟退火算法能以较高的计算效率和较少的迭代步数求解到问题的最优解或近似最优解，路线设计方案分析如下表5.6和5.7所示：表5.6最优线路方案表运营里程线路序号上车点服务量各上车站点服务乘客数载客率（km）11-3-531（11,9,11）13.588.5%22-630（18,12）11.685.7%34-7-830（10,12,8）15.585.7%410-929（11,18）14.582.8%49 表5.7线路站点乘客绕行距离分析表直达里程定制公交行驶里平均绕行距离线路序号乘客站点绕行距离（km）（km）程（km）（km）112.513.51.51310.410.60.21.2357.27.20211.111.60.520.2569.99.90414.915.50.63713.413.90.50.36811.911.901013.214.51.340.65912.512.50按照线路方案的结果，一方面，每条定制公交线路的载客率都达到了80%~85%之间，保障了公司的收入效益；另一方面，每条线路的站点平均绕行距离不大，控制在1.5km以内，属于乘客能够接受的范围，保障了定制公交“快速直达”的运输特性和服务水平。因此，从结果分析可知，本文提出的定制公交乘客站点确定的思路和方法，能很好的满足其布局的“趋同性、聚集性和唯一性”三项基本原则，为线路设计方案的提出做好了基础铺垫，线路设计模型和算法的设计，具备了很好的适应性和实践性。二者相互结合运用，能够从提供定制公交服务的企业以及乘坐乘客的角度两方面综合考虑，进而得出定制公交线路整体最优方案，在成本与服务水平之间找到了均衡点。5.4本章小结在对定制公交的整体问题进行分析后，本章首先分析了西安高新国际的地理优势和实际的通勤出行现状分析，明确了在高新国际开通定制公交线路的可行性。其次，通过调查问卷的方式收集了定制公交开通的预约需求客流，按照配置问题的优化方法，从资源配置、站点布局以及线路设计等方面展开了实际问题的分析与研究。最后，很好的将理论研究基础和实际相结合，验证了定制公交线路设计模型和算法的可操作性和实施性。50 结论与展望1本论文的主要结论当前，我国很多大中城市和地区都在积极探索和推广定制公交服务，为广大城市居民特别是深受职住分离困扰严重的上班族提供便利。而随着定制公交服务的不断深入和发展，合理的规划定制公交运营的线路也是一件非常关键的事情，本文经过研究主题、研究内容的构思和酝酿，研究理论的准备，研究资料的收集整理，研究手段和方法的探索，最终完成了论文的撰写，获得了如下的一些成果。（1）提出了定制公交新型客运模式以及路线设计优化的研究意义，对比国内外相关研究现状，总结提炼关于运营模式、站点选址、车辆路径、线网优化的研究成果。结合定制公交的运行特性，指出了在线路上设计和站点布局问题研究上的不足和缺乏，引出了本文研究定制公交的主要内容和研究思路。（2）提出了定制公交的定义和运营特点，分析了早期关于“定制”特点的“楼巴”、“社区通勤快车”等服务模式的运营问题，总结了国内相关一部分城市（北京、青岛、大连等）的定制公交发展状况。在此基础上，从通勤出行现状的改变和公共交通服务水平持续低效两个方面来引出了定制公交发展的必要性。以及今后发展过程中有待改进和研究的问题，进一步提高了对定制公交的认识。最后总结阐述了定制公交研究过程中与站点选址和线路设计的相关理论基础。（4）通过对定制公交发展过程中需要解决的实际问题归纳和提出，得出了在前期资源配置、站点的选址布局和线路设计的定制公交配置问题优化方法。（5）结合了聚类分析方法和定制公交实际运营特性，提出了K-means聚类分析方法和范围覆盖公式来确定定制公交站点的选址与布局，解决了线路设计问题的关键一步。（6）结合了定制公交线路设计中的载客率、容量限制、绕行距离限制等实际约束条件，建立了以行驶总里程为目标的定制公交线路设计模型。在分析模型特点和解的构成之后，设计了模型的求解方法并采用了拟退火算法求解线路设计模型，得出线路设计模型的最优解。（7）通过在西安高新国际开通定制公交的实际背景，从一开始的客流调查到之后线路设计，做了较为细致的研讨和研究，针对具体的调查数据对模型和算法进行验证，51 测试结果表明，本文提出的模型和算法在实际问题的应用，具备实际操作性和可行性2主要的创新点定制公交是城市客运发展过程中的一种新型模式，本文是对一种新型模式在理论和实践上的探讨，主要的创新有：（1）定制公交站点的选址布局：提出了符合定制公交实际特点的站点选址的步骤，利用聚类分析方法和服务范围限定来实现站点的选址与布局，既具有较为清晰的研究思路，也深化了选址布局问题的研究。（2）路线优化设计：对于具有“定点、定时、定车”的定制公交运营特性，本文从成本、服务水平和公平性来考虑设计目标，巧妙的将“快速直达”的服务水平和“均衡载客率”的公平性目标在约束条件中体现，构建了运营成本为优化目标的函数模型，是对一般车辆路径问题在理论和实践上的探索的创新。（3）算法的设计：在路线设计模型的基础上，分析了模型解的构成情况，将模拟退火算法的实现原理与定制公交实际的运营情况进行有效的结合，使得模拟退火算法在新的问题模式上有了进一步的应用。3有待进一步研究的问题相对于一般的大众出行行为方式来说，定制公交出行方式的选择更加具有时间和空间上的确定性。一方面，这种出行方式的产生，既会影响到人们的日常出行活动，也会对城市交通情况产生影响；另一方面，随着城市规模的扩大和城市居民职住分离现象的突出，通勤出行行为更是会出行形式多样化、时间和空间集中化、数量规模化的特点。因此，综合本文的研究成果和所考虑的实际条件，今后有待进一步研究的问题主要有：（1）首先，涉及到乘客合乘站点和目的地需求对应时，本文只是单纯的考虑了一个目的站点的调查与研究，这与实际的校车路径和企业通勤班车的运营情况有一定的相似性，没有很好的体现定制公交的特殊性和个性化。之后的研究工作可以进一步的研究定制公交混载乘客的情况，也就是一个车辆中乘客的目的地和时间需求不同的问题。（2）本文在建立定制公交路线设计模型时，将早晚高峰时城市交通状况所带来的问题影响虚拟化。而在实际问题过程中，交通拥堵问题所带来的时间消耗和距离绕行是52 不可避免的，因此可能在一定程度上影响了到达站点的时间安排不准时现象。因此，在设计定制公交线路设计时就应该考虑这方面的因素，而达到线路设计最大的效益是我们将来研究的重点。（3）本文在构建线路上模型时，为了将问题得以简化，设置了较多的模型假设条件，只考虑了单目的单车型的条件。而在实际过程中，多车型的选择配置可能更加有利于定制公交车辆资源的有效利用，因此，问题的进一步复杂化将更加具有实际的操作性。（4）定制公交问题的研究在中国还处于初步阶段，很多关于政策、规划、机构组织、运营、行业管理等方面问题没有深入研究，今后研究问题可以从这些问题多方面的展开探讨和研究。53 参考文献[1]徐康明,李佳玲,冯浚等.定制公交服务初探[J].城市交通,2013,11(5):24-27.[2]李震宇,胡欣竹.浅谈定制公交发展现状及启示[J].城市道桥与防洪,2014,(11):26-32.[3]李彬.定制公交与定制公交客车研究[D]:[长安大学博士学位论文].西安:长安大学,2014,43-62.[4]程立勤.基于点线面层次分析法定制公交线网布局[J].大连交通大学学报,2014,35(3):23-26.[5]张露.城市通勤商务班车运营模式研究[D]:[长安大学硕士学位论文].西安:长安大学,2014,7-15.[6]HamiltonB.Wastefulcommuting.TheJournalofPoliticalEconomy,1982,90(5):935-953.[7]叶英杰.基于空间co-location模式挖掘的城市公交站点的选址分析[D]:[云南大学硕士学位论文].昆明:云南大学,2014,6-24.[8]高选幸.校车路径算法研究及管理系统的设计与实现[D]:[中国计量学院硕士学位论文].杭州:中国计量学院,2014,22-34.[9]王林,陈大鹏.公交站点选址的分析与模糊评判[J].交通科技与经济,2009,(6):47-49.[10]张富,朱泰英.校车站点及线路的优化设计[J].数学的实践与认识,2009,(04):141-145.[11]吕林.城市公交站点设计优化设计方法研究[D]:[东南大学硕士学位论文].南京:东南大学,2006,24-31.[12]党兰学,陈小潘,孔云峰.校车路径问题模型及算法研究进展[J].河南大学学报,2013,43(6):682-691.[13]党兰学.大规模混载校车路径问题优化算法研究[D]:[河南大学博士学位论文].开封:河南大学,2014,14-26.[14]赵冬玲.一种车辆路径规划的新型蚁群算法研究[J].店子器件,2014,37(3):519-523.[15]洪联系.带时间窗口动态车辆路径规划模型及其求解算法[J].计算机工程与应用,2012,48(4):244-249.[16]余明珠,李建斌,雷东.装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J].中国管理科学,2010,18(2):89-95．[17]王杰.车辆路径规划的连续多目标优化模型设计及其求解方法[D]:[西安电子科技大54 学硕士论文].西安：西安电子科技大学,2013,21-27．[18]KimBI,KimS,ParkJ.Aschoolbusschedulingproblem[J].EuropeanJournalofOpera-tionalResearch,2012,218:577-585.[19]Euchi,J,MraihiR.TheurbanbusroutingproblemsintheTunisiancasebythehybridartificialantcolonyalgorithm[J].SwarmandEvolutionaryComputation,2012(2):15-24．[20]GroerC,GoldenB,WasilE.Alibraryoflacalsearchheuristicsforthevehiclerou-tingproblem[J]MathematicalProgrammingComputation,2010,2(2):79-101.[21]BentR,PVanHentenryck.Atwo-stagehybridalgorithmsforpickupanddeliveryvehicleroutingproblemswithtimewindows[J].Computers&OperationsResearch,2006(33):875-893.[22]ValerieGuihaire,Jin-kaoHao.TransitNetworkTimetablingandVehicleAssign-mentforRegulatingAuthorities[J].Computer&IndustrialEngineering.2010,59(1):16-23.[23]RolfBorndorfer,MarikaNeuman.ModelforLinePlaningwithTransfer[R]Germany.2010:1-15.[24]王炜,杨新苗,陈学武等.城市公共交通系统规划方法与管理技术[M].北京:科学出版社,2006.42-57.[25]张杰林,王炜,陈学武.城市常规公交线网的“一路一线”布局构想[J].交通运输工程与信息学报,2010,8(1):96-102.[26]王毅之.基于节点度和介数相结合的城市公交线网优化模型与求解算法研究[D]:[吉林大学硕士学位论文].长春:吉林大学,2014,13-32.[27]魏华.轨道交通与常规公交衔接优化关键问题研究[D]：[长安大学博士学位论文].西安:长安大学,2014,22-25.[28]俞洁,潘述亮等.基于服务分区的常规公交枢纽布局优化模型[J].交通运输系统工程与信息,2014,14(4):113-120.[29]高健.基于居民出行行为的城市多级公交线网时空协调优化理论与方[D]:[北京交通大学博士学位论文].北京:北京交通大学,2014,13-20.[30]姬海,王宇,吕凯.城市公交线网优化模型系统设计[J].电子技术与软件工程,2015,(1):4-12.[31]北京交通发展研究中心.2013北京市交通发展年度报告[R].北京:北京市交通委员会,55 北京交通发展研究中心,2013.[32]杭州市综合交通研究中心.2011杭州市年度交通发展报告[R].杭州:杭州市城乡建设委员会，杭州市综合交通研究中心,2012.[33]朱清新.聚类分析及其应用研究[D]:[西安电子科技大学博士学位论文].西安:西安店子科技大学,2010,25-34.[34]郎茂祥.配送车辆优化调度模型与算法[M].北京:电子工业出版社，2009.25-48.[35]赵子燕.基于模拟退火算法的启发式算法在VRP中的应用[D]:[华中师范大学硕士学位论文].武汉:华中师范大学,2013,4-18.[36]倪庆剑,邢汉承,张志政,王蓁蓁.蚁群算法及其应用研究进展[J].计算机应用与软件,2008,25(8):12-16.[37]高健.基于居民出行行为的城市多级公交线网时空协调优化理论与方法[D]:[北京交通大学博士学位论文].北京:背景交通大学,2014,52-89.[38]徐笑梅,常玉林,李晋.基于低碳理念的公交线网优化模型[J].交通信息与安全,2012,(2):18-24.56 致谢经过硕士研究生两年的学习、研究与探索，让跨专业的我逐渐对交通运输专业有了一个全面的了解和认识，这些成绩都离不开我的导师胡列格。本次论文也是得益于胡老师的多次指导，在此我向他表示最真诚的感谢。回想起来，本是道路工程专业的我，凭着对交通大专业的热情与爱好，选择了交通运输规划与管理方向继续研究深造。尽管当时对交通专业的知识了解甚少，但是胡列格导师并没有因为我对交通知识的缺乏而对我丧失信息，始终以他那严谨的学术作风和细致的治学态度对我多方面的进行指导，让我无论是在理论知识还是在做人做事方面，都得到了很大的进步。因此，感谢您多年来的谆谆教导，感谢您一直以来在学术和生活方面给予我的关怀我帮助。其次，还得感谢团队的王佳老师两年来对我的多次帮助和指导，教会我将理论知识很好的结合到实际当中，获得了很多在研究项目中的实践机会。同时也感谢我的周百会、夏云等多位师兄师姐在学习和生活上对我的照顾，是你们让我开心愉快的度过了研究生生活。最后，向所有帮助和关心过我的老师们、同学们表达我最真诚的谢意。刘喜2015年4月57