Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
PDF

Palabras clave

Multicover problem
heuristic methods
greedy algorithms
combinatorial optimization
Problema de multicubrimiento
métodos heurísticos
algoritmos glotones
optimización combinatoria

Cómo citar

Gutiérrez Andrade, M. A., de los Cobos Silva, S. G., Pérez Salvador, B. R., & Goddard Close, J. (2003). El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México. Revista De Matemática: Teoría Y Aplicaciones, 10(1-2), 147–155. https://doi.org/10.15517/rmta.v10i1-2.230

Resumen

En este artículo se desarrolla un algoritmo heurístico y su correspondiente implementación para resolver un problema de muestreo en la red de rutas de transporte urbano de la Ciudad de México. El problema consiste en la selección de al menos 2 puntos (paradas de la ruta) en cada una de las 236 rutas en el estudio con un total de 8390 paradas. El problema anterior, se plantea como un problema de multicubrimiento (multicover problem) con 236 restricciones y 8390 variables binarias. Este problema es un problema NP-duro, por lo que se implementó un algoritmo heurístico para obtener los puntos de muestreo.

https://doi.org/10.15517/rmta.v10i1-2.230
PDF

Citas

Chvátal, V. (1979) “A greedy heuristic for the set-covering problem”, Mathematical of Operations Research 4(3): 233–235.

Hochbaum, D.S. (1997) Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, Boston, USA.

Murty, K.G. (1995) Operations Research Deterministic Optimization Models. Prentice Hall, New Jersey, USA.

Pisinger, D. (2002) “Heuristics for the container loading problem”, European Journal of Operational Research 141: 382–392.

Wenxun, X. (2002) “A bin packing problem with over-sized items”, Operations Research Letters, 30(3): 832–888.

Willoughby, K.A. (2002) “A mathematical programming analysis of public transit systems”, Omega 30: 137–142.

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.