Article
VNS heuristic for the (r|p)-centroid problem on the plane
Author/s | Daydov, Ivan
Kochetov, Yuri Carrizosa Priego, Emilio José |
Department | Universidad de Sevilla. Departamento de Estadística e Investigación Operativo |
Publication Date | 2012-12-01 |
Deposit Date | 2021-04-15 |
Published in |
|
Abstract | In the (r | p)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidean plane, and facilities can be opened ... In the (r | p)-centroid problem, two players, called leader and follower, open facilities to service clients. We assume that clients are identified with their location on the Euclidean plane, and facilities can be opened anywhere in the plane. The leader opens p facilities. Later on, the follower opens r facilities. Each client patronizes the closest facility. Our goal is to find p facilities for the leader to maximize his market share. For this ΣP2-hard problem we develop the VNS heuristic, based on the exact approach for the follower problem. We apply the (r | Xp−1+1)-centroid subproblem for finding the best neighboring solution according to the swap neighborhood. It is shown that this subproblem is polynomially solvable for fixed r. Computational experiments for the randomly generated test instances show that the VNS heuristic dominates the previous ones. |
Citation | Daydov, I., Kochetov, Y. y Carrizosa Priego, E.J. (2012). VNS heuristic for the (r|p)-centroid problem on the plane. Electronic Notes In Discrete Mathematics, 39 (1), 5-12. |
Files | Size | Format | View | Description |
---|---|---|---|---|
VNS heuristic for the (rp)-centroid ... | 311.1Kb | [PDF] | View/ | |