下载文档原格式
2007B题：乘公交，看奥运（数据有变化）我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。
这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。
针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。
请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。
并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时：6分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：5分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：8分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。
【附录2】公交线路及相关信息（见公汽线路信息，对原数据文件B2007data.rar 有少量更改）城市公交线路选择优化模型摘要本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。
公交中乘车时间和线路的最优站点摘要：公交车站点的选址问题，和乘车时间，对于这个问题的研究也比较多。
本文针对玉溪师范学院学生乘坐公交车问题进行调查研究，采用离散模型中嵌套连续模型。
把整个路线以站点为界划分为n+1个区间，由于区间内的乘客要向最近站点走去，首先，通过提出合理的假设且基于限制条件：所有站点间距之和最大程度接近路线总长；先对每一个区间长度进行计算；其次，要使所有乘客花费的总时间最少，只要每一个乘客所花费的时间最少即可，故又将整个路线划分为n+1个时间段，令同一个时间段内的每一个乘客所花费的时间相等，接着对每一个时间段的所有乘客所花费的时间ti (i=1,2…n+1).进行计算，即在区间内采用连续模型；最后，将所有乘客所花费的时间求和。
本文围绕乘车时间的问题实际调查合理的假设、严密的逻辑分析、精确的计算，得出乘客乘车时间过长和站点选址的影响。
基于条件：(1)所有站点间距之和最大程度接近路线总长;(2)乘客所花时间最少。
对于调查实际和假设的参数，计算得到设置4个站点较为合理。
此时平均每个乘客花费时间0.659742小时,相邻站点之间的距离从L1=0.5公里依次递增。
关键词：公交车乘车时间站点选址离散模型一，问题提出城市公共交通是城市重要的交通运输工具，公交车的经济实惠和方便快捷的优势受到了广大人民的青睐，但是也存在着许多弊端。
本文首先调查了玉溪师范学院东大门，西大门和东北门2路和3路公交车的等候时间，测出学生从宿舍出发乘车步行时间，并对在校部分学生做了相应访谈，然后统计数据并用概率和统计的知识进行分析讨论了公交车的等候时间问题；进而建立数学模型分析推导出乘客公交车等候的时间T,并针对玉溪师范学院乘坐校门口公交车等候时间过长的原因进行研究调查结果具体数据见附录中表格。
就学生乘坐2路和3路公交车而言,乘车前学生步行需要花费时间，公交车等候也需花费时间，为了节约每一位乘客的乘车时间,加之每辆公交车的容量有限,这就要求对站点设置做合理的规划。
公交车公交站调度与路径优化技术研究公交车是城市公共交通系统中的重要组成部分，为广大市民提供便捷、经济的出行方式。
公交车调度与路径优化技术是提高公交运营效率、缩短乘客出行时间以及减少城市交通拥堵的重要手段。
本文将对公交车调度与路径优化技术进行研究，并分析其在提高公共交通服务质量方面的应用价值。
一、公交车调度技术公交车调度是指对公交车辆进行合理安排，以实现运力的充分利用和公交线路的正常运行。
公交车调度技术的关键是确定公交车站的发车间隔时间和车辆的到站时间，从而降低乘客的等待时间和排队长度。
1. 调度模型调度模型是公交车调度技术的核心工具，它建立了公交车站与出租车站之间的关系，并根据车辆实时位置、乘客需求以及交通状况等因素来制定最佳调度方案。
常见的调度模型有线性规划、动态规划和模拟仿真等。
2. 乘客需求预测准确预测乘客需求是公交车调度的关键环节，其结果直接影响到公交车站的发车间隔时间和车辆的到站时间。
乘客需求预测可以通过历史乘客流量数据、天气状况、节假日等因素进行分析和预测。
3. 线路优化线路优化是指通过对公交车线路进行调整，以减少公交车的里程、提高运行速度和减少交通拥堵。
线路优化可以采用离散优化算法、遗传算法和蚁群优化算法等。
二、路径优化技术路径优化技术是指通过优化车辆行驶路径，以减少公交车在路上的时间和里程，提高公交车的运行效率和服务质量。
1. 路况检测与导航路况检测与导航是通过安装在公交车上的导航仪、传感器等设备实时获取路况信息，包括交通流量、交通信号灯状态、道路堵塞情况等。
通过收集和分析这些信息，可以为公交车提供最佳行驶路径，避开拥堵路段。
2. 特殊区域路径规划城市中常存在一些特殊区域，如施工区、限行区等，这些区域对公交车行驶路径产生一定的限制和影响。
路径优化技术可以通过预先规划合适的绕行路线，避免这些特殊区域。
3. 车辆密度平衡城市公交车通常面临车辆密度不均衡的问题，有些区域车辆密度较高，而有些区域车辆密度较低。
服务轨道交通的接运公交候选路线生成与布局优化在城市发展过程中，随着人口的增长和交通需求的提升，轨道交通系统已经成为现代城市交通的重要组成部分。
但是，单纯依靠轨道交通系统无法满足整个城市的交通需求，因此需要与其他交通方式进行衔接。
接运公交是一种重要的衔接方式，可以在轨道交通车站附近提供短程接驳服务，方便乘客的出行。
生成接运公交候选路线的具体方法可以分为以下几个步骤：1.数据收集与分析：通过调查乘客的出行需求、轨道交通线路的客流分布、周边道路交通情况等，收集相关数据，并进行分析。
根据数据分析的结果，确定候选路线的起点、终点以及途经的衔接点。
2.路线规划：根据起点、终点和衔接点确定候选路线的大致走向，考虑交通状况、道路宽度、车流量等因素，确定具体的道路线路。
3.站点布局：确定接运公交的站点布局，使其能够与轨道交通站点紧密衔接，方便乘客的换乘。
站点布局需要考虑乘客出行的需求，尽量减少乘客的步行距离，提高公交接驳服务的便捷性。
4.优化路线与站点：通过模型计算和仿真分析，对候选路线和站点布局进行优化。
优化目标可以包括最小化乘客的换乘时间、最大化接运公交的服务范围、最小化公交车辆的行驶里程等。
通过不断调整路线和站点的位置，找到一个较优的方案。
5.风险评估与决策：评估候选路线和站点布局的风险，考虑可能出现的交通拥堵、道路施工等因素对接运公交服务的影响。
根据风险评估结果，综合考虑各种因素，做出最终决策。
在接运公交候选路线的布局优化过程中，还需要注意以下几个方面：1.多元化出行需求：不同乘客有不同的出行需求，有些乘客需要直达服务，有些乘客需要短途换乘服务。
因此，在候选路线的布局中应尽量满足不同类型乘客的需求，提供多样化的接运公交服务。
2.轨道交通线路覆盖：在候选路线的布局中，应尽量考虑轨道交通线路的覆盖范围，使接运公交线路能够补充轨道交通的短板，提供更完善的交通服务。
3.站点信息公示：在接运公交站点布局中，应考虑乘客的信息获取能力，设置站点信息公示牌、导向标志等，提供准确的信息，方便乘客的换乘和出行。
摘要本文是为了开发一个解决长沙市公交线路选择问题的自主查询计算机系统。
在充分理解题意的基础上，我们从总体上把握，一致认为这是运筹学中的最短路问题。
我们所提供的这个系统，对于当乘客输入起始站和终点站，点击查询结果后，查询机就能很快地给出乘车路线及乘车所需要的最短时间，并且还可以给出相应的乘车费用。
也可以在有多个乘车站点的情况下，自主选择出最优乘车顺序以及相应的乘车最短时间和乘车费用。
公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。
针对市场需求，我们设计了一个解决公交线路选择问题的自主查询计算机系统。
其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。
对于问题一，在仅仅考虑公共汽车的换乘的时候，我们以最短的乘车时间和最优的乘车费用作为两个目标函数，建立相应的双目标规划模型：()Tmin和()Mm in。
对于问题二，在问题一的基础上，我们添加了排列组合模型，全列出所有的乘车顺序情况，由问题一所建模型求出各种情况下的最优时间和最优路费，然后综合比较选出所有情况中的最优乘车顺序。
利用Dijkstra算法解出我们所需要的结果。
我们同样利用了双目标函数的统筹规划原理，在Dijkstra的算法下，解决了在公共汽车换乘的问题，求得最短时间问题，找到了最合适的公交路线，均为最短的乘车时间和最优的乘车费用，从而更加完善了我们的公交系统。
本文的特点是在建立模型和算法的基础上，进行编程，使其具备系统查询功能，克服了人工查询数据的繁杂过程，使得到的结果更为准确，同时，此程序可以进行推广使用，为解决日常生活中最优路径的选择问题提供了方法，给人们的出行带来方便。
关键词：最短行程双目标网络模型 Dijkstra算法排列组合一、问题重述公共交通作为长沙市交通网络中的重要组成部分，由于公共交通对资源的高效利用，使得通过大力发展公共交通，实行公交优先成为缓解日趋严重的道路交通紧张状况的必然选择。
然而，面对迅速发展和不断更新的长沙市公共交通网，如何快速的寻找一条合理的乘车路线或换乘方案，成为长沙市居民和外地游客一个比较困惑的问题。
乘客公汽线路选择优化模型刘国英曹才子吴华香（三峡大学湖北·宜昌443000）摘要公汽是整个城市交通系统中的一个重要组成部分，在方便人们出行的同时也给乘客带来了线路选择的困扰。
本文给出任意两公汽站点之间线路选择问题的一般数学模型与算法，首先利用图论思想建立邻接矩阵，将其转化为有向最短线路问题，再根据公众出行对时间、费用和换乘次数的不同需求，建立单目标优化模型，得出单目标最优方案；此外通过建立多目标优化模型，还提供了同时考虑三种因素的综合最优方案，供乘客选择符合自己乘车需求的路线。
关键词图论思想最短线路单目标优化模型多目标优化模型中图分类号：TP301文献标识码：A1公汽线路选择分析1.1公汽线路的三种情况本文依据公汽行驶的轨迹，综合考虑实际情况后将公汽线路主要划分为三种类型：（1）上行线、下行线原路返回：这种线路有两个端点站，在两个端点站之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列。
由于路线的方向不同，因此上行线和下行线可抽象成两条线路处理，线路号与收费规则相同。
（2）环行线：对于环形线路，一次线路无重复经过的站点，以城市中心为基点，从始发站绕市中心行驶一圈到终点站，且始发站与终点站相同。
（3）往返线路不一致：上行线、下行线经过的站点不完全一致。
1.2公汽线路选择的影响因素随着城市化的加速，城市交通线路逐渐四通八达，公汽作为城市重要的交通方式之一，在优化城市交通，方便市民出行，发展城市经济等方面均发挥着重要的作用。
在实际生活中，公众乘坐公汽主要考虑步行时间、转乘次数、行程时间、车站始发情况、负载量及乘车费用等因素，其中转乘次数、时间、车费三个因素对乘客公汽线路的选择影响最大，因此本文主要基于这三个因素建立优化模型来设计不同的乘车方案以满足乘客不同的出行需求。
其中对于换乘次数，本文把换乘次数限制在转乘两次之内，这符合大多数乘客的乘车习惯，换乘次数分别为直达、一次换乘和两次换乘；时间由乘车时间和换乘时间决定，换乘时间包含步行时间和等车时间；费用的差别主要由换乘次数决定，换乘次数越多费用越高。
选址问题数学模型选址问题数学模型摘要本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。
通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。
对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题针对问题1：0-1规划的穷举法模型。
该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。
针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。
最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。
最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。
针对问题3：建立了双目标最优化模型。
首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8 、11 和12.5 ，三组巡视的总路程达到35.3 ，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。
城市公交换乘最佳路径选择的模型和算法
陈密芳
【期刊名称】《石家庄职业技术学院学报》
【年(卷),期】2009(21)6
【摘要】换乘是公共交通中常见的问题.为在公交换乘中选择最佳路径,建立了多目标选择的公交换乘最佳路径算法.其核心是通过建立线路关系矩阵,找到起始站点到目的站点3次换乘之内的所有换乘方案,根据优先考虑的目标从所有方案中选出最
佳路径,并同时考虑发车频率、各站间行驶时间和距离、转乘车行走的时间和距离、交通费用等实际因素.最后用一算例验证了该算法的有效性和合理性.
【总页数】4页(P22-25)
【作者】陈密芳
【作者单位】石家庄铁道学院交通工程分院,河北,石家庄,050061
【正文语种】中文
【中图分类】U121;O232
【相关文献】
1.城市公交最优路径选择的数学模型及其算法 [J], 王庆;潘荣英
2.城市公交换乘数据模型研究及算法实现 [J], 扈震;张发勇;刘书良
3.基于综合矩阵的城市公交网络模型的公交换乘研究及算法实现 [J], 谭泽芳
4.城市公交换乘的数学模型及其算法实现 [J], 王庆平;张兴芳;宋颖;于会增
5.基于深度优先遍历算法-回溯算法的公交网络限时免费换乘优化模型求解 [J], 魏金丽;范鑫贺;刘莲莲;刘阳;任杰睦;孙启龙
因版权原因，仅展示原文概要，查看原文内容请购买。
公交站场选址布局优化模型和算法魏明;陈学武;孙博【摘要】现有研究没有将公交站场选址和线路车辆停放调度作为一个整体,无法发挥整个公交系统的最大效率.针对此缺陷,根据不同线路的首末站在时间和空间上的停车需求不平衡性,综合考虑车场能力、建设成本和最大里程等现实因素,以极小化所有公交车的行驶里程为目标,建立一种公交站场选址布局优化模型,确定站场的最佳位置和泊位数,将各线路的所有车辆安排至相应站场.根据问题特征,设计求解该问题的两阶段启发式算法,给出了具体求解流程,并分析其计算复杂性.最后,结合一个算例,计算最佳的公交站场选址方案,分析参数灵敏性对其布局的影响程度,从而验证模型和算法的有效性.%Existing studies have not integrated bus station parked vehicle location and route scheduling as a whole, which cannot maximize the efficiency of the entire transit system. For the imbalance in time and space of number of parking vehicles belonged to all of start-end stops, this paper studies a mixed integer programming model for bus parking site layout optimization problem. The model involves how to determine the best location and the number of parking station, and arrange all vehicles belong to each route to the appropriate parking station. The objective is to minimize a total of round-trip mileages for all buses from start-end stops to parking stations, where some realistic constraints such as station' s capacity, construction costs and maximum mileage etc are considered. According to characteristic of the model, a two-stage heuristic algorithm, which gives specific solving process and analyzes its computational complexity, is proposed to obtain the model' s non-inferior solutions.Finally, a numerical example is taken to calculate its best scheme and analyze influence of parameters' sensitivity on them, which shows model and its algorithm' correctness and effectiveness.【期刊名称】《交通运输系统工程与信息》【年(卷),期】2015(015)004【总页数】5页(P113-117)【关键词】城市交通;站场选址布局;停车方案;两阶段启发式算法【作者】魏明;陈学武;孙博【作者单位】东南大学城市智能交通江苏省重点实验室,南京210096;南通大学交通学院,江苏南通226019;东南大学城市智能交通江苏省重点实验室,南京210096;南通大学交通学院,江苏南通226019【正文语种】中文【中图分类】TP301.6;U116.2Absttrraacctt：Existing studies have not integrated bus station parked vehicle location and route scheduling as a whole, which cannot maximize the efficiency of the entire transit system. For the imbalance in time and space of number of parking vehicles belonged to all of start-end stops, this paper studies a mixed integer programming model for bus parking site layout optimization problem. The model involves how to determine the best location and the number of parking station, and arrange all vehicles belong to each route to the appropriate parking station. The objective is tominimize a total of round-trip mileages for all buses from start-end stopsto parking stations, where some realistic constraints such as station' s capacity, construction costs and maximum mileage etc are considered. According to characteristic of the model, a two-stage heuristic algorithm, which gives specific solving process and analyzes its computational complexity, is proposed to obtain the model' s non-inferior solutions. Finally, a numerical example is taken to calculate its best scheme and analyze influence of parameters' sensitivity on them, which shows model and its algorithm' correctness and effectiveness.Key woorrddss：urban traffic; parking site layout; parking plan; two-stage heuristic algorithm由于城市居民出行在时间和空间上不均衡，每条线路配备不同数量车辆，当日常运营开始或结束时，因首末站自身没有足够多的泊位数，大部分公交车均需往返于首末站和站场之间.针对不同线路的首末站在时间和空间上的停车需求不平衡性，考虑土地利用性质的影响，若公交站场的建设规模及布局缺乏科学规划，必然出现部分站场的泊位数不足或资源浪费、往返空驶里程较多等现象[1,2].因此，如何合理布设公交站场的规模与数量，显得尤为重要.公交站场选址布局优化问题（Bus Parking Site Layout Optimization Problem，BPSLOP）主要解决两个问题：①站场选址和规模；②线路车辆停放.BPSLOP与一般选址问题类似[3]，可借鉴其研究思路和方法.目前，BPSLOP的研究文献较少，多数侧重于定性分析[4,5]，较少涉及定量研究.在定量研究方面，前者一般利用重力模型进行站场选址[6]，或根据客流决定[7]；后者是一个运输优化问题，邹成伟研究了一类公交站场优化选址模型，并利用单纯形法进行求解[8]；宋世辉提出了一类多目标公交站场设施布置优化模型[9].此外，部分学者利用DEA/AHP多角度评价公交站场的优劣[10].由上可知，现有研究均将公交站场选址和线路车辆停放调度分开来研究，无法进行整个公交系统的全局最优资源配置.针对现有研究的不足之处，本文研究一类BPSLOP，考虑车场能力、建设成本和最大里程等现实因素，以极小化所有公交车的行驶里程为目标，建立一种公交站场选址和线路车辆停放调度的集成模型，并设计求解该问题的两阶段启发式算法.最后，结合某城市的实际案例，计算最佳的公交站场选址，将所有车辆从各站场运输至相应停车场，并分析参数灵敏性对其布局的影响程度，检验本研究的有效性.2.1 假设(1)根据客流时空分布预测，确定所有线路在不同首末站的未来配车数. (2)不允许线路车辆在晚上停放于各首末站. (3)根据交通部门规划，已知建设公交站场的总投入资金，以及每个候选点的基本情况.2.2 符号变量总共有S个首末站，每个首末站∀s∈S经营Rs条线路，每条线路∀j∈Rs配备的车辆数为nj.总共有M个候选站场，若将某个候选站场∀i∈M选为站场，考虑它的建设费用ci、每个泊位的土地经济费用pi元和停车能力约束li.首末站∀s∈S和候选站场∀i∈M之间距离为ds,i，它们之间最大里程记为L .C为政府投资建设站场的总费用.2.3 决策变量xi表示某个候选站场∀i∈M是否被选为站场. yi表示站场∀i∈M的停车位数量. zi,j表示每条线路∀j∈Rs在站场∀i∈M的车辆数.2.4 目标函数2.5约束条件在上述模型中，式(1)是问题的目标函数，表示各线路的所有车辆从首末站返回站场的总行驶里程最小.式(2)–式(6)是约束条件，其中：式(2)表示至少建设一个场站；式(3)确保站场的车辆数小于一定值；式(4)表示附近站场必须满足某线路的停车需求；式(5)确保不同线路的首末站和站场之间距离小于一定距离；式(6)表示站场的建设费用小于某值.根据问题特征，该问题的求解关键可分为两步：首先，从一系列候选站场中筛选最佳站场，并确定其泊位数；其次，将各线路的所有车辆合理安排至相应站场.在第一阶段，遵循式（2）和式（5），将所有首末站划分为一系列片区，由式（6）确定候选站场的数量范围，从一系列候选地中，采用深度优先搜索算法，遍历并寻找每个片区的所有可行站场选址方案，基于式（3）的贪婪规则，确定它们的泊位数.在第二阶段，该问题抽象为运输问题，利用表上作业法，满足式（4），对每一个候选站场选址方案，将所有车辆从各首末站运输至相应站场，确定它们之间的数量. 综上所述，求解该问题的两阶段启发式算法流程如下：步骤1初始化.读取首末站和候选站点的基本数据，设置参数L、C .步骤2根据参数L，基于聚类算法将所有首末站划分为N个片区S=S1⋃S2⋃...⋃SN.步骤3采用深度优先搜索算法，逐步遍历所有片区的可能候选站场方案.令k =1.步骤4计算第k个片区的所有首末站Sk的停车需求，根据约束式（3）、式（5）和式（6），筛选一系列候选站场步骤4.1根据式（5），查找第i个片区范围内的所有候选站场集合M'k⊆M .步骤4.2若满足和，计算步骤5 k=k+1，若k≤N ,转步骤4；否则转步骤6.步骤6将所有片区首末站Sk的停车需求，以及候选站场Mk''的泊位数，视为一个运输问题，利用表上作业法求解当前问题的目标函数f .步骤7 若f≤f*，f*=f .步骤8若没有遍历整个解空间，转步骤3；否则，算法终止，输出最优解.由上可知，算法主要包括聚类、深度优先搜索，以及候选站场确定及其运输作业求解三个部分，其算法复杂性为，由于M'k的数量较少，所以算法接近多项式算法. 某城市共有16个首末站和14个候选站场，其拓扑结构如图1所示，根据停车需求时空分布不均衡性，拟从中确定最佳站场位置及其规模，并计算各首末站至站场的停车数.首末站和候选站场的基本信息如表1和表2所示，其它参数为L =2.5 km、C =700 000元.利用Matlab编写求解BPSLOP的程序，所有首末站的聚类如图2所示，总共划分为3个片区，筛选出5个站场10、1、11、12、4，它们的建设费用为679500元，停车位数量为25、60、40、33和34才满足其停车需求，线路停车调度方案如表3所示，所有车辆的总行驶里程为320.7 km.此外，分析参数L、C对BPSLOP的影响，如图3和图4所示，从中可知：（1）当L =1.5 km、2 km和2.5 km时，随着L逐渐减少，首末站划分的片区数增加，这引起需要更多的停车场，虽然停车场建设费用变得更高，但是总的行驶里程渐渐减少.（2）当C =600千元、650千元、700千元时，随着C逐渐减少，由于首末站划分的片区数没有增加，它们的站场选址相对容易受限其建设费用，因而偏好建设费用少而距离远的站场，从而总的行驶里程可能渐渐变大.为了揭示公交站场选址和线路车辆停放调度之间最佳耦合关系，本文构建了一类混合数学规划的集成模型和算法，根据停车需求时空分布不平衡性，确定站场选址优化方案，以及车辆停放方案，并分析参数L、C对优化结果的影响.研究表明：随着L逐渐减少，这引起需要更多的停车场，但是总的行驶里程渐渐减少；随着C逐渐减少，偏好建设费用少而距离远的站场，从而总的行驶里程可能渐渐变大.本文的研究结论对公交站场的建设规模及布局具有一定指导意义.但是本文假设所有线路在不同首末站的未来配车数是固定值，其根据客流时空分布预测获得，由于客流波动的随机性，弹性停车需求情形下的BPSLOP更符合实际，这类BPSLOP将是今后进一步研究的方向.【相关文献】[1] Ceder A. Public transit planning and operation theory, modeling and practicce[M]. Elsevier Ptc Ltd,2007.[2]王超,徐猛.考虑道路交通拥堵的公交发车间隔优化模型[J].交通运输系统工程与信息, 2011,11(4)：166-172. [WANG C, XU M. An optimal bus headway model considering trafficcongestion[J]. Journal of Transportion Systems Engineering and Information Technology, 2011, 11(4)：166-172.][3] Wang F, Xu Y. A review of the discrete facility location problem[J]. International Journal of Plant Engineering and Management,2006,1,40-50.[4]孙俊.大型公交站场布局规划[J].城市公共交通,2004, 3：14-16. [SUN J. Distribution planningof large-scale transit depots[J]. City Public Traffic, 2004,3:14-16.][5]翁勇.基于用地分析的公交站场布局规划研究[J].公路运输, 2008,1:90-93. [WENG Y. Study on layout planning of bus station based on analysis of land use [J]. Highway Transportation, 2008,1:90-93. ][6] Leonnie N, Attahiru S, Afifi H. The reliability of using the gravity model for forecasting trip distribution[J]. Transportation,1987,14(3):175-193.[7] Lee K, Roh M, Jeong H. An improved genetic algorithm for multi- floor facility layout problems having inner structure walls and passages[J]. Computers and Engineering, 2005,32(4):22-30.[8]邹成伟,黄国贤.公交站场优化选址研究[C].海峡两岸智慧型运输系统学术研讨会,2006,171-176. [ZOU C W,HUANG H X. Research on location optimization for transit depots[C]. Cross Strait Symposium on Intelligent Transportation System,2006,171-176.][9]宋世辉.公交站场布局规划研究[D].重庆交通大学, 2009. [SONG S H. Study on the layout planning of transit station field[D]. Chongqing Traffic University, 2009.][10]宋世辉.基于DEA/AHP模型的公共交通系统评价[J].中国科学论坛,2008,6: 96-98. [SONG S H. The public traffic system evaluation based on DEA/AHP model[J]. China Science Forum, 2008,6: 96-98.]。
