关键词: 长输管道, 匹配, 泵组合, 组合优化, 搜索算法, 搜索树

Abstract: In order to solve the optimal matching problem of oil pipelines by dynamic programming,a sub-problem of how to find the effective pump combination in pipeline pumping station arises.From the concept of effective pump combination,two models on the sub-problem are established,which correspond to two modes of pump combination in a pumping station,series and parallel.Being a combinatorial optimization problem,the two models can be solved by heuristic DFS algorithm,and the process of the algorithm may be graphically described by a binary searching tree.To a great extent.the efficiency of the algorithm depends on the effectiveness of the backtracking principles used in the searching process,so a set of backtracking principles which are based on the features of the two models are set up.Practical applications of the heuristic DFS algorithm have shown that it is efficient,with the number of pump combinations in enumeration largely reduced.The problem and the algorithm proposed in this paper are of general importance for the optimal matching problems of nipei:nes and pipeline networks of oil and gas.