求解多车型校车路径问题的带参数选择机制的GRASP算法

考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。

GRASP Algorithm with Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem

This paper dealt with the heterogeneous fleet school bus routing problem,in which students are served by a heterogeneous fleet of buses with various capacities,fixed and variable costs.A GRASP (greedy randomized adaptive search procedure) algorithm with probability selection mechanism was proposed to solve the problem.In the initial solution construction phase,a set of threshold parameters with selection possibility is designed to control the size of restric-ted candidate list (RCL).The threshold parameter is selected by roulette-wheel selection method.The initial solution is then improved by variable neighborhood search (VNS).The selection probabilities for threshold parameters are equally set at first and periodically updated when certain iterations are finished.Each threshold parameter is evaluated by its historical performance records and its selection probability value is adjusted according to its performance.This parameter selection mechanism aims to find better average solution gradually.Our experiments are executed on a set of benchmark instances with different bus types.The results confirm that the proposed GRASP algorithm is more effective compared with classical GRASP algorithm.In addition,the proposed algorithm gives better results than existing algorithms for heterogeneous fleet school bus routing problem.