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.
Licencia
Copyright
© Revista de Matemática: Teoría y Aplicaciones, 2003
Afiliaciones
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
Cómo citar
Comentarios
El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
- Miguel Angel Gutiérrez Andrade ,
- Sergio Gerardo de los Cobos Silva ,
- Blanca Rosa Pérez Salvador ,
- John Goddard Close
Vol. 10 Núm. 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones
Publicado: Feb 1, 2003
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.