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

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

摘要

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

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

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