【作者】 高文韬；

【导师】 马继辉；

【作者基本信息】 北京交通大学 ， 交通运输（专业学位）， 2024， 硕士

【摘要】 公交线网规划作为城市公共交通运营的基础性环节,其规划合理性直接关乎市民的出行便捷度和公交公司的运营成本效益。鉴于公交线网规划问题(Transit Route Network Design Problem,TRNDP)涉及站点繁多、线路错综复杂的特性,公交公司难以对其进行较为精细的规划。鉴于此,本文充分考虑公交线网规划问题的规划目标和受到的各种约束,构建了公交线网分层规划模型。随后对自适应大邻域搜索(Adaptive Large Neighborhood Search,ALNS)算法进行改进,并将其用于公交线网规划问题的求解。通过对不同规模的案例进行求解和分析,验证了该算法在公交线网规划问题求解方面的高效性与可靠性。本文的主要工作如下:1.针对公交线网规划问题,本文构建了一个线性的整数规划模型。该模型旨在最大化直达客流密度与站点覆盖率,同时最小化线网总长,以实现公交线网的优化布局。在建模过程中,充分考虑了线路长度、站点数量、线路形态及客流需求等多重约束条件。同时创新性地提出通过角度方式对线路形态进行约束,相比传统的非直线系数方法,更能有效地约束线路形态,使规划结果更加贴近实际运营需求,并在案例求解部分对此进行了验证。此外,为了满足现实公交线网分层规划的需求,本文还设计了子层公交线网规划模型,使得模型能够灵活地表示各级公交线网及其间的相互关系。2.鉴于公交线网规划问题的复杂性,本文采用了ALNS算法框架进行求解,并针对该问题的特点对算法进行了一系列改进。首先,通过引入列生成的思想,为算法提供了一个优质的初始解。其次,设计了破坏算子和修复算子各五种,丰富了算法的邻域结构,增强了算法的全局搜索能力。此外,通过自适应地调整线路选取、算子权重以及权重更新规则,优化了算法的自适应机制,进一步提升了算法的寻优性能。同时,对当前解接受条件进行设计,使其获得一定的跳出局部最优的能力。3.为了验证本文所提算法的有效性,本文选取了多个基准数据集和实际案例数据进行广泛的求解实验。这些案例包括不同规模的Mandl路网、Sioux-Fall路网、Mumford路网以及真实的大规模实际路网数据。通过对比分析,本文算法在求解公交线网规划问题方面展现出了显著的优越性。灵敏度分析验证了本文算法在不同参数条件下的稳定性和鲁棒性。在实际大规模路网案例的求解中,本文所得线网与城市出行结构高度契合,各项评价指标均表现优异,可以为实际公交线网规划提供参考。总体而言,本文研究可以为城市公交线网规划提供一定的理论指导和决策方法支撑,助力我国城市公交运营企业提升服务质量、节约运营成本。更多还原

【Abstract】 As the fundamental part of urban public transport operation,the designing of bus network is directly related to the convenience of citizens’ travel and the operational cost of bus companies.Considering the problem of transit route network design(TRNDP),involves a large number of stops and complicated routes,making it difficult for bus companies to make a detailed design.Therefore,this paper fully considers the planning objectives and various constraints of TRNDP,and constructed a hierarchical planning model for the bus network.Subsequently,the Adaptive Large Neighborhood Search(ALNS)algorithm is improved and applied to solve TRNDP.Through solving and analyzing cases of different scales,it is verified that the algorithm is efficient and reliable in solving the TRNDP.The main work of this paper is as follows:For the problem of bus network planning,this paper constructs a linear integer programming model.The model aims to maximize the density of direct passenger flow and stop coverage while minimizing the total length of the network.In the modeling process,multiple constraints such as route length,number of stops,route shape,and passenger flow demand are fully considered.At the same time,it is creatively proposed to constrain the route shape by angle,which can more effectively constrain the route shape compared to traditional non-linear coefficient method.In addition,in order to meet the needs of realistic bus network hierarchical planning,this paper also designs a sub-layer bus network planning model,which enables the model to flexibly represent all levels of bus networks and their interrelationships.In view of the complexity of the TRNDP,this paper adopts the ALNS algorithm framework for solving it.We made a series of improvements to the algorithm based on the characteristics of the problem.Firstly,by introducing the idea of column generation,a high-quality initial solution is provided for the algorithm.Secondly,five kinds of destructive operators and five kinds of repair operators are designed,enriching the neighborhood structure of the algorithm and enhancing its global search ability.In addition,by adaptive route selection,operator weights adjustment,and weight update rules,the adaptive mechanism of the algorithm is constrained,further improving the optimization performance of the algorithm.At the same time,the current solution acceptance condition is designed to enable it to obtain certain ability to escape local optimality.In order to verify the effectiveness of the algorithm proposed in this paper,a wide range of benchmark data sets and real case data were selected for extensive solving experiments.These cases include different sizes of Mandl’s network,Sioux-Fall network,Mumford’s networks,and real large-scale actual road network data.Through comparative analysis,the proposed algorithm exhibits significant advantages in solving TRNDP.Sensitivity analysis verifies the stability and robustness of the algorithm under different parameter conditions.In the solving of large-scale road network cases,the network obtained in this paper highly fits the urban travel demand structure,and all evaluation indicators perform well,which can provide reference for actual bus network planning.Overall,this study can provide theoretical guidance and decision-making methods for urban public transport network planning,and help urban public transport operators improve service quality and save operating costs.更多还原