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

标题：校车调度问题作者：工业gc1102班目录提出问题模型假设模型建立模型求解1.1问题概述•随着高校招生比例的逐年增加，全国各大高校都面临着扩建、发展的问题。武汉理工大学在合并后，各校区比较分散，教师以及学生如何在各校区便捷的通行，是一个值得去探究的问题。就教职工而言，由于他们基本都居住在老校区，因此往返于新老校区之间，便成为教职员工一大棘手的问题。对于学生来说，也有令他们头疼的地方。对于武汉理工大学而言，由于行车路线、距离以及课程安排的变化，学生们一般选择坐校车来往返各校区，而由于存在许多动态因素，出现了有老师或学生上下课赶不上校车的现象。因此，等候校车成为了很多师生经常面临的问题。由此可见，本为师生提供方便的校车，不时成为困扰师生正常工作学习的问题。总的来说，候车时间与上、下课时间的协调是针对老师首要解决的问题。根据实际情况，我们了解到，现在校车周一到周五是根据上课、下课时刻表来决定发车时间的。基于以上校车调度方面存在的问题，本文试图建立模型，设计校车调度的优化方案，从而实现对校车调度方面问题的解决及优化。1.2校车调度优化问题解析校车调度工作除了要考虑学校后勤集团的收益，还要考虑乘客利益，并且乘客利益优先于企业利益。本模型从校车乘客和后勤集团双方利益最大化出发，根据校车在实际运营时乘客流量在时间上的不均衡规律，以极小化后勤集团和出行者费用总和为目标进行建模和优化。如何优化校车调度？最小的等待时间乘客的利益最优的校车数目最优的发车间隔校方的利益2.1数学模型的假设数学建模要对现实世界的特定对象作一些重要的简化和假设，把实际问题抽象为一个数学问题．本文做如下假设：•①各校车为同种车型；•②同一时段相邻的两车发车时间间隔相等；•③校车的运能能满足运量要求；•④校车有两个车门，可同时上下车；•⑤各时段内，各站客流到达分布服从均匀分布；•⑥站间区间内车辆运行速度为恒定值，且途中无特殊事件发生；•⑦出行者消耗的单位时间费用是固定值u2；•⑧校车单位乘次营运成本是固定值u1。序号时间段人流量1上午：7:30--8:00高峰2上午：8:00--9:45平峰3上午：9:45--10:10高峰4上午：10:10--11:45平峰5上午：11:45--12:15高峰6下午：1:30--2:00高峰7下午：2:00--3:45平峰8下午：3:45--4:10高峰9下午：4:10--5:45平峰10下午：5:45--6:15高峰2.2相关数据未来城新一新三新二食堂图书馆教四食堂体育馆体育场华师工程实训中心机电大楼珞狮路珞狮路珞狮路雄楚大道雄楚大道雄楚大道长江出版城新四南湖新图书馆博学广场学生公寓学生公寓学生公寓学生公寓学生公寓超市绿化梅岭后街张黄新村绿化绿化绿化南门学生公寓学生公寓绿化绿化田径场羽毛球、篮球场体育馆绿化绿化篮球场书城路书城路绿化鉴主鉴三食堂食堂学生公寓足球场篮球网球场学生公寓绿化洪兴巷洪达巷足球场篮球场食堂材料学院光纤大楼理工广场大门大门大门大门大门大门大门大门鉴四食堂绿化学生公寓图书馆篮球场篮球场南湖——东院校车停靠站点南湖——东院校车路线3.1建立模型以后勤集团和出行者费用最小为目标，以发车间隔为待求变量，建立模型．1)营运成本C1．车辆营运成本可以表示为线路总乘次与单位乘次营运成本积的形式：式中：C1为车辆营运成本，元／h；将一天划分为K个时段，个；Tk为第k时段校车营运时间，h；Hk为第k时段的发车间隔，h；u1为车辆的单车营运成本，元／h/乘次。2)出行者费用C2．出行者费用C2由乘客候车消耗的时间费用Ca与不下车乘客由于站点停车所消耗的时间费用Cb组成，可以表示为：C2=Ca+Cb．(2)①乘客候车消耗的时间费用Ca．111(/)KkCuTkHk以此将校车的运营时间划分为10个时间段，即K=10，并对人流量的大小进行定性分类。问题在于无论以平峰或高峰的人流量来确定运行车辆的数量和发车时间间隔都是不合理的，故应进行优化。2.3行车路线东院西院鉴湖南湖总站点数J=4。112()KJkjCauUkjHk式中：u2为乘客的单位时间价值，元／h／人次；Ukj为k时段、第j站的乘客到站密度，假设服从均匀分布;J为公交站点数。②不下车乘客由于公交站点停车所消耗的时间费用Cb。112KJkjCbuDkj式中Dkj为k时段J站点的不下车乘客数，人次／h。1()JjDkjBkjAkj式中：Bkj为k时段J站点的上车乘客数，人次／h；Akj为k时段站点的下车乘客数，人次／h。3.2优化模型•后勤集团的营运成本C1与出行者费用C2二者处于对立的关系，因此本文属于典型的多目标优化问题．依据本文特点，选取权重和方法作为多目标函数优化算法，得到目标函数，待求变量为发车间隔H。以f作为校车调度的目标，兼顾了乘客和后勤集团的成本，有利于实现乘客与后勤集团的共同利益，对于调度优化来说是一个适当的目标。min12fpCqC约束条件：minmaxHHH（1）111()/((/))80%KJKkjkDkjQdJTkHk（2）maxNkN（3）式中:p,q为权重系数，取正数；Hmax为最大发车间隔，h；Hmin为最小发车间隔，h；Qd为公交车辆额定载客量，人；Nk为k时段是所需车辆数。Nmax为所能提供的最大的车辆数。当满座率达到80%时准许发车。4.利用遗传算法解决校车调度问题•4.1编码（1）本文建立分时段等间隔的模型，即把一天划分为K个时段，每个时段的发车间隔相等．考虑通过染色体表示各个时段的发车间隔，进而得到发车时刻表。：假设最大发车间隔为15min，最小发车间隔为1min，则可供选择的区间为14min=840s,将此区间分成100等份，所以表示每个时段发车间隔的基因二进制串长度至少需要7位。我们把一天划分为K=10个时段，那么染色体的长度为l=70位。（2）编码精度：σ=4.2适应度函数计算适应度函数是用来度量群体中各个体的适应能力的。在群体中，适应度大的个体遗传到下一代的概率较大，否则较小。maxmin21lHH本文引入PaulL．Stoffa提出的适值模拟退火拉伸方法，通过设置可变的适应度函数来解决这一问题。()/CfTFie1*gTTck式中：Fi为第i个染色体的适配值；f为第i个染色体的目标值；C为一个较大的正值，如果C-f0，取Fi=0；g为遗传迭代数序号；Tc，T分别为初始温度和当代温度；k为降温速率，取值为0．99。4.3选择运算采用轮盘赌注的方法，将当前群体中适应度较高的个体按某种规则或模型遗传到下一代。本文中后代产生的概率为其中，个体适应度为，个体适应度总和4.4交叉运算（1）随机配对（2）随机设置交叉点（3）交叉部分基因/PiFiFiFiFi•4.4变异运算•遗传算法实现变异是赋予每个基因一个相对较小的变异概率P，通过随机模拟决定该基因是否变异。•4.5解码，输出结果•使用以下公式解码：1701maxminmin(*2)*21niiHHXHbi得出结果。结束语本文针对极小化后勤集团和出行者费用总和为目标进行建模和优化。在考虑了不同目标要求下,将多目标规划转化为单目标规划的数学模型。在实际中,高校每天实际乘车的师生是随时间的不同而变化的，优化模型是一个永无止境的问题。鉴于作者水平，本文难免有所疏漏，望加以指正。谢谢大家