西宁市长海医院在哪里:大型公交网络线路查询模型与算法

分析了大型城市公交网络的特点，为满足乘客出行时各种不同的需求，综合考虑换乘次数、出行时间与乘车费用等多种不同因素，通过构造线路与站点、站点与站点的连接矩阵，结合矩阵算法与搜索算法的优点，提出了一种分类多目标优化搜索算法。该算法搜索时间较短，能够生成多条备选路径供出行者选择，能基本满足自主查询计算机系统的需要。

对于公交线路查询的数学模型， 国内外学者提出了许多算法，包括迪杰斯特拉(Dijkstra)算法、弗罗伊德(Floyd) 算法与矩阵算法等[1]-[8]。其中Dijkstra算法稳定性强，是目前公认的最好算法。但是对公交线路来说，直接应用Dijkstra算法求得最优路径问题存在着明显不足。例如, Dijkstra算法要求网络拓扑图和表示网络图的数据结构简洁，这对于复杂的城市公交网络拓扑关系来说，就必须在对其进行复杂的抽象后，合并成简捷的网络拓扑图，这无疑增加了程序的复杂性。此外，其它一些算法如：基于最小换乘次数的最优路径算法[9]与基于最短路径查询的城市公交网络拓扑建模研究[10]等，对中、小型公交网络比较适合。考虑到大型公交网络中线路与站点较多且有地铁线路的存在，一般的矩阵算法与搜索算法计算时间长，无法满足自主查询计算机系统的需要。人们在选择公交出行线路时考虑的因素很多，如换乘次数是否最少、出行耗时是否最少与花费是否最少等。面对如此多的因素, 有时就很难做出准确的判断, 所以希望能够得到一定的指导和多种出行方案以供选择。大多数乘客在选择公交线路出行时，首先考虑的是乘车是否方便，就换乘次数而言，一般不大于两次；其次是乘车所花费的时间是否最少，这主要是通过公交线路的距离、换乘次数与换乘时间来衡量；在此基础上最后考虑费用最低。公交线路应同时考虑换乘次数、出行时间与乘车费用，地铁线路应以出行时间为主，同时考虑换乘次数，一般不考虑乘车费用。本文通过构造线路与站点、站点与站点的连接矩阵，结合矩阵算法与搜索算法的优点，提出了一种分类多目标优化搜索算法。具体分为三个数学模型：模型一只考虑公汽线路，在不超过两次换乘的情况下，分别提供了以出行时间最短为第一目标、乘车费用最少为第二目标和乘车费用最少为第一目标、出行时间最短为第二目标的最佳乘车线路；模型二只考虑地铁线路，以出行时间最短为目标，地铁站点可以直达，非地铁站点可通过地铁换乘得到最佳乘车线路；模型三考虑了步行小段距离再乘车或转车的更为实际的情况。

1．模型假设

（1）假设出行者选择乘车路线时换乘次数不超过两次；

（2）假设车辆在行驶过程中不发生堵车；

（3）假设等待时间相同，不考虑乘车高峰等待时间过长问题；

（4）假设公汽、地铁每站行驶时间相同；

（5）假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，其耗时相当于公汽换乘地铁的步行时间与地铁换乘公汽的步行时间之和；

（6）假设地铁票价相同，无论地铁线路间是否换乘；

（7）如果考虑乘客选择步行，假设换乘次数最多一次；

（8）假设一次出行步行次数不超过三次；

（9）假设每次步行时间与距离相同。

2．符号说明：

（1）A，B，C，…… 表示站点名称，同时也表示站点号；

（2） 表示站点A在第 条线路中的位置；

（3） 表示从站点A到站点B的第 条线路；

（4） 表示第 条线路从站点A到站点B的直达费用；

（5） 表示第 条公汽线路从站点A到站点B的直达时间， 表示地铁线路从站点A到站点B的直达时间， 分别表示公汽换乘公汽、地铁换乘地铁、地铁换乘公汽、公汽换乘地铁的平均耗时、同一地铁站点的两个公汽站点之间的步行时间， 表示相邻公汽站之间平均行驶时间， 表示相邻地铁站之间平均行驶时间， 表示一次步行的时间；

（6） 表示第 条线路从站点A到站点B经过的站数；

（7） 表示一次步行的距离；

（8） 表示与某站点A距离小于 的所有站点构成的集合；

（9） 表示线路与站点的连接矩阵；

（10） 表示站点与站点的连接矩阵。

3．模型一：公汽线路数学模型

根据人们的出行习惯，在选择从站点A到站点B的行车线路时，首先会先看是否有从站点A到站点B的直达线路，如果有会选择直达方案，如果存在不止一条直达线路，再考虑所走路线的远近，选择距离最近的乘车方案；如果没有直达线路，就会考虑一次换车的方案，即判断经过站点A的线路与经过站点B的线路是否有公共站点C，如果有则可以在公共站点C处换乘；如果没有一次换乘方案，则又要考虑经过站点A的线路上某一站点C，判断经过站点C的线路与经过站点B的线路是否有公共站点D，如果有就再到站点D 换乘，两次换乘可到达站点B；如果没有，则需要转乘三次或三次以上才可到达目的地。但基于现在的交通网络越来越发达的情形，需换乘三次的情况已越来越少，另外，基于出行方便的心理，出行者很少愿意换乘三次，因此，为了简化模型，我们假设换乘次数不超过两次。

3.1直达数学模型

其中：单一票价 ；分段计价

，其中：

3.2换乘一次数学模型

3.3换乘两次数学模型

3.4模型算法与设计

首先构造线路与站点的连接矩阵 ，其中 表示站点 在第 条线路上， 表示站点 不在第 条线路上， 为线路总数，包括上行、下行与环行线路，为便于查找，线路相同的上下行与环行线路按不同的线路输入， 为站点总数。

3.4.1直达数学模型算法与设计

(1)输入乘车的起始站点A及终到站点B；

(2)求出经过站点A 的所有线路集 ，任取一条线路 ，判断站点B是否在线路 上，然后判断站点A与站点B是否同向，即站点B在该线路上的位置是否大于站点A的位置（环行线路无需判断）。具体求法是，在连接矩阵 的第A列中查找1所在行的位置，逐一判断这些有1的行中第B列所在的位置是否也是1，如果不是1说明该行所表示的线路中包含站点A但不包含站点B，如果都是1，然后根据线路数据信息判断 是否大于 ；

(3)如果没有找到直达线路，或找到直达线路唯一，结束运行。否则在所有结果中寻找费用最小或出行时间最短的线路；

(4)如果费用最小或出行时间最短的直达线路唯一，结束运行。否则在所得线路中分别再搜索出行时间最短与乘车费用最小的直达线路，并输出结果。

3.4.2一次换乘数学模型算法与设计

(1)输入乘车的起始站点A及终到站点B；

(2)求出经过站点A 的所有线路集 和经过站点B 的所有线路集 .

(3)任取一条线路 与 ，判断是否存在公共站点。在连接矩阵 中，将第 行与第 行相加，结果中如果有2存在，说明存在公共站点。

(4)线路 与 如果存在公共站点C=D，则判断其是否同向，否则再换一条线路重新搜索；

(5)若公共站点对线路 与 都同向，则线路 与 为站点A到站点B的一次换乘线路，C或D为一次换乘站点，否则，换一条线路重新搜索，直至找到所有一次换乘线路为止。

(6)类似直达数学模型算法，计算最小乘车费用与出行时间，输出一次换乘最佳线路。

3.4.3两次换乘数学模型算法设计

(1)输入乘车的起始站点A及终到站点B；

(2)求出经过站点A 的所有线路集 和经过站点B 的所有线路集 .

(3)任取一条线路 与 ，再在所有公交线路中任取一条不同于线路 、 的线路 ，其中 ， 为线路总数。用类似一次换乘数学模型的算法判断线路 与 以及 与 是否存在公共站点C=E和F=D，如果存在，继续判断站点A与C、C与D以及D与B是否同向；

(4)如果存在公共站点C=E和F=D，而且站点A与C、C与D以及D与B都同向，则 、 与 为站点A到站点B的两次换乘线路，C与D为两次换乘站点，否则，换一条线路重新搜索，直至找到所有两次换乘线路为止。

(5)类似直达数学模型算法，计算最小乘车费用与出行时间，输出两次换乘最佳线路。

4．模型二：地铁线路数学模型

该模型中包含了地铁线路，考虑到直接计算最优路径将十分复杂，将地铁，公汽分开考虑，即将线路分为两种情形，情形一是包含地铁线路或公汽线路中包含地铁站点的线路，情形二是不包含地铁线路与地铁站点的公汽线路。首先从情形一中筛选出不同需求的最佳线路，然后再与模型一得出的最佳线路作比较，进而确定总的最佳线路。由于情形二已在模型一中研究，模型二只对情形一进行讨论。

乘坐地铁一般费用较高，其主要目的在于如何缩短出行时间，因此模型二只考虑出行时间最短问题。模型二按照换乘次数又分为：地铁直达模型，公汽换乘地铁模型，地铁换乘公汽模型，公汽换乘公汽再换乘地铁模型，公汽换乘地铁再换乘公汽模型，地铁换乘公汽再换乘公汽模型。在换乘地铁的模型中，包含了通过地铁站进行公汽换乘的情形，可能不进行地铁换乘。由于模型二所包含的模型较多，下面重点讨论地铁直达模型、公汽换乘地铁模型与公汽换乘地铁再换乘公汽模型。

4.1地铁直达模型

该模型最短出行时间线路唯一，无需多线路优化。

(1)起始站点与终到站点同在直线上；

(2)起始站点与终到站点同在环线上，换乘站点C与D同在环线上除外；

其中： 为地铁环线总站数。

(3)起始站点A与终到站点B不同在直线或环线上，设C与D为换乘站点，A、B不同于C、D；

4.2公汽换乘地铁模型

4.2.1模型建立

设起始站点A为非地铁站点的某一公汽站点，终到站点B为地铁站点M的某一公汽站点。

(1)线路 的终到站点C=B；

(4.2.1)

(2)线路 终到站点C为B所在的地铁站点M的另一公汽站点；

(4.2.2)

(3)线路 的终到站点C为另一地铁站点N( M)的某一公汽站点；

(4.2.3)

其中：N为A到B所有可行线路的总数。

4.2.2算法设计

(1)输入乘车的起始站点A及终到站点B，A为非地铁站点的某一公汽站点，B为地铁站点M的某一公汽站点；

(2)任取一地铁站点的某一公汽站点C，用模型一中的方法判断是否存在A到C的直达公汽线路，如果存在，求出出行时间最短的线路，将其线路与站点C的所有信息保存，否则，对所有地铁站的所有公汽站点进行搜索；

(3)任取一条出行时间最短的线路 ，判断站点B是否等于C，如果是，使用(4.2.1)式计算出行时间, 否则，转下一步；

(4)判断B所在的地铁站点M的其它公汽站点是否等于C，如果是，使用(4.2.2)式计算出行时间，否则，转下一步；

(5)设C所在的地铁站点为N( M)，使用(4.2.3)式计算出行时间；

(6)搜索所有经过站点A直达地铁站点出行时间最短的线路。

如果每次所得时间小于现有出行时间，记录线路与站点数据信息，放弃原数据信息；如果每次所得时间等于现有出行时间，在原有数据信息中添加新的线路与站点数据信息；否则原有数据信息不变。

4.3公汽换乘地铁再换乘公汽模型

4.3.1模型建立

设起始站点A与终到站点B为非地铁站点的公汽站点，M与N为连接A、B的两地铁站点，E、F分别为地铁站点M、N中的一公汽站点。

(1)若M=N且E F（E=F为模型一中的直达或一次换乘模型）

(4.3.1)

(2)若M N

(4.3.2)

其中：N为A到B所有可行线路的总数。

4.3.2算法设计

(1)输入乘车的起始站点A及终到站点B，A、B均为非地铁站点的公汽站点；

(2)任取一地铁站点的某一公汽站点C，用模型一中的方法判断是否存在A到C的直达公汽线路，如果存在，求出出行时间最短的线路，将其线路与站点C的所有信息保存，否则，对所有地铁站的所有公汽站点进行搜索；

(3)任取一地铁站点的某一公汽站点D，用模型一中的方法判断是否存在D到B的直达公汽线路，如果存在，求出出行时间最短的线路，将其线路与站点D的所有信息保存，否则，对所有地铁站的所有公汽站点进行搜索；

(4)任取一条出行时间最短的线路 、 ，判断C是否等于D，如果是，使用模型一中的直达模型或一次换乘模型计算出行时间，否则，转下一步；

(5)判断C所在的地铁站点M是否等于D所在的地铁站点N，如果相等，使用（4.3.1）计算出行时间；否则，转下一步；

(6)使用（4.3.2）计算出行时间，并对所有出行时间最短的线路 、 进行搜索。

如果每次所得时间小于现有出行时间，记录线路与站点数据信息，放弃原数据信息；如果每次所得时间等于现有出行时间，在原有数据信息中添加新的线路与站点数据信息；否则原有数据信息不变。

5．模型三：允许步行小段距离的数学模型

在上面的算法中只有当不同线路之间具有公共站点时才能够进行换乘，这样计算出来的结果有时并不符合实际情况，比如在实际出行时可以直达或只需换乘一次便可到达目的地的情况，但计算出来的结果却需要换乘两次。出现这种情况的原因是忽视了现实生活中人们步行小段距离后乘车或换乘的现象。具体来说，人们可以就近乘车也可以步行小段距离后乘车；在换乘时，不一定下车后直接在下车的站点处换乘，往往需要步行小段距离到附近的站点去换乘；同时也可能出现下车后步行小段距离才到达目的地的情况。人们选择这种方式通常可以减少换乘次数。如果允许步行次数可以为三次，即乘车前后与转车允许步行小段距离，一般最多换乘一次即可到达目的地。

5.1步行直达模型

，

其中：单一票价 ；分段计价

，其中： ， 为步行次数。

5.2步行换乘一次数学模型

， 为步行次数。

5.3模型算法设计

类似地铁站点中的公汽站点，将与某站点A距离小于 的所有站点构成的集合计作 ，构造站点与站点的连接矩阵 ，其中 为站点总数。当站点 与站点 距离小于 时， ；否则，

5.3.1步行直达模型算法设计

(1)输入乘车的起始站点A及终到站点B；

(2)任取站点 ，任取经过C的一条线路 ，设C在 上可到达的站点为： ,若 ，则 为A到B的步行直达线路，此时，若C=A，B= ，则步行次数为0；若C=A，或B= ，则步行次数为1；否则步行次数为2，若 ，转下一步；

(3)对经过站点C的所有线路 进行搜索，并对 中的所有站点进行搜索。

如何判断站点B是否属于 ，具体做法是将站点连接矩阵 的 行相加，判断站点B所在的列是否大于0，如果大于0，说明 ，然后再具体判断B所在的集合，否则说明 ， 不是A到B的步行直达线路。

5.3.2步行换乘一次数学模型算法设计

(1)输入乘车的起始站点A及终到站点B；

(2)任取站点 ，任取经过C的一条线路 ，设C在 上可到达的站点为： ；任取站点 ，任取经过D的一条线路 ，设 为线路 上可到达站点D的所有站点，对每一个 判断是否属于 。若 ，则 与 为A到B的步行换乘一次线路。此时，若A=C， ，D=B同时成立，则步行次数为0；若其中两个等式成立，步行次数为1；如果只有一个等式成立，步行次数为2；否则，步行次数为3。若 ，则转下一步；

(3)对所有 进行搜索，对经过站点D的所有线路 进行搜索，对 中的所有站点进行搜索；对经过站点C的所有线路 进行搜索，对 中的所有站点进行搜索。

6.模型求解与检验

使用2007年高教社杯全国大学生数学建模竞赛B题中的数据，对模型进行Matlab编程求解，所得结果见下表。

表：模拟结果

模型输入 直达线路 换乘一次 换乘两次 地铁线路

(1)3359-1828 无 101分钟(3元) 73分钟(3元) 84.5分钟(5元)

(2)1557-0481 无 无 106分钟(3元) 116.5分钟(5元)

(3)0971-0485 无 128分钟(3元) 106分钟(3元) 96分钟(5元)

(4)0008-0073 无 83分钟(2元) 67分钟(3元) 53.5分钟(5元)

(5)0148-0485 无 无 106分钟(3元) 87.5分钟(5元)

(6)0087-3676 无 65分钟(2元) 46分钟(3元) 30分钟(3元)

最佳线路不唯一，换乘两次的线路更多一些，比如：(1)3359-1828换乘两次的最佳线路(都是73分钟，3元)，共106条线路。下面是部分结果：

(1)S3359-S1828

L015下行 L201上行 L041上行

S3359 S2903 S0458 S1828 3元21站(73分钟)

40 41 6 22 10 14(站点位置)

(2)S1557-S0481

L084下行 L189下行 L460下行

S1157 S1919 S3186 S0481 3元32站(106分钟)

27 39 19 22 16 33(站点位置)

(3)S0971-S0485

L094上行 T1 L051上行

S0971 S567 D1 D21 S466 S0485 5元31站(96分钟)

25 31 1 21 26 31(站点位置)

(4)S0008-S0073 5元13站（53.5分钟）

L200上行 T1 T2 L103上行

S0008 S2534 D15 D12 D25 S525 S0073

2 8 15 12 4 2 2 4(站点位置)

(5)S0148-S0485

L024下行 T1 L051上行

S0148 S1487 D2 D21 S466 S0485 5元28站(87.5分钟)

17 21 2 21 26 31(站点位置)

(6)S0087-S3676

T2

S0087 D27 D36 S3676 3元8站(30分钟)

5 15 (站点位置)

7.模型的评价与改进

7.1模型与算法的优点

（1）通过构造线路与站点、站点与站点的连接矩阵，大大缩短了程序运行时间，能基本满足自主查询计算机系统的需要。获得直达、一次换乘与地铁最佳线路的运行时间都可在瞬间完成；如果没有一次换乘线路，获得两次换乘最佳线路的平均时间为1分30秒（S1557-S0481运行时间1分18秒；S0148-S0485运行时间1分32秒）；若存在一次换乘线路，特别在一次换乘线路较多时，获得两次换乘最佳线路的运行时间较长，但一般不超过5分钟（S3359-S1828运行时间4分23秒；S0971-S0485运行时间4分56秒；S0087-S3676运行时间1分2秒；S0008-S0073运行时间26分49秒）。

（2）能够生成多条备选路径供出行者选择，满足了不同查询者的需求。

（3）详细分析了公汽环行线路、通过地铁站点换乘等复杂情况。公汽环行线路中存在多个双位站点（直行线路中也可能存在双位站点），即同一站点在线路中有两个位置。为了精确计算出行时间，分情况进行了讨论：①双位站点为起始站点。当终到站点在线路中的位置介于两双位站点之间时，双位站点的位置取较小的，否则取较大的位置；②双位站点为终到站点。当起始站点在线路中的位置介于两双位站点之间时，双位站点的位置取较大的，否则取较小的位置。通过地铁站点换乘计算出行时间时，若换乘公汽站点相同，线路相同，出行时间为公汽直达时间；若换乘公汽站点相同，换乘公汽线路不同，出行时间为公汽一次换乘线路的出行时间；若在同一地铁站点换乘，换乘公汽站点不同，出行时间为公汽直达时间，加上通过地铁换乘的时间；若在不同地铁站点换乘，出行时间为公汽线路与地铁线路的直达时间，加上公汽换乘地铁、地铁换乘公汽的时间。

（4）只需对数据库进行部分修改与添加，所有程序稍加修改，即可适应公交线路的变化。

7.2模型与算法的缺点

在一次换乘线路较多时，获得两次换乘最佳线路的时间较长。这可能与Matlab程序执行效率较低有关。

7.3模型与算法的改进

（1）继续讨论不太容易想到的细节问题；

（2）尝试使用其它算法程序进行求解；

（3）查找数据资料，对模型三进行求解与检验。

参考文献:

[1].闫小勇,牛学勤等.公交网络多路径选择启发式算法研究[L].城市交通.2005, 3(3):23

[2].张　海,余玛俐等.城市公共交通数据库查询算法的实现[L].计算机与现代化.2006,136(12):60

[3].苏爱华,施法中,公交网络换乘问题的一种实现[L].工程图学学报.2005(4): 55

[4].梁虹,袁小群,刘蕊.一种新的公交数据模型与公交查询系统实现[L].计算机工程与应用.2007,43(3):234

[5].姜启源,数学模型（第三版）[M]高教出版社

[6].李丹,曲玉萍,王晓燕.城市公交出行系统中最优路线算法研究[L].交通标准化.2005,147:122

[7].李擎,宋顶立等.两种改进的最优路径规划算法[L].北京科技大学学报.2005, 27(3):367

[8].翁敏,毋河海等.基于公交网络模型的最优出行路径选择的研究[L].武汉大学学报.2004,29(6):500

[9].陆忠,钱翔东,张登荣等.基于最短路径查询的城市公交网络拓扑建模研究[L]. 遥感信息.2002(1):11

[10].朱江云,王玉琨.基于最小换乘次数的最优路径算发[L].福建电脑.2007(3): 121