Revista de Matemática: Teoría y Aplicaciones (Feb 2009)

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

DOI
https://doi.org/10.15517/rmta.v10i1-2.230
Journal volume & issue
Vol. 10, no. 1-2
pp. 147 – 155

Abstract

Read online

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. Keywords: Multicover problem, heuristic methods, greedy algorithms, combinatorial optimization.