有有效时间约束的最大流问题及其算法

摘要

交通运输在抗震救灾中起着非常重要的作用,无论是运输量的多少或是时间的及时与否,都直接影响着救灾的效果.而前人的单发点最短路径算法,难以满足救灾中多处救援物资及时到达和救援物资量上的需要.本文设计了确定救援站点(发点)的快速搜索程序,并在此基础上将单发点的救援路线问题扩展为多发点问题.同时考虑各条路段的最大运输量,使得出的紧急救援路线,不仅能满足救援物资的及时到达,同时又能满足对救援物资等运输量上的需求.