公交查询系统的最佳乘车方案研究与设计(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也相应的有三种不同的选择：不换乘地铁、换乘公

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库公交查询系统的最佳乘车方案研究与设计(3)在线全文阅读。