面向多种应用场景的校车路径问题超启发优化算法研究

In practice of the school bus route planning, a variety of factors such as the number of schools, the types of school buses, the different demands of students, and the planning constraints and objectives should be considered carefully. However, the existing algorithms for school bus routing problem (SBRP) were proposed mainly to solve a specific and simplified routing problem, and thus are difficult to be used in actual school bus route planning. This project aims to develop a hyper-heuristic algorithm for solving the general-purpose SBRP. The research focuses on four topics: the definition of general-purpose SBRP; the design and implementation of a hyper-heuristic algorithm for SBRP; the performance analysis and calibration of the proposed algorithm; and the case studies. The research will be conducted in the following steps: (1) the mathematical definition and model formulation of SBRP according to various planning scenarios and the characteristics of the problem. (2) The design of a metaheuristic framework consisting of the common algorithm components and the low-level heuristic library, the building of the high-level strategies based on learning mechanism, and the implementation of a hyper-heuristic algorithm based on this framework. (3) The comprehensive testing of the low-level heuristics and high-level hyper-heuristic strategies on a set of SBRP benchmark instances, mainly focusing on the suitability and performance of the algorithm selection strategies on different routing problems and different spatiotemporal configurations of the problem instances. (4) The case studies of school bus routes planning by using the proposed hyper-heuristic algorithm in GIS. The research findings will contribute to the general-purpose and high-performance algorithm design for SBRP. The proposed hyper-heuristic algorithm also has application potentials in real world school bus route planning.

校车路径规划实践中，学校数量、校车类型、学生需求、规划目标等因素的差异产生了多种规划场景。现有校车路径问题(SBRP)算法多针对某个特定规划场景，算法可移植性和通用性较差。本项目拟设计一个高效的、面向多种应用场景的SBRP超启发算法，从以下方面展开研究：①分析多种应用场景下的问题特征，完成SBRP的定义和整型规划模型。②基于SBRP的统一表达，设计SBRP元启发算法框架完成基本数据结构、函数库以及与问题特征相关的低层启发算法的开发；构建基于学习机制的高层控制策略，实现基于邻域搜索元启发的超启发算法。③使用基准案例测试超启发算法的性能，分析SBRP问题特征、时空特征、高层启发策略与算法性能间的关系。④在GIS软件内完成算法集成，开发校车路径规划工具，并使用实际案例进行验证。项目的研究成果不仅对指导SBRP算法设计有重要的理论价值，而且在实际校车路径规划中也有较高的应用价值。

本项目针对涉及学校数量、车辆类型、学生需求及优化目标等多种特征的校车路径问题进行研究，主要目标是设计能够适用多种应用场景下校车路径规划的高效可用的超启发算法。根据研究计划，主要从SBRP问题的定义和建模、SBRP超启发算法设计、算法测试与分析以及案例研究等4个方面进行研究。首先，对不同应用场景下的问题特征进行分析，以总成本为优化目标，结合车辆、车型和任务等约束条件建立SBRP的混合整型规划模型。该模型支持多学校、多车型、需求拆分、混载等多种SBRP问题特征。其次，对具有多种问题特征的SBRP统一表达为多校混载多车型需求拆分的SBRP问题，在此基础上设计一个以邻域搜索类启发算法为核心的算法框架。该框架包含基础数据结构、基本函数库、启发策略、初始解构造算法库和与问题特征相关的低层启发算法库；其中低层启发算法库中包含点边操作和点对操作的邻域算子、车型调整算子、拆分算子和破坏重建算子等。基于该算法框架，设计了基于强化学习的高层控制策略，通过低层启发算法评价、选择和解的接受策略等实现SBRP超启发算法。对实现的超启发算法进行测试和分析，使用基准案例进行测试结果表明设计的超启发算法优于现有的SBRP求解算法。最后，将设计的超启发算法与ArcGIS进行集成，研发了校车路径规划工具。以无锡市惠山区几所学校为例进行案例研究，并将研究结果与ArcGIS VRP Tools的规划结果进行比较，实验结果表明了设计的超启发算法的有效性和适用性。