Kybernetika 61 no. 2, 141-167, 2025

Hybrid algorithms for fixed charge transportation problem

Nermin KartliDOI: 10.14736/kyb-2025-2-0141

Abstract:

In this paper, we consider the fixed-cost transportation problem. This problem is known to be NP-hard. Therefore, various heuristic and metaheuristic approaches have been proposed to find an approximate optimal solution. In this paper, we propose three hybrid algorithms that combine the ideas of metaheuristic and heuristic approaches in different ways. Two of the proposed algorithms consist of the sequential implementation of metaheuristic and heuristic algorithms, while the third one is a full hybrid algorithm designed by completely intertwining these two approaches. Experimental results on medium-size problems show that our proposed full hybrid algorithm provides approximately a 5\% improvement over metaheuristic algorithms and a 4\% improvement over heuristic algorithms. In addition, the improvement ratio increases as the size of the problem increases.

Keywords:

transportation problem, fixed charge transportation problem, genetic algorithms, metaheuristic algorithms

Classification:

90C08, 90B06, 90C59, 90C10

paper.pdf

References:

  1. V. Adlakha and K. Kowalski: On the fixed-charge transportation problem. Omega 27 (1999), 3, 381-388.   DOI:10.1016/S0305-0483(98)00064-4
  2. V. Adlakha and K. Kowalski: A simple heuristic for solving small fixed-charge transportation problems. Omega 31 (2003), 3, 205-211.   DOI:10.1016/S0305-0483(03)00025-2
  3. V. Adlakha, K. Kowalski and R. R. Vemuganti: Heuristic algorithms for the fixed-charge transportation problem. Opsearch 43 (2006), 132-151.   DOI:10.1007/BF03398770
  4. V. Adlakha, K. Kowalski and B. Lev: A branching method for the fixed charge transportation problem. Omega 38 (2010), 5, 393-397.   DOI:10.1016/j.omega.2009.10.005
  5. S. E. Amrahov, Y. Ar, B. Tugrul, B. E. Akay and N. Kartli: A new approach to Mergesort algorithm: Divide smart and conquer. Future Generation Computer Systems 157 (2024), 330-343.   DOI:10.1016/j.future.2024.03.049
  6. M. L. Balinski: Fixed-cost transportation problems. Naval Research Logistics Quarterly 8 (1961), 1, 41-54.   DOI:10.1002/nav.3800080104
  7. A. Biswas, S. Roy and S. P. Mondal: Evolutionary algorithm based approach for solving transportation problems in normal and pandemic scenario. Applied Soft Computing 129 (2022), 109576.   DOI:10.1016/j.asoc.2022.109576
  8. H. I. Calvete, C Gale, J. A. Iranzo and P. Toth: A matheuristic for the two-stage fixed-charge transportation problem. Computers Oper. Res. 95 (2018), 113-122.   DOI:10.1016/j.cor.2018.03.007
  9. O. Cosma, P. C. Pop and D. D\u{a}nciulescu: A novel matheuristic approach for a two-stage transportation problem with fixed costs associated to the routes. Computers Oper. Res. 118 (2020), 104906.   DOI:10.1016/j.cor.2020.104906
  10. G. B. Dantzig: Linear programming. Oper. Res. 50 (2002), 1, 42-47.   DOI:10.1287/opre.50.1.42.17798
  11. A. Ebrahimnejad: New method for solving fuzzy transportation problems with LR flat fuzzy numbers. Inform. Sci. 357 (2016), 108-124.   DOI:10.1016/j.ins.2016.04.008
  12. A. E. Eiben and A. E. Smith: Introduction to Evolutionary Computing. Springer-Verlag, Berlin, Heidelberg 2015.   CrossRef
  13. M. M. El-Sherbiny and R. M. Alhamali: A hybrid particle swarm algorithm with artificial immune learning for solving the fixed charge transportation problem. Computers Industr. Engrg. 64 (2013), 2, 610-620.   DOI:10.1016/j.cie.2012.12.001
  14. M. Hakim and R. Zitouni: An approach to solve a fuzzy bi-objective multi-index fixed charge transportation problem. Kybernetika 60 (2024), 3, 271-292.   DOI:10.14736/kyb-2024-3-0271
  15. E. Hazrati Nejad, S. Yigit-Sert and S. Emrah Amrahov: An effective global path planning algorithm with teaching-learning-based optimization. Kybernetika 60 (2024), 3, 293-316.   DOI:10.14736/kyb-2024-3-0293
  16. W. M. Hirsch and G. B. Dantzig: The fixed charge problem. Naval Res. Logist. Quarterly 15 (1968), 3, 413-424.   DOI:10.1002/nav.3800150306
  17. F. L. Hitchcock: Distribution of a product from several sources to numerous locations. J. Math. Physics 20 (1941), 224-230.   DOI:10.1002/sapm1941201224
  18. J. Hong, A. Diabat, V. V. Panicker and Sand . Rajagopalan: A two-stage supply chain problem with fixed costs: An ant colony optimization approach. Int. J. Product. Econom. 204, (2018), 214-226.   DOI:10.1016/j.ijpe.2018.07.019
  19. A. Hosseini and M. S. Pishvaee: Capacity reliability under uncertainty in transportation networks: An optimization framework and stability assessment methodology. Fuzzy Optim. Decision Making 21 (2022), 3, 479-512.   DOI:10.1007/s10700-021-09374-9
  20. J. Jansi Rani, A. Manivannan and S. Dhanasekar: Interval valued intuitionistic fuzzy diagonal optimal algorithm to solve transportation problems. Int. J. Fuzzy Systems 25 (2023), 4, 1465-1479.   DOI:10.1007/s40815-022-01446-1
  21. N. Jawahar and A. N. Balaji: A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge. Eur. J. Oper. Res. 194 (2009), 2, 496-537.   DOI:10.1016/j.ejor.2007.12.005
  22. N. Jawahar, A. Gunasekaran and N. Balaji: A simulated annealing algorithm to the multi-period fixed charge distribution problem associated with backorder and inventory. Int. J. Prod. Res. 50 (2012), 9, 2533-2554.   DOI:10.1080/00207543.2011.581013
  23. J. B. Jo, Y. Li and M. Gen: Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Computers Industr. Engrg. 53 (2007), 2, 290-298.   DOI:10.1016/j.cie.2007.06.022
  24. N. Kartlı, E. Bostancı and M. S. Guzel: A new algorithm for the initial feasible solutions of fixed charge transportation problem. In: 2022 7th International Conference on Computer Science and Engineering (UBMK), IEEE 2022, pp. 82-85.   DOI:10.1109/ubmk55850.2022.9919524
  25. N. Kartli, E. Bostanci and M. S. Guzel: A new algorithm for optimal solution of fixed charge transportation problem. Kybernetika 59 (2023), 1, 45-63.   DOI:10.15625/2615-9023/18488
  26. N. Kartli, E. Bostanci and M. S. Guzel: Heuristic algorithm for an optimal solution of fully fuzzy transportation problem. Computing 106 (2024), 10, 3195-3227.   DOI:10.1007/s00607-024-01319-5
  27. N. Kartli:     CrossRef
  28. M. M. Lotfi and R. Tavakkoli-Moghaddam: A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Appl. Soft Comput. 13 (2013), 5, 2711-2726.   DOI:10.1016/j.asoc.2012.11.016
  29. D. Mardanya and S. K. Roy: New approach to solve fuzzy multi-objective multi-item solid transportation problem. RAIRO Oper. Res. 57 (2023), 1, 99-120.   DOI:10.1051/ro/2022211
  30. S. Mirjalili: Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Comput. Appl. 27 (2016) 1053-1073.   DOI:10.1007/s00521-015-1920-1
  31. A. S. Mohammed, S. E. Amrahov and F. V. Celebi: Bidirectional conditional insertion sort algorithm; An efficient progress on the classical insertion sort. Future Generation Computer Systems 71 (2017), 102-112.   DOI:10.1016/j.future.2017.01.034
  32. A. Mondal and S. K. Roy: Behavioural threeway decision making with Fermatean fuzzy Mahalanobis distance: Application to the supply chain management problems. Appl. Soft Computing 151 (2024), 111182.   DOI:10.1016/j.asoc.2023.111182
  33. V. V. Panicker, R. Vanga and R. Sridharan: Ant colony Optimization algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge. Int. J. Prod. Res. 51 (2013), 3, 698-717.   DOI:10.1080/00207543.2012.658118
  34. A. N. S. Paojiyah, A. P. Az'zahra, V. F. Aulia and E. R. Wulan: Penerapan Dragonfly Optimization Algorithm (DOA) untuk Menyelesaikan Fixed Charge Transportation Problem (FCTP). KUBIK: Jurnal Publikasi Ilmiah Matematika 9 (2024), 2, 187-197.   CrossRef
  35. P. C. Pop, C. Sabo, B. Biesinger, B. Hu and G. R. Raidl: Solving the two-stage fixed charge transportation problem with a hybrid genetic algorithm. Carpathian J. Math. 33 (2017), 3, 365-371.   CrossRef
  36. K. A. A. D. Raj and C. Rajendran: A genetic algorithm for solving the fixed-charge transportation model: two-stage problem. Comput. Oper. Res. 39 (2012), 9, 2016-2032.   DOI:10.1016/j.cor.2011.09.020
  37. R. V. Rao, V. J. Savsani and D. Vakharia: Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems. Computer-aided Design 43 (2011), 303-315.   DOI:10.1016/j.cad.2010.12.015
  38. B. Saikia, P. Dutta and P. Talukdar: An advanced similarity measure for Pythagorean fuzzy sets and its applications in transportation problem. Artif. Intell. Rev. 56 (2023), 11, 12689-12724.   DOI:10.1007/s10462-023-10421-7
  39. S. Sandhiya and A. Dhanapal: Solving neutrosophic multi-dimensional fixed charge transportation problem. Contemp. Math. 5 (2024), 3, 3601-3624.   DOI:10.37256/cm.5320244927
  40. G. Singh and A. Singh: Extension of particle swarm optimization algorithm for solving transportation problem in fuzzy environment. Appl. Soft Comput. 110 (2021), 107619.   DOI:10.1016/j.asoc.2021.107619
  41. Shivani, D. Chauhan and D. Rani: A feasibility restoration particle swarm optimizer with chaotic maps for two-stage fixed-charge transportation problems. Swarm Evolutionary Comput. 91 (2024), 101776.   DOI:10.1016/j.swevo.2024.101776
  42. M. Sun, J. E. Aronson, P. G. Mckeown and D. Drinka: Tabu search heuristic procedure for the fixed charge transportation problem. Eur. J. Oper. Res. 106 (1998), 2-3, 411-456.   CrossRef