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

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

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分钟，而且费用也减少了一元。所以出行时，适当的选择步行是一种很好的方式。

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