A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem

• 作者: Mircea Parpalea
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: DYNAMIC Network PARAMETRIC COST Bi-Criteria Minimum COST FLOW Successive Shortest PATH
• 年，卷（期）: 2011,（3）
• 页码范围: 116-126
• 页数: 11页
• 分类号: O1

摘要

This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.