公交线路

乘公交，看奥运

摘要

本文解决的是公交线路选择问题，根据查询者的各种不同需求，设计出一套线路选择的模型与算法。乘客一般希望自己乘坐的公交线路经济、方便、快捷，因此我们分别以总费用最小、总耗费时间最少以及总换车次数最少为目标，建立最优化模型。

针对问题一：由于交通网络的复杂性，公交线路的选择问题不同于一般的图论问题，根据城市公共交通的自身特点，利用改进的扩散路由算法，可以实现在城市中任意两站之间的线路查询。乘客一般希望乘坐的公交路线能够经济、快捷、方便，因此可以分别以总费用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数据处理

公汽线路的类型是有差别的：

一．按票价信息分为：单一票制和分段计价，两种线路有不同的收费方法。 二．按线路的循环模式分为：单线（分为上下行不一致的Ⅰ型和上下行一致的Ⅱ型两种）、环线（设为Ⅲ型）和按原路返回（设为IV）。

其中可将按原路返回的线路（IV）归为上下行一致的II型（原序作为上行，倒序作为下行），这样就将线路分为两类：单线和环线。

针对问题一：我们将公汽线路1~1040进行编号，把公汽线路信息表做成如下1040?3的结构数组——“公汽线路信息数组”data_1： 公汽线路编号 票价信息 线路信息 分段计价 S0619-S1914-??S0128-S0710 001 分段计价 S0710-S0128??S1914-S0619 002 分段计价 S3748-S2160??-S1968-S0004 003 分段计价 S0004-S1968??S2160-S3748 004 ?? ?? ?? 1037 1038 1039 1040 ?Li??2?????Li????2??分段计价 分段计价 单一票制1元 单一票制1元 S0036-S0203??-S1462-S3414 S3414-S1462??-S0203-S0036 S0600-S2861??-S2645-S1848 S1848-S2645??-S2027-S0600 公汽线路编号对应的公汽线路为： Li%2?0Si

Li%2?0针对问题二：将地铁线路T1分为上下行（原序作为上行，倒序作为下行），这样地铁线路T1为单线，地铁线路T2为环线。将地铁线路T1、T2编号1041~1044存入公汽线路的三维数组中，并作出所有公汽站点和地铁站点的关联矩阵。把公汽—地铁线路信息表做成如下1044?3的结构数组——“公汽—地铁线路信息数组”data_2：

公汽线路编号 票价信息 线路信息 分段计价 S0619-S1914-??S0128-S0710 001 分段计价 S0710-S0128??S1914-S0619 002 分段计价 S3748-S2160??-S1968-S0004 003 分段计价 S0004-S1968??S2160-S3748 004 ?? ?? ?? 1037 1038 1039 1040 1041 1042 1043 1044 分段计价 分段计价 单一票制1元 单一票制1元 单一票制3元 单一票制3元 单一票制3元 / S0036-S0203??-S1462-S3414 S3414-S1462??-S0203-S0036 S0600-S2861??-S2645-S1848 S1848-S2645??-S2027-S0600 D01-D02-D03……-D22-D23 D23-D22-D21……-D02-D01 D24-D25-D26……-D39-D24 /

END 公汽-地铁线路编号对应的公汽-地铁线路为： ?Li??2?????Li????2??Li%2?0Si

Li%2?05.问题一的解答

针对问题一：尽考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 5.1算法的设计

【】

扩散路由算法设计1

设城市的所有公交线路，记为L?(L(1),L(2),...,L(i),...,L(n))其中L(i)表示第i号公交线路的线路名，记为L(i)?(i,ria,...,rij,...,rim)，其中rij表示i路公交车线路上的第j站名称。因此，R?(rij)Route1:A?B?C?D Route2:D?E?F Route3:B?G?H?D

n?m

假设公交存在如下线路(暂只考虑单程)：

?Route1:A?B?C?D???则R??Route2:D?E?F?

?Route3:B?G?H?D???其中每行代表一路公交，任一站的全部后续站为它所能直接到达的站，如图1所示，在连通图中表现为邻结点。路由扩散算法具体的实现是将每一个分组将被发送到除了它进来的那条线路以外的每一条输出线路上。公交网络中可直达的站类似网络中的邻接点，在R中表现为同一行的后继元素。

图一 从A点开始依次可到达的站点

查询从起点X开始，扩散到除了它过来的那个站点以外的每一个站点上，然后判断这些站点中是否包括终点Y，否则再从每个扩散到达的站点继续扩散，逐步扩展以X为基点的网络，一直找到Y为止。扩散深度越大，运算也越复杂，因此深度一般不超过4，即换乘3次。而现实中如果一个城市的公交足够发达，线

路设置较合理的话，极少有换乘超过3次的情况。

很显然，扩散法将会产生大量的重复分组，实际上，需要采取一种办法来抑制扩散过程，否则将有大量无效重复的运算。选择性扩散是很重要的，在换乘时，问题很突出的表现出来。假设线路Routel，Route2和Route3如上，且其它任何线路均不经过C地。考察从B地出发去往F地，易知，需要换乘一次。由于FlB={C，D，G，H)(其中FlB的l表示扩散深度，对应乘车的次数，B为扩散点)。因此C，D，G，H均可能成为换乘地点，但经过C的公交线路集Rc={Routel}，而经过B的线路集RB={Route1，Route3}，Rc?RB??，即换乘无意义。因此扩散只进入D，G和H，到C后应给予抑制，防止进入下一层的扩散。最后，线路集合中经过结点数最少、总权值最小的路径，即X到Y的最佳路径。

算法实现：

Step1:确定起始站X(X?Li?)与终点站Y（Y?Lj?），并将其输入系统中; Step2:由X在Li中开始扩散，逐个查找其对应元素Li?所在行的后续元素：当

Li??Lj?，i=j则Li?为Li线路上的直达站，集合记为F1X={x1(Dx1), x2(Dx2),

x3(Dx3)….}(其中F1X的1为扩散深度，X为扩散点，Dx1为X到x1间隔站数，xm多次存在，只保留Dxm值的最小者)。

Step3:Y是否属于集合F1X中？如果是，则说明X到Y可以直达，不需换乘，直接转到Step6步执行；否则，执行Step4。

Step4：选择集合F1X换乘有意义的站，逐个作为顶点在扩散，访问它们除X以外每个元素。

Step5:Y是否属于集合F2X中？如果是，说明X到Y乘两次（换一次车）可以到达，直接转到Step6步执行；否则，进行进一步扩散到深度为3的顶点（换二次车）。

Step6：将满足条件的线路（可能不止一种）优化并输出结果，结束运算。

算法的具体流程图如下（图5.1）：

图5.1 算法流程图

5.2模型一的建立

为了满足不同查询者的各种不同需求，我们分别以总费用M最小、总耗费时间

T最少以及总换车次数N最少为目标建立最优化模型。

g（1） 以总费用M最少为最优路线的模型：

N?1 目标函数为： minM??Pi?1i

Pi?1,w?1orw?2,i?2s???2,w?2,2?1si?40 ?3,w?2,?41si?（2） 以总耗费时间Tg最少为最优路线的模型： 总时间Tg等于公汽行驶时间与公汽换乘时间之和 目标函数为：minTN?1g?3??i?1si?5?N

（3） 以总换车次数N最少为最优路线的模型： 目标函数为：min

N?Nss

5.2模型一的求解

根据以上算法和前面建立的模型一（不考虑地铁站换乘），用matlab进行编程（程序见附录一）就可以得出不同目标下的最优路线。 （1）以耗时最少为目标的最优路线

起始站S3359到终到站S1828耗时最少为101min； 起始站S1557到终到站S0481耗时最少为106min； 起始站S0971到终到站S0485耗时最少为128min； 起始站S0008到终到站S0073耗时最少为83min； （注：其耗时最少的路线有13条）

起始站S0148到终到站S0485耗时最少为106min； （注：其耗时最少的路线有3条）

起始站S0087到终到站S3676耗时最少为65min； 其耗时最少的最优路线如表5.1所示。 起始站到终点站 最佳线路 车费 时间换车/元 /min 次数 S3359?S1828 3 101 1 L436dL167dS3359????S1784????S1828 S1557?S0481 S0971?S0485 S0008?S0073 S0148?S0485 S0971????S2184????S485 S0008????S2083????S0073 S0087????S3496????S3676 S1557????S1919????S3186????S0481L460uL363uL189dL013dL417d3 3 2 3 106 128 83 106 2 1 1 2 L463dL057uL454uL209d

S0087?S3676 S0148????S0036????S2210????S0485L417dL308uL156u2 65 1 （2）以费用最少为目标的最优路线 起始站S3359到终到站S1828费用最少为3元； 起始站S1557到终到站S0481费用最少为3元； 起始站S0971到终到站S0485费用最少为3元； 起始站S0008到终到站S0073费用最少为2元； 起始站S0148到终到站S0485费用最少为3元； 起始站S0087到终到站S3676费用最少为2元； 其费用最少的最优路线如表5.2所示。 起始站到终点最佳线路 站 S3359?S1828 S1557?S0481S3359????S1784????S1828 L436dL167d车费 /元 3 3 时间换车/min 次数 101 1 106 2 S0971?S0485S1557????S1919????S3186????S0481L460uL363uL189d 3 2 3 2 65 2 128 83 106 1 1 2 S0008?S0073S0971????S2184????S485 L013dL417d S0148?S0485S0008????S2083????S0073 L463dL057u S0087?S3676S0148????S0036????S3332????S0485L417dL308uL156u S0148????S0036????S2210????S0485L417dL308uL156u（3）以换车次数最少为目标的最优路线 起始站S3359到终到站S1828换车次数最少为1次； 起始站S1557到终到站S0481换车次数最少为2次； 起始站S0971到终到站S0485换车次数最少为1次； 起始站S0008到终到站S0073换车次数最少为1次； 起始站S0148到终到站S0485换车次数最少为2次； 起始站S0087到终到站S3676换车次数最少为2次； 其换车次数最少的最优路线如表5.3所示。 起始站到终点最佳线路 站 S3359?S1828 S1557?S0481 S3359????S1784????S1828 S1557????S1919????S3186????S0481L460uL363uL189dL436dL167d车费 /元 3 3 时间换车/min 次数 101 1 112 2

S0971?S0485 S0008?S0073 S0148?S0485 S0971????S2184????S485 L013dL417d3 3 3 128 83 106 1 1 2 S0008????S2083????S0073 L463dL057uS0148????S0036????S3351????S0485L156uL308uL156u 2 65 2 S0087?S3676 S0148????S0036????S2210????S0485L417dL308uL156u 5.3模型的评价

再次考虑换乘次数与时间、车费等因素对最佳线路的影响：

对于所给六组数据，分别以时间和车费为优化目标的最佳线路完全相同。这说明省时和省钱原则在公汽线路选择上的一致性。

换乘一次的方案（如果存在的话）相比较换乘两次的方案，所用时间普遍较多、而所用费用却稍微偏低。这说明对于一个线路和站点很多、较发达的公交系统来说，换乘次数增加只是感觉上比较麻烦，而实际上由于及时调整了线路，整体上可以节约大量的时间，当然相对应的，由于多乘了若干次车，车费就会增加。但总体来说时间上的差异是主要的。

6.问题二的解答

问题二：同时考虑公汽与地铁线路，解决以上问题。 6.1模型二的建立

为了满足不同查询者的各种不同需求，我们分别以总费用M最小、总耗费时间

T最少以及总换车次数N最少为目标建立最优化模型。

g（1）以总费用M最少为最优路线的模型：

N?1 目标函数为： minM??Pi?1i

Pi?1,w?1orw?2,i?20s???2,w?2,2?1si?40 ?3,w?3orw?2s,i?41?（2） 以总耗费时间Tg最少为最优路线的模型：

总时间Tg等于公汽和地铁的行驶时间与公汽换乘时间和地铁换乘时间之和 目标函数为：

minT

Nss?Nds?1g?3??i?1Ndd?Nsd?1si?2.5??i?1ti?5?Nss?4?Ndd?7?Nds?6?Nsd（3） 以总换车次数N最少为最优路线的模型： 目标函数为：minN?Nss?N?Nddds?Nsd

6.2模型二的求解

根据以上算法和前面建立的模型一（不考虑地铁站换乘），用matlab进行编程（程序见附录一）就可以得出不同目标下的最优路线。 （1）以耗时最少为目标的最优路线

起始站S3359到终到站S1828耗时最少为73min； 起始站S1557到终到站S0481耗时最少为106min； 起始站S0971到终到站S0485耗时最少为101min； 起始站S0008到终到站S0073耗时最少为70min； 起始站S0148到终到站S0485耗时最少为92.5min； 起始站S0087到终到站S3676耗时最少为38min； 其耗时最少的最优路线如表5.1所示。 起始站到终点站 最佳线路 车费 时间换车/元 /min 次数 S3359?S1828 3 73 2 L015dL027S3359????S2903???? S1784????S1828S1557?S0481 L167dS1557????S1919????S3186????S0481L460L084dL189d3 5 3 5 3 106 2 S0971?S0485 S097????S0567??????S0466????S0485L051uL094uD01???D21T1101 2 S0008?S0073 S0008????S1383????S2184????S0073L345uL043dL29670 2 S0148?S0485 S0148????S1487??????S0466????S0485L051uL024D02???D21T192.5 2 S0087?S3676 S0087??????S3676 D27????D36T238 0 （2）以费用最少为目标的最优路线 起始站S3359到终到站S1828费用最少为3元； 起始站S1557到终到站S0481费用最少为3元； 起始站S0971到终到站S0485费用最少为3元； 起始站S0008到终到站S0073费用最少为2元； 起始站S0148到终到站S0485费用最少为5元； 起始站S0087到终到站S3676费用最少为1元；

其费用最少的最优路线如表5.2所示。 起始站到终点最佳线路 站 S3359?S1828 S1557?S0481S3359????S1748????S1828 L436dL167d车费 /元 3 3 时间换车/min 次数 101 1 106 2 S0971?S0485S1557????S1919????S3186????S0481L460L084dL189d 3 2 5 1 46 0 128 83 92.5 1 1 2 S0008?S0073S097????S2184????S0485 L013dL417d S0148?S0485S0008????S0400????S0073 L159dL474 S0087?S3676S0148????S1487??????S0466????S0485L051uL024D02???D21T1 S0087???S0088????S0427???S3676L231 （3）以换车次数最少为目标的最优路线 起始站S3359到终到站S1828换车次数最少为1次； 起始站S1557到终到站S0481换车次数最少为2次； 起始站S0971到终到站S0485换车次数最少为1次； 起始站S0008到终到站S0073换车次数最少为1次； 起始站S0148到终到站S0485换车次数最少为2次； 起始站S0087到终到站S3676换车次数最少为0次； 其换车次数最少的最优路线如表5.3所示。

起始站到终点最佳线路 站 S3359?S1828 S1557?S0481 S3359????S1748????S1828 L436dL167d车费 /元 3 3 时间换车/min 次数 101 1 106 2 S1557????S1919????S3186????S0481L460L084dL189d 3 2 5 3 38 0 128 83 92.5 1 1 2 S0971?S0485 S0008?S0073 S0148?S0485 S097????S2184????S0485 S0008????S0400????S0073 L159dL474L013dL417dS0148????S1487??????S0466????S0485L051uL024D02???D21T1S0087?S3676 S0087??????S3676 D27????D36T2

6.3模型二的评价

7.问题三的解答

问题三：假设知道所有站点之间的步行时间，建立一个任意两站点之间线路选择问题的数学模型。 7.1模型三的建立

在该问中，我们可以通过步行，从一个车站走到另一个车站，从而找到更省时间或更方便的乘车线路。

在问题一和问题二中，只能由本车站通过地铁站换乘。而在我们知道了任意两站之间的步行时间后，从理论上讲所有车站之间可以通过步行来换乘车线路。但从实际出发，人的步行距离和时间是有可接受限度的，即不能走很长的距离和时间。

因此我们要对步行时间加以限制，假设步行的最大时间限制为tm

假设所有相邻公汽站点的距离相等，乘客在相邻公汽站点之间的步行时间为

tB，则步行的站点个数最多为

?tm?

???tB?假设所有相邻地铁站点的距离相等，乘客在相邻地铁站点之间的步行时间为

?tm?tD，则步行的站点个数最多为??

?tD?是否选择步行方式的函数：

???? foo?t?????1?tm?fs????tB?i0?tm?fs????tB?iN?1???? foo?t?????1?tm?fd????tD?i

0?tm?fd????tD?i（1）以总费用M最少为最优路线的模型： 目标函数为： minM??Pi?1i?(1?foot)?3?N

sd

Pi?1,w?1orw?2,i?2s???2,w?2,2?1si?40 ?3,w?2,?41si?（2） 以总耗费时间Tg最少为最优路线的模型：

附录二

function vvdt(start,aim) [fee d C]=data(); for i=1:39

if find(C{i}==start) start=10000+start; end

if find(C{i}==aim) aim=10000+aim; end end

if numel(find(d==start))==0

fprintf('The path cannot be found!'); else

[row col]=find(d==start); for i=1:numel(row) [rows

cols(i,1:numel(find(d(row(i),:)==start)))]=find(d(row(i),:)==start); end

F=creatF(start,row,cols,d); end

if ismember(aim,F(:,2)) num=find(F(:,2)==aim); line=round(F(num,3)-0.5); long=F(num,1)-1; time=3*F(num,1);

value=val(0,F(num,:),fee); updown=ud(F(num,3));

n={start,updown,line,aim,long,time,value}; print(n); else

size_F=size(F); cha=1; Fc={}; n={};

for i=1:size_F(1)

[row1 col1]=find(d==F(i,2)); [rows cols]=find(d==start); row1=setdiff(row1,rows); if numel(row1)>0 for j=1:numel(row1)

col1(j,1:numel(find(d(row1(j),:)==F(i,2))))=find(d(row1(j),:)==F(i,2));

end

F1=creatF(F(i,2),row1,col1,d); Fc=[Fc F1];

if ismember(aim,F1(:,2)) num1=find(F1(:,2)==aim); line1=round(F(i,3)-0.5); mid1=F(i,2); long1=F(i,1)-1;

line2=round(F1(num1,3)-0.5); long2=F1(num1,1)-1;

time=3*(F(i,1)+F1(num1,1))+5; value=val(0,F(i,:),fee);

value=val(value,F1(num1,:),fee); updown1=ud(F(i,3)); updown2=ud(F1(num1,3));

n(cha,:)={start,updown1,line1,mid1,long1,updown2,line2,aim,long2,time,value};

cha=cha+1; end end end if cha==1

fprintf('The path with once chang cannot be found!\\n'); sizec=size(Fc); kind=1;

for j=1:sizec(2) siz=size(Fc{j}); Fj=Fc{j}; for k=1:siz(1)

[row2 col2]=find(d==Fj(k,2)); [rows cols]=find(d==Fj(1,2)); [row col]=find(d==start); row2=setdiff(row2,rows); row2=setdiff(row2,row); if numel(row2)>0 for l=1:numel(row2)

col2(l,1:2)=find(d(row2(l),:)==Fj(k,2)); end

F2=creatF(Fj(k,2),row2,col2,d); if ismember(aim,F2(:,2)) num2=find(F2(:,2)==aim); num1=find(Fj(:,2)==F2(1,2)); num=find(F(:,2)==Fj(1,2));

line1=round(F(num,3)-0.5); line2=round(Fj(num1,3)-0.5); line3=round(F2(num2,3)-0.5); mid1=F(num,2); mid2=Fj(num1,2); long1=F(num,1)-1; long2=Fj(num1,1)-1; long3=F2(num2,1)-1;

time=3*(long1+long2+long3+3)+10; value=val(0,F(num,:),fee); value=val(value,Fj(num1,:),fee); value=val(value,F2(num2,:),fee); updown1=ud(F(num,3)); updown2=ud(Fj(num1,3)); updown3=ud(F2(num2,3));

n(kind,:)={start,updown1,line1,mid1,long1,updown2,line2,mid2,long2,updown3,line3,aim,long3,time,value};

kind=kind+1; end end end end if kind==1

fprintf('The path with twice change cannot be found!\\n');; else

xlswrite('C:\\Users\\Administrator\\Desktop\\all',n,'Sheet2','A1'); minn=n{1,14}; for i=1:kind-1 if n{i,14}

for i=1:kind-1 if n{i,14}==minn print(n(i,:)); end end end else

xlswrite('C:\\Users\\Administrator\\Desktop\\all',n,'Sheet1','A1'); minn=n{1,10};

for i=1:cha-1 if n{i,10}

for i=1:cha-1 if n{i,10}==minn print(n(i,:)); end end end end return

function F=creatF(start,rows,cols,d) F=[0 start 0]; n=numel(rows); for j=1:n

maxcol=numel(nonzeros(d(rows(j),:))); cn=numel(cols(j,:)); if cn>1

for k=1:cn-1

for i=cols(j,k)+1:cols(j,k+1)-1

x=[i-cols(j,k) d(rows(j),i) rows(j)/2+0.5]; F=[F;x]; end end

for i=cols(j,cn)+1:maxcol

x=[i-cols(j,cn) d(rows(j),i) rows(j)/2+0.5]; F=[F;x]; end else

for k=cols(j)+1:maxcol

x=[k-cols(j) d(rows(j),k) rows(j)/2+0.5]; F=[F;x]; end end end

size_F=size(F); f=unique(F(:,2)); size_f=size(f); j=0; re=0;

for i=1:size_F(1) if ismember(F(i,2),f)

f(find(f==F(i,2)))=[]; else

if ~ismember(F(i,2),re) j=j+1; re(j)=F(i,2); end end end others=[]; for k=1:j

[row col]=find(F(:,2)==re(k)); [minre,where]=min(F(row,1)); where=row(where);

other=setdiff(row',where); others=[others other]; end

F(others,:)=[]; return

function value=val(vl,F,fee)

te=importdata('d:\\?òμ???μμ\\×à??\\fee.mat'); if strcmp(fee{round(F(3)-0.5)},'3?a') value=vl+1; else

if strcmp(fee{round(F(3)-0.5)},'μ￥ò??±??1?a?￡')|F(1)<=20 value=vl+1; else

if F(1)>20&F(1)<=40 value=vl+2; else

value=vl+3; end end end return

function updown=ud(F) if round(F)==F updown='é?'; else

updown='??'; end return

function print(n) if numel(n)==7

fprintf('?ú?éò?′ó%d??3?×?%sDD%d?·1????±μ?%d??￡??Dí??-1y%d??3μ??￡?3?3μê±??%d·??ó￡????¨·?%d?a￡?×￡?ú3?3μó??ì￡?',n{1},n{2},n{3},n{4},n{5},n{6},n{7}); end

if numel(n)==11

fprintf('?ú?éò?′ó%d??3?×?%sDD%d?·1???μ?%d??￡??Dí??-1y%d??3μ??,′ó′???×a3?%sDD%d?·1????±μ?%d??,?Dí??-1y%d??3μ??￡?3?3μê±??%d·??ó￡????¨·?%d?a￡?×￡?ú3?3μó??ì￡?\\n',n{1},n{2},n{3},n{4},n{5},n{6},n{7},n{8},n{9},n{10},n{11}); end

if numel(n)==15

fprintf('?ú?éò?′ó%d??3?%sDD%d?·μ?%d??￡?í??-%d??3μ??,×a3?%sDD%d?·μ?%d??,í??-%d??3μ??￡??ù×a3?%sDD%d?·?±μ?%d??,í??-%d??3μ??￡?3?3μê±??%d·??ó￡????¨·?%d?a￡?×￡?ú3?3μó??ì￡?\\n',n{1},n{2},n{3},n{4},n{5},n{6},n{7},n{8},n{9},n{10},n{11},n{12},n{13},n{14},n{15}); end return

function [fee,d,Cit]=data()

data=importdata('C:\\Users\\Administrator\\Desktop\\data.mat');%???tdata.matóéè?1¤μ?è??°1.1 1??????·D??￠.txt?±???tμ?MATLAB?D2úéú?￡ i=1;

while ~strcmp(data{i},'END') for j=1:4

ls{(i+3)/4,j}=data{i-1+j}; end i=i+4; end

fee=ls(:,2); siz=size(ls); for i=1:siz(1) a=ls{i,3}; b='0';

for j=1:numel(a) if

~strcmp(a(j),'S')&~strcmp(a(j),'-')&~strcmp(a(j),'é?')&~strcmp(a(j),'DD')&~strcmp(a(j),'￡o')&~strcmp(a(j),'?·') b=strcat(b,a(j)); end end

b=b(2:numel(b)); for k=1:numel(b)/4

c(i,k)=str2num(b(4*(k-1)+1:4*k)); end end

for i=1:siz(1) a=ls{i,3}; a1=ls{i,4}; b1='';

if strcmp(a1,'')&strcmp(a(1),'?·') c1(i,1)=0; end

if strcmp(a1,'')&strcmp(a(1),'S') for j=1:numel(a)

if ~strcmp(a(j),'S')&~strcmp(a(j),'-') b1=strcat(b1,a(j)); end end l=1;

for k=numel(b1)/4:-1:1

c1(i,l)=str2num(b1(4*(k-1)+1:4*k)); l=l+1; end end b1='';

if ~strcmp(a1,'') for j=1:numel(a1) if

~strcmp(a1(j),'S')&~strcmp(a1(j),'-')&~strcmp(a1(j),'??')&~strcmp(a1(j),'DD')&~strcmp(a1(j),'￡o') b1=strcat(b1,a1(j)); end end

for k=1:numel(b1)/4

c1(i,k)=str2num(b1(4*(k-1)+1:4*k)); end end end j=1;

for i=1:siz(1)

d(j,1:numel(c(i,:)))=c(i,:); d(j+1,1:numel(c1(i,:)))=c1(i,:); bh(j,1)=i; j=j+2; end

d(1041,1:23)=[10001 10002 10003 10004 10005 10006 10007

10008 10009 10010 10011 10012 10013 10014 10015 10016 10017 10018 10019 10020 10021 10022 10023]; for i=1:numel(d(1041,:))

d(1042,i)=d(numel(d(1041,:))-i+1); end

d(1043,1:19)=[10024 10025 10026 10012 10027 10028 10029 10030 10031 10032 10018 10033 10034 10035 10036 10037 10038 10039 10024]; Cit{1}=[0567, 0042, 0025]; Cit{2}=[ 1487]; Cit{3}=[ 0303, 0302]; Cit{4}=[ 0566];

Cit{5}=[ 0436, 0438, 0437, 0435]; Cit{6}=[ 0392, 0394, 0393, 0391]; Cit{7}=[ 0386, 0388, 0387, 0385];

Cit{8}=[ 3068, 0617, 0619, 0618, 0616]; Cit{9}=[ 1279];

Cit{10}=[ 2057, 0721, 0722, 0720]; Cit{11}=[ 0070, 2361, 3721]; Cit{12}=[ 0609, 0608];

Cit{13}=[ 2633, 0399, 0401, 0400]; Cit{14}=[ 3321, 2535, 2464]; Cit{15}=[ 3329, 2534]; Cit{16}=[ 3506, 0167, 0168];

Cit{17}=[ 0237, 0239, 0238, 0236, 0540]; Cit{18}=[ 0668]; Cit{19}=[ 0180, 0181];

Cit{20}=[ 2079, 2933, 1919, 1921, 1920]; Cit{21}=[ 0465, 0467, 0466, 0464]; Cit{22}=[ 3457]; Cit{23}=[ 2512]; Cit{24}=[ 0537, 3580];

Cit{25}=[ 0526, 0528, 0527, 0525]; Cit{26}=[ 3045, 0605, 0607]; Cit{27}=[ 0087, 0088, 0086]; Cit{28}=[ 0855, 0856, 0854, 0857]; Cit{29}=[ 0631, 0632, 0630]; Cit{30}=[ 3874, 1426, 1427]; Cit{31}=[ 0211, 0539, 0541, 0540]; Cit{32}=[ 0978, 0497, 0498]; Cit{33}=[ 1894, 1896, 1895]; Cit{34}=[ 1104, 0576, 0578, 0577]; Cit{35}=[ 3010, 0583, 0582]; Cit{36}=[ 3676, 0427, 0061, 0060];

Cit{37}=[ 1961, 2817, 0455, 0456]; Cit{38}=[ 3262, 0622]; Cit{39}=[ 1956, 0289, 0291]; for i=1:39

for j=1:numel(Cit{i}) c=Cit{i};

[rows col]=find(d==c(j)); for k=1:numel(rows)

[row cols(k,1:2)]=find(d(rows(k),:)==c(j)); end

for k=1:numel(rows)

d(rows(k),cols(k,:))=10000+i; end end end

fee{1041}='3?a'; fee{1042}='3?a'; fee{1043}='3?a'; return

本文来源：https://www.bwwdw.com/article/0285.html