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

摘要： 采用了赋权有向图来表示成品油管道工艺方案优化设计问题,若干个泵站位置候选点对应图的顶
点,两顶点间管段的总费用现值对应弧的权值,通过循环调用Dijkstra算法,求解出了前N 条最短路径作为最优和
次优方案,以备多方案比选。该方法既兼顾了工程实际的要求,又可以给出最优、次优工艺方案。实际算例表明该
方法切实可行。所提出的方法可以推广应用到其它油气管道工艺方案优化设计或其它工程应用。

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