摘要
在给定单校校车路径的基础上,校车调度问题是在满足学校上学时间约束下寻找服务所有路径的最优校车安排.而上学时间的设置对调度的效果有直接影响,目前基于学校上学时间调整的校车调度大多以精确求解方法为主,在大规模案例上求解质量相对较低.针对该问题,设计了一个两阶段启发式求解算法.第一阶段以服务所有路径所需校车数量为优化目标,通过应用构造启发式算法选择学校上学时间;第二阶段在模拟退火算法框架下,使用VRP局部搜索算子求解学校上学时间固定的校车调度问题.模拟实验基于已有校车路径问题的测试案例,结果表明相对于精确求解方法,该算法显著降低了校车数量,能够获得较好的校车路径规划方案.
Optimal school bus routing and scheduling for multiple schools in a city or county region can reduce the total number of school buses required,and thus saves the cost of school bus operations. How ever,the benefit of bus scheduling depends largely on the settings of school bell times. M ost of the existing literatures related to the school bus scheduling problem w ith school bell time adjustment are solved by exact approaches. The exact approaches can only solve small size problem,but cannot get high quality solutions for large scale problem. This paper aims to design an optimization algorithm for the school bell time adjustment and school bus scheduling problem. Given the school bus trips and the school bell time settings for each school in a region,w e proposed a tw o-stage heuristic algorithm. In the first stage,the bell times for all schools are adjusted by iteratively changing bell times and evaluating the required number for bus scheduling. In the second stage,a simulated annealing（ SA） algorithm is introduced to improve the solution of bus scheduling obtained in the first stage. The aim is to decrease the number of routes and the total travel distance. Four local search operators for vehicle routing problem（ VRP）,one-point move,tw o-point move,tw o-opt move and cross-exchange move,are embedded in the SA framew ork. The effectiveness of this algorithm is verified on a set of large-scale benchmarks w ith seven scenarios of bell time adjustment. The results show that the number of school buses required can be reduced greatly by adjusting the school bell times.
出处
《小型微型计算机系统》
CSCD
北大核心
2015年第9期2159-2165,共7页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(41401461)资助
河南省教育厅科学技术研究重点项目(14A520041)资助
关键词
校车路径问题
校车调度问题
上学时间调整
优化算法
school bus routing problem
school bus scheduling problem
school bell time adjustment
optimization algorithm
