Minimum cost time-varying network flow problems

被引：18

作者：

Nasrabadi, Ebrahim ^{[1
]}

Hashemi, S. Mehdi ^{[1
]}

机构：

[1] Amirkabir Univ Technol, Dept Comp Sci, Tehran, Iran

来源：

OPTIMIZATION METHODS & SOFTWARE | 2010年 / 25卷 / 03期

关键词：

network flows; time-varying networks; shortest dynamic path; minimum cost dynamic flow; MAXIMAL DYNAMIC FLOWS; SHORTEST-PATH; ALGORITHMS;

D O I：

10.1080/10556780903239121

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper deals with a general minimum cost dynamic flow problem in a discrete time model with time-varying transit times, transit costs, transit capacities, storage costs, and storage capacities. For this problem, an algorithm of time complexity O(V nT(n+T)) is presented, where V is an upper bound on the total supply, n is the number of nodes, and T denotes the given time horizon of the dynamic flow problem. The algorithm is a discrete-time version of the successive shortest path algorithm.

引用

页码：429 / 447

页数：19

共 32 条

[1]

Ahuja R., 1993, NETWORK FLOWS THEORY

[2] Dynamic shortest paths minimizing travel times and costs [J].

Ahuja, RK ;

Orlin, JB ;

Pallottino, S ;

Scutellà, MG .

NETWORKS, 2003, 41 (04) :197-205

[3]

[Anonymous], THESIS CORNELL U

[4]

Aronson J. E., 1989, Annals of Operations Research, V20, P1, DOI 10.1007/BF02216922

[5]

Cai X, 1997, NETWORKS, V29, P141, DOI 10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO

[6]

2-H

[7] Time-varying minimum cost flow problems [J].

Cai, X ;

Sha, D ;

Wong, CK .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 131 (02) :352-374

[8]

Chabini I, 1998, TRANSPORT RES REC, P170

[9] Logistics for world-wide crude oil transportation using discrete event simulation and optimal control [J].

Cheng, LF ;

Duran, MA .

COMPUTERS & CHEMICAL ENGINEERING, 2004, 28 (6-7) :897-911

[10] SHORTEST ROUTE THROUGH A NETWORK WITH TIME-DEPENDENT INTERNODAL TRANSIT TIMES [J].

COOKE, KL ;

HALSEY, E .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1966, 14 (03) :493-&

← 1 2 3 4 →