License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SCOR.2014.25
URN: urn:nbn:de:0030-drops-46676
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4667/
Go to the corresponding OASIcs Volume Portal

Bendík, Ján

Solving the p-median location problem with the Erlenkotter approach in public service system design

pdf-format:
4.pdf (0.6 MB)

Abstract

The problem can be often formulated as a weighted p-median problem. Real instances of the problem are characterized by big numbers of possible service center locations, which can take the value of several hundreds or thousands. The optimal solution can be obtained by the universal IP solvers only for smaller instances of the problem. The universal IP solvers are very time-consuming and often fail when solving a large instance. Our approach to the problem is based on the Erlenkotter procedure for solving of the uncapacitated facility location problem and on the Lagrangean relaxation of the constraint which limits number of the located center. The suggested approach finds the optimal solution in most of the studied instances. The quality and the feasibility of the resulting solutions of the suggested approach depend on the setting of the Lagrangean multiplier. A suitable value of the multiplier can be obtained by a bisection algorithm. The resulting multiplier cannot guarantee an optimal solution, but provides a near-to-optimal solution and a lower bound. If our approach does not obtain the optimal solution, then a heuristic improves the near-to-optimal solution. The resulting solution of our approach and the optimal solution obtained by the universal IP solver XPRESS-IVE are compared in the computational time and the quality of solutions.

BibTeX - Entry

@InProceedings{bendk:OASIcs:2014:4667,
  author =	{J{\'a}n Bend{\'i}k},
  title =	{{Solving the p-median location problem with the Erlenkotter approach in public service system design}},
  booktitle =	{4th Student Conference on Operational Research},
  pages =	{25--33},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-67-5},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{37},
  editor =	{Pedro Crespo Del Granado and Martim Joyce-Moniz and Stefan Ravizza},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4667},
  URN =		{urn:nbn:de:0030-drops-46676},
  doi =		{10.4230/OASIcs.SCOR.2014.25},
  annote =	{Keywords: p-median location problem, Erlenkotter's approach, Lagrangean relaxation}
}

Keywords: p-median location problem, Erlenkotter's approach, Lagrangean relaxation
Collection: 4th Student Conference on Operational Research
Issue Date: 2014
Date of publication: 06.08.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI