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

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.