Digital Library of the European Council for Modelling and Simulation

Title:	Solving Non-Quadratic Matrices In Assignment Problems With An Improved Version Of Vogel's Approximation Method
Authors:	Maximilian Selmair, Alexander Swinarew, Klaus-Jürgen Meier, Yi Wang
Published in:	(2019). ECMS 2019 Proceedings Edited by: Mauro Iacono, Francesco Palmieri, Marco Gribaudo, Massimo Ficco, European Council for Modeling and Simulation. DOI: http://doi.org/10.7148/2019 ISSN: 2522-2422 (ONLINE) ISSN: 2522-2414 (PRINT) ISSN: 2522-2430 (CD-ROM) 33rd International ECMS Conference on Modelling and Simulation, Caserta, Italy, June 11^th – June 14^th, 2019
Citation format:	Maximilian Selmair, Alexander Swinarew, Klaus-Jürgen Meier, Yi Wang (2019). Solving Non-Quadratic Matrices In Assignment Problems With An Improved Version Of Vogel's Approximation Method, ECMS 2019 Proceedings Edited by: Mauro Iacono, Francesco Palmieri, Marco Gribaudo, Massimo Ficco European Council for Modeling and Simulation. doi: 10.7148/2019-0261
DOI:	https://doi.org/10.7148/2019-0261
Abstract:	The efficient allocation of tasks to vehicles in a fleet of self-driving vehicles (SDV) becomes challenging for large-scale 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; Koruko˘glu and Ballı 2011; Balakrishnan 1990). The under-lying 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.
Full text: