全国大学生数学建模竞赛中公交车调度问题的求解.docVIP

全国大学生数学建模竞赛中公交车调度问题的求解 成都航空职业技术学院 lounudofCh~.g,hAeronautic Vocatio~mlamp;Technicall 2002年6月第2期(总第5l期) Vo1.18No.2(SerialNo.51)2002 全国大学生数学建模竞赛中公交车 调度问题的求解 成都航空职业技术学院刘红张强杜瑜 摘要:本文首先对题目进行了综合分析,分析出模型的主要特点,找出问题及解决问题的主 要方法一阿克玛(Akirna)方法;然后对该模型进行了详细求解,最后对这个调度问题给出了一个明 确,完整的数学模型,并在采集运营数据方面给出了相关的建议,同时也对该模型进行了推广. 关键词:阿克玛(Akirna)方法曲线拟合计算机模拟 我国正处在加快城市基础设施建设阶段,城市 建设中,交通问题是关系到经济发展速度的一个重 要因素.在交通问题中,公交是一个城市的命脉,为 此,我们有必要对城市的公交车调度问题找出一套 最优化的方案,以期在城市基础设施建设中作出自 己的贡献. 1.问题提出 公共交通是城市交通的重要组成部分,作好公 交车的调度对于完善城市交通环境,改进市民出行 状况,提高公交公司的经济和社会效益,都具有重要 意义.下面考虑一条公交线路上公交车的调度问 题,其数据来自我国一座特大城市某条公交线路的 客流调查和运营资料. 该条公交线路上行方向共l4站,下行方向共l3 站,给出的是典型的一个工作日两个运行方向各站 上下车的客数量统计.公交公司配给该线路同一型 号的大客车,每辆标准载客100人,据统计客车在该 线上运行的平均速度为20公里/小时.运营调度要 求,乘客侯车时间一般不要超过l0分钟,早高峰时 一 般不要超过5分钟,车辆满载率不应超过120%, 一 般也不要低于50%. 试根据这些材料和要求,为该线路设计一个便 于操作的全天(工作日)的公交车调度方案,包括两 个起点站的发车时刻,一共需要多少辆车,这个方案 以怎样的程度照顾到了乘客和公交公司双方的利益 等等. 2.问题总体分析 通过对问题的分析和理解,本问题有以下几大 特点: 首先,本模型是个双目标(公交公司的最大效益 和乘客的满意度)最优化模型,但在本模型中,目标 一 乘客的满意度(服务质量和候车时间的长短),侧 重于候车时间的长短上,而候车时间的长短直接体 现在合理的公交车调度上,因此,此双目标问题可通 过转化为单目标问题得以解决;同时可以预测出,整 个模型的建立,按常规用一个完整的数学解析式建 立数学模型是非常困难的,在此可考虑把问题分解 处理的办法,本模型的求解就是采用分解成一些小 问题求解,然后采用部分枚举法得出最优解. 其次,本模型给出了大量数据,这是自开展此项 竞赛以来数据最多的一道竞赛题,对大量数据的处 理,通常都要用到阿克玛(Akima)方法(拟合的方 法),本题将充分使用此方法.首先将所有数据拟合 成一条曲线,然后通过曲线的特点得出它的规律一 曲线服从泊松分布,最后得出不同站点间的人流量, 通过人流量以及其它因素得出发车量和发车时间分 布. 再次,由于本模型数据多的特点,采取先用数据 模拟出曲线,再由曲线得出泊松分布函数,在整个求 解过程中,阿克玛(Akima)方法是解决整个问题的关 键,由于此方法的特点是误差较大,因此,本模型对 误差的合理性及应用性检验成为本模型的又一重点 和难点. 最后,我国是一个人口大国,尤其是大,中城市, ? 35? 全国大学生数学建模竞赛中公交车调度问题 人口更加稠密,因此在现实生活中,经常存在排队现 场,另外,随着计算机技术的迅速发展,需要计算机 对大量数据进行处理,本文在对排队问题,尤其是调 度问题以及计算机对数据的处理方面得出了较宝贵 的思想方法和解决办法. 3.基本的假设 (1)假设交通畅通无阻,客车不会在路上发生任 何意外. (2)假设在同一线路上的客车彼此赶不上,而且 不存在超车的问题. (3)假设上下乘客互不干扰,即前门上后门下. (4)假设每名乘客上下车的时间分别服从[4, 12][1,7]的均匀分布. 站. (6)假设公交公司配给该线路同一型号的大客 车. (7)假设公交车在站停留时间不规定在乘客等 待时间范围内. (8)假设同一时间段内前后两辆车的载客情况 相同. 关于假设,需要说明的是:假设非常重要,假设 过多,问题的实用面减少,假设过少,对问题的求解 增加较大难度,同时,假设还分常规假设和重点假 设,常规假设一般要与实际相符合,重点假设主要是 为了求解.如上述假设(4),(8)就是重点假设,但需 注意,假设必须检验,特别是重点假设. (5)假设客车在站停留期间不会有乘客到达车4.符号的说明 符号假设内容 T发车时间间隔(分) Nh汽车总量(辆) (i一1)T第i辆车离开起点站