Some aspects on solving transportation problem
DOI:
https://doi.org/10.2298/YJOR190615024DKeywords:
Transportation Problem, NorthWest Corner Solution, Weighted König-Egerváry theorem, Assignment Problem, Weighted Hungarian Method, Sample SurveyAbstract
In this paper, we consider a class of transportation problems which arises in sample surveys and other areas of statistics. The associated cost matrices to these transportation problems are of special structure. We observe that the optimality of North West corner solution holds for the problem where cost component is replaced by a convex function. We revisit assignment problem and present a weighted version of König-Egerváry theorem. Finally, we propose weighted Hungarian method to solve the transportation problem.References
Adhikary, K., Roy, J., and Kar, S., "Newsboy problem with birandom demand," Decision Making: Applications in Management and Engineering, 2 (1) (2019) 1-12.
Anholcer, M., "Stochastic generalized transportation problem with discrete distribution of demand," Operations Research and Decisions, 23 (4) (2013) 9-19.
Appa, G., "The transportation problem and its variants," Journal of the Operational Research Society, 24 (1) (1973) 79-99.
Arabeyre, J.P., Fearnley, J., Steiger, F.C., and Teather, W., "The airline crew scheduling problem: A survey," Transportation Science, 3 (2) (1969) 140-163.
Aragon, J., and Pathak, P.K., "An algorithm for optimal integration of two surveys," Sankhya: The Indian Journal of Statistics, Series B, 52 (2) (1990) 198-203.
Archetti, C., Bertazzi, L., Laporte, G., and Speranza, M.G., "A branch-and-cut algorithm for a vendor-managed inventory-routing problem," Transportation Science, 41 (3) (2007) 382-391.
Arthanari, T.S., "Optimization in Statistics-Recent Trends," Compstat, Proceedings in Computational Statistics 9th Symposium, Dubrovnik, Yugoslavia, 1990, 171-176.
Barma, P.S., Dutta, J., and Mukherjee, A., "A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem," Decision Making: Applications in Management and Engineering, 2 (2) (2019) 112-125.
Burkard, R.E., Klinz, B., and Rudolf, R., "Perspectives of Monge properties in optimization," Discrete Applied Mathematics, 70 (2) (1996) 95-161.
Causey, B.D., Cox, L.H., and Ernst, L.R., "Applications of transportation theory to statistical problems," Journal of the American Statistical Association, 80 (392) (1985) 903-909.
Cechlarova, K., "Persistency in the assignment and transportation problems," Mathematical Methods of Operations Research, 47 (2) (1998) 243-254.
Celik, M., Er, I.D., and Topcu, Y.I., "Computer-based systematic execution model on human resources management in maritime transportation industry: The case of master selection for embarking on board merchant ships," Expert Systems with Applications, 36 (2) (2009) 1048-1060.
Dantzig, G.B., and Fulkerson, D.R., "Minimizing the number of tankers to meet a fixed schedule," Naval Research Logistics Quarterly, 1 (3) (1954) 217-222.
Daz-Parra, O., Ruiz-Vanoye, J.A., Bernabe, L.B., Fuentes-Penna, A., and Barrera-Camara, R.A., "A survey of transportation problems," Journal of Applied Mathematics, Article ID 848129, 2014.
Daz-Parra, O., Ruiz-Vanoye, J.A., Penna, A.F., Loranca, B.B., Perez-Ortega, J., Barrera-Camara, R.A., Velez-Daz, D., and Perez-Olguin, N.B., "Oil Platform Transport Problem (OPTP) is NP-hard," International Journal of Combinatorial Optimization Problems and Informatics, 8 (3) (2017) 219.
Ebrahimi, H., and Tadic, M., "Optimization of dangerous goods transport in urban zone," Decision Making: Applications in Management and Engineering, 1 (2) (2018) 131-152.
Egervary, E., "On combinatorial properties of matrices," Matrizok kombinatorius tulajdonsagairol, Matematiaki es Fizikai Lapok, 38 (1931) 16-28.
Emden-Weinert, T., and Proksch, M., "Best practice simulated annealing for the airline crew scheduling problem," Journal of Heuristics, 5 (4) (1999) 419-436.
Evans, J.R., "The factored transportation problem," Management Science, 30 (8) (1984) 1021-1024.
Fagerholt, K., "Optimal fleet design in a ship routing problem," International Transactions in Operational Research, 6 (5) (1999) 453-464.
Fiala, T.M.T., and Pulleyblank, W.R., "Precedence constrained routing and helicopter scheduling: heuristic design," Interfaces, 22 (3) (1992) 100-111.
Ford, L.R., and Fulkerson, D.R., "Flows in Networks," Princeton University Press, USA, 1962.
Gendreau, M., Laporte, G., and Seguin, R., "A tabu search heuristic for the vehicle routing problem with stochastic demands and customers," Operations Research, 44 (3) (1996) 469-477.
Ghanbari, Reza and Mahdavi-Amiri, Nezam, "Solving bus terminal location problems using evolutionary algorithms," Applied Soft Computing, 11 (1) (2011) 991-999.
Goldstein, D., Shehab, T., Casse, J., and Lin, H.C., "On the formulation and solution of the convoy routing problem," Transportation Research Part E: Logistics and Transportation Review, 46 (4) (2010) 520-533.
Goossens, D., and Spieksma, F.C.R., "The transportation problem with exclusionary side constraints," 4OR, 7 (1) (2009) 51-60.
Helme, M.P., "Reducing air traffic delay in a space-time network," 1992 IEEE International Conference on Systems, Man, and Cybernetics, IEEE, Chicago, IL, USA (1992) 236-242.
Homan, A.J., "On simple linear programming problems," Selected Papers of Alan J. Homan: With Commentary, pp. 317-327, World Scientific, 2003.
Kasana, H.S., Kumar, K.D., "An efficient algorithm for multiobjective transportation problems," Asia-Pacific Journal of Operational Research, 17 (1) (2000) 27-40.
Homan, K.L., and Padberg, M., "Solving airline crew scheduling problems by branch-and-cut," Management Science, 39 (6) (1993) 657-682.
Konig, D., "Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre," Mathematische Annalen, 77 (1916) 453-465.
Kim, B.I., Kim, S., and Park, J., "A school bus scheduling problem," European Journal of Operational Research, 218 (2) (2012) 577-585.
Kuhn, H.W., "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, 2 (1-2) (1955) 83-97.
Kuhn, H.W., "Variants of the Hungarian method for assignment problems," Naval Research Logistics Quarterly, 3 (4) (1956) 253-258.
Lawler, E.L., "Combinatorial optimization: networks and matroids," Courier Corporation, Dover Publications Inc., Mineola, New York, 1976.
Liu, G.S., and Zhang, J.Z., "Decision making of transportation plan, a bilevel transportation problem approach," Journal of Industrial & Management Optimization, 1 (3) (2005) 305-314.
Liu, S.C., and Lee, S.B., "A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration," The International Journal of Advanced Manufacturing Technology, 22 (11-12) (2003) 941-950.
Matei, A., and Tille, Y., "Maximal and minimal sample coordination," Sankhya: The Indian Journal of Statistics, 3 (4) (2005) 590-612.
Michalewicz, Z., Vignaux, G.A., and Hobbs, M., "A nonstandard genetic algorithm for the nonlinear transportation problem," ORSA Journal on Computing, 3 (4) (1991) 307-316.PA, John Wiley & Sons, London, 2008.
Mitra, S.K., and Mohan, S.R., "On the optimality of North West Corner solution in some applications of the transportation problem," Technical Report No. 8801, Indian Statistical Institute, Delhi Centre, 1988.
Mula, J., Peidro, D., Daz-Madronero, M., and Vicens, E., "Mathematical programming models for supply chain production and transport planning," European Journal of Operational Research, 204 (3) (2010) 377-390.
Newton, R.M., and Thomas, W.H., "Bus routing in a multi-school system," Computers & Operations Research, 1 (2) (1974) 213-222.
Østebø, B.O., Hvattum, L.M., and Fagerholt, K., "Optimization of stowage plans for RoRo ships," Computers & Operations Research, 38 (10) (2011) 1425-1434.
Pamučar, D., and Ćirović, G., "Vehicle route selection with an adaptive neuro fuzzy inference system in uncertainty conditions," Decision Making: Applications in Management and Engineering, 1 (1) (2018) 13-37.
Popović, D., Vidović, M., and Radivojević, G., "Variable neighborhood search heuristic for the inventory routing problem in fuel delivery," Expert Systems with Applications, 39 (18) (2012) 13390-13398.
Raj, D., "On the method of overlapping maps in sample surveys," Sankhya: The Indian Journal of Statistics (1933-1960), 17 (1) (1956) 89-98.
Roy, A., Manna, A., and Maity, S., "A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique," Decision Making: Applications in Management and Engineering, (2019).
Scheuerer, S., "A tabu search heuristic for the truck and trailer routing problem," Computers & Operations Research, 33 (4) (2006) 894-909.
Souriau, W., Vansteenwegen, P., Berghe, G.V., and Oudheusden, D.V., "A greedy randomized adaptive search procedure for the team orienteering problem," EU/Meeting, Troyes, France, 2008.
Speranza, M.G., "Trends in transportation and logistics," European Journal of Operational Research, 264 (3) (2018) 830-836.
Szwarc, W., "Instant transportation solutions," Naval Research Logistics Quarterly, 22 (3) (1975) 427-440.
Toth, P., and Vigo, D., "The vehicle routing problem," SIAM Monographs on Discrete Mathematics and Applications, University City Science Center, Philadelphia, 2002.
Vignaux, G.A., and Michalewicz, Z., "A genetic algorithm for the linear transportation problem," IEEE Transactions on Systems, Man, and Cybernetics, 21 (2) (1991) 445-452.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
