公交查询系统的最佳乘车方案研究与设计

公交查询系统的最佳乘车方案研究与设计

摘要

本文要求设计一个公交线路计算机自助查询系统，针对不同需求的出行者推荐相应的最佳路线。这是一个多目标决策的网络优化问题，并且随着问题的深入逐层递进，我们建立了三个多目标优化模型解决此问题。

针对问题一，将三种不同的公汽线路抽象化，建立站点间直达线路信息存储元胞结构。调查分析得出，尽管乘客对公交线路的需求侧重点各有不同，但都包括乘车次数少、时间短、费用少和拥挤程度低，以前三个量为目标，拥挤程度为约束，建立多目标整数规划模型，根据多目标分层序列法，出于对乘客不同需求的考虑，采用3种对每个需求侧重程度不同的策略，利用局部搜索算法，求出6条线路在3种不同策略下的最优线路(最佳线路见表(1)至(3))。

针对问题二，同时考虑公汽与地铁线路，将地铁站点与邻接的公汽站点抽象为同一新站点，重新建立站点间直达线路信息存储元胞结构。在问题一的基础上增加考虑地铁站对费用、换乘时间和行驶时间的影响，仍然以乘客对线路的三种主要需求为目标，以拥挤程度为约束，建立多目标整数规划模型，利用MATLAB软件编程求解得到3种不同策略下的最优路线(最佳线路见表(4)至(6))。

针对问题三，增加考虑步行的出行方式，在公汽站点间当站点数目不超过2时，可以以步行代替，从而减少换乘次数。在此基础上，按换乘次数少、时间短、费用少的顺寻建立多目标整数规划模型，利用MATLAB软件编程求解得到相应的最佳路线。以线路S1557→S0481和S0148→S0485为例，最佳路线分别为： S1557→步行2站→S2143-L084-S1919-L043-S3077-L273，需3元，92分钟；S0148→步行1站→S3182-L308-S36-L157-S0722→步行1站→S0485，需2元，69分钟。

关键字 元胞结构 多目标整数规划 多目标分层序列法 局部搜索算法

1.问题重述

1.1问题背景

传承华夏五千年的文明，梦圆十三亿华夏儿女的畅想，我国人民翘首企盼的第29届奥运会明年8月将在北京举行!在观看奥运的众多方式之中，现场观看无疑是最激动人心的。届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。为了迎接2008年奥运会，北京公交做了充分的准备，首都的公交车大都焕然一新，增强了交通的安全性和舒适性，公交线路已达800条以上，使得公众的出行更加通畅、便利。但同时也面临多条线路的选择问题。为满足公众查询公交线路的选择问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 1.2待解决的问题

这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决的问题有：

1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站到终到站最佳路线（要有清晰的评价说明）。

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

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

2.问题假设

假设一：各路线公交车发车频度相同； 假设二：相邻站点间平均行驶时间一定；

假设三：公交运行顺畅：无交通阻塞、无车辆故障、无道路交通事故等意外情况； 假设四：公交准点到达，不考虑红绿灯等待时间；

假设五：乘客在起始站时不考虑拥挤程度，只在转乘时考虑拥挤程度； 假设六：乘客到起始站乘车时，不考虑等车时间；

假设七：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，在此换乘

过程中不考虑换乘时间和费用。

3.符号说明

LijVijPijSij 站点之间的最小换乘次数 实际换车次数 从站点i到站点j的费用Pij 表示站点i到站点j经过的站点数目 表示从起始站startp到终点站endp的站点数 表示从站点i上车时站点i距离startp的站点数 nijaijZij?A 表示从起始站i到终点站?j公汽换乘公汽的次数 B 表示从起始站i到终点站j公汽换乘地铁的次数 ZijC 表示从起始站i到终点站j地铁换乘公汽的次数 ZijDZij表示从起始站i?到终点站j地铁换乘地铁的次数 ? tij T 站点i到站点j的步行时间 邻近站点的时间上确界 任意两个邻近站点平均步行时间 表示邻接公汽站点间的步行时间 t0 t 4.问题分析

这是一个多目标决策的网络优化问题。公交查询系统需要满足查询者各种不同需求，给出最优方案，这是我们建立模型的根本出发点，有关问题的求解随着规模扩大将逐层深入。

对于问题一，题目给出的公汽线路主要分为上下行线、原路折回线及环行线，线路不同，选择不同，故对每种线路需要进行抽象化处理。站点较多，信息量较多，需要选择合适的存储方法存储数据，存储题中的线路名、车号和时间。解决这些问题后，就要对乘客的出行需求进行调查，看看乘客出行时主要考虑哪些因素，根据调查结果可以选定主要的需求建立多目标规划模型。本题数据量较多，一般的算法可能不能处理，所以要探索合适的算法，然后用MATLAB软件编程求解，可以求出不同需求的出行者相应的公交路线。

对于问题二，在问题一的基础上更进一步探讨同时考虑公汽和地铁线路的情况。我们同样需要对地铁线路进行抽象化处理，基于假设七，同一地铁站与邻接的公汽站可以进行归一化处理，因为这些站点间的换成无需支付地铁费并且时间可以忽略不计，还要将地铁站相关信息和公交站相关信息合理存储。根据问题一中的乘客需求，同样建立多目标规划模型，但由于有了地铁这种出行方式，在乘车费用与车辆换乘方面有所不同。设计合适的算法，编程求解得到不同需求的乘客相应的最优路线。

对于问题三，该问在问题二的基础上增加考虑步行对最优路线选取带来的影响，可以把步行作为另一种交通工具进行考虑。根据实际情况对步行相关信息做出合理的假设，由于步行这种出行方式不花费时间，对换乘次数以及换乘方式都没有影响，只改变出行时间。所以在问题三中，我们对出行时间优先考虑，再考虑换乘次数和乘车费用，同样建立多目标优化模型，运用MATLAB编程求解得到任意站点间的最佳路线。

5.问题一的解答

问题一仅考虑公汽线路，我们建立了模型一进行求解。 5.1问题一的数据处理 5.1.1三种公汽线路的处理

根据题中信息，我们知道公汽线路分三种，下面将这三种线路进行数据处理： ? 下行线是上行线原路返回

1 2 3 4 5 6

这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列,只是线路的方向不同； ? 上行线与下行线的站点名不完全相同

1

2

3

4

5

6

7

8

这种线路与下行线是上行线的原路返回不同，下行线与上行线经过的站点不完全相同，但是起始站和终点站相同； ? 线路为环形线

对环形线路的站点进行分析，把一个环形拉成一条直线，以该直线的终点为对称点进行翻折，将终点左边的直线对称到右边，形成该直线的延长线，如下：

2

1 3 1 2 3 4 3 2 1 4

这种环形线原有的路线包括：12,13,14,23,24,34,21,31,41,32,42, 43，抽象成直线后的路线有：12,13,14,23,24,34,43,42,41,32,31,21，与原路线相同，所以这种抽象方法是合理的。 5.1.2建立“公汽直达数据库DM”

从实际出发，结合公众出行心理，公汽线路选择应优先考虑两站点之间是否有直达车，那么在查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。

在数据导入的过程中，首先考虑直接从文本文件导入MATLAB中，但是本题共有3957 个站点, 520条公交线路,若每个队列的每个数据都是用双精度进行存储，那么内存占用大，实际输出时运行时间长，考虑到所存储的信息量包括公汽号、公交站点、乘车时间以及乘车费用等多个因素，所以采用MATLAB中的元胞数组建立公汽直达数据库DM进行存储(建立数据库DM的代码详见附录一)，节省存储空间。 5.2模型一的准备

5.2.1公交乘客的出行需求

公交线网优化的最终目的是尽最大可能满足乘客的出行需求。建立合理的线网优化模型，重要的一点是通过对居民出行心理、行为进行调查研究，以确定模型的优化目标和约束条件。居民公交出行需求，是居民对公交服务的期望。

由于我们设计出来的系统需要满足查询者不同的需求，要建立合适的出行路线选择模型，必须对公交乘客选择出行路径时需要考虑的因素进行调查分析。我们对随州市居民的出行需求进行调查结果，用excel画出居民对出行时的费用、乘车时间、乘换次数、步行时间以及拥挤程度的统计结果如下图(1)：

图(1)：居民出行需求结果的统计

我们可以看到，出行者对不同因素的看重比例是不同的，该市居民出行需求对于北京这样的大城市也同样适用。由于一般情况下路程长短和所用时间是密切联系的，乘客关注路程也是为了节约时间，所以问题中已经将路程的相关信息转化成为时间了，即只需考虑时间最短。因此我们的模型中对公交网络的优化需要考虑四个主要优化目标：换乘次数最少，时间最短，费用最少，拥挤程度最低。 5.2.2换乘次数的抽象

根据公交线路的设计，尽管起始站和终点站位置相同，也可能有多种乘车方式，这些乘车方式中可能是直达的，也可能要转乘一次，也可能需转乘两次，或三次及三次以上，以startp表示起始站，endp表示终点站，那么某乘客从startp到endp的几种乘车方式如下： ? 直达的示意图

? 换乘一次的示意图

? 换乘两次示意图

startp 中转站一 中转站二 endp

如果公交线路设计合理的话，那么几乎所有的站点均可以在转成两次以内达目的地，而且乘换次数过多，容易使乘客产生烦躁情绪，需要更长的时间和更多的费用；因此在设计算法时，只搜索直达、换乘一次和换乘2次的乘车方案。 5.2.3计算机系统自主查询路线的流程

通过上述调查显示的统计结果得知，乘客乘车都会考虑换乘次数，时间，费用以及拥挤程度的问题，但是不同的乘客对这些需求考虑的先后次序不同，比如：度假的乘客，一般会首先考虑乘车时间；所带行李较多的乘客，一般会首先考虑拥挤程度和换乘次数等。

一般情况下，人们往往会选择直达，也就说如果两站点之间有直达车辆，乘客会选择直达。由于直达的车辆不止一辆，可以根据不同乘客的需求，选择相应的最优方案。当没有直达车辆时，乘客可以根据自己不同的需求，选择属于自己的最优路线。

根据上述分析，我们构建的公交线路选择问题的自主查询计算机系统应该考虑不同乘客对不同需求的重视程度，根据上述分析，公交线路自主查询系统的流程如下图(2)：

图(2):公交线路自主查询系统的流程图

5.3模型一的建立

我们要建立如图(2)所示的公交线路自主查询系统，就要对不同行程需求的乘客推荐相应的最佳路线，根据实际情况可以确定三个目标，分别为：换乘次数，乘车时间，乘车费用。

结合数据处理中的实际情况，不同的乘客对不同需求的重视程度不同，所以对于不同的乘客，我们要给出相应的最佳路线，从三个方面综合考虑，分别给出优先考虑乘换次数以及优先考虑乘车时间的最优推荐路线。我们考虑运用多目标优化设计的分层序列法建立模型，进行求解，在此引入多目标分层序列法。

多目标分层序列法：将k个目标函数按重要程度排序k1,k2,?,kn，其中k1的优先级最高，应该首先得到满足，其次是k2，直到得出满足所有的目标函数的解，或是此时的解只有一个。

根据实际情况，可以根据多目标优化设计的分层序列法对我们建立的三个目标函数的顺序进行调整，得到不同乘客所对应的不同的最佳路线。当满足这些目标的路线不止一条时，我们选取离始发站最近的解，因为离始发站越近，公交的拥挤程度相对越小。

当以某个目标函数作为第k1个目标函数，即决策变量时，只需将该目标函数的顺序进行调整，使之成为第k1个目标函数。当目标函数有三个时，排序后共有六种可能的情形，但不是每种情形都要考虑。根据调查结果，我们确定了乘客出行时考虑较多的三种类型，在此分别称为策略一、策略二和策略三。

策略一：按换乘次数最少、乘车时间最短、乘车费用最少的顺序考虑； 策略二：按乘车时间最短、换乘次数最少、乘车费用最小的顺序考虑； 策略三：按换乘次数最小、乘车费用最少、乘车时间最短的顺序考虑。 5.3.1确定目标函数

在建立的公汽直达数据库DM的基础上，分别确定三个目标函数。 Target one ：乘换次数最少

设Lij表示站点之间的换乘次数，根据公交线路的设计，尽管起始站和终点站位置相同，也可能有多种乘车方式，这些乘车方式中可能是直达的，也可能要换乘一次，也可能需换乘两次。将换乘次数作为第k1个目标，希望在满足该要求的基础上再考虑其它方案，即在建立的公汽直达数据库DM中进行搜索，如果有直达方案，仅在直达方案中推荐满足其它目标函数的最佳路线。那么目标一要求Lij最小，即 MinLij。

Target two ：乘车时间最少

通过分析我们知道，乘车中的时间包括：行驶时间和换乘时间。基于假设六，乘客到起始站乘车时，不考虑等车时间。而车辆换乘的过程实际上包括换乘时间和等车时间。公汽换公汽时间固定是5 分钟，则换乘时间(包括换乘过程中的等车时间)为：5Lij

设实际换车次数为Vij，那么实际乘车的数量为Vij?1，所以行驶总时间为：

i,j?E?t?Vijij?1?，其中Lij?Vij?2

i,j?E那么乘车时间为：

?t?Vijij?1??5Lij

ijij即第二个目标函数为： Mini,j?E?t?V?1??5Lij

Target three ：乘车费用最少

乘车费用分为单一票价与分段计价两种方式，用qij表示从站点i到站点

?1j的计费方式，那么qij??，其中1表示单一票价，2表示分段计费；又由于分

?2段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元，可设Sij 表示站点i到站点j经过的站点数目，那么从站点i到站点j的费用Pij为：

?1,??1,?Pij???2,???3,?q?q?qijijij?1??2,1?Sij?20??2,20?Sij?40?ij

?qi,j?E?2,Sij?40?ij那么行程总费用为：

?P?Vij?1?

ijij从而得到第三个目标函数为： Mini,j?E?P?V?1?

综上我们建立的多目标整数规划目标函数为：

MinMinMin5.3.2确定约束条件

Liji,j?E?t?Vijijij?1??5Lij ?1?i,j?E?P?Vij模型中我们仅考虑换乘2次的路线，所以实际换车次数Vij应该大于换车次数的最小值，但是小于2，即Lij?Vij?2；当确定的最佳路线的换乘次数、乘车时间和乘车费用相同时，考虑以拥挤程度的高低来确定最终的最佳路线。

拥挤程度：实际生活中，当离起始站点越近时，车上的乘客越少。设nij表示从起始站startp到终点站endp的站点数目，aij表示从站点i上车时站点i距离

startp的站点数，那么aij的最小值越接近nij表示拥挤程度越高，aij的最小值越

接近0表示拥挤程度越低。所以0?Minaij?nij。 所以模型一的约束条件为：

?0?Minaij?nij? ?Lij?Vij?2??i,j?E5.3.3确定模型一

综上所述，可以确定多目标整数规划模型为：

MinMinMinLiji,j?E?t?Vijijij?1??5Lij ?1?i,j?E?P?Vij?0?Minaij?nij? s.t?Lij?Vij?2??i,j?E5.4模型一的求解 5.4.1算法设计

基于局部搜索和优化枚举的算法，我们充分利用公交网络自身的特点，采用局部搜索思想，对三种不同的策略进行分类，在每种策略中求出最优解。首先根据乘客输入的起始点和终点，分别对存储的数据进行搜索，筛选出可行的线路；然后根据三种不同的策略在选出的可行路线中，选出每种策略的最优方案。具体算法实现过程如下：

1) 输入起始点i，终点j以及选择的策略种类k，k?1,2,3；

2) 搜索从站点i可乘坐公交线路的集合R(i)，在终点可乘坐公交线路的集合

R(j)；

3) 判断是否直达；

? R(i)或R(j)是空集，说明两站之间没有线路可以到达 ? R(i)?R(j)?0，说明两站之间不能直达，转入4) ? R(i)?R(j)?0，说明两站之间可以直达，转入8)

4) 以起始点搜索直达下有站点的集合M，以终点搜索直达上游站点集合N； 5) 判断是否是一次换车

? M?N?0，存在一次换车就可到达，转入8) ? M?N?0，不存在一次换车就可到达，转入6)

(注：M?N?0中，可能包含直达路线，要筛选剔出) 6) 扫描是否?m?M,?n?N，若存在?m,n?，则可以直达，若不存在，则将点

?i,m?,?n,j?加入集合F，集合F表示需要换车两次；

7) 判断是否需要两次换车

? 集合F不是空集，转入8) ? 集合F是空集，不考虑

8) 基于三种不同的策略，推荐最优乘车线路 5.4.2求解结果

根据上面的算法思想，可以运用MATLAB软件进行编程(代码详见附录二)，由于我们采用的是多目标分层序列整数规划模型，所以根据确定的三种不同的策略，可以得到相应策略的最佳路线，表(1)至表(3)分别给出了三种不同策略下题中要求解的六条线路的最佳路线。

表(1)：策略一中六条线路的最佳路线

线路 S3359-S1828 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 换乘次数 时间 花费 1 2 1 1 2 1 101 76 128 83 73 65 3 3 3 2 3 2 坐车路线 L436-S1784-L217 L084-S1919-L043-S3077-L273 L013-S2184-L417 L355-S2263-L345 L024-S1234-L505-S516- L104 L454-S3496-L209 距离始发站 17 28,20 14 11 16,23 6 (注：策略一按换乘次数、乘车时间、乘车费用的顺序进行考虑)

表(2)：策略二中六条线路的最佳路线

线路 S3359-S1828 时间 换乘次数 花费 73 2 3 坐车路线 L324-S2027-L201-S458 -L041 距离始发站 7,10 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 76 64 37 73 46 2 2 2 2 2 3 3 3 3 3 L084-S1919-L043-S3077-L273 L013-S345-L505-S516-L104 L150-S1381-L290-S3645-L020 L024-S1234-L505-S516- L104 L021-S88-L231-S427- L097 28,20 17,23 31,17 16,23 14,3 (注：策略二按乘车时间、换乘次数、乘车费用的顺序进行考虑)

表(3)：策略三中六条线路的最佳路线

线路 S3359-S1828 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 换车次数 花费 时间 1 2 1 1 2 1 3 3 3 2 3 2 101 76 128 83 73 65 坐车路线 L436-S1784-L217 L084-S1919-L043-S3077-L273 L013-S2184-L417 L355-S2263-L345 L024-S1234-L505-S516- L104 L454-S3496-L209 距离始发站 17 28,20 14 11 16,23 6 (注：策略三按换乘次数、乘车时间、乘车费用的顺序进行考虑)

5.5模型一的结果分析

比较表(1)至表(3)的结果，可以看到策略一和策略三的结果完全一样，这主要是因为乘坐公交的费用变化不显著，每经过20个站点才增加一元钱，这样一来在某个范围内，乘坐公交的费用相差不会很远，所以对路线的选取不会有太大影响。我们纵向比较三种策略的时间，将三种策略下的时间变化作图如下：

三条13012011010090策略一六条线路时间的变化策略三六条线路时间的变化时间807060策略二六条线路时间的变化50403011.522.533.54六条线路4.555.56

图(3)：三种策略的时间比较

由图可以看出，优先考虑时间和优先考虑换乘次数时，推荐的最优路线在乘车时间上的波动很大，说明我们的策略分配是合理的。对于比较重视时间的乘客，优先考虑时间，就会节约很多时间；对于不赶时间，觉得换乘麻烦而重视换乘次

数的乘客，相对来说所需时间要多。以第三条线路S0971-S0485为例，优先考虑乘车时间时，需要37分钟，而优先考虑乘换次数时，需要128分钟，即优先考虑时间比优先考虑乘换次数在这条线路上可以节约91分钟。所以针对不同的乘车需求，我们确定了不同的乘车策略是非常有必要的。

6.问题二的解答

问题二同时考虑公汽与地铁线路，我们建立了模型二进行求解。 6.1问题二的数据处理 6.1.1对两条地铁线路的处理

基于对三种公汽线路路线的抽象方法，用相同的方法对两地铁线路T1,T2进行抽象化处理。

T1:返回时沿原路返回，这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列,只是线路的方向不同； T2:环行线路，根据对公汽线路中环形线路的抽象方法把地铁线路中的环形线路拉成一条直线。 6.1.2归一化处理

由地铁换乘公汽信息数据文件可知，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，从而可以认为在实际情况中，同一地铁站点与对应的公汽站点之间距离很近，为了简化该问题，可以将这些站点作为一个站点进行考虑。我们将其抽象化处理如下图(4)：

图(4)：归一化处理

基于这种思想，在整个交通网络中将同一地铁站点及其紧邻站点分别做归一站点处理，可以认为在新站点所代表的站点集中的任意站点间的距离可以忽略不计，从而时间也可忽略不计。

6.1.3建立“公汽、地铁直达数据库DM?”

原公交站点有3957个，考虑地铁站点后，站点总数增加至3996个，如果按照建立数据库DM的方法存储数据，那么数据更新的过程所需时间很长，不太实际。所以采用将归一化处理后的站点以txt(详见附录三)的形式存储，把39个地铁站加入到原来的DM数据库中，把归一化处理的新站点以函数的形式导入到数据库，形成一个新的数据库DM?，地铁费用和地铁换乘公汽的等待时间均被填充到元胞内，将新数据库中的站点称为新站点。那么建立DM?的实质是新站点与新站点间的直达线路信息集。用户输入起点和终点后，系统内部先自动查找两点所属的新站点，然后查找新站点间可直达的线路，并给出起点及其附近站点直达终点及其附近站点的最佳乘车线路。 6.2模型二的建立

问题二同时考虑公汽与地铁线路，乘客的需求分析与问题一中相同，要建立公汽、地铁线路计算机自主查询系统，对不同行程需求的乘客推荐相应的最佳路线，仍然采用多目标分层序列法，确定三个目标，分别为：换乘次数，乘车时间，乘车费用。根据调查结果，我们考虑乘客出行时考虑较多的三种类型，在此分别称为策略一、策略二和策略三。

策略一：按换乘次数最少、乘车时间最短、乘车费用最少的顺序考虑； 策略二：按乘车时间最短、换乘次数最少、乘车费用最小的顺序考虑； 策略三：按换乘次数最小、乘车费用最少、乘车时间最短的顺序考虑。 6.2.1确定目标函数

在建立的公汽、地铁直达数据库DM?的基础上，分别确定三个目标函数。 Target one ：乘换次数最少

?表示站点之间的换乘次数，根据公交线路的设计，尽管起始站和终点设Lij站位置相同，也可能有多种乘车方式，这些乘车方式中可能是直达的，也可能要

换乘一次，也可能需换乘两次。在建立的公汽、地铁直达数据库DM?中进行搜索，如果有直达方案，仅在直达方案中推荐满足其它目标函数的最佳路线。那么

?最小，即MinLij?。 要求LijTarget two ：乘车时间最少 基于假设六，到起始站等车的时间忽略不计，那么乘车时间包括行驶时间和换车时间。

??Vij??1? ?是各站最快直达时间，Vij?是实际转车次数，则行驶时间为：tij设tij在起始站点i到终点站j的过程中，设Zij?A表示在此过程中从公汽站换乘公汽

BC站的次数，此时i,?表示从公汽站换乘地铁站的次数，Zij表示从j?[1,3957]，Zij?,j?[3958,3996]。地铁站换乘公汽次数，此时iZ?D表示从地铁站换乘地铁的次数，

ijBCD那么换乘时间为：5ZijA?6Zij ?7Zij?4ZijBCD??Vij??1??5ZijA?6Zij?7Zij?4Zij 所以总的乘车时间为：tij，即第二个目标函BCD??Vij??1??5ZijA?6Zij?7Zij?4Zij数为：Mintij

Target three ：乘车费用最少

?表 问题一中乘车费用分为两个部分，在问题二中增加了地铁费用，用qij?1????2其中1表示单一?有三种取值，即qij示从站点i到站点j的计费方式，那么qij?3??表示站点i到站点j经过的站票价，2表示分段计费，3表示地铁票价；可设Sij?点数目，那么从站点i到站点j的费用Pij为：

??1qij?1?1q??2,1?S?20ijij????2,20?Sij?40 Pij???2qij?3??2,Sij?40qij???3qij??3ijijijij?P??V??1??L??V??2?其中V?表示实际换乘次数。

从而得到第三个目标函数为： Min?P??V??1?

那么行程总费用为：

iji,j?Eijiji,j?E综上我们建立的多目标整数规划目标函数为：

?MinLijMinMin6.2.2确定约束条件

BCD??Vij??1??5ZijA?6Zij tij?7Zij?4Ziji,j?E?P??V??1?ijij?1设Kj=?K??A,B,C,D?，当K?A,j?[1,3957]时，1表示在公汽站点j换

0?1,3957]乘公汽，0表示在公汽站点j不换乘公汽；当K?B,j?[时，1表示在公汽

站点j换乘地铁，0表示在公汽站点j不换乘地铁；当K?C,j?[3958,3996]时，1表示在地铁站j换乘公汽，0表示在地铁站j不换乘公汽；当K?D时，1表示在地铁站j换乘地铁，0表示在地铁站j不换乘地铁，而地铁换乘地铁只有当两条地铁线路经过的站点相同时，才可以换乘，由题中给出的地铁T1线换乘公汽信息与地铁T2线换乘公汽信息可知：地铁线T1,T2只同时经过D12和D18。此时j分别等于3969,3975。

讨论乘客是否换乘的约束条件，乘客在公汽站时有三种不同的选择，分别为

不换乘公汽、换乘公汽和转乘地铁，三种选择不能同时进行，那么相应的约束条件为： Aj?Bj?1 j?[1,3957]

乘客在地铁站D12和D18也相应的有三种不同的选择：不换乘地铁、换乘公

汽和换乘地铁，三种选择不能同时进行，所以相应的约束条件为：

Cj?Dj?1j?[3969,3975]

实际生活中，当离起始站点越近时，车上的乘客越少。aij的最小值越接近nij表示拥挤程度越高，aij的最小值越接近0表示拥挤程度越低，则0?Minaij?nij

另外也要考虑实际乘车次数Vij?的限制，在模型中我们仅考虑两次换乘以内的

??Vij??2，综上约束条件为： 情形，所以Lij?Aj?Bj?1 j?[1,3957]??Cj?Dj?1j?[3969,3975]?0?Mina?n?ijijs.t? ??Vij??2?Lij?i,??j?[1,3957]?,j?[3958,3996]??i6.2.3确定模型二

综上我们确定多目标整数规划模型为： ?MinLijMinMinBCD??Vij??1??5ZijA?6Zijtij?7Zij?4Zij

i,j?E?P??V??1?ijij?Aj?Bj?1 j?[1,3957]??Cj?Dj?1j?[3969,3975]?0?Mina?n?ijijs.t? ??Vij??2?Lij?i,??j?[1,3957]?,j?[3958,3996]??i6.3模型二的求解

模型二中的算法跟模型一中的算法一样，根据局部搜索算法思想，可

以运用MATLAB软件进行编程(代码详见附录四)，由于我们采用的是多目标分层序列整数规划模型，所以根据确定的三种不同的策略，可以得到相应策略的最佳路线，表(4)至表(6)分别给出了三种不同策略下题中要求解的六条线路的最佳路线。

表(4)：策略一中六条线路的最佳路线

线路 S3359-S1828 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 换乘次数 时间 花费 1 2 1 1 2 0 101 76 128 83 73 25 3 3 3 2 3 3 坐车路线 L436-S1784-L217 L084-S1919-L043-S3077-L273 L013-S2184-L417 L355-S2263-L345 L024-S1234-L505-S516- L104 D27-D36 距离始发站 17 28,20 14 11 16,23 5 (注：策略一按换乘次数、乘车时间、乘车费用的顺序进行考虑)

表(5)：策略二中六条线路的最佳路线

线路 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 时间 换乘次数 花费 1 2 2 2 2 0 3 3 3 5 3 3 76 85 67 73 25 坐车路线 L436-S1784-L217 L084-S1919-L043-S3077-L273 L084-S1919-L259-S211-L273 L150-S1426-T2-S528-L103 L024-S1234-L505-S516- L104 D27-D36 距离始发站 17 28,20 23,14 8,2 16,23 5 S3359-S1828 101 (注：策略二按乘车时间、换乘次数、乘车费用的顺序进行考虑)

表(6)：策略三中六条线路的最佳路线

线路 S3359-S1828 S1557-S0481 S0971-S0485 S0008-S0073 S0148-S0485 S0087-S3676 换车次数 花费 时间 1 2 1 1 2 0 3 3 3 2 3 3 101 76 128 83 73 25 坐车路线 L436-S1784-L217 L084-S1919-L043-S3077-L273 L013-S2184-L417 L355-S2263-L345 L024-S1234-L505-S516- L104 D27-D36 距离始发站 17 28,20 14 11 16,23 5 (注：策略三按换乘次数、乘车时间、乘车费用的顺序进行考虑)

6.4模型二的结果分析

比较表(4)至(6)，对三种策略下的最优路线进行分析发现，对于线路S3359-S1828和S1557-S0481无论是乘车时间、费用还是拥挤程度都是一样的，但是对于有些路线，在不同策略下的相关信息会有很大的区别，比如：线路S0971-S0485，在优先考虑乘车次数的策略下，所需时间为128分钟，但是在优先考虑时间的策略下，所需时间为85分钟，相对减少了43分钟，可见对于那些比较重视时间的乘客来说，优先考虑时间的策略要更优，所以我们从乘客不同需求进行考虑，给出相应的最佳出行路线是合理的。

7.问题三的解答

问题三将步行作为一种交通方式进行考虑，建立了模型三进行求解。

7.1问题三的数据处理 7.1.1关于步行的假设

设站点i到站点j的步行时间为tij，若tij?T，则称站点i与站点j互称为邻近站点，T是邻近站点的时间上确界，即乘客所能忍受的最长步行时间，可令T?12分钟，规定步行后换乘车次只能在邻近站点或同一站点。

1) 所有站点之间的步行时间固定不变,并且不受外界其他因素的干扰； 2) 只有公汽站点间可以步行，地铁站点间不能步行； 3) 任意两个邻近站点平均步行时间是t0?5分钟。 7.1.2步行邻边化

假设站点i到站点j的平均步行时间为t?i,j?，定义以乘客所在的起始点为圆心，以最长步行时间T对应的距离为半径的圆形区域称为起始点startp的邻接圆域。由假设知，邻接圆域内任意公汽站点b都与startp相邻接，且b与startp的邻接耗时为t?startp,b?。将邻接圆域抽象为下图：

b 公汽startp T 地铁b

7.2模型三的建立

问题三在问题二的基础上增加考虑了步行对最优路线选取的影响，我们把步

行作为一种花费为0，只需计算时间的交通工具。在仅考虑公汽或考虑公汽及地铁的时候，我们都对有不同需求的乘客推荐相应的最佳路线，即考虑了三个策略。但对于该问，步行并没有增加出行的花费，每个站点间平均步行时间为5分钟，就算乘公汽或地铁也要分别花费3分钟或2.5分钟，所以考虑步行对出行时间和乘车费用的影响不大，但是步行一站或两站很可能会导致换乘次数的变化和换乘站点的变化，所以我们只考虑以换乘次数作为第K1个目标函数的多目标规划，在优先考虑换乘次数的基础上，再考虑乘车时间次数和乘车费用，即前两问中的策略一。

7.2.1确定目标函数

Target one ：乘换次数最少

把步行作为一种交通工具考虑后，对换乘次数并没有什么影响，所以换乘次

? 数同问题二，该目标函数为：MinLijTarget two：乘车时间最短

问题三跟问题二中乘车时间不同的是要考虑步行的时间，即包括行驶时间、

换乘时间和邻接公汽站点间的步行时间。

??Vij??1? ?是各站最快直达时间，Vij?是实际转车次数，则行驶时间为：tijtijBCD换乘时间同问题二，为：5ZijA?6Zij ?7Zij?4Zij设t表示邻接公汽站点间的步行时间，为乘车需要乘客步行的站数可能不止一站，也有可能不步行，可令k表示乘客步行经过的站点数，则邻接公汽站点间的步行时间为： t?kt0

BCD??Vij??1??5ZijA?6Zij?7Zij?4Zij?kt0 所以乘车时间为：tijBCD??Vij??1??5ZijA?6Zij?7Zij?4Zij?kt0 从而得到第一个目标函数为：MintijTarget three ：乘车费用最少

步行并不能增加乘车费用，所以乘车费用的目标函数也跟问题二中相同，即

Mini,j?E?P??V??1?

ijij综上，多目标整数规划目标函数为：

?MinLij MinBCD??Vij??1??5ZijA?6Zijtij?7Zij?4Zij?kt0

Min7.2.2确定约束条件

i,j?E?P??V??1?ijij步行对换乘问题，包括换乘次数以及换乘方式均没有影响，所以问题二中的

约束条件均适合问题三。另外我们假设任意两个邻近站点平均步行时间是t0?5分钟，又邻近站点的时间上确界为T?12，即kt0?T，得到k??0,1,2?。所以约束条件为：

?Aj?Bj?1 j?[1,3957]??Cj?Dj?1j?[3969,3975]?L??V??2ij?ij s.t?j?[1,3957]?i,??i?,j?[3958,3996]???kt0?Tk??0,1,2?7.2.3确定模型三

综上，我们确定的多目标整数规划模型为：

C??Vij??1??5ZijA?6ZijB?7ZijMintij?4ZijD?kt0MinMin?Liji,j?E

ijij?P??V??1??Aj?Bj?1 j?[1,3957]??Cj?Dj?1j?[3969,3975]?0?Mina?nijij????Vij??2subjectto?Lij

???i,j?[1,3957]?i?,j?[3958,3996]???kt0?Tk??0,1,2?7.3模型三的求解

模型三中以换乘次数少、乘车时间短、费用少为考虑的先后顺序建立的多目

标整数规划模型三，增加考虑步行后，一些相隔2站以内的站点可以通过步行到达。以题中给出的六条线路中的S1557-S0481，S0148-S0485为例，起始点S1557与S3158,S0645,S0646相隔仅一站，与S2628,S2143,S3135相隔2站可以步行，终点S0481与S0872,S2101,S3919相隔仅一站，与S0492,S0903，S1179,S0871,S3667,S3919相隔2站也可以步行。线路S0148-S0485也可以按照同样的方法进行分析，在此分析的基础上可以运用MATLAB软件编程进行求解(代码详见附录五)，以线路S1557-S0481，S0148-S0485为例，得到优先考虑乘车时间的最佳路线如下表(7)：

表(7)：问题三中的最佳路线

线路 S1557-S0481 S0148-S0485 最优路线 从S1557步行2站到S2143-L084-S1919-L043-S3077-L273 从S0148步行1站到S3182-L308-S36-L157-S0722再步行一站到S0485 换乘 1 1 时花间 费 92 69 3 2 7.4模型三的结果分析

基于问题三数据处理中的假设(2)，只有公汽站点间可以步行，地铁站点间不能步行；所以步行这种出行方式的增加只会对公汽之间的换乘产生影响，所以可以将模型三中的结果与模型一策略一中的结果对比，模型一中线路S1557-S0481，S0148-S0485相应的路线、乘车时间、换乘次数如下表(8):

表(8):模型一中相应路线的结果

线路 S1557-S10481 S0148-S0485 最优路线 L084-S1919-L043-S3077-L273 L024-S1234-L505-S516- L104 换乘次数 2 2 时间 76 73 花费 3 3 将表(7)与表(8)对比可以看出对于线路S1557-S0481，当转乘次数减小时，总的出行时间变长，费用不变；但是对于路线S0148-S0485，当转乘次数减少时，不仅出行时间减少4分钟，而且费用也减少了一元。所以出行时，适当的选择步行是一种很好的方式。

8.模型的评价、改进和推广

模型的评价

优点：

1、通过实际调查，确定了乘客对乘车的不同需求，以乘车时间、换乘次数、乘车花费为目标建立多目标优化模型，使问题更加清晰，得出的线路更全面合理；

2、将复杂的公交网转化为图论问题，在图论基础上求解出转乘次数不超过两次 时的所有可行方案，根据乘客的不同需求，给出最佳路线方案，模型实用性较强；

3、利用MATLAB元胞数组存储数据信息，缩小信息存储空间，并选用适当的搜索算法，缩短运算时间，有较强的实用性；

4、模型的现实意义强，具有很好的实用性和扩展性。 缺点：

1、在转乘次数超过2次的情况下，运用所建立的模型求解计算过程复杂，计算量过大；故模型存在一定的局限性。

2、由于在计算过程中题目给的平均行驶及转车时间是非现实的，所以使得本模型的应用于现实时存在偏差。 模型的改进

由于公交网本身就是一个复杂的连通图，数据信息量大，而我们所建立的模型只考虑了乘客对乘车时间，转乘次数，乘车费用以及拥挤程度的需求，可以适当的考虑其他的需求，如：乘车途中的观光路线，线路中经过的标志性建筑等因素。从人性化的角度考虑，还可以把车辆的负载量，舒适度考虑进去。

另外，本文是一个静态的交通系统，所有的信息都已经给定。通过本题的数学模型，只要给出起始点和目的地，我们就可以通过算法求得应该走的路线，所花的时间以及乘车费用。但是在现实生活中，交通系统随时都可能在发生变化，如：上下班时候的某些线路运力不足，由于交通事故某两个站点之间的线路暂时中断，但是这些在本题中都没有能够反应出来，这样我们的路径推荐模型就可能将用户带到已经中断或者是非常拥挤的线路中。所以从实际出发，应该建立动态系统，将交通系统查询计算机网络化，每一个查询终端类比为一个路由器，同时采用类似于路由算法的实时更新算法。这样才能够根据最新的数据信息判断出最优方案。 模型的推广

本文采用多目标规划模型确定北京的公交线路，多目标规划模型不仅可以应用于公交线路的查询还可以运用到其他方面，比如：国防部门设计某种导弹时，一般都要求导弹的射程要远，精度要高，重量要最轻以及消耗燃料要最省等；在物资调运过程中，既要考虑在运输过程中少走冤枉路，同时又要考虑节约运费等。

9.参考文献

[1] 湖北大学生数学竞赛专家组，数学建模（本科册），华中科技大学出版社，

2006.2.

[2] 王沫然 MATLAB与科学计算（第二版）电子工业出版社 2005.12.

[3] 沈雷 张鑫 马福诚 一种公共交通的最优路径算法 海洋测绘第25卷 第6期

2005.11,41-43.

[4] 姜启源 谢金星 叶俊 数学模型（第三版）[M] 北京：高等教育出版社2003

10.附录

附录一： directMatrix.m%生成直达数据库DM clear all; clc %生成3996*3996的空直达矩阵 DM=cell(3996,3996); %数据导入 file=fopen('d:\\我的文档\\桌面\\1.1 公汽线路信息.txt','r'); lcount=0; while 1 fprintf('已导入%d行\\n',lcount); lcount=lcount+1; tline=fgetl(file); if strcmp(tline,'END') fprintf('the end\\n'); break; end if strcmp(tline,'') continue; end if strcmp(tline(1),'L') busNumStr=tline; continue; end if strcmp(tline,'单一票制1元。') ticketType=1; continue; end if strcmp(tline,'分段计价。') ticketType=2; continue; end %对第一种情况，有上下行的进行处理 if strcmp(tline(1:2),'上行')||strcmp(tline(1:2),'下行') stationNum=(size(tline,2)-8)/6+1; for startP=1:stationNum-1 for endP=startP+1:stationNum existNum=size(DM{str2num(tline(6*startP-1:6*startP+2)),str2num(tline(6*endP-1:6*endP+2))},1); DM{str2num(tline(6*startP-1:6*startP+2)),str2num(tline(6*endP-1:6*endP+2))}(existNum+1,:)={busNumStr,3*(endP-startP),ticketCost(ticketType,startP,endP),startP}; end end continue; end %对第二种情况，上下行一致的进行处理 if strcmp(tline(1),'S') stationNum=(size(tline,2)-5)/6+1; for startP=1:stationNum for endP=1:stationNum if startP==endP continue; end existNum=size(DM{str2num(tline(6*startP-4:6*startP-1)),str2num(tline(6*endP-4:6*endP-1))},1); if startPstationNum-1 ww=startP-stationNum+1; else ww=startP; end DM{saveStation(startP),saveStation(endP)}(existNum+1,:)={busNumStr,3*abs(endP-startP),ticketCost(ticketType,startP,endP),ww}; end end continue; end end 附录二： ticketCost.m%计算票价的函数（第一问） unction cost=ticketCost(ticketType,startP,endP) if ticketType==1 cost=1; end if ticketType==2 passStation=abs(endP-startP); if passStation<=20 cost=1; elseif passStation<=40 cost=2; else cost=3; end end changeBus1.m%计算换乘一次的（第一问） function a=changeBus1(DM,startP,endP) a={}; midP=[]; for i=1:3957 if size(DM{startP,i},1)~=0 midP=[midP,i]; end end for i=1:size(midP,2) if size(DM{midP(i),endP},1)==0 midP(i)=0; end end for i=1:size(midP,2) if midP(i)==0 continue; end lineOne=size(DM{startP,midP(i)},1); lineTwo=size(DM{midP(i),endP},1); for jj=1:lineOne for kk=1:lineTwo sizea=size(a,1); a(sizea+1,:)={DM{startP,midP(i)}{jj,1},midP(i),DM{midP(i),endP}{kk,4},DM{midP(i),endP}{kk,1},DM{startP,midP(i)}{jj,2}+DM{midP(i),endP}{kk,2}+5,DM{startP,midP(i)}{jj,3}+DM{midP(i),endP}{kk,3}}; end end end changeBus2.m%计算换乘2次的（第一问） function a=changeBus2(DM,startP,endP) a={}; midP=[]; mid2P=[]; for i=1:3957 if size(DM{startP,i},1)~=0 midP=[midP,i]; end end for i=1:3957 if size(DM{i,endP},1)~=0 mid2P=[mid2P,i]; end end for i=1:size(midP,2) for j=1:size(mid2P,2) if size(DM{midP(i),mid2P(j)},1)==0 continue; end for mm=1:size(DM(startP,midP(i)),1) for nn=1:size(DM(midP(i),mid2P(j)),1) for kk=1:size(DM(mid2P(j),endP),1) sizea=size(a,1); a(sizea+1,:)={DM{startP,midP(i)}{mm,1},midP(i),DM{midP(i),mid2P(j)}{nn,4},DM{midP(i),mid2P(j)}{nn,1},mid2P(j),DM{mid2P(j),endP}{kk,4},DM{mid2P(j),endP}{kk,1},DM{startP,midP(i)}{mm,2}+DM{midP(i),mid2P(j)}{nn,2}+DM{mid2P(j),endP}{kk,2}+10,DM{startP,midP(i)}{mm,3}+DM{midP(i),mid2P(j)}{nn,3}+DM{mid2P(j),endP}{kk,3}}; end end end end end strategy1.m%策略1（第一问） %策略1，优先考虑转乘次数，再考虑时间，最后考虑费用 function a=strategy1(DM,startP,endP) a={}; if size(DM{startP,endP},1)~=0 a=DM{startP,endP}; a=sortrows(a,2); if size(a,1)>=20 a=a(1:20,:); end end if size(DM{startP,endP},1)==0&&size(changeBus1(DM,startP,endP),1)~=0 a=changeBus1(DM,startP,endP); a=sortrows(a,5); if size(a,1)>=20 a=a(1:20,:); end end if size(DM{startP,endP},1)==0&&size(changeBus1(DM,startP,endP),1)==0 a=changeBus2(DM,startP,endP); a=sortrows(a,8); if size(a,1)>=20 a=a(1:20,:); end end strategy2.m%策略2（第一问） %策略2，首先考虑时间，再考虑转乘次数，最后考虑费用 function a=strategy2(DM,startP,endP) a={}; a1=DM(startP,endP);

a2=changeBus1(DM,startP,endP); a3=changeBus2(DM,startP,endP); a1k=[]; if size(a1(1,:),2)>=2 a1k=[ones(size(a1,1),1),[1:size(a1,1)]',cell2mat(a1(:,2))]; end a2k=[]; if size(a2,2)>=2 a2k=[ones(size(a2,1),1)+1,[1:size(a2,1)]',cell2mat(a2(:,5))]; end a3k=[ones(size(a3,1),1)+2,[1:size(a3,1)]',cell2mat(a3(:,8))]; ?k ￠k ￡k if size(a1k,1)==0&&size(a2k,1)==0 ak=[a3k]; end if size(a1k,1)==0&&size(a2k,1)~=0 ak=[a2k;a3k]; end if size(a1k,1)~0 ak=[a1k;a2k;a3k]; end ak=sortrows(ak,3); if size(ak,1)>=21 ak=ak(1:20,:); end for i=1:size(ak,1) sizea=size(a,1); if ak(i,1)==1 a(sizea+1,:)={a1{ak(i,2),1},a1{ak(i,2),2},a1{ak(i,2),3},0,0,0,0,0,0}; continue; end if ak(i,1)==2 a(sizea+1,:)={a2{ak(i,2),1},a2{ak(i,2),2},a2{ak(i,2),3},a2{ak(i,2),4},a2{ak(i,2),5},a2{ak(i,2),6},0,0,0}; continue; end if ak(i,1)==3 a(sizea+1,:)={a3{ak(i,2),1},a3{ak(i,2),2},a3{ak(i,2),3},a3{ak(i,2),4},a3{ak(i,2),5},a3{ak(i,2),6},a3{ak(i,2),7},a3{ak(i,2),8},a3{ak(i,2),9}}; continue; end end strategy3.m%策略3（第一问） %策略3，优先考虑转乘次数，最后考虑费用,再考虑时间 function a=strategy3(DM,startP,endP) a={}; if size(DM{startP,endP},1)~=0 a=DM{startP,endP}; a=sortrows(a,3); if size(a,1)>=20 a=a(1:20,:); end end if size(DM{startP,endP},1)==0&&size(changeBus1(DM,startP,endP),1)~=0 a=changeBus1(DM,startP,endP); a=sortrows(a,6); for i=2:size(a,1) kkk=size(a,1); if a{i-1,6}~=a{i,6} kkk=i; break; end end a=a(1:kkk,:); a=sortrows(a,5); if size(a,1)>=20 a=a(1:20,:); end end if size(DM{startP,endP},1)==0&&size(changeBus1(DM,startP,endP),1)==0 a=changeBus2(DM,startP,endP); a=sortrows(a,9); kkk=size(a,1); for i=2:size(a,1) if a{i-1,9}~=a{i,9} kkk=i; break; end end a=a(1:kkk,:); a=sortrows(a,8); if size(a,1)>=20 a=a(1:20,:); end end Main.m%例子程序 clc %以策略1为例，其实站点为3359，终点为1828，请自行修改数据 a=strategy1(DM,3359,1828)

附录三： 地铁到公交站.txt%第二问用到的导入数据 01 0567 0042 0025 02 1487 03 0303 0302 04 0566 05 0436 0438 0437 0435 06 0392 0394 0393 0391 07 0386 0388 0387 0385 08 3068 0617 0619 0618 0616 09 1279 10 2057 0721 0722 0720 11 0070 2361 3721 12 0609 0608 13 2633 0399 0401 0400 14 3321 2535 2464 15 3329 2534 16 3506 0167 0168 17 0237 0239 0238 0236 0540 18 0668 19 0180 0181 20 2079 2933 1919 1921 1920 21 0465 0467 0466 0464 22 3457 23 2512 24 0537 3580 25 0526 0528 0527 0525 26 3045 0605 0607 27 0087 0088 0086 28 0855 0856 0854 0857 29 0631 0632 0630 30 3874 1426 1427 31 0211 0539 0541 0540 32 0978 0497 0498 33 1894 1896 1895 34 1104 0576 0578 0577 35 3010 0583 0582 36 3676 0427 0061 0060 37 1961 2817 0455 0456 38 3262 0622 39 1956 0289 0291 addRailway.m%在DM的基础上增加地铁信息 file=fopen('d:\\我的文档\\桌面\\1.2 地铁线路信息.txt','r'); lcount=0; while 1 fprintf('已导入%d行\\n',lcount); lcount=lcount+1; tline=fgetl(file); if strcmp(tline,'END') fprintf('the end\\n'); break; end if strcmp(tline,'') continue; end if strcmp(tline(1),'T') railwayStr=tline; continue; end if strcmp(tline(1:10),'票价3元，本线路使用') continue; end %对地铁线路T1进行处理 if strcmp(tline(1),'D') railwayNum=(size(tline,2)-3)/4+1; for i=1:railwayNum-1 for j=i+1:railwayNum startR=str2num(tline(4*i-2:4*i-1))+3957; endR=str2num(tline(4*j-2:4*j-1))+3957; existNum=size(DM{startR,endR},1); DM{startR,endR}(existNum+1,:)={'T1',2.5*(j-i),3,i}; end end end %对地铁线路T2进行处理 if strcmp(tline(1:2),'环行') railwayNum=(size(tline,2)-6)/4; midR=[]; for i=1:railwayNum midR=[midR,str2num(tline(4*i+1:4*i+2))]; end midR=[midR,midR(1:size(midR,2)-1)]; for i=1:railwayNum for j=i+1:i+railwayNum-1 existNum=size(DM{midR(i)+3957,midR(j)+3957},1); DM{midR(i)+3957,midR(j)+3957}(existNum+1,:)={'T2',2.5*(j-i), 3,i}; end end end end importRail2Bus.m%加入地铁站到车站的对应信息 clc Rail2Bus=importdata('d:\\我的文档\\桌面\\Rail2Bus.txt'); directGo.m%新的直达信息函数（考虑地铁后） function a=directGo(DM,startP,endP,Rail2Bus) a={}; ss=[0,1,startP,0,0,0,0]; ee=[0,1,endP,0,0,0,0,]; for i=1:39 for j=3:7 if startP==Rail2Bus(i,j) ss=Rail2Bus(i,:); end if endP==Rail2Bus(i,j) ee=Rail2Bus(i,:); end end end if startP-3957>=1 ss=Rail2Bus(startP-3957,:); end if endP-3957>=1 ee=Rail2Bus(endP-3957,:); end if ss(1)~=0&&ee(1)~=0 ss(1); ee(1); DM{ss(1)+3957,ee(1)+3957}; sizeDM=size(DM{ss(1)+3957,ee(1)+3957},1); if sizeDM~=0 for i=1:sizeDM sizea=size(a,1); a(sizea+1,:)={DM{ss(1)+3957,ee(1)+3957}{i,1},DM{ss(1)+3957,ee(1)+3957}{i,2},DM{ss(1)+3957,ee(1)+3957}{i,3},DM{ss(1)+3957,ee(1)+3957}{i,4}}; end end end for i=1:ss(2) for j=1:ee(2) sizeDM=size(DM{ss(i+2),ee(j+2)},1); if sizeDM>=1 for k=1:sizeDM sizea=size(a,1); a(sizea+1,:)={DM{ss(i+2),ee(j+2)}{k,1},DM{ss(i+2),ee(j+2)}{k,2},DM{ss(i+2),ee(j+2)}{k,3},DM{ss(i+2),ee(j+2)}{k,4}}; end end end end if size(a,1)>=2 a=sortrows(a,2); end %{ if size(a,1)>=1 kk=size(a,1); for i=1:kk if strcmp(a{i,1}(1),'T') a(i,:) end end end %} 附录四：

问题二中代码与问题一中代码重复部分较多，并且算法相似，故在此将该问代码略去。 附录五： Question3.m%第三问代码 %以3359,1828为例 startP=3359; endP=1828; a={}; if size(directGo(DM,startP,endP,Rail2Bus),1)~=0 a=directGo(DM,startP,endP,Rail2Bus); a=sortrows(a,2); if size(a,1)>=20 a=a(1:20,:); end end if size(directGo(DM,startP,endP,Rail2Bus),1)==0&&size(changeBus1(DM,startP,endP,Rail2Bus),1)~=0 a=changeBus1(DM,startP,endP,Rail2Bus); a=sortrows(a,5); if size(a,1)>=20 a=a(1:20,:); end end if size(directGo(DM,startP,endP,Rail2Bus),1)==0&&size(changeBus1(DM,startP,endP,Rail2Bus),1)==0 a=changeBus2(DM,startP,endP,Rail2Bus); a=sortrows(a,8); if size(a,1)>=20 a=a(1:20,:); end end a

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