Solving non-quadratic Matrices in Assignment Problems with an improved Version of Vogel's Approximation Method

Abstract

The efficient allocation of tasks to vehicles in a fleet of self-driving vehicles (SDV) becomes challenging for largescale systems (e.g. more than hundred vehicles). Operations research provides different methods that can be applied to solve such assignment problems. Integer Linear Programming (ILP), the Hungarian Method (HM) or Vogel’s Approximation Method (VAM) are frequently used in related literature (Paul 2018; Dinagar and Keerthivasan 2018; Nahar et al. 2018; Ahmed et al. 2016; Korukoglu and Balli 2011; Balakrishnan 1990). The underlying paper proposes an adapted version of VAM which reaches better solutions for non-quadratic matrices, namely Vogel’s Approximation Method for non-quadratic Matrices (VAM-nq). Subsequently, VAM-nq is compared with ILP, HM and VAM by solving matrices of different sizes in computational experiments in order to determine the proximity to the optimal solution and the computation time. The experimental results demonstrated that both VAM and VAM-nq are five to ten times faster in computing results than HM and ILP across all tested matrix sizes. However, we proved that VAM is not able to generate optimal solutions in large quadratic matrices constantly (starting at approx. 15×15) or small non-quadratic matrices (starting at approx. 5×6). In fact, we show that VAM produces insufficient results especially for non-quadratic matrices. The result deviate further from the optimum if the matrix size increases. Our proposed VAM-nq is able to provide similar results as the original VAM for quadratic matrices, but delivers much better results in non-quadratic instances often reaching an optimum solution. This is especially important for practical use cases since quadratic matrices are rather rare.