烟台市公交线路优化模型.docx

烟台市公交线路优化模型摘要：乘坐公交车出行时，我们都希望直接达到目的地，即使没有直达车，我们也希望尽可能少的转乘。本文旨在研究在烟台市区乘坐公交车出行选择线路问题，出于对问题的考虑，本文对算法进行了改进，将公交转乘问题抽象为分层最短路问题。然后，建立了多目标规划模型，并任取六对起始站终到站站点对模型进行了验证，得到最佳路线，如下：关键词：最短路径；Floyd 算法；多目标规划；公交路线优化1 问题的提出随着社会的不断发展，每个城市的公交系统都得到了不同程度的提高，人们出行时更倾向乘坐公交车。在乘坐公交时，每个乘客都希望直接达到目的地，即使没有直达车，他们也希望尽可能少的转乘。因此，如何做到经济、方便、快捷的到达目地的，成为每个乘客比较关心的问题；而且转乘次数是乘客最关心的乘车因素。题目中要求根据烟台市区公交车线路图，给出任意两个公交车站点应如何选择线路，使转乘尽可能少，建立数学模型与算法，并利用该算法，在烟台市区任意选择6对起始站终到站站点，计算最佳路线。2 条件的假设与符号的约定2.1条件的假设（1）假设所有公交线路双向发车，所以线路中的各个站点没有乘车的先后次序之分，线路上任意站点可以互达；（2）假设车从首站出发开往尾站和从尾站出发开往首站所经过的站点都是一样的；（3）假设任意相邻站点的距离相同；（4）假设每条公交线路况和车况相同，不影响公交的正常运行，且不考虑交通拥挤、交通事故及道路流量对乘车时间和选择路线的影响； （5）假设公交车准时出发并准时到达站点；2.2 符号的约定 第站点到第站点经过的站点数第站点到第站点的直达信息 第站点到第站点的转乘站信息无向图的顶点非直达的站点之间的距离直达决策变量3 问题的分析该问题是烟台市公交路线选择最优问题，主要要求为建立线路选择的模型和设计相应的算法，来满足乘客的各种不同需求。根据题目中要求：乘坐公交尽可能少的转乘，本文拟收集烟台市所有公交路线，并把这些公交路线途经的所有的站点标上序号。在公交网络中，乘客在选择路线时，会对如下因素进行考虑：换乘次数是否最少，路程是否最短等。乘客一般不会随意换车，因为从一条线路换乘到另一条线路既费时又费力，在很多情况下，换乘另一趟车需要步行到另一个站台。这就有一段的步行距离的代价，而且在站台等车也是要消费时间的。所以对于公交乘客来说，最佳路线的意义就是换乘的次数要最少。考虑到上述情况，本文拟以转乘次数最少为前提，然后再在其基础上考虑路程最优，建立以换乘次数为第一目标、公交车行驶路程为第二目标的目标优化模型，进行求解。由于本题涉及数据信息量较大，如何巧妙的处理这些数据成为解答本题的关键。根据编号的所有站点，本文拟构造无向图，建立元胞数组来存储直达公交路线的站点的信息（直达车次，站点间距等）及转乘站点的信息（转乘次数，路线编号，转乘路线等）；在求解最短路径问题时，本文拟采用算法求出转乘次数最少的路线及其所经过的所有的站点。最后，应用多目标优化模型求出在烟台市区任意选择的6对起始站终到站站点的最佳路线。 4 建立模型前的准备4.1对烟台市所有公交站点建立无向图任意两个站点分别为某条公交路线上的起点与终点。在计算任意两个相邻站点的距离时不用考虑方向，故本文建立一个无向图1，记为,其中称为的点集合，为的边集合，并且是一个无序二元组，记为。4.2构建元胞数组根据统计，烟台市总共有71条公交线，1112个公交站点。由于公交站点数量庞大和计算机内存的限制，为减少存储空间，我们建立元胞数组并将公交线上任意两个站点之间的最短直达信息(乘几路车及经过多少站到达)存入元胞数组中，如下表所示：表1 元胞数组表1 元胞数组cell 1,1cell1,2cell1,1112cell i,1cell i,2celli,11124.3 改进的算法：算法是一种用于寻找给定的加权图中顶点间最短路径的算法。通过一个图权值矩阵，求出它的每两点间的最短矩阵。从加权图中的带权邻接矩阵开始，递归地进行次更新。即由矩阵，按一个公式，构造出矩阵；又用同样地公式由构造出；最后又用同样的公式由构造出矩阵。矩阵的行列元素便是号顶点到号顶点的最短路径权，称为为图的权矩阵，同时还可引入一个后继节点矩阵来记录两点间的最短路径。采用的是松弛技术，对在和之间的所有其他点进行一次松弛，所以时间复杂度为。其状态转移方程如下：其中表示到的最短权，是穷举的断点。改进的算法，考虑到了转乘次数。并不直接将直接赋值，而是在一次遍历中将最短路存入另一数组中，即一次遍历后，再将的改变的值赋给，这样就能保证换乘次数。5模型的建立及求解5.1烟台市公交路线选择多元目标优化模型5.1.1确定决策变量由烟台市公交路线总共有71条，公交站点一共1112个，乘车路线：设总乘车次数为，起始点为，终到点为；所乘车次按先后依次为：各转车地点分别为： 则乘车路线可表示为：5.1.2建立模型先考虑换乘次数的因素，由公交乘客出行的共同心理，乘客会优先考虑换乘次数最少的乘车方案。再转乘次数相同的情况下，乘客会优先考虑路程最短的乘车方案。如果假设各公交站点之间的路程都相同的话，那么就可以视为经过的站最少的转乘方案。首先建立的直达带权矩阵，及直达矩阵：，其中，其中：公共汽车站的站点数为1112；表示第个站点到第个站点之间经过的站点数。然后定义矩阵算子“”如下：设均为阶方阵，可以得到矩阵。其中矩阵中的元素为： 于是，可得多目标优化化模型为5.2运用Floyd 算法解决转乘次数最少最短路径问题Step1:建立求短路径问题的数学模型设烟台市的任一公交站点为图的一个顶点，连接任意两个公交站点的公交路线为图的边，记为。记为图的边之长，即为两站点间距。对任意的的顶点,寻求轨道,使得 , （1）即从到得所有轨道长中寻找最小的一个，是轨道上各边长之和。这样就建立了关于最短路径问题2的数学模型。Step2:改进Floyd算法的基本思想 改进Floyd-Warshall算法的原理是分层次动态规划，用于求解在某一层次中任意两点间的最短距离，时间复杂度为，空间复杂度为。在每层次迭代前，都要建立一个无穷邻接矩阵（仅储存无边相连的顶点的邻接矩阵），来存放在迭代过程中得到的最短路径。然后考察无穷邻接矩阵，从中选出尚未连变的任意两顶点和，每次插入一个顶点。然后将到间的已知路径与插入顶点作为中间顶点（一条路径中除始点和终点外的其他顶点)时可能产生的到的路径距离比较，取较小值存入无穷邻接矩阵中。最后，将无穷邻接矩阵的非无穷元素付给原邻接矩阵，进行下一层迭代。递推产生个矩阵，当所有的顶点都有边相连或者再也找不到能够相连的顶点时，就得到了图的分层次最短邻接矩阵。计算时用迭代公式： （2） 其中是迭代次数，。最后，当时，即是各顶点之间的最短通路值。Step3:Floyd 算法构造距离矩阵的原理对1112个站点的公交系统进行编号，将顶点用1112个整数（从1到1112）进行编号，提取出71条公交路线中任意两站点的最短距离作为边长，构建带权邻接矩阵，作为距离矩阵的初值，即。构造邻接元胞数组，（为公交车编号，为站点直接直达最短路长）。设置最大转乘次数为。第一步：构造，其中若。然后对任意的若进行一维搜索，是从到的只允许以作为中间点的路径中最短路长度，将转乘次数及中转站点存入元胞数组中。得到此层次上的最短路,转乘次数增1。第二步：将得到的最短路数据赋值给，判断转乘次数是否等于，若是，跳出循环；否则判断中是否还有未连边的点，即是否存在两个点有。若存在，转到第一步进行下一层迭代；否则，即得到最少转乘次数下的最短路径。第三步：任意取6对起始站终到站站点，代入元胞数组、中，求出最短路径。Step4:模型的求解及结果分析 模型的求解流程如图所示：5.3运用Floyd 算法解决转乘次数最少最短路径问题 任意取6对起始站终到站站点，带入求得他们基于最少转乘的最短乘车方案，如下表表2 六对站点换乘方案始发站所乘车次第一次换乘站点所乘车次第二次换乘站点所乘车次终点站换乘次数经过站点66（鲁东大学）41路163（祥和花鸟市场）17路151（烟台大学）112+365（上尧花园）50路30（石沟屯）51路391（滨州医学院烟台校区）121+1015（烟台三中）62路719（牟平长途车站）602路1000（双良家园）148+966（鲁东大学）3路53（官庄）201路778（石屋营）526路924（富士康东门）213+4+465（上尧花园）50路76（北马路汽车站）21路348（西蒙西）16+19142（南山公园）58路76（北马路汽车站8路162（幸福十六村）15+9 通过分析得出的结果，我们发现任意两站点间的最少转乘次数几乎都没有超过两次，而且经过的总站数较为合理。这完全符合公交路线的设计理念及乘客的乘车心理。并且通过实例验证和实际分析，我们发现我们的结论确实是最优的乘车方案。6模型的评价和改进6.1模型的评价（1） 模型的优点：本文建立了多目标规划，能够有效地筛选掉大部分无效信息在转乘次数一定时出现的行程较长的转乘方案。并且通过改进图论Floyd 算法，可以在所给图中成功地建立节点与节点间的关系，并可以求出节点与节点间在某一层次的最短路径。因此能够保证在换乘次数最少情况下得到距离最短的换乘方案。（2） 模型的缺点：由于不能确定公交站点间的最大换乘次数，所以需要给出一个限定值。并且当可能有多条最优路线时，建立的模型只能找出其中一条。6.2模型的改进与推广 本模型还可以加入其他因素，如，乘车与等待时间，所需费用，和交通拥挤情况等。并且根据不同乘客的需求，可以对所建立的多目标模型中的目标进行排列组合分别求解，得到具有个性化的最佳路线供乘客选择。本题的求解是一个新型的运筹学最短路问题，运用改进的Floyd-Warshall算法建立的模型使用范围非常广泛，在工业、商业、交通