一种求解大规模校车调度问题的元启发式算法

校车调度问题(SBSP)是通过调度使一辆校车服务完一个学校后继续服务其他学校,以减少一个地区所需的校车总数,进而降低校车采购成本和运营成本。目前的SBSP求解方法是将其转化为指派问题或运输问题,使用混合整型规划算法或者简单启发式算法进行求解,但求解性能有局限。本文在单校校车路径规划的基础上,将单校路径抽象为虚拟站点,进而将SBSP转换为带有时间窗的车辆路径问题(VRPTW),设计元启发算法进行求解。使用构造启发式算法获得初始解后,在模拟退火算法框架中通过典型的局部搜索算子搜索邻域解,逐步改善求解质量。搜索算子包括单点移动、两点交换、2-OPT和Cross-Exchange。迭代优化过程中以校车路径数为主要目标,路径长度为次要目标。为避免邻域搜索陷入局部最优,算法以一定的概率接受部分使路径长度增加的解。15个案例实验验证了本算法的有效性,与现有算法相比,能够获得更好的优化目标,适用于大规模的校车调度。

一种基于学校上学时间调整的校车调度算法

在给定单校校车路径的基础上,校车调度问题是在满足学校上学时间约束下寻找服务所有路径的最优校车安排.而上学时间的设置对调度的效果有直接影响,目前基于学校上学时间调整的校车调度大多以精确求解方法为主,在大规模案例上求解质量相对较低.针对该问题,设计了一个两阶段启发式求解算法.第一阶段以服务所有路径所需校车数量为优化目标,通过应用构造启发式算法选择学校上学时间;第二阶段在模拟退火算法框架下,使用VRP局部搜索算子求解学校上学时间固定的校车调度问题.模拟实验基于已有校车路径问题的测试案例,结果表明相对于精确求解方法,该算法显著降低了校车数量,能够获得较好的校车路径规划方案.