校车路径问题元启发算法设计与GIS集成

发布时间：2018-05-21 01:01

本文选题：校车路径问题 + 开放式车辆路径问题　；参考：《河南大学》2013年硕士论文

【摘要】：为中小学生提供校车服务是我国义务教育发展的必然要求。然而，规划校车路径是校车运行管理中的一个难题。合理的校车路径规划，既能减少所需校车数量，又可缩短校车运行里程，从而节省校车运营服务成本。本文尝试建立校车路径问题（School BusRouting Problem，SBRP）数学模型，设计元启发算法进行路径优化，并将优化算法集成在GIS中，为校车路径规划提供软件工具。因SBRP本质上属于车辆路径问题（VRP）范畴，本文借鉴VRP模型和算法，针对校车停车场不在学校的实际情况，，选择开放VRP模型构建SBRP优化模型。模型中，以校车运行总路径长度最短为目标，以校车容量、学生最长乘车时间等为限制条件。模型优化算法流程如下：建立模型，构造初始解，在模拟退火元启发框架中利用VRP邻域交换算子优化路径，通过C++程序设计实现优化算法。为验证本算法的有效性和计算效率，利用模拟数据进行算法测试，并与ArcGIS网络分析模块中VRP工具优化结果进行比较。最后，在GIS中设计校车路径规划工具。在ArcGIS10中管理学校、停车场、学生乘车站点、交通网络等地理数据，基于Geoprocessing框架设计规划工具。利用Python程序设计实现工具参数设置、模型参数计算、模型建模、优化模块调用、优化结果可视化等功能。并用一所初级中学作为测试实例进行校车路径规划。实验结果表明：使用模拟退火元启发算法解决校车问题是可行的。从多个初始解进行优化的模拟退火算法与ArcGIS中添加禁忌算法的VRP求解算法相比，解的质量有所提高。本文算法数据结构设计简单，占用内存少，在针对校车路径规划方面表现出明显的优势；且将通过ArcGIS网络分析功能算出的OD距离矩阵作为算法输入项，提高了对实际问题的处理能力。通过工具箱输入相关参数之后，能够快速的找到近似最优的校车安排方案，并且进行了可视化的输出，使规划者对规划方案有直观认知。
[Abstract]:Providing school bus service for primary and middle school students is an inevitable requirement for the development of compulsory education in China. However, planning the path of school bus is a difficult problem in the operation and management of school buses. The reasonable path planning of school buses can not only reduce the number of school buses, but also shorten the running mileage of the school bus, thus saving the service cost of the school car. This paper tries to establish the school bus path. School BusRouting Problem (SBRP) mathematical model, design meta heuristic algorithm for path optimization, and integrate the optimization algorithm in GIS, to provide software tools for school bus path planning.
Because SBRP is essentially a vehicle routing problem (VRP) category, this paper uses the VRP model and algorithm, and selects the open VRP model to construct SBRP optimization model in view of the school bus parking lot without the actual situation of the school. In the model, the model takes the shortest path length of the school bus as the target, the school bus capacity, the longest train time, and so on as the limiting condition. The optimization algorithm flow is as follows: establish the model, construct the initial solution, optimize the path by using the VRP neighborhood switching operator in the simulated annealing element heuristic framework, and implement the optimization algorithm through the C++ program. In order to verify the effectiveness and calculation efficiency of the algorithm, the simulation data is used to test the algorithm, and the VRP tool in the ArcGIS network analysis module is superior to the tool. Finally, the school bus path planning tool is designed in GIS. In the ArcGIS10 management school, parking lot, student station, traffic network and other geographical data, based on the Geoprocessing framework design and planning tools. Using the Python program design to implement tool parameters setting, model parameters calculation, model modeling, optimization module calls, The function of visualization is optimized, and a junior middle school is used as an example to carry out the school bus path planning.
The experimental results show that it is feasible to solve the school bus problem using the simulated annealing element heuristic algorithm. Compared with the VRP algorithm of adding tabu algorithms in ArcGIS, the quality of the solution is improved. The design of the algorithm is simple and the memory is less, and it is aimed at the path planner of the school bus. The surface shows obvious advantages, and the OD distance matrix calculated by the ArcGIS network is used as the input item of the algorithm, and the processing ability of the actual problem is improved. After input of the relevant parameters in the toolbox, the approximate optimal school bus arrangement can be found quickly, and the visual output is carried out to make the planners to the rules. The plan has a visual cognition.
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：P208;TP301.6

【共引文献】