公交查询系统的最佳乘车方案设计(含程序)

来源：尚车旅游网

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

摘要

本文研究的问题是针对已知的公交线路信息如何设计出最佳的乘车方案。首先，进行数据处理，用excel建立起公交线路矩阵。

然后，上网查阅了公交乘客乘车心理分析的资料，得出影响乘客出行的三个主要因素依次为为：换乘次数、出行时间、出行费用

随后，建立了站点—线路序列模型。利用公交乘客的出行过程抽象为站点—线路的交替转换的思想，从而确定了出行者出行路线的一般数学表达式。针对问题一，仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标、乘车费用为第三目标，建立起多目标最优化分层求解模型。并依靠站点—线路序列模型确定的出行线路表达式，采用图论中计算方法并结合广度搜索法经matlab编程(见附录一) 得到了公交乘客的最少换乘次数，所经过的站点，出行时间、出行费用(见表1)。

针对问题二，在问题一的基础上考虑了地铁线路，处理的方法是将地铁线当成特殊的公交线，将地铁站点当成公交站点并与给定的公交站连接。按照问题一的模型和算法得到乘客的最少换乘次数，出行时间、出行费用(见表2)。针对问题三，在问题二的基础上考虑了所有站点之间的步行时间，由成人步行速度估算出该时间大小。步行线路与公汽线路相同但每条均有上行和下行。将步行线路矩阵与公交线路矩阵整合后按照问题二的算法得到乘客的最少换乘次数，出行时间、出行费用(见。

最后，建立公交负载模型对前三问的模型进行了改进。考虑到了实际中公交线路堵车的情况，将堵车线路拆分为两段新的线路并相应改变公交线路矩阵。算法与前三问算法相同，但使得最佳路径的选择更加灵活且更符合实际情况。

关键词：分层求解交替序列多目标最优化改进广度搜索法

1问题重述

问题背景

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

需要解决的问题

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：

问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 问题二：同时考虑公汽与地铁线路，解决以上问题。

问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

2模型的假设及符号说明

模型假设

假设1：假设乘客都是理性乘车且能顺利到达目的地

假设2：假设不考虑红绿灯造成的等待时间，不考虑堵车，车祸等因素假设3：假设乘客能接受的最大换乘次数为2次假设4：假设乘客乘车过程中不能2次经过同一站点。假设5：假设公交与地铁换乘距离固定，换乘步行时间为常数

符号说明

符号说明 S S公汽站点集，SS0001,S0002,,S3957 L表示公汽线路集，LL001,L002,,L520 D地铁站点集，DD01,D02,,D39 T表示地铁线路集，TT1,T2 vik出行者选择第i条公交线路所经过的第k个站点(vikS或vikD) L D T vik Pik Pik出行者选择第i条公交线路所乘坐的第k辆公交工具(PikL或PikT) Ni Si ti Qi 换乘次数途经的车站数行程时间所需费用 3问题分析

本文研究的问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑，以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。

针对问题一：问题一要求只考虑公汽线路，给出最佳路径。通过查阅相关资料，知道对乘客影响最大的三个因素：换乘次数，行程时间，所需费用(重要性

从大到小)。据此，我们建立以换乘次数为第一目标，行程时间最为第二目标，所需费用为第三目标的多目标最优化模型。对于换乘次数，联系被选择线路上的站点—线路交替序列TRi个数可以表示出来；站点总数则采用给同一线路上的站点排序的方法也可以求到，由于只考虑了公汽之间的换乘，则出行时间只与换乘次数和所历站数有关；对于出行费用则在换乘次数的基础上，引入分段计价的加价函数也可求得。

针对问题二：问题二在一得基础上考虑可以搭乘地铁，乘客的选择更加灵活。主要变化为：地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少；地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费耗时换乘到下一个公汽站。我们可以把跨公交站的步行视为一种免费耗时的交通方式，据此分层求解。

针对问题三：考虑到出行者在步行时，所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知，步行时所经过的两站点之间的步行时间是一个已知值。当换乘的两站之间站数不多时，我们考虑步行，这要可以减少换乘次数，节约金钱。

4数据处理及分析

数据处理 4.1.1数据统计

我们运用Excel软件对给的“公汽线路信息”和“地铁线路信息”进行统计得到如下数据：

表1

公汽线路分段5

站点数环形公汽地铁站地铁线路直行线环形线单一上下行路上下行路计价票价径不同 409条径相同 89条路线站点 22条 3957个点 39个路 1条路 1条 283条 237条公交系统共有公汽线路520条总站点3996个地铁线路共2条根据表一并结合本文参数设定中的票价信息，综合考虑，分析如下：在分段计价路线中，共有27条的公汽站点数不超过20，有148条的公汽站点数在21~40之间，公汽站点数超过40的线路有108条。因此，从单独的计算角度来考虑，可以将分段计价中站数不超过20的线路归为单一票制1元的线路，因此上述信息可修正为：票价信息为单一票制1元的线路264条；在分段计价的路线中，共有256条，其中有148条的公汽站点数在21~40之间，公汽站点数超过40的线路有108条。 4.1.2数据的储存与处理

由于所给的数据格式不利于程序软件直接读取和操作，我们运用Excel将数据处理为规范格式，建立起公交线路矩阵A。

(1)把公汽线路信息以及地铁线路信息分别导入到Excel表格中

(2)将公汽数据中的上下行相同、上下行不同、环行的线路分别找出并归类。 (3)将上下行相同的上行序列倒序后作为下行序列。则每条线路对应两个行向量。 (4)环行线路若有n个站点，则依次以每个站点为起点和终点建立起n条首位相同的线路序列。

(5) 在第k条线路对应的所有序列前加上数字k作为标记列，其意义为第k条路线。 (6)运用Excel的查找替换功能将公汽站点编号“S”和地铁站点编号“D”分别用0和111代替。目的是为了在汽车站和地铁站区别的条件下让matlab可以识别和进行矩阵操作。

(7)将所有的序列整合到同一个excel表中，建立交线路矩阵A，每一行储存一条线路站点信息，没有信息的点用“0”填充。公交线路矩阵A

v11v21Avn1v12v22vn2v13v23vn3v1dv2dvnd... 建立交线路矩阵A后，我们可以把矩阵A导入MATLAB中，运用改进广度搜索算法求解最佳路径。

5模型的准备

乘客心理调查

北京公交车线路达800条以上，每一个公交站点可能有多条线路贯穿，通往不同的起点或终点，同样，一个目的地也可由多条线路到达，错综复杂的公交车路线犹如网状般将各站点联系起来，将城市的行人们带到其各自的目的地。

我们通过互联网查阅相关资料发现，影响乘客公交线路的选择，主要有以下几个因素：换乘次数，行程时间，所需费用，途经的总站数等。

其中有%的乘客出行时，首先考虑的是乘车费用，%的乘客首先考虑的是行程时间，42%的乘客首先考虑的是换乘次数。

图1：乘客出行调查图

45.00%40.00%35.00%30.00%25.00%20.00%15.00%10.00%5.00%0.00%所需费用行程时间换乘次数其它

就乘客本身而言，公交乘客出行更多考虑的是出行的方便性和舒适性，下

面就影响公交乘客出行的各因素进行具体分析，不妨将以上影响因素作如下归纳解释：

(1)换乘次数：出行者完成一次从出发点到终点出行过程中所换车的次数。 (2)行程时间：出行者在一次乘公交出行过程中所用的总时间。 (3)所需费用：出行者在完成一次由起点到达目的地过程中所花的车费。 (4)途径的总站数：出行者完成一次出发点到终点过程中所经过的车站总数

影响选择因素分析

“换乘次数”和“行程时间”是影响出行者的两个独立的因素，经研究表明多数的公交乘客希望换乘次数最少，况且公交公司对公交线路的设计也是尽量减少乘客的平均换乘次数；而且公交乘客出行时还受到行李、地理位置等客观因素的影响，这样更不希望有较多的换乘。其次对于看奥运非常心切的出行者来讲，出行耗时对他们也是比较关键的。在此当给出供乘客选择的公交路线也应当尽可能的满足公交乘客的需求。当然，在此基础上我们还要考虑乘车费用。

综上所述，可以以换乘次数最少为第一目标，再选择易于量化的“出行时间”和“所需费用”作为第二位的优化目标。由此，我们认为，乘客在选择路线时，可以根据自己的不同需求，对线路进行选择。

最优乘车方案算法分析

在站点上放置一个便于乘客查询到达目的地的理想乘车方案的计算机系统，必须让计算机收集到本站到其他任意一站的路径与换乘信息，因此单独设计这样的算法是相当困难的，而且算法的精度要求也比较高。对本文附件中的公交系统中所列的3957个公汽站点和39个地铁站点来说，直接要得到所有任意两站点之间的最优公交路径的计算量是相当大的。当面对这样一个密集的交通网络来说，对路线的选择主要是将面临一个P类问题，根据P类问题的处理特点，可以用某种主次改进的方法来求解。由于每次改进中的计算量都是多项式界的，改进的次

数也是多项式界的。目前已找到具有这种特性的算法，如椭球算法，卡马卡算法，但都相当复杂。因此要满足出行者的路线需求，则有必要对目标进行归类筛选，以降低不必要的选择、计算与搜索。不妨采用改进的广度优先搜索算法，基于改进次数为多项式界的算法理论，本文选择从某次乘公交的起点和终点的两端进行同时搜索，在满足换乘次数最少的条件下寻找不同线路中的共同站点或不同站点之间的相同线路，并计算其总路线的中的乘车时间和站点数。

6站点—线路交替序列模型的建立

模型的建立

本文所要解决的根本问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑，以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。

我们建立交替序列模型寻找最优线路。

6.1.1模型的预处理

出行者所选择出行的起始站为v0，终到站为vd，从v0到vd的所有路径的集合也为TR，其中第i条路径为TRi，所乘坐的第k节公交工具为pik。进一步分析和考虑出行者乘公交的具体情况，一个出行者的出行可简单描述为如下路径

图2：出行者选乘公交路径规律分析示意图

选择路线起始站出发离开公交终到站结束

第Ni次换乘选乘初次车乘第1节公交中转站1 第1次换乘乘第2节公交中转站2 第 2次乘第Ni+1节公交中转站Ni 乘第3节

…… 中转站3

从图中内容也可以反应，出行者出行乘公交的路径可看着是站点、车次、站

点、车次的交替进行，直至到达终到站。为区别前后的车次或站点，使得前后排列的站点与车次都有一定的顺序，由于出行者不能在同一站点上出现两次，即

vik各不相同，特别地令vi0v0，viN1vd；

i6.1.2交替序列的表示

分析可知，选择线路上的站点—线路交替序列TRi为：

其中站点—线路交替序列TRi表示从起始点v0选择线路pi1到达vi1，换乘pi2

到达vi2，……，最终到达vd的第i种路径。

起始站v0到达终到站vd的公交线路选择集TR，即：

TRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd

对于乘客而言，我们只要知道他的出行起始站v0和终到站vd之后，便可以

TRiv0,pi1,vi1,pi2,vi2,,vd在路径集TR中找到他最需要的出行路线。本模型对路线的选择范围确定了界限，这样也明确了寻求最优线路的讨论范围，即搜索的路径(公交线路pik)和节点(公交站点vik)都是相互关联的。

7问题一的解答

多目标最优化分层求解模型的建立 7.1.1确定目标函数

本文所要解决的根本问题最佳乘车路线的设计问题。建立以换乘次数Ni为第一目标，再选择易于量化的“出行时间ti”作为第二目标的多目标最优化模型。

minNiminti minQi为了便于求解我们定义目标函数U表示以Ni为第一目标，ti作为第二目标

Qi作为第三目标：

minU(Ni,ti,Qi)

TRi7.1.2确定约束条件

1.目标函数U最小时，换乘次数和乘车时间也要求最小，因此U与Ni及ti

是正相关的。

UU0,0. titi2. 由于在优先选择权上，按相应条件，在目标函数U(Ni,ti)中，Ni应优于ti，

UU Niti7.1.3相关变量的确定

求解Ni取最小值时，再进行其它变量的确定与计算，才能选择到相应的目标。即需要在可行域TRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd中进行优先性的条件搜索。

I换乘次数

设Ri表示有序集TRiv0,pi1,vi1,pi2,vi2,,vd中的元素的个数，为便于区别，现标记RiCardTRi，换乘次数可表示为

iNiRi112

II所通过的总站数

设非环行线路pik上的两个站点vik1和vik在沿着公交工具行进方向上的站数按照正整数从小到大的排序分别为k(pik,vik1)和k(pik,vik)，其中仍然记

vi0v0；viNi1vd，于是由数据处理中的相关统计结果可知：

min(k(pik,vik))k(pik,vik1)k(pik,vik)max(k(pik,vik))

当线路pik为环行线路时，设该环行路线上的总站数为Kik，vi1为pik上的任意一站，vi0，vi2分别为公交工具在沿着pik行进方向上的最后一站和前一站，于是可标记

k(pik,vi0)Kik；

k(pik,vi1)1；

k(pik,vi2)2；…；

k(pik,vij)j；…

所以出行者乘坐pik线路的公交所经过的站点数目为：

pik为非环行线路；k(pik,vik)k(pik,vik1)pik(vik1,vik)k(pik,vik)k(pik,vik1)Kikpik为环行线路.

所以，出行者途经的总站数为共条行车路线上车站数的总和，即

SiNi1k1pik(vik1,vik)

III乘客所用时间

设出行者选择第i条线路从起始站v0到达终到站vd所耗的平均总时间为ti，换乘一次所耗的平均时间为to=5分钟，相邻两站点之间乘车的平均时间为to=3分钟。则有

*tit0Nit0(Si1)

IV乘车总费用

公汽线路上的单一制票价为1元，分段计价的票价标准为出行者通过本线路0~20个站：1元；21～40站：2元；40站以上：3元。公汽的单一票价为Qi0，出行者在所选择的出行线路中所应支付的车旅费为Qi，所乘同一公交线路上的最高收费为Qi1，分段计价时加价的最少站数为L0，于是有：

pik(vik1,vik)QiQi0(Ni1)L(pik)min，Qi11

Lk10Ni*Qi01Qi13（元）其中A表示取不超过A的最大整数，参数：（元），，L020.

0线路pik为单一票制线路；L*(pik).1线路pik为分段记价线路

综上所述，对问题一建立多目标优化分层求解模型

minU(Ni,ti,Qi)

TRiTRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd;TRi;RiCardiNRi11;i2Ni1 s..tSipik(vik1,vik).k1*tit0Nit0•(Si1)Npik(vik1,vik)QQNiL*(p)min，Q1i1i0iikiLk10模型的求解

7.2.1线路的抽象处理

从A站到B站的行车路线时，首先考虑是否有经过A站直接到达B站。如果存在不只一条的直达线路，在考虑所走路线的远近，选择距离最近的乘车方案；如果没有直达车，就会考虑换一次车的方案。即经过A站的车与经过B站的车是否有公共站点C。如果有，则可在公共站点C处转车到达站点B。如果没有换一次车的方案，则又要考虑乘坐经过A点的车到某一站C下车，经过C站点的车与经过B站点的车是否有公共站点D，如果有，就到公共站点D转车，两次转车可到达站点B；如果没有，则需要转乘三次或三次以上才可到达目的地。在上述情况中如果存在不止一种的选择方案，则在考虑乘车距离，选择路程最短的乘车方案。

x C A

A B

A C D C D B A B

(a)直达的情况 (b)换乘一次车的情况 (c)换乘两次车的的情况 (d)换乘多次车的情况

图2 公交线路换乘方案示意图

运用matlab求解如下（具体程序见附录一）

表1问题一的结果

换乘次路径数 L436L167S3359S1784S1828 时间(分) 95 97 122 77 97 59 费用(元) 3 3 4 2 3 2 总站数 33 33 42 27 33 21 1 2 1 1 2 1 L084L189460S1557S1919S3186S0481 L013L485S0971S2184S0417 L159L474S0008S0400S0073 L308L156L417S0148S0036S2210S0485 L454L209S0087S3496S3676 结果分析

我们以换乘次数为第一目标，假设乘客可以接受的换乘次数不超过2次，将问题简化。只考虑乘公汽，所求的6条路径没有直达的其中第1，3,4,6条要换乘一次；第2,5条路径要换乘2次。

8问题二的解答

多目标最优化分层求解模型的建立

8.1.1确定目标函数

问题二在问题一的基础上考虑可以搭乘地铁。乘客的选择更加灵活。其主要变化的因素有：1地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少

2地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费换乘到下一个公汽站。

minU(Ni,ti,Qi)

TRi8.1.2确定约束条件

UUUU0,0, titiNiti8.1.3变量的确定

当并入地铁公汽的交通网络时，增加地铁站与其周围的公汽站之间的步行线连接转换后，本问题可转化为问题一中的模型求解，同样有出行者通过公汽换乘、地铁换乘、公汽与地铁之间的换乘后从起始站v0到达终到站vd的可行路径集为：

其中pik的属性将被扩大，它将表示公汽、地铁、步行这三类交通路线中的某一类交通路线；而vik的含义与问题一中vik的含义相同，仍表示公交站点或地铁站点。

I换乘次数与途经总站数

同样设路径TRi的换乘次数为Ni,途经总站数为Si，同问题一对Ni，Si仍然有：

TRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd15

Ni1Ri1RiCardTRi,Ni1,Sipik(vik1,vik)

i2k1II出行者乘公交所用时间

在地铁——公汽的公交系统中，出行者将会表现在公汽运行耗时，地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时。为简化变量，考虑出行者的异站步行也纳入到公交线的行列中，则所消耗的时间可归结为：交通工具运行耗时，交通线路换乘耗时两类。

设出行者从起始站v0到达终到站vd所用的总时间为ti，从公交站点vik1乘

pik线路公交工具到达公交站点vik所消耗的时间（包括相邻两站点间的停站时

间）为：t(vik1,vik)，由pik线路的公交工具换乘到pik1线路的公交工具所消耗的时间为：t(pik,pik1) ，由基本参数设定的信息可得：

tiNi1k1pik(vik1,vik)t(vik1,vik)t(pik,pik1)k1Ni

其中

vik1S;vikS；32.5vik1D;vikD；t(vik1,vik)7vik1D;vikS；

vik1S;vikD；60其它.4t(pik1,pik)50IV乘车总费用

pik1T;pikT；pik1L;pikL；其它.

在问题二的讨论中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，而在本问题中，有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，同样根据问题一中，对乘公交

所支付费用的讨论思想，仍然令乘坐公汽的单一票价为Qi0，出行者在所选择的出行线路中所应支付的车旅费为Qi，所乘同一公交线路上的最高收费（含地铁收费）为Qil，分段计价时加价的最少站数为L0，于是有：

pik(vik1,vik)QiQi0N（pik,pik1）L(pik)min，Qi11Lk1k10NiNi*

其中参数：Qi01（元），Qi13（元），L020 A表示取不超过A的最大整数；

线路；0线路pik为单一票制线路或地铁L*(pik).1线路pik为分段记价的公交线路

1pikL,pi1LN(pik,pik1)3pikT,pik1T0其它

综上所述，对问题二建立多目标最优化分层求解模型

minU(Ni,ti,Qi)

TRiTRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd;RCardTR;iiiR1Nii1;2Ni1s.t Sipik(vik1,vik).k1Ni1Nitipik(vik1,vik)t(vik1,vik)t(pik,vik1);k1k1NiNipik(vik1,vik)QiQi0N(pik,pik1)L*(pik)min，Q1i1Lk1k10L020;Qi13;Qi01.17

模型的求解 8.2.1设计算法

1输入乘车的起始站点A及目的站点B；

2求经过站点A的所有线路集S(I)和经过站点B的所有线路集T(J)； 3判断S(I)=T(J)

如果有，则找到了从站点A到站点B的直达线路S(I)即T(J)，输出结果，结束运算，如果没有则进行下一步。

4求线路S(I)上的站点E(I,U)以及线路T(J)上的站点F(J,V)；

5判断是否存在相同站点，即E(I,U)=F(J,V)，或者存在紧邻站点，即满足

t(E,F)w；如果满足E(I,U)=F(J,V)，则线路S(I)，T(J)即为一次转车的线

路，E(I,U)即为转车站点且换车时不用更换站点；如果满足E(I,U)F(J,U)但满足t(E,F)w，则线路S(I)，T(J)即为一次专车线路，E(I,U)即为转车站点但换车时要步行到紧邻站点F(J,V)。如果没有，再执行下面步骤。

6求经过E(I,U)的线路集R(K)，经过F(J,V)的线路集Y(O)；

7判断R(K)=Y(O)吗如果有，则线路S(I)，R(K)，T(J)为两次换车的线路，换车站点为E(I,U)和F(J,V)，输出结果，结束运算；如果没有则执行下面步骤。

8求线路R(K)上的站点G(K,W)和线路Y(O)上的站点L(O,X)；

9判断是否存在相同站点，即G(K,W)=L(O,X)，或者存在相邻站点，即满足t(G,L)w；如果满足G(K,W)=L(O,X)，则线路S(I)，R(K)，Y(O)，T(J)即为三次转车的线路，E(I,U)，G(K,W)，F(J,V)即为转车站点，且换车时不用更换站点；如果满足G(K,W)L(O,X)但满足t(G,L)w，则在站点G(K,W)专车时要步行到紧邻站点L(O,X)。

算法流程图

开始获取起点和终点 S(I)T(J) 假 E(I,U)F(J,V)ord(E,F)w假 R(K)Y(O)假 G(K,W)L(O,X) ord(G,L)w真真真真输出S(I),R(K),Y(O), 输S(I),T(J), 出输出S(I),R(K), T(J)E(I,U)F(J,V) T(J),E(I,U),G(K,W), L(O,X),F(J,V) 选择换乘次数最少且花费时间最短的乘车结束

运用matlab求解结果如下（具体程序见附录二）

表2问题二的结果

路径换乘次时间费用19

数 L436L167S3359S1784S1828 (分) 95 97 122 77 97 (元) 3 3 4 2 3 3 1 2 1 1 2 0 L084L189460S1557S1919S3186S0481 L013L485S0971S2184S0417 L159L474S0008S0400S0073 L308L156L417S0148S0036S2210S0485 T02S0087D27D36S3676 结果分析

对比问题一与问题二的求解结果可知，前面5条路线求解的最佳路径是一样的，原因在于在换乘次数和行程时间差不多的情况下，地铁较贵为3元。所以，这种情况下，尽量不乘坐地铁。比较第6条路径，我们发现乘坐地铁使得行程时间大大缩短，并且由于地铁站和起始站在一起，乘坐地铁不用换乘。故考虑地铁后，第6条路径大大优化。

9问题三的解答

多目标最优化分层求解模型的建立 9.1.1确定目标函数

考虑到出行者在步行时，所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知，步行时所经过的两站点之间的步行时间是一个已知值。据实际情况，假设步行者步行在相邻两公汽站所用

时间平均是公汽经过这两站（包括停站时间）所用时间的k倍，则由基本参数设定可知，步行者通过这样两站点所用的平均时间为3k分钟，于是将行人步行所经过的线路也纳入到公交线路中，其特点是费时费力但选择灵活。

minU(Ni,ti,Qi)

TRi9.1.2确定约束条件

UUUU0,0, titiNiti9.1.3确定变量

设出行者以步行、乘公交、换乘等任意的出行方式从初始站V0到达终到站

Vd的可行路径集为：

TRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd，

其中，上式中的pik、vik都与问题二中pik、vik的含义分别相同， I换乘次数、途经总站数

设该路径TRi的换乘次数为Ni,途经总站数为Si，仍然有

NiNi1k1Ri112

ikSip(vik1,vik)

II出行者乘公交所用时间

在步行—地铁—公汽的公交系统中，出行者将会出现公汽运行耗时，地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时，公交站点之间的步行耗时。同样考虑出行者的异站步行纳入到公交线的行列中来简化变量，则所耗时间仍然可分

为：交通工具运行耗时（包括步行耗时），交通线路换乘耗时两类。

同样设出行者从起始站v0到达终到站vd所用的总时间为ti，从公交站点vik1乘pik线路公交工具到达公交站点vik所消耗的时间（包括相邻两站点间的停站时间）为：t(vik1,vik)，由pik线路的公交工具换乘到pik1线路的公交工具所消耗的时间为：t(pik,pik1) ，则由基本参数设定的信息可得：

Ni1tipk1ik(vik1,vik)t(vik1,vik)t(pik,pik1)

k1Ni其中

32.57t(vik1,vik)63k0vik1S,vikS；vik1D,vikD；vik1D,vikS；vik1S,vikD；vik1S,vikS,pik1L,pikT;其它.

k为公汽行进时是出行者步行时的平均倍率。

4t(pik1,pik)50III乘车总费用

在问题三的讨论中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，而在本问题中，有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，步行的出行者在步行的公交站点线路上也不需要支付公交费用，同样由问题一中对乘公交所支付的费用的讨论思想，同样令乘坐公汽的单一票价为Qi0，出行者在所选择的出行线路中所应支付的车旅费为Qi，所乘同一公交线路上的最高收费（含地铁收费）为Qi1，分段计价时加价的最少站数为L0，于是有：

pik1T;pikT；pik1L;pikL；其它.

p(v,v)QiQi0N（pik,pik1）L*(pik)minikik1ik，Qi11

L0k1k1NiNi其中A表示取不超过A的最大整数，在本题中L020；Qi13；Qi01

线路；0线路pik为单一票制线路或地铁L(pik).1线路pik为分段记价的公交线路

*1pikL,pi1LN(pik,pik1)3pikT,pik1T0其它

综上所述，对问题三建立多目标最优化分层求解模型

minU(Ni,ti,Qi)

TRi

TRTRi|TRiv0,pi1,vi1,pi2,vi2,,vd;RCardTR;iiiR11;Nii2Ni1s..tSipik(vik1,vik).

k1Ni1Nitipik(vik1,vik)t(vik1,vik)t(pik,vik1);k1k1NiNipik(vik1,vik)QiQi0N(pik,pik1)L*(pik)min，Q1i1Lk1k10L020;Qi13;Qi01.模型的求解

由于成年人的平均行走速度为s，相邻车站的距离大约为1000m，我们假设相邻车站距离，人步行所要的时间约为11min 运用matlab求解如下（具体程序见附录三）

S3359S1828

先在站点S3359乘坐 436 路车到S1784,然后步行到S1828；一共费时104 分钟,

总花费为：3元

S971S485

先在站点S971乘坐 13 路车到S2184,然后步行到S485；一共费时131 分钟,总花费为：4元

S87S3676

先在站点S87乘坐 454 路车到S3496,然后步行到S3676；一共费时68 分钟,总花费为：2元

S8S73

先在站点S8乘坐 159 路车到S400,然后步行到S73；一共费时86 分钟,总花费为：2元结果分析

对比分析问题二和问题三的求解结果，考虑当两站间相隔站数不多时，可以步行这一情况后，选择路径，换乘次数和费用减少，所消耗的时间增加。比如

S3359S1828，考虑这一情况后，时间增加了9min，不用换乘了。步行是一种耗时省钱，选择灵活的方式。

10模型的改进、评价及推广

模型的改进

在实际生活中选择了最短的公交线路但并不一定耗时就是最少的，因为各线路还可能存在堵车的情况，即公交线路的负载超载。因此，模型的改进以“提高最优路径选择的灵活性展开”。

另外，我们也可以在路径选择过程中考虑旅游景点的问题，选择路径尽量便于乘客的旅游观光。

综合以上两点，改进后模型更加贴近实际，更加合理。

模型的评价：

优点： (1)用图论的知识将公交线路进行抽象处理，将现实问题数学化，使得求

解简单方便。

(2)对乘客心理进行了调查，使得多目标函数的确立更加科学合理，层次求解更有依据。

(3)考虑了公交线路实际的负载情况，使得路径的选择更加灵活，符合实际情况。

缺点： (1)只适用于找出直达、换乘一次或换乘两次的最优线路，具有局限性。

(2)转乘两次结果的计算时间超过了3分钟，算法的时间复杂程度偏大。 (3)在第三问中将各相邻站点间步行时间假设为相等，与实际生活相差太大。模型的推广：

该模型不但可以应用城市公交出行线路的选择，还可以应用于各种物流问题，如货物从生产地运往销售地如何选择交通方式和运输线路。

参考文献

[1]杨新苗、王炜、马文腾，基于GIS的公交乘客出行路径选择模型[J]，东南大

学学报（自然科学版），30（6）：87-88，2000年。

[2]韩传峰、胡志伟，城市公交路网性能评估的网络图方法[J]，系统工程，21（3）：58-61，2003.

[3]赵巧霞、马志强、张发，以最小换乘次数和站数为目标的公交出行算法[J]，

计算机应用，24（12）：136-137，2004年。

[4]杨启帆、方道元，数学建模[M]，杭州：浙江大学出版社，188-189，1999年

[5]王建林，基于换乘次数最少的城市公交网络最优路径算法[J]，浙江交通职业

技术学院院报，25（5）：673-676，2000.

[6]陈萧枫、蔡秀云、唐德强，最短路径算法分析及其在公交查询的应用[J],工程图学学报，(3)：20-24，2001.

附录一

%-----------------------第一问程序--------------------------

load %导入汽车路线信息数据库（矩阵） basedata=base_dat11; fprintf('请输入起初站号：'); begin0=input(''); bg=0;

fprintf('请输入终点站号：'); end0=input('');

%------------------------查找和起点相关的路线条数并记下该路线-------------------

A=zeros(86); %记载与起点相关的路线条数(包括起点为线路中间某点) Lhao=zeros(1,86); %记载与起点相关的路线条数(包括起点为线路中间某点)所对应的汽车路数

for i=1:size(basedata,1)

basedata0=qzreos(basedata(i,:));

luhao0=basedata0(1); %记下公汽路号 basedata0=basedata0(2:end);

if (basedata0(1)==basedata0(end)) %为环形线路 for m=1:size(basedata0,2)-1 if basedata0(m)==begin0 bg=bg+1;

A(bg,1:size(basedata0,2)-m)=basedata0(m:end-1);

A(bg,size(basedata0,2)-m+1:size(basedata0,2)-1)=basedata0(1:m-1);

Lhao(bg)=luhao0; break; else

continue; end end else

for j=1:size(basedata0,2) %考虑到中间站为输入的起始点 if (basedata0(j)==begin0) bg=bg+1;

A(bg,1:(size(basedata0,2)-j+1))=basedata0(j:size(basedata0,2)); Lhao(bg)=luhao0; break; else

continue; end end end end

%比较各条可行路线中的最优路线

A0=A(1:bg,:); %-------------------记下可行路线的条数及具体线路------------------

Lh0=Lhao(1:bg); %-------------------记下可行路线对应的汽车路数-------------------- qq=0;

%-----------判断是否换乘---------------

[en,state,l,tt,z]=direct(begin0,end0);

if state==1 %-----------不用换乘---------------- en=qzreos(en); s0=size(en);

fprintf('不用换乘！\\n'); fprintf('直接从站点S%4d.\\n',begin0,l,end0); fprintf('具体路线为：\\n'); fprintf(' %d ',en); fprintf('\\n');

fprintf('总用时为：%3d 分钟\\n',tt); fprintf('总费用为：%3d 元\\n',z); else

%下面是求出换乘一次的情况下的最优路线

T=zeros(1,bg); %-----------用于记录换行后的每条全路线的用时-------

F=zeros(1,bg); %-----------用于记录换行后的每条全路线的总费用-------

LU=zeros(2,bg); %-----------用于记录换行的最优路线的汽车路数-------

L=zeros(bg,172); %---------用于记录换行后的每条全路线的具体路径------

en0=zeros(1,172); %---------最佳路线-----------------

LU0=zeros(2,1); %---------最佳路线对应的汽车路数（有先后）-----------------

t=0; %----------最佳路线对应的时间---------- z0=0; %----------最佳路线对应的总费用---------

S%d乘坐%3d 路车到达终点站

for i=1:bg

%---------------------先对每一条路线做处理-------------------- H=zeros(85,172); %-------可能的换乘全路径------------ L0=zeros(1,85); %----每个站点可能的最佳换乘路径对应用时-------

F0=zeros(1,85); %----每个站点可能的最佳换乘路径对应费用-------

Lu=zeros(1,85); %----每个站点可能的换乘路径对应汽车路数---- h=0; %----记录每条路线上的换乘站数------ for j=2:86 %----由于是换乘，故从每条线路的第二站开始----- [e1,s1,l1,tt0,z00]=direct(A0(i,j),end0); if s1==1 h=h+1; s=size(e1,2);

L0(h)=5+(j-2)*3+(s-2)*3; %求每一条路线的费用 if j<=20 F0(h)=1+z00; elseif j>40 F0(h)=3+z00; else

F0(h)=2+z00; end

%----------------

H(h,1:j-1)=A0(i,1:j-1);H(h,j:j+s-1)=e1; H(h,j+s)=A0(i,j); %记录下换乘点 Lu(h)=l1;

else

continue; end end

%-----找出某条路线最佳的换乘点--------- if h~=0

min0=999; for n=1:h if L0(n)==0 continue; elseif L0(n)n0=n; %记住用时最小的路线编号 T(i)=min0; L(i,:)=H(n0,:);

LU(1,i)=Lh0(i); %换乘前的汽车路数 LU(2,i)=Lu(n0); %换乘后的汽车路数 F(i)=F0(n0); else

continue; end end else

continue; end end

%---------------------------------------

%--------据用时最短找到最佳路径---------- min0=999; for i=1:bg if T(i)==0 continue; elseif T(i)n0=i; %记住用时最小的路线编号 %-------找到了最佳路线-------------------- en0=L(n0,:);

t=min0; %最佳路线对应的时间 LU0(:,1)=LU(:,n0); z0=F(n0); else

continue; end end

if en0(1)~=0

en0=qzreos(en0);

en00=en0(1:size(en0,2)-1); fprintf('需要换乘一次！\\n'); fprintf('具体路线为：\\n'); fprintf(' %d ',en00); fprintf('\\n');

fprintf('即：先在站点S%d乘坐 %d 路车到S%d,然后改乘 %d 路车到S%d

；

一

共

费

时

分

钟

总

花

费

为

：

元

\\n',begin0,LU0(1),en0(end),LU0(2),en0(end-1),t,z0);

else qq=1; end end if qq==1

TT=zeros(1,bg); %-----------用于记录换行后的每条全路线的用时-------

LL=zeros(bg,258); %---------用于记录换行后的每条全路线的具体路径------

LLU=zeros(3,bg); %-----------用于记录换行的最优路线的汽车路数-------

FF=zeros(1,bg); %-----------用于记录换行后的每条全路线的总费用-------

HH0=zeros(1,bg); %-------后面的隐藏换乘点-------------- en0=zeros(1,258); %---------最佳路线-----------------

LU0=zeros(3,1); %---------最佳路线对应的汽车路数（有先后）-----------------

t=0; %----------最佳路线对应的时间---------- z0=0; %----------最佳路线对应的总费用--------- h0=0; %-------最佳隐藏换乘点---------- for i=1:bg

HH=zeros(bg,258); %-------可能的换乘全路径------------ H0=zeros(1,85); %-------后面的隐藏换乘点

LL0=zeros(1,85); %----每个站点可能的最佳换乘路径对应用时-------

FF0=zeros(1,85); %----每个站点可能的最佳换乘路径对应费用-------

LLu=zeros(2,85); %----每个站点可能的换乘路径对应汽车路数(有前后两次)----

h=0; %----记录每条路线上的换乘站数------ w=size(qzreos(A0(i,:)),2);

for j=2:w %----由于是换乘，故从每条线路的第二站开始----- [e2,s2,l2,ttt0,zz00]=direct1(A0(i,j),end0); if s2==1 h=h+1;

e3=e2(1:end-1); %最后一个为换乘点 s=size(e3,2);

LL0(h)=2+(j-1)*3+ttt0; %求每一条路线的费用 if j<=20

FF0(h)=1+zz00; elseif j>40 FF0(h)=3+zz00; else

FF0(h)=2+zz00; end

%----------------

HH(h,1:j-1)=A0(i,1:j-1);HH(h,j:j+s-1)=e3;

HH(h,j+s)=A0(i,j); %路线的最后一个元素记录第一个换乘点 LLu(:,h)=l2; H0(h)=e2(end); else

continue; end

end

%-----找出某条路线最佳的换乘点--------- if h~=0

min0=99999; for n=1:h if LL0(n)==0 continue; elseif LL0(n)n0=n; %记住用时最小的路线编号 TT(i)=min0; LL(i,:)=HH(n0,:);

LLU(1,i)=Lh0(1,i); %换乘前的汽车路数 LLU(2:3,i)=LLu(:,n0); %换乘后的汽车路数 FF(i)=FF0(n0); HH0(i)=H0(n0); else

continue; end end else

continue; end end

%--------------------------------------- %--------据用时最短找到最佳路径----------

min0=99999; for i=1:bg if TT(i)==0 continue; elseif TT(i)n0=i; %记住用时最小的路线编号 %-------找到了最佳路线-------------------- en0=LL(n0,:);

t=min0; %最佳路线对应的时间 LU0(:,1)=LLU(:,n0); z0=FF(n0); h0=HH0(n0); else

continue; end end

if en0(1)~=0

en0=qzreos(en0);

en00=en0(1:size(en0,2)-1); fprintf('需要换乘二次！\\n'); fprintf('具体路线为：\\n'); fprintf(' %d ',en00); fprintf('\\n');

fprintf('即：先在车站S%d乘坐 %d 路车到S%d,然后改乘 %d 路车到S%d,最后转乘 %d 路车到达S%d一共费时%d 分钟,总花费为：%d元\\n',begin0,LU0(1),en0(end),LU0(2),h0,LU0(3),en0(end-1),t,z0);

end end

附录二

%---------------第二问程序---------------

load %导入汽车路线信息数据库（矩阵） basedata=a1;

fprintf('请输入起始站号：'); begin0=input(''); bg=0;

fprintf('请输入终点站号：'); end0=input(''); ed=0;

%------------------------查找和起点相关的路线条数并记下该路线-------------------

A=zeros(88); %记载与起点相关的路线条数(包括起点为线路中间某点) B=zeros(88); %记载与终点相关的路线条数(包括起点为线路中间某点)

Lhao=zeros(88,1); %记载与起点相关的路线条数(包括起点为线路中间某点)所对应的汽车路数

LHao=zeros(88,1); %记载与终点相关的路线条数(包括起点为线路中间某点)所对应的汽车路数

for i=1:size(basedata,1)

basedata0=qzreos(basedata(i,:));

luhao0=basedata0(1); %记下公汽路号 basedata0=basedata0(2:end);

if (basedata0(1)==basedata0(end)) %为环形线路 for m=1:size(basedata0,2)-1 if basedata0(m)==begin0

bg=bg+1;

A(bg,1:size(basedata0,2)-m)=basedata0(m:end-1);

A(bg,size(basedata0,2)-m+1:size(basedata0,2)-1)=basedata0(1:m-1); Lhao(bg)=luhao0; end

if basedata0(m)==end0 ed=ed+1;

B(ed,1:size(basedata0,2)-m-1)=basedata0(m+1:end-1);

B(ed,size(basedata0,2)-m:size(basedata0,2)-1)=basedata0(1:m); LHao(ed)=luhao0; break; else

continue; end end else

for j=1:size(basedata0,2) %考虑到中间站为输入的起始点 if (basedata0(j)==begin0) bg=bg+1;

A(bg,1:(size(basedata0,2)-j+1))=basedata0(j:size(basedata0,2)); Lhao(bg)=luhao0; break; end

if (basedata0(j)==end0) ed=ed+1;

B(ed,1:j)=basedata0(1:j); LHao(ed)=luhao0; break; else

continue; end end end end

%比较各条可行路线中的最优路线

A0=A(1:bg,:); %-------------------记下与起点相关的可行路线的条数及具体线路------------------

Lh0=Lhao(1:bg); %-------------------记下与起点相关的可行路线对应的汽车路数--------------------

B0=B(1:ed,:); %-------------------记下与终点相关的可行路线的条数及具体线路------------------

LH0=LHao(1:ed); %-------------------记下与终点相关的可行路线对应的汽车路数--------------------

%---------------------求每条与起点相关的路线上可乘地铁点----------------------------

D=zeros(bg,88); %记载起始站点的相关换乘点 D0=zeros(ed,88); %记载终点站点的相关换乘点 for i=1:bg

d0=qzreos(A0(i,:)); for j=1:size(d0,2)

for p=521:size(basedata,1)

basedata00=qzreos(basedata(p,:));

if basedata00(2)==A0(i,j)

if 11100continue; end else

continue; end end

if D(i,j)~=0 break; else

continue; end end end for i=1:ed

d0=qzreos(B0(i,:)); for j=1:size(d0,2)

for p=521:size(basedata,1)

basedata00=qzreos(basedata(p,:)); if basedata00(2)==B0(i,j)

if 1110041

else

continue; end else

continue; end end

if D0(i,j)~=0 break; else

continue; end end end

%---------------确定起始点入站的地点---------------------------------- Z=zeros(3,bg); %记载每条线路的入地铁的线路站点及地铁站点 for i=1:bg

d0=qzreos(A0(i,:)); for j=1:size(d0,2) if D(i,j)~=0

Z(1,i)=D(i,j); %入地铁的地铁站点 Z(2,i)=A0(i,j); %入地铁的线路站点 Z(3,i)=j-1; else

continue; end end

end

%---------------确定终点入站的地点---------------------------------- Z0=zeros(3,ed); %记载每条线路的入地铁的线路站点及地铁站点 for i=1:ed

d0=qzreos(B0(i,:)); for j=1:size(d0,2) if D0(i,j)~=0

Z0(1,i)=D0(i,j); %入地铁的地铁站点 Z0(2,i)=B0(i,j); %入地铁的线路站点 Z0(3,i)=size(d0,2)-j; else

continue; end end end

%------------分别算出所有可行线路的耗间--------------- H=zeros(bg,ed); %记录耗时 F=zeros(bg,ed); %记录费用 for i=1:bg for j=1:ed

H(i,j)=Z(3,i)*3+6+ditiejishi(Z(1,i),Z0(1,j))+6+Z0(3,j)*3; F(i,j)=jifei(Z(3,i))+3+jifei(Z0(3,j)); end end

%求出矩阵中最小的数的坐标号，即对应为最佳路径 P=0;Q=0;o=999999; for i=1:bg

for j=1:ed if H(i,j)==0 continue; elseif H(i,j)continue; end end end

l1=Lh0(P);s1=Z(2,P); d1=Z(1,P); if d1>20000 d1=d1-22200; else

d1=d1-11100; end

s2=Z0(2,Q);l2=LH0(Q); d2=Z0(1,Q); if d2>20000 d2=d2-22200; else

d2=d2-11100; end t0=H(P,Q); f0=F(P,Q);

fprintf('最佳路线为：');

fprintf('先乘坐%d路车到S%d,换乘地铁D%d,再在地铁站点D%d换乘%d路车的S%d到达终点站S%d.\\n',l1,s1,d1,d2,l2,s2,end0); fprintf('总耗时为：%3.2f\\n',t0); fprintf('总费用为：%3.2f\\n',f0);

附录三

%-----------------------第三问程序--------------------------

load %导入汽车路线信息数据库（矩阵） basedata=base_dat11; fprintf('请输入起初站号：'); begin0=input(''); bg=0;

fprintf('请输入终点站号：'); end0=input('');

%------------------------查找和起点相关的路线条数并记下该路线-------------------

A=zeros(86); %记载与起点相关的路线条数(包括起点为线路中间某点) Lhao=zeros(1,86); %记载与起点相关的路线条数(包括起点为线路中间某点)所对应的汽车路数

for i=1:size(basedata,1)

basedata0=qzreos(basedata(i,:));

luhao0=basedata0(1); %记下公汽路号 basedata0=basedata0(2:end);

if (basedata0(1)==basedata0(end)) %为环形线路

for m=1:size(basedata0,2)-1 if basedata0(m)==begin0 bg=bg+1;

A(bg,1:size(basedata0,2)-m)=basedata0(m:end-1);

A(bg,size(basedata0,2)-m+1:size(basedata0,2)-1)=basedata0(1:m-1); Lhao(bg)=luhao0; break; else

continue; end end else

for j=1:size(basedata0,2) %考虑到中间站为输入的起始点 if (basedata0(j)==begin0) bg=bg+1;

A(bg,1:(size(basedata0,2)-j+1))=basedata0(j:size(basedata0,2)); Lhao(bg)=luhao0; break; else

continue; end end end end

%比较各条可行路线中的最优路线

A0=A(1:bg,:); %-------------------记下可行路线的条数及具体线路------------------

Lh0=Lhao(1:bg); %-------------------记下可行路线对应的汽车路数-------------------- qq=0;

%-----------判断是否换乘--------------- [en,state,l,tt,z]=direct(begin0,end0);

if state==1 %-----------不用换乘---------------- en=qzreos(en); b0=size(en,2);

%---------判断是否为环路线----------- ss=0; %记录是否为环形线路的状态 for i=1:b0

if S(i)==l

ss=1; break; else continue;

end

if ss==1 %为环线线路

fprintf('该起始终点站在同一环形线路上！\\n');

fprintf('直接从%d 走到终点站%d即可；费时为15分钟,费用为零.\\n',begin0,end0); else

fprintf('无需步行；直接从站点%d乘坐%3d 路车到达终点站S%4d.\\n',begin0,l,end0);

fprintf('具体路线为：\\n'); fprintf(' %d ',en); fprintf('\\n');

fprintf('总用时为：%3d 分钟\\n',tt); fprintf('总费用为：%3d 元\\n',z); end else

%下面是求出换乘一次的情况下的最优路线

T=zeros(1,bg); %-----------用于记录换行后的每条全路线的用时-------

F=zeros(1,bg); %-----------用于记录换行后的每条全路线的总费用-------

LU=zeros(2,bg); %-----------用于记录换行的最优路线的汽车路数-------

L=zeros(bg,172); %---------用于记录换行后的每条全路线的具体路径------

en0=zeros(1,172); %---------最佳路线-----------------

LU0=zeros(2,1); %---------最佳路线对应的汽车路数（有先后）-----------------

t=0; %----------最佳路线对应的时间---------- z0=0; %----------最佳路线对应的总费用--------- for i=1:bg

F0=zeros(1,85); %----每个站点可能的最佳换乘路径对应费用

-------

L0(h)=5+(j-2)*3+(s-2)*3; %求每一条路线的费用 if j<=20 F0(h)=1+z00; elseif j>40 F0(h)=3+z00; else

F0(h)=2+z00; end

%----------------

H(h,1:j-1)=A0(i,1:j-1);H(h,j:j+s-1)=e1; H(h,j+s)=A0(i,j); %记录下换乘点 Lu(h)=l1; else

continue; end end

%-----找出某条路线最佳的换乘点--------- if h~=0

min0=999; for n=1:h if L0(n)==0 continue; elseif L0(n)n0=n; %记住用时最小的路线编号 T(i)=min0; L(i,:)=H(n0,:);

LU(1,i)=Lh0(i); %换乘前的汽车路数 LU(2,i)=Lu(n0); %换乘后的汽车路数 F(i)=F0(n0); else

continue; end end else

continue; end end

%--------------------------------------- %--------据用时最短找到最佳路径---------- min0=999; for i=1:bg if T(i)==0 continue; elseif T(i)50

min0=T(i);

n0=i; %记住用时最小的路线编号 %-------找到了最佳路线-------------------- en0=L(n0,:);

t=min0; %最佳路线对应的时间 LU0(:,1)=LU(:,n0); z0=F(n0); else

continue; end end

if en0(1)~=0

en0=qzreos(en0);

en00=en0(1:size(en0,2)-1);

fprintf('先在站点S%d乘坐 %d 路车到S%d,然后步行到S%d；一共费时

分

钟

总

花

费

为

：

元

\\n',begin0,LU0(1),en0(end),en0(end-1),t+9,z0); else qq=1; end end if qq==1

TT=zeros(1,bg); %-----------用于记录换行后的每条全路线的用时-------

LL=zeros(bg,258); %---------用于记录换行后的每条全路线的具体路径------

LLU=zeros(3,bg); %-----------用于记录换行的最优路线的汽车路数

-------

FF=zeros(1,bg); %-----------用于记录换行后的每条全路线的总费用-------

HH0=zeros(1,bg); %-------后面的隐藏换乘点-------------- en0=zeros(1,258); %---------最佳路线-----------------

LU0=zeros(3,1); %---------最佳路线对应的汽车路数（有先后）-----------------

t=0; %----------最佳路线对应的时间---------- z0=0; %----------最佳路线对应的总费用--------- h0=0; %-------最佳隐藏换乘点---------- for i=1:bg

HH=zeros(bg,258); %-------可能的换乘全路径------------ H0=zeros(1,85); %-------后面的隐藏换乘点

LL0=zeros(1,85); %----每个站点可能的最佳换乘路径对应用时-------

FF0=zeros(1,85); %----每个站点可能的最佳换乘路径对应费用-------

LLu=zeros(2,85); %----每个站点可能的换乘路径对应汽车路数(有前后两次)----

h=0; %----记录每条路线上的换乘站数------ w=size(qzreos(A0(i,:)),2);

for j=2:w %----由于是换乘，故从每条线路的第二站开始----- [e2,s2,l2,ttt0,zz00]=direct1(A0(i,j),end0); if s2==1 h=h+1;

e3=e2(1:end-1); %最后一个为换乘点 s=size(e3,2);

LL0(h)=2+(j-1)*3+ttt0; %求每一条路线的费用 if j<=20

FF0(h)=1+zz00; elseif j>40 FF0(h)=3+zz00; else

FF0(h)=2+zz00; end

%----------------

HH(h,1:j-1)=A0(i,1:j-1);HH(h,j:j+s-1)=e3;

HH(h,j+s)=A0(i,j); %路线的最后一个元素记录第一个换乘点 LLu(:,h)=l2; H0(h)=e2(end); else

continue; end end

%-----找出某条路线最佳的换乘点--------- if h~=0

min0=99999; for n=1:h if LL0(n)==0 continue; elseif LL0(n)n0=n; %记住用时最小的路线编号

TT(i)=min0; LL(i,:)=HH(n0,:);

LLU(1,i)=Lh0(1,i); %换乘前的汽车路数 LLU(2:3,i)=LLu(:,n0); %换乘后的汽车路数 FF(i)=FF0(n0); HH0(i)=H0(n0); else

continue; end end else

continue; end end

%--------------------------------------- %--------据用时最短找到最佳路径---------- min0=99999; for i=1:bg if TT(i)==0 continue; elseif TT(i)n0=i; %记住用时最小的路线编号 %-------找到了最佳路线-------------------- en0=LL(n0,:);

t=min0; %最佳路线对应的时间

LU0(:,1)=LLU(:,n0); z0=FF(n0); h0=HH0(n0); else

continue; end end

if en0(1)~=0 en0=qzreos(en0); ll0=size(en0,2); en00=en0(1:ll0-1);

fprintf('先在站点S%d乘坐 %d 路车到S%d,然后改乘 %d 路车到S%d,最后步行到达S%d；一共费时%d 分钟,总花费为：%d元\\n',begin0,LU0(1),en0(end),LU0(2),h0,en0(end-1),t-round((ll0-1)/3)*3,z0-1); end end

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文