License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.30
URN: urn:nbn:de:0030-drops-190679
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19067/
Go to the corresponding LIPIcs Volume Portal

Ploskas, Nikolaos ; Stergiou, Kostas ; Tsouros, Dimosthenis C.

The p-Dispersion Problem with Distance Constraints

pdf-format:
LIPIcs-CP-2023-30.pdf (0.7 MB)

Abstract

In the (maxmin) p-dispersion problem we seek to locate a set of facilities in an area so that the minimum distance between any pair of facilities is maximized. We study a variant of this problem where there exist constraints specifying the minimum allowed distances between the facilities. This type of problem, which we call PDDP, has not received much attention within the literature on location and dispersion problems, despite its relevance to real scenarios. We propose both ILP and CP methods to solve the PDDP. Regarding ILP, we give two formulations derived from a classic and a state-of-the-art model for p-dispersion, respectively. Regarding CP, we first give a generic model that can be implemented within any standard CP solver, and we then propose a specialized heuristic Branch&Bound method. Experiments demonstrate that the ILP formulations are more efficient than the CP model, as the latter is unable to prove optimality in reasonable time, except for small problems, and is usually slower in finding solutions of the same quality than the ILP models. However, although the ILP approach displays good performance on small to medium size problems, it cannot efficiently handle larger ones. The heuristic CP-based method can be very efficient on larger problems and is able to quickly discover solutions to problems that are very hard for an ILP solver.

BibTeX - Entry

@InProceedings{ploskas_et_al:LIPIcs.CP.2023.30,
  author =	{Ploskas, Nikolaos and Stergiou, Kostas and Tsouros, Dimosthenis C.},
  title =	{{The p-Dispersion Problem with Distance Constraints}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19067},
  URN =		{urn:nbn:de:0030-drops-190679},
  doi =		{10.4230/LIPIcs.CP.2023.30},
  annote =	{Keywords: Facility location, distance constraints, optimization}
}

Keywords: Facility location, distance constraints, optimization
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

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