|
Digital
Library of the European Council for Modelling and Simulation |
Title: |
Evaluation
Of Algorithm Performance For Simulated Square And Non-Square Logistic
Assignment Problems |
Authors: |
Maximilian Selmair, Sascha Hamzehi, Klaus-Juergen Meier |
Published in: |
(2021). ECMS 2021,
35th Proceedings DOI: http://doi.org/10.7148/2021 ISSN:
2522-2422 (ONLINE) ISSN:
2522-2414 (PRINT) ISSN:
2522-2430 (CD-ROM) ISBN: 978-3-937436-72-2 Communications of the ECMS , Volume 35, Issue 1, June 2021, United Kingdom |
Citation
format: |
Maximilian Selmair, Sascha Hamzehi, Klaus-Juergen Meier (2021). Evaluation Of Algorithm Performance For Simulated Square And Non-Square Logistic Assignment Problems, ECMS 2021 Proceedings Edited By: Khalid Al-Begain, Mauro Iacono, Lelio Campanile, Andrzej Bargiela European Council for Modeling and Simulation. doi: 10.7148/2021-0016 |
DOI: |
https://doi.org/10.7148/2021-0016 |
Abstract: |
The optimal
allocation of transportation tasks to a fleet of vehicles, especially for
large-scale systems of more than 20 Autonomous Mobile Robots (AMRs), remains a major challenge in logistics. Optimal in
this context refers to two criteria: how close a result is to the best
achievable objective value and the shortest possible computational time.
Operations research has provided different methods that can be applied to
solve this assignment problem. Our literature review has revealed six commonly
applied methods to solve this problem. In this paper, we compared three
optimal methods (Integer Linear Programming, Hungarian Method and the Jonker Volgenant Castanon algorithm) to three three
heuristic methods (Greedy Search algorithm, Vogel’s Approximation Method and
Vogel’s Approximation Method for non-quadratic Matrices). The latter group generally yield results faster, but were not
developed to provide optimal results in terms of the optimal objective value.
Every method was applied to 20.000 randomised
samples of matrices, which differed in scale and configuration, in simulation
experiments in order to determine the results’ proximity to the optimal
solution as well as their computational time. The simulation results
demonstrate that all methods vary in their time needed to solve the
assignment problem scenarios as well as in the respective quality of the
solution. Based on these results yielded by computing quadratic and
non-quadratic matrices of different scales, we have concluded that the Jonker Volgenant Castanon algorithm is deemed to be the best method for
solving quadratic and non-quadratic assignment problems with optimal
precision. However, if performance in terms of computational time is prioritised for large non-quadratic matrices (50×300 and
larger), the Vogel’s Approximation Method for non-quadratic Matrices
generates faster approximated solutions. |
Full
text: |