Transshipment problem

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}=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}}$ 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}}}$,

such that

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

• ${\displaystyle x'_{r,r}=1}$ and ${\displaystyle x'_{m+j,i}=1}$ need to be excluded from the model; on the other hand, without the ${\displaystyle x'_{m+j,i}=1}$ constraint the optimal path would consist only of ${\displaystyle x'_{r,r}}$-type loops which obviously can not be a feasible solution.
• Instead of ${\displaystyle x'_{m+j,i}=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.

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}}$ in order to separate it from the times introduced during the first stage.

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

${\displaystyle z=max\left\{t'_{i,m+j}:x_{i,m+j}>0\;\;(i=1\ldots m,\;j=1\ldots 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},i=1\ldots m,\;j=1\ldots n\right\}}$ needs to be partitioned into subgroups ${\displaystyle L_{k},k=1\ldots q}$, where each ${\displaystyle L_{k}}$ contain the ${\displaystyle t'_{i,m+j}}$-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}}$'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}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.}$

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}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.}$