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

公交查询系统的最佳乘车方案研究与设计摘要本文要求设计一个公交线路计算机自助查询系统，针对不同需求的出行者推荐相应的最佳路线。这是一个多目标决策的网络优化问题，并且随着问题的深入逐层递进，我们建立了三个多目标优化模型解决此问题。针对问题一，将三种不同的公汽线路抽象化，建立站点间直达线路信息存储元胞结构。调查分析得出，尽管乘客对公交线路的需求侧重点各有不同，但都包括乘车次数少、时间短、费用少和拥挤程度低，以前三个量为目标，拥挤程度为约束，建立多目标整数规划模型，根据多目标分层序列法，出于对乘客不同需求的考虑，采用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→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2.问题假设假设一：各路线公交车发车频度相同；假设二：相邻站点间平均行驶时间一定；假设三：公交运行顺畅：无交通阻塞、无车辆故障、无道路交通事故等意外情况；假设四：公交准点到达，不考虑红绿灯等待时间；假设五：乘客在起始站时不考虑拥挤程度，只在转乘时考虑拥挤程度；假设六：乘客到起始站乘车时，不考虑等车时间；假设七：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，在此换乘过程中不考虑换乘时间和费用。3.符号说明ijL站点之间的最小换乘次数ijV实际换车次数ijP从站点i到站点j的费用ijPijS表示站点i到站点j经过的站点数目ijn表示从起始站startp到终点站endp的站点数ija表示从站点i上车时站点i距离startp的站点数AijZ表示从起始站i到终点站j公汽换乘公汽的次数BijZ表示从起始站i到终点站j公汽换乘地铁的次数CijZ表示从起始站i到终点站j地铁换乘公汽的次数DijZ表示从起始站i到终点站j地铁换乘地铁的次数ijt站点i到站点j的步行时间T邻近站点的时间上确界0t任意两个邻近站点平均步行时间t表示邻接公汽站点间的步行时间4.问题分析这是一个多目标决策的网络优化问题。公交查询系统需要满足查询者各种不同需求，给出最优方案，这是我们建立模型的根本出发点，有关问题的求解随着规模扩大将逐层深入。对于问题一，题目给出的公汽线路主要分为上下行线、原路折回线及环行线，线路不同，选择不同，故对每种线路需要进行抽象化处理。站点较多，信息量较多，需要选择合适的存储方法存储数据，存储题中的线路名、车号和时间。解决这些问题后，就要对乘客的出行需求进行调查，看看乘客出行时主要考虑哪些因素，根据调查结果可以选定主要的需求建立多目标规划模型。本题数据量较多，一般的算法可能不能处理，所以要探索合适的算法，然后用MATLAB软件编程求解，可以求出不同需求的出行者相应的公交路线。对于问题二，在问题一的基础上更进一步探讨同时考虑公汽和地铁线路的情况。我们同样需要对地铁线路进行抽象化处理，基于假设七，同一地铁站与邻接的公汽站可以进行归一化处理，因为这些站点间的换成无需支付地铁费并且时间可以忽略不计，还要将地铁站相关信息和公交站相关信息合理存储。根据问题一中的乘客需求，同样建立多目标规划模型，但由于有了地铁这种出行方式，在乘车费用与车辆换乘方面有所不同。设计合适的算法，编程求解得到不同需求的乘客相应的最优路线。对于问题三，该问在问题二的基础上增加考虑步行对最优路线选取带来的影响，可以把步行作为另一种交通工具进行考虑。根据实际情况对步行相关信息做出合理的假设，由于步行这种出行方式不花费时间，对换乘次数以及换乘方式都没有影响，只改变出行时间。所以在问题三中，我们对出行时间优先考虑，再考虑换乘次数和乘车费用，同样建立多目标优化模型，运用MATLAB编程求解得到任意站点间的最佳路线。5.问题一的解答问题一仅考虑公汽线路，我们建立了模型一进行求解。5.1问题一的数据处理5.1.1三种公汽线路的处理根据题中信息，我们知道公汽线路分三种，下面将这三种线路进行数据处理：下行线是上行线原路返回这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列,只是线路的方向不同；上行线与下行线的站点名不完全相同这种线路与下行线是上行线的原路返回不同，下行线与上行线经过的站点不完全相同，但是起始站和终点站相同；线路为环形线12345612345678对环形线路的站点进行分析，把一个环形拉成一条直线，以该直线的终点为对称点进行翻折，将终点左边的直线对称到右边，形成该直线的延长线，如下：这种环形线原有的路线包括：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)：23124321314图(1)：居民出行需求结果的统计我们可以看到，出行者对不同因素的看重比例是不同的，该市居民出行需求对于北京这样的大城市也同样适用。由于一般情况下路程长短和所用时间是密切联系的，乘客关注路程也是为了节约时间，所以问题中已经将路程的相关信息转化成为时间了，即只需考虑时间最短。因此我们的模型中对公交网络的优化需要考虑四个主要优化目标：换乘次数最少，时间最短，费用最少，拥挤程度最低。5.2.2换乘次数的抽象根据公交线路的设计，尽管起始站和终点站位置相同，也可能有多种乘车方式，这些乘车方式中可能是直达的，也可能要转乘一次，也可能需转乘两次，或三次及三次以上，以startp表示起始站，endp表示终点站，那么某乘客从startp到endp的几种乘车方式如下：直达的示意图换乘一次的示意图换乘两次示意图startp中转站一中转站二endp如果公交线路设计合理的话，那么几乎所有的站点均可以在转成两次以内达目的地，而且乘换次数过多，容易使乘客产生烦躁情绪，需要更长的时间和更多的费用；因此在设计算法时，只搜索直达、换乘一次和换乘2次的乘车方案。5.2.3计算机系统自主查询路线的流程通过上述调查显示的统计结果得知，乘客乘车都会考虑换乘次数，时间，费用以及拥挤程度的问题，但是不同的乘客对这些需求考虑的先后次序不同，比如：度假的乘客，一般会首先考虑乘车时间；所带行李较多的乘客，一般会首先考虑拥挤程度和换乘次数等。一般情况下，人们往往会选择直达，也就说如果两站点之间有直达车辆，乘客会选择直达。由于直达的车辆不止一辆，可以根据不同乘客的需求，选择相应的最优方案。当没有直达车辆时，乘客可以根据自己不同的需求，选择属于自己的最优路线。根据上述分析，我们构建的公交线路选择问题的自主查询计算机系统应该考虑不同乘客对不同需求的重视程度，根据上述分析，公交线路自主查询系统的流程如下图(2)：图(2):公交线路自主查询系统的流程图5.3模型一的建立我们要建立如图(2)所示的公交线路自主查询系统，就要对不同行程需求的乘客推荐相应的最佳路线，根据实际情况可以确定三个目标，分别为：换乘次数，乘车时间，乘车费用。结合数据处理中的实际情况，不同的乘客对不同需求的重视程度不同，所以对于不同的乘客，我们要给出相应的最佳路线，从三个方面综合考虑，分别给出优先考虑乘换次数以及优先考虑乘车时间的最优推荐路线。我们考虑运用多目标优化设计的分层序列法建立模型，进行求解，在此引入多目标分层序列法。多目标分层序列法：将k个目标函数按重要程度排序12,,,nkkk，其中1k的优先级最高，应该首先得到满足，其次是2k，直到得出满足所有的目标函数的解，或是此时的解只有一个。根据实际情况，可以根据多目标优化设计的分层序列法对我们建立的三个目标函数的顺序进行调整，得到不同乘客所对应的不同的最佳路线。当满足这些目标的路线不止一条时，我们选取离始发站最近的解，因为离始发站越近，公交的拥挤程度相对越小。当以某个目标函数作为第1k个目标函数，即决策变量时，只需将该目标函数的顺序进行调整，使之成为第1k个目标函数。当目标函数有三个时，排序后共有六种可能的情形，但不是每种情形都要考虑。根据调查结果，我们确定了乘客出行时考虑较多的三种类型，在此分别称为策略一、策略二和策略三。策略一：按换乘次数最少、乘车时间最短、乘车费用最少的顺序考虑；策略二：按乘车时间最短、换乘次数最少、乘车