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 No. 1-2 (2003), Articles
Vol. 10 No. 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

Articles
https://doi.org/10.15517/rmta.v10i1-2.230
Published 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 (Español (España))

Keywords

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

How to Cite

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

Download Citation

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

Abstract

In this paper an heuristic algorithm is developed. Its implementation is developed as well, in order to solve a sampling problem in the urban transportation network in Mexico City. The problem consist of the selection of at least 2 points (stops) on each of the 236 routes in the study comprising a total of 8390 stops. This problem is presented as a multicover problem subject to 236 restrictions and 8390 binary variables. Given that this an NP-hard problem, it was implemented an heuristic algorithm to determine the sampling points.

https://doi.org/10.15517/rmta.v10i1-2.230
PDF (Español (España))

References

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.

Comments

Downloads

Download data is not yet available.