Solution Approaches to the Three-index Assignment Problem

This thesis explores the axial Three-Index Assignment Problem (3IAP), also called the Multidimensional Assignment Problem. The problem consists in allocating n jobs to n machines in n factories, such that exactly one job is executed by one machine in one factory at a minimum total cost. The 3IAP is an extension of the classical two-dimensional assignment problem. This combinatorial optimisation problem has been the subject of numerous research endeavours, and proven NP-hard due to its inextricable nature. The study adopts an algorithmic approach to develop swift and e ective methods for solving the problem, focusing on balancing computational e ciency and solution accuracy. The Greedy-Style Procedure (GSP) is a novel heuristic algorithm for solving the 3IAP, guaranteeing feasible solutions in polynomial time. Speci c arrangements of cost matrices can lead to the generation of higher-quality feasible solutions. In addressing the 3IAP, analysing the tie-cases and the matrix ordering led to new variants. Further exploration of cost matrix characteristics has allowed two new heuristic classes to be devised for solving 3IAP. The approach focuses on selecting the best solution within each class, resulting in an optimal or a high-quality approximate solution. Numerical experiments con rm the e ciency of these heuristics, consistently delivering quality feasible solutions in competitive computational times. Moreover, by employing diverse optimisation solvers, we propose and implement two e ective methods to achieve optimal solutions for 3IAP in good CPU times. The study introduces two local search methods based on evolutionary algorithms to solve 3IAP. These approaches explore the solution space through random permutations and the Hungarian method. Building on this, a hybrid genetic algorithm that integrates these local search strategies has been proposed for solving the 3IAP. Implementing the Hybrid Genetic Algorithm (HGA) produces high-quality solutions with reduced computational time, surpassing traditional deterministic approaches. The e ciency of the HGA is demonstrated through experimental results and comparative analyses. On medium to large 3IAP instances, our method delivers comparable or better solutions within a competitive computational time frame.
Two potential future developments and expected applications are proposed at the end of this project. The rst extension will examine the correlation between cost matrices and the optimal total cost of the assignment and will investigate the dependence structure of matrices and its inuence on optimal solutions. Copula theory and Sklar's theorem can help with this analysis. The focus will be on understanding the stochastic dependence of cost matrices and their multivariate properties. Furthermore, the impact of variations in cost distributions, is often modelled based on economic sectors. The second extension involves integrating variable costs de ned by speci c probability distributions, enhancing the comprehensive analysis of economic scenarios and their impact on the assignment problem. The study considers various well-de ned probability distributions and highlights more practical applications of the assignment problem in real-world economics. The project's original contribution lies in its algorithmic approach to investigating the 3IAP, which has led to the development of new, fast, and e cient heuristic methods that strategically balance computational speed and the accuracy of the solutions achieved.