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

• 作者: 党兰学 孔云峰 陈小潘
• 来源期刊: 地球信息科学学报
• 关键词: 校车调度问题 校车路径问题 带时间窗的车辆路径问题 模拟退火算法
• 年，卷（期）: 2013,（6）
• 所属期刊栏目: 地理模型与算法
• 页码范围: 879-886
• 页数: 8页
• 字数: 6125字
• 语种: 中文
• DOI: 10.3724/SP.J.1047.2013.00879

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈小潘	河南大学黄河中下游数字地理技术教育部重点实验室	19	87	5.0	8.0
5	党兰学	河南大学黄河中下游数字地理技术教育部重点实验室	25	168	7.0	12.0
6	孔云峰	河南大学黄河中下游数字地理技术教育部重点实验室	82	984	17.0	28.0