Solving the Fixed Charge Transportation Problem by New Heuristic Approach

Journal of Optimization in Industrial Engineering

مقاله 5، دوره 12، شماره 1 - شماره پیاپی 25، خرداد 2019، صفحه 41-52   

نوع مقاله: Original Manuscript

شناسه دیجیتال (DOI): 10.22094/joie.2017.738.1469

نویسندگان

Komeil Yousefi¹؛ Ahmad J. Afshari¹؛ Mostafa Hajiaghaei-Keshteli^{* 2}

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

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

چکیده

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.

کلیدواژه‌ها

Fixed charge Transportation problem؛ Heuristic؛ Metaheuristic Algorithms؛ Priority-based

مراجع

Adlakha, V., & Kowalski, K. (2003). A simple heuristic for solving small fixed-charge transportation problems. Omega, 31(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 Research, 172(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 Research, 62(5), 1095-1106.

Dwyer, P. S. (1966). Use of completely reduced matrices in solving transportation problems with fixed charges. Naval Research Logistics Quarterly, 13(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 Engineering, 64(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 spectrum, 28(3), 337-354.

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

Guignard, M. (1988). A Lagrangean dual ascent algorithm for simple plant location problems. European Journal of Operational Research, 35(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 Computing, 11(2), 2069-2078.

Hajiaghaei-Keshteli, M., & Aminnayeri, M. (2014). Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm. Applied Soft Computing, 25, 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 Engineering, 59(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 Research, 46(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 Research, 50(9), 2533-2554.

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

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

Klose, A. (2008). Algorithms for solving the single-sink fixed-charge transportation problem. Computers & Operations Research, 35(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 Systems, 8(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 Science, 3(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 Science, 3(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 Computing, 13(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 Technology, 70(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 Applications, 38(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 Research, 106(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 Engineering, 96, 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 Sciences, 8(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 Computing, 12(9), 2997-3003.