Solving the Fixed Charge Transportation Problem by New Heuristic Approach

Document Type: Original Manuscript

Authors

1 Department of Industrial Engineering, Shomal University, Amol, Iran

2 Department of Industrial Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran

10.22094/joie.2017.738.1469

Abstract

The fixed charge transportation problem (FCTP) is a deployment of the classical transportation problem in which a fixed cost is incurred, independent of the amount transported, along with a variable cost that is proportional to the amount shipped. Since the problem is considered as an NP-hard, the computational time grows exponentially as the size of the problem increases. In this paper, we propose a new heuristic along with well-known metaheuristic like Geneticalgorithm (GA), simulated annealing (SA) and recently developed one, Keshtel algorithm (KA) to solve the FCTP. Contrary to previous works, we develop a simple and strong heuristic according to the nature of the problem and compare the result with metaheuristics. In addition, since the researchers recently used the priority-based representation to encode the transportation graphs and achieved very good results, we consider this representation in metaheuristics and compare the results with the proposed heuristic. Furthermore, we apply the Taguchi experimental design method to set the proper values of algorithms in order to improve their performances. Finally, computational results of heuristic and metaheuristics with different encoding approaches, both in terms of the solution quality and computation time, are studied in different problem sizes.

Graphical Abstract

Solving the Fixed Charge Transportation Problem by New Heuristic Approach

Highlights

  • We employ new and recent metaheuristics for the first time in the literature to solve the FCTP.
  • We develop a simple and strong heuristic according to the nature of the problem and compare the result with metaheuristics.
  • We use the priority-based representation to encode the transportation graphs and compare the results with the proposed heuristic.
  • The Taguchi experimental design method is applied to set the proper values of algorithms.
  • Computational results of heuristic and metaheuristics with different encoding approachesare studied

Keywords

Main Subjects


Adlakha, V., & Kowalski, K. (2003). A simple heuristic for solving small fixed-charge transportation problems. Omega31(3), 205-211.

Aguado, J. S. (2009). Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems. Annals of Operations Research172(1), 45.

Balinski, M. L. (1961). Fixed‐cost transportation problems. Naval Research Logistics (NRL)8(1), 41-54.

Buson, E., Roberti, R., & Toth, P. (2014). A reduced-cost iterated local search heuristic for the fixed-charge transportation problem. Operations Research62(5), 1095-1106.

Dwyer, P. S. (1966). Use of completely reduced matrices in solving transportation problems with fixed charges. Naval Research Logistics Quarterly13(3), 289-313.

El-Sherbiny, M. M., & Alhamali, R. M. (2013). A hybrid particle swarm algorithm with artificial immune learning for solving the fixed charge transportation problem. Computers & Industrial Engineering64(2), 610-620.

Gen, M., & Cheng, R. (1997). Foundations of genetic algorithms. Genetic Algorithms and Engineering Design, 1-41.

Gen, M., & Cheng, R. (2000). Genetic algorithms and engineering optimization (Vol. 7). John Wiley & Sons.

Gen, M., & Li, Y. (1999). Spanning tree-based genetic algorithm for the bicriteria fixed charge transportation problem. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on (Vol. 3, pp. 2265-2271). IEEE.

Gen, M., Altiparmak, F., & Lin, L. (2006). A genetic algorithm for two-stage transportation problem using priority-based encoding. OR spectrum28(3), 337-354.

Glover, F. (2005). Parametric ghost image processes for fixed-charge problems: A study of transportation networks. Journal of Heuristics11(4), 307-336.

Guignard, M. (1988). A Lagrangean dual ascent algorithm for simple plant location problems. European Journal of Operational Research35(2), 193-200.

Hajiaghaei-Keshteli, M. (2011). The allocation of customers to potential distribution centers in supply chain networks: GA and AIA approaches. Applied Soft Computing11(2), 2069-2078.

Hajiaghaei-Keshteli, M., & Aminnayeri, M. (2014). Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm. Applied Soft Computing25, 184-203.

Hajiaghaei-Keshteli, M., Molla-Alizadeh-Zavardehi, S., & Tavakkoli-Moghaddam, R. (2010). Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm. Computers & Industrial Engineering59(2), 259-271.

Hirsch, Warren M., and George B. Dantzig.(1968). "The fixed charge problem. Naval Research Logistics Quarterly, 15(3), 413-424.

Holland, J. H. (1975). Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. Ann Arbor, MI: University of Michigan Press.

Hwang, R. K., Katayama, H., & Gen, M. (2008). U-shaped assembly line balancing problem with genetic algorithm. International Journal of Production Research46(16), 4637-4649.

Jawahar, N., Gunasekaran, A., & Balaji, N. (2012). A simulated annealing algorithm to the multi-period fixed charge distribution problem associated with backorder and inventory. International Journal of Production Research50(9), 2533-2554.

Jo, J. B., Li, Y., & Gen, M. (2007). Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Computers & Industrial Engineering53(2), 290-298.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science220(4598), 671-680.

Klose, A. (2008). Algorithms for solving the single-sink fixed-charge transportation problem. Computers & Operations Research35(6), 2079-2092.

Lee, J. E., Gen, M., & Rhee, K. G. (2009). Hybrid priority-based genetic algorithm for multi-stage reverse logistics network. Industrial Engineering and Management Systems8(1), 14-21.

Loch, G. V., & da Silva, A. C. L. (2014). A computational experiment in a heuristic for the Fixed Charge Transportation Problem. International Refereed Journal of Engineering and Science3(4).

Loch, G. V., & da Silva, A. C. L. (2014). A computational experiment in a heuristic for the Fixed Charge Transportation Problem. International Refereed Journal of Engineering and Science3(4).

Lotfi, M. M., & Tavakkoli-Moghaddam, R. (2013). A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Applied Soft Computing13(5), 2711-2726.

Mahmoodi-Rad, A., Molla-Alizadeh-Zavardehi, S., Dehghan, R., Sanei, M., & Niroomand, S. (2014). Genetic and differential evolution algorithms for the allocation of customers to potential distribution centers in a fuzzy environment. The International Journal of Advanced Manufacturing Technology70(9-12), 1939-1954.

Molla-Alizadeh-Zavardehi, S., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. (2011). Solving a capacitated fixed-charge transportation problem by artificial immune and genetic algorithms with a Prüfer number representation. Expert Systems with Applications38(8), 10462-10474.

Shetty, B. (1990). A relaxation/decomposition algorithm for the fixed charged network problem. Naval Research Logistics (NRL)37(2), 327-340.

Steinberg, D. I. (1970). The fixed charge problem. Naval Research Logistics Quarterly, 17(2), 217-235.

Sun, M., & McKeown, P. G. (1993). Tabu search applied to the general fixed charge problem. Annals of Operations Research, 41(4), 405-420.

Sun, M., Aronson, J. E., McKeown, P. G., & Drinka, D. (1998). A tabu search heuristic procedure for the fixed charge transportation problem.European Journal of Operational Research, 106(2), 441-456.

Sun, M., Aronson, J. E., McKeown, P. G., & Drinka, D. (1998). A tabu search heuristic procedure for the fixed charge transportation problem. European Journal of Operational Research106(2-3), 441-456.

Taguchi, G. (1986). Introduction to quality engineering: designing quality into products and processes.

Tari, F. G., & Hashemi, Z. (2016). A priority based genetic algorithm for nonlinear transportation costs problems. Computers & Industrial Engineering96, 86-95.

Walker, W. E. (1976). A heuristic adjacent extreme point algorithm for the fixed charge problem. Management Science, 22(5), 587-596.

Wright DD, Haehling von Lanzenauer C (1989) Solving the fixed charge problem with Lagrangian relaxation and cost allocation heuristics. Eur. J. Oper. Res. 42(3):305–312.

Wright, D., & von Lanzenauer, C. H. (1991). COAL: A new heuristic approach for solving the fixed charge problem—computational results. European Journal of Operational Research, 52(2), 235-246.

Xie, Fanrong, and Renan Jia. "Nonlinear fixed charge transportation problem by minimum cost flow-based genetic algorithm." Computers & Industrial Engineering 63, no. 4 (2012): 763-778.

Yadegari, E., Zandieh, M., & Najmi, H. (2015). A hybrid spanning tree-based genetic/simulated annealing algorithm for a closed-loop logistics network design problem. International Journal of Applied Decision Sciences8(4), 400-426.

Yaghini, M., Momeni, M., & Sarmadi, M. (2012). A simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design. Applied Soft Computing12(9), 2997-3003.