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

Ivan Davydov, Petr Gusev

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


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.

Язык оригиналаанглийский
Название основной публикацииVariable Neighborhood Search - 7th International Conference, ICVNS 2019, Revised Selected Papers
РедакторыRachid Benmansour, Angelo Sifaleras, Nenad Mladenovic
ИздательSpringer Gabler
Число страниц14
ISBN (печатное издание)9783030449315
СостояниеОпубликовано - 1 янв. 2020
Событие7th International Conference on Variable Neighborhood Search, ICVNS 2019 - Rabat, Морокко
Продолжительность: 3 окт. 20195 окт. 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12010 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция7th International Conference on Variable Neighborhood Search, ICVNS 2019


Подробные сведения о темах исследования «Local Search Approach for the (r|p)-Centroid Problem Under ℓ1 Metric». Вместе они формируют уникальный семантический отпечаток (fingerprint).