摘要
为适应校车路径规划中校车有多种车型且每种车型数量受限的需求,建立车辆数限制的多车型校车路径问题(HFSBRP)的数学模型,并提出一种迭代局部搜索算法进行求解。该算法借助邻域随机选择的变邻域下降搜索(VND)算法完成局部提升。局部提升过程中,首先调整车型,然后再混合使用缩减路径数和提高车辆利用率的邻域解接受策略以提高算法的寻优能力,为保证解的多样性,允许接受一定偏差范围内的邻域解。此外,为避免算法过早陷入局部最优,设计了多点交换和移动的扰动规则。基于国际基准测试案例进行模型验证和算法测试,实验结果表明了模型的正确性和算法的有效性。
In practice of school bus route planning, the bus fleet usually consists of a limited number of buses with different capacities, purchase costs and operation costs. However, the heterogeneous fixed fleet school bus routing problem （HFSBRP） has not been well investigated. In this paper, we introduced a mathematical model for HFSBRP and also proposed an iterated local search （ILS） algorithm to optimize the total cost. The ILS is combined with a variable neighborhood descent （VND） algorithm with random neighborhood selection. In local search, the bus type for one or more routes will be adjusted to reduce the costs. Two acceptance rules are used to accept the solution while satisfying the rules. In addition, some worst solutions within the scope of cost deviation are accepted to keep the diversification of the search. Moreover, a perturbation mechanism with multiple points swap or shift is used to avoid local optima. The experimental results demonstrate the correctness and effectiveness of the proposed model.
出处
《计算机科学》
CSCD
北大核心
2016年第12期234-240,共7页
Computer Science
基金
国家自然科学基金项目:大规模混载校车路径问题多目标优化算法研究(41401461)
河南省教育厅自然科学重点项目(15A520009)资助
关键词
多车型校车路径问题
车辆数限制
迭代局部搜索
随机邻域选择
Heterogeneous school bus routing problem, Fixed fleet, Iterated local search, Random variable neighborhood search
