G-2019-61
The conditional \(p\)-dispersion problem
et référence BibTeX
We introduce the conditional \(p\)
-dispersion problem (c-pDP), an incremental variant of the \(p\)
-dispersion problem (pDP). In the c-pDP, one is given a set \(N\)
of \(n\)
points, a symmetric dissimilarity matrix \(D\)
of dimensions \(n\times n\)
, an integer \(p\geq 1\)
and a set \(Q\subseteq N\)
of cardinality \(q\geq 1\)
. The objective is to select a set \(P\subset N\setminus Q\)
of cardinality \(p\)
that maximizes the minimal dissimilarity between every pair of selected vertices, i.e., \(z(P\cup Q) ≔ \min\{D(i, j), i, j\in P\cup Q\}\)
. The set \(Q\)
may model a predefined subset of preferences or hard location constraints in incremental network design. We adapt the state-of-the-art algorithm for the pDP to the c-pDP and include ad-hoc acceleration mechanisms designed to take advantage of the information provided by the set \(Q\)
. We perform exhaustive computational experiments and show that the proposed acceleration mechanisms help reduce the total computational time by a large margin. We also assess the scalability of the algorithm and derive managerial insights regarding the value of building a network from scratch compared to an incremental design.
Paru en août 2019 , 40 pages