A combinatorial optimization formulation for the home away assignment problem

Publicaciones en Ciencias y Tecnología

View Publication Info
 
 
Field Value
 
Title A combinatorial optimization formulation for the home away assignment problem
Una formulación combinatoria para el problema de asignación local-visitante
 
Creator Perdomo, Jorge
Lara Urdaneta, Hugo
 
Description The sports scheduling problem has been center of attention in the Operational Research community due to their variety of models, and computational complexity of solutions (see for example Ribeiro (2010)). In a Round Robin tournament, the schedule is proposed by assigning a “home" or “away" labels to a preestablished itinerary, in a such way that the total distance traveled by the teams during the tournament is minimized. In terms of operation research, the problem is modeled as a binary quadratic programming problem with linear constraints. In Suzuka y cols. (2005) the problem is treated as a MIN-RES-CUT. In this work we study the structure of the home-away assignment problem, and propose a simplification of the combinatorial formulation. We solve exactly small instances of the problem with an exhaustive search, and also approximately solve larger instances with a random search.
El problema de elaboración de calendarios deportivos ha centrado la atención de la comunidad de investigación de operaciones por la variedad de modelos y la complejidad computacional de las soluciones (ver por ejemplo Ribeiro (2010)). En torneos tipo Round Robin de ida y vuelta el calendario se propone asignando la etiqueta de local o visitante a cada equipo, en un itinerario preestablecido de manera que se minimice el recorrido total de los equipos durante el torneo. En términos de investigación de operaciones lo modelamos como un problema de optimización cuadrática binaria con restricciones lineales. Suzuka, Miyashiro, Yoshise, y Matsui (2005) lo tratan como uno de encontrar el corte mínimo con restricciones (Min-Res-Cut) en un grafo no dirigido, proporcionando una formulación de optimización combinatoria. En el presente trabajo estudiamos la estructura del problema de asignación local-visitante, y proponemos una simplificación de la formulación de optimización combinatoria. Resolvemos de forma exacta con una búsqueda exhaustiva instancias pequeñas del problema, y resolvemos de forma aproximada con una búsqueda aleatoria instancias mayores.
 
Publisher Universidad Centroccidental Lisandro Alvarado
 
Date 2013-11-07
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Research article
Artículo de investigación original
 
Format application/pdf
 
Identifier https://revistas.ucla.edu.ve/index.php/pcyt/article/view/704
 
Source Publicaciones en Ciencias y Tecnología; Vol 7 No 2 (2013): July-December; 127-141
Publicaciones en Ciencias y Tecnología; Vol. 7 Núm. 2 (2013): Julio-Diciembre; 127-141
Publicaciones en Ciencias y Tecnología; v. 7 n. 2 (2013): Julio-Diciembre; 127-141
2477-9660
1856-8890
 
Language spa
 
Relation https://revistas.ucla.edu.ve/index.php/pcyt/article/view/704/279
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library