Proc. Indian Acad. Sci., Vol. 86 A, No. 6, December 1977, pp. 513-518, 9 Printed in India.

Time minimizing transportation problems

J K SHARMA and KANTI SWARUP*

Mathematics Department, DN College, Meerut 250 002
*Indian Institute of Publie Administration, New Delhi 110 002

MS received 28 Ap¡ 1977; revised 30 September 1977

Abstraet. A procedure for time minimization in a transportation problem is developed

and consists of a finite number of interactions and is based on moving from a basie
feasible solution to another till the Iast solution is arrivr at. A numerical example
is given in support of the theory.

Keywords. Time minimization; transportation prob/em; closed loop; basic and

non-basie eells.

1. Introductfon

Recently, the problem of transportation in minimum time has been studied by

Hammer 1969, Gartinkel and Rao 1971, and Szwarc 1971, etc. In this paper, another
method of achieving a minimum time of transportation has been developed which is
very different from other existing methods.
In a time minimizing transportation problem time matrix [tu] is given where t u is
the time of transporting goods from ith origin to jth destination. For any given
feasible solution X = [Xu] satisfying the given condition of supply and demand, the
time of transportation is the maximum of tu's among the cells in which there are
posifive allocations i.e. time of transportation is [max t o : x u > (3]. This time of
(i,j)
transportation remains independent of the amount of commodity sent so long as
xu>O.
Ir is assumed that (i) the carriers have suiticient capacity to carry goods from an
odgin to destination in a single trip (ii) they start simultaneously from their respective
origins.
For situations where reducing, if not minimizing, the time of transportation may
be important are:
1. In military transportation, where in times of emergency, the time of transportation
is of prime consideration, 2. In the transportation of perishable goods such as
fresh fruits and vegetables, etc., where a delay in transportation may result in mueh
larger loss than any cost advantage attained by transporting at lowest cost, 3. When
redueing the pipe-line inventory is important. The opportunity eost on money Iocked
up in the forro of pipe-line inventory, may be higher than a cost advantage attained
by transporting at lowest eost, 4. When the service level provided by a producer to
its stockists in terms of promptness of delivery Oead time reduction) constitutes an
important competitive advantage.

513
514 J K S h a r m a a n d K a n t t Swarup

Doubtless, many other situations can be thought of where the time of transporta-
tion is a re]evant consideration.

2. Theoretical developments

The time minimizing transportation problem is to determine the real non-negativo

variables ' x u ', i ~- 1, 2, .... m ; j = 1, 2 . . . . , n satisfying the constraints

N
F, x u=a. i=1,2 .... , m (supply) (1)
j=l

m
F, x u = bJ, j = l , 2, ... , n ( d e m a n d )
151

x~j t> 0

and minimize [max t u : x u > 0]

(i,/)
where a~ and bj are given non-negative number and

m n

i-1 1-1

Here the objr function is n o t a convex function.

2.1. Definitions

2.1.1. A f e a s i b l e solution: A set X ---- [xu] o f non-negative numbers satisfying (1) is

~ l l e d a feasible solution.

2.1.2..4 b e t t e r f e a s i b l e solution: Let X 1 = [xXu] and X i : [xso] be two fcasiblo

solutions of problem of transportation in minimum time; Let

M1 = ((i,1) : x,,: > 0}, M, ~ {(i,2) .~x,,j > 0 }

T 1 -~ max tu, Ti-~ max tu

ff,/) ~ M, (t,/) G M ,

N 1 ----~.(i, j ) : t u ----- T x, (t, j ) E MI~"

N s -----~(i, j ) : t,: = Ts, (i, j ) E Ms~-

A soIution Xs is said to be better than X l, ir either T~ < Tx or Ts = Tz,

F, xtu < ,~ XZu

ff, /) E N, U,/) ~ N,
Time minimizing transportation problems 515

2.1.3. Optimal solution: A feasible solution for which [max t o : x U > 0] is minimal
ff,J)
and there exist no better feasible solution is said to be the optimal solution.

3. The basie theorems

On the basis of theorems 1 and 2 given below, we develop a new algorithm for the
time transportation problem.
Theorem 1: If there is a feasible solution to a set of simultaneous equations
A X ~ b, X >1 O, then there is a basic feasible solution (Hadley 1962, p. 80).
Hadley (1962) has proved this theorem by reducing the number of positive variables
in the given feasible solution one by one till the columns of A associated with positive
variables Bre lineafly independent.
Ir may be noted that in the proof of this theorem the set of positive variables in
the basic feasible solution is a subset of the positive variables in the given feasible
solution. The values of the variables in the two sets, however, may be dŸ241
Theorem 2. A locally optimal solution to the problem of transportation in mŸ
mum time is also globally optimal.
The proof of this theorem has been given by Hammer (1969), Gar¡ and Rao
(1971) and Szwarc (1971).

4. The algorithm

The algorithm eonsists of three main steps:

1. Construction of a starting basic feasible solution, which can be obtained by
any available method for cost minimizing transportation problem.
2. Finding of ah adjacent better basic feasible solution and
3. Perform step 2 till no better adjacent basic feasible solution can be obtained.
Step 2, deals with the determination of a cell (i, j) not in the basis which, when
introduced into the basic would reduce the time of transportation or reduce the allo-
cation in the cell belongs to N. Wherc N is the set of cell (or cells) with positive
allocations and corresponding time equal to the time of transportation.
Ir there are two of more than two cells belonging to N having the time equal to the
time of transportation then we make basic such a variable which, when becoming
positive, reduce the value of ,Y, xlj so that ultimately we may be able to reduce
ff,j) ~ N
the time of transportation (if further reduction is possible). This can be done
in the same way as discussed by Hammer (1971). For the sake of convenience,
among the cells belonging to N, wc select the cell to minimize time of transportation
which have maximum allocation. Furthermore if there is a tie with respect to maxi-
muro allocations in the cells belonging to N, the allocation may be reduced in any
one of hern.
Hence step 2 consists of the following substeps:

2.1. Determination of a cell (h, k) belongs to N having the greatest allocation say
516 J K Sharma and Kanti Swarup

2.2. Determination of the set Shk ofall cells (i,j) not in the basis, such that ifany one
of these cells introduced into the basis would either eliminate the cell (h, k) or
reduce the amount xh~.

2.3. Choosing among the elements of S~~ the one, say (r, s) for which t,,is mŸ
as follows:
Construet a closed loop as in the regular transportation problem starting from the
cell determincd in step 2.1 and through that non-basic cell (E S~k) having minimum
t~j such that when values at the corncrs are shifted around, the basic variable (step
2.1) is deriven towards zero and no variables becomes negative. If this r loop
is not possible, then try to construet a loop through another non-basie cell, say (p, q)
E Shk having next higher value of ha. If this loop is also not possible then construct
another loop through the ccll E Sh~,having next higher value of hj than (p, q) and so
on. If no sucia closed loop is possible, the process tcrminates. Otherwise go to
step 2.4.

2.4. Introduce the cell into the basic determined in 2.3.

Determination of the set Shk

Let X ---- [x~j] be any basic feasible solution of our problem yielding time T of trans-
portation.
Let M ---- ( (i, j) : xl~ > 0) : N : ( (i, j) : hj : T, (i, j) E M}. To the set M of basic
elements (considered as vertices) can be associated by a graph by considering their
seniority in the matrix -(ti ii- (i.e. the values of hj's corresponding to the basic ceUs).
Let us divide the set M into levels Lo, Lt, L a ... in the following way: The
level L O will consists only the vertex (h, k) determined by (2.1). The level Li, will
consist of all those elements of M having th'k' < thk. The level L2 will consist of
all those elements of M having th'k" < th'k' < th~ and so on. The decomposition into
levels is unique due to lack of cycles in the graph of M.
As in Hammer (1969), now let us associate to every row i and index u (i) in the
following way: if the element of M belonging to row i are (i, Jl) E Lpt, (i,.~) E Lo,, ...
and p(i) is the smallest of indices Pi, P2 .... then

f~ ifp(i) is even
u(i) -~ ifp(i) is odd

In the same way, let us associate to every coloran j ah index v (j) in the following way:
If the elements of M belonging to column j are (j, ir) E Lq~, (j, ia) E Lq, ... and if
q(j) is the smallest of the indices qt, q2 . . . , then
v(j) = 110 if q(j)is even
ir q(j) is odd

Further, let us put (i, j) j~ M, Z (i, j) : u(i) -{- v (j) -- 1. Thus we constructed the
set Sh~ of those non-basic ceUs for which Z (i, j) ~< 0 a n d a closed loop can be cons-
tructed, i.e.
S~k = ( ( i , j ) : (i,j) ~ M, Z ( i , j ) <~ O, t u < T}
Time minimizing transportation problems 517

If Sh, ----~, process terminates.

If Sht # ~, go to step 2
Convergence. The procedure is bound to converge for it involves movement from
one basic feasible solution to another basic feasible solution which are finite in num-
ber.

5. Remark
There is no loss of generality in assuming that the problem is non-degenerate.

6. Numerical example

Let there be four producers supplying 37, 22, 32 and 14 units, respectively, with six
consumers demanding 15, 20, 15, 25, 20 and 10 units respectively, and the following
table gives data concerning the transportation times t o, i-----1,2 .... ,4; j = l , 2 .... ,6.
al

25 30 20 40 45 37 37

30 25 20 30 40 20 22

40 20 40 35 45 22 32

25 24 50 27 30 25 14

15 20 15 25 20 10
An inifial ~asible solufionXxis ~venbelow (ByNo~h-West Corner rule).
u(i)
15 20 ] 2 I o
I131 9 l i o
~~11'1 o
] 4 10 0
~j) 1 o o 1 0 1

Here, T1 = 45, N 1 = ((3,5)} hence (h, k) = (3,5) and the levels according to the values
of to's in basic cells are
Lox={(3,5)), L~X-~{(3,4)), Ltt={(l,2),(2,4),(4,5)]} -
L,I = {(1,1), (4,6)}, r 91 = {(1,3), (2,3)}
we have Sta~ = {(1,6), (2,6), (3,6)}.
518 J K Sharma o.ad Kanti Swarup

The smallest t~j with (i, j ) E Sa51 being t2e= 2 0 , we introduce it into the basis, this
will eliminate of reduce the allocation of (3,5) = (h, k), thus the new solufion X s is
given by
u(O
15 20 2 O

13 9 0

25 7 0

13 1 0

v(j) 1 0 0 1 0 l
Hcre Ti ----45, N, = { (3, 5)} hence (h, k) = 3, 5).
Procecding in the same manncr we gct an optimal solution given below

(u~O
15 13 9 O

6 6 10 0

25 I

14 0
v(j) i o o 1 o 0
Since Sat : ~. Thus the process terminates.
Hence the time of transportation is T = 40.

Acknowledgements

We are grateful to Council of Scientific and Industrial Research for the financial
assistance and to the referee for bis valuable suggestions.

Referenees

Dantzig G B 1963 Linear Programming and Extensions Oqew Jersey: Prinr Univ. Press)
Garfinkel R S and Rao M R 1971 Nav. Res. Log. Q. 18 465
Hadley G 1962Linear Progranuninf (Mass: Addison Wesley)
Hammer P L 1969 Nav. Res. Log. Q. 16 345
Hammer P L 1971 Nav. Res. Log. Q. 18 487
Szwarc W 1971 Nav. Res. Log. Q. 18 473