摘要
为形成科学、合理的公路网布局方案,为公路网布局实践提供理论支撑,以节点重要度为基础,在一定的约束条件下,以满足节点间的运输需求为目的,以路网总旅行时间最小为目标构建混合整数规划模型。在此基础上,以路段重要度和运输需求为启发式条件,设计基于随机游走算法和模拟退火算法的两阶段启发式算法,对MATLAB生成的随机算例进行求解。计算结果表明,在算法迭代初期,节点重要度较大的节点优先被连通,伴随迭代次数的增加和一定的随机扰动,节点在实现全部连通的基础上以路网总旅行时间最小为目标进行优化,最终获得目标函数值最优的公路网布局方案。算例求解过程符合公路网规划实践规律,表明了该模型和算法的有效性,同时表明模拟退火算法对随机游走算法求得的初始解具有一定的优化效果。可以看出,两阶段启发式算法能在较短时间内求解NP-hard问题并获得相对满意的解,可为求解大规模网络优化问题提供一定的方法借鉴。
In order to form a scientific and reasonable highway network layout and provide theoretical support for the practice of highway network planning,based on the importance degree of the nodes and certain constraints,a mixed integer programming model was constructed to meet the transportation demand between nodes.The goal of the planning model was to minimize the total travel time of the highway network.On this basis,a two-stage heuristic algorithm based on random walk algorithm and simulated annealing algorithm was designed.The random examples generated by MATLAB were solved,taking the importance degree of road section and transportation demand as heuristic conditions.The results showed that at the beginning of the algorithm iteration,the nodes with higher node importance were connected first.With the increasing number of iterations and certain random interference,the nodes were achieved full connectivity and continuously optimized with the objective of minimizing the total travel time.Finally,the high-way network layout scheme with the optimal objective function value was obtained.The solution process of the example conforms to the practice law of highway network planning,which shows the effectiveness of the model and the algorithm.At the same time,it shows that the simulated annealing algorithm has a certain optimization effect on the initial solution of the random walk algorithm.It can be seen that the two-stage heuristic algorithm can solve the NP-hard problem in a short time and obtain a relatively satisfactory solution,which can provide a certain method reference for solving large-scale network optimization problems.
作者
常馨玉
CHANG Xin-yu(China Academy of Transportation Sciences,Beijing 100029,China)
出处
《交通运输研究》
2021年第4期58-66,共9页
Transport Research
关键词
公路网布局
路段重要度
运输需求
混合整数规划模型
两阶段启发式算法
highway network layout
importance degree of road section
transportation demand
mixed integer programming model
two-stage heuristic algorithm
