Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Transshipment problem
open-in-new
<h2 id="overview">Overview</h2> <p>Transshipment or Transhipment is the <a href="/facts/Shipment/0wYezNsU">shipment</a> of <a href="/facts/Cargo/0aDk22Yl">goods</a> or <a href="/facts/Intermodal_container/797lTKzR">containers</a> to an intermediate destination, and then from there to yet another destination. One possible reason is to change the <a href="/facts/Means_of_transport/FATJmIdV">means of transport</a> during the journey (for example from <a href="/facts/Ship_transport/rB1EQAfm">ship transport</a> to <a href="/facts/Road_transport/z2IPvusI">road transport</a>), known as <a href="/facts/Transloading/tysQ3bHE">transloading</a>. Another reason is to combine small shipments into a large shipment (consolidation), dividing the large shipment at the other end (deconsolidation). Transshipment usually takes place in <a href="/facts/Transport_hub/LthX69gf">transport hubs</a>. Much international transshipment also takes place in designated <a href="/facts/Customs_area/ngScQKAz">customs areas</a>, thus avoiding the need for customs checks or duties, otherwise a major hindrance for efficient transport. </p> <h2 id="formulation-of-the-problem">Formulation of the problem</h2> <p>A few initial assumptions are required in order to formulate the transshipment problem completely: </p> <ul><li>The system consists of <i>m</i> origins and <i>n</i> destinations, with the following indexing respectively: i = 1 , … , m {\displaystyle i=1,\ldots ,m} , j = 1 , … , n {\displaystyle j=1,\ldots ,n} </li> <li>One uniform good exists which needs to be shipped</li> <li>The required amount of good at the destinations equals the produced quantity available at the origins</li> <li>Transportation simultaneously starts at the origins and is possible from any node to any other (also to an origin and from a destination)</li> <li>Transportation costs are independent of the shipped amount</li> <li>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)<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a></li></ul> <h2 id="notations">Notations</h2> <ul><li> t r , s {\displaystyle t_{r,s}} : time of transportation from node <i>r</i> to node <i>s</i></li> <li> a i {\displaystyle a_{i}} : goods available at node <i>i</i></li> <li> b m + j {\displaystyle b_{m+j}} : demand for the good at node <i>(m+j)</i></li> <li> x r , s {\displaystyle x_{r,s}} : actual amount transported from node <i>r</i> to node <i>s</i></li></ul> <h2 id="mathematical-formulation-of-the-problem">Mathematical formulation of the problem</h2> <p>The goal is to minimize ∑ i = 1 m ∑ j = 1 n t i , j x i , j {\displaystyle \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}t_{i,j}x_{i,j}} subject to: </p> <ul><li> x r , s ≥ 0 {\displaystyle x_{r,s}\geq 0} ; ∀ r = 1 … m {\displaystyle \forall r=1\ldots m} , s = 1 … n {\displaystyle s=1\ldots n} </li> <li> ∑ s = 1 m + n x i , s − ∑ r = 1 m + n x r , i = a i {\displaystyle \sum _{s=1}^{m+n}{x_{i,s}}-\sum _{r=1}^{m+n}{x_{r,i}}=a_{i}} ; ∀ i = 1 … m {\displaystyle \forall i=1\ldots m} </li> <li> ∑ r = 1 m + n x r , m + j − ∑ s = 1 m + n x m + j , s = b m + j {\displaystyle \sum _{r=1}^{m+n}{x_{r,m+j}}-\sum _{s=1}^{m+n}{x_{m+j,s}}=b_{m+j}} ; ∀ j = 1 … n {\displaystyle \forall j=1\ldots n} </li> <li> ∑ i = 1 m a i = ∑ j = 1 n b m + j {\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}} </li></ul> <h2 id="solution">Solution</h2> <p>Since in most cases an explicit expression for the objective function does not exist, an alternative method is suggested by Rajeev and <a href="/facts/Satya_Prakash_(physicist)/v18aPpKX">Satya</a>. 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 n ⋅ m {\displaystyle n\cdot m} time-minimizing problem, in each case using the remained n + m − 2 {\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. </p> <h3>Phase 1</h3> <p>Since costs are independent from the shipped amount, in each individual problem one can normalize the shipped quantity to <i>1</i>. The problem now is simplified to an assignment problem from <i>i</i> to <i>m+j</i>. Let x r , s ′ = 1 {\displaystyle x'_{r,s}=1} be <i>1</i> if the edge between nodes <i>r</i> and <i>s</i> is used during the optimization, and <i>0</i> otherwise. Now the goal is to determine all x r , s ′ {\displaystyle x'_{r,s}} which minimize the objective function: </p><p> T i , m + j = ∑ r = 1 m + n ∑ s = 1 m + n t r , s ⋅ x r , s ′ {\displaystyle T_{i,m+j}=\sum _{r=1}^{m+n}\sum _{s=1}^{m+n}{t_{r,s}\cdot x'_{r,s}}} , </p><p>such that </p> <ul><li> ∑ s = 1 m + n x r , s ′ = 1 {\displaystyle \sum _{s=1}^{m+n}{x'_{r,s}}=1} </li> <li> ∑ r = 1 m + n x r , s ′ = 1 {\displaystyle \sum _{r=1}^{m+n}{x'_{r,s}}=1} </li> <li> x m + j , i ′ = 1 {\displaystyle x'_{m+j,i}=1} </li> <li> x r , s ′ = 0 , 1 {\displaystyle x'_{r,s}=0,1} .</li></ul> <h4>Corollary</h4> <ul><li> x r , r ′ = 1 {\displaystyle x'_{r,r}=1} and x m + j , i ′ = 1 {\displaystyle x'_{m+j,i}=1} need to be excluded from the model; on the other hand, without the x m + j , i ′ = 1 {\displaystyle x'_{m+j,i}=1} constraint the optimal path would consist only of x r , r ′ {\displaystyle x'_{r,r}} -type loops which obviously can not be a feasible solution.</li> <li>Instead of x m + j , i ′ = 1 {\displaystyle x'_{m+j,i}=1} , t m + j , i = − M {\displaystyle t_{m+j,i}=-M} can be written, where <i>M</i> is an arbitrarily large positive number. With that modification the formulation above is reduced to the form of a <a href="/facts/Assignment_problem/dIMpM0aW">standard assignment problem</a>, possible to solve with the <a href="/facts/Hungarian_method/rRCJebc1">Hungarian method</a>.</li></ul> <h3>Phase 2</h3> <p>During the second phase, a time minimization problem is solved with <i>m</i> origins and <i>n</i> destinations without transshipment. This phase differs in two main aspects from the original setup: </p> <ul><li>Transportation is only possible from an origin to a destination</li> <li>Transportation time from <i>i</i> to <i>m+j</i> is the sum of durations coming from the optimal route calculated in Phase 1. Worthy to be denoted by t i , m + j ′ {\displaystyle t'_{i,m+j}} in order to separate it from the times introduced during the first stage.</li></ul> <h4>In mathematical form</h4> <p>The goal is to find x i , m + j ≥ 0 {\displaystyle x_{i,m+j}\geq 0} which minimize </p><p> z = m a x { t i , m + j ′ : x i , m + j > 0 ( i = 1 … m , j = 1 … n ) } {\displaystyle z=max\left\{t'_{i,m+j}:x_{i,m+j}>0\;\;(i=1\ldots m,\;j=1\ldots n)\right\}} , such that </p> <ul><li> ∑ i = 1 m x i , m + j = a i {\displaystyle \sum _{i=1}^{m}{x_{i,m+j}}=a_{i}} </li> <li> ∑ j = 1 n x i , m + j = b m + j {\displaystyle \sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}} </li> <li> ∑ i = 1 m a i = ∑ j = 1 n b m + j {\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}} </li></ul> <p>This problem is easy to be solved with the method developed by <a href="/facts/Satya_Prakash_(physicist)/v18aPpKX">Prakash</a>. The set { t i , m + j ′ , i = 1 … m , j = 1 … n } {\displaystyle \left\{t'_{i,m+j},i=1\ldots m,\;j=1\ldots n\right\}} needs to be partitioned into subgroups L k , k = 1 … q {\displaystyle L_{k},k=1\ldots q} , where each L k {\displaystyle L_{k}} contain the t i , m + j ′ {\displaystyle t'_{i,m+j}} -s with the same value. The sequence L k {\displaystyle L_{k}} is organized as L 1 {\displaystyle L_{1}} contains the largest valued t i , m + j ′ {\displaystyle t'_{i,m+j}} 's L 2 {\displaystyle L_{2}} the second largest and so on. Furthermore, M k {\displaystyle M_{k}} positive priority factors are assigned to the subgroups ∑ L k x i , m + j {\displaystyle \sum _{L_{k}}{x_{i,m+j}}} , with the following rule: </p><p> α M k − β M k + 1 = { − v e , i f α < 0 v e , i f α > 0 {\displaystyle \alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.} </p><p>for all β {\displaystyle \beta } . With this notation the goal is to find all x i , m + j {\displaystyle x_{i,m+j}} which minimize the goal function </p><p> z 1 = ∑ k = 1 q M k ∑ L k x i , m + j {\displaystyle z_{1}=\sum _{k=1}^{q}{M_{k}}\sum _{L_{k}}{x_{i,m+j}}} </p><p>such that </p> <ul><li> ∑ i = 1 m x i , m + j = a i {\displaystyle \sum _{i=1}^{m}{x_{i,m+j}}=a_{i}} </li> <li> ∑ j = 1 n x i , m + j = b m + j {\displaystyle \sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}} </li> <li> ∑ i = 1 m a i = ∑ j = 1 n b m + j {\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}} </li> <li> α M k − β M k + 1 = { − v e , i f α < 0 v e , i f α > 0 {\displaystyle \alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.} </li></ul> <h2 id="extension">Extension</h2> <p>Some authors such as Das et al (1999) and Malakooti (2013) have considered multi-objective Transshipment problem. </p> <ul><li>R.J Aguilar, Systems Analysis and Design. Prentice Hall, Inc. Englewood Cliffs, New Jersey (1973) pp. 209–220</li> <li>H. L. Bhatia, K. Swarup, M. C. Puri, Indian J. pure appl. Math. 8 (1977) 920-929</li> <li>R. S. Gartinkel, M. R. Rao, Nav. Res. Log. Quart. 18 (1971) 465-472</li> <li>G. Hadley, Linear Programming, Addison-Wesley Publishing Company, (1962) pp. 368–373</li> <li>P. L. Hammer, Nav. Res. Log. Quart. 16 (1969) 345-357</li> <li>P. L. Hammer, Nav. Res. Log. Quart. 18 (1971) 487-490</li> <li>A.J.Hughes, D.E.Grawog, Linear Programming: An Emphasis On Decision Making, Addison-Wesley Publishing Company, pp. 300–312</li> <li>H.W.Kuhn, Nav. Res. Log. Quart. 2 (1955) 83-97</li> <li>A.Orden, Management Sci, 2 (1956) 276-285</li> <li>S.Parkash, Proc. Indian Acad. Sci. (Math. Sci.) 91 (1982) 53-57</li> <li>C.S. Ramakrishnan, OPSEARCH 14 (1977) 207-209</li> <li>C.R.Seshan, V.G.Tikekar, Proc. Indian Acad. Sci. (Math. Sci.) 89 (1980) 101-102</li> <li>J.K.Sharma, K.Swarup, Proc. Indian Acad. Sci. (Math. Sci.) 86 (1977) 513-518</li> <li>W.Szwarc, Nav. Res. Log. Quart. 18 (1971) 473-485</li> <li>Malakooti, B. (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons.</li> <li>Das, S. K., A. Goswami, and S. S. Alam. “Multiobjective Transportation Problem with Interval Cost, Source and Destination Parameters.” European Journal of Operational Research, Vol. 117, No. 1, 1999, pp. 100–112</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Transshipment Problem and Its Variants: A Review". ResearchGate. Retrieved 2020-11-02. <a href="https://www.researchgate.net/publication/317012808" target="_blank">https://www.researchgate.net/publication/317012808</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>