校车调度问题建模与仿真 武汉理工大学

武汉理工大学校车调度优化模型——制作者：工业gc1102班——主讲人：钱文家韦铈双目录

3.模型的假设

4.模型的建立及其求解

5.结束语

6.结束语

2.问题的提出的背景1.摘要1.摘要

以武汉理工大学南湖教学区师生校车站点及发车时间安排为对象,首先针对乘车站点建立了目标非线性

规划模型。其中目标函数为所有乘客到达站点的总的距离最小;站点确定后针对车辆数最少，车辆行驶的总距离最短，各辆车的运行距离均衡及各辆车的负荷均衡这4个目标建立针对线路优化的多目标非线性规划模型,并给出了解决这类问题的启发式优化算法。该模型与一般算法更实际,更具体的给出了问题的解答。关键词:校车问题;最优化;非线性规划;启发式算法2.问题提出1.1.现状随着高校招生比例的逐年增加，全国各大高校都面临着扩建、发展的问题。武汉理工大学在合并后，各校区比较分散，教师以及学生如何在各校区便捷的通行，是一个值得去探究的问题。就教职工而言，由于他们基本都居住在老校区，因此往返于新老校区之间，便成为教职员工一大棘手的问题。对于学生来说，也有令他们头疼的地方。对于武汉理工大学而言，由于行车路线、距离以及课程安排的变化，学生们一般选择坐校车来往返各校区，而由于存在许多动态因素，出现了有老师或学生上下课赶不上校车的现象。因此，等候校车成为了很多老师经常面临的问题。由此可见，本为师生提供方便的校车，不时成为困扰师生正常工作学习的问题。总的来说，候车时间与上、下课时间的协调是针对老师首要解决的问题。根据实际情况，我们了解到，现在校车周一到周五是根据上课、下课时刻表来决定发车时间的。基于以上校车调度方面存在的问题，本文试图建立模型，设计校车调度的优化方案，从而实现对校车调度方面问题的解决及优化。如何优化校车调度？乘客离站点的距离最短乘客满意度最优的校车数目最优的行车路线校车的利益1.2.现有的路线3.模型假设假设一：校车在行驶过程中，不存在堵车现象,且途中无特殊事件发生，且校车从南湖校区到达东院所需要的时间为15min；假设二：每辆校车只能容纳C=45人，不存在严重超载行为；假设三：将南湖教学区的可以作为校车停靠点的地方等效成教学区分为：新一教学,新二教学楼，新三教学楼，食宿生活区分为：食堂，南舍区和北舍区；假设四：南湖教学区要求建立两个校车停靠点，分别在教学区和食宿区各一个;假设五：南湖教学区的师生从所在地到达最近的校车站点所用的时间最多为4min.4.模型的建立及其求解一.符号说明新一教学楼，新二教学楼，新三教学楼，食堂，南舍，北舍代号分别为：S1,S2,S3,S4,S5,S6;时间7:30,9:40,11:50,13:30,15:40,17:40代号分别为：T1,T2,T3,T4,T5,T6;另外Smn：表示Sm到Sn的距离；Nij：表示在校车停靠地点Si，时间点Tj时乘车去东院的学生人数。4.模型的建立及其求解4.1停靠站点的选取符号说明S1

,S2,S3,S4,S5,S6：分别表示新一，新二，新三，食堂，南舍区，北舍区；T1,

T2,T3,T4,T5,T6分别表示时刻：7:30,9:40,11:50,13:30,15:40,17:40；Smn：表示Sm到Sn的距离；Nij：表示在校车停靠地点Si，时间点为Tj时，乘车去东院的学生人数。将南湖分为两个区域（住宿生活区、教学区），并在两个区中选择各选一个校车停靠站点；现分别在两个区中各拟定三个候选停靠站点，然后通过进一步计算确定南湖校区最终的两个停靠站点；初选站点见以下地图（南湖中红色三角标记）；相关数据分别见表一、表二；初选站点教学区、生活区各初选站点间的距离（单位：m）S1S2S3S16050S260110S350110S4S5S6S410080S5100180S680180表一教学区各初选站点间的距离表二生活区各初选站点间的距离各时刻各点需要到东院的人数（单位：人）新一新二新三食堂南舍北舍7:30——————1520309:40603010——101011:50804010——————13:30————————808015：40402010——101017:4020101052010构造目标函数MinZ1=MinZ2=约束条件：1.校车容量限制：k=1,2,...,L每辆车的乘客数不超过其载客量2.可行性限制：LC>=n所有校车的载客能力大于等于总的载客数3.乘客限制：i=1,...n每位乘客只能做一辆车输出结果：站点一新一站点二北舍7:34——两辆校车9:44三辆校车一辆校车11:54三辆校车——13:34——四辆校车15:44两辆校车一辆校车17:44一辆校车一辆校车

对于校车线路优化,应从车辆数最少，车辆行驶的总距离最短，各辆车的运行距离均衡及各辆车的负荷均衡这4个目标进行最优化。4.2校车线路确定的数学模型目标函数：l.车辆数最少M1=min{L|L*C>=n};其中:L表示校车的总数,C表示校车的容量(假设均是标准大客车),n表示乘客的总数.2.车辆行驶的总距离最短M2=min若校车直接从Si站到Sj站否则3.各辆车的运行距离均衡(不同乘客相对公平）M3=min(max-min)4.各辆车的负荷均衡(不同乘客相对公平)M4=min(max)综合以上四个因素，目标函数可建立为：F=min其中ak为权重系数ak>=0,k=1,2,3,4约束条件：1.校车容量限制：k=1,2,...,L每辆车的乘客数不超过其载客量2.可行性限制：LC>=n所有校车的载客能力大于等于总的载客数3.乘客限制：i=1,...n每位乘客只能做一辆车4.校车经过站点的限制

j=1...m,k=1,...L任意站点一辆校车最多通一次任意站点至少一辆校车通过5.每辆校车的终点必须是学校，终点站学校可以看作是虚拟的第m+1个站点6.非负约束，0-1约束已经整数约束算法设计(启发式算法)：l)输入:校车的容量C,权重系数ak,k=1,2,3,4(根据实际偏重可人为调整);2)循环输入校车的总数L,取L=[n/C],[n/C]+1,[n/C]+2,...,因为校车总数L与M1以及整个目标函数有关,如果看做一变量的话会使问题求解变得非常困难,而L最多可取有限多个(n个),而实际上我们的第一优化目标就是车辆数最少,所以可行的L会更少;3)在给定校车数L下,首先确定出距离学校最远的L个站点,利用这些站点与学校分别作直线,确定出L条线段,定义为L条初始线路,记最长线路的长度为S;4)对每条初始线路进行站点补充:在剩余的站点中,把离自己最近(即点到直线距离最最小)的站点并入该路线中,若此时新的线路长度依然小于最长初始线路的长度S,则继续重复补充站点;否则停止补充转(5);5)若所有站点已考虑,则转(6).否则从初始线路出发,首先将离最长初始线路最近的点加入到该线路中,计算其长度记为S',令S=S',转(4);6)在站点补充完毕后,计算每条线路上乘客的人数,安排校车,若校车的载客量满足均衡要求,则停止,否则对相邻线路上距离最近的站点上的乘客进行互补交换,直到满足要求.最后通过比较不同的校车的总数L下的有效解(与权重系数占ak,