Kybernetika 59 no. 1, 45-63, 2023

A new algorithm for optimal solution of fixed charge transportation problem

Nermin Kartli, Erkan Bostanci and Mehmet Serdar GuzelDOI: 10.14736/kyb-2023-1-0045

Abstract:

Fixed charge transportation problem (FCTP) is a supply chain problem. In this problem, in addition to the cost per unit for each transported product, a fixed cost is also required. The aim is to carry out the transportation process at the lowest possible cost. As with all supply chain problems, this problem may have one, two, or three stages. An algorithm that can find the optimal solution for the problem in polynomial time is not known, even if it is a single-stage problem. For this reason, new algorithms have been proposed in recent years to provide an approximate solution for the problem. The vast majority of these algorithms are meta-heuristic algorithms. In this study, we propose a new heuristic algorithm to find an optimal solution for the 1-stage FCTP. We compare the results of our algorithm with the results of other existing algorithms.

Keywords:

supply chain, transportation problem, fixed charge transportation problem, feasible solution, optimal solution

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), 2, 132-151.   CrossRef
  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. V. Adlakha, K. Kowalski, R. R. Vemuganti and B. Lev: More-for-less algorithm for fixed-charge transportation problems. Omega: Int. J. Manag. Sci. 35 (2007), 1, 116-127.   DOI:10.1016/j.omega.2006.03.001
  6. W. B. Allen and D. Liu: An inventory-transport model with uncertain loss and damage. Logist.Transport. Rev. 29 (1993), 2, 101.   CrossRef
  7. P. Amorim, H. Meyr, C. Almeder and B. Almada-Lobo: Managing perishability in production-distribution planning: a discussion and review. Flexible Services Manufactur. J. 25 (1993), 3, 389-413.   CrossRef
  8. S. H. Amin and F. Baki: A facility location model for global closed-loop supply chain network design. Appl. Math. Modell. 41 (2017), 316-330.   DOI:10.1016/j.apm.2016.08.030
  9. M. L. Balinski: Fixed-cost transportation problems. Naval Res. Logistic Quarterly 8 (1961), 1, 41-54.   DOI:10.1002/nav.3800080104
  10. H. I. Calvete, C. Gale, J. A. Iranzo and P. Toth: A matheuristic for the two-stage fixed-charge transportation problem. Comput. Oper. Res. 95 (2018), 113-122.   DOI:10.1016/j.cor.2018.03.007
  11. 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. Comput. Oper. Res. 118 (2020), 104906.   DOI:10.1016/j.cor.2020.104906
  12. M. M. El-Sherbiny and R. M. Alhamali: A hybrid particle swarm algorithm with artificial immune learning for solving the fixed charge transportation problem. Comput. Industr, Engrg. 64 (2013), 2, 610-620.   DOI:10.1016/j.cie.2012.12.001
  13. M. Eskandarpour, P. Dejax and O. Peton: A large neighbourhood search heuristic for supply chain network design. Comput. Oper. Res. 8 (2017), 4, 23-37.   DOI:10.1016/j.cor.2016.11.012
  14. J. Gottlieb and L. Paulmann: Genetic algorithms for the fixed charge transportation problems. In: Proc. of the IEEE Conf. on Evolutionary Computation, ICEC 1998, pp. 330-335.   DOI:10.1109/icec.1998.699754
  15. F. L. Hitchcock: Distribution of a product from several sources to numerous locations. J. Math. Physics 20 (1941), 224-230.   DOI:10.1002/sapm1941201224
  16. W. M. Hirsch and G. B. Dantzig: The fixed Charge problem. Naval Res. Log. Quart. 15 (1968), 413-424.   DOI:10.1002/nav.3800150306
  17. J. Hong, A. Diabat, V. V. Panicker and S. 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
  18. N. Jawahar and A. N. Balaji: A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge. Europ. J. Oper. Res. 194 (2009), 2, 496-537.   DOI:10.1016/j.ejor.2007.12.005
  19. 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 (2011), 9, 2533-2554.   DOI:10.1080/00207543.2011.581013
  20. J. B. Jo, Y. Li, Y. and M. Gen: Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Comput. Industr. Engrg. 53 (2007), 2, 290-298.   DOI:10.1016/j.cie.2007.06.022
  21. N. Kartlı, E. Bostancı and M. S. Güzel: A new algorithm for the initial feasible solutions of fixed charge transportation problem. In: 7th International Conference on Computer Science and Engineering (UBMK), IEEE 2022, pp. 82-85.   DOI:10.1109/ubmk55850.2022.9919524
  22. P. Li: Solving the sensor cover energy problem via integer linear programming. Kybernetika 57 (2021), 4, 568-593.   DOI:10.14736/kyb-2021-4-0568
  23. V. Lin: Binary integer programming solution for troubleshooting with dependent actions. Kybernetika 53 (2017), 3, 493-512.   DOI:10.14736/kyb-2017-3-0493
  24. 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
  25. 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 (2012), 3, 698-717.   DOI:10.1080/00207543.2012.658118
  26. V. V. Panicker, R. Sridharan and B. Ebenezer: Three-stage supply chain allocation with fixed cost. J. Manuf. Technol. Manag. 23 (2012), 7, 853-868.   DOI:10.1108/17410381211267691
  27. 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, 36-371.   CrossRef
  28. K. A. A. D. Raj and C. Rajendran: A hybrid genetic algorithm for solving single-stage fixed-charge transportation problems. Technol. Oper. Manag. 2 (2011), 1, 1-15.   DOI:10.1016/j.proeng.2011.08.023
  29. 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
  30. G. Singh and A. Singh: Solving fixed-charge transportation problem using a modified particle swarm optimization algorithm. Int. J. System Assurance Engrg. Management 12 (2021), (6), 1073-1086.   DOI:10.1007/s13198-021-01171-2
  31. M. Sun, J. E. Aronson, P. G. Mckeown and D. Drinka: A tabu search heuristic procedure for the fixed charge transportation problem. Europ. J. Oper. Res. 106 (1999), 2-3, 411-456.   DOI:10.1016/s0377-2217(97)00284-1
  32. F. G. Tari and I. Hashemi: Prioritized K-mean clustering hybrid GA for discounted fixed charge transportation problems. Comput. Industr. Engrg. 126 (2018), 63-74.   DOI:/10.1016/j.cie.2018.09.019