An efficient algorithm for two-stage capacitated time minimization transportation problem with restricted flow. (English) Zbl 07902486
Summary: This paper discusses a two-stage capacitated time minimization transportation problem with the restricted flow (TSCTMTP-F) in which the transportation takes place in two stages and only a specified amount of commodity is transported in both stages. The total amount \(F_1\) is transported during Stage-I and \(F_2\) during Stage-II, and the objective is to minimize the sum of the transportation times for Stage-I and Stage-II. In 2017, Kaur et al. [RAIRO-Oper. Res. 51 (2017) 1169–1184] studied this problem and developed a polynomially bounded iterative algorithm (Algorithm-A) to solve TSCTMTP-F. However, their proposed algorithm has some flaws and may not always yield an optimal solution to the problem TSCTMTP-F. An improved iterative algorithm (Algorithm-C) is proposed in this paper that guarantees an optimal solution to the problem. Various theoretical results prove the convergence and efficiency of Algorithm-C to obtain an optimal solution to the problem TSCTMTP-F. Numerical problems are included in the support of theory along with a counter-example for which Algorithm-A fails to obtain its optimal solution. Computational experiments on a variety of test problems have been carried out to validate the convergence and efficiency of Algorithm-C.
References:
| [1] | R.K. Ahuja, Algorithms for the minimax transportation problem. Nav. Res. Logist. Q. 33 (1986) 725-739. · Zbl 0624.90066 |
| [2] | E. Ammar and E. Youness, Study on multiobjective transportation problem with fuzzy numbers. Appl. Math. Comput. 166 (2005) 241-253. · Zbl 1099.90049 |
| [3] | S. Bansal and M.C. Puri, A min max problem. Math. Oper. Res. 24 (1977) 191-200. · Zbl 0453.90058 |
| [4] | D. Barman, A. Kuiri and B. Das, A two-vehicle two-stage solid transportation problem with bi-fuzzy coefficients through genetic algorithm. Int. J. Math. Oper. Res. 18 (2021) 444-464. · Zbl 1482.90034 |
| [5] | J. Behnamian, S.M.T. Fatemi Ghomi, F. Jolai and O. Amirtaheri, Realistic two-stage flow shop batch scheduling problems with transportation capacity and times. Appl. Math. Model. 36 (2012) 723-735. · Zbl 1236.90049 |
| [6] | A. Biswas, A.A. Shaikh and S.T.A. Niaki, Multi-objective non-linear fixed charge transportation problem with multiple modes of transportation in crisp and interval environments. Appl. Soft. Comput. 80 (2019) 628-649. |
| [7] | G.A. Bula, H.M. Afsar, F.A. González, C. Prodhon and N. Velasco, Bi-objective vehicle routing problem for haz-ardous materials transportation. J. Clean. Prod. 206 (2019) 976-986. |
| [8] | H.I. Calvete, C. Gale, J.A. Iranzo and P. Toth, A metaheuristic for the two-stage fixed-charge transportation problem. Comput. Oper. Res. 95 (2018) 113-122. · Zbl 1458.90068 |
| [9] | D. Chakraborty, D.K. Jana and T.K. Roy, Multi-objective multi-item solid transportation problem with fuzzy inequality constraints. J. Inequal. Appl. 2014 (2014) 1-21. · Zbl 1379.90033 |
| [10] | P. Charnsethikul and S. Svetasreni, The constrained bottleneck transportation problem. J. Math. Stat. 3 (2007) 24-27. · Zbl 1183.90055 |
| [11] | N. Chikhi, M. Abbas, R. Benmansour, A. Bekrar and S. Hanafi, A two-stage flow shop scheduling problem with transportation considerations. 4OR 13 (2015) 381-402. · Zbl 1328.90046 |
| [12] | O. Cosma, P.C. Pop and C.P. Sitar, An efficient iterated local search heuristic algorithm for the two-stage fixed-charge transportation problem. Carpathian J. Math. 35 (2019) 153-164. · Zbl 1463.90010 |
| [13] | O. Cosma, P.C. Pop and D. Danciulescu, A parallel algorithm for solving a two-stage fixed-charge transportation problem. Informatica 31 (2020) 681-706. |
| [14] | K. Dahiya and V. Verma, Capacitated transportation problem with bounds on rim conditions. Eur. J. Oper. Res. 178 (2007) 718-737. · Zbl 1163.90361 |
| [15] | G.B. Dantzig, Linear Programming and Extensions. RAND Corporation, Santa Monica, CA (1963). · Zbl 0108.33103 |
| [16] | G. Dogaru and C. Nistor, Considerations on time minimization in transportation problem with impurities. Sci. Study Res. 19 (2009) 213-219. · Zbl 1240.90043 |
| [17] | W. Grabowski, Transportation problem with minimization of time. Prz. Stat. 11 (1964) 333-359. |
| [18] | K. Gupta and R. Arora, Optimum cost-time trade-off pairs in a fractional plus fractional capacitated transportation problem with restricted flow. Invest. Oper. 41 (2020) 27-41. |
| [19] | K. Gupta and S.R. Arora, Bottleneck capacitated transportation problem with bounds on rim conditions. Opsearch 50 (2013) 491-503. · Zbl 1353.90023 |
| [20] | S. Gupta, I. Ali and A. Ahmed, Efficient fuzzy goal programming model for multi-objective production distribution problem. Int. J. Appl. Comput. Math. 76 (2018) 1-19. · Zbl 1404.90029 |
| [21] | P.L. Hammer, Time-minimizing transportation problems. Nav. Res. Logist. Q. 16 (1969) 345-357. · Zbl 0197.45604 |
| [22] | Y. Hinojosa, J. Puerto and F. Saldanha-da-Gama, A two-stage stochastic transportation problem with fixed handling costs and a priori selection of the distribution channels. TOP 22 (2014) 1123-1147. · Zbl 1336.90018 |
| [23] | M. Jain and P.K. Saksena, Time minimizing transportation problem with fractional bottleneck objective function. Yugosl. J. Oper. 22 (2012) 115-129. · Zbl 1289.90137 |
| [24] | E. Jain, K. Dahiya and V. Verma, Three-phase time minimization transportation problem. Eng. Optim. 53 (2021) 461-473. · Zbl 1523.90033 |
| [25] | D. Kannan, K. Govindan and H. Soleimani, Artificial immune system and sheep flock algorithms for two-stage fixed-charge transportation problem. Optimization 63 (2014) 1465-1479. · Zbl 1301.65046 |
| [26] | P. Kaur, A. Sharma, V. Verma and K. Dahiya, An alternate approach to solve two-level hierarchical time minimiza-tion transportation problem. 4OR 20 (2012) 23-61. |
| [27] | P. Kaur, V. Verma and K. Dahiya, Capacitated two-stage time minimization transportation problem with restricted flow. RAIRO-Oper. Res. 51 (2017) 1169-1184. |
| [28] | S. Khanna, H.C. Bakhsi and S.R. Arora, Time minimization transportation problem with restricted flow. Cahiers du CERO 25 (1983) 65-74. · Zbl 0505.90048 |
| [29] | A. Khurana and S.R. Arora, The sum of a linear and a linear fractional transportation problem with restricted and enhanced flow. J. Interdiscip. Math. 9 (2006) 373-383. · Zbl 1149.90103 |
| [30] | A. Khurana, D. Thirwani and S.R. Arora, An algorithm for solving fixed charge bi-criterion indefinite quadratic transportation problem with restricted flow. Int. J. Optim.: Theory Methods App. 1 (2009) 367-380. · Zbl 1190.90027 |
| [31] | J.B. Orlin, A polynomial time primal network simplex algorithm for minimum cut flows. Math. Program. 78 (1997) 109-129. · Zbl 0888.90058 |
| [32] | P. Pandian and G. Natarajan, Solving two stage transportation problems, in International Conference on Logic, Information, Control and Computation, edited by P. Balasubramaniam. Vol. 140. Springer Berlin Heidelberg, Berlin, Heidelberg (2011) 159-165. · Zbl 1211.90032 |
| [33] | J.A. Paul and M. Zhang, Supply location and transportation planning for hurricanes: a two-stage stochastic pro-gramming framework. Eur. J. Oper. Res. 274 (2019) 108-125. · Zbl 1430.90121 |
| [34] | G.V. Sarma, The transportation problem with objective of simultaneous minimization of total transportation cost and transportation time to each destination. Opsearch 35 (1998) 238-260. · Zbl 1141.90484 |
| [35] | D. Sengupta and U.K. Bera, Reduction of type-2 lognormal uncertain variable and its application to a two-stage solid transportation problem, in Operations Research and Optimization: FOTA 2016. Springer Proceedings in Math-ematics & Statistics, edited by S. Kar, U. Maulik and X. Li. Vol. 225. Springer Singapore (2018) 333-345. · Zbl 1429.90038 |
| [36] | V. Sharma, K. Dahiya and V. Verma, A note on a two-stage interval time minimization transportation problem. ASOR Bull. 27 (2008) 12-18. |
| [37] | V. Sharma, K. Dahiya and V. Verma, Capacitated two-stage time minimization transportation problem. Asia-Pac. J. Oper. Res. 27 (2010) 457-476. · Zbl 1197.90079 |
| [38] | A. Sharma, V. Verma, P. Kaur and K. Dahiya, An iterative algorithm for two-level hierarchical time minimization transportation problem. Euro. J. Oper. Res. 246 (2015) 700-707. · Zbl 1346.90600 |
| [39] | P. Singh, Multiple-objective fractional costs transportation problem with bottleneck time and impurities. J. Inf. Optim. Sci. 36 (2015) 421-449. |
| [40] | P. Singh and P.K. Saxena, Multiple objective cost-bottleneck time transportation problem with additional impurity constraints. Asia-Pac. J. Oper. Res. 17 (2000) 181-197. · Zbl 1042.90589 |
| [41] | S. Sungeeta, T. Renu and S. Deepali, A review on fuzzy and stochastic extensions of the multi-index transportation problem. Yugosl. J. Oper. Res. 27 (2017) 3-29. · Zbl 1474.90064 |
| [42] | L. Tang and H. Gong, A hybrid two-stage transportation and batch scheduling problem. Appl. Math. Model. 32 (2008) 2467-2479. · Zbl 1167.90520 |
| [43] | D. Thirwani, S.R. Arora and S. Khanna, An algorithm for solving fixed charge bi-criterion transportation problem with restricted flow. Optimization 40 (1997) 193-206. · Zbl 0880.90038 |
| [44] | J.M. Vinotha, W. Ritha and A. Abraham, Total time minimization of fuzzy transportation problem. J. Intell. Fuzzy Syst. 23 (2012) 93-99. · Zbl 1269.90017 |
| [45] | F. Xie and Z. Li, An iterative solution technique for capacitated two-stage time minimization transportation problem. 4OR 20 (2022) 637-684. · Zbl 1502.90030 |
| [46] | F. Xie, M.M. Butt and Z. Li, A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem. Comput. Oper. Res. 86 (2017) 124-139. · Zbl 1391.90104 |
| [47] | H. Zhu, A two stage scheduling with transportation and batching. Inf. Process. Lett. 112 (2012) 728-731. · Zbl 1248.68227 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
