乘公交，看奥运
摘要
本文解决的是公交线路选择问题，根据查询者的各种不同需求，设计出一套线路选择的模型与算法。乘客一般希望自己乘坐的公交线路经济、方便、快捷，因此我们分别以总费用最小、总耗费时间最少以及总换车次数最少为目标，建立最优化模型。
针对问题一：由于交通网络的复杂性，公交线路的选择问题不同于一般的图论问题，根据城市公共交通的自身特点，利用改进的扩散路由算法，可以实现在城市中任意两站之间的线路查询。乘客一般希望乘坐的公交路线能够经济、快捷、方便，因此可以分别以总费用M最小、总耗费时间Tg最少以及总换车次数N最少为目标建立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。如下表： 出发站 ? 终点站 最短耗时（min） 最少转乘次数（次） 最少费用（元） S3359 S1828 101 1 3 ? S1557 S0481 106 2 3 ? S0971 S0485 128 1 3 ? S0008 S0073 83 1 2 ? S0148 S0485 106 2 3 ? S0087 S3676 65 2 2 ? 针对问题二：在问题一的基础上加入了地铁线路，算法与问题一一样，利用改进的扩散路由算法分别以总费用M最小、总耗费时间Tg最少以及总换车次数N最少为目标建立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。如下表： 出发站 ? 终点站 最短耗时（min） 最少转乘次数（次） 最少费用（元） S3359 S1828 73 1 3 ? S1557 S0481 106 2 3 ? S0971 S0485 101 1 3 ? S0008 S0073 70 1 2 ? S0148 S0485 92.5 2 5 ? S0087 S3676 38 0 1 ? 针对问题三：在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间，因此我们要对步行时间加以限制。在设定最大步行时间限制的情况下， 分别以总费用M最小、总耗费时间Tg最少以及总换车次数N最少为目标建立最优化模型。
最后，我们利用GUI Design Studio软件设计出北京公交自主查询系统的GUI图形界面，并对仅考虑公汽线路的情况（问题一）和考虑公汽与地铁线路的情况（问题二）分别进行仿真，得到满足查询者各种不同需求的最佳线路。该公交自主查询系统实用性强，可以满足查询者的各种不同需求。
关键字：改进的扩散路由算法、GUI图形界面、最优化模型、换车次数
1.问题重述
问题背景
我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
公交线路及相关信息： 【附录1】基本参数设定
相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟
公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价
为：0～20站：1元；21～40站：2元；40站以上：3元
地铁票价：3元（无论地铁线路间是否换乘）
注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。 【附录2】公交线路及相关信息 （见数据文件B2007data.rar）
本文需解决的问题有：
问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
问题二：同时考虑公汽与地铁线路，解决以上问题。
问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
2.模型假设与符号说明
2.1模型假设
假设一：公汽线路间的换乘只能是在同一公汽站或是在对应的地铁站； 假设二：查询者转乘公交的次数不超过两次； 假设三：不考虑公汽线路出现拥堵的情况； 假设四：从起点步行至通过地铁站相连的车站和从某站（通过地铁站与终点相连）步行至终点所花费的时间不计入总乘车时间。
2.2符号说明 Li T ig表示第i条公汽线路编号 表示第i条地铁线路编号（i=1,2） 表示从起点站到终点站耗费的总时间 表示相邻公汽站平均行驶时间 表示相邻地铁站平均行驶时间 表示公汽换乘公汽换乘次数 表示地铁换乘地铁换乘次数 表示地铁换乘公汽换乘次数 表示公汽换乘地铁换乘次数 表示总换车次数 表示总费用 表示选择的交通方式（其中w=1表示单一票价的公汽；w=2表示分段计价的公汽；w=3 表示地铁） 表示乘坐第i辆公汽需要经过的站点个数 表示乘坐第i列地铁需要经过的站点个数 T TT s d ss dd ds sd NNNNNMw s iti Pi 表示乘坐第i辆车的费用 表示步行的最大时间限制 tm fsfd i 表示步行经过的公汽站点的个数 表示步行经过的地铁站点的个数 i
3.问题分析
本文研究的是公交线路的选择问题。某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统，以满足查询者的各种不同需求。为了设计这样一个系统，其核心是线路选择的模型与算法。 需求分析：
要开发此公交线路选择的自主查询计算机系统至少需要满足以下要求：
第一，模型的算法要利于程序的实现和在现实中的推广应用。即用户输入起始站和终到站两个参数后要在尽量短的时间内得到最佳的公交线路走法。
第二，要满足查询者的各种不同需求。所谓“不同需求”一是乘公交的时间要尽量少，二是车费要尽量少，三是转车次数要尽量少；
因此我们认为，算法简单易行是本文建立模型的最重要标准。
算法分析：
如果将整个城市看成一个连通图，图中的顶点代表公交站点，边代表公交线路，边的权值为相应点间隔的车站数，问题则等价于求赋权图中两点间的最短路径。求任意两顶点之间的最短路径算法很多，最经典的是Dijkstra算法，在地理信息系统中得到广泛应用。但是，Dijkstra算法难以应付公交线路网络中的复杂性。 根据城市公共交通的自身特点，考虑到便携设备本身存在的缺陷，如CPU运算速度低，内存容量小等，不宜采用Dijkstra算法，而改进利用扩散路由算法，实现在城市中任意两站之间的线路查询。 针对问题一：
首先，数据处理。由于公汽线路的类型是有差别的，按票价信息分为：单一票制和分段计价；按线路的循环模式分为：单线（分为上下行不一致的Ⅰ型和上下行一致的Ⅱ型两种）、环线（设为Ⅲ型）和按原路返回（设为IV）。其中可将按原路返回的线路（IV）归为上下行一致的II型（原序作为上行，倒序作为下行），这样就将线路分为两类：单线和环线。将公汽线路编号1~1040存入三维细胞元组中，并作出所有公汽站点的关联矩阵。
其次，选择算法。公交线路的选择问题不同一般的图论问题，根据城市公共交通的自身特点，改进利用扩散路由算法，可以实现在城市中任意两站之间的线路查询。
最后，模型确定。乘客一般希望乘坐的公交路线能够经济、快捷、方便，因此可以分别以总费用M最小、总耗费时间Tg最少以及总换车次数N最少为目标建
立最优化模型，根据改进的扩散路由算法选择出分别以总费用最小、总耗费时间最少以及总换车次数最少为目标的最佳路线。 针对问题二：
在问题一的基础上加入了地铁线路，并且与地铁站相邻的公汽站点可以通过地铁站步行达到。算法与问题一相似：
首先，考虑是否有直达的情况，如果可以直达则考虑起点站与终点站是否与统一地铁线路相邻，相邻则坐地铁直达，不相邻则坐公汽直达；
其次，考虑换一次车的情况，有四种可能：公汽换公汽、公汽换地铁、地铁换地铁、地铁换公汽。如果起点站与终点站都不与地铁相邻则为第一种可能，如果起点站不与地铁相邻而终点站与地铁相邻则为第二种可能，如果起点站与终点站都与地铁相邻则为第三种可能，如果起点站与地铁相邻而终点站与地铁不相邻则为第四种可能；
最后，考虑换两次车的情况，有六中可能：公汽换公汽再换公汽、公汽换地铁再换公汽、公汽换地铁再换地铁、地铁换公汽再换公汽、地铁换公汽再换地铁、地铁换地铁再换地铁。根据上面讨论将各种可能加入到算法中实现。 针对问题三：
在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间，因此我们要对步行时间加以限制。在设定最大步行时间限制的情况下， 分别以总费用M最小、总耗费时间T最少以及总换车次数N最少为目标建立最优化模型。
g4.数据处理
4.1数据存储
数据的处理是和我们的模型与算法密切相关的，即有什么样的模型算法就对应着特定形式的数据处理。根据上面对问题的分析，在解决该问题的过程中，我们要找的最佳路线，是通过搜索出所有可能线路对应的目标值、然后比较目标值得到的。而搜索的对象就是跟优化目标密切相关的关联矩阵。
我们通过以下的方法进行数据处理：
把“1.1 公汽线路信息.txt”、“2.1 地铁T1线换乘公汽信息.txt”和“2.2 地铁T2线换乘公汽信息.txt”三个文本文件导入到Matlab中，成为细胞元矩阵； 公汽线路编票价信息 上行线信息 下行线信息 号 分段计价 S0619-S1914-?-S0710 L001 分段计价 S3748-S2160?-S0004 S0004-S1968??S2160-S3748 L002 ?? ?? ?? ?? L519 L520 分段计价 S0036-S0203…S3414 S3414-S1462……-S0203-S0036 S1848-S2645??-S2027-S0600 单一票制1元 S0600-S2861?-S1848 4.2数据处理