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
Страницы81-94
Число страниц14
ISBN (печатное издание)9783030449315
DOI
СостояниеОпубликовано - 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
СтранаМорокко
ГородRabat
Период03.10.201905.10.2019

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

  • Цитировать

    Davydov, I., & Gusev, P. (2020). Local Search Approach for the (r|p)-Centroid Problem Under ℓ1 Metric. В R. Benmansour, A. Sifaleras, & N. Mladenovic (Ред.), Variable Neighborhood Search - 7th International Conference, ICVNS 2019, Revised Selected Papers (стр. 81-94). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12010 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-44932-2_6