Transshipment problem

Formulation of the problem

A few initial assumptions are required in order to formulate the transshipment problem completely:

• The system consists of m origins and n destinations, with the following indexing respectively: ${\displaystyle i=1,\dots ,m}$, ${\displaystyle j=1,\dots ,n}$
• One uniform good exists which needs to be shipped
• The required amount of good at the destinations equals the produced quantity available at the origins
• Transportation simultaneously starts at the origins and is possible from any node to any other (also to an origin and from a destination)
• Transportation costs are independent of the shipped amount
• The transshipment problem is a unique Linear Programming Problem (LLP) in that it considers the assumption that all sources and sinks can both receive and distribute shipments at the same time (function in both directions)

Notations

• ${\displaystyle t_{r,s}}$: time of transportation from node r to node s
• ${\displaystyle a_i}$: goods available at node i
• ${\displaystyle b_{m+j}}$: demand for the good at node (m+j)
• ${\displaystyle x_{r,s}}$: actual amount transported from node r to node s

Mathematical formulation of the problem

The goal is to minimize ${\displaystyle \sum _{i=1}^m\sum _{j=1}^n{t}_{i,j}{x}_{i,j}}$ subject to:

• ${\displaystyle x_{r,s}\ge 0}$; ${\displaystyle \mathrm{\forall }r=1\dots m}$, ${\displaystyle s=1\dots n}$
• ${\displaystyle \sum _{s=1}^{m+n}{x}_{i,s}-\sum _{r=1}^{m+n}{x}_{r,i}=a_i}$; ${\displaystyle \mathrm{\forall }i=1\dots m}$
• ${\displaystyle \sum _{r=1}^{m+n}{x}_{r,m+j}-\sum _{s=1}^{m+n}{x}_{m+j,s}=b_{m+j}}$; ${\displaystyle \mathrm{\forall }j=1\dots n}$
• ${\displaystyle \sum _{i=1}^m{a}_i=\sum _{j=1}^n{b}_{m+j}}$

Solution

Since in most cases an explicit expression for the objective function does not exist, an alternative method is suggested by Rajeev and Satya. The method uses two consecutive phases to reveal the minimal durational route from the origins to the destinations. The first phase is willing to solve ${\displaystyle n\cdot m}$ time-minimizing problem, in each case using the remained ${\displaystyle n+m-2}$ intermediate nodes as transshipment points. This also leads to the minimal-durational transportation between all sources and destinations. During the second phase a standard time-minimizing problem needs to be solved. The solution of the time-minimizing transshipment problem is the joint solution outcome of these two phases.

Phase 1

Since costs are independent from the shipped amount, in each individual problem one can normalize the shipped quantity to 1. The problem now is simplified to an assignment problem from i to m+j. Let ${\displaystyle x_{r,s}^{\prime }=1}$ be 1 if the edge between nodes r and s is used during the optimization, and 0 otherwise. Now the goal is to determine all ${\displaystyle x_{r,s}^{\prime }}$ which minimize the objective function:

${\displaystyle T_{i,m+j}=\sum _{r=1}^{m+n}\sum _{s=1}^{m+n}{t}_{r,s}\cdot x_{r,s}^{\prime }}$,

such that

• ${\displaystyle \sum _{s=1}^{m+n}{x}_{r,s}^{\prime }=1}$
• ${\displaystyle \sum _{r=1}^{m+n}{x}_{r,s}^{\prime }=1}$
• ${\displaystyle x_{m+j,i}^{\prime }=1}$
• ${\displaystyle x_{r,s}^{\prime }=0,1}$.

Corollary

• ${\displaystyle x_{r,r}^{\prime }=1}$ and ${\displaystyle x_{m+j,i}^{\prime }=1}$ need to be excluded from the model; on the other hand, without the ${\displaystyle x_{m+j,i}^{\prime }=1}$ constraint the optimal path would consist only of ${\displaystyle x_{r,r}^{\prime }}$-type loops which obviously can not be a feasible solution.
• Instead of ${\displaystyle x_{m+j,i}^{\prime }=1}$, ${\displaystyle t_{m+j,i}=-M}$ can be written, where M is an arbitrarily large positive number. With that modification the formulation above is reduced to the form of a standard assignment problem, possible to solve with the Hungarian method.

Phase 2

During the second phase, a time minimization problem is solved with m origins and n destinations without transshipment. This phase differs in two main aspects from the original setup:

• Transportation is only possible from an origin to a destination
• Transportation time from i to m+j is the sum of durations coming from the optimal route calculated in Phase 1. Worthy to be denoted by ${\displaystyle t_{i,m+j}^{\prime }}$ in order to separate it from the times introduced during the first stage.

In mathematical form

The goal is to find ${\displaystyle x_{i,m+j}\ge 0}$ which minimize

${\displaystyle z=max\left\{t_{i,m+j}^{\prime }:x_{i,m+j}>0(i=1\dots m,j=1\dots n)\right\}}$,
such that

• ${\displaystyle \sum _{i=1}^m{x}_{i,m+j}=a_i}$
• ${\displaystyle \sum _{j=1}^n{x}_{i,m+j}=b_{m+j}}$
• ${\displaystyle \sum _{i=1}^m{a}_i=\sum _{j=1}^n{b}_{m+j}}$

This problem is easy to be solved with the method developed by Prakash. The set ${\displaystyle \left\{t_{i,m+j}^{\prime },i=1\dots m,j=1\dots n\right\}}$ needs to be partitioned into subgroups ${\displaystyle L_k,k=1\dots q}$, where each ${\displaystyle L_k}$ contain the ${\displaystyle t_{i,m+j}^{\prime }}$-s with the same value. The sequence ${\displaystyle L_k}$ is organized as ${\displaystyle L_1}$ contains the largest valued ${\displaystyle t_{i,m+j}^{\prime }}$'s ${\displaystyle L_2}$ the second largest and so on. Furthermore, ${\displaystyle M_k}$ positive priority factors are assigned to the subgroups ${\displaystyle \sum _{L_k}{x}_{i,m+j}}$, with the following rule:

${\displaystyle \alpha M_k-\beta M_{k+1}=\{\begin{array}{cc}-ve,& if\alpha <0\\ ve,& if\alpha >0\end{array}}$

for all ${\displaystyle \beta }$. With this notation the goal is to find all ${\displaystyle x_{i,m+j}}$ which minimize the goal function

${\displaystyle z_1=\sum _{k=1}^q{M}_k\sum _{L_k}{x}_{i,m+j}}$

such that

• ${\displaystyle \sum _{i=1}^m{x}_{i,m+j}=a_i}$
• ${\displaystyle \sum _{j=1}^n{x}_{i,m+j}=b_{m+j}}$
• ${\displaystyle \sum _{i=1}^m{a}_i=\sum _{j=1}^n{b}_{m+j}}$
• ${\displaystyle \alpha M_k-\beta M_{k+1}=\{\begin{array}{cc}-ve,& if\alpha <0\\ ve,& if\alpha >0\end{array}}$

Extension

Some authors such as Das et al (1999) and Malakooti (2013) have considered multi-objective Transshipment problem.