Metaheuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem

Roman Plotnikov, Adil Erzin

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

Аннотация

We consider a Min-Power Bounded-Hops Symmetric Connectivity problem that consists in the construction of communication spanning tree on a given graph, where the total energy consumption spent for the data transmission is minimized and the maximum number of edges in a path in the tree between any pair nodes is bounded by some predefined constant. We focus on the planar Euclidian case of this problem where the power cost necessary for the communication between two network elements is proportional to the squared distance between them. Since this is an NP-hard problem, we propose different heuristics based on the following metaheuristics: genetic local search, variable neighborhood search, and ant colony optimization. We perform a posteriori comparative analysis of the proposed algorithms and present the obtained results in this paper.

Язык оригиналаанглийский
Название основной публикацииLearning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers
РедакторыNikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos
ИздательSpringer Gabler
Страницы355-369
Число страниц15
ISBN (печатное издание)9783030386283
DOI
СостояниеОпубликовано - 1 янв 2020
Событие13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Греция
Продолжительность: 27 мая 201931 мая 2019

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

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

Конференция

Конференция13th International Conference on Learning and Intelligent Optimization, LION 13
СтранаГреция
ГородChania
Период27.05.201931.05.2019

Fingerprint Подробные сведения о темах исследования «Metaheuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Plotnikov, R., & Erzin, A. (2020). Metaheuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem. В N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Ред.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (стр. 355-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_29