El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México

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...

Descripción completa

Detalles Bibliográficos
Autores principales:	Gutiérrez Andrade, Miguel Angel, de los Cobos Silva, Sergio Gerardo, Pérez Salvador, Blanca Rosa, Goddard Close, John
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2003
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/230

id	RMTA230
record_format	ojs
spelling	RMTA2302022-01-19T15:52:42Z El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México Gutiérrez Andrade, Miguel Angel de los Cobos Silva, Sergio Gerardo Pérez Salvador, Blanca Rosa Goddard Close, John Multicover problem heuristic methods greedy algorithms combinatorial optimization Problema de multicubrimiento métodos heurísticos algoritmos glotones optimización combinatoria 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. 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 implementó un algoritmo heurístico para obtener los puntos de muestreo. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2003-02-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/230 10.15517/rmta.v10i1-2.230 Revista de Matemática: Teoría y Aplicaciones; Vol. 10 No. 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 147-155 Revista de Matemática: Teoría y Aplicaciones; Vol. 10 Núm. 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 147-155 Revista de Matemática; Vol. 10 N.º 1-2 (2003): Revista de Matemática: Teoría y Aplicaciones; 147-155 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/230/210 Derechos de autor 2003 Revista de Matemática: Teoría y Aplicaciones
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Gutiérrez Andrade, Miguel Angel de los Cobos Silva, Sergio Gerardo Pérez Salvador, Blanca Rosa Goddard Close, John
spellingShingle	Gutiérrez Andrade, Miguel Angel de los Cobos Silva, Sergio Gerardo Pérez Salvador, Blanca Rosa Goddard Close, John El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
author_facet	Gutiérrez Andrade, Miguel Angel de los Cobos Silva, Sergio Gerardo Pérez Salvador, Blanca Rosa Goddard Close, John
author_sort	Gutiérrez Andrade, Miguel Angel
description	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 implementó un algoritmo heurístico para obtener los puntos de muestreo.
title	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
title_short	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
title_full	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
title_fullStr	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
title_full_unstemmed	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
title_sort	el problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la ciudad de méxico
title_alt	El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2003
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/230
work_keys_str_mv	AT gutierrezandrademiguelangel elproblemadelmulticubrimientounaaplicacionparalaselecciondeparadasenlareddetransportedelaciudaddemexico AT deloscobossilvasergiogerardo elproblemadelmulticubrimientounaaplicacionparalaselecciondeparadasenlareddetransportedelaciudaddemexico AT perezsalvadorblancarosa elproblemadelmulticubrimientounaaplicacionparalaselecciondeparadasenlareddetransportedelaciudaddemexico AT goddardclosejohn elproblemadelmulticubrimientounaaplicacionparalaselecciondeparadasenlareddetransportedelaciudaddemexico
_version_	1811744064509313024

El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México

Ejemplares similares