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

图(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；

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