公交车调度问题数学建模.docx
《公交车调度问题数学建模.docx》由会员分享,可在线阅读,更多相关《公交车调度问题数学建模.docx(13页珍藏版)》请在冰点文库上搜索。
公交车调度问题数学建模
作品编号:
B题
2014年铜仁学院大学生数学建模竞赛
参赛作品
作品名称
公交车的合理调度
队员1
蒋宇数学与应用数学53
队员2
张明数学与应用数学79
队员3
孔小晴数学与应用数学55
竞赛时间
2014年6月20日—22日
成绩评定1
成绩评定2
成绩评定3
最终评定
铜仁学院数学科学学院制
摘要
完善的公共交通体系反应了一个城市经济社会发展的水平,公交车系统是公共交通的重要组成部分。
公交车线路的合理规划与公交车的调度既关系到公交公司的经济效益,同时也涉及到广大市民对于城市发展的社会满意度,即城市的社会声誉。
根据所给的客流量及运营情况排出公交车调度时刻表,以及反映客运公司和乘客的利益有多个指标,建立了乘客的利益及公司利益两个目标函数的多目标规划数学模型。
基于多目标规划分析法,进行数值计算,从而得到原问题的一个明确、完整的数学模型,并在模型扩展中运用已建的计算机模拟系统对所得的结果和我们对于调度方案的想法进行分析和评价。
首先通过数据的分析,并考虑到方案的可操作性,将一天划为;引入乘客的利益、公司利益作为两个目标函数,建立了两目标优化模型。
通过运客能力与运输需求(实际客运量)达到最优匹配、满载率高低体现乘客利益;通过总车辆数较少、发车次数最少表示公司利益建立两个目标函数。
应用matlab中的fgoalattain进行多目标规划求出发车数,以及时间步长法估计发车间隔和车辆数。
关键字:
公交车调度;多目标规划;数据分析;数学模型;时间步长法,matlab
一问题的重述:
假设铜仁市四路公交车线路上每个站台工作日内的乘客数分布情况与“铜仁学院站台”相同,建立相应数学优化模型,给出该公交线路一个工作日内公交车的合理调度方案,路公交线路上下行方向各16站,总共有L辆汽车在运行。
这些汽车将按照发车时刻表及到达次序次发车,循环往返地运行来完成运送乘客的任务。
既要兼顾市民乘车满意度,又充分考虑公交公司经济效益的最大化。
4路公交车站点客流量见下表(粗略统计)
从实验中学到五中
站点名称
实验中学
江华国际大酒店
公园道一号
铜仁职院
上车人数
11
3
1
1
下车人数
1
1
0
0
等待时间
0
3.8
5
2
站点名称
学院附中
铜仁学院
沙子傲路口
供电局
上车人数
1
2
5
1
下车人数
0
4
1
0
等待时间
1.5
2
3.8
3
站点名称
二完小
蓝波弯
地王广场
锦江广场
上车人数
3
4
8
3
下车人数
0
1
0
1
等待时间
5.3
1
4.1
3.8
站点名称
兴市桥
梵瑞酒店
三江公园
五中
上车人数
3
1
3
3
下车人数
2
3
3
9
等待时间
1.7
1
0.5
2.5
从五中到实验中学
站点名称
五中
三江公园
梵瑞酒店
兴市桥
上车人数
17
3
0
1
下车人数
0
1
1
1
等待时间
3.5
1.2
2.8
4.8
站点名称
锦江广场
地王广场
蓝波弯
二完小
上车人数
8
3
2
3
下车人数
2
1
1
0
等待时间
0
9
3.3
1.6
站点名称
供电局
沙子傲路口
铜仁学院
学院附中
上车人数
1
5
8
3
下车人数
1
2
2
1
等待时间
5
4
0
9
站点名称
铜仁职院
公园道一号
江华酒店
实验中学
上车人数
3
4
8
3
下车人数
0
1
2
0
等待时间
5.3
1
2
7
1已知数据及问题的提出
我们要考虑的是铜仁市的4路公交线路上的车辆调度问题。
现已知该线路上行的车站总数N1(=16),下行的车站总数N2(=16),并且给出每一个站点上下车的人数。
公交线路总路程L(=L);公交行驶的速度V=20km/h;运营调度要求,车辆满载率不应超过r=120%,一般也不要底于r=50%。
现要我们根据以上资料和要求,为该线路设计一个公交公司发车时间的调度方案、一共需要多少辆车、公交车道路行驶过程中的速度以及公交车车型的选择的方案。
并给出刻划乘客和公交公司双方利益、满意程度的指标,进行评估等。
2准备工作
我们首先来看一下上、下行线的有关客流量数据。
由给出数据对数据进行处理,可简化模型求出每分钟的平均客流量。
从实验中学到五中
站点名称
实验中学
江华国际大酒店
公园道一号
铜仁职院
上车人数
11
0.8
0.2
0.5
下车人数
1
0.3
0
0
等待时间
0
3.8
5
2
站点名称
学院附中
铜仁学院
沙子傲路口
供电局
上车人数
0.6
4
2.0
0.8
下车人数
0
1
0
0.3
等待时间
1.5
2
3.8
3
站点名称
二完小
蓝波弯
地王广场
锦江广场
上车人数
3
4
8
3
下车人数
0
1
0
1
等待时间
5.3
1
4.1
3.8
站点名称
兴市桥
梵瑞酒店
三江公园
五中
上车人数
3
1
3
3
下车人数
2
3
3
9
等待时间
1.7
1
0.5
2.5
从五中到实验中学
站点名称
五中
三江公园
梵瑞酒店
兴市桥
上车人数
17
3
0
1
下车人数
0
1
1
1
等待时间
3.5
1.2
2.8
4.8
站点名称
锦江广场
地王广场
蓝波弯
二完小
上车人数
0.5
0
0
0
下车人数
1
2
2
5
等待时间
0
9
3.3
1.6
站点名称
供电局
沙子傲路口
铜仁学院
学院附中
上车人数
1.8
1
6
1.2
下车人数
1.2
3
6
3.6
等待时间
5
4
0
9
站点名称
铜仁职院
公园道一号
江华酒店
实验中学
上车人数
2
1
0
2
下车人数
1
2
4
3
等待时间
5.3
1
2
7
请注意这个表格是对数据的简单处理,剔除、修正一些不合理的数据,并且以人/分钟为单位保留一位小数进行四舍五入。
需要注意:
下车平均客流量是将在每个站点的下车人数进行时间划分,是在以无论等多长时间乘客都不会离开的前提下假设的;表格中出现的0不是说此站没有人,而是客流量太小可以忽略不计。
然后将各站的上车平均客流量和下车平均客流量之和进行比较,大于或等于3.0人次每分钟的定为大站,认为在该站上下车需耗时2分钟,即Δti=2;1.0人次每分钟至3.0人次定为中等站,消耗1分钟;上下车耗时1分钟小于5000人为小站,上下车耗时0.5分钟。
3问题的初步分析及基本假设
制定公交车调度方案需要考虑的因素非常多,且很多因素都是随机的。
为了抓住重点,简化模型建立及求解,必须作一定的简化假设和设定。
1)汽车从起点站发车后,都能在额定的时间里到达终点站;
2)汽车行驶过程都看做匀速行驶;
3)乘客在规定的时间内都可以乘车;
4)乘客的满意程度只以他所乘的车的拥挤程度来衡量;
5)在车站等待的人绝大多数不会离去。
6)公交站点确定,距离的调整不考虑特殊情况
7)根据给定数据客流量是一个平均值,则考虑调度问题只需考虑一个时间段即可。
8)车辆上行或下行到达终点时,所有的乘客必须下车;
9)在同一个时间段内,相邻两辆车发车时间间隔相等;10)对全天而言客车公司基本把所有的顾客运完;
4 模型的建立
4.1符号说明:
N 某时段发车次数(注:
由于数据给定为平均客流量只需考虑在一个完整的周期内的车次,即从始发站到终点站的这段时间)
B某时段的平均满载率
T=L/v+Σti一辆公交从始发站到终点站的整个时间
ai第i站上车平均客流量
R=T*Σai
B=R/(c×N) R为某时段的总上车人数,c=100人/车次
α 供求匹配比 α=(ΣV)/(ΣQ)
k 控制参数
Q 某时段运客能力(人×公里)
Q=某时段发车次数Ni×每辆车标准载客量c×单程(上行或下行)总运行距离L。
其中,上行时,L公里;下行时,L公里
V某时段的需要运客量(人×公里)
V=Σj(xj-yj)*T*Lj j∈(24,12...,1,0),上行方向;j∈(0,2,3,...24),下行方向。
其中,xj为某时段内Aj站的上车人数;yj为某时段内Aj站的下车人数
Lj为Aj站距该单程方向上终点站的距离。
问题一:
发车次数的确定
依据前面的分析,兼顾乘客与公交公司双方的利益,分别对单程的上行路线和下行路线建立如下的多目标规划模型:
目标函数:
Ⅰ 供求的最优匹配min(Q×B-V)^2
Ⅱ 各时段的发车车次均最小min{N}
约束条件:
① 各时段的平均满载率限制0、5≤B≤1、2
② 供求匹配比限制α≤k
4、2目标函数说明:
目标函数Ⅰ使某时段的运客能力Q与运输需求(实际客运量)V达到最优匹配,β反映满载率高低的影响。
目标函数Ⅱ使所需的最大发车次,在满足约束条件下尽可能少,以使总车辆数较少。
4、3约束条件说明:
条件①是限制满载率满足运营调度要求,是考虑了程客的利益。
条件②是限制供求匹配比α小于常数k。
补充约束条件:
为使始发站车场的每天起始时刻的车辆数保持不变,需使总发车次数与总收车次数相等,即必须使单程车次总数达到匹配(N1=N2),而N1不能减少(受满载率限制),因此我们在求解下行方向的Ni时增加约束ΣN2i=N1.在增添约束条件ΣN2i=N1之后,用二次规划求得各时段发车次数N1i和N2i。
问题二:
发车数量及发车间隔的确定
(1)发车间隔的确定
在这部分,我们采用时间步长法,根据假设一个时段内发车间隔时间ti相等,则ti可由N确定,从而得到发车时刻表。
按此发车时刻表模拟实际运行过程,目标是确定满足时刻表的最小车辆数n,统计各项运营指标,搜索最优调度方案解。
(2)模型一:
确定最小车辆数目n
根据“按流发车”和“先进先出”的原则,对起点站,在发车时刻应至少有一辆车可以发出(处于等待发车状态)。
若有多辆车,则先进站者先发车,其余车辆“排队”等候;若无车可发,则出现“间断”。
完整的运营过程应保证车辆严格按时刻表发车,不发生间断。
设A23站和A0站分别有车场A和B,从车场中不断有车发出,同时接受车进场,则车场中的车的数目是随时间变化的状态量。
用Na和Nb来描述车场A和车场B中要满足车流不间断所需的最小数目,分别搜索其在运行过程中的最大值,则所需最小车量数目n=Na+Nb。
(3)模型二:
统计各项运营指标
确定各项运营指标,采用模拟统计的计算方法,对不同的运营指标进行定量计算,主要功能是通过定量分析运营指标来检验方案的可行性,以确定方案调整。
由于车次与发车时刻一一对应,而车辆的队列顺序是不发生改变,因而对所需车辆进行统一编号,则对每一车次,与其对应的车辆编号是确定的,故我们直接对第k次车进行考察。
我们统计的指标及其定义如下:
平均满载率 上行方向 B01=(ΣkΣj1B(k,j1)/(N1·J1)
下行方向B02=(ΣkΣj2B(k,j2)/(N2·J2)
满载率分布可以由B(k,j)确定。
平均候车时间上行方向T1=(ΣkΣj1T(k,j1)/(N1·J1)
下行方向T2=(ΣkΣj2T(k,j2)/(N2·J2)
符号说明:
D(k,j)第k次车到第j站时上车与下车的人数之差;(已知)
C(k,j)第k次车离开第j站时站台上的滞留人数;C(k,j)=C(k-1,j)+D(k,j)-(120-B(k,j-1)
B(k,j)第k次车离开第j站时车上的人数;B(k,j)=B(k,j-1)+D(k,j)+C(k-1,j)-C(k,j)
T(k,j)为第k次车离开第j站时站台上滞留者的滞留时间;T(k,j)=C(k,j)·ti
β(k,j)为第k次车离开第j站时的满载率,β(k,j)=B(k,j)/100;
N1,N2为一天单程所发的车次总数;J1,J2为单程站台总数;
4.4 模拟结果及统计指标分析
设全程的长度为L=12km,车的平均速度为v=20km/h,假设站点间的距离为等距的。
根据大小站及距离得出上行方向需要的时间为67分钟,下行方向需要的时间为66.5分钟,上行方向乘客需求量V=189下行方向乘客需求量V=90。
根据计算得上行N=10,B=1。
下行N=9,B=1。
上行平均每4分钟发一辆车,下上行平均每5分钟发一辆车
5调度方案:
认为在该路线上运行的总车数固定不变,形成序贯流动的车流,依照“按流开车”和“先进先出”的原则,按发车时刻表发车。
6模型的进一步讨论
1)关于采集运营数据的讨论
由于我们假设在一个时段内乘客到站服从均匀分布,而实际中乘客到站时间不可能都服从均匀分布。
特别是数据给出的是一个公交车在每一站的经验值就会使模型结论误差较大。
我们建议以下几种改进采集方式的方法:
(1)由于实际问题中统计的人数不可能服从均匀分布,而且存在一天中不同时间段分高峰期和低峰期。
所以数据的统计应按照一天为单位分段统计更加合理。
(2)采取不等的统计人数的间隔时间在高峰期的情况下,为削弱乘客到站时间不均匀分布带来的影响,可适当减小统计的间隔时间但统计时间加密应有一定限度。
对客流量很小的时段,我们可适当增大统计的间隔时间。
(3)增加能反应有关滞留人数的统计数据。
(4)按相等到站人数来区分时间段的统计方法是统计达到一定到站人数时的时间点,其优点是能较为准确地反映客流量的变化情况,有利于按其分布的疏密进行车辆调度,以更好的满足乘客的需要。
(5)考虑到实际问题中,公交线路存在单车场和双车场。
单车场问题相当于将重点站看作一个中间站点,即把双车场模型的方法延伸到48个站点进行单方向运算。
方法同双车场的上行运算,所以不再重复。
(6)单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本;双车场调度方案的运营成本小,更好的兼顾到乘客与公司双方的利益。
我们建议,在有双车场的条件下选取双车场调度方案更好。
当需进行路线规划,需要选取单车场或双车场时,建议根据实际所需成本来选取方
案。
7模型的评价
本文的优点如下:
1)模型的主体是采用时间步长法,模拟生成的发车时刻表的实际运行过程,准确性高,容量大,逻辑性严格,计算速度快,具有较强的说服力和适应能力。
2)定义了能定量衡量我们的调度方案对乘客和公交公司双方利益满足程度的统计指标。
3)在求最少车辆数时,将两个车场看作两个发射源,通过对两个车场的存车状态的实时模拟,形成不间断的运营过程,从而求得所需车辆数目。
本文的缺点是:
1)对于运营数据的采集方式,只给出了一些原则和想法,没有经过仿真验证。
2)对于乘客到站的分布,直接将人流量假设为均匀分布,没有对其他分布的情况再作讨论。
可将分布时段划分为高峰期,平常期,低峰期。
3)对于车辆行驶速度假设为匀速,在实际运营过程存在,站点的停留。
未将停留时间考虑进去可能产生误差。