公交线路选择优化模型
李昆程鹏曹梦涛
摘要本题是一个公交线路查询的优化问题。根据查询者对换乘次数少、出行时间短以及出行费用低的不同需求，找出适合查询者的最优公交出行线路。
首先，本文提出了单次出行最大换乘次数为2的模型假设，并分析了Dijkstra算法在公交路径查询中的不适用性，试图提出有效的查询算法。
在问题一中，本文从公交系统线路图出发，在模型一中提出了基于“点”单源广度优先搜索模型。为了克服这种单向搜索效率低下的缺点，在模型二中，我们建立了基于“线”的双向广度优先搜索模型，极大的提高了搜索效率，分别得到了题目中六对起讫站点之间直达、一次换乘和二次换乘的所有可行线路。为了找到符合需求的最优线路，我们抓住换乘次数、出行时间和出行费用这三个影响线路选择的主要因素，针对三个影响因素重要程度相差较大的情况，建立了基于影响因素优先级的线路选择模型，即模型三。相反地，针对三个影响因素的重要程度相差不大的情况，我们在模型四中制定了因
W
素的重要性尺度和综合评价指标，通过量化的方法建立了基于综合评价的线路选择模
i
型。通过C++程序求解，分别得到了模型三与模型四的最优线路。
问题二仅仅在问题一的基础上加入了针对地铁的考虑。因此，两个问题在模型和算法上具有很大的相似性。我们首先找出了地铁线与公汽线之间的站点联系，针对搜索效率极高的模型二进行相应的改进，找到了换乘次数不超过两次的所有可行线路。和处理问题一中最优线路的确定方法类似，依据模型三和模型四，分别找出了基于优先级的最优线路和基于综合评价的最优线路。
针对问题三，本文定义了乘客的“步行容忍时间”，从而确定了某站点的“步行邻点集”。在“步行容忍时间”的约束下，试图找出换乘次数更少，出行时间更短、出行费用更低的出行方案。
在论文的最后，我们首先对“最大换乘次数为两次”的模型假设进行讨论，通过分析肯定了假设的合理性。其次，通过对模型三与模型四这两种最优线路选择方案进行比较，分析了各自的优劣。最后，我们通过查找文献，并联系客观实际，提出了“换乘次数是乘客的主要考虑因素”，并在此基础上结合模型三与模型四的优点，进一步提出了基于换乘次数最少的综合评价模型。
关键词公交线路选择单源广度优先搜索双向广度优先搜索需求优先级综合评价
1问题重述
我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485
(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S3676
2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
【附录1】基本参数设定
相邻公汽站平均行驶时间（包括停站时间）：3分钟
相邻地铁站平均行驶时间（包括停站时间）：2.5分钟
公汽换乘公汽平均耗时：5分钟（其中步行时间2分钟）
地铁换乘地铁平均耗时：4分钟（其中步行时间2分钟）
地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）
公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元
地铁票价：3元（无论地铁线路间是否换乘）
注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。
【附录2】公交线路及相关信息（见数据文件B2007data.rar）
2问题分析
近几年来，城市的公交系统有了很大的发展。公交运输的覆盖面越来越广，公交线路也日益增多，公共交通逐渐成为绝大多数出行者的首选方式。发达的城市公交系统使得公众的出行更加通畅、便利，同时也给人们出行乘车线路的选择带来了一定的困扰。方便、快捷、经济的公交出行线路方案，不仅可以方便公众的出行，同时也为城市交通减少了不必要的交通流量，有利于提高城市交通的运行效率，展现城市的现代化风貌。
2.1影响公交出行线路选择的因素
在研究公交最优路线选择的算法时，应该从实际情况出发考虑。因此，我们有必要先了解乘客出行时所考虑的因素，通过对乘客出行心理、行为的研究来确定模型的优化目标和约束条件。
按照传统的想法，乘客总是选择从起始点到终讫点的最短路径。研究表明[1]，最短路径并不是决定公交线路选择的主要因素。其它因素却是十分重要的影响因素。通常受到以下几个因素的作用。
（1）换乘次数：指乘客在完成一次出行过程中所换公交车的次数。
（2）出行距离：包括车上距离和车外距离。车上距离指乘客完成一次出行的过程中，乘坐的所有公交车辆（包括地铁）行驶的总距离（在问题一与问题二的模型中进行讨论）；车外距离指乘客为了乘车而步行的距离（在问题三的模型中进行讨论）。在本模型中，由于相邻车站的平均行驶时间已知，因此车上距离体现在车上耗时上。
（3）出行耗时：指乘客在一次出行过程中所需的时间，它也包括车上和车外部分。车上耗时即指乘客在公交车辆（包括地铁）上花费的总时间。车外耗时除了在车外距离部分所耗的时间外，还包括在车站等车的时间。
（4）出行费用，指的是乘客在完成一次出行过程中所花的车费。
针对如此多的因素，有时很难做出有关出行方案的准确判断。因此，我们根据人们出行的实际需要，分别针对出行方便（换乘次数最少）、快捷（出行耗时最少）、经济（出行成本最低）提出两站之间多种的乘车方案，以便乘客根据自己的不同需要进行选择选择。
2.2公交线路的形式
公交线路的形式是公交线路信息组织与处理的关键。针对本题而言，北京市公交线路的形式主要有三种，如图2.2—1所示：
I II III
2.2—1
（1）往返一致型：下行时车辆严格依照上行线路往返；
（2）圆环型：线路的起点和终点相接，运行路径为圆环；
（3）往返不一致型：车辆上下行线路基本一致，但是局部站点不同。
2.3Dijkstra算法不适合公交最优路径查询[2]
公交路径查询要求的是从起点到终点的最优路径，而Dijkstra算法求出的是从某点到其余各点的最短路径。在一个类似北京这样的大型城市里，站点少则几百，多则上千，这无疑会增加运算时间和程序的复杂度。在大量数据的情况下，计算速度会慢的让人难以忍受。其次，用Dijkstra算法求出的最短路径在多数情况下不适合公交线路，因为Dijkstra算法求出的结果可能是：从A站到B站需要转几次甚至十几次车，此结果只对私车出行有益，对公交线路没有意义。
3模型假设
?相邻公汽站平均行驶时间(包括停站时间)：3分钟。
?相邻地铁站平均行驶时间(包括停站时间)：2.5分钟。
?公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟，候车时间3分钟)。?地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟，候车时间2分钟)。?地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟，候车时间3分钟)。?公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟，候车时间2分钟)。
?公汽票价分为单一票价与分段计价两种。其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元。
?无论地铁线路间是否换乘，地铁票价均为3元。
?同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。?假设乘客每次出行公汽与公汽的换乘次数不超过两次。?出行耗时从起始站点的上车时刻算起，不考虑有关起始站点的步行时间和候车时间。
4符号说明
——经过站点的所有公交线路的集合
i S i ——第条出行线路公汽换乘公汽的次数（不通过地铁站）1i N i ——第条出行线路的地铁换乘地铁的次数2i N i ——第条出行线路的地铁换乘公汽的次数3i N i ——第条出行线路的公汽换乘地铁的次数
4i N i ——第条出行线路的公汽通过地铁站换乘公汽的次数5i N i ——第条出行线路乘坐公汽的总站数1i n i ——第条出行线路乘坐地铁的总站数2i n i ——第条出行线路的出行耗时
i T i ——第条出行线路在公交车辆上（包括地铁）消耗时间的总和1i t i ——第条出行线路换乘消耗时间的总和2i t i ——第条出行线路出行费用的总和
i C i ——某条出行线路中两相邻站点（指起点、终点或换乘站点）之间的行车区段
l ——第条出行线路上第区段的票价函数。
(,,)ticket l A B i l ——第个影响因素的权系数(1,2,3)k w k =k ——第个影响因素的量化指标
(1,2,3)k num k =k
——第条出行线路上所选择出行方案的综合评价指标
i W i 5模型的建立与求解
根据2.1所述，在本模型中，由于相邻车站的平均行驶时间已知，因此车上距离在车上耗时中体现出来。在充分考虑影响公交出行线路选择的各个因素的前提下，我们本着出行方便、快捷、经济的原则，分别选取换乘次数、出行耗时和出行费用最小为目标建立优化模型。
5.1仅考虑公汽线路时，任意两个公汽站点之间的可行线路统计
为了找到任意两个公汽站点之间的最优线路，首先我们需要确定任意两个公汽站点之间的可行线路。这里的可行线路是指通过不大于两次的换乘能够连通指定两公汽站点的线路。
考虑到两个站点之间可能出现没有直达车而出现换乘的情况，因此，在上文假设中换乘次数不超过两次的前提下，我们试图通过设计一定的算法，分别求出任意两公交站点之间不需换乘的线路、需要换乘一次的线路以及需要换乘两次的线路，以及相应的时间消耗、费用等参数。
我们将公交站点抽象成公交系统交通图中的“点”，将公交线路抽象成公交系统交通图中的“线”，“点”与“线”相互联系，共同构成了复杂的公共交通系统。5.1.1模型一：基于“点”的单源广度优先搜索模型
引用文献[3]中提出了一种“两点乘车算法”，其核心思想是以起点为“根”，通过公交线路间的可换乘表（Route-Route ）长“枝”，通过公交线路的长枝表（Route-Con ）确定下一层“枝”生长的“节点”，最终长成以出行起点为顶的有向树。本模型在其算法思想基础上进行拓展，提出以“点”为中心，基于“点”的单源广度优先搜索模型，找出两确定站点之间换乘次数不大于两次的公交出行线路。
算法步骤如下：
Step 1：以起点临近站点为“根”，令其为；把的下游相邻站点作为第一层“枝”S S 的节点，设其为，，……,如图5.1.1—1所示：（图中只列出了第一层和第二1,1S 1,2S 1,3S 层）
Step 2：长“枝”时，记录换车次数。当换车次数时终止长“枝”。
num 2num >
Step 3：根据实际生成的“长枝表”，找出首次出现终点的“枝”的节点，经由D 各层“枝”连接与的连线，就是一条符合要求的公交线路。再根据记录其换乘次数S D 的变量即可完整的确定该条公交线路的方案。
num 该模型紧紧围绕公交系统网络图中“点”这一中心，通过节点树确定出可行的公交线路方案，思想简明易懂。但是，这种算法“单源”的特性决定了其搜索效率的低下。附件所给数据中包含了3957个公汽站点，数据量庞大，通过多层生“枝”，搜索速度慢，效率低。若运用于公交查询系统，很难在较短的时间内查询出可行的公交线路。因此，我们并没用使用该模型进行求解。
为了克服模型一搜索效率地下的缺点，在下文中，我们对模型一进行改进，提出了基于“线”的的双向广度优先搜索模型。
5.1.2模型二：基于“线”的双向广度优先搜索模型
“线”是“点”的组织形式，能够有效体现“点”的关联性。因此，为了弥补基于“点”的单源广度优先搜索模型效率低下的不足，本模型提出了基于“线”的双向广度优先搜索算法，从“线”的两端入手，以彼此为目标同步进行广度优先搜索，提高了搜索效率，减少了搜索时间。
本模型中线路的选取从起点和终点同步开始，运用集合的思想，找出起点与终点、起点与某换乘站点、终点与某换乘站点、两换乘站点之间所在线路的交集。若交集非空，则两条线路是可换乘的。
定义：上游——对于同一线路上的A、B两站点，若公交车辆沿此线路经由A站点开往B站点，则A站点在B站点的上游。
以下讨论中，均假设A站点在B站点的上游。对于B站点在A站点上游的情况，讨论类似，这里不再给出。
算法思想如下：
Step 1[图5.1.2—1(a)]：假设乘客从A站点去往B站点。若经过A站点的所有线路的集合为，经过B站点的所有线路的集合为。若，则为A站点A S B S 11A B S S S S ∩=≠Φ且1S 去往B站点的直达线路的集合。即A站点去往B站点能够直达的必要条件为：
A B S S ∩≠Φ
Step 2[图5.1.2—1(b)]：依然从“线”考虑，如果经过A站点的某线路上存在一点C，且C存在于经过B站点的某条线路上,则A站点经过C站点一次换乘可到达B站点。即一次换乘的必要条件为：
,..A C B C S S C s t S S ∩≠Φ
???
∩≠Φ
?站点 Step 3[图5.1.2—1(c)]：按照上述“线”的思想，若经过A站点的某线路上存在一点C，经过B站点的某线路上存在一点D，且，则A站点依次经过C、D两站点C D S S ∩≠Φ二次换乘，可到达B站点。即二次换乘的必要条件为：
,..A C C D D B
S S C D s t S S S S ∩≠Φ??
?∩≠Φ
??∩≠Φ?站点、
A B
S A S B
S 1S A
S B
S C S A S C S D S B
(a (b )
(c )
图5.1.2—1线路换乘示意图
5.2仅考虑公汽线路时，任意两个公汽站点之间的最优线路5.2.1相关参数的计算
（1）出行耗时——车上耗时与换乘耗时之和，即：
i T 1i t 2i t ……(式5.2.1—1)
12i i i T t t =+相邻公汽站平均行驶时间（包括停站时间）为3分钟，则有；公汽换乘耗时513i i t n =分钟，则有,那么
215i i t N =……(式5.2.1—2)
1135i i i T n N =+（2）出行费用——第条出行线路上乘坐公汽从A站点去往B站点的出行总费用
(,)i C A B i 定义：——第条出行线路上乘坐公汽从A站点去往B站点的过程中，(,,)i ticket l A B i 第区段的票价函数。
l ……(式5.2.1—3)
1(,,)23i ticket l A B ??
=???元 （单一票制，分段计价0～20站）元 （分段计价21～40站）元 （分段计价40站以上）定义：条件——处于第条出行线路上。
()case i i 第条出行线路上乘坐公汽从A站点去往B站点的出行总费用可表示为：
i i C ……(式5.2.1—4)
()
(,)(,,)i i
case i C A B ticket l A B =
∑
通过C++程序，使用模型二中基于“线”的双向广度优先搜索算法寻找可行线路，按照换乘次数分类，其统计结果如下：
起点终点直达换乘一次换乘二次
S3359S182801110185
S1557S04810022
S0971S04850123136
S0008S0073010115628
S0148S04850034
S0087S367602840
表5.2.1—1可行线路统计
从统计结果中我们看出：六对起讫站点之间没有直达线路。这时因为我们没有考虑地铁线路，而地铁站是许多公汽站点的连接点。因此，公汽线路的连通性（即两条公汽线路间的可换乘性）大大降低。
5.2.2模型三：基于需求优先级的公交线路选择模型
不同的查询者对换乘次数、出行耗时以及乘车费用往往具有不同的需求。有的人认为乘车方便是第一位的，那么他会优先选择换乘次数最少的路线；有的人需要赶时间，那么他就会优先选择出行耗时最少的线路；有的人认为经济实惠最重要，那么他就会优先选择乘车费用最低的线路。
这里，我们根据公交线路查询者对换乘次数少、出行耗时短以及乘车费用低的需求程度定义优先级，建立基于需求优先级的公交线路选择模型。例如：某查询者认为优先级“换乘次数>出行耗时>出行费用”，那么他就会首先按照换乘次数最短的方案出行；如果此时换乘次数最短的路线有多条，查询者继续考虑这些可行路径中出行耗时最短的路径；倘若所有可行路线的耗时均相同，那么查询者将优先采用费用最低的线路出行。
根据模型二的求解结果，在Excel中我们将可行线路分别按照换乘次数、出行耗时和出行费用进行升序排序。由于线路众多，排序表仅在附件中以Excel表格的形式列出。这里，我们仅列出符合条件的最优线路。
（1）S3359—S1828
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”和“换乘次数>出行耗时>出行费用”三种不同的优先级分别查询可行线路，我们发现这三种优先级对应的所有最优线路完全一致。最优线路共有两条，如表5.2.2—1所示：(表中不同最优线路的排序不分先后，下文相同，不再一一赘述)
最优线路起点公汽线1换乘站公汽线2终点
1S3359L436S1784L167S1828
2S3359L436S1784L217S1828
表5.2.2—1
线路一由站点S3359经由线路L436，在站点S1784换乘，经由线路L167,到达站点S1828。
线路二由站点S3359经由线路L436，在站点S1784换乘，经由线路L217,到达站点S1828。（后文中对最优线路表的理解方式相同，不再一一赘述）
这两种公交线路均需换乘1次，出行耗时101分钟，乘车费用3元。
按照“出行费用>出行耗时>换乘次数”、“出行耗时>换乘次数>出行费用”和“出行耗时>出行费用>换乘次数”三种不同的优先级分别查询可行线路，我们发现这三种优先级对应的所有最优线路完全一致，共有78条线路。由于线路众多，在表5.2.2—2中我们只列出其中五条最优线路。
最优路线起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S3359L015S2903L027S1784L167S1828
2S3359L123S2903L027S1784L167S1828
3S3359L132S2903L027S1784L167S1828
4S3359L436S2903L201S0458L041S1828
5S3359L474S2903L201S1790L041S1828
表5.2.2—2
这78种公交线路均需换乘2次，出行耗时73分钟，乘车费用3元。
（2）S1157—S0481
按照“换乘次数>出行耗时>出行费用”、“出行耗时>换乘次数>出行费用”和“出行耗时>出行费用>换乘次数”三种不同的优先级分别查询可行线路，我们发现这三种优先级对应的所有最优线路完全一致。最优线路共有4条，如表5.2.2—3所示：最优线路起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S1557L084S1919l417S3919L072S0481
2S1557L084S1919l417S3919L166S0481
3S1557L363S1919l417S3919L072S0481
4S1557L363S1919l417S3919L166S0481
表5.2.2—3
这4种最优公交线路均需换乘2次，出行耗时127分钟，乘车费用4元。
按照“换乘次数>出行耗时>出行费用”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”三种不同的优先级分别查询可行线路，我们发现这三种优先级对应的所有最优线路完全一致。最优线路共有2条，如表5.2.2—4所示：最优线路起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S1557L084S3389L080S1327L072S0481
2S1557L084S3389L279S1327L072S0481
表5.2.2—4
这两种最优公交线路均需换乘2次，出行耗时145分钟，乘车费用3元。
（3）S0971—S0485
按照“换乘次数>出行耗时>出行费用”的优先级查询可行线路，找到一条最优线路。如表5.2.2—5所示：
最优线路起点公汽线1换乘站公汽线2终点
1S0971L013S2184L417S0485
表5.2.2—5
这种最优公交线路均需换乘1次，出行耗时128分钟，乘车费用4元。
按照“换乘次数>出行费用>出行耗时”和“出行费用>换乘次数>出行耗时”这两种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有4条，如表5.2.2—6所示：
最优线路起点公汽线1换乘站公汽线2终点
1S0971L013S2322L417S0485
2S0971L013S1770L417S0485
3S0971L013S1789L417S0485
4S0971L013S2119L417S0485
表5.2.2—6
这4种最优公交线路均需换乘2次，出行耗时134分钟，乘车费用3元。
按照“出行耗时>出行费用>换乘次数”、“出行耗时>换乘次数>出行费用”和“出行费用>出行耗时>换乘次数”这三种不同的优先级分别查询可行线路，我们发现这三种优先级对应的所有最优线路完全一致。最优线路共有12种。由于线路众多，在表5.2.2—7中我们只列出其中五条最优线路。
最优线路起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S0971L119S2992L027S0516L104S0485
2S0971L013S1609L140S3037L104S0485
3S0971L013S1609L140S2654L104S0485
4S0971L024S1609L140S3037L104S0485
5S0971L024S1609L140S2654L104S0485
表5.2.2—7
这12种最优公交线路均需换乘2次，出行耗时115分钟，乘车费用3元。
（4）S0008—S0073
按照“出行耗时>出行费用>换乘次数”和“出行耗时>换乘次数>出行费用”这两种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有14条。由于线路众多，在表5.2.2—8中我们只列出其中五条最优线路。
最优线路起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S0008L355S2755L017S0604L057S0073
2S0008L355S2755L017S2650L057S0073
3S0008L159S0630L231S0609L057S0073
4S0008L198S1691L476S2083L057S0073
5S0008L198S3766L476S2083L057S0073
表5.2.2—8
这14种最优公交线路均需换乘2次，出行耗时70分钟，乘车费用3元。
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”这四种不同的优先级分别查询可行线路，我们发现这四种优先级对应的所有最优线路完全一致。最优线路共有10条。由于线路众多，在表5.2.2—9中我们只列出其中五条最优线路。
最优线路起点公汽线1换乘站公汽线2终点
1S0008L159S0291L058S0073
2S0008L159S3614L058S0073
3S0008L355S2263L345S0073
4S0008L355S3917L345S0073
5S0008L463S2083L057S0073
表5.2.2—9
这10种最优公交线路均需换乘1次，出行耗时83分钟，乘车费用2元。
（5）S0148—S0485
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”、“出行耗时>出行费用>换乘次数”、“出行耗时>换乘次数>出行费用”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”这六种不同的优先级分别查询可行线路，我们发现这六种优先级对应的所有最优线路完全一致。最优线路共有2条，如表5.2.2—10所示：
最优线路起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S0148L308S0036L156S2082L045S0485
2S0148L308S0036L157S1406L045S0485
表5.2.2—10
这10种最优公交线路均需换乘2次，出行耗时121分钟，乘车费用3元。
（6）S0087—S3676
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”的优先级查询可行线路，我们发现这四种优先级对应的所有最优线路完全一致。最优线路只有1条。如表5.2.2—11所示：
最优线路起点公汽线1换乘站公汽线2终点
1S0087L454S3496L209S3676
表5.2.2—11
这条最优公交线路只需换乘1次，出行耗时65分钟，乘车费用2元。
按照“出行耗时>换乘次数>出行费用”和“出行耗时>出行费用>换乘次数”这两种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有6条。如表5.2.2—12所示：
最优路线起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S0087L021S0088L231S0427L097S3676
2S0087L021S0088L231S0427L462S3676
3S0087L206S0088L231S0427L097S3676
4S0087L206S0088L231S0427L462S3676
5S0087L454S0088L231S0427L097S3676
6S0087L454S0088L231S0427L462S3676
表5.2.2—12
这6条最优公交线路均需换乘2次，出行耗时46分钟，乘车费用3元。
5.2.3模型四：基于综合评价的公交线路选择模型
现实生活中，影响查询者选择出行线路的因素往往有多种，但是某几种影响因素的重要程度可能会十分接近。例如，对于某查询者而言，由于实际情况所需，换乘次数和乘车耗时同等的重要，他必须同时优先考虑。这时，5.2.2中基于需求优先级的线路选择模型就很难帮助查询者做出决策。因此，我们需要建立一种同时考虑多种因素的综合评价模型。
根据实际情况，我们对影响选择出行线路的三个因子——换乘次数、乘车耗时和乘车费用分别赋予不同的权重，则第条出行线路的综合评价指标可定义1,2,3)k w k =(i i W 为：
……（式5.2.3—1）123i W w w w =?×?×?×换乘次数乘车耗时乘车费用关于上式的几点说明：
（1）定义式中，有关负号“－”的说明
i W 越大，表明第个因子对出行线路的选择越为重要。同样的，越大，1,2,3)k w k =(k i W 表明第条出行线路越要优先考虑。对于换乘次数、乘车耗时、乘车费用单一因素而言，i 其绝对值越小，表明此出行线路在其对应影响因素方便的表现越优秀。相反，这三个影响因素的绝对值越大，其对应线路的评价指标越低下。为了保证三个影响因素与、
i W i W 的“同向性”，我们在评价指标的定义式中，三个影响因素之前均加了负1,2,3)k w k =(i W 号“－”。
（2）归一化处理
从可行线路的统计表中我们看到，换乘次数、乘车耗时和乘车费用三个影响因子之间在数值上可能相差很大。在某条线路的综合评价指标的确定时，为了防止三个不同i W 影响因素之间出现“大数吃掉小数”的现象，我们需要对其按照下式进行规一化处理。因为我们的目的是换乘次数少、乘车耗时短、乘车费用低，类似于要求成本最低。因此，我们使用“成本型”归一化公式进行处理：
……（式5.2.3—2）
min
max min
'X X X X X ?=
?对于某两站点之间，出现了所有可行线路的换乘次数相等的情况。这时按照上述归一化公式进行归一化处理时，会出现分母为零的情况。这种情况下，查询者选择何种线路，换乘次数始终固定不变，也就是说换乘次数已经不是查询者需要考虑的影响因素了。这时，我们令，则第条出行线路的综合评价指标的定义式可简化为：
10w =i i W ……（式5.2.3—3）
23i W w w =?×?×乘车耗时乘车费用（3）量化指标的确定
(1,2,3)k w k =
不同的查询者对三个影响因素的需求是不同的，在制作公交线路查询系统时，如果将设置为定值，则查询出的线路不一定是最适合查询者出行的公交线路。(1,2,3)k w k =因此，我们在设计公交线路的查询系统时，应从查询者的实际需求出发，对查询者针对三个影响因素的需求程度进行询问并记录，找出适合该查询者的最优线路，充分体现查询系统的“查询自主性”。
因此，查询系统在确定公交线路之前，首先需要对查询者对换乘次数、乘车耗时以及乘车费用这三个影响因素的需求程度进行了解。我们参考Saaty等人提出的1—9比较尺度的思想[4]，制定出了针对公交线路选择的三个影响因素的影响尺度。
将三个影响因素的影响尺度分为不重要、一般、重要、比较重要、非常重要五个等级，分别对应量化指标1、2、3、5、7、9。如表5.2.3—1所示：
设为第个影响因素的量化指标，则：
(1,2,3)k num k =k ……（式5.2.3—4）
3
1
k
k k
k num w num
==
∑有关不能使用归一化公式的处理方法，已在说明（2）中讨论。
为了体现在影响公交线路选择的各因素重要性相近的情况下本模型的优势，在充分联系实际的前提下，我们对三个影响因素设置相近而不相同的量化指标值进行求解。
假设某查询者使用查询系统时，认为换乘次数比较重要，乘车耗时重要，乘车费用重要性一般，其对应量化指标值依次为7，5，3。换乘次数、乘车耗时和乘车费用的权重系数依次为：。依据式5.2.3—4，我们求得三个影响因素的权重向量为：123,,w w w 123711
[][]
1535
w w w w == 利用式5.2.3—2进行归一化处理，分母为零的情况按照上文中的讨论令其权重系数为零。再根据式5.2.3—2和式5.2.3—3求得起讫两站点之间所有可行线路的综合评价指标，找出指定的起讫两站点之间可行线路中最大的线路，即为本模型所求的最优i W i W 线路。在Excel中通过公式编辑直接对题目中的六对起讫站点求解结果如下：（1）S3359—S1828
最大综合评价指标，对应的最优线路有两条，如表5.2.3—2所示：（表10.02935W =?中最优线路顺序不分先后，下文相同，不再赘述）
等级不重要一般重要比较重要非常重要
量化指标
1
3
5
7
9
表5.2.3—1五种影响等级的量化值
两条最优线路换乘次数都为1次，出行耗时都为101分钟，乘车费用都为3元（2）S1557—S0481
最大综合评价指标，对应的最优线路有两条，如表5.2.3—3所示：20.18750W =?（3）S0971—S0485
最大综合评价指标，对应的最优线路有4条，如表5.2.3—2所示：
30.02050W =?（4）S0008—S0073
最大综合评价指标，对应的最优线路有10条，如表5.2.3—5所示：
40.01301W =?（5）S0148—S0485
最优线路
起点公汽线1换乘站1公汽线2终点
1S3559L436S1784L167S18282S3559L436S1784L217
S1828
表5.2.3—2
最优线路
起点公汽线1换乘站1公汽线2换乘站2公汽线3终点
1S1557L084S3389L080S1327L072S4812
S1557
L084S3389L279S1327L072
S481
表5.2.3—3
最优线路
起点公汽线1换乘站公汽线2终点1S0971L013S2322L417S04852S0971L013S1770L417S04853S0971L013S1789L417S04854
S0971
L013
S2119
L417
S0485
表5.2.3—4
最优线路
起点公汽线1换乘站公汽线2终点1S0008L159S0400L474S00732S0008L159S2633L474S00733S0008L159S3053L474S00734S0008L159S2683L058S00735S0008L159S0291L058S00736S0008L159S3614L058S00737S0008L355S2263L345S00738S0008L355S3917L345S00739S0008L355S2303L345S007310
S0008
L463
S2083
L057
S0073
表5.2.2—5
最大综合评价指标，对应的最优线路有两条，如表5.2.3—6所示：50W =（6）S0087—S3676
最大综合评价指标，对应的最优线路有两条，如表5.2.3—7所示：
60.03519W =?上述求解过程仅仅是本模型实际应用的一个特例，在此列出是为了体现在三个影响因素的重要性差别不大的情况下，本模型求解最适合查询者需求的公交线路这类问题具有一定的优势。在实际应用中，应根据查询者的具体需求确定三个影响因素的权重系数向量，进而求出出行线路综合评价指标最大的所有最优线路，满足查123[]w w w w = i W 询者的要求。
5.3同时考虑公汽和地铁线路时，任意两个站点之间的可行线路统计
本问题与5.1具有很大的相似性，因此我们可以通过类比的方法，对搜索速度较快的模型二进行修正，找到同时考虑公汽和地铁线路时任意两个站点之间的可行线路。
我们需要对模型二进行两方面的修正：
（1）增加了两条地铁线路，往返型线路T1和环线T2。题中线路T1的上行和下行站点设置完全对称。我们可以将线路T1和T2类比为新增加的两条公汽线路。
（2）根据假设，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘而无需支付地铁费。我们将同一地铁站对应的所有公汽站的站名都记为该地铁站的站名，这样，这些公汽站所对应的线路在该地铁站处就能够换乘了。例如：地铁站D01对应公汽车站S0567、S0042、S0025，将这三个公汽站更名为D1，则经过公汽车站S0567、S0042、S0025的线路在地铁站D1处可换乘。
（3）对于地铁可以直达的起讫站站点，我们不考虑地铁与公汽之间相互换乘的情况。究其原因，我们仍然从影响公交线路选择的三个因素进行考虑。
第一：换乘次数增加。因为在这种情况下，只要地铁与公汽之间换乘一次，那么换乘次数即增加1。
第二：出行耗时变长。公汽速度没有地铁快，无论是公汽换乘地铁，还是地铁换乘公汽，都没有地铁直达（或者两条地铁线之间转乘）的时间短。也就是说，地铁与公汽之间的换乘，增加了出行耗时。
第三，出行费用增加。地铁之间换乘无需购票，而地铁与公汽之间的换乘则需要再次购票，增加了出行费用。
第四，同一地铁站对应的任意两个公汽站之间通过地铁站换乘时，平均耗时为11分钟。其中公汽站步行至地铁站及反向步行过程均耗时4分钟，等候公汽耗时3分钟。
根据上述三点，我们对模型二进行改进，并对程序进行相应的修正，在换乘次数不
最优线路
起点公汽线1换乘站1公汽线2换乘站2公汽线3终点
1S0148L308S0036L156S2082L045S04852
S0148
L308S0036L157S1406L045
S0485
表5.2.3—6
最优线路
起点线路1换乘站线路2终点1
S0087
L454
S3496
L209
S3676
表5.2.3—7
多于两次的前提下，分直达、换乘次数为1、换乘次数为2三种情况分别找出了题目中六对起讫站点的可行出行线路。（由于数据量庞大，可行线路数据表在附件中以Excel文件的形式给出）
5.4同时考虑公汽和地铁线路时，任意两个公汽站点之间的最优线路5.4.1相关参数的计算
（1）出行耗时——车上耗时与换乘耗时之和，即：
i T 1i t 2i t 12i i i
T t t =+车上耗时包括公汽车上耗时与地铁车上耗时，即；换乘耗时包1i t 1123 2.5i i i t n n =+2i t 括公汽间互换耗时（不经过地铁站）、地铁间互换耗时、公汽与地铁间互换耗时和公汽间经过地铁站互换耗时，即,那么第条可行线路的出212345547611i i i i i i t N N N N N =++++i 行耗时为：
i T 1212123453 2.5547611i i i
i i i i i i i
T t t n n N N N N N =+=++++++（2）出行费用——第条出行线路上乘坐公交（包括公汽和地铁）从A站点去往(,)i C A B i B站点的出行费用总和。
根据5.2.1中的定义，有：
(,,)i ticket l A B 1(,,)23i ticket l A B ??
=???
元 （公汽：单一票制，分段计价0～20站）元 （公汽：分段计价21～40站）
元 （公汽：分段计价40站以上；地铁）第条出行线路上乘坐公汽从A站点去往B站点的出行总费用可表示为：
i i C ()
(,)(,,)
i i
case i C A B ticket l A B =
∑5.4.2可行线路的寻找
模型二中基于“线”的双向广度优先搜索算法具有极高的搜索效率。这里，我们针对模型二及其算法进行修正，在C++环境下通过程序找出题目中六对起讫站点间的可行线路。
依据换乘次数划分，可行线路数目统计如表5.4.2—1所示：
起点终点直达换乘一次换乘二次
S3359S182801110586
S1557S048100268
S0971S04850125462
S0008S0073011427943
S0148S048500258
S0087S367612840
表5.4.2—1可行线路统计
从表5.4.2—1中我们看到，题目中的线路（6）S0087—S3676具有直达的可行线路，而且S0087和S3676两站点均有地铁站对应。通过计算机模拟我们找出该线路的具体途径，发现该直达线路为地铁直达。根据5.3中的讨论，我们可以直接确定：在下文的两种最优线路选择模型中，该地铁直达线路均为最优线路。
5.4.3同时考虑公汽和地铁时，基于模型三中需求优先级的公交最优线路选择
（1）S3359—S1828
按照“换乘次数>出行耗时>出行费用”和“换乘次数>出行费用>出行耗时”的优先级查询可行线路，找到两条最优线路。如表5.4.3—1所示：
最优路线起点公汽线换乘站终点
1S3359L436S1784S1828
2S3359L436S1784S1828
表5.4.3—1
这种最优公交线路均需换乘1次，出行耗时101分钟，乘车费用3元。
按照“出行耗时>出行费用>换乘次数”、“出行耗时>换乘次数>出行费用”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”这4种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有78条，由于线路众多，在表5.4.3—2中我们只列出其中五条最优线路。
最优路线起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S3359L324S1746L027S1784L217S1828
2S3359L484S1746L027S1784L167S1828
3S3359L015S2903L027S1784L167S1828
4S3359L015D2903L027S1784L217S1828
5S3359L123S2903L027S1784L167S1828
表5.4.3—2
这78种最优公交线路均需换乘2次，出行耗时73分钟，乘车费用3元。
（2）S1557—S0481
按照六种优先级顺序得到的最优线路完全相同，最优线路共有10条。由于线路众多，在表5.4.3—3中我们只列出其中五条最优线路。
最优路线起点公汽线中转站公汽线中转站公汽线终点1S1557L084S1919L417S2424L254S0481
2S1557L084S1919L417S2424L312S0481
3S1557L084S1919L417S2424L447S0481
4S1557L084S1919L417S2424L460S0481
5S1557L084S1919L417S2424L516S0481
表5.4.3—3
这10种最优公交线路均需换乘2次，出行耗时112分钟，乘车费用3元。
（3）S0971—S0485
按照“换乘次数>出行耗时>出行费用”的优先级找到一条最优线路，如表5.4.3—4所示：
最优线路起点公汽线1换乘站公汽线2终点
1S0971L013S2184L417S0485
表5.4.3—4
这种公交线路需换乘1次，出行耗时128分钟，乘车费用4元。
按照“换乘次数>出行耗时>出行费用”的优先级找到四条最优线路，如表5.4.3—5所示：
最优路线起点公汽线换乘站公汽线终点
1S0971L013S2322L417S0485
2S0971L013S1770L417S0485
3S0971L013S1789L417S0485
4S0971L013S2119L417S0485
表5.4.3—5
这4种公交线路均需换乘2次，出行耗时均为134分钟，乘车费用均为3元。
按照“出行耗时>出行费用>换乘次数”和“出行耗时>换乘次数>出行费用”两种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有12条。由于线路众多，在表5.4.3—6中我们只列出其中五条最优线路。最优路线起点公汽线1换乘站1换乘站1地铁线换乘站2换乘站2公汽线2终点1S0971L094S0567D01T1D21S0466L051S0485 2S0971L094S0567D01T1D21S0464L104S0485 3S0971L094S0567D01T1D21S0466L051S0485 4S0971L094S0567D01T1D21S0464L104S0485 5S0971L094S0567D01T1D21S0466L051S0485
表5.4.3—6
这4种公交线路均需换乘2次，出行耗时均为96分钟，乘车费用均为5元。
按照“出行费用>换乘次数>出行耗时”的优先级找到4条最优线路，如表5.4.3—7所示：
最优路线起点公汽线1换乘站公汽线2终点
1S0971L013S2322L417S0485
2S0971L013S1770L417S0485
3S0971L013S1789L417S0485
4S0971L013S2119L417S0485
表 5.4.3—7
这4种公交线路均需换乘1次，出行耗时均为134分钟，乘车费用均为3元。
按照“出行费用>出行耗时>换乘次数”的优先级找到12条最优线路。由于线路众多，在表5.4.3—8中我们只列出其中五条最优线路。
最优路线起点公汽线1换乘站1公汽线2换乘站2公汽线3终点1S0971L119S1520L027S0516L104S0485
2S0971L119S2992L027S0516L104S0485
3S0971L119S1609L140S3037L104S0485
4S0971L119S1609L140S2654L104S0485
5S0971L119S1609L140S3037L104S0485
表5.4.3—8
这3条公交线路均需换乘2次，出行耗时均为115分钟，乘车费用均为3元。
（4）S0008—S0073
按照“出行耗时>出行费用>换乘次数”和“出行耗时>换乘次数>出行费用”这两种不同的优先级分别查询可行线路，我们发现这两种优先级对应的所有最优线路完全一致。最优线路共有5条。在表5.4.3—9中列出。
最优路线起点公汽线换乘站公汽线换乘站公汽线终点1S0008L200S2534L080S0608L057S0073
2S0008L200S2534L156S0608L057S0073
3S0008L200S2534L157S0608L057S0073
4S0008L200S2534L279S0608L057S0073
5S0008L200S2534L348S0608L057S0073
表5.4.3—9
这14种最优公交线路均需换乘2次，出行耗时64分钟，乘车费用3元。
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”这四种不同的优先级分别查询可行线路，我们发现这四种优先级对应的所有最优线路完全一致。最优线路共有10条。由于线路众多，在表5.4.3—10中我们只列出其中五条最优线路。
最优路线起点公汽线换乘站公汽线终点
1S0008L159S0400L474S0073
2S0008L159S2633L474S0073
3S0008L159S3053L474S0073
4S0008L159S2683L058S0073
5S0008L159S0291L058S0073
这10种最优公交线路均需换乘1次，出行耗时83分钟，乘车费用2元。
（5）S0148—S0485
按照“换乘次数>出行耗时>出行费用”、“换乘次数>出行费用>出行耗时”、“出行耗时>出行费用>换乘次数”、“出行耗时>换乘次数>出行费用”、“出行费用>换乘次数>出行耗时”和“出行费用>出行耗时>换乘次数”这六种不同的优先级分别查询可行线路，我们发现这六种优先级对应的所有最优线路完全一致。最优线路共有1条，如表5.4.3—11所示：这10种最优公交线路均需换乘2次，出行耗时103分钟，乘车费用3元。
（6）S0087—S3676
在5.4.2的最后，我们已经对该线路进行了相关讨论。无论是换乘次数最少优先，还是出行时间最短优先，乘坐地铁T2由D27到D36直达是符合实际需求的最优解。这种情况下出行耗时33分钟，出行费用3元。
但是从出行花费最低优先的角度出发，乘坐公交线路进行一次换乘费用最低。此时出行费用为2元，出行耗时60分钟。最优线路如表5.4.3—12所示：
5.4.4同时考虑公汽和地铁时，基于模型四中综合评价的公交最优线路选择
按照模型四的算法，对题目中六对起讫站点求解，结果如下：（1）S3359—S1828
最大综合评价指标，对应的最优线路有两条，如表5.4.4—1所示：10.02935W =?两条最优线路换乘次数都为1次，出行耗时都为101分钟，乘车费用都为3元（2）S1557—S0481
最大综合评价指标，对应的最优线路有10条，如表5.4.4—2所示：
20W =表5.4.3—10
最优路线起点公汽线换乘站公汽线换乘站公汽线终点
1S0148L308S3604L454S1919L417S0485
表5.4.3—11
最优路线起点公汽线换乘站公汽线终点
1S0087L454S3496L209S3676
表5.4.3—12
最优线路
起点公汽线1换乘站1公汽线2换乘站2公汽线3终点
1S3559L015S1903L207S1784L167S18282
S3559
L015S2903L207S1784L217
S1828
表5.4.4—1
1、公交线网优化 公交优先项目提出了成都市中心城区公交线网优化方案、骨干线网优化方案，同时对天府新区公交线网进行优化和规划。 成都市常规公交目前已初步形成“环形+放射状”的“快、干、支、微”四级线网体系。 城市公交骨架线路是在公交网络体系中起支架作用的线路，它衔接区域内公交客流需求较大的枢纽点，主要满足直达客流的需要，以实现乘客快速、便捷的转移。公交骨架线路效率的高低直接影响整个网络运行效率。 成都市公交线网概念骨架图 按照城市任何两个公交服务区之间均应提供快速公交服务的理念，构筑抽象的理想快线网络。通过网络拟合，筛选可行网络，考虑对策略发展区快线支持，补充得到近期快线实施网络。以实施网络为基础，对现有线网进行改造，得到近期快线方案，如下图。
成都市近期公交快线网络规划图 线网优化实例图 随着2014年四川天府新区正式成立，天府新区成都直管区与中心城区形成双核发展；成都市第十三次党代会报告提出：“推动天府新区产城融合，突出国际化服务和创新型引领，突出天府国际空港新城的国际门户功能和龙泉山现代化
产业基地的集聚优势，把天府新区打造成为新兴增长极核。”因此，将天府新区成都直管区与中心城区的快捷连通作为公交快线布设的重要因素，同时兼顾天府新区内部各核心组团（天府新城、成都科学城、南部特色优势产业功能区）的连通性，规划布局多条公交干线。 天府新区新增/调整快线布局
天府新区公交干线布局 2、交通集成模型数据库 交通模型数据库项目的开展形成了多个预测模型和各项交通指标数据库，使得成都在机动化快速发展中的交通模式向智慧出行、绿色出行和可持续发展方向转变。 数据库建设一览表
公交车排班模型中的线性规划求解问题 摘要 本文研究的是在满足各时段（早高峰、日间平峰、晚高峰，晚平峰四个时段）时间，公交车以一定间隔连续发车的条件下，排班的最优问题。根据各小题的约束条件，用运筹学中的线性规划知识建立模型，再利用Lingo求解,分别算出所需公交车总数以及单班车、双班车各需求量，制定排班的优化方案。 对于题目条件，我们有三个设想，其一，根据现实生活经验可知，公交车发车间隔相对固定，方便市民安排计划候车出行；其二，从简化模型的角度考虑，每辆车的司机固定，即司机间不允许换车开车；其三，单班车一天不超过5个班次，即认定为所有单班车一天总班次相加不超过5班。 对于题目一，从各班次发车间隔相等这一假定条件出发，要使在早高峰时段运行的车辆数最少，只需发车间隔尽可能大，于是我们取早的最大发车间隔5 分钟来安排发车，由于该题无对单班车数量的其他要求，我们假定单班车在早高峰时段安排2辆，同时考虑到车辆要完成一个班次的运行后才可进行下一班次，建立相关模型，用Lingo编程求解得早高峰时段总共运行24个班次，所需的最少公交车数为16辆。 对于问题二，在已有模型的基础上，综合考虑全天的工作安排，发车间隔仍取每个阶段的最大发车间隔，同样的，考虑到单班车只在高峰期运行，在早高峰运行2到3个班次，在晚高峰运行2到3个班次，且每天运行不超过五个班次，，根据资源利用的最大化原则，我们知道单班车数不能超过3辆，这里我们仍假设单班车数为2辆，根据题目要求，我们要使每辆公交车的工作时间和上下午司机的工作时间尽可能均匀，且要使车辆的利用率得到最大，根据以上条件建立公交车排班模型，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。具体公交车排班计划表见表2—1。 对于问题三，该题约束了单班车数量不少于3辆，由问题二的分析既得单班车数量为3辆，改变问题二模型中的相关参数，用Lingo编程求解得全天总共运
2007B题：乘公交，看奥运（数据有变化）我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观 众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 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 有少量更改）
《交通标准化》２００６年第１０期 ＣＯＭＭＵＮＩＣＡＴＩＯＮＳＳＴＡＮＤＡＲＤＩＺＡＴＩＯＮ．Ｎｏ．１０，２００６ 报告认为该段路堑处于古滑坡前缘，最大开挖坡高为１３ｍ左右。根据勘探地质资料，路堑开挖后可能诱发古滑坡复活，故在滑体中部设１４根抗滑桩。由于对该路段土性的误判，即将残坡积层下伏厚层河流阶地沉积物判为上部滑坡堆积物，滑动面为基岩面，人为增加了滑体厚度及滑坡规模。当施工第一根抗滑桩挖到设计标高处时，设计人员到现场验槽，发现下部挖桩废渣为卵石土，主要成分为砂岩、花岗岩、 石英岩等，成分杂乱，砂质充填，不是残坡积成因堆积物；但二级坡开挖面仍为残坡积物，为谨慎起见，施工方暂停抗滑桩施工，局部开挖一级坡断面，开挖后发现下部卵石层为河流堆积物，卵石排列韵律明显，且无变形迹象。根据揭露地层情况，滑坡残坡积堆积物厚度薄，上部山体基岩出露，后缘残留物较少，重新分析路堑开挖后稳定性，认为不可能复活，因而取消原抗滑桩措施及有关附属工程措施，只 进行一般边坡防护，为工程建设挽回直接经济损失２００多万元。 ４结语 ４．１公路工程设计是一系统性 工程，边坡工程是公路工程中重要的组成部分，同时受建设区域自然地质环境、路线设计、施工等多因素的影响，不确定因素较多，需认真分析研究。 ４．２山区公路工程病害的发生， 主要受坡体地质条件（时代成因、物力力学性质等）控制，而人工切坡、降水等外在条件为诱发因 城市公交线网优化的 非线性模型 姚本伦１，张卫华２ （１．合肥城市规划设计研究院，安徽合肥２３０００１；２．合肥工业大学交通研究所，安徽合肥２３０００９） 摘要：通过对城市公交线网优化的整体研究，给出其优化的主要内容、优化原则以及线网优化的主要因素，提出公交线 网优化的约束条件和三大优化目标，并给出相应的数学表达式使约束条件和优化目标定量化，同时建立公交线网整体优化的模式，并对其进行讨论和评价，有助于提高城市公交线网的优化效率，同时可使约束条件和优化目标定量化。 关键词：公共交通；线网优化；整体模式；中图分类号：Ｕ２２ 文献标识码：Ａ 文章编号：１００２－４７８６（２００６）１０－００９４－０４ ＡＮｏｎ－ｌｉｎｅＯｐｔｉｍｕｍＭｏｄｅｌｏｆＵｒｂａｎＰｕｂｌｉｃＴｒａｆｆｉｃＮｅｔｗｏｒｋ ＹＡＯＢｅｎ－ｌｕｎ１，ＺＨＡＮＧＷｅｉ－ｈｕａ２ （１．ＨｅｆｅｉＵｒｂａｎＰｌａｎｎｉｎｇ＆ＤｅｓｉｇｎＩｎｓｔｉｔｕｔｅ，Ｈｅｆｅｉ２３００１，Ｃｈｉｎａ；２．ＴｒａｆｆｉｃＩｎｓｔｉｔｕｔｅ，ＨｅｆｅｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ， Ｈｅｆｅｉ２３０００９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂａｓｅｄｏｎｔｈｅｓｔｕｄｙｏｆｕｒｂａｎｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎａｎｄｔｈｅｄｉｓｃｕｓｓｉｏｎｏｎｔｈｅ ｃｏｎｔｅｎｔ，ｐｒｉｎｃｉｐｌｅａｎｄｍａｉｎｆａｃｔｏｒｓｆｏｒｏｐｔｉｍｉｚａｔｉｏｎｗｉｔｈｒｅｌａｔｉｖｅｍａｔｈｅｍａｔｉｃａｌｅｘｐｒｅｓｓｉｏｎｓｆｏｒｄｉｓｔｉｎｃｔｏｐｔｉ－ｍｕｍｏｂｊｅｃｔｓｆｕｎｃｔｉｏｎｆｏｒｍａｎｄｒｅｓｔｒｉｃｔｃｏｎｄｉｔｉｏｎｓ，ａｖａｒｉｅｄｏｂｊｅｃｔｉｖｅｓａｎｄｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｏｆｐｕｂｌｉｃｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎｃａｎｂｅｂｕｉｌｔ．Ｉｔｉｓｈｅｌｐｆｕｌｆｏｒｉｍｐｒｏｖｉｎｇｔｈｅｏｐｔｉｍｉｚｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｕｒｂａｎｔｒａｆｆｉｃｌｉｎｅｎｅｔｗｏｒｋ． Ｋｅｙｗｏｒｄｓ：ｐｕｂｌｉｃｔｒａｆｆｉｃ；ｌｉｎｅｎｅｔｗｏｒｋｏｐｔｉｍｉｚａｔｉｏｎ；ｉｎｔｅｇｅｒｍｏｄｅｌ""""""""""""""""""""""""""""""""""""""""""""" ９４
第17卷第2期 湖南城市学院学报（自然科学版）V ol.17 No.2 2008年6月 Journal of Hunan City University （Natural Science） Jun. 2008 公交最优路径选择的数学模型及算法 雷一鸣 （广东工业大学华立学院，广州 511325） 摘要：在公交出行查询系统中，最关键的部分是寻找两站点间乘车的出行最优路径问题．建立了以最小换乘次数为第一目标，最小途经站点为第二目标的公交出行最优路径模型．同时，设计了一种算法以确定最优公交线路序列，分析了线路相交的几种情况，给出了换乘点选择方法． 关键词：最优路径；换乘次数；公交网络 中图分类号：O232文献标识码：A文章编号：1672–7304(2008)02–0050–03 公交最优路径问题一直是应用数学、运筹学、计算机科学等学科的一个研究热点．对公交最优路径问题的理论研究主要包括公交网络的数学描述和设计最优路径算法．在公交网络描述方面，Anez等用对偶图描述能够涵盖公交线路的交通网络，Choi等讨论了利用GIS技术从街道的地理数据产生公交线路和站点的问题；在设计最优算法方面，常用的算法[1]有Dijkstra算法、Floyd 算法、Moore-pape算法等．Moore-pape算法计算速度较快，适用于大型网络，但它无法进行“一对一”的计算．Floyd算法虽然可以快速地进行“多对多”的计算，但它不能应用于大型网络，而Dijkstra算法是目前公认的最好的算法，但它数据结构复杂、算法时间长，不适合公交线路的查询．本文首先对公交网络进行了数学描述，考虑到公交乘客出行时所面临的各种重要因素，包括换乘次数、途径站点、出行耗时和出行费用等，选择以换乘次数最少作为最优路径算法的第一约束目标，而出行耗时虽难以准确测算但它与途径站点数相关，所以选择易于量化的途经站点数最少作为第二约束目标，建立公交乘车数学模型，设计相应的算法，并利用有关实验数据验证了它的有效性和可行性． 1 模型的建立及其算法 1.1 模型假设及符号规定 为了更好地建立数学模型，首先对公交网络及出行者作出以下假设[2]： 1)不考虑高峰期、道路交通堵塞等外界因素对乘车耗时的影响． 2)假设出行者熟悉公交站点及附近地理位置，并且知道可乘的各种公汽和地铁以及到达目的地有哪几种不同选择的机会．在公交线路网中， 不同的公交线路在行程上一定会有重叠，也就是说不同的线路上一定会有同名站点．在进行网络分析时，把空间上相近的异线同名站点合理抽象成一个节点． 3)假设出行者对公汽和地铁的偏好程度不一样．在不换乘的情况下，宁愿乘地铁，以求舒适；在路途较近的情况下，宁愿坐公汽而放弃乘地铁．出行者可根据自己的偏好结合自己的出行需求（换乘次数、最短路程、费用等），可在各种出行方案中选出满足自己出行需求的乘车方案．设() L I为经过点A或其附近的公交线路集，其中1,2,..., I m =；() S J为经过点B或其附近的公交线路集，其中,,..., J12n =；(,) E I U为线路 ) (I L上的站点，其中,,..., U12p =；(,) F J V为线路) (J S上的站点，其中,,..., V12q =；() X K为经过站点) ,(U I E的线路，其中,,..., K12w =；() Y O 为经过站点) , (V J F的线路，其中,,..., O12v =；(,) d E F M ≤表示从站点E步行到站点F之间的距离不超过乘客换车时步行的最大心理承受值M，其中M表示乘客在换车时步行的最大心理承受值．通常，M与公交站点间的平均距离呈线性正相关． Ai Z表示站点A的下行第i个站点； Bj Z表示站点B的上行第j个站点；另外，公交的可行线 路的集合可表示为：{| i i TR TR TR == 0112,1 ,,,,,, i i i i d a p a p a ? < ,} id d p a>，其中，{} 01,1 ,,,, i i d d a a a a ? 为站点集合，{} 12,1 ,,,, i i i d d p p p p ? 为公交车次的集合， i TR 收稿日期：2008-03-10 作者简介：雷一鸣(1972-)，男，湖南临武人，助教，硕士，主要从事数学模型及经济信息管理研究．
公交站优化设计意义 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
公交站优化设计意义 公交停靠站点相对于城市道路及用地来说,虽然仅仅只是一个点,但由于其在公交系统中必不可缺的重要性,使其广泛的分布在城市各处,公交停靠站的布局、设置和设计不仅关系到公共交通运输的质量和效率,而且影响道路交通的运行质量和城市环境,牵扯到方方面面的问题。论文通过较为全面的交通调查和深入的理论分析,在总结公交运行、停靠特征规律的基础上,研究探讨了路段和交叉口不同类型公交停靠站点与其他交通流之间的相互作用和影响机理,建立了路段及交叉口不同类型公交站点车辆停靠延误模型及公交停靠对其他交通流延误和道路通行能力的影响模型,在比较分析、综合优化的基础上,研究发展了一套比较系统的公交停靠站布局、设置和设计的优化技术和方法。论文首先对公交停靠的最基本特征指标-公交车辆到达分布、加减速时间分布、公交停靠时间分布特征进行了分析,并给出了分布拟合函数,找出了各种特征分布所遵循的规律。在公交停靠站点对路段交通流的影响研究方面,论文选取了最常见的三幅路和四幅路沿机非分隔带和沿人行道设置的五种类型的公交站点。通过制定详细的调查方案,分别对各种类型公交站点对路段交通流的影响因素进行了全面细致的调查,然后根据调查数据,分析了各种影响因素对交通流运行的影响程度和态势,选取主要影响因素,构建了不同类型公交站点车辆停靠对道路交通流影响的理论模型,进而根据调查数据对所建模型进行回归拟合,确定了各类影响模型的回归参数和拟合效果。在公交停靠站点对信号交叉口交通流的影响研究方面,根据公交车辆停靠对不同类
龙源期刊网 https://www.doczj.com/doc/e113969271.html, 公交线路选择的优化模型 作者：张俊丽 来源：《价值工程》2015年第28期 摘要：本文针对城市公交线路选择问题建立了相应的数学模型。将公共自行车看作独立于公汽、地铁的第三种交通方式。利用网络图，主要从换乘次数、出行花费和出行总时间三个方面来确定最佳线路，分别考虑了各单目标，增加不同的上限约束，建立了任意两站点的最佳线路相应的网络流模型。 Abstract： In this paper， the corresponding mathematical model is established for the problem of urban public transportation route selection. The public bicycle as independent of the bus， the subway third modes of transport. Using the network diagram， three main factors are considered to find the best route， the number of trips， travel expenses and travel time.The network flow model of the best optimal line between any two sites， which considers the single objective and the different upper bound constraints. 关键词：公交系统；最佳线路；最小费用流；优先因子 Key words： bus system；best line；minimum cost flow；priority factor 中图分类号：U491.1+7 文献标识码：A 文章编号：1006-4311（2015）28-0206-02 0 引言 城市公共交通网络是城市交通网络的重要组成部分，提高城市交通系统的利用率被公认为是改善交通拥堵的有效途径之一。而如何优化城市现有公交网络以提高城市公交系统的利用率，是当今倍受关注的一个重要课题。公交汽车和城市轨道交通在城市公共交通体系中发挥着大动脉的作用，但是由于线路和站点布局的限制，是无法覆盖城市每一个角落的。即在公共交通体系的末端，缺少一套针对每个乘客特定的短途出行需求的公共交通微循环系统。为了解决这一问题，一种能够实现城市公共交通微循环的公共自行车租赁系统被引入我国。西安市区也常规地在轨道交通站点、公交站点、社区门口设置租赁点，通过“公共自行车管理系统”来管理这些租赁点的自行车。对租赁站点的发展规模预测、追加投资额的分配问题进行探讨，对政府建设城市公共自行车租赁系统具有一定的指导意义。但是在如何将公共交通中地铁、公共汽车、公共自行车租赁有效结合一直是个空白。 本文给出了城市中任意两站点最佳线路方案。本文认为所谓最佳线路，应该从乘车费用、公共自行车骑行时间、换乘次数、出行时间四个方面来理解。对于任意两站点的最佳线路，建立了网络流模型。 1 模型准备：构造容量费用网络图N=（V，E，C，B）
11701 B 本科 2001年全国大学生数学建模竞赛答卷 （全国一等奖） 学员：叶云周迎春齐欢指导老师：朱家明 公交车调度方案的优化模型 摘要 本文建立了公交车调度方案的优化模型，使公交公司在满足一定的社会效益和获得最大经济效益的前提下，给出了理想发车时刻表和最少车辆数。 并提供了关于采集运营数据的较好建议。 在模型Ⅰ中，对问题1建立了求最大客容量、车次数、发车时间间隔等模型，运用决策方法给出了各时段最大客容量数，再与车辆最大载客量比较， 得出载完该时组乘客的最少车次数462次，从便于操作和发车密度考虑，给 出了整分发车时刻表和需要的最少车辆数61辆。模型Ⅱ建立模糊分析模型， 结合层次分析求得模型Ⅰ带给公司和乘客双方日满意度为（0.941，0.811） 根据双方满意度范围和程度，找出同时达到双方最优日满意度 (0.8807,0.8807)，且此时结果为474次50辆；从日共需车辆最少考虑，结果 为484次45辆。对问题2，交待了综合效益目标模型及线性规划法求解。对 问题3，采集方法是遵照前门进中门出的规律，运用两个自动记录机对上下 车乘客数记录和自动报站机(加报时间信息)作录音结合，给出准确的各项数 据，返站后结合日期储存到公司总调度室。 关键词：公交调度模糊优化法层次分析满意度
一、问题的提出 公交公司制定公交车调度方案，要考虑公交车、车站和乘客三方面因素。我国某特大城市某条公交线路情况，一个工作日两个运营方向各个站上下车的乘客数量统计见表1。已知运营情况及调度要求如下： 1、公交线路上行方向共14站，下行方向共13站； 2、公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运营的平均速度为20公里/小时。车辆满载率不应超过120%，一般也不低于50%； 3、乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟。 现提出以下三个问题： 1、试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。 2、如何将这个调度问题抽象成一个明确完整的数学模型，并指出求解方法。 3、据实际问题的要求，如果要设计好更好的调度方案，应如何采集运营数据。 二、符号约定 a：上或下行第j时段第k站上车人数 ijk b：上或下行第j时段第k站下车人数 ijk l上或下行第j时段最大客容量 ij k上或下行时第j时段平均载客量 ij C日所需总车次 c上或下行第j时段的车次 ij s上或下行第j时段平均发车时差 ij p上或下行第j时段平均载客量 ij t上或下行的平均发车时间间隔 ij
公共交通网络运营优化系统的设计与实现3 王建明,靳文舟,郝小妮 (华南理工大学土木与交通学院,广东广州 510640) 摘 要:阐述了公共交通网络运营优化系统的功能结构,分析了系统的运行思路;针对公交预测子系统,提出了基于IC卡的基础公交数据的获取及分层配流思想;针对网络运营评价子系统, 提出了以政府、企业和乘客三方主体为目标的评价方法;针对网络运营优化子系统,提出了逐层实 现公交线网优化的“分层配流优化”思想;基于组件ArcEngine等软件,设计了公共交通网络运营 优化系统,实现对优化结果的图形化显示,为规划部门及企业提供决策信息。 关键词:公共交通;系统开发;网络运营优化;网络运营评价 中图分类号:U491.1 文献标志码:A 文章编号:1671-2668(2010)02-0033-03 3基金项目:国家863计划项目(2007AA11Z201);国家自然科学基金项目(50878089) 随着中国城市道路建设步伐的不断加快,城市 土地利用日益紧张,道路供给远远低于需求,交通拥 堵问题愈演愈烈,于是,优先发展运量大、占地少的 城市公共交通成为各大城市解决交通问题的共识。 但公共交通的发展速度远远跟不上城市发展的步 伐,主要有以下原因:1)政府、企业在运营模式上 缺乏对构建一体化公交体系的深入思考;2)公共交 通便捷、经济的优势没有体现出来;3)公共交通网 络运营优化技术理论还未形成可操作、成熟、完备的 体系;4)国际上流行的软件和模型很难适应中国的 实际交通状况。而公共交通网络运营优化系统的实 现是解决线网优化和运营优化的重要手段。因此, 通过深入研究公共交通的网络运营优化技术,运用 综合交通网规划思想,建立一套公共交通网络运营 优化系统尤为重要。 1 系统架构 公共交通网络运营优化系统的功能结构如图1 所示,主要由基础数据、公交预测、网络运营优化和 网络运营评价等子系统组成。 公共交通网络运营优化系统的运行思路:针对 铁路与公路客运站、轨道交通和常规公交的基础数 据及社会经济情况、城市规划布局和人口分布情况 等建立数据库,通过数据分析和建模计算公交需求 预测数据,把得到的预测数据分配到公交线网上,对 公交网络运营效果进行评价;在评价的基础上建立 优化目标与模型,对公交网络运营进行优化调整;再 在调整后的公交线网上进行公交需求预测,通过预 测结果进行线网的再次评价。这样通过根据实际网 络营运状况不断进行优化调整,形成客流数据与公 交网络的动态调整平衡,最终使公共交通网络运营 总体趋向最优化 。 图1 公共交通网络运营优化系统功能结构 2 系统设计 建立公共交通网络运营优化系统的目的是调整 网络运营配置、整合各种公交方式以发挥网络运营 的最佳总体效率,为动态公交网络调整和运营策略 的制定提供科学的决策支持。其设计目标:1)为公 交企业及管理部门提供管理和决策的辅助手段;2) 提供便捷的属性和空间数据库建立、维护、分析方法 33 公 路 与 汽 运 总第137期 H i g hw ays&A utomoti ve A p plications
公交公交车调度方案优化设计 摘要 本文利用某一特大城市某条公交路线上的客流调查运营资料，以乘客的平均抱怨度、公司运营所需的总车辆数、公司每天所发的总车次数以及平均每车次的载客率为目标函数，建立了的分时段等间隔发车的综合优化调度模型。在模型求解过程中，采用了时间步长法、等效法以及二者的结合的等效时间步长法三种求解方法，尤其是第三种求解方法既提高了速度又改善了精度。结合模型的求解结果，我们最终推荐的模型是分时段等间隔发车的优化调度方案。 在建立模型时，我们首先进行了一些必要假设和分析，尤其是针对乘客的抱怨程度这一模糊性的指标，进行了合理的定义。既考虑了乘客抱怨度和等待时间长短的关系，也照顾了不同时间段内抱怨度对等待时间的敏感性不同，即乘客在不同时段等待相同时间抱怨度可能不一样。 主要思想是通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优的发车时间间隔，但计算量过大，对初值依赖性强。等效法是基于先来先上总候车时间和后来先上的总候车时间相等的原理，通过把问题等价为后来先上的情况，巧妙地利用“滞留人数”的概念，把原来数据大大简化了。很快而且很方便地就可求出给定发车间隔时的平均等待时间，和在给定平均等待时间的情况下的发车间隔，但该方法只能对不同时段分别处理。结合前两种方法的优点提出等效时间步长法，即从全天时段内考虑整体目标，使用等效法为时间步长法提供初值，通过逐步求精，把整个一天联合在一起进行优化。通过对模型计算结果的分析，我们发现由于高峰期乘车人数在所有站点都突然大量增加，而车辆调度有滞后效应，从而建议调度方案根据实际情况前移一段适当的时间。在模型的进一步讨论和推广中，我们还对采集运营数据方法的优化、公共汽车线路的通行能力以及上下行方向发车的均衡性等进行了讨论。 在求具体发车时刻表时，利用等效时间步长法，较快地根据题中所给出的数据设计了一个较好的照顾到了乘客和公交公司双方利益的公交车调度方案，给出了两个起点站的发车时刻表（见表二），得出了总共需要49辆车，共发440辆次，早高峰期间等待时间超过5分钟的人数占早高峰期间总人数的0.93%，非早高峰期间等待时间超过10分钟的人数占非早高峰期间总人数的3.12%。引入随机干扰因子，使各单位时间内等车人数发生随机改变。在不同随机干扰水平下，对推荐的调度方案进行仿真计算，发现平均抱怨度对10%的随机干扰水平相对改变只有0.53%，因此该方案对随机变化有很好的适应性，能满足实际调度的需要。 1．问题的提出
城市公交线路选择优化模型 摘要 本文针对城市公交线路选择问题建立了两个模型,一个是基于集合寻线算法模型，另一个是图论模型。 基于集合寻线算法模型中,首先固定换乘次数n,通过集合论的相关知识把确定换乘点的具体位置, 转化成确定一些集合间的交集，从而建立集合寻线算法，再根据集合相关公式,得到所有可行线路；进一步考虑时间和费用等因素,对可行线路进行处理比较，得出最佳线路。 图论模型中,通过图论的知识将整个北京市交通线路构建出一个有向图,每个站点与有向图的顶点一一对应，同一线路上的相邻站点对应为有向边，通过不同目标(时间、费用）给有向图进行不同的赋权,分别将不同目标转化为赋权有向图寻找最短有向路,根据最短路径算法，得到最佳线路。最后综合评价了两个模型的优缺点。 关键词:集合寻线算法；最短路算法;换乘点;赋权有向图
1 问题提出 北京将于200８年举行奥运会,届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交,包括公汽、地铁等)出行。随着现代化的步伐加快,城市的公交系统有了很大发展,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。在现实生活中,公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路,所以针对市场需求以及公交线路选择上的问题,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 该系统的核心在于线路选择的模型与算法，应该从实际情况出发,满足查询者的各种不同需求。根据附录１、附录2，解决如下问题: １.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法,求出以下6对起始站→终到站之间的最佳线路。 (1) S3359→Ｓ182８（２) Ｓ155７→S０481（3）S0９71→Ｓ048５ (4) S00０8→Ｓ０073 (５）S0１48→S04８5 (６）S0０8７→Ｓ 36７６ ２.同时考虑公汽与地铁线路，解决以上问题。 3.假设知道所有站点之间步行时间,给出任意两站点之间线路选择的数学模型。 2 问题分析 为了研制开发一个解决公交线路最佳选择(即乘客在多条公交线路中根据自己的需求获得最适合自己的线路)问题的自主查询计算机系统,只要乘客给出起点站A和终点站B两个站点,系统就给出最佳交通线路，使得公众出行更加通畅、便利。而问题核心是如何在多条线路选择中获得最佳线路。 乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站,但若多次换乘公交，可能导致乘客所花时间及其费用的增加,更会给乘客造成不便。在奥运将在北京举行的背景下,我们知道乘客前往观看奥运比赛时,主要注重的是能否及时到达,所以在为乘客选择线路时,力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化，我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路,再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。 3 模型准备 3.1 模型假设 1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费)； 2.假设所有交通线路都不出现停运或者线路变动； 3.假设公汽的环行行驶线路是单向的。 3.2符号约定 c:相邻公汽站平均行驶时间(包括停站时间)，min c； = 3 d； = d：相邻地铁站平均行驶时间（包括停站时间），min 5.2 e:公汽换乘公汽平均耗时,min e(其中步行时间2min）; 5 = f(其中步行时间2min); = 4 f：地铁换乘地铁平均耗时,min
公交线路选择优化问题 摘要本文针对公交线路选择问题进行了讨论。最佳路线的选择受时间和票价两个因素的影响，将题目已知的公交线路信息转化成线路矩阵处理。 首先，从时间角度分析，所要寻找的路线经过的站点数和转车次数应该尽可能的少，考虑到所选择线路到达终点站所用的时间包括公交经过线路上各站点的时间、转车时间和步行时间，建立以所需时间最少为目标函数的线性优化模型一，从实际出发限制转车次数最多为2次，根据搜索算法利用MATLAB编程，求得问题一中S3359→S1828（其余见正文）之间的最佳路线为：L436下行-S1784-L167下行和L436下行-S1784-L217下行，所用时间为101分钟，总车费为3元；问题二中S3359→S1828之间的最佳路线为：L015 上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。 其次，从票价角度分析，寻找的路线应尽可能是单一票价车路线或经过站点数尽可能少的分段计价车路线，考虑到所选择线路需要的总车费包括公汽费用和地铁费用，建立以所需车费最少为目标函数的线性优化模型二，根据搜索算法利用MATLAB编程，求得问题一中S3359→S1828之间存在L436下行-S1784-L167下行等10条最佳路线（其余见正文），所用时间为101分钟，总车费为3元；问题二中S3359→S1828之间的最佳路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。 再次，根据乘客的不同需求可以赋予时间和票价两个因素不同的权值，建立以所需时间与所用票价在各自权值下的和最小为目标函数的线性优化模型三，当取权值皆为0.5时得问题一中S3359→S1828之间的最佳路线为：L436下行-S1784-L167下行和L436下行-S1784-L217下行，所用时间为101分钟，总车费为3元；问题二中S3359→S1828之间的最佳路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。 最后，对模型进行了评价，并将该模型推广到路径选择问题中。 关键词公交线路选择；线性优化模型；搜索算法
公交车调度 公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。 该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。 试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。 如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。
公交车调度方案的优化设计 摘要 本文利用某一特大城市某条公交路线上的客流调查运营资料，以乘客的平均抱怨度、公司运营所需的总车辆数、公司每天所发的总车次数以及平均每车次的载客率为目标函数，建立了的分时段等间隔发车的综合优化调度模型。在模型求解过程中，采用了时间步长法、等效法以及二者的结合的等效时间步长法三种求解方法，尤其是第三种求解方法既提高了速度又改善了精度。结合模型的求解结果，我们最终推荐的模型是分时段等间隔发车的优化调度方案。 在建立模型时，我们首先进行了一些必要假设和分析，尤其是针对乘客的抱怨程度这一模糊性的指标，进行了合理的定义。既考虑了乘客抱怨度和等待时间长短的关系，也照顾了不同时间段内抱怨度对等待时间的敏感性不同，即乘客在不同时段等待相同时间抱怨度可能不一样。 主要思想是通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优的发车时间间隔，但计算量过大，对初值依赖性强。等效法是基于先来先上总候车时间和后来先上的总候车时间相等的原理，通过把问题等价为后来先上的情况，巧妙地利用“滞留人数”的概念，把原来数据大大简化了。很快而且很方便地就可求出给定发车间隔时的平均等待时间，和在给定平均等待时间的情况下的发车间隔，但该方法只能对不同时段分别处理。结合前两种方法的优点提出等效时间步长法，即从全天时段内考虑整体目标，使用等效法为时间步长法提供初值，通过逐步求精，把整个一天联合在一起进行优化。通过对模型计算结果的分析，我们发现由于高峰期乘车人数在所有站点都突然大量增加，而车辆调度有滞后效应，从而建议调度方案根据实际情况前移一段适当的时间。在模型的进一步讨论和推广中，我们还对采集运营数据方法的优化、公共汽车线路的通行能力以及上下行方向发车的均衡性等进行了讨论。 在求具体发车时刻表时，利用等效时间步长法，较快地根据题中所给出的数据设计了一个较好的照顾到了乘客和公交公司双方利益的公交车调度方案，给出了两个起点站的发车时刻表（见表二），得出了总共需要49辆车，共发440辆次，早高峰期间等待时间超过5分钟的人数占早高峰期间总人数的0.93%，非早高峰期间等待时间超过10分钟的人数占非早高峰期间总人数的3.12%。引入随机干扰因子，使各单位时间内等车人数发生随机改变。在不同随机干扰水平下，对推荐的调度方案进行仿真计算，发现平均抱怨度对10%的随机干扰水平相对改变只有0.53%，因此该方案对随机变化有很好的适应性，能满足实际调度的需要。
2007高教社杯全国大学生数学建模竞赛题目 （请先阅读“对论文格式的统一要求”） B题：乘公交，看奥运 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)：3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。 【附录2】公交线路及相关信息（见数据文件B2007data.rar）
公交线网优化设计理论及实现方法研究 优先发展城市公共交通系统是解决大、中城市交通问题的最佳途径。在国家大力发展公共交通和提倡公交优先的背景下,本文以国家“十五”科技攻关项目“公交专用道信号优先控制策略与技术研究”和国家自然科学基金重点项目“城市交通网络优化与管理”为依托,围绕城市公共汽车交通网络设计的关键理论与实现技术展开研究,以学术意义和实用价值并重为原则,在公交网络设计方法研究、公交线网优化设计模型与算法研究,公交线路规模与资源配置优化研究,公交线网优化设计辅助决策研究等方面取得了一系列成果。首先,论文从方法构筑层面,提出了理想条件下的公交网络及枢纽布局模式,并依据不同时期与条件的网络设计需求特点,将公交线网优化设计分为方案改进型和方案生成型两类,并详细分析了每种设计方法的输入和处理流程;其次,论文从网络优化层面,以用户出行时间和未满足出行需求量(无有效公交出行路径出行量)两者费用最小为目标构筑了公交线网优化设计模型,基于候选线路集生成方法的研究,结合公交出行路径搜索与客流分配方法,提出了一种基于路线优选的公交线网优化设计方法,并引入模拟退火拉伸思想,改进了遗传算法的遗传选择操作,实现了一种基于改进遗传算法对公交线网优化模型的求解方法;再次,论文从线路优化层面分别提出了公交线路规模优化与资源配置优化问题,并研究了线路布设、站点布局、车辆配置、运营组织等四个方面的优化问题,重点研究了基于乘客出行距离分布规律,乘客平均出行时间最小化的公交站距优化模型及算法。随后,论文从实现层面研究了公交线网优化设计辅助决策系统的功能需求、总体设计以及开发方法,并基于组件式GIS实现了原型系统的开发。 最后,论文对全文进行了总结,指出了论文的创新点,并对有待于进一步研究的问题进行了展望。本论文的研究成果在理论层面有助于公交线网优化设计、公交线路站点布局优化方案的实施;应用层面为开发公交线网优化设计辅助决策系统提供了方法指导,为进一步开发线网优化决策支持系统奠定了基础,是未来公交网络设计领域研究的重要方向。
第30卷第6期2000年11月 东南大学学报( 自然科学版) JO URNAL OF S OU THEAS T UNIVERSITY (Natural Science Edition) Vol 130No 16 Nov.2000 基于GIS 的公交乘客出行路径选择模型X 杨新苗 王 炜 马文腾 (东南大学交通学院,南京210096) (清华大学,北京100084) 摘 要 公交乘客出行路径选择模型是公交乘客信息系统的关键技术.本文通过对公交乘客出行心理的研究,结合地理信息系统(G IS)的特点,提出了以换乘次数最少为首要目标、出行距离最短为第二目标的基于GIS 的公交乘客出行路径选择模型.为提高路径搜索效率,模型中提出了GI S 方向估价函数的概念.在南京市实际公交网络上的试算结果表明该模型实用、高效. 关键词 出行路径选择模型;乘客信息系统;公共交通;地理信息系统分类号 U121 X 国家自然科学基金资助项目(59838310). 收稿日期:2000-02-28. 第一作者:男,1974年生,博士研究生. 公交乘客出行路径选择模型的研究对于公交乘客信息系统的研究和开发有着重要的意义.乘客信息系统是智能交通系统中的重要组成部分.乘客信息系统中以提供公交信息为主的部分称为公交乘客信息系统.公交乘客信息系统最重要的一个功能是在乘客给出起迄点后,自动生成最优的出行路径方案供乘客选择.搜索与生成最优出行路径的理论模型就是公交乘客出行路径选择模型.公交乘客出行路径选择模型研究的实质是寻找乘客的出行在公交网或道路网上分布的规律.研究和建立更接近现实的模型,有利于得到更合理的公交客流分配结果.国内对乘客出行心理的研究较少,现有的出行路径选择模型多为基于/出行距离最短0或/出行耗时最少0的最短路模型,但实际的调查却表明/换乘次数0是大部分公交乘客在选择出行路径时首要考虑的因素.而且现有的模型基本上是在道路网上进行的,道路网上的最优路径,不一定是公交网上可行的路径.本文通过对公交乘客出行心理的研究,结合GIS(地理信息系统)的特点,提出了以/换乘次数最少0为首要目标、/出行距离最短0为第二目标的公交乘客出行路径选择模型,并且在南京市公交网络上进行了试算. 1 公交乘客出行心理研究 通过对公交乘客的出行心理、行为进行调查研究,确定模型的优化目标和约束条件.公交乘客选择出行路径的决策过程主要受到以下3个因素的作用:/换乘次数0、/出行距离0和/出行耗时0.换乘次数是指乘客在完成一次出行过程中所换乘的次数.出行距离分为车上距离和车外距离两部分.车外距离是乘客为乘车而步行的距离,它包括从起点到上车站台的距离、换乘距离以及下车后到目的地的距离.出行耗时同样也包括车上和车外两部分,只不过乘客的车外耗时还包括在站台上的等车时间.1999年在南京市的8个主要公交站点进行了一次公交乘