On Maximal Flow Problem in a Transportation Network with a Bundle

Journal of

tl~e

Operations Researcl'l

Society of Japan

VOLUME 10 June 1968 NUMBERS 3 & 4

- - - -- - -

-ON MAXIMAL FLOW PROBLEM IN A TRANSPORTATI-ON

NETWORK WITH A BUNDLE

TAKASHI KOBAYASHI

Faculty of Engineering, University of Tokyo

(Received June I, 1967)

Abstract

The author reduces the maximal flow problem in a transportation network with a-bundle, which is a subset of its arcs and associated with a capacity, to a parametric programming problem. The latter is related to one of the usual transportation network problems, and a primal-dual algorithm for solving it is shown. This approach is very similar to Jewell's for the critical path analysis in a project with a divisible activity.

1. Introduction

Berge [1] presented the maximal How problem in a transportation network with bundles as one of special problems of maximal flow. Bundle implies a subset of arcs of the network and is associated with a capacity. The author reduces the maximal How problem in a network with a bundle to a parametric programming problem which is related to one of the usual transportation network problems, and shows a primal-dual

70 T. Kobaya8hi

algorithm for solving the latter. It is very similar to Jewell's algorithm [4] used for the critical.path analysis in a project with a divisible activity.

2. Mathematical Formulations of Problems

Let A denote the set of directed arcs, ordered pairs of nodes, of a transportation network with n nodes: 1 (the source), 2, " " n-l, n (the sink). We shall consider the case when A consists of a bundle B whose capacity is C and its complement

B,

each arc (i, j) of which is associated with capacity Ci j • We define P (i) and S(i) for node i as follows:

PCi)= {jjU, i)eA} ,

S(t)

=

{jj(i, j)eA} .

Then, a mathematical formulation of the original problem is obtained:

subject to

Maximize p,

l

P, for i=l,

I:

Xij-

I:

Xfi= 0, for ri:1,

n,

jESCi) jEI'(i) •

-p, for

t=n,

Ci/~X; i~O for

Ci,

j)eB ,

Xij~O

I:

Xij:;aC. (i,jJEB

for (i, j)eB ,

Here, we shall introduce a parameter A and consider a parametric programming problem:

subject to

Maximize {J.p-

I:

Xii} ,

B

l

p, for i=l,

I:

xij-

I:

Xji= 0, for ;*1,

n,

jESCi) jEI'(i)

-p, for

i=n,

Cij~Xij~O for (i,j)eB,

Xii~O for (i,j)eB.

Maximum Flow Problem 71

the followings.

Theorem 1. Let (p.*,X*) be an optimal solution of PIA for some positive

A. If

r:

X;I= C, it is also optimal to the original problem.

s

Proof. (p.*, X*) is a feasible solution of the original since

r:

X;j~C, Let

s

(fl, X) be an optimal solution of the original. Then, (f-/, X) is a feasible

solution of PIA. Hence,

As A>O, f-/*';;;,f-/. Therefore, (f-/*, X*) is an optimal solution of the

original problem.

Theorem 2. For A greater than

IBI,

the number of elements of B, an optimal solution of PIA, (f-/*, X*) is also optimal to the original problem if

r:

X;j<C,

B

Proof. Obviously, (f-/*, X*) is a feasible solution of the original. Assume that it is not optimal. Then, there exists a path from node 1 to node

n,

CiI=l,

i2 , · · · , im _ l , im=n), such that

3) (ik+1' ik)sA and Xi;+ lik>O.

By selecting a sufficiently small positive number e and putting

f-/=p*+e,

I

X;J+e, if (z,j) is a forward arc of the path (Case 1 or 2), Xij= x;J-e, if (i,j) is a reverse are of the path (Case 3),

X;j, otherwise,

72 T. Kobagaahi

which contradicts that (p.*, X*) is optimal to PI~. Hence, (p.*, X*) is optimal to the original. The proof is completed.

From the theorems above, we may solve a parametric programming problem PIJ, instead of solving the original directly. PI~ is one of the problems related to the following transportation network flow problem: D*lp.

subject to

Minimize

{I:

Xij} ,

B

1

p. for ;=1,

I:

Xij-

I:

Xji= 0 for i*l, n,

jES(i) jEi'(i) .

-I' for t=n,

Cij~Xij~O for (i,j)eB,

for (i,j)eB. Note that I' is a parameter here.

According to Kurata's formulations [5],· we shall introduce the dual problem of PIJ (called DI.l.), the restricted one based on (v), which is a part of an optimal solution of DI~, (v, t) (called RPI~(v», and the restricted one based on (X), an optimal solution of D*Ip. (called RP*II'(X». DI.l.

subject to

RPj.l.(!;) subject to

Minimize

{I:

Cijtij} ,

B tJ~O, Vi-Vj+tij~O , Vi-vj;;;;;-l, Maximize p., for (i,j)eR, for (t",j)sB.

1

p. for i=l,

I:

Xij-

I:

Xji= 0 for i*l, n,

jES(i) jEi'(i) •

-p. for z=n,

Xij=O if (i,j)sR and Vi-Vj>O, Cij;;;;;Xij;;;;;O

Xij=Cij Xij=O

Xij~O

if (i,j)sR and Vi-Vj=O,

if (i,j)sR and Vi-Vj<O,

if (i,j)sB and Vi-vj>-l,

· Maximum Flow Problem

where (v) is a part of an optimal solution of DIA, (v, t). RP*lp(X)

subject to

Maximize A,

Vn-Vt-A=o,

V,-Vj~O if (i,j)eB and xu=O,

Vi-Vj=O if (i,j)eB and Cij>Xij>O,

V,-Vj;;S;O if (i,j)eB and X'j=Cij,

Vi-vj;;;;;-1 if (i,j)eB and Xij=O,

vi-vJ=-1 if (i,j)eB and Xij>O,

where (X) is an optimal solution of D*lp.

The following theorems are proved by Kurata's propositions.

'/3

Theorem 3. (p, X) is a feasible solution of RPIA(V) if and only if it is an optimal solution of PIA.

Theorem 4. Let (A, v) be an optimal solution of RP*lp(X), and tij=max

(Vj-V, ,0) for (i,j)eB.

Then, 1) (v, t) is optimal to DIA, and

2) (p, X) is a feasible solution of RPIA(V) and also an optimal

one of PIA.

The next theorem is available when we wish to get an optimal solution for a special value of C.

Theorem 5. Let (Pt. Xt) and (P2, X 2) be both optimal solutions of PIA.

Then, for 0<0<1, [O,tl.t+(1-0)P2, OXd-(1-0)X2] is also optimal to PIA.

3. Algorithm

Since it is easily seen that (X=Oj is an optimal solution of D*lp=O,

Y'e start with p=O, X= 0, and continue to solve RP*lp(X), or RPIA(V)

alternatively until it occurs that A>

I

BI

or that

L:

X'j;;;;; C. The flow chart B

of the algorithm is shown in Fig. 1.

To solve RP*lp(X), Iri's G matrix method [3] is applicable, and the procedure for solving RPI)(v) given its feasible solution can be con-structed similarly as the usual maximal flow labeling procedure [2]. Here, it is very useful that an optimal solution of RPIA(V) is a feasible

solu-74

T. Kobayashi

Put

f.l=O

and X

=0.

Find an optimal solution

of RPl(If.l(%):

(A, V

).

Y

Find an optimal solution

No!

Yes!

Fig. 1.

tion in the next step (Theorem 4). Details of these procedures are deleted.

4. Remarks

In a network with two or more bundles, it is much difficult to solve the problem by this approach.

Maximum Flow Problem 75 It is advisable that the labeling procedure and (9 matrix method are programmed in more general forms so as to be applied to the transport-ation network problem, the critical path method, and some other problems to arise.

Acknowledgement

The author is deeply grateful to Dr. M. Iri for his suggestion of the problem.

REFERENCES

[ 1] C. Berge and A. Ghouila-Houri, Programming, Games and Transportation Networks (English Translation), Methuen, 1965.

[ 2] L.R. Ford and D.R. Fulkerson, Flows in Networks, Princeton University Press,

1962.

[3] M. Iri, "A New Method of Solving Transportation- Network Problems,"

]ORS], 3, (1960).27-87

[4] W.S. Jewell, " Divisible Activities in Critical Path Analysis," ]ORSA 13, (1965) 747-760.

[5] R. Kurata, "Primal Dual Method of Parametric Programming and Iri's Theory on Network Flow Problems," JaRS], 7, (1965) 104-144.