大规模混载校车路径问题多目标优化算法研究

School bus route planning is a key step to improve the school bus service efficiently and effectively. The mixed load school bus routing problem (SBRP), seeking to plan an efficient route schedule for multiple schools, is a challenging combinatorial optimization problem in operations research. This project aims to design a multi-objective optimization algorithm for solving large-scale mixed load SBRP. The major research topics are: (1) the mathematical formulation and GIS modeling of mixed load SBRP; (2) the design of a general algorithm framework for solving mixed load SBRP, including various data structure, common functions, neighborhood operators, basic heuristic and meta-heuristic algorithms; (3) the meta-heuristic algorithm testing, analysis and tuning, focusing on the algorithm performance, neighborhood search strategy and parameter estimation; (4) the development of school bus routing tools in GIS. Based on a feasible SBRP solution constructed by using heuristic algorithm, the multi-stage neighborhood searches controlled by meta-heuristic mechanisms are used to improve the solution literately. Different from the existing algorithms, the proposed algorithm introduces the pickup-and-deliver neighborhood operators in SBRP for the first time, and also uses the spatiotemporal neighborhood for reducing the computation complexity. The algorithm performances, such as usability, solution quality and computation efficiency, will be tested using benchmark instances and case studies. The research findings will contribute to new algorithm design for solving large-scale multi-school SBRP problems, and the research results will also benefit the local government’s planning and management of school bus services.

校车路径规划实践中，多校混载的运营模式能显著地提高校车的利用率，降低运营成本。本研究针对混载校车路径规划这一难题，探索大规模校车路径问题(SBRP)多目标优化算法。主要内容：SBRP数学模型表达与GIS建模；设计SBRP优化算法框架，包括数据结构、基础函数、邻域算子、求解算法等，基于算法框架实现大规模混载SBRP的元启发算法；基于算法原理、计算复杂度分析和案例测试，探索算法中的各种执行策略和参数设置规律；将SBRP算法与GIS环境集成，研发校车路径规划工具。研究思路：在元启发算法框架下引入PDPTW邻域算子，通过局部邻域搜索分阶段进行多目标优化；引入时空邻域搜索，提高算法的求解速度；采用SBRP测试案例库和实际案例验证算法的有效性和运行效率。研究目标是提升大规模混载SBRP求解算法的优化质量和计算效率。这一研究将为大规模校车路径规划奠定算法基础，为提升校车运营效率提供保障。

本项目针对大规模多校混载运营模式下校车路径规划问题进行研究，主要目标是设计高效可用的混载校车路径规划算法。根据计划，主要从4个方面进行研究：SBRP数学模型表达与GIS建模；设计SBRP优化算法框架，基于算法框架实现大规模混载SBRP的元启发算法；基于算法原理、计算复杂度分析和案例测试，探索算法中的各种执行策略和参数设置规律；将SBRP算法与GIS环境集成，研发校车路径规划工具。首先，在分析混载SBRP路径特征的基础上，给出了混载SBRP的数学模型，支持多目标、多车型、多场站。设计了一个支持轨迹法元启发算法的校车路径问题求解框架，从最底层的数据结构、基础类库、基本的邻域算子、元启发算法、策略设计等，并基于框架提出了基于PDPTW的混载校车路径优化方案，实现了具体的算法。通过算法分析及测试，考虑学校与学生乘车站点的时间和空间约束，设计了基于时空距离的邻域搜索策略来降低算法的求解时间。基于国际基准案例的测试结果表明，新提出的求解算法比国际上现有算法车辆数缩减提高9%左右。将研究提出的求解算法与ArcGIS集成，设计并实现了校车路径规划工具。基于巩义的案例数据集，对算法进行了测试分析，表明提出的求解算法能够规划出更优的运营路线。