Capacitated two-stage time minimization transportation problem with restricted flow
Kaur, Prabhjot1 ; Verma, Vanita2 ; Dahiya, Kalpana1
1 University Institute Of Engineering and Technology, Panjab University, 160014 Chandigarh, India
2 Department of Mathematics, Panjab University, 160014 Chandigarh, India
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 447-467.

This paper discusses a capacitated time minimization transportation problem in which transportation operation takes place in two stages. In the first stage, due to some constraints, only a specified flow F 1 is transported from available sources to various destinations and in the second stage, a flow F 2 is transported depending upon the total demand of the destinations. The current problem is motivated by a production system of a steel industry where semi-finished jobs, initially located at various bins in its warehouse, are transported to various manufacturing facilities by transporters for the final processing and finishing. Due to some additional constraints, it is not possible to transport the number of semi-finished jobs equal to the exact number of final products to be manufactured, in one go. Therefore the transportation operation has to take place in two stages. Further, a capacity is associated with each bin-machine link which makes the current problem, a capacitated, two stage time minimization transportation problem with restricted flow. The objective is to minimize the sum of the transportation times for Stage-I and Stage-II. A polynomial time iterative algorithm is proposed that within each iteration, solves a restricted version of a related standard capacitated time minimization transportation problem and generates a pair of Stage-I and Stage-II times with Stage-II time strictly less than the Stage-II time of the previous iteration, whereas Stage-I time may increase. Out of these generated pairs, a pair with the minimum sum of transportation times of Stage-I and Stage-II is selected that gives the global optimal solution. Numerical illustration is included in the support of the theory.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016033
Classification : 90C26, 90C27
Mots-clés : Non-convex programming, combinatorial optimization, time transportation problem, capacitated transportation problem, flow constraint
Kaur, Prabhjot 1 ; Verma, Vanita 2 ; Dahiya, Kalpana 1

1 University Institute Of Engineering and Technology, Panjab University, 160014 Chandigarh, India
2 Department of Mathematics, Panjab University, 160014 Chandigarh, India 
@article{RO_2017__51_2_447_0,
     author = {Kaur, Prabhjot and Verma, Vanita and Dahiya, Kalpana},
     title = {Capacitated two-stage time minimization transportation problem with restricted flow},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {447--467},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {2},
     year = {2017},
     doi = {10.1051/ro/2016033},
     mrnumber = {3657434},
     zbl = {1365.90217},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2016033/}
}
TY  - JOUR
AU  - Kaur, Prabhjot
AU  - Verma, Vanita
AU  - Dahiya, Kalpana
TI  - Capacitated two-stage time minimization transportation problem with restricted flow
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 447
EP  - 467
VL  - 51
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2016033/
DO  - 10.1051/ro/2016033
LA  - en
ID  - RO_2017__51_2_447_0
ER  - 
%0 Journal Article
%A Kaur, Prabhjot
%A Verma, Vanita
%A Dahiya, Kalpana
%T Capacitated two-stage time minimization transportation problem with restricted flow
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 447-467
%V 51
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2016033/
%R 10.1051/ro/2016033
%G en
%F RO_2017__51_2_447_0
Kaur, Prabhjot; Verma, Vanita; Dahiya, Kalpana. Capacitated two-stage time minimization transportation problem with restricted flow. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 447-467. doi : 10.1051/ro/2016033. http://archive.numdam.org/articles/10.1051/ro/2016033/

R.K. Ahuja and J.B. Orlin, The scaling network simplex algorithm. Oper. Res. 40 (1992) 5–13. | DOI | MR | Zbl

G.M. Appa, The transportation problem and its variants. J. Oper. Res. Soc. 24 (1973) 79–99. | DOI | MR | Zbl

R.D. Armstrong and Z. Jin, A new strongly polynomial dual network simplex algorithm. Math. Program. 78 (1997) 131–148. | DOI | MR | Zbl

S. Arora and M.C. Puri, On lexicographic optimal solutions in transportation problem. Optimization 39 (1997) 383–403. | DOI | MR | Zbl

S. Arora and M.C. Puri, On a standard time transportation problem. ASOR Bulletin 20 (2001) 2–14.

M.E. Brigden, A Variant of Transportation problem in which the constraints are of Mixed Type. Oper. Res. Quarterly 25 (1974) 437–445. | DOI | MR | Zbl

S. Bansal and M.C. Puri, A min-max problem. ZOR 24 (1980) 191–200. | MR | Zbl

C. Berge, Theory of Graphs and its Applications. Dunod, Paris (1958).

H.L. Bhatia, K. Swarup and M.C. Puri, A procedure for time minimizing transportation problem. Indian J. Pure Appl. Math. 8 (1977) 920–929. | MR | Zbl

G.B. Dantzig, Linear Programming and Extensions. Princeton University Press, Princeton (1963). | MR | Zbl

G.B. Danzing and M. Thapa, Linear programming: Theory and extensions. Springer Verlag, New York, Berlin (1963). | MR

K. Dahiya and V. Verma, Capacitated transportation problem with bounds on rim conditions.Eur. J. Oper. Res. 178 (2007) 718–737. | DOI | MR | Zbl

P.L. Hammer, Time minimization transportation problem. Naval Res. Logist. Quart. 18 (1969) 345–357. | DOI | MR | Zbl

H.M. Wagner, On a class of capacitated transportation problem. Manage. Sci. 5 (1959) 304–318. | DOI | MR | Zbl

F.L. Hitchcock, The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941) 224–230. | DOI | JFM | MR | Zbl

A. Gani, Two stage fuzzy transportation problem.J. Phys. Sci. 10 (2006) 63–69.

R.S. Garfinkel and M.R. Rao, The bottleneck transportation problem. Naval Res. Logist. Quart. 18 (1971) 465–472. | DOI | MR | Zbl

P. Kaur and K. Dahiya, Two-Stage interval time minimization transportation problem with capacity constraints. Innovative Syst. Designs 6 (2015) 79–85.

S. Khanna, H.C. Bakshi and M.C. Puri, On controlling total flow in transportation problems. In: Scientific Management of Transport Systems. North Holland, The Neitherlands (1981) 293–301. | MR | Zbl

S. Khanna, H.C. Bakshi and M.C. Puri, Solving a Transportation problem with Mixed Constraints and a Specified Transportation Flow. Opsearch 20 (1983) 16–24. | MR | Zbl

D. Klingman and R. Russel, The Transportation problem with Mixed Constraints. Oper. Res. Quarterly 25 (1974) 447–455. | DOI | MR | Zbl

K.G. Murty, Linear and Combinatorial Programming. John Wiley and Sons, Inc., New York (1976). | MR | Zbl

J.B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program. 78 (1997) 109–129. | DOI | MR | Zbl

S. Parkash, On minimizing the duration of transportation. Proc. Indian Acad. Sci. 91 (1982) 53–57. | DOI | Zbl

P. Pandian and G. Natrajan, Solving two stage transportation problem.Commun. Comput. Inf. Sci. 140 (2011) 159–165. | Zbl

V. Sharma, K. Dahiya and V. Verma, A note on two stage interval time minimization transportation problem. ASOR Bulletin 27 (2008) 12–18.

A. Sharma, V. Verma, P. Kaur and K. Dahiya, An iterative algorithm for two level hierarchical time minimization transportation problem. Eur. J. Oper. Res. 246 (2015) 700–707. | DOI | MR | Zbl

V. Sharma, K. Dahiya and V. Verma, Capacitated two stage transportation problem. Asia Pacific J. Oper. Res. 27 (2010) 457–476. | DOI | MR | Zbl

V.J. Sudhakar, V.N. Kumar, A different approach for solving two stage fuzzy transportation problem.Int. J. Contemp. Math. Sci. 6 (2011) 517–526. | MR | Zbl

W. Szwarc, Some remarks on time transportation problem. Naval Res. Logist. Quart. 18 (1971) 465–472. | DOI | MR | Zbl

Cité par Sources :