A novel approach and hybrid parallel algorithms for solving the fixed charge transportation problem

Ahmed Lahjouji El Idrissi, Ismail Ezzerrifi Amrani, Adil Ben-Hdech, Ahmad El Allaoui

Abstract


This article is dedicated to the efficient resolution of the fixed charge transport problem (FCTP) with the goal of identifying optimal solutions within reduced timeframes. FCTP is a combinatorial and NP-complete problem known for its exponential time complexity relative to problem size. Metaheuristic methods, including genetic algorithms, represent effective techniques for obtaining high-quality FCTP solutions. Consequently, the integration of parallel algorithms emerges as a strategy for expediting problem-solving. The proposed approach, referred to as the parallel genetic algorithm (PGA), entails the application of a genetic algorithm across multiple parallel architectures to tackle the FCTP problem. The primary aim is to explore fresh solutions for the fixed charge transportation problem using genetic algorithms while concurrently optimizing the time required to achieve these solutions through parallelism. The FCTP problem is fundamentally a linear programming challenge, revolving around the determination of optimal shipment quantities from numerous source locations to multiple destinations with the overarching objective of minimizing overall transportation costs. This necessitates consideration of constraints tied to product availability at the sources and demand dynamics at the destinations. In this study, a pioneering approach to addressing the Fixed Charge Transportation Problem (FCTP) using parallel genetic algorithms (PGA) is unveiled. The research introduces two distinct parallel algorithms: The Master-Slave Approach (MS-GA) and the Coarse-Grained Approach (CG-GA). Additionally, investigation into the hybridization of these approaches has led to the development of the NMS-CG-GA approach. The numerical results reveal that our parallelism-based approaches significantly improve the performance of genetic algorithms. Specifically, the Master-Slave (MS-GA) approach demonstrates its advantages in solving smaller instances of the FCTP problem, while the Coarse-Grained (CG-GA) approach exhibits greater effectiveness for larger problem instances. The conclusion reached is that the novel hybrid parallel genetic algorithm approach (NMS-CG-GA) outperforms its predecessors, yielding outstanding results, particularly across diverse FCTP problem instances.

Keywords


Parallel Genetic Algorithm (PGA); Fixed Charge Transportation Problem (FCTP); Master-Slave Approach; Coarse-Grained Approach; Hybrid parallel genetic algorithm Approach

Full Text:

PDF

References


Nicholson, C. D., & Zhang, W. Optimal network flow: A predictive analytics perspective on the fixed-charge network flow problem. Computers & Industrial Engineering, 2016, vol. 99, pp. 260-268. DOI: 10.1016/J.CIE.2016.07.030.

Tsai, Chun-Wei., Tseng, Shih-Pang., & Chiang, Ming-Chao. A fast parallel genetic algorithm for traveling salesman problem. Methods and Tools of Parallel Programming Multicomputers: Second Russia-Taiwan Symposium, MTPP 2010, Lecture Notes in Computer Science, vol. 6083. Springer, Berlin, Heidelberg, 2010, pp. 241-250. DOI: 10.1007/978-3-642-14822-4_27.

Skorpil, V., Oujezsky, V., Cika, P., & Tuleja, M. Parallel processing of genetic algorithms in Python language. 2019 PhotonIcs & Electromagnetics Research Symposium - Spring (PIERS-Spring), Rome, Italy, 2019, pp. 3727-3731. DOI: 10.1109/PIERS-Spring46901.

Gottlieb, J., & Paulmann, L. Genetic algorithms for the fixed charge transportation problem. 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360), Anchorage, AK, USA, 1998, pp. 330-335. DOI: 10.1109/ICEC.1998.699754.

Midya, S., Roy, S. K., & Yu, V. F. Intuitionistic fuzzy multi-stage multi-objective fixed-charge solid transportation problem in a green supply chain. International Journal of Machine Learning and Cybernetics, 2021, vol. 12, pp. 699-717. DOI: 10.1007/s13042-020-01197-1.

Adlakha, V., & Kowalski, K. A simple heuristic for solving small fixed-charge transportation problems. Omega, 2003, vol. 31, iss. 3, pp. 205-211. DOI: 10.1016/S0305-0483(03)00025-2.

Roberti, R., Bartolini, E., & Mingozzi, A. The fixed charge transportation problem: An exact algorithm based on a new integer programming formulation. Management Science, 2015, vol. 61, iss. 6, pp. 1275-1291. DOI : 10.1287/mnsc.2014.1947.

Kowalski, K., & Lev, B. On step fixed-charge transportation problem. Omega, 2008, vol. 36, iss. 5, pp. 913-917. DOI: 10.1016/j.omega.2007.11.001.

Adlakha, V., & Kowalski, K. A heuristic method for ‘more-for-less’ in distribution related problems. International Journal of Mathematical Education in Science and Technology, 2001, vol. 32, iss. 1, pp. 61-71. DOI: 10.1080/00207390117225.

Kurennov, S., Barakhov, K., & Vambol, O. Topological optimization of a symmetrical adhesive joint. Island model of genetic algorithm. Radioelectronic and Computer Systems, 2022, no. 3, pp. 67-83. DOI: 10.32620/reks.2022.3.05.

Neskorodieva, T., Fedorov, E., Chychuzhko, M., et al. Metaheuristic method for searching quasi-optimal route based on the ant algorithm and annealing simulation. Radioelectronic and Computer Systems, 2022, no. 1, pp. 92-102. DOI: 10.32620/reks.2022.1.07.

Booker, L. B., Goldberg, D. E., & Holland, J. H. Classifier systems and genetic algorithms. Artificial Intelligence, 1989, vol. 40, iss. 1-3, pp. 235-282. DOI: 10.1016/0004-3702(89)90050-7.

Kim, H. J., & Hooker, J. N. Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach. Annals of Operations Research, 2002, vol. 115, iss. 1-4, pp. 95-124. DOI: 10.1023/A:1021145103592.

Lahjouji El Idrissi, A., Ezzerrifi Amrani, I., & El Allaoui, A. Improved Parallel Genetic Algorithm for Fixed Charge Transportation Problem. In: Farhaoui, Y., Rocha, A., Brahmia, Z., Bhushab, B. (eds) Artificial Intelligence and Smart Environment. ICAISE 2022. Lecture Notes in Networks and Systems, 2023, vol. 635. pp. 524-530. Springer, Cham. DOI: 10.1007/978-3-031-26254-8_76.

Michalewicz, Z., & Schoenauer, M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary computation, 1996, vol. 4, no. 1, pp. 1-32. DOI: 10.1162/evco.1996.4.1.1.

Michalewicz, Z., Vignaux, G. A., & Hobbs, M. A nonstandard genetic algorithm for the nonlinear transportation problem. ORSA Journal on computing, 1991, vol. 3, iss. 4, pp. 307-316. DOI: DOI: 10.1287/ijoc.3.4.307.

Molla-Alizadeh-Zavardehi, S., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. Solving a capacitated fixed-charge transportation problem by artificial immune and genetic algorithms with a Prüfer number representation. Expert Systems with Applications, 2011, vol. 38, iss. 8, pp. 10462-10474. DOI: 10.1016/j.eswa.2011.02.093.

Lotfi, M. M., & Tavakkoli-Moghaddam, R. A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Applied Soft Computing, 2013, vol. 13, iss. 5, pp. 2711-2726. DOI: 10.1016/j.asoc.2012.11.016.

Liu, C., & Kroll, A. Performance impact of mutation operators of a subpopulation-based genetic algorithm for multi-robot task allocation problems. SpringerPlus, 2016, vol. 5, article no. 1361. DOI: 10.1186/s40064-016-3027-2.

El Idrissi, A. L., Tajani, C., & Sabbane, M. HOPX crossover operator for the fixed charge logistic model with priority based encoding. International Journal of Electrical and Computer Engineering, 2018, vol. 8, iss. 6, pp. 5351-5358. DOI: 10.11591/ijece.v8i6.pp5351-5358.

Leite, J. P. B., & Topping, B. H. V. Improved genetic operators for structural engineering optimization. Advances in Engineering Software, 1998, vol. 29, iss. 7-9, pp. 529-562. DOI: 10.1016/S0965-9978(98)00021-0.

Harada, T., & Alba, E. Parallel genetic algorithms: a useful survey. ACM Computing Surveys, 2020, vol. 53, iss. 4, article no. 86, pp. 1-39. DOI: 10.1145/3400031.

Gehring, H., & Bortfeldt, A. A parallel genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 2002, vol. 9, no 4, pp. 497-511. DOI: 10.1111/1475-3995.00369.

He, J., Chang, D., Mi, W., & Yan, W. A hybrid parallel genetic algorithm for yard crane scheduling. Transportation Research Part E: Logistics and Transportation Review, 2010, vol. 46, iss 1, pp. 136-155. DOI: 10.1016/j.tre.2009.07.002.

Mygal, V., Mygal, G., & Mygal, S. Artificial intelligence as the cognitive value of heuristic models. Radioelectronic and computer systems, 2022, no 2, pp. 118-130. DOI: 10.32620/reks.2022.2.10.




DOI: https://doi.org/10.32620/reks.2023.3.02

Refbacks

  • There are currently no refbacks.