校车路径问题的约束检测算法

Constraints detection method for school bus routing problem

依据校车服务学校的数量和顺序可将校车路径问题(SBRP)分为单校、多校不混载和多校混载三类。现有算法对不同类型的SBRP进行容量、时间窗等约束检测时采用不同的方法,对待复杂应用需要通过遍历进行检测。为此设计一种适用于不同类型SBRP的分段检测算法,将路径上的学校站点视为检测点,按检测点对路径分段,基于各个检测路段上的剩余容量和剩余时间检测整条路径是否违反约束。最后在大规模混载校车路径问题上的实验表明分段检测算法是有效的。

School bus routing problem （SBRP） can be classified into three types： the single-school problem, the multi-school problem not allowing mixed load, and the multi-school problem allowing mixed load. The detection of constraints such as school time window, bus capacity is one of the key steps in SBRP algorithm design. Existing algorithms for SBRP usually de- sign different insertion detection methods for each type of SBRP. This paper introduced a generic segment-based constraints de- tection algorithm for inserting a node to a route. One route was split into several segments according to school stop, which was regard as the check point. Instead of traversing all stops in a route, the feasibility of a proposed route was verified by checking the remaining time and remaining capacity of each segment. The experiment shows the effectiveness and efficiency of segmen- ted detection algorithm in solving large-scale mixed-load SBRP.