${}^{\ast }$Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas- Sétif 1, Sétif, Algérie, e-mail: rzitou@yahoo.fr.

${}^{\mathrm{\S }}$Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas- Sétif 1, Sétif, Algérie, e-mail: achache_m@yahoo.fr.

1 Introduction

The transportation problem is an important subject in real-world life that covers many important problems in economy, telecommunication and localization, among others. As a special case, the transportation problem with two-dimensional index has been extensively studied and solved by L. V. Kantorovich and M. K. Gavurin (1949, [ 4 ] ) and G. B. Dantzig (1951, [ 2 ] ). Next, the study and the solution have been extended to transportation problems where the dimension of the index is higher than two. Since the sixties, several papers have been published for uncapacitated problems with a three-dimensional index and a general multi-dimensional index, see for instance [ 3 ] , [ 5 ] , [ 6 ] and [ 7 ] .

Recently, Zitouni [ 10 ] , first introduced an algorithm for solving a capacitated transportation problem with 4-index (four subscripts). The choice for the index transportation problem allows us to getting an idea for the more general multi-dimensional transportation problem case.

Our aim in this paper is to examine two exact simplicial methods for the solution of the capacited 4-index transportation problem, the method developed in [ 10 ] and the simplex method. Because the algorithm developed in [ 10 ] , tackles directly the problem, and shows its elegant computation and its rapidity convergence to provide a solution of this problem. For the comparison purpose, the obtained numerical results are compared with those obtained by the classical simplex approach applied to the reformulation of this problem as a linear program.

The outline of the paper is as follows. In Section 2, the 4-index capacited transportation problem formulation is stated. In section 3, the transportation problem solution is given. In section 4, the detailed description of two exact simplicial algorithms and the convergence of the second algorithm are presented. In section 5, some computational results are reported, followed by an important numerical comparison between their performances. Finally, a conclusion and future researchers are drawn in the last section.

Some notation used throughout the paper is as follows. ${\mathbb{R}}^r$ denotes the space of $r$-dimensional real vectors whereas the set of all matrices with type $(r_1,r_2)$ is denoted by ${\mathbb{R}}^{r_1\times r_2}$. If $x,z\in$ ${\mathbb{R}}^r,$ then $x^{T}z$ denote their usual inner product. If $S\in {\mathbb{R}}^{r_1\times r_2}$, then its rank is defined as $\mathrm{rank}(S)=r\le min(r_1,r_2)$.

2 The capacitated 4-index transportation problem formulation

The capacitated transportation problem with a four-dimensional index, denoted by $(T_{4C})$, is formulated as the following constrained optimization problem:

          subject to the constraints:

where ${\alpha }_i$, ${\beta }_j$, ${\gamma }_k$, ${\delta }_l$, $d_{ijkl}$ and $c_{ijkl}$ are given and such that for all $i$, $j$, $k$, and $l$, ${\alpha }_i>0,$ ${\beta }_j>0,$ ${\gamma }_k>0,$ ${\delta }_l>0,$ $d_{ijkl}>0$ and $c_{ijkl}\ge 0$.

The $T_{4C}$ problem can be also reformulated as the following linear program:

with

• $x=(x_{1111},...,x_{mnpq}{)}^T\in {\mathbb{R}}^N,$

• $c=(c_{1111},...,c_{mnpq}{)}^T\in {\mathbb{R}}^N,$

• $d=(d_{1111},...,d_{mnpq}{)}^T\in {\mathbb{R}}^N,$

• $b=({\alpha }_1,...,{\alpha }_m,{\beta }_1,...,{\beta }_n,{\gamma }_1,...,{\gamma }_p,{\delta }_1,...,{\delta }_q{)}^T\in {\mathbb{R}}^M,$

• $A\in {\mathbb{R}}^{M\times N}$, where $M=m+n+p+q$ and $N=mnpq$.

In this representation $x=(x_{1111},x_{1211},...,x_{mnpq})$ has been associated to a vector $x\in {\mathbb{R}}^N$. To do that, we associate to each $(i,j,k,l)\in \{1,..,m\}\times \{1,..,n\}\times \{1,..,p\}\times \{1,..,q\}$ a vector $P_{ijkl}\in {\mathbb{R}}^M$. Only four entries of the vector $P_{ijkl}$ are nonzero, they are located on lines $i,$ $m+j,$ $m+n+k$ and $m+n+p+l,$ and their common value is 1. Note that $P_{ijkl}$ are the columns of $A$, they are called coefficients vectors.

In the sequel, we quote the following useful definitions (see [ 13 ] ).

Throughout the paper, we assume that the following feasibility assumption for $T_{4C}$,

holds.

As a consequence, it results that

Unlike the transportation problem with two-dimensional index, the matrix $A$ is not totally unimodular since some of its minors do not belong to $\{-1,0,1\}$.

It is useful to present the data of the problem thanks to the following transportation table. It consists of an array of $M$ rows and $N$ columns, three additional rows and an additional column. The entries of these $N$ columns of the first, second, and third additional rows are reserved for the data of the quantities $d_{ijkl}$, $c_{ijkl}$, and $x_{ijkl}$, respectively. The additional column is for the data of quantities ${\alpha }_i$, ${\beta }_j$, ${\gamma }_k$, and ${\delta }_l$, respectively. Finally, the entry of the array on the line corresponding to ${\alpha }_{i^{{}^{\prime }}}$ and the column $P_{ijkl}$ is $1$ if $i=i^{{}^{\prime }}$ and $0$ otherwise. Same things for ${\beta }_{j^{{}^{\prime }}}$, ${\gamma }_{{}_{k^{{}^{\prime }}}}$, and ${\delta }_{l^{{}^{\prime }}}$. We illustrate that by the following example.

$$

c1211

.

cmnpq

.

x1111

.

$$ $$

x1211

.

xmnpq

.

α1

.

$$
1|c|: : ... : 1|c|:
1|c|0 0 ... 1 1|c|$$

αm

.

$$
1|c|1 0 ... 0 1|c|$$

β1

.

$$
1|c|0 1 ... 0 1|c|$$

β2

.

$$
1|c|: : ... : 1|c|:
1|c|0 0 ... 1 1|c|$$

βn

.

$$
1|c|1 1 ... 0 1|c|$$

γ1

.

$$
1|c|: : ... : 1|c|:
1|c|0 0 ... 1 1|c|$$

γp

.

$$
1|c|1 1 ... 0 1|c|$$

δ1

.

$$
1|c|: : ... : 1|c|:
1|c|0 0 ... 1 1|c|$$

δq

.

$$

$$

$T_{4C}$ - Transportation table.

3 Transportation problem solution

3.1 Feasibility conditions

We begin first to give a useful theorem that ensures the feasibility of $T_{4C}$ problem (see [ 13 ] ).

1. It is clear that if $x=(x_{ijkl})$ is a feasible solution for the problem $T_{4C}$, then conditions 8 and 9 hold.
2. Assume that $x=(x_{ijkl})$ is a vector of ${\mathbb{R}}^N$ such that

We can easily verify that $x$ is a feasible solution for the problem $T_{4C}$. Note that if the set of feasible solutions of the problem $T_{4C}$ is non empty, then it is a polytopes. Since the objective function is continuous, then the set of the solution of the problem $T_{4C}$ is non empty, i.e., there exists at least an optimal solution of it.

3.2 Optimality conditions

In this subsection, we give a theorem that ensures when a feasible solution, is an optimal solution of $T_{4C}$.

For that, we consider the following formulation of the problem $T_{4C}$:

and its dual problem is given by

Let $(y,z)$ an optimal solution of the problem 12. Then a feasible solution $x$ of the problem 11 is optimal if and only if the two following complementarity conditions are satisfied

and

• If  $x_{ijkl}=0,$   then   $x_{ijkl}<d_{ijkl}$  and 14 imply   $z_{ijkl}=0.$ So   $(A^{T}y{)}_{ijkl}\le c_{ijkl}$.

• If   $0<x_{ijkl}<d_{ijkl}$   then  14 implies   $z_{ijkl}=0$   and 13 leads to   $(A^{T}y-z-c{)}_{ijkl}=0.$ So $(A^{T}y{)}_{ijkl}=c_{ijkl}$.

• If $x_{ijkl}=d_{ijkl}$ then $x_{ijkl}>0$ and 13 imply $(A^{T}y-z-c{)}_{ijkl}=0$, consequently $(A^{T}y-c{)}_{ijkl}=z_{ijkl}.$ Finally, we get $(A^{T}y{)}_{ijkl}\ge c_{ijkl}.$

4 Description of two simplicial algorithms for $T_{4C}$

4.1 The simplex algorithm

In this subsection, in order to apply the technical of the simplex algorithm for solving $T_{4C}$ problem, we need first to put $T_{4C}$ in the framework of a special linear program. The simplex algorithm, is referred to us as Algorithm 1. It is well-known that the problem $T_{4C}$, according to 7, can be easily reformulated as the following linear program:

in adding to the constraints those of the form: $x_{ijkl}+y_r=d_{ijkl}$, (see 6 above), for $i=1,\dots ,m,$ $j=1,\dots ,n,$ $k=1,\dots ,p,$ $l=1,\dots ,q,$ $r=1,...,N$, where

• $y_r$ is the gap variable,

• $\hat{x}=(x^T,y^T{)}^T\in {\mathbb{R}}^{2N}$ with $y=(y_{1,}\dots ,y_N{)}^T,$

• $\hat{c}=(c^T,0^T{)}^T\in {\mathbb{R}}^{2N}$ where $0$ is a $N$-null vector,

• $\hat{b}=(b^T,d^T{)}^T\in {\mathbb{R}}^{M+N},$ with $d$ is the vector of $N$ components $d_{ijkl}.$

• $\text{Unknown environment 'tabular'}$A0$\text{Misplaced hline}$I_NI_N$$

R^M+N×2N$$  with $\mathrm{rank}(\hat{A})=M+N-3$. $I_N\in {\mathbb{R}}^{N\times N}$ is the identity matrix.

4.2 Algorithm 2

According to the particularities of $T_{4C}$ problem, Zitouni [ 10 ] , proposed a modification of the simplex algorithm. This algorithm is referred here as Algorithm 2, which shares with the simplex algorithm, a structure consists also of two phases such as the finite convergence and the use of the pivot principle. The advantage of this new algorithm is that it tackles the $T_{4C}$ directly without passing by other reformulations. For more comprehension of this new algorithm, we detail its fundamental ingredients (steps) as follows.

Phase 1. (It finds a basic feasible solution or declare that $T_{4C}$ is not solvable)

Step 1:

Initialization: for all $(i,j,k,l),$ ${\hat{\alpha }}_i={\alpha }_i,$ ${\hat{\beta }}_j={\beta }_j,$ ${\hat{\gamma }}_k={\gamma }_k,$ ${\hat{\delta }}_l={\delta }_l$ and $b_{ijkl}=0$, ($b_{ijkl}$ is a boolean variable equal to $1$ if $x_{ijkl}$ has already been determined and $0$ if not yet),

$E=\{(i,j,k,l),\text{ such that }{b}_{ijkl}=0\}$.

Iteration:

While $E$ is non empty do

• Choose an 4-tuple $(\overline{i},\overline{j},\overline{k},\overline{l})\in E,$ such that $c_{\overline{i}\overline{j}\overline{k}\overline{l}}=\underset{(i,j,k,l)\in E}{min}{c}_{ijkl},$ (see Remark 6)

• Take $x_{\overline{i}\overline{j}\overline{k}\overline{l}}=min({\hat{\alpha }}_{\overline{i}},{\hat{\beta }}_{\overline{j}},{\hat{\gamma }}_{\overline{k}},{\hat{\delta }}_{\overline{l}},$  $d_{\overline{i}\overline{j}\overline{k}\overline{l}}),$ and $b_{\overline{i}\overline{j}\overline{k}\overline{l}}=1,$ (i.e., $x_{\overline{i}\overline{j}\overline{k}\overline{l}}$ is determined),

• Update ${\hat{\alpha }}_{\overline{i}},{\hat{\beta }}_{\overline{j}},{\hat{\gamma }}_{\overline{k}},$ and ${\hat{\delta }}_{\overline{l}}$ by the procedure (P1) below.

Step 2:

a) Determine $\xi$ as shown in the procedure (P2) below.
If $\xi =0,$ then $x=(x_{ijkl})$ is an initial basic feasible solution for the problem $T_{4C},$ we denote it by $x^{(0)}.$ Go to Phase 2.

Else, construct the problem $T_{4C}(\tilde{M})$ (as shown in the procedure (P3) below) and determine for it an initial basic feasible solution ${\bar{x}}^{(0)}$ as in step 1 by taking ${\overline{x}}_{m+1,n+1,p+1,q+1}^{(0)}=0$. Note that ${\bar{x}}^{(0)}=({\bar{x}}_{ijkl}^{(0)}),$ with $i=1,\dots ,m+1$, $j=1,\dots ,n+1,$ $k=1,\dots ,p+1$ and $l=1,\dots ,q+1$. If ${\bar{x}}^{(0)}$ is optimal then the problem $T_{4C}$ is not solvable. Stop.

b) Improvement of a basic feasible solution for $T_{4C}(\tilde{M}).$

Initialization: $r=1,$ $\xi >\mathbf{0}$ is known,

1) Determine ${\bar{x}}^{(r)}$ as in Phase 2.

2) If ${\overline{x}}_{m+1,n+1,p+1,q+1}^{(r)}=\xi \mathbf{,}$ then $x^{(r)}=(x_{ijkl}^{(r)})$ with $i=1,\dots ,m,$ $j=1,\dots ,n,$ $k=1,\dots ,p,$ and $l=1,\dots ,q,$ is an initial basic feasible solution for the problem $(T_{4C}).$ Go to Phase 2.

3) If ${\bar{x}}^{(r)}$ is optimal (Phase 2), then the problem $T_{4C}$ is not solvable. Stop. 4) Do $r=r+1$ and repeat 1),$$ to 3).

Next, we describe the second phase.

Phase 2. (Research of an optimal solution for $T_{4C})$

When Phase 2 starts, we know an initial basic feasible solution $x^{(0)}.$ Take $r=0$.

a) Determine the set $I^{(r)}$ of the interesting 4-tuple $(i,j,k,l),$ (see Remark 7).

b) For all $(i,j,k,l)\in I^{(r)}$, solve the linear system

c) For all $(i,j,k,l)\notin I^{(r)}$ determine

d) Apply the procedure described in (P4) below.

If the optimality condition holds then the feasible solution $x^{(r)}$ is optimal. stop.

Else determine a vector $P_{i_0{j}_0{k}_0{l}_0}$ entering at the base, it corresponds to ${\mathrm{△}}_{i_0{j}_0{k}_0{l}_0}^{(r)}$.

e) Construct a cycle ${\mu }^{(r)}$ via the procedure described in (P5) and determine a new feasible solution as the procedure (P6) shows.

f) Do $r=r+1$ and repeat a), to e) until the optimality condition holds.

Also, the algorithm makes appeal to the following procedures.

(P1) - Updating of ${\hat{\alpha }}_{\overline{i}},{\hat{\beta }}_{\overline{j}},{\hat{\gamma }}_{\overline{k}},$ and ${\hat{\delta }}_{\overline{l}}$.

1) ${\hat{\alpha }}_{\overline{i}}={\hat{\alpha }}_{\overline{i}}-x_{\overline{i}\overline{j}\overline{k}\overline{l}},$

if ${\hat{\alpha }}_{\overline{i}}=0$ then take $x_{\overline{i}jkl}=0$ for all $(j,k,l)\ne (\overline{j},\overline{k},\overline{l})$ and $b_{\overline{i}jkl}=1$ for all $(j,k,l),$

2) ${\hat{\beta }}_{\overline{j}}={\hat{\beta }}_{\overline{j}}-x_{\overline{i}\overline{j}\overline{k}\overline{l}},$

if ${\hat{\beta }}_{\overline{j}}=0$ then take $x_{i\overline{j}kl}=0$ for all $(i,k,l)\ne (\overline{i},\overline{k},\overline{l})$ and $b_{i\overline{j}kl}=1$ for all $(i,k,l),$

3) ${\hat{\gamma }}_{\overline{k}}={\hat{\gamma }}_{\overline{k}}-x_{\overline{i}\overline{j}\overline{k}\overline{l}},$

if ${\hat{\gamma }}_{\overline{k}}=0$ then take $x_{ij\overline{k}l}=0$ for all $(i,j,l)\ne (\overline{i},\overline{j},\overline{l})$ and $b_{ij\overline{k}l}=1$ for all $(i,j,l),$

4) ${\hat{\delta }}_{\overline{l}}={\hat{\delta }}_{\overline{l}}-x_{\overline{i}\overline{j}\overline{k}\overline{l}},$

if ${\hat{\delta }}_{\overline{l}}=0$ then take $x_{ijk\overline{l}}=0$ for all $(i,j,k)\ne (\overline{i},\overline{j},\overline{k})$ and $b_{ijk\overline{l}}=1$ for all $(i,j,k).$

(P2) - Determination of $\xi$.

Note that the numbers $a_i,$ $b_j,$ $e_k$ and $f_l$ are nonnegative.

(P3) - Construction of the problem $T_{4C}(\tilde{M}).$

The problem $T_{4C}(\tilde{M})$ is obtained from problem $T_{4C}$ by adding four fictitious points with indices $m+1,$ $n+1,$ $p+1,$ and $q+1$ such that:  $c_{m+1,n+1,p+1,q+1}=0,$ and  $c_{m+1,jkl}=c_{i,n+1,kl}=c_{ij,p+1,l}=c_{ijk,q+1}=\tilde{M},$ where $\tilde{M}$ is a very large number and there are no limitation on the capacities for the paths involving a fictitious point.

(P4) - Determination of a vector $P_{i_0{j}_0{k}_0{l}_0}$ entering at the base or confirming that the feasible solution $x^{(r)}$ is optimal.

Take ${\mathrm{\Gamma }}_0^{(r)}$ and ${\mathrm{\Gamma }}_d^{(r)}$ as two tables such that

and elements ${\mathrm{△}}_{ijkl}^{(r)}$ are represented as variables $x_{ijkl}$ in the transportation table.
By going from the left to the right in ${\mathrm{\Gamma }}_0^{(r)},$ choose

if all elements of ${\mathrm{\Gamma }}_0^{(r)}$ are nonnegative then choose in ${\mathrm{\Gamma }}_d^{(r)}$ similarly,

If all elements of ${\mathrm{\Gamma }}_d^{(r)}$ are non positive, then the feasible solution $x^{(r)}$ is optimal. Stop.

(P5) - Determination of a cycle.

A cycle ${\mu }^{(r)}$ containing some interesting 4-tuple $(i,j,k,l)$ and the non interesting 4-tuple $(i_0,j_0,k_0,l_0)$ corresponding to ${\mathrm{△}}_{i_0{j}_0{k}_0{l}_0}^{(r)}$ is determined by solving the linear system $\sum _{(i,j,k,l)\in I^{(r)}}{\alpha }_{ijkl}^{(r)}{P}_{ijkl}=-P_{i_0{j}_0{k}_0{l}_0}$
The non null solutions ${\alpha }_{ijkl}^{(r)}$ are called coefficients of the cycle ${\mu }^{(r)}$.

(P6) - Determination of a new feasible solution.

Take

If ${\mathrm{△}}_{i_0{j}_0{k}_0{l}_0}^{(r)}\in {\mathrm{\Gamma }}_0^{(r)}$, determine

Next, take

Else $({\mathrm{△}}_{i_0{j}_0{k}_0{l}_0}^{(r)}\in {\mathrm{\Gamma }}_d^{(r)})$, determine

Next, take

(P7) - Determination of a set $I^{(r)}$ in a degenerate case.

1. Take

• $E_b$ the set of vectors corresponding to variables $x_{ijkl}^{(r)}$ verifying

  $$0<x_{ijkl}^{(r)}<d_{ijkl}$$

  and $N_b$ is its element number.

• $E_h$ the set of vectors corresponding to variables $x_{ijkl}^{(r)}$ verifying

  $$x_{ijkl}^{(r)}=0\text{ or }{x}_{ijkl}^{(r)}=d_{ijkl}$$

  and $N_h$ is its element number. We are $N_h=N-N_b,$  with $N=mnpq.$

• $E_s$ any subset with $s=\mathrm{rank}(A)-N_b$ elements of $E_h$, for example the first $s$ elements in $E_h$ by going from the left to the right in the transportation table.

2. At the beginning of this procedure, we know a subset $E_s$ of $E_h$.

i) If the set$(E_s\cup E_b)$ is a free base, then a set $I^{(r)}$ is determined. Stop.

ii) Replace the first (the second, the third,..., or the $s^{th}$) element in $E_s$ by the $(s+1{)}^{th}$ element in $E_h$, or take any other subset $E_s$ of $E_h$, and repeat i) until a set $I^{(r)}$ will be determined. Stop.

4.3 The convergence of Algorithm 2

Assume that the problem $T_{4C}$ is non degenerate. Observe that if $x^{(r)}$ and $x^{(r+1)}$ are two successive feasible solutions of the problem $T_{4C}$ with $Z^{(r)}$ and $Z^{(r+1)}$ are respectively the corresponding objective values then

with

So $Z^{(r+1)}<Z^{(r)}$.
Hence the Algorithm 2 guaranties that the same base never appear in two distinct iterations and since the number of the visited vertices is necessarily finite (at most $C_N^{M-3}$), then it converges finitely.

5 Computational results

The implementation of the two algorithms is running on a Pentium IV with a Microsoft Windows Environment, they are totally written with Borland Delphi. Table 1 summarizes the results obtained for a few numerical experiments.

6 Conclusion and future researches

In this paper, we presented two exact simplicial methods for solving the capacited 4-index transportation problem. The numerical experiments showed that Algorithm 1 is more efficient than Algorithm 8 with respect to the number of iterations and also to the computational time. Moreover, as we have successfully done in some experiments, the arrangements made on Algorithm 1 have appropriately treated the degeneracy problems and led to a considerable reduction of the computational results.

Finally, we point out that our obtained results are independent of the number of indices of the problem, so we can extend Algorithm 1 for solving capacitated transportation problems with the number of indices that are greater than four.