武汉理工大学校车调度问题

1、标题：校车调度问题,作者：工业gc1102班,目录,1.1问题概述,随着高校招生比例的逐年增加，全国各大高校都面临着扩建、发展的问题。武汉理工大学在合并后，各校区比较分散，教师以及学生如何在各校区便捷的通行，是一个值得去探究的问题。就教职工而言，由于他们基本都居住在老校区，因此往返于新老校区之间，便成为教职员工一大棘手的问题。对于学生来说，也有令他们头疼的地方。对于武汉理工大学而言，由于行车路线、距离以及课程安排的变化，学生们一般选择坐校车来往返各校区，而由于存在许多动态因素，出现了有老师或学生上下课赶不上校车的现象。因此，等候校车成为了很多师生经常面临的问题。由此可见，本为师生提供方便的校车

2、，不时成为困扰师生正常工作学习的问题。总的来说，候车时间与上、下课时间的协调是针对老师首要解决的问题。根据实际情况，我们了解到，现在校车周一到周五是根据上课、下课时刻表来决定发车时间的。基于以上校车调度方面存在的问题，本文试图建立模型，设计校车调度的优化方案，从而实现对校车调度方面问题的解决及优化。,1.2校车调度优化问题解析 校车调度工作除了要考虑学校后勤集团的收益 ，还要考虑乘客利益 ，并且乘客利益优先于企业利益。本模型从校车乘客和后勤集团双方利益最大化 出发 ，根据 校车 在 实 际运 营 时 乘 客 流 量在时间上 的不 均衡 规 律 ，以极小 化 后勤集团和 出行者费用总和为目标进行

3、建模和优化。,如何优化校车调度？,2.1数学模型 的假设 数学建模要对现实世界的特定对象作一些重要 的简化和 假设 ，把 实 际 问题 抽象 为一 个 数 学 问题 本 文做 如下 假 设 ： 各校车为 同种车 型 ； 同一时段相邻 的两车发车时间间隔相等； 校车的运能能满足运量要求 ； 校车有两个车门，可同时上下车； 各 时段 内，各站客流到达分布服从均匀分布； 站间区间内车辆运行 速度为恒定值，且途中无特殊事件发生 ； 出行者消耗的单位时间费用是固定值u2 ； 校车单位 乘次营运成本是固定值u1。,2.2相关数据,3.1建立模型,以后勤集团和 出行 者 费用 最 小 为 目标 ，以发车间隔

4、为待求变量 ，建立模型 1) 营运成本 C1 车辆营运成本可以表示为线路总乘次与单位乘次营运成本积的形式： 式 中：C1为车辆营运成本 ，元h ；将一天划分为 K 个时段 ，个；Tk为第 k 时段校车营运时间，h ；Hk为第 k 时段的发车间隔，h ；u1为车辆的单车营运成本 ，元h/乘次。 2) 出行者费用 C 2 出行者费用 C2由乘客候车消耗的时间费用 Ca与不下车乘客 由于站点停车所消耗的时间费用 Cb 组成 ，可以表示为： C2=Ca+ Cb (2 ) 乘客候车消耗的时间费用 Ca,以此将校车的运营时间划分为10个时间段，即K=10，并对人流量的大小进行定性分类。问题在于无论以平峰或

5、高峰的人流量来确定运行车辆的数量和发车时间间隔都是不合理的，故应进行优化。 2.3行车路线,东院 西院 鉴湖 南湖,总站点数J=4。,式中：u2为乘客的单位时间价值 ，元h人次 ；Ukj 为 k 时段 、第j 站 的乘 客到 站密度 ，假设 服从 均 匀分布 ;J为公交站点数。 不下车乘客由于公交站点停车所消耗 的时间费用Cb。,式中Dkj为k 时段J 站点的不下车乘客数 ，人次h。,式 中 ：Bkj 为 k 时段 J 站点 的上 车乘客 数 ，人 次h；Akj为k 时段 站点的下车乘客数 ，人次h。,3.2优化模 型,后勤集团的营运成本 C1 与出行者费用 C2 二者处于对立的关系，因此本文

6、属于典型的多目标优化问题依据本文特点，选取权重和方法作为多 目标函数优化算法，得到 目标 函数 ，待求变量为发车间隔 H。以 f作为校车调度的 目标 ，兼顾 了乘客和后勤集团的成本 ，有利于实现乘客与后勤集团的共同利益，对 于调度优化来说是一个适当的目标。,约束条件：,（1）,（2）,（3）,式中:p,q为权重系数 ，取正数 ；Hmax为最大发 车间隔 ，h ；Hmin为最小发车间隔 ，h ；Qd 为公 交车辆额定载客量 ，人；Nk为k时段 是所需车辆数。Nmax为所能提供的最大的车辆数。当满座率达到80%时准许发车。,4.利用遗传算法解决校车调度问题,4.1编码 （1）本文建立分 时段等 间

7、隔 的模 型 ，即把 一天 划分 为 K 个 时段 ，每个时段的发车间隔相 等考虑通过 染色体表示各个时段的发车间隔，进而得到发车时刻表。：假设 最 大发 车间 隔为 15 min ，最 小 发 车间隔为 1 min ，则可供选择的区间为14min=840s,将此 区间分成 100 等份，所以表示每个时段发 车 间 隔 的 基 因 二 进 制 串 长 度 至 少 需 要 7位。我们把一天划分为 K=10个时段 ，那么染色体的长度为 l=70位。 （2）编码精度： = 4.2适应度函数计算 适应度 函数是用来度量群体中各个体的适应能力的。在群体中，适应度大的个体遗传到下一代的概率较大，否则较小。

8、,本 文引入 P aul L Stoffa 提 出的适值模 拟退 火拉 伸 方 法 ，通 过 设 置 可 变 的适 应 度 函数来 解决 这一 问题 。,式中： Fi为第 i 个染色体 的适配值 ；f 为第 i 个染色体 的 目标 值 ；C 为 一 个 较 大 的 正值 ，如 果C-f 0 ，取 Fi=0；g 为遗传迭代数序号；Tc，T 分别 为初始 温度 和 当代 温度 ；k 为 降温 速率 ，取值 为 099。,4.3选择运算 采用轮盘赌注的方法，将当前群体中适应度较高的个体按某种规则或模型遗传到下一代。本文中后代产生的概率为 其中，个体适应度为 ，个体适应度总和 4.4交叉运算 （1）随机配对 （2）随机设置交叉点 （3）交叉部分基因,4.4变异运算 遗传算法实现变异是赋予每个基因一个相对较小的变异概率 P ，通过 随机模拟决定该基因是否变异。 4.5解码，输出结果 使用以下公式解码：,得出结果。,结束语,本文针对极