公交网络线路与发车频率协同优化问题的元启发式算法研究

Transit network design is critical for improving the service level and operation efficiency of public transit service, and thus relieving traffic congestion and environment pollution problem. Due to the computational complexity, the route first frequency second sequential optimization method is commonly adopted for transit network design. However, without frequency information, the most important evaluation criteria including traveler waiting time，route choice, transfer times, and network operation cost cannot be evaluated. This posts constraints on the optimization of transit network design. With the advatanges of metaheuristics in solving hard combinatorial problems, this project is to conduct research on effective transit assignment method considering both route and frequency, optimal design of transit network encoding method, efficient neighborhood search operators, and effective solution diversity control scheme, so as to reduce the computational complexity of the problem which leads to the development of efficient and effective metaheuristics for solving the transit network simultaneous optimization problem. The outcome of this project is expected to fill the gap in the existing literature in optimial transit network design, and provide methodological basic for improving the service level and operational efficiency of transit network.

公交网络的优化设计对提高公交服务质量和运营效率、缓解交通拥堵、减少环境污染有重要意义。公交网络优化通常采取先设计线路、后优化发车频率的序贯优化方法。但在公交线路设计时不考虑发车频率将无法评价乘客候车时间、路线选择、换乘次数、以及公交运营成本等重要指标，从理论上制约了公交网络设计的最优化。而显著的计算复杂性是解决线路与频率协同优化问题的难点。本项目结合元启发式算法在解决复杂组合优化问题方面的优势，针对公交网络优化问题的特点，通过研究基于线路与频率的高效公交乘客配流方法、构建公交网络最优编码方法、设计面向线路与频率协同优化的高效邻域搜索算子、建立有效防止算法过早收敛的解多样性控制机制等关键途径，降低公交网络协同优化问题求解复杂性，进而建立高效的公交网络协同优化元启发式算法。相关研究对公交网络最优化设计理论进行补充，为提高公交网络服务水平及运营效率提供基本的方法支持。

本项目对公交网络优化问题进行了研究，提出并建立了线路与发车频率协同优化的相关理论和方法。首先，项目组通过调研对公交乘客的选择行为进行研究，在此基础上建立了基于公交乘客选择行为的公交配流模型，相关配流方法能客观考虑公交线路及发车频率对乘客配流的影响，为实现公交网络线路设计与发车频率协同优化奠定基础。进而，项目组针对不同优化目标及约束条件研究并建立了公交网络优化问题的数学规划模型，相关模型实现对公交网络线路及发车频率的协同优化。通过小规模算例对所建立的模型进行有效性验证，结果表明，对比现有的序贯优化模型，相关模型能获得更好的优化结果。为了有效解决现实规模的优化问题，本项目研究并设计了公交网络线路及频率协同优化问题的元启发式算法。针对公交网络优化问题的特点，设计了相关元启发式算法使用的独特解编码方法、多个高效邻域搜索算子、及解多样性保持机制，提高相关算法的计算效率。我们通过大规模算例开展了算法实验，验证了相关算法的优化效果。最后，项目组通过调研获得若干城市的公交网络数据，最后选取了两个具体的公交网络优化实例对所建立的模型和优化方法开展了应用研究。研究表明，所建立的模型和优化方法能有效地对现有公交网络进行优化，提高公交网络服务水平并降低运营成本。总体上，本项目研究对公交网络最优化设计理论进行了必要的补充，为提高公交网络服务水平及运营效率提供基本的方法支持。