公交查询系统的最佳乘车专项方案设计含程序.doc

公交查询系统最佳乘车方案设计
摘要
本文研究问题是针对已知公交线路信息如何设计出最佳乘车方案。
一方面，进行数据解决，用excel建立起公交线路矩阵。
然后，上网查阅了公交乘客乘车心理分析资料，得出影响乘客出行三个重要因素依次为为：换乘次数、出行时间、出行费用
随后，建立了站点—线路序列模型。运用公交乘客出行过程抽象为站点—线路交替转换思想，从而拟定了出行者出行路线普通数学表达式。
针对问题一，仅考虑公汽状况下，以换乘次数至少为第一目的、出行时间为第二目的、乘车费用为第三目的，建立起多目的最优化分层求解模型。并依托站点—线路序列模型拟定出行线路表达式，采用图论中计算办法并结合广度搜索法经matlab编程(见附录一) 得到了公交乘客至少换乘次数，所通过站点，出行时间、出行费用(见表1)。
针对问题二，在问题一基本上考虑了地铁线路，解决办法是将地铁线当成特殊公交线，将地铁站点当成公交站点并与给定公交站连接。按照问题一模型和算法得到乘客至少换乘次数，出行时间、出行费用(见表2)。
针对问题三，在问题二基本上考虑了所有站点之间步行时间，由成人步行速度估算出该时间大小。步行线路与公汽线路相似但每条均有上行和下行。将步行线路矩阵与公交线路矩阵整合后按照问题二算法得到乘客至少换乘次数，出行时间、出行费用(见9.2)。
最后，建立公交负载模型对前三问模型进行了改进。考虑到了实际中公交线路堵车状况，将堵车线路拆分为两段新线路并相应变化公交线路矩阵。算法与前三问算法相似，但使得最佳途径选取更加灵活且更符合实际状况。

核心词：分层求解 交替序列 多目的最优化 改进广度搜索法
1问题重述
1.1问题背景
国内人民翘首企盼第29届奥运会来年8月将在北京举办，届时有大量观众到现场观看奥运比赛，其中大某些人将会乘坐公共交通工具（简称公交，涉及公汽、地铁等）出行。这些年来，都市公交系统有了很大发展，北京市公交线路已达800条以上，使得公众出行更加畅通、便利，但同步也面临多条线路选取问题。针对市场需求，某公司准备研制开发一种解决公交线路选取问题自主查询计算机系统。
1.2需要解决问题
为了设计这样一种系统，其核心是线路选取模型与算法，应当从实际状况出发考虑，满足查询者各种不同需求。请你们解决如下问题：
问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选取问题普通数学模型与算法。并依照附录数据，运用你们模型与算法，求出如下6对起始站→终到站之间最佳路线（要有清晰评价阐明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
问题二：同步考虑公汽与地铁线路，解决以上问题。
问题三：假设又懂得所有站点之间步行时间，请你给出任意两站点之间线路选取问题数学模型。
2模型假设及符号阐明
2.1模型假设
假设1：假设乘客都是理性乘车且能顺利到达目地
假设2：假设不考虑红绿灯导致等待时间，不考虑堵车，车祸等因素
假设3：假设乘客能接受最大换乘次数为2次
假设4：假设乘客乘车过程中不能2次通过同一站点。
假设5：假设公交与地铁换乘距离固定，换乘步行时间为常数
2.2符号阐明
符号
阐明

S公汽站点集，

L表达公汽线路集，

D地铁站点集，

T表达地铁线路集，
vik
出行者选取第条公交线路所通过第个站点(或)

出行者选取第条公交线路所乘坐第辆公交工具(或)
Ni
换乘次数
Si
路过车站数
ti
行程时间
Qi
所需费用

3问题分析
本文研究问题是设计一种公交线路选取自助查询计算机系统，并从实际状况出发考虑，以满足查询者各种不同需求。设计该系统核心是线路选取模型与算法。
针对问题一：问题一规定只考虑公汽线路，给出最佳途径。通过查阅有关资料，懂得对乘客影响最大三个因素：换乘次数，行程时间，所需费用(重要性从大到小)。据此，咱们建立以换乘次数为第一目的，行程时间最为第二目的，所需费用为第三目的多目的最优化模型。对于换乘次数，联系被选取线路上站点—线路交替序列TRi个数可以表达出来；站点总数则采用给同一线路上站点排序办法也可以求到，由于只考虑了公汽之间换乘，则出行时间只与换乘次数和所历站数关于；对于出行费用则在换乘次数基本上，引入分段计价加价函数也可求得。
针对问题二：问题二在一得基本上考虑可以搭乘地铁，乘客选取更加灵活。重要变化为：地铁票价稍高但是固定且在地铁航线之间换乘而不需此外支付交通费用，相邻站点之间距离较公汽站点大，而运营时间却相对减少；地铁与公汽之间进行换乘时，由于地铁站点不也许与公汽站点都建在同一种地方，因而从地铁站到公汽站步行时间相对较多，并且位于与地铁换乘公汽站点还可以通过本地铁站进行免费耗时换乘到下一种公汽站。咱们可以把跨公交站步行视为一种免费耗时交通方式，据此分层求解。
针对问题三：考虑到出行者在步行时，所通过任意两站点之间途径都应当是至少有一条公汽线路上公交工具通过，由问题三条件可知，步行时所通过两站点之间步行时间是一种已知值。当换乘两站之间站数不多时，咱们考虑步行，这要可以减少换乘次数，节约金钱。
4数据解决及分析
4.1数据解决
4.1.1数据记录
咱们运用Excel软件对给“公汽线路信息”和“地铁线路信息”进行记录得到如下数据：
表1
公汽线路
站点数
地铁线路
分段计价
单一
票价
上下行途径不同
上下行途径相似
环形路线
公汽
站点
地铁站点
直行线路
环形线路
283条
237条
409条
89条
22条
3957个
39个
1条
1条
公交系统共有公汽线路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

建立交线路矩阵A后，咱们可以把矩阵A导入MATLAB中，运用改进广度搜索算法求解最佳途径。
5模型准备
5.1乘客心理调查
北京公交车线路达800条以上，每一种公交站点也许有多条线路贯穿，通往不同起点或终点，同样，一种目地也可由多条线路到达，错综复杂公交车路线犹如网状般将各站点联系起来，将都市行人们带到其各自目地。
咱们通过互联网查阅有关资料发现，影响乘客公交线路选取，重要有如下几种因素：换乘次数 ，行程时间，所需费用，路过总站数等。
其中有18.6%乘客出行时，一方面考虑是乘车费用，30.4%乘客一方面考虑是行程时间，42%乘客一方面考虑是换乘次数。
图1：乘客出行调查图

就乘客自身而言，公交乘客出行更多考虑是出行以便性和舒服性，下面就影响公交乘客出行各因素进行详细分析，不妨将以上影响因素作如下归纳解释：
(1)换乘次数：出行者完毕一次从出发点到终点出行过程中所换车次数。
(2)行程时间：出行者在一次乘公交出行过程中所用总时间。
(3)所需费用：出行者在完毕一次由起点到达目地过程中所花车费。
(4)途径总站数：出行者完毕一次出发点到终点过程中所通过车站总数

5.2影响选取因素分析
“换乘次数”和“行程时间”是影响出行者两个独立因素，经研究表白多数公交乘客但愿换乘次数至少，况且公交公司对公交线路设计也是尽量减少乘客平均换乘次数；并且公交乘客出行时还受到行李、地理位置等客观因素影响，这样更不但愿有较多换乘。另一方面对于看奥运非常心切出行者来讲，出行耗时对她们也是比较核心。在此当给出供乘客选取公交路线也应当尽量满足公交乘客需求。固然，在此基本上咱们还要考虑乘车费用。
综上所述，可以以换乘次数至少为第一目的，再选取易于量化“出行时间”和“所需费用”作为第二位优化目的。由此，咱们以为，乘客在选取路线时，可以依照自己不同需求，对线路进行选取。
5.3最优乘车方案算法分析
在站点上放置一种便于乘客查询到达目地抱负乘车方案计算机系统，必要让计算机收集到本站到其她任意一站途径与换乘信息，因而单独设计这样算法是相称困难，并且算法精度规定也比较高。对本文附件中公交系统中所列3957个公汽站点和39个地铁站点来说，直接要得到所有任意两站点之间最优公交途径计算量是相称大。当面对这样一种密集交通网络来说，对路线选取重要是将面临一种类问题，依照类问题解决特点，可以用某种主次改进办法来求解。由于每次改进中计算量都是多项式界，改进次数也是多项式界。当前已找到具备这种特性算法，如椭球算法，卡马卡算法，但都相称复杂。因而要满足出行者路线需求，则有必要对目的进行归类筛选，以减少不必要选取、计算与搜索。不妨采用改进广度优先搜索算法，基于改进次数为多项式界算法理论，本文选取从某次乘公交起点和终点两端进行同步搜索，在满足换乘次数至少条件下寻找不同线路中共同站点或不同站点之间相似线路，并计算其总路线中乘车时间和站点数。
6站点—线路交替序列模型建立
6.1模型建立
本文所要解决主线问题是设计一种公交线路选取自助查询计算机系统，并从实际状况出发考虑，以满足查询者各种不同需求。设计该系统核心是线路选取模型与算法。
咱们建立交替序列模型寻找最优线路。
6.1.1模型预解决
出行者所选取出行起始站为v0，终到站为vd，从v0到vd所有途径集合也为TR，其中第i条途径为TRi，所乘坐第节公交工具为pik。进一步分析和考虑出行者乘公交详细状况，一种出行者出行可简朴描述为如下途径
图2：出行者选乘公交途径规律分析示意图
起始站
中转站1
乘第1节公交
离开公交
结束
选乘初次车
出发
……
中转站2
中转站3
选取路线
乘第2节公交
第1次换乘
终到站
乘第3节公交
第
2次换乘
中转站Ni
乘第Ni+1节公交
第Ni次换乘

从图中内容也可以反映，出行者出行乘公交途径可看着是站点、车次、站点、车次交替进行，直至到达终到站。为区别先后车次或站点，使得先后排列站点与车次均有一定顺序，由于出行者不能在同一站点上浮现两次，即vik各不相似，特别地令，；
6.1.2交替序列表达
分析可知，选取线路上站点—线路交替序列为：

其中站点—线路交替序列表达从起始点选取线路，换乘到达，……，最后到达第种途径。
起始站到达终到站公交线路选取集，即：

对于乘客而言，咱们只要懂得她出行起始站v0和终到站vd之后，便可以在途径集TR中找到她最需要出行路线。本模型对路线选取范畴拟定了界限，这样也明确了谋求最优线路讨论范畴，即搜索途径(公交线路pik)和节点(公交站点vik)都是互有关联。
7问题一解答
7.1多目的最优化分层求解模型建立
7.1.1拟定目的函数
本文所要解决主线问题最佳乘车路线设计问题。建立以换乘次数Ni为第一目的，再选取易于量化“出行时间ti”作为第二目的多目的最优化模型。

为了便于求解咱们定义目的函数U表达以Ni为第一目的，ti作为第二目的
Qi作为第三目的：

7.1.2拟定约束条件
1.目的函数U最小时，换乘次数和乘车时间也规定最小，因而U与Ni及ti
是正有关。

2. 由于在优先选取权上，按相应条件，在目的函数中，应优于，

7.1.3有关变量拟定
求解Ni取最小值时，再进行其他变量拟定与计算，才干选取到相应目的。即需要在可行域中进行优先性条件搜索。
I换乘次数
设表达有序集中元素个数，为便于区别，现标记，换乘次数可表达为

II所通过总站数
设非环行线路上两个站点和在沿着公交工具行进方向上站数按照正整数从小到大排序分别为和，其中依然记；，于是由数据解决中有关记录成果可知：

当线路为环行线路时，设该环行路线上总站数为，为上任意一站，，分别为公交工具在沿着行进方向上最后一站和前一站，于是可标记
；；；…；；…
因此出行者乘坐线路公交所通过站点数目为：

因此，出行者路过总站数为共条行车路线上车站数总和，即

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

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

其中表达取不超过最大整数，参数：（元），（元），.

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

7.2模型求解
7.2.1线路抽象解决
从A站到B站行车路线时，一方面考虑与否有通过A站直接到达B站。如果存在不只一条直达线路，在考虑所走路线远近，选取距离近来乘车方案；如果没有直达车，就会考虑换一次车方案。即通过A站车与通过B站车与否有公共站点C。如果有，则可在公共站点C处转车到达站点B。如果没有换一次车方案，则又要考虑乘坐通过A点车到某一站C下车，通过C站点车与通过B站点车与否有公共站点D，如果有，就到公共站点D转车，两次转车可到达站点B；如果没有，则需要转乘三次或三次以上才可到达目地。在上述状况中如果存在不止一种选取方案，则在考虑乘车距离，选取路程最短乘车方案。

(d)换乘多次车状况
图2 公交线路换乘方案示意图
(a)直达状况
(b)换乘一次车状况
A
B
C
B
A
(c)换乘两次车状况
A
B
C
D
A
B
C
D

运用matlab求解如下（详细程序见附录一）
表1问题一成果
途径
换乘次数
时间(分)
费用(元)
总站数

1
95
3
33

2
97
3
33

1
122
4
42

1
77
2
27

2
97
3
33

1
59
2
21

7.3成果分析
咱们以换乘次数为第一目的，假设乘客可以接受换乘次数不超过2次，将问题简化。只考虑乘公汽，所求6条途径没有直达其中第1，3,4,6条要换乘一次；第2,5条途径要换乘2次。
8问题二解答
8.1多目的最优化分层求解模型建立
8.1.1拟定目的函数
问题二在问题一基本上考虑可以搭乘地铁。乘客选取更加灵活。其重要变化因素有：1地铁票价稍高但是固定且在地铁航线之间换乘而不需此外支付交通费用，相邻站点之间距离较公汽站点大，而运营时间却相对减少
2地铁与公汽之间进行换乘时，由于地铁站点不也许与公汽站点都建在同一种地方，因而从地铁站到公汽站步行时间相对较多，并且位于与地铁换乘公汽站点还可以通过本地铁站进行免费换乘到下一种公汽站。

8.1.2拟定约束条件

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

其中pik属性将被扩大，它将表达公汽、地铁、步行这三类交通路线中某一类交通路线；而含义与问题一中含义相似，仍表达公交站点或地铁站点。
I换乘次数与路过总站数
同样设途径换乘次数为路过总站数为，同问题一对，依然有：

II出行者乘公交所用时间
在地铁——公汽公交系统中，出行者将会体当前公汽运营耗时，地铁运营耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时。为简化变量，考虑出行者异站步行也纳入到公交线行列中，则所消耗时间可归结为：交通工具运营耗时，交通线路换乘耗时两类。
设出行者从起始站到达终到站所用总时间为，从公交站点乘线路公交工具到达公交站点所消耗时间（涉及相邻两站点间停站时间）为：，由线路公交工具换乘到线路公交工具所消耗时间为： ，由基本参数设定信息可得：

其中

IV乘车总费用
在问题二讨论中，乘车总体耗费会受到出行者换乘次数，乘坐分段计价车时通过站数影响，而在本问题中，有假设懂得同一地铁站相应任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，同样依照问题一中，对乘公交所支付费用讨论思想，依然令乘坐公汽单一票价为Qi0，出行者在所选取出行线路中所应支付车旅费为Qi，所乘同一公交线路上最高收费（含地铁收费）为Qil，分段计价时加价至少站数为L0，于是有：

其中表达取不超过A最大整数；参数：（元），（元），

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

8.2模型求解
8.2.1设计算法
1输入乘车起始站点及目站点；
2求通过站点A所有线路集S(I)和通过站点B所有线路集T(J)；
3判断S(I)=T(J)
如果有，则找到了从站点到站点直达线路S(I)即T(J)，输出成果，结束运算，如果没有则进行下一步。
4求线路S(I)上站点E(I,U)以及线路T(J)上站点F(J,V)；
5判断与否存在相似站点，即=，或者存在紧邻站点，即满足；如果满足=，则线路，即为一次转车线路，即为转车站点且换车时不用更换站点；如果满足但满足，则线路，即为一次专车线路，即为转车站点但换车时要步行到紧邻站点。如果没有，再执行下面环节。
6求通过线路集，通过线路集；
7判断=吗？如果有，则线路，，为两次换车线路，换车站点为和，输出成果，结束运算；如果没有则执行下面环节。
8求线路上站点和线路上站点；
9判断与否存在相似站点，即=，或者存在相邻站点，即满足；如果满足=，则线路，，，即为三次转车线路，，，即为转车站点，且换车时不用更换站点；如果满足但满足，则在站点专车时要步行到紧邻站点。
算法流程图
开始

获取起点和终点

真
假
假
假
输出,,

输出,,

输出,,,
,,,
,

选取换乘次数至少且耗费时间最短乘车方案最为最后成果

真
真
真
结 束

运用matlab求解成果如下（详细程序见附录二）
表2问题二成果
途径
换乘次数
时间(分)
费用(元)

1
95
3

2
97
3

1
122
4

1
77
2

2
97
3

0
34.5
3

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

9问题三解答

9.1多目的最优化分层求解模型建立
9.1.1拟定目的函数
考虑到出行者在步行时，所通过任意两站点之间途径都应当是至少有一条公汽线路上公交工具通过，由问题三条件可知，步行时所通过两站点之间步行时间是一种已知值。据实际状况，假设步行者步行在相邻两公汽站所用时间平均是公汽通过这两站（涉及停站时间）所用时间倍，则由基本参数设定可知，步行者通过这样两站点所用平均时间为分钟，于是将行人步行所通过线路也纳入到公交线路中，其特点是费时费力但选取灵活。

9.1.2拟定约束条件

9.1.3拟定变量
设出行者以步行、乘公交、换乘等任意出行方式从初始站V0到达终到站Vd可行途径集为：
，
其中，上式中、都与问题二中、含义分别相似，
I换乘次数、路过总站数
设该途径换乘次数为路过总站数为，依然有

II出行者乘公交所用时间
在步行—地铁—公汽公交系统中，出行者将会浮现公汽运营耗时，地铁运营耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时，公交站点之间步行耗时。同样考虑出行者异站步行纳入到公交线行列中来简化变量，则所耗时间依然可分为：交通工具运营耗时（涉及步行耗时），交通线路换乘耗时两类。
同样设出行者从起始站到达终到站所用总时间为，从公交站点乘线路公交工具到达公交站点所消耗时间（涉及相邻两站点间停站时间）为：，由线路公交工具换乘到线路公交工具所消耗时间为： ，则由基本参数设定信息可得：

其中

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

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

其中表达取不超过最大整数，在本题中；；

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

9.2模型求解
由于成年人平均行走速度为1.5m/s，相邻车站距离大概为1000m，咱们假设相邻车站距离，人步行所要时间约为11min
运用matlab求解如下（详细程序见附录三）

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

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

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

先在站点S8乘坐 159 路车到S400,然后步行到S73；一共费时86 分钟,总耗费为：2元
9.3成果分析
对比分析问题二和问题三求解成果，考虑当两站间相隔站数不多时，可以步行这一状况后，选取途径，换乘次数和费用减少，所消耗时间增长。例如，考虑这一状况后，时间增长了9min，不用换乘了。步行是一种耗时省钱，选取灵活方式。
10模型改进、评价及推广
10.1模型改进
在实际生活中选取了最短公交线路但并不一定耗时就是至少，由于各线路还也许存在堵车状况，即公交线路负载超载。因而，模型改进以“提高最优途径选取灵活性展开”。
此外，咱们也可以在途径选取过程中考虑旅游景点问题，选取途径尽量便于乘客旅游观光。
综合以上两点，改进后模型更加贴近实际，更加合理。
10.2模型评价：
长处： (1)用图论知识将公交线路进行抽象解决，将现实问题数学化，使得求
解简朴以便。
(2)对乘客心理进行了调查，使得多目的函数确立更加科学合理，层次求解更有根据。
(3)考虑了公交线路实际负载状况，使得途径选取更加灵活，符合实际状况。
缺陷： (1)只合用于找出直达、换乘一次或换乘两次最优线路，具备局限性。
(2)转乘两次成果计算时间超过了3分钟，算法时间复杂限度偏大。
(3)在第三问中将各相邻站点间步行时间假设为相等，与实际生活相差太大。
10.3模型推广：
该模型不但可以应用都市公交出行线路选取，还可以应用于各种物流问题，如货品从生产地运往销售地如何选取交通方式和运送线路。

参照文献
[1]杨新苗、王炜、马文腾，基于GIS公交乘客出行途径选取模型[J]，东南大学学报（自然科学版），30（6）：87-88，。
[2]韩传峰、胡志伟，都市公交路网性能评估网络图办法[J]，系统工程，21（3）：58-61，.
[3]赵巧霞、马志强、张发，以最小换乘次数和站数为目的公交出行算法[J]，计算机应用，24（12）：136-137，。
[4]杨启帆、方道元，数学建模[M]，杭州：浙江大学出版社，188-189，1999年
[5]王建林，基于换乘次数至少都市公交网络最优途径算法[J]，浙江交通职业技术学院院报，25（5）：673-676，.
[6]陈萧枫、蔡秀云、唐德强，最短途径算法分析及其在公交查询应用[J],工程图学学报，(3)：20-24，.

附录一

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

load base_dat11.txt %导入汽车路线信息数据库（矩阵）
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%d乘坐%3d 路车到达终点站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； %----------最佳路线相应总费用---------
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)<min0
min0=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)<min0
min0=T(i);
n0=i； %记住用时最小路线编号
%-------找到了最佳路线--------------------
en0=L(n0,:);
t=min0； %最佳路线相应时间