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
Vol. 10 Núm. 1-2 (2003), Artículos
Vol. 10 Núm. 1-2 (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

Artículos
https://doi.org/10.15517/rmta.v10i1-2.230
Publicado February 1, 2003
Miguel Angel Gutiérrez Andrade
Departamento de Sistemas, Universidad Autónoma Metropolitana-Azcapotzalco, Av. San Pablo 180, Colonia Reynosa Tamaulipas, 02200 México, D.F. México
Sergio Gerardo de los Cobos Silva
Departamento de Ingeniería Eléctrica, Universidad Autónoma Metropolitana – Iztapalapa, Av. Michoacán y La Purísima s/n, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340 México
Blanca Rosa Pérez Salvador
Departamento de Matemáticas, UAM-I, Departamento de Ingeniería Eléctrica, Universidad Autónoma Metropolitana – Iztapalapa, Av. Michoacán y La Purísima s/n, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340 México
John Goddard Close
Departamento de Ingeniería Eléctrica, Universidad Autónoma Metropolitana – Iztapalapa, Av. Michoacán y La Purísima s/n, Col. Vicentina, Del. Iztapalapa, México D.F., C.P. 09340 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
ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver

Descargar cita

Endnote/Zotero/Mendeley (RIS) BibTeX
Crossref
Scopus
Google Scholar
Europe PMC

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.