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 问题提出北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。

随着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询者的各种不同需求。

根据附录1、附录2，解决如下问题：1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

并根据附录数据，利用建立的模型与算法，求出以下6对起始站→终到站之间的最佳线路。

(1) S3359→S1828 (2) S1557→S0481 (3) S0971→S0485(4) S0008→S0073 (5) S0148→S0485 (6) S0087→S36762.同时考虑公汽与地铁线路，解决以上问题。

3.假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模型。

2 问题分析为了研制开发一个解决公交线路最佳选择（即乘客在多条公交线路中根据自己的需求获得最适合自己的线路）问题的自主查询计算机系统，只要乘客给出起点站A和终点站B两个站点，系统就给出最佳交通线路，使得公众出行更加通畅、便利。

而问题核心是如何在多条线路选择中获得最佳线路。

乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站，但若多次换乘公交，可能导致乘客所花时间及其费用的增加，更会给乘客造成不便。

在奥运将在北京举行的背景下，我们知道乘客前往观看奥运比赛时，主要注重的是能否及时到达，所以在为乘客选择线路时，力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。

为了使问题简单化，我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路，再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。

、3 模型准备3.1 模型假设1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费）；2.假设所有交通线路都不出现停运或者线路变动；3.假设公汽的环行行驶线路是单向的。

3.2 符号约定c ：相邻公汽站平均行驶时间（包括停站时间），min 3=c ； d ：相邻地铁站平均行驶时间（包括停站时间），min 5.2=d ；e ：公汽换乘公汽平均耗时，min 5=e （其中步行时间2min ）；f ：地铁换乘地铁平均耗时，min 4=f （其中步行时间2min ）； g ：地铁换乘公汽平均耗时，min 7=g （其中步行时间4min ）； h ：公汽换乘地铁平均耗时，min 6=h （其中步行时间4min ）； ij t ：交通工具与交通工具换乘所需时间；k ：地铁票价，3=k 元； n ：换乘次数；ij N ：乘客在可选择的从起始站到终点站线路中第i 条线路的换乘点（包括始点和终点），1,,2,1,0+=n j ，0i N 为起点，1,+n i N 为终点；j M ：乘客从第1-j 换乘点上车到第j 换乘点的下车所付的票价，1,,2,1+=n j ； j W ：公交车从第1-j 换乘点到第j 换乘点经过的站点数（含第j 换乘点）1,,2,1+=n j ；j C ：公交车在第i 线路上从第j 换乘点到第1+j 换乘点线路；ij k ：公交车在第i 线路上从第1-j 换乘点到第j 换乘点经过每站所需时间； ni T ：只换乘n 次乘客从起始站到终点站选择第i 条线路所需要的总时间； ni S ：只换乘n 次乘客从起始站到终点站选择第i 条线路所需要的总费用。

4 基于集合寻线算法的模型4.1 集合寻线算法的建立现实乘客换乘的次数n 很小，公司在设计一个城市公交线路时，为了使线路更合理，一般不会使乘客要通过多次换乘（超过3次）才到达终点站。

则不妨假设换乘次数[]2,0∈n ，Z n ∈。

我们可以看到问题中关键要解决的是找出换乘点ij N 的具体位置，显然换乘点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。

由于公交线路不是一条直线段或者有一定几何规律的曲线，所以我们通过代数的相关知识，把具有同一属性的站点放入同一集合中，这样就把问题转化成代数问题。

基于此思想，我们建立以下集合寻线算法：步骤1：找出经过终点B 站的所有公交线路j B 存放到集合}|{j j B B B Y ∈=，以及这些线路j B 经过的所有站点存放到集合Q 。

步骤2：找出经过起始站A 的所有公交线路i A ，存放到集合}|{i i A A A X ∈=，以及这些公交线路i A 经过的站点存放到集合P 。

步骤3：判断X 和Y 的关系：1．若∅≠Y X ，即存在+∈Z j i ,，使得j i B A =，表示起始站A 到终点站B 之间有一条或几条直达线路，乘客不必换乘公交车，算出这些直达线路各自所需要的时间和票价；通过比较大小，得到该情况下的乘车最少时间min T 和最少费用min S ，以及其相应的线路。

2．若∅=Y X ，则说明起始站A 与终点站B 之间不存在公交车直达的情况，只能通过换乘才能到达终点站B ，则要寻找换乘点。

步骤4：查找公交线路i A 与公交线路j B 的所有共同站点a ，存放到集合}|{j i B A a a I ==。

集合I 中的元素是换乘点。

步骤5：判断集合I ：1．如果集合∅≠I ，即乘客可以通过一次换乘就能到达终点站。

记录换乘点及其相应线路。

2．如果集合∅=I ，即乘客不能通过一次换乘到达终点站，则要选取新的起始点。

步骤6：选取新的起始点：从集合P 中任取一站点A '（A A ≠'），即遍历集合P 中所有的元素，以站点A '代替原来的起始站A 。

转到步骤2，这样就能找出所有经过两次换乘的线路。

步骤7：通过重复上面的6个步骤可得经过n 次换乘的所有可能线路。

4.2 模型的建立4.2.1 时间及费用计算我们固定换乘次数n ，通过集合寻线算法，得到通过n 次换乘的所有可达线路，再对这些线路进行下面的运算：从起点站A 到终点站B ，i A ：经过起点站A 的第i 条公交线路； j B ：经过终点站B 的第j 条公交线路；只通过n 次换乘到达可选择的线路共有U 条，设第i 条乘坐线路的换乘点为ij N ,1,,1,0+=n j ，0i N 为起点，1,+n i N 为终点,第i 条线路上从第j 换乘点到第1+j 换乘点线路为ij C ，其途径的站点数ij W ，i n j ,,1,0 =，所付的票价ij M ,相邻站点平均行驶时间ij k ，第j 个换乘点需要的换乘时间为ij t 。

1）只考虑公汽线路：a.第i 线路所需要的总时间：en cW t W k T nj ij n j ij n j ij ij ni +=+=∑∑∑===111（1）其中，c 表示公汽相邻两站的平均行使时间，e 汽车换乘需要的平均耗时。

b.第i 线路所需要的总费用：∑==nj ij ni M S 1（2）其中,⎪⎪⎪⎩⎪⎪⎪⎨⎧=⎪⎭⎪⎬⎫>≤<≤<=004034020220011ij ij ij ij ij ij ij W C W W W C M ，段乘坐按段收费公汽，，，段乘坐单一票价公汽，2）同时考虑公汽与地铁线路：a.第i 线路所需要的总时间：∑∑==+=nj ij n j ij ij ni t W k T 11（3）其中，⎪⎩⎪⎨⎧=段乘坐地铁，段乘坐汽车，ij ij ij C d C c k⎪⎪⎩⎪⎪⎨⎧=，公汽换乘地铁，地铁换乘公汽，地铁换乘地铁，公汽换乘公汽h g f e ij tb.第i 线路所需要的总费用：∑==nj ij ni M S 1 （4）⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=⎪⎭⎪⎬⎫>≤<≤<=0040340202200131ij ij ij ij ij ij ij ij W C W W W C C M ，段乘坐按段收费汽车，，，段乘坐地铁，路段乘坐汽车单一票价线， 3）同时考虑公汽、地铁和步行时间：a.第i 线路所需要的总时间：∑∑==+=nj ij n j ij ij ni t W k T 11（5）其中，⎪⎩⎪⎨⎧=段为步行，段乘坐的是地铁，段乘坐的是汽车，ij ij ij ij C v C d C c k⎪⎪⎩⎪⎪⎨⎧=，公汽换乘地铁，地铁换乘公汽，地铁换乘地铁，公汽换乘公汽h g f e ij t b.第i 线路所需要的总费用：∑==nj ij ni M S 1 （6）⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=⎪⎭⎪⎬⎫>≤<≤<=0040340202200131ij ij ij ij ij ij ij ij W C W W W C C M ，段乘坐按段收费汽车，，，段乘坐地铁，路段乘坐汽车单一票价线， 注意：由于步行不需费用，所以要给个步行线路约束：步行时间不超过T 。