公交线路的车辆调度问题_2001年全国大学生数学建模竞赛B题.pdf

文章编号 1671 2250 2002 01 0014 05 公交线路的车辆调度问题 2001 年全国大学生数学建模竞赛 B 题 何永强1 黄 剑2 陆新根1 1 浙江万里学院工程技术系 98 级学生 宁波 315100 2 浙江万里学院计算机系 00 级学生 宁波 315100 指导教师 郭秋丽 岑仲迪 摘 要 通过计算机模拟仿真得到各间隔的参数 而后转化为多目标规划再求解 对已有的数据进行分析 运 用模糊聚类分析法 将一工作日分为若干段 问题 1 对模型 1 考虑了乘客的上下车人次都是定长 均匀 分布 通过计算机仿真求得各间隔的参数 然后通过多目标规划进行求解 并得到最终解 对于模型 2 我们考虑了乘客的上下车人数都是服从 Poisson 分布 用 Monte Carlo 法进行仿真 然后通过多目标规划进行求解 并得到最终解 问题 2 在求解过程中时间段的划分对其程序有很大程度的影响 在实际采集数据中应当注意到各个时 间段 关 键 词 模糊聚类 多目标规划 Monte Carlo 仿真 中图分类号 O29 文献标识码 A 1 问题重述 公共交通是城市交通的重要组成部分 作好公交车的调度对于完善城市交通环境 改进市民出行状况 提高公交公司的经济和社会效益 都具有重要意义 下面考虑一条公交线路上公交车的调度问题 其数据来 自我国一座特大城市某条公交线路的客流调查和运营资料 该条公交线路上行方向共 14 站 下行方向共 13 站 该文给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计 公交公司配给该线路同一 型号的大客车 每辆标准载客 100人 据统计客车在该线路上运行的平均速度为 20km h 1 运营调度要求 乘客候车时间一般不要超过 10min 早高峰时一般不要超过 5min 车辆满载率不应超过 120 一般也不要 低于 50 试根据这些资料和要求 为该线路设计一个便于操作的全天 工作日 的公交车调度方案 包括两个起点站 的发车时刻表 一共需要多少辆车 这个方案以怎样的程度照顾到了乘客和公交公司双方的利益等等 如何将 这个调度问题抽象成一个明确 完善的数学模型 指出求解模型的方法 根据实际问题的要求 如果设计更好的 调度方案 应如何采集运营数据 有关每条线路 上行 下行 每站 A0 A13 在每小时 5B00 23B00 内上车与 下车人数的统计数据见表格 详见 www 163 com 教育频道 第 15 卷 第 1期 浙江万里学院学报 Vol 15 No 1 2002 年 3 月 Journal of Zhejiang Wanli University Mar 2002 收稿日期 2001 10 09 作者简介 何永强 1981 男 浙江义乌人 黄剑 1982 男 浙江衢州人 陆新根 1979 男 浙江海宁人 本文曾获 2001 年全国大学生数 学建模竞赛浙江省二等奖 根据数学论文署名的国际惯例 作者排序参照姓名的拼音顺序 2 问题分析 2 1 影响问题分析的主要因素 影响该问题的主要因素有汽车的数量 乘客人数与到站规律 发车间隔及线路上的其它随机因素对车 辆运行的干扰 评价公共汽车运行结果的指标很多 一般说来 好的运行效果主要应做到以下三点 1 总留乘时间要少 以减少乘客等待时间 提高服务质量 其中 总留乘时间 E 第 i 车站留乘人数 留乘时间 2 满载率高 运行车公里数要少 其中 车公里数 车次数 线路长度 3 客人数小于 50人时 总空车时间 E 50 某车某一段乘客数 运行时间 显然 减少乘客等待时间和减少运行车公里数两个要求相互矛盾 如何在这些目标中找一个合理的匹 配关系 是运输管理中的一个重要问题 我们可以利用计算机仿真得到不同车辆配置 不同发车间隔 不同 乘客流量下的总留乘时间 车公里数等 2 2 汽车 车站和乘客 实体是汽车 车站和乘客 此外所指的汽车属性包括在车场排队还是运行 运行至哪一点 运行时间 车 上乘客人数等 而乘客的属性有等车 等车时间 乘车 车站的属性则是该站是否有乘客等车 系统中所涉及 的事件有首站发车事件 到达中途站事件 到达终点站事件 乘客到达事件 上 下车事件 1 首站发车活动 根据发车时刻表从首站发车 这要考虑是否到了发车时刻及车场是否有车可发 还 要考虑首站的上车人数 到达下一站的时间 2 到达中途站活动 这需计算在本站上下车的人数 确定乘车人数及时间 预测汽车下一个的后续活 动的出现时间 累加运行公里数 3 末站调头活动 就是确定汽车的去向 是立即发车还是等待发车 2 3 模糊聚类分析法划分不同时间段 为了便于调度 根据所提供的上下车人次的数据和我国实际的上下班制度 我们对时间段按照模糊聚 类分析法进行进一步划分 分为不同时间段高峰期 低潮期 一般期 3 模型建立 3 1 车辆调度策略及其仿真 该题是一个动态的变化过程 无法就某个时刻单独取出单独考虑 并且在整个车辆运行过程中 随机的 因素较多 难以准确地把握 无法较为简便 准确的求出评价调度方案的指标 如 总的空车时间 总留乘时 间 车公里数 所以我们运用了仿真的思想将其动态的过程进行模拟 以求出各个评价指标 首先 根据表格给出的数据 以及实际生活的情况 也为了简化仿真的复杂度 我们将一个工作日分为 n 个时间段 根据已有的数据确定一个发车间隔的范围 如 在高峰期发车的间隔为 1 5min 而在低潮期发生 间隔为 10 15min 一般时段发车间隔 7 10min 第二步 对第一个时间段进行仿真搜索 先设定这一时段的发车间隔 在仿真过程中 计算出各个仿真 时刻每一辆车的载客数 车辆的位置 以及各个站点的等待的人数 并对所需要的评价指标进行累加 在结 束时 得出该发车间隔所对应的评价指标 及在结束时 运行状态的各个车的具体状态 如 位置 载客量 第三步 对所求得的评价指标进行分析 求得最佳的评价指标组合以及所对应最佳发车间隔 第四步 对下一个时段进行仿真 在开始读入上一个阶段的最佳发车间隔做仿真 结束时的运行车辆的 状态 改变发车间隔继续仿真 同理得出最佳的时间间隔 此处读入上一仿真结束时的运行车辆的状态 并 对其进行的延续 可更好的对相邻的时间的进行衔接 更符合实际 使得出的解更有可信度 如此循环 求得 各个阶段的最佳发车间隔 便可制定出最佳的发车间隔 3 2 模型 3 2 1 模型假设 15 第 1 期何永强 黄 剑 陆新根 公交线路的车辆调度问题 1 单位时间内到达第 i 个车站的人数服从定长 均匀 分布 2 车上每位乘客在以后各站下车人数 服从定长 均匀 分布 3 考虑各站的上下车都是同时进行 每位乘客的上下车时间都相等 4 各辆汽车的最大容量是指车内座席数和有效站面积上的站立人数 5 汽车的运行时间只包括乘客上下车时间和必要的运行时间 不考虑其它时间 6 在同一时间段内按等间隔发车 以方便工人操作 7 假设车上载客人数小于 50 为空车 以 50 此刻车上人数 为缺载人数 总空车时间 E i 号车缺载人数 运行时间 8 假设未搭上车的乘客为留乘乘客 总留乘时间 E 第 i 个车站留乘人数 留乘时间 9 高峰时 t间F5min 非高峰时 t间 6 13min 晨间和夜间 t间E7 15min 3 2 2 参数说明 t间 发车间隔 A 加权系数 3 2 3 模型求解 以下用模糊聚类法将一工作日数单位时间段 归划为更为概括的时段 第一步 确定各时间段的特征指标 Vij 它是时间段 Ti和Tj相应各站的上车人数比 第二步 数据标准化处理 采用极差正规化公式 Uij Vij minVij max Vij minVij 第三步 标定 采用夹角余弦公式 rij E 18 k 1uikuikE 18 k 1u 2 ikE 18 k 1u 2 ik其中rij表示各时间段之间的相似程度 第四步 分类 再由 rij来判别它们的类别 分类结果如下 5B00 6B00 6B00 9B00 9B00 16B00 16B 00 19B00 19B00 22B00 22B00 23B00经计算 机仿真得出 5B00 6B00时间段系列数据 见表 1 从表 1 可以看出 空车时间及车公里数与 总留乘时间是相互矛盾的要求 即总空车时间 和车公里数减少了 总留乘时间必然增加 它们 分别代表了公交公司的利益和乘客的利益 此 时间主要考虑两个方面 总留乘时间和车公里 数 为了计算方便 现使它们的量纲一致 即车 公里数 平均速度 使后者的单位成为时间的单 位 可归为一个双目标规划 表 1 用模糊聚类法得出的 5B00 6B00时间段系列数据 发车间隔 min 总空车时间 min 总留乘时间 min 车次行驶 路程数 km 总车量数 7 8 9 10 11 12 13 14 15 11677 10282 9277 4 8642 2 8140 8 7166 7 6651 7 6327 1 6067 5 0 0 0 0 72 1 247 2 663 6 679 7 1156 3 263 234 204 3 204 3 175 1 175 1 146 146 146 13 12 10 9 8 8 7 7 6 R min f t间 f t间 表示总留乘时间与发车间隔 t间 的函数 H min g t间 g t间 表示车总运行时间与发车间隔 t间 的函数 而在实际调度中 调度者总是权衡总留乘时间和汽车总的 运行时间 选择一个令双方都满意的调度方案 称为有效调度方 案 因此分别对目标函数 R 和H 赋予权重1 A和 A 0 AF1 将上式化为单目标规划模型 min W A R H 1 A 加权系数 A称为调度偏好系数 A值由调度者自己决定 列举 5B00 6B00 时间段内的加权系数 由偏好系数加权法 可得 结果见表 2 表 2 5B00 6B00 时间段经加权调整后的发车间隔 顾客 偏好系数 公交公司 偏好系数 发车间隔 min 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 13 13 13 11 11 11 11 11 9 16浙江万里学院学报2002年 3月 为了顾及双方的利益 取 A为 0 5 所以可得 5B00 6B00 的发车间隔为 11min 以后各个时间段都是用 这种方法进行求解见表 3 并根据发车间隔可以制定出发车时间表 见表 4 表 3 各时间段的发车间隔 时间段 发车间隔 min 6B00 9B00 9B00 16B00 16B00 19B00 19B00 20B00 22B00 23B00 2 11 4 11 15 表 4 各时间段的调度方案 时间段 发车间隔 min 首发时间 本时段 所需车数 5B00 6B00 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 11 2 11 4 11 15 5B05 6B00 9B02 16B00 19B04 22B00 8 69 29 29 11 6 3 2 4 模型 1 的讨论 从模型 1中可考查的是单位时间内到达车站的人数是服从定长分布 在一般的现实生活中到达车站的 人数是服从泊松 Poisson 分布 下面对模型 1 进行改进 称之为模型 2 3 3 模型 2 3 3 1 模型假设 1 单位时间内乘客到达第 i 个车站的人数服从泊松 Poisson 分布 2 车上每位乘客在以后各站下车人数 服从泊松 Poisson 分布 3 其余假设和模型 1 相同 3 3 2 参数说明 zk 总空车时间 slt 总留乘时间 cl 车公里数 A 加权系数 3 3 3 模型求解 用蒙特卡洛 Monte Carlo 法进行仿真 Monte Carlo 法的基本思想是通过某种 试验0的方法 求出某一 随机变量的平均值 并用此作为所求事件出现的概率或所讨论随机变量的期望值 第一步 变均匀分布为泊松分布 求出某一发车间隔 ti时的一组评价指标 zk1 slt1 cl1 第二步 多次求发车间隔为 ti时的评价指标 求出平均 zk E zki i slt E slti i cl E cli i 表 5 用蒙特卡洛法仿真得出的 5B00 6B00 时间段的系列数据 发车间隔 min 总空车时间 min 总留乘时间 min 车次行驶 路程数 km 总车量数 7 8 9 10 11 12 13 14 15 110717 12782 11516 9843 4 9457 7528 6 7362 6434 6131 87 1142 2290 1670 1 1900 4392 11140 16638 20708 263 234 204 3 204 3 175 1 175 1 146 146 146 14 12 11 9 9 8 7 7 7 第三步 求出各个发车间隔的 平均评价指标 经计算机仿真得出 5B00 6B 00 时间段系列数据 见表 5 主要考虑两个方面 总留乘时 间和车公里数 为了计算方便 现 使它们的量纲一致 即车公里数 平均速度 使后者的单位成为时间 的单位 要使得顾客和公交公司双 方都满意 显然这两者之间是存在 矛盾的 可归为一个双目标规划 R min f t间 f t间 表示总留乘时间与发车间隔 x 的函数 H min g t间 g t间 表示车总运行时间与发车间隔 x 的函数 在实际调度中 调度者总是权衡总留乘时间和汽车总的运行时间 选择一个令双方都满意的调度方案 称为有效调度方案 因此分别对目标函数 R 和 H 赋予权重 1 A和 A 0 AF1 将上式化为单目标规划 17 第 1 期何永强 黄 剑 陆新根 公交线路的车辆调度问题 模型 minW A R H 1 A 加权系数 A称为调度偏好系数 A值由调度者自 己决定 列举 5B00 6B00 时间段内的加权系数 用偏好系 数加权法 可得结果见表 6 为了顾及双方的利益 取 A为 0 5 所以可得5B00 6B00的发车间隔为 13min 以后各个时间段都是用 这种方法进行求解见表 7 并根据发车间隔可以制定 出发车时间表 见表 8 表 6 5B00 6B00 时间段经加权调整后的发车间隔 顾客 偏好系数 公交公司 偏好系数 发车间隔 min 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 13 13 13 13 13 13 13 13 13 表 7 各时间段的发车间隔 时间段发车间隔 min 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 3 13 2 7 15 表 8 各时间段的调度方案 时间段 发车间隔 min 首发时间 本时段 所需车数 5B00 6B00 6B00 9B00 9B00 16B00 16B00 19B00 19B00 22B00 22B00 23B00 13 3 13 2 7 15 5B08 6B00 9B04 16B00 19B05 22B00 7 35 21 75 23 6 参考文献 1 叶其孝 大学生数学建模竞赛辅导教材 一 二 三 四 M 1 长沙 湖南教育出版社 19991 2 卢开澄 单目标 多目标与整数规划 M 1 北京 清华大学出版社 19991 3 周义仓 赫孝良 数学建模实验 M 1 西安 西安交通大学出版社 19991 The Problem on Bus Route Dispatching 2001 Mathematical Contest in Modeling Problem B HE Yong qiang1 HUANG Jian2 LU Xin gen 1 Department of Engineering Technology of Zhejiang Wanli University Ningbo 315100 P R China 2 Department of Computer of Zhejiang Wanli University Ningbo 315100 P R China Abstract T he parameters of each interval were obtained by simulating on computer and turned into mult i objec tive planning in order to solve the problem The avaiable data were analyzed T he method of fuzzy assembling type was applied and one