关键词: 通风网络图, 最长路径法, 整数规划, 分层法, 模拟退火遗传算法

Abstract: Drawing ventilation network graph based on longest path method requires frequently searching the longest path between any two nodes. There is a lot of time wasted in useless paths search process because of the depth first search algorithm. Geometric intersection method is adopted to determine the arc crossings, but it has low efficiency and can not effectively reduce the arc crossings number. The layered method is introduced to ventilation network graph drawing. The longest path method is employed to rank nodes of ventilation network, and long edges are removed by solving integer programming problem for optimizing node ranking. Then simulated annealing-genetic algorithm is used to optimize the nodes order based previous node ranking step, reducing the arc crossings number from the network topology. In order to decrease the meaningless longest path search process, a modified version of the longest path method is made to calculate node coordinates and arc shape, which is called longest parallel path method. The test example of drawing ventilation network graph is presented based on layered method.

Key words: ventilation network graph, longest path method, integer programming, layered method, simulated annealing-genetic algorithm