一种公交调度问题的数学模型与应用

《一种公交调度问题的数学模型与应用》由会员分享，可在线阅读，更多相关《一种公交调度问题的数学模型与应用（23页珍藏版）》请在装配图网上搜索。

1、 本科生毕业论文（设计）一种公交调度问题的数学模型与应用姓名雪燕学号专业资源环境与城乡规划管理指导教师樊明2014年6月2日21 / 23摘要 本文针对公交车调度问题，在尽量满足乘客和公交车公司双方利益的前提下,建立模型，从一个典型工作日客运人数的一般规律和实际生活中人们的生活规律中采集数据，将所给的数据进行转换处理, 以每个时段发出的公交车将乘客进行重新划分, 分析数据,然后由各时段站间最大运送乘客数量求出该时段的最少发车次数, 进而求出需要的最少车辆。文章主要以车辆载客限制、乘客等待时间为约束条件, 以公交公司运营的公交车数最少为目标函数, 建立整数规划模型。通过具体数据分析, 将公交车运

2、行时段分为早高峰、平峰、晚高峰，进而计算出发车时间间隔。由于考虑到乘客和公交公司的利益,力求达到社会总效益最大化，对各时段发车时间间隔以与发车次数做出轻微适当调整，尤其是人多人少时段，并计算出公交车的平均满载率，并对所求结果进行评价关键词：整数模型；时段;站间运送乘客数量；平均满载率Error! Reference source not found.AbstractBus scheduling problem, the author of this paper, to satisfy passengers and bus companies under the premise of the i

3、nterests of both sides, build a model, on the basis of the general regularity of a typical weekday passenger Numbers and the life of people in actual life rule in collecting data, will give the data conversion process, for each time to the bus passengers from the analysis of the data, and then by th

4、e time standing between the maximum number of passengers the least start of the session, and then calculate need minimum of vehicles. Article mainly passenger cars, passenger waiting time as constraint conditions, with the operation of the bus company bus number minimum as objective function, intege

5、r programming model is established in 1. By analyzing specific data, bus operation time can be divided into early peak, peak, peak later, car departure time intervals are calculated. Due to considering the interests of the passengers and bus companies, to achieve social benefit maximization, the num

6、ber of various departure time intervals of time and start to make a slight adjust, especially people have less time, and calculate the average bus load factors, and to evaluate the result of the petitionsKey Words:Integer model; Period of time; The number of passengers stand between transport; The a

7、verage load factors目录1. 引言 （一）研究的背景 （二）研究的容 （三）研究的意义2.公交调度数学模型的建立 2.1公交问题的提出 2.2问题的分析 2.3基本假设 2.4模型的建立3.模型的实践 3.1选取路线的模拟 3.2该线路上公交运行概况 3.3对采集的数据预处理 3.4划分时间段与数据计算（一）定义与划分时间段（二）各时段最大乘客人数统计与分析（三）各时段公交车运营次数 3.5模型计算4.模型的评价 4.1乘客的满意程度 4.2公交公司的利益评价 4.3模型中的误差分析 4.4本文模型评价综述5.模型的改进与应用 5.1模型的改进 5.2模型的推广与应用1引 言

8、（一） 研究的背景随着改革开放和经济的发展，人民的生活水平越来越高,人们的环保和低碳意识也越来越强烈，尤其是这两年雾霾现象越来越困扰着人们的生活，为人们的室外活动造成了很大的影响，因此作为人们出行工具之一的公共交通也备受人们青睐。发展公交是城市交通发展的方向，如果公交方便、准点、舒适、安全，市民就更愿意坐公交，公交才能真正成为城市的主要交通工具，这样城市的交通才能得到改善。因而做好公交车的调度对于完善城市交通环境、改进市民出行情况、提高公交公司的经济和社会效益，具有十分重要的意义（二）研究的容 公交车一方面给人们的出行带来了方便, 另一方面也给公交公司带来了经济效益.对乘客来讲在乘车出行方便的

9、同时也要面临等车难的问题(尤其是在上下班的高峰期), 乘客希望等车的时间尽可能短,即有更多的公交车可乘.而对公交公司来讲低成本高收益是目的, 于是乘客的利益与公交公司的利益在某种程度上出现了矛盾,其实双方利益看似矛盾实则一致。根据一个典型工作日客运人数的一般规律和实际生活中人们的生活规律，如果公交车的发车时间间隔越短，则所需车辆总数就会越多,从而乘客等待时间就越少，而公交公司的成本就会越大，笔者在考虑乘客利益的基础上兼顾公交公司的利益建立公交车调度模型,在力求达到社会效益最大化的目标上，由站间最大运送乘客数量求出该时段的最少发车次数, 进而求出需要的最少车辆, 并对所求结果进行评价（三）研究的

10、意义公交车是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行情况、提高公交公司的经济和社会效益，具有十分重要的意义2公交调度数学模型建立2.1公交问题的提出公交车是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行情况、提高公交公司的经济和社会效益，具有十分重要的意义。利用数据（典型的一个工作日，两个运行方向的各站上下车的乘客总数量统计）来自某条公交线路的客流量调查和运营资料。公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在线路上运行的平均速度为2 0 km/ h 。运行调度要求，乘客候车时间一般不要超过10min，早高峰

11、时一般不要超过5min，车辆载满率不应超过120%，一般不要低于50%，根据所给资料和要求，为此线路设计一个同时兼顾顾客和公交车司机的利益的便于操作的全天（工作日）的公交车调度模型，计算出最适宜的公交车辆数。2.2问题的分析由题目可知：1）这是一个典型的工作日，所以乘客在各站下车的人数是一定的。2）每辆车的满载率为120%，一般不要低于50%。3）乘客的候车时间一般不要超过1 0mi n，但在高峰期不要超过5 mi n 。4）上行方向有14 个站，下行有13 个站。各站的距离已知，车的平均速度已知为20km/h 5）从公司的角度来说车的载满率越高、用的车辆越少越好（即车与车的间隔越长越好）。从

12、乘客的角度来看车的次数越多越好（即车与车的间隔越小越好）。要求：考虑到乘客与公交公司双方的利益来安排这一天发车的时刻表，并求出一共需要多少辆车。根据给定的有关数据，首先应确定三个因素，即乘客到站的规律、乘客下车的规律、发车方案2.3基本假设1)设公交车匀速行驶,不计乘客上、下车的时间;2）各时段到达某车站的乘客数服从均匀分布;3)每个时段的发车时间间隔是相同的;4)在某一时段发出的第一辆车与最后一辆车到达某一站点的时间段在该站等车的乘客都可由该时段发出的车运走;5)某一时段发的车在某站运送的是该时段和下一时段到达该站的乘客, 并且两时段乘客的比例由该站距始发站的距离决定.2.4模型的建立本文建

13、立公交车调度的整数规划模型，将站点分为上行方向和下行方向，以公交车运营前上行方向起点站和下行方向起点站所停公交车数之和最少为目标函数，即：， (式2-1)分别表示公交车运营前上下行方向起点站公交车数，为满足乘客利益，需要一定数量的公交车才能将等车乘客全部运完，要运完上、下行方向的乘客，将行驶全程所需时间定为一个时间段，则每时间段上、下行方向发车次数满足：其中B1=120，B2=50，令各时间段上行方向所发车次为xi，下行方向所发车次为yi，各时间段至少发车次数为pi,各时间段最多发车次数为qi，则满足： ， (式2-2)，表示上行方向数据，表示下行方向数据充分考虑到乘客的利益，上行方向起点站和

14、下行方向起点站在每一时刻必须至少有一辆公交车分别停靠等待乘客，到发车时间后再开离车站，则上、下行方向起始车站公交车数量限制为： （式2-3）其中，表示上行方向起始站在i时刻发车前由起始站开出的车次数，表示上行方向起始站在i时刻发车前由末站开进起始站的车次数，表示下行方向起始站在i时刻发车前由起始站开出的车次数，下行方向起始站在i时刻发车前由末站开进起始站的车次数， 为了维持公交系统的平衡，满足以后公交车的正常运营，在车次安排以后，一个工作日上行方向和下行方向所发车次还应该分别相同，即： 鉴于本文是基于整数规划模型，最后每个时段所发车次还应该是整数。综上所述，本文得到如下模型：目标函数为： （式

15、2-1）约束条件为： 3模型的实践3.1选取路线的模拟选取城市某条公交线路上的客流和公交运营数据资料为例，对上面所建立模型进行检验，数据来自该线路一个典型工作日两个运营方向上各站点上下车的乘客数量。运行线见图3-1 图3-1 公交线路示意图3.2该线路上公交运行概况 公交公司每辆车标准载客100 人，客车运行的平均速度为20公里/小时。候车时间一般不要超过10分钟，高峰时一般不要超过5 分钟，车辆满载率不应超过120% ，一般也不要低于50% ，还给出各站点之间距离等。3.3对采集的数据预处理 首先对所给数据进行处理合总，可以计算出上、下行方向路线长度分别为： （式3-1）其中表示上行方向路线

16、长度，表示下行方向线路长度，分别表示上下行方向站间距离由公交车平均速度V=20km/h,并结合时间，距离，速度的关系公式可计算每趟车跑一趟平均消耗时间上下行方向分别为。我们可以粗略认为公交车单行运营一次大约需要45分钟。 3.4划分时间段与数据计算 （一）定义与划分时段： 一般可以按一小时为一时段，把5：00至6：00，6：00至7：00，22：00至23：00分别记为第1 时段，第2 时段，第18时段，由第i(i = 1, 2, .18) 个时段在第j 站等车的人数 （m = 1, 2 .1 表示上行方向，2 表示下行方向）可知车开到第j 站时车上现有的总人数R总为： （式3-2）由 式3-

17、2可知，当k 分别取1,2, ,13时就得到公交车在上、下行方向各站点车上现有人数，从而得出每一时段最拥挤站点与车上最大现有乘客数： （式3-3）（二） 各时段最大乘客人数统计与分析：由于本文所研究公交车单行运行一次大约需要45分钟，因此本文以45分钟作为一个时间段，则将原来18个时间段重新划分成24个时间段，将计算出的上行方向以一小时为一时段的最大乘车人数转化为以45分钟为一个时段的车上现有最大乘车人数表，结果如下表3-1与折线图3-2：表3-1 上行方向各时段最大乘客人数上行方向各时段最大乘客人数时段人数时段人数152613661216471465632726159694376416160

18、052029172079614411811427106319565889520348910172130810939222401186023143127802415资料来源：交通统计年鉴图3-2 上行方向车上各时段最大乘客人数折线图由以上结果知，以每45分钟一个时段时，早高峰对应在2,3,4,5 时段。同理可算得下行方向的数据表3-2与折线图3-3：表3-2 下行方向各时段最大乘车人数下行方向各时段最大乘客人数 时段 人数时段人数140138632221417643152015226543389162081513771719796103318123278571910218622201006987

19、92176310108922321111229232341277824141资料来源：交通统计 图3-3 下行方向各时段最大乘车人数 由表3-2与图3-3可找出下行方向的高峰期集中在3,4,5时段。（三）各时段公交车运营次数： 考虑到公交公司的利益，在公交车能把全部候车乘客运完的前提下，可以放宽乘客一般等车时间不超过10分钟的条件。在早高峰时，考虑乘客的利益，等车时间一般不超过5 分钟，将其转化成公交车运营次数为: 考虑到车辆满载率条件的限制，将每45分钟为一时段的车上现有最大乘车人数转化成每时段所发车次数满足：(式3-4)为了照顾乘客利益，在上、下行方向公交车开始运营阶段和完毕前阶段，将上限

20、或者下限不足一辆的按一辆计算，即取整原则，用MATLAB编程可分别计算出上、下行方向所发车次数上、下限见表3-4，表3-5。本文重点研究在满足顾客利益的前提下的各时段至少发车次数，即最终优化次数，目的是得到社会效益最大化。表3-4 上行方向段发各时车次数表时段次数最终优化次数时段次数最终优化次数1551366214141455322221588431311613135171717171761212181010799195587720359882135108822251177231512772415表3-5 下行方向各时段发车次数表时段次数优化次数时段次数优化次数1151377215141515

21、313131519194272716171751111171616699181010777199985520889772166109922351110102325126624153.5模型的计算采用统计软件编程进行计算，结果整理如下：公交车运营前上行方向起点站站所停公交车数为辆，下行方向起点站站所停公交车数为辆，由公式2-1得公交公司一共需要公交车辆，上、下行方向每天所发车次均为236 次。进而计算出上、下行方向每时段所发车次，再依据假设中乘客的到达模式与整数原则，用公式可以得出，站 的简单发车时刻表（用各时段发车间隔时间简述）如下表3-6：表3-6 上、下行方向各时段发车时间间隔上行方向下行

22、方向时段间隔时段间隔 时段间隔时段间隔19139191362314929143321563315242163421635317354173621826518573199761958620989206962123962171062223105222311623451152345 由于上述24个时段的划分只是一种统计划分，首发车可以在5:00之前发车也可以在5:00之后，在不知道其他限制条件的情况下也可以定为5:00发车。4.模型的评价4.1乘客的满意程度： 我们用平均等待时间(即所有乘客等待时间的平均值)评价乘客的满意度，由以上所求的发车间隔，我们可用公式计算出高峰期（上下行方向的2,3,4,5

23、时段）和一般平常期的平均等待时间：（式4-1）故而可以认为乘客还算是满意的。4.2公交公司的利益评价： 我们用用平均满载率(一天中发的车的载客能力利用率)评价公交公司的利益.早高峰发车间隔决定乘客的候车时间，也决定公交车的满载情况，用以下公式计算每时段满载率以与平均满载率： （式4-2） （式4-3）通过计算可得，公交车平均满载率上行方向为:，下行方向为： ，平均满载率说明公交车的满载情况，因此从公交公司利益出发，在兼顾乘客利益的基础上来说，所得结果还是相当满意的。4.3模型中的误差分析在模型求解时为了计算方便，本文在数据处理时对数据做了近似取值，其中在按45分钟一个时段对最大等车人数进行转化

24、时对数据进行取整，这样等车人数会减少，但在计算上、下行方向的车辆上、下限时进行取整加1，这使得计算出来的车辆数增大，这样在两方面的近似取值对最终的结果相对来说不会产生太大的影响，因此在本模型中由于数据处理带来的误差是可以承受的。 4.4本文模型评价综述 本文在考虑公交公司利益的基础上，兼顾乘客的利益，建立了整数规划模型，以公交公司利益优先并兼顾乘客利益，得出了上、下行方向每天最少公交车数和发车间隔表。由于在建模过程中认为乘客的到达服从均匀分布，而实际上乘客到站不可能是均匀的，特别在高峰期间，乘客到站的不均匀使建模结果产生很大的偏差，并且由于本文对模型进行严格的时间控制, 使得在整个运送过程中没

25、有乘客等待时间超过10min, 并且平均等待时间达到一个较小的值, 这对乘客来说是非常满意的, 同时也有利于提高公司的社会效益.而对公交公司来说, 虽然车的载客能力利用率已经较大, 但在早晨和晚上的时段, 安排的车的满载率远远低于50%, 因此可以适当地减少早上和晚上的发车班次, 以提高车的利用率.并且严格保证乘客的利益为兼顾原则。5模型的改进与应用5.1模型的改进1)求发进一步车次数时可以考虑时间长一些, 即把不同的时段合在一起考虑, 可以减少发车次数.2)找到一个更好的评价函数, 能够同时对公交公司的利益与乘客的满意度进行比较.3)每个站点都可以看作一个服务系统, 可以近似看作一个排队问题

26、, 整个系统就可以看作一个多服务系统的排队问题.5.2模型的推广与应用 为了更好地设计调度方案, 可以在节假日或者连续多天进行调查, 采集数据, 并且在全天的运营调查中调查各站所有乘客的下车地点和他们分别坐了几站.而在公交系统中实际是多条路线在运营, 每条路线都可以用这种方法来考虑, 只是要多考虑一下各条路线之间的联系(因为有的路线是重合的).参考文献1赫孝良, 戴永红, 周义仓. 数学建模竞赛赛题简析与论文点评M.:交通大学,2002,6.2石爱菊, 周林.公交车优化调度中的几个问题的研究 .数学的实践与认识, 2002, 32(2):189-195.3朱道元.数学建模案例精选 .:科学,2

27、0034傅昌建, 彩霞, 敏.关于公交车调度的优化问题 .工程数学学报, 2002, 19(1):89-94.5龚劬, 琼荪, 何中市, 等.数学实验 .:科学, 2000.6启源,金星,叶俊.数学模型M. :高等教育,2003.7肖华勇. 基于MATLAB和LINGO的数学实验M. : 西北工业大学,2009.8董强, 超慧, 马熠. 公交车调度问题的研究J. 工程数学学报,2002,19(5):59-66.9谭泽光, 启源.公交车调度问题的数学模型 .工程数学学报, 2002, 19(1):101-106.10戴明强, 卫军, 新鹏. 一类公交车调度问题的数学模型与其解法J.运筹与管理,2

28、004,13(01): 74-76.（交待选题背景，文章结构等容）正文中，凡是一级标题，都用三号宋体加粗，居中，其上下空一行（空行也是小四宋体）。二级标题用小四宋体加粗。三级以下与正文全部用小四宋体，不加粗。全文用1.25倍行间距。注意：小数点要用小四宋体，不然，看不清，不要用英文小数点。（空行，小四）一、一级标题三号宋体加粗居中，上下空一行（空行，小四）（一）二级标题缩进两格小四号宋体加粗，括号后不加顿号，完毕不用标点符号段首缩进两格。除一级标题下空一行（小四字一行），全文均不再空行即段前段后为0行。正文除一级标题外，全部用小四号宋体字，1.25倍行间距，请不要使用自动编号。表下的“资料来源

29、：”用仿宋字。1三级标题缩进两格，小四号宋体，注意1的后面用圆点而不是顿号（1）缩进两格，括号后不能再加顿号（2）2（1）（2）（二）二级标题缩进两格，小四号宋体加粗，注意括号后面不加顿号1（1）（2）2（1）（2）以下为论文表的格式例，表的行、列多少可以根据需要在菜单中的“表格”中选择“插入”或“删除”来操作。表体一要放置在页要居中；表文字一般使用五号字居中，根据情况，表编序按一级标题序号加横杠和序数的方式。如表1-1、表2-1、表3-1、依次进行。论文中采用的表，必须在正文文字中显示，如“见表1-6”等。一般表序号以表的左侧为起点缩进两格，表题名称居中小四字宋体加粗，有“单位”的，居右适当

30、位置。资料来源用五号仿宋体，以表的左侧线为起点缩进两格。如下样式：表1-6 表标题名称 单位：资料来源：（用仿宋五号字）论文中图的格式例如下，居中放置，图名（图序和图名均用小四宋体号字，加粗）在图下居中，图序用图1-1，图1-2编排，图序号与图名中间空2格。“如以下图1-3”。（编号采用一级标题序号加横杠加序数的方式。）图1-3图名论文中公式的格式例如下，其序号编排要求如上面表。公式请用Word中的“公式编辑器”编辑，你可以，然后在自定义对话框中的“命令”项的“类别”列表中选择“插入”，在“命令”列表中选择“公式编辑器”，用左键按住拖到上面的工具栏中。这样你就可以单击上面的图标“”开始编辑公式

31、了。另一种编辑公式的方法是在菜单中的“插入”中选择“对象”，在“对象列表”中向下拖动选择“Microsoft公式(或Microsoft Equation)”，然后单击“确定”。公式编号用公式1-1，公式1-2等进行。一般居中放置。公式要在正文中指出见公式2，如下：Y=A+BX （式1-2）二、单击此处键入题目（一）单击此处键入题目直接引语须用双引号标注，注明主要责任者与时间。1单击此处键入题目（1）（2）2单击此处键入题目正汉（1997）指出： “交易费用理论在逻辑关系上还有一个重大的缺陷即没有将市场的不确定性和市场风险纳入他们的分析框架。” 间接引语须加小括号注明主要责任者与时间。由于某些交

32、易的特殊性使交易双方之间存在严重的信息不对称现象，掌握信息的一方可以通过偷懒、欺诈等手段获取个人利益，不完全履行合约。这种由交易的特殊性而带来的个人私利就是机会主义行为的收益，它能够强化个人的机会主义行为。（威廉姆森，1979）说明：引用他人论点，不论是直接引用还是间接引用，均按照GB/T 7714-2005文后参考文献著录规则，正文中采用著者出版年制。参考文献则按引用的先后顺序，用尾注方式列在文末，单独一页。正文引用的文献采用著者一出版年制时，各篇文献的标注容由著者姓氏与出版年构成，并置于小括号“( )”。倘若只标注著者姓氏无法识别该人名时，可标注著者，例如中国人著者、朝鲜人著者、日本人用汉

33、字的著者等。集体著者著述的文献可标注机关团体名称。倘若正文中已提与著者，则在其后的“( )”只须著录出版年。示例:多次引用同一著者的同一文献主编靠编辑思想指挥全局已是编辑界的共识(忠智,1997),然而对编辑思想至今没有一个明确的界定，故不妨提出一个构架参与讨论。由于“思想”的涵是“客观存在反映在人的意识中经过思维活动而产生的结果(中国社会科学院语言研究所词典编辑室,1996)1194。所以“编辑思想”的涵就是编辑实践反映在编辑工作者的意识中，“经过思维活动而产生的结果”。中国青年杂志创办人追求的高格调理性的成熟与热点的凝聚(彻东，1998)，说明其读者群的文化的品位的高层“方针”指“引导事业

34、前进的方向和目标”(中国社会科学院语言研究所词典编辑室，1996)454,对编辑方针，1981年中国科协副主席裴丽生曾有过科学的论断，“自然科学学术期刊必须坚持以马列主义、思想为指导，贯彻为国民经济发展服务，理论与实践相结合，普与与提高相结合，百花齐放，百家争鸣的方针。”(裴丽生，1981)，它完整地回答了为谁服务，怎样服务，如何服务得更好的间题。三号宋体其下空一行，以下的内容，全部用小四宋体，1.25倍行间距。参考文献标示，严格按照GB/T 7714-2005文后参考文献著录规则，采用著者出版年制。要求10篇以上。参考文献1作者书名M出版地：名，yyyy程恩富.西方产权理论评析M.:当代中国

35、，1997.2作者文章名J杂志名，yyyy（期序号）若有卷标时年后要用逗号分开写卷号接括号，即yyyy,卷号（期序号）.正汉.寻求对企业性质的完整解释：市场分工的不完备性与企业的功能J.经济研究，1997(7）3作者文章名N报纸名，yyyy-mm-dd（版次）.王可.房地产市场的拐点论N.房地产报，2006-01-25（2）4作者文章名EB/OL（发表日期）引用日期.访问路径.萧钮.出版业信息化迈人快车道EB/OL.(2001-12-19)2002-04-15. Creader/news/20011219/9.htm.OnlineComputerLibraryCenter,Inc.Histor

36、yofOCLCEB/OL.2000-01-08.h ttp:/.oclc.org/about/history/default.htm.5网上书如下：作者.书名M/OL.出版地：，出版日期引用日期.访问路径.6网上杂志如下：作者.文章名J/OL.杂志名，发表日期（期序号）引用日期.访问路径.江向东.互联网环境下的信息处理与图书管理系统解决方案J/OL.情报学报，1999,18(2)：42000-01-187O.E.Williamson, Transaction Cost Economics: The Governance of Contractual Relations,J.Journal of Lawand Economics, October 1979, 22: 233-261.致 （提示：致为宋体三号字，下空一行。下面容为小四宋体，1.25倍行间距。）