关键词: 赋权有向图   ,   , N 条最短路径  ,   ,  成品油管道   ,  , 优化设计

Abstract: Under condition of the possible locations of the pump station were determined. And   applied directed edge-weight graph to describe the optimization problem of the products pipeline, and graph theory was used to analyze the problem. The candidate pump station locations were taken as the vertices and the total cost of the pipeline system between the two vertices were looked as the edge-weighted. Then algorithm recursively calling the Dijkstra algorithm was designed and analyzed to obtain N shortest paths, so the optimal alternative and the quasi-optimal alternatives were obtained at the same time, these alternatives can be used to compare by the designer. Moreover, the algorithm was tested by a real example; it can meet the need of real application. Applied this method can avoid adjustment the locations of the pump station, and more fit the need of the engineering. It also can be extended to the other long-distance oil or gas pipeline optimal design.

Key words: Directed edge-weighted graph  , N shortest paths   ,   , Products pipeline  ,   , Optimal design