Ir al contenido

Documat


The Single Period Coverage Facility Location Problem:: Lagrangean heuristic and column generation approaches

  • Maria Albareda-Sambola [1] ; Elena Fernández [1] ; Yolanda Hinojosa [2] ; Justo Puerto [2]
    1. [1] Universitat Politècnica de Catalunya

      Universitat Politècnica de Catalunya

      Barcelona, España

    2. [2] Universidad de Sevilla

      Universidad de Sevilla

      Sevilla, España

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 18, Nº. 1, 2010, págs. 43-61
  • Idioma: inglés
  • Enlaces
  • Resumen
    • In this paper we introduce the Single Period Coverage Facility Location Problem. It is a multi-period discrete location problem in which each customer is serviced in exactly one period of the planning horizon. The locational decisions are made independently for each period, so that the facilities that are open need not be the same in different time periods. It is also assumed that at each period there is a minimum number of customers that can be assigned to the facilities that are open. The decisions to be made include not only the facilities to open at each time period and the time period in which each customer will be served, but also the allocation of customers to open facilities in their service period.

      We propose two alternative formulations that use different sets of decision variables. We prove that in the first formulation the coefficient matrix of the allocation subproblem that results when fixing the facilities to open at each time period is totally unimodular. On the other hand, we also show that the pricing problem of the second model can be solved by inspection. We prove that a Lagrangean relaxation of the first one yields the same lower bound as the LP relaxation of the second one. While the Lagrangean dual can be solved with a classical subgradient optimization algorithm, the LP relaxation requires the use of column generation, given the large number of variables of the second model. We compare the computational burden for obtaining this lower bound through both models.


Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno