Algebraic solution of weighted minimax single-facility constrained location problems

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

2 Цитирования (Scopus)

Аннотация

We consider location problems to find the optimal sites of placement of a new facility, which minimize the maximum weighted Chebyshev or rectilinear distance to existing facilities under constraints on the feasible location domain. We examine a Chebyshev location problem in multidimensional space to represent and solve the problem in the framework of tropical (idempotent) algebra, which deals with the theory and applications of semirings and semifields with idempotent addition. The solution approach involves formulating the problem as a tropical optimization problem, introducing a parameter that represents the minimum value in the problem, and reducing the problem to a system of parametrized inequalities. The necessary and sufficient conditions for the existence of a solution to the system serve to evaluate the minimum, whereas all corresponding solutions of the system present a complete solution of the optimization problem. With this approach, we obtain a direct, exact solution represented in a compact closed form, which is appropriate for further analysis and straightforward computations with polynomial time complexity. The solution of the Chebyshev problem is then used to solve a location problem with rectilinear distance in the two-dimensional plane. The obtained solutions extend previous results on the Chebyshev and rectilinear location problems without weights.
Язык оригиналаанглийский
Название основной публикацииRelational and Algebraic Methods in Computer Science - 17th International Conference, RAMiCS 2018, Proceedings
Подзаголовок основной публикации17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29 – November 1, 2018, Proceedings
РедакторыWalter Guttmann, Jules Desharnais, Stef Joosten
Место публикацииCham
ИздательSpringer Nature
Глава19
Страницы317-332
Число страниц16
ISBN (электронное издание)978-3-030-02149-8
ISBN (печатное издание)978-3-030-02148-1
DOI
СостояниеОпубликовано - окт 2018
СобытиеThe 17th International Conference on Relational and Algebraic Methods in Computer Science - Open University of The Netherlands, Groningen, Голландия
Продолжительность: 29 окт 20181 ноя 2018
Номер конференции: 17
http://www.ramics-conference.org/

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

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

конференция

конференцияThe 17th International Conference on Relational and Algebraic Methods in Computer Science
Сокращенный заголовокRAMiCS
СтранаГолландия
ГородGroningen
Период29/10/181/11/18
Адрес в сети Интернет

Предметные области Scopus

  • Теория оптимизации
  • Алгебра и теория чисел
  • Теория управления и исследование операций
  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Algebraic solution of weighted minimax single-facility constrained location problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать