Local Search Approach for the (r|p)-Centroid Problem Under ℓ1 Metric

Ivan Davydov, Petr Gusev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review


In the-centroid problem, two players, called the Leader and the Follower, open facilities to service customers. We assume that customers are identified with their location on the plane, and facilities can be opened anywhere on the plane. The Leader opens p facilities. Later on, the Follower opens r facilities. Each customer patronizes the closest facility. The distances are calculated according to-metric. The goal is to find the location of the Leader’s facilities maximizing her market share. We provide the results on the computational complexity of this problem and develop a local search heuristic, based on the VNS framework. Computational experiments on the randomly generated test instances show that the proposed approach performs well.

Original languageEnglish
Title of host publicationVariable Neighborhood Search - 7th International Conference, ICVNS 2019, Revised Selected Papers
EditorsRachid Benmansour, Angelo Sifaleras, Nenad Mladenovic
PublisherSpringer Gabler
Number of pages14
ISBN (Print)9783030449315
Publication statusPublished - 1 Jan 2020
Event7th International Conference on Variable Neighborhood Search, ICVNS 2019 - Rabat, Morocco
Duration: 3 Oct 20195 Oct 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12010 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Variable Neighborhood Search, ICVNS 2019


  • (R-P)-centroid
  • Bilevel programming
  • Facility location
  • Manhattan metric
  • Stackelberg game
  • Variable neighborhood search


Dive into the research topics of 'Local Search Approach for the (r|p)-Centroid Problem Under ℓ1 Metric'. Together they form a unique fingerprint.

Cite this