A novel approach to solve assignment problems

Abstract

The Assignment Problem is a fundamental combinatorial optimization problem with vast applications in operations research, supply chain management, transportation, etc. Traditionally, techniques like Hungarian, branch-and-bound and LP formulations have been used to obtain optimal solutions in polynomial time. However, these approaches may become computationally expensive in large-scale, dynamic or fuzzy environments. This paper presents a novel heuristic-hybrid method for solving the assignment problem with an adaptive-penalty to handle infeasibility and convergence toward optimality. Comparative computational and modelling studies with the Hungarian method show that in small test cases, the approach of this paper attains a fairly competitive optimality and it is extremely efficient than other methods such as Hungarian etc. In order to illustrate this, two numerical examples are provided balanced and unbalanced.