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

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

摘要

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

针对问题一，将三种不同的公汽线路抽象化，建立站点间直达线路信息存储元胞结构。调查分析得出，尽管乘客对公交线路的需求侧重点各有不同，但都包括乘车次数少、时间短、费用少和拥挤程度低，以前三个量为目标，拥挤程度为约束，建立多目标整数规划模型，根据多目标分层序列法，出于对乘客不同需求的考虑，采用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)：

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

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/8pe2.html