MULTICOMMODITY NETWORK FLOWS WITH SAFETY CONSIDERATIONS
成果类型：
Article
署名作者：
CHEN, YL; CHIN, YH
署名单位：
National Tsing Hua University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S48
发表日期：
1992
页码：
S48-S55
关键词：
摘要：
Previous research on the multicommodity minimum cost flow problem (MMCFP) has assumed that there are two types of values associated with an arc. The first is the capacity of the arc and the second is the unit flow cost along the arc. This paper adds the third attribute-the degree of difficulty-into the conventional model of the MMCFP. In this way, a new problem, which is more general and difficult than the conventional MMCFP, is formed. However, we show that these two problems are indeed polynomially equivalent. With the equivalence, the techniques developed for solving the conventional MMCFP can be used to solve the new but more general problem.