一类点权网络的最小费用流问题  

Minimum Cost Flow Problem on Some Networks with Node Weight

作　　者：高明霞[1,2] 贺国光[2] 

机构地区：[1]兰州交通大学交通运输学院,兰州730070 [2]天津大学管理学院,天津300072

出　　处：《武汉理工大学学报（交通科学与工程版）》2012年第3期454-457,共4页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：教育部博士点基金项目(批准号:20116204120005);教育部人文社科基金项目(批准号:12XJCZH002)资助

摘　　要：以城市路网为背景求最小费用流时不能忽略交叉口的费用和通行能力限制,但由于交叉口延误等费用和通行能力具有方向性,普通最小费用流算法无法直接应用于这类问题.文中以节点权重表示交叉口的延误和通行能力,将城市道路网表示为一个节点具有分方向权重的点权网络,提出了一个改进的最小费用路算法求解这类点权网络中的最小费用流问题.算法计算时间复杂性为O(nmf0).以一个数值算例说明了算法的应用.Minimum cost flow problem has been widely used in the area of traffic and transportation. But urban road network is special for intersection movement capacity and delay have different value in different direction, and intersection capacity and delay can not be ignored when finding minimum cost flow in such network. Most minimum cost flow algorithms can not be directly adopted to find mini- mum cost flow in such network. Urban road network is modeled through a directed network with capacity and delay at intersections represented by directional weight at nodes. An improved successive shortest path algorithm is presented to find minimum cost flow in such network. Its time complexity is O（nmfo）. A numerical example is given.

关 键 词：城市路网 点权网络 最小费用流 最小费用路算法 

分 类 号：O157.5[理学—数学]