最佳公交线路选择模型1

公交线路优化选择的研究[摘要] 本文对四川省达州市公交线路进行研究，利用dijkstra 算法引入0—1变量，并添加了乘客乘车所需时间和费用的偏好系数求解模型，建立一个多目标规划模型。

针对实际问题，利用 lingo 软件求解模型，得到了符合实际的结果。

[关键词] 公交线路 dijstra算法 0-1规划偏好系数加权法1.问题背景随着经济的迅速发展，城市的日益繁荣，城市车辆日益增多使得交通拥塞，能源紧张，噪音废弃污染越来越严重。

为了解决这些问题，政府部门鼓励人们出行选择乘坐公交。

然而随着公交系统的大力发展，线路越来越多，也越来越复杂，如何选择最优的乘车方案成为人们出行时的难题。

本文主要根据四川省达州市公交线路的特点和乘客出行时的乘车需求建立优化模型，并能求出以下站点的最优路线。

(1) 西客站→南客站 (2) 北客站→西客站 (3) 南客站→北客站为了简化模型，我们做了以下的基本参数假定：相邻公汽站平均行驶时间(包括停站时间)：3分钟；公汽换乘公汽平均耗时：5分钟 (其中步行时间2分钟)2.问题分析2.1 达州市公交线路比较复杂，公众在出行时都希望选择一条最优的乘车路线。

尽可能使在行程中所用的时间和乘车所用的费用最少。

结合实际情况，在很多时候我们乘车的费用最少却花费很多时间，或是时间达到最少费用却未必最少。

由此我们建立一个关于时间、费用最少的多目标规划模型。

2.2 实际问题中数据庞大无规律，且求解过程中不宜操作。

为了简单运算，由此我们引入数组概念，将两相邻的公交站点之间构想成一个数组元素，由这些数组元素共同组成整个公交线路。

3.模型的建立与求解3.1 问题分析题一要求给出任意两公汽站点之间线路选择问题的一般数学模型与算法，并利用所求得的模型与算法，首先要明白什么样的路线在乘客心目中才是最佳路线。

调查报告资料显示，在大多数乘客心目中的最佳路线是这样一条路线：乘车费用少、行程时间短、车上不拥挤、交通不拥挤等等。

北京市公交最优乘车路径选择的数学模型摘要2008年8月，奥运圣火将在北京点燃。

盛大的奥运赛事聚焦了全世界人民的目光，明年的北京将绽放最绚丽的光彩。

届时，客流量将会大幅上升，环境、交通、城市建设都将面临很大考验。

怎样才能更好的解决奥运期间市民和游客的出行问题呢？针对这样的实际问题，我们设计了一个城市公交线路的自主查询系统，建立了关于城市公交最优乘车路径选择的数学模型和算法，巧妙的运用Java语言编写程序，解决了现实生活中乘车路径选择的问题。

针对问题 1，在只考虑公汽线路时，首先求出起始站和终到站所有公交线路集合的交集，若此交集为非空交集，则选择所有直达线路中途经站点数最少，即花费最少的线路出行；若交集为空，选择起始站附近的站点，求出此站和终到站所有公交线路集合的交集，若为非空交集，则可选择换乘一次的方法出行；否则，换乘两次，换乘三次……直到找到换乘N次的乘车方案为止。

存在多条乘车线路时，考虑途经站点最少的乘车方式。

在此基础上，通过运用Java语言编程，确定了所需的最优乘车路径：（1）乘坐L436路公交车从S3359到S1784站，在S1784站换乘L167或L217路到S1828站，全程换乘一次，耗时101分钟，乘车费用为3元；（2）乘坐L84路公交车从S1557到S1919站，在S1919站换乘L189到S1402站,在S1402换乘L460到S0481站，全程换乘两次，耗时112分钟，乘车费用为3元；（3）乘坐L13路公交车从S0971到S2184，在S2184站换乘L417路到S0485站，全程换乘一次，耗时128分钟，乘车费用为3元；（4）乘坐L43路公交车从S0008到S1383，在S1383站换乘L282路到S0073站，全程换乘一次，耗时113分钟，乘车费用为3元；（5）乘坐L308路公交车从S0148到S0302，在S0302站换乘L427到S2027站，在S2027站换乘L469到S0485,全程换乘两次，耗时118分钟，乘车费用为3元；（6）乘坐L454路公交车从S0087到S3469，在S3469站换乘L209路到S3676站，全程换乘一次，耗时65分钟，乘车费用为2元；针对问题 2，要求同时考虑公汽线路和地铁线路，在同一地铁站对应的任意公汽站间可免费换乘，利用问题1的思想建立数学模型，运用Java语言编程，得到同时考虑公汽和地铁时的最优乘车路径：前五对起始站→终到站的最优乘车路径的选择与问题1一致。

公交车调度⽅案的优化模型第三篇公交车调度⽅案的优化模型2001年 B题公交车调度Array公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出⾏状况、提⾼公交公司的经济和社会效益，都具有重要意义。

下⾯考虑⼀条公交线路上公交车的调度问题，其数据来⾃我国⼀座特⼤城市某条公交线路的客流调查和运营资料。

该条公交线路上⾏⽅向共14站，下⾏⽅向共13站，表3-1给出的是典型的⼀个⼯作⽇两个运⾏⽅向各站上下车的乘客数量统计。

公交公司配给该线路同⼀型号的⼤客车，每辆标准载客100⼈，据统计客车在该线路上运⾏的平均速度为20公⾥/⼩时。

运营调度要求，乘客候车时间⼀般不要超过10分钟，早⾼峰时⼀般不要超过5分钟，车辆满载率不应超过120%，⼀般也不要低于50%。

试根据这些资料和要求，为该线路设计⼀个便于操作的全天（⼯作⽇）的公交车调度⽅案，包括两个起点站的发车时刻表；⼀共需要多少辆车；这个⽅案以怎样的程度照顾到了乘客和公交公司双⽅的利益；等等。

如何将这个调度问题抽象成⼀个明确、完整的数学模型，指出求解模型的⽅法；根据实际问题的要求，如果要设计更好的调度⽅案，应如何采集运营数据。

公交车调度⽅案的优化模型*摘要：本⽂建⽴了公交车调度⽅案的优化模型，使公交公司在满⾜⼀定的社会效益和获得最⼤经济效益的前提下，给出了理想发车时刻表和最少车辆数。

并提供了关于采集运营数据的较好建议。

在模型Ⅰ中，对问题1建⽴了求最⼤客容量、车次数、发车时间间隔等模型，运⽤决策⽅法给出了各时段最⼤客容量数，再与车辆最⼤载客量⽐较，得出载完该时组乘客的最少车次数462次，从便于操作和发车密度考虑，给出了整分发车时刻表和需要的最少车辆数61辆。

模型Ⅱ建⽴模糊分析模型，结合层次分析求得模型Ⅰ带给公司和乘客双⽅⽇满意度为（0.941，0.811）根据双⽅满意度范围和程度，找出同时达到双⽅最优⽇满意度(0.8807,0.8807)，且此时结果为474次50辆；从⽇共需车辆最少考虑，结果为484次45辆。

公交最优路线问题摘要针对公交系统的特点，该文把环形路线和往返路线做成上下行路线，由此构造了1040行、100列的矩阵K（矩阵的每个非零元素为对应路线的站点）。

矩阵的行下标对应公交系统中的线路号（行数为偶数：线路号=行数/2；行数为奇数：线路号=（行数+1）/2），矩阵的列下标对应每条路线上公汽经过站点的次序，当路线中的站点不足100个时，矩阵中对应的位置以0代替。

鉴于公交系统网格的复杂性，没有采用常规的迪克斯特拉（Dijkstra）算法，而是提出了一个能高效搜索任意两站点之间的路线选择的算法。

基本思想时从经过起始站的路线出发，搜寻出任意两站点间转乘次数不超过两次的可行路线，然后对可行解进一步处理，建立了以时间最少为目标的优化模型。

从实际情况出发，经过尝试与探索，为了满足查询者的不同需求，归纳出直达，换乘一次，换乘两次的情况，并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的站点，最后提出了进一步的意见和建议。

利用此模型和算法求解所给的6对起始站→终到站之间的最佳（最省时）路线。

这6对路线的具体情况如表1表1 6对起始站→终到站之间的最佳（最省时）路线关键字：优化模型，最优路线，搜索筛选，换乘次数，乘车时间。

一 问题重述城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

如果能够提供一种服务，为市民特别是外来旅游、出差、就医等急需了解本地道路情况的人提供方便、快捷、经济、高效的乘车方案，将方便他们的出行和生活，同时减少不必要的交通流量，提高交通运输效率。

这已是一个越来越迫切急于解决的现实问题。

针对市场需求，本文研制开发了一个解决公交线路选择问题的自主查询计算机系统。

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

需解决如下问题：给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

第一部分训练任务简介任务一：考试公平性是评价考试质量的重要方面，也是一个受到广泛关注的问题。

现代教育虽然趋向现代化，许多教学可以通过计算机实现，但也有许多的问题是计算机无法解决的，由绝大部分的考试是离不开评委亲自的审查，因为许多的学术问题上，计算机是不会知道的，所以工作量只可以是人为的评改。

体现最主要的，就是试卷的合理均匀的分配。

在大学生数学建模竞赛的评卷工作中，M 个评委（M 个评委来自不同的学校）要完成 N 份试卷的打分，竞赛试卷来自 K 个学校，第 i 个学校有竞赛试卷 1 份，为节省人力，每份试卷只要由其中 p(p<M<K<<N)各评委进行打分就行了。

1．根据回避原则，要求评委不能阅自己学校的试卷。

要求给出试卷合理的均匀分配方案的数学模型，使各评委的阅卷工作量均衡，试卷分配均衡分散。

2．给出试卷合理的均衡分配方案的计算机程序，所需参数为 p,M,k,N,输出参数为各评委分别阅卷的号码。

任务二：某城市现有公共汽车线路N 条，横贯整个市区。

由于城市比较大，从某地到另一个地方，乘坐公共汽车往往要在中间某地换车。

请你设计一个算法，可算出从某地到另外一个地方（无论换车与否）的最佳乘车路线。

请自拟一个例子（实际某城市交通路线更好）模拟仿真。

任务三：学习数学软件（MathType5.2、MATLAB 、Maple、Mathematica4.0、LINGO8.0）安装调试；基本命令使用（变量赋值、定义函数、过程控制、绘图命令、拟合、线性规划、非线性规划）；高等数学实验（绘图，极限，求导，积分，解微分方程）；线性代数实验（矩阵基本运算，线性方程组求解，解超定方程组，优化命令）。

并在提交的综合训练文档附录中的给出下列 6 个程序的译文(数学模型)及解答：（1） c=[6,6,16,16,10,10,15,15];A=[0.5/100 0 1.5/100 0 0.5/100 0 1.5/100 0;0 1.5/100 0 0.5/100 0 0.5/100 0 0.5/100;0 0 0 0 0 0 1 1;10 10 10 10;0 10 10 10 1]; b=[0;0;50;100;200;Aeq=[1,1,1,1,1,1,1,1];beq=[350];lb=zeros(8,1);[x,fval]=linprog(c,A,b,Aeq,beq,lb) %目标为最小的线性规划（2）c=[400, 1000, 300,200]; %目标函数系数（产出系数）A=[2,3,1,0;3,4,0,0;0,0,1,0]; %约束条件系数b=[16;24;5];Aeq=[0,2,1,1];beq=[0];xL=[0,0,0,0]; % x 取值范围的最小值xU=[]; % x 取值范围的最大值x0=[0,0,0,0]; % x 取迭代初始值[t,w]=linprog(c,A,b,Aeq,beq,xL,xU); %目标为最小的线性规划t=t,y= w%等价转换目标为最大并输出（3） function f=fun3(x);f=x(1)2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2x0=[1;1];A=[2 3 ;1 4]; b=[6;5]; Aeq=[];beq=[];VLB=[0;0]; VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)（4） x=linspace(0,2*pi,30);y=sin(x);z=cos(x);plot(x,y,'r',x,z,'go'),gtext('sin(x)');gtext('cos(x)');（5）x=[1:1:12];y=[9,10,11,12,13,14,13,12,11,9,10,11];a1=polyfit(x,y,3) % 三次多项式拟合系数降幂排列;a2=polyfit(x,y,5) %五次多项式拟合；a3= polyfit(x,y,8) %八次多项式拟合；b1= polyval(a1,x) %三次拟合多项式的值；b2= polyval(a2,x),b3= polyval(a3,x), r1= sum((yb1).^2) %三次多项式误差平方和， r2=sum((yb2).^2) %五次次多项式误差平方和；r3= sum((yb3).^2) %八次多项式误差平方和%plot(x,y,'*') %用*画出 x,y图像%hold on，p lot(x,b1, 'r') %用红色线画出 x,b1 图像%hold on，p lot(x,b2, 'g') %用绿色线画出 x,b2图像%hold on，plot(x,b3, 'b:o') % （6） clear,for n = 1:200x(n)=n;t(n) = sin(n*pi/50);plot(n,t(n),'*'),hold onend,plot(x,3*cos(2*t).*exp(t),'')第二部分题目解答任务一：本文就试卷评阅的几个方面作了对比分析，在试卷分配方面利用0-1规划的分层多目标规划解决了试卷的合理分配问题；在对分数的统计排名方面，建立基于关联度分析的试卷综合排名，并对评委评分的评分准确性进行排名，建立评委的评卷水平对试卷排名的反馈体系。

最佳路径选择方案的优化模型摘要本文对乘公交、看奥运这一实际问题进行了深入的研究，首先对公交乘客进行了心理分析，得出影响乘客出行的三个主要因素分别为：换乘次数、出行时间、出行费用，通过调查研究，得出换乘次数最少是乘客出行考虑的最主要因素，其次是出行时间和出行费用。

然后利用公交乘客的出行过程抽象为站点—线路的交替转换的思想，建立了站点—线路序列模型，从而确定了出行者对路线的所有选择方案。

针对问题一：仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标建立了优化模型一，再以换乘次数最少为第一目标、出行费用为第二目标建立了优化模型二，从而满足了两类不同乘客的需求。

并依靠站点—线路序列模型采用图论中计算方法，分别得到了公交乘客的最少换乘次数，所经过的站点，出行时间、出行费用以及相应的算法。

针对问题二：在问题一的基础上再考虑地铁线路，建立了对应的两组优化模型，并推导出相应的改进算法。

针对问题三：在问题一、二的基础上，考虑出行者可以通过步行到达相邻的公交站点的情况，同样建立了两组相应的优化模型，并给出了相应的计算方法。

然后利用基于换乘次数最少的最优路径改进算法思想，借助MATLAB软件编程分别对问题一和二进行了求解，得到的结果见模型的求解（正文第21、22页）。

最后对所求得的结果进行了对比分析和检验，根据各参数的变化关系，进行了灵敏性分析，本模型主要抓住了乘客的心理需求，实用性强，具有较强的现实意义。

关键词：站点—线路序列最优路径改进算法公交一、问题的提出1.1基本情况我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。

这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择（包括不同线路上的换乘交通工具的路径选择等）问题。

B题：重庆市主城区公交线网的优化与评价姓名学院年级专业学号联系电话相关学科成绩高等数学线性代数概率统计数学模型数学实验英语四级英语六级徐清鹏09电气学院07班0989 87573 475张雅洁09电气学院01班0991 75566 480刘维09电气学院0109 92 83 525重庆市主城区公交线网的优化与评价摘要: “畅通重庆”是建设五个重庆的战略目标之一，通过有效融合公交网和轻轨网的,是实现这一目标的有效途径。

因此对重庆市主城区现有的地面公交线路进行优化和调整具有十分重要的意义。

针对问题一：采用定性与定量相结合的递阶层次分析法(AHP)对重庆市市现有的公交线路网现状进行进行分析，筛选了与公交线路网评价有关的四个方面（线路网络能力、客运能力、经济效益、环境影响）下的12个主要指标建立模型。

建立各个层次的判断矩阵，通过MATLAB 软件计算各个方面的总权重值并进行排序，并采用一致性判断指标决定判断的合理程度。

最后采用线性加权的的方法建立综合评价模型：N =∑E 1i ω1i +∑E 2i ω2i +∑E 3i ω3i +∑E 4i ω4i 3i=13i=13i=13i=1依据查询在重庆市主城通行的公交车数据及与选取指标相关数据，计算出各指标的有关系数，并参照公交线网络指标评价标准的建议值对各个指标评分，得出其得分为，等级为中。

针对问题二：鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra 算法,而是采用了基于公交停靠站换乘功能进行OD 预测。

算出铁路（或轻轨）停靠站的公交客运量。

同时建立了分别以剩余客流量,接运站点数量为目标的优化模型。

然后对OD 客流量剩余值进行确定，得到的由三部分（需要保留的路线，改变的路线布设，合并和消除的路线）构成的“轨道-接运公交网”。

针对问题三:我们主要以轻轨地铁路线为主干线对重庆市主城的公交线路进行规划设计。

由于规划年限较短，我们对乘坐公交的人口，公交车数量，客流量等因素采用马尔萨斯（Malthus ）模型。

最佳公交线路的实时查询模型及算法摘要本文针对查询者的不同需求，为公交查询系统提供了最佳线路查询的模型与算法。

查询者的需求从换乘次数少、时间少和费用少三方面进行考虑。

故查询算法从换乘次数（从实际出发，换乘不超过两次）入手：对直通的任意两站点，可设计出较简单的最佳直通线路查询算法（直通算法）。

故对需要查询的两站点，算法先由线路、站点的原始数据判断此两站点是否直通，若是，便可通过直通算法进行查询。

不论是否存在直通线路，算法都考虑对换乘的情形进行查询。

考虑到城市公交系统中的站点基数较大，可行的换乘方案数也将较大，故查询算法根据所有可行的一、二换乘点必与起、止站点直通的原则，对可能成为给定两站点的换乘点的站点进行了筛选，得到相关站点集，较大的缩小了查询的范围。

得到相关站点集后，建立了反映站点集中任意两站点直通关系的连通矩阵，并通过矩阵乘法，较快地得出了所有可行的一次、二次换乘点。

考虑到所有可行的换乘点可能较多，特别是二次换乘的情形，故查询算法采用分支定界法以较高效率对最佳方案进行了最后的筛选。

在考虑地铁的公交系统时，本文从实际出发，对模型进行了一定的修改。

同时，本文考虑了引入站点之间的步行时间的情况，提出了线路选择的模型。

由于筛选算法、矩阵乘法和分支定界法的高效性，整个查询算法具有很高的效率，并能在换乘次数不超过两次的条件下，求得全局最优解，得出满足查询者不同需求的所有最佳方案。

并且，从系统设计的角度出发，整个系统需要预存的数据量很小，系统的实用性很强。

对给定的六对站点，采用本算法进行查询，在1.7GHZ的CPU环境下，平均运行时间为：1.27秒，最长运行时间为7.43秒，验证了算法的实时性。

同时，对每一对站点，得到了满足不同查询需求的所有最佳线路方案，验证了模型与算法的精确性。

关键词：最佳线路、实时、筛选算法、分支定界一、问题重述第29届奥运会将于今年8月在北京举行，届时有大量观众到现场观看比赛，其中大部分人将乘坐公共交通工具（包括公汽、地铁等）出行。