Tehnički vjesnik, Vol. 28 No. 5, 2021.
Izvorni znanstveni članak
https://doi.org/10.17559/TV-20200618162959
Particle Swarm Algorithm for Improved Handling of the Mirrored Traveling Tournament Problem
Kevin Tole*
orcid.org/0000-0003-0373-3691
; Technical University of Mombasa, Institute of Computing and Informatics, P.O. Box 90420 - 80100, Mombasa Kenya
Muhammed Milani
; Bandirma Onyedi Eylul Universit, Faculty of Computer Engineering, PK: 10200 Bandırma / BALIKESİR-Turkey
Fullgence Mwakondo
; Technical University of Mombasa, Institute of Computing and Informatics, P.O. Box 90420 - 80100, Mombasa Kenya
Sažetak
In this study, we used a particle swarm optimization (PSO) algorithm to address a variation of the non-deterministic polynomial-time NP-hard traveling tournament problem, which determines the optimal schedule for a double round-robin tournament, for an even number of teams, to minimize the number of trips taken. Our proposed algorithm iteratively explored the search space with a swarm of particles to find near-optimal solutions. We also developed three techniques for updating the particle velocity to move towards optimal points, which randomly select and replace row and column parameters to find candidate positions close to an optimal solution. To further optimize the solution, we calculated the particle cost function, an important consideration within the problem conditions, for team revenues, fans, and media. We compared our computation results with two well-known meta-Heuristics: a genetics algorithm utilizing a swapping method and a Greedy Randomized Adaptive Search Procedure Iterated Local Search algorithm heuristic on a set of 20 teams. Ultimately, the PSO algorithm generated solutions that were comparable, and often superior, to the existing well-known solutions. Our results indicate that our proposed algorithm could aid in reducing the overall budget expenditures of international sports league organizations, which could enable significant monetary savings and increase profit margins.
Ključne riječi
double-round robin tournament; home-away assignment; NP-hard; particle swarm optimization; traveling tournament problem
Hrčak ID:
261342
URI
Datum izdavanja:
15.8.2021.
Posjeta: 936 *