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

武汉理工大学校车调度优化模型; 目 录;1.摘要;2.问题提出; 如何优化校车调度？;1.2.现有的路线;3.模型假设;4.模型的建立及其求解;4.模型的建立及其求解; 将南湖分为两个区域（住宿生活区、教学区），并在两个区中选择各选一个校车停靠站点； 现分别在两个区中各拟定三个候选停靠站点，然后通过进一步计算确定南湖校区最终的两个停靠站点； 初选站点见以下地图（南湖中红色三角标记）； 相关数据分别见表一、表二； ;初选站点;教学区、生活区各初选站点间的距离（单位：m）; 各时刻各点需要到东院的人数 （单位：人）;构造目标函数 Min Z1= ;约束条件：;输出结果：;对于校车线路优化, 应从车辆数最少 ，车辆行驶的总距离最短 ，各辆车的运行距离均衡及各辆车的负荷均衡这 4 个 目标进行最优化。;目标函数??;综合以上四个因素，目标函数可建立为： F=min 其中ak为权重系数 ak=0,k=1,2,3,4 ;约束条件：;4.校车经过站点的限制 j=1...m,k=1,...L 任意站点一辆校 车最多通一次 任意站点至少一辆校车通过 5.每辆校车的终点必须是学校，终点站学校可以看作是虚拟的第m+1个站点 6.非负约束，0-1约束已经整数约束 ;算法设计(启发式算法)：;4) 对每条初始线路进行站点补充 : 在剩余的站点中, 把离 自己最近 (即点到直线距离最 最小) 的站点并入该路线中, 若此时新的线路长度依然小于最长初始线路的长度 S , 则继续重复补充站点 ; 否则停止补充转 (5); 5) 若所有站点已考虑, 则转 (6). 否则从初始线路出发, 首先将离最长初始线路最近的点加入到该线路中, 计算其长度记为 S, 令 S = S, 转 (4); 6) 在站点补充完毕后, 计算每条线路上乘客的人数, 安排校车, 若校车的载客量满足均 衡要求, 则停止, 否则对相邻线路上距离最近的站点上的乘客进行互补交换, 直到满足要求. 最后通过 比较不同的校车的总数 L 下的有效解 (与权重系数 占ak,k=1,2,3,4 有关), 找出一组满足特定要求的解;结束语;