Tesis profesional presentada por Luis Oswaldo Valencia Rosado [luis.valenciaro@udlap.mx]

Maestría en Ciencias en Ingeniería Industrial con área de concentración en Optimización y Sistemas Logísticos. Departamento de Ingeniería Industrial y Mecánica. Escuela de Ingeniería, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Dr. Juan Antonio Díaz García
Vocal y Director: Dra. Dolores Edwiges Luna Reyes
Secretario: Dra. Carmen Xóchitl Flores Mendoza

Cholula, Puebla, México a 15 de mayo de 2015.

Resumen

The Capacitated p-median Problem (CPMP) is a facility location problem and as such, it can be used for partitioning geographical areas. The goal is to set a certain number (p) of facilities and to assign users to them in such way that the sum of the distances between the users and the facility is minimized, having in mind that those facilities are limited in capacity. In this work combinatorial techniques were used to provide primal and dual bounds for this...

Palabras clave: optimization, capaciated p-median problem, CPMP, heuristics for facility location problems, Lagrangean relaxation.

Resumen (archivo pdf, 502 kb).

Índice de contenido

Índices (archivo pdf, 367 kb)

Capítulo 1. Introduction (archivo pdf, 520 kb)

Capítulo 2. Literature Review (archivo pdf, 522 kb)

Capítulo 3. Theoritical Framework (archivo pdf, 551 kb)

  • 3.1 Mathematical formulation of the problem
  • 3.2 Relaxation of an optimization problem
  • 3.3 The subgradient method of optimization
  • 3.4 Decomposition
  • 3.5 The Knapsack Problem
  • 3.6 The Generalized Assignment Problem

Capítulo 4. Methodology (archivo pdf, 774 kb)

  • 4.1 Lagrangean Relaxation for the CPMP
  • 4.2 First Approach: Lagrangean Heuristic for the Capacitated P-Median Problem
  • 4.3 Second Approach: Cluster Median Improvement Heuristic

Capítulo 5. Computational Experience (archivo pdf, 725 kb)

Capítulo 6. Conclusions and future work (archivo pdf, 386 kb)

Referencias (archivo pdf, 375 kb)

Valencia Rosado, L. O. 2015. Primal and dual bounds for the capaciated p-median problem obtained by a lagrangean heuristic and a cluster median improvement heuristic. Tesis Maestría. Ciencias en Ingeniería Industrial con área de concentración en Optimización y Sistemas Logísticos. Departamento de Ingeniería Industrial y Mecánica, Escuela de Ingeniería, Universidad de las Américas Puebla. Mayo. Derechos Reservados © 2015.