Section 8

Variable Neighborhood Search Algorithm for Radio Communication System Planning Problem with Reliability

Tatiana Levanova, Stanislav Belan

The importance of telecommunications for navigation, research, and other purposes is noted in many countries of the Arctic region. For a number of reasons, it is proposed to use radio communication by both High frequency and Medium frequency transmission to forward information. High-frequency transmitters are located far away on the continental territory and transmit a signal to Medium frequency transmitters that are located near consumers in the Far North. To solve this problem, mathematical models of the discrete location problem can be built taking into account various features of radio communications. In this paper, one such model is considered including the reliability of the information transmission network. It describes the situation when clients should receive a signal with some given reliability. In order to solve this problem, an original variable neighborhood search algorithm was built. Special neighborhoods were proposed, and a series of test cases were formed. Experimental studies were carried out, their results were analyzed.

Scheduling of Patients in Emergency Departments with a Variable Neighborhood Search

Thiago Alves de Queiroz, Manuel Iori, Arthur Kramer, Yong-Hong Kuo

The dynamic scheduling of patients to doctors in an emergency department environment is tackled in this work. We consider the case in which patients arrive dynamically during the working hours, and the objective is to minimize the weighted tardiness. We propose a greedy heuristic based on priority queues and a general variable neighborhood search (GVNS). In the greedy heuristic, patients are scheduled by observing their urgency, while in the GVNS, the schedule is optimized every time a patient arrives. The GVNS uses six neighborhood structures and a variable neighborhood descent to perform the local search. The GVNS also handles the static problem whose solution can be used as a reference for the dynamic one. Computational results on 80 instances show that using the GVNS better approximates the static problem, besides giving an overall reduction of 66.8 percentage points over the greedy heuristic.

DOI: 10.1007/978-3-030-69625-2_11

A GRASP/VND Heuristic for the Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability

Sebastián Laborde, Franco Robledo, Pablo Romero, Omar Viera

The object under study is a combinatorial optimization problem motivated by the topological network design of communication systems, meeting reliability constraints. Specifically, we introduce the Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability, or GSPNCHR for short. Since the GSPNCHR belongs to the class of NP-Hard problems, approximative algorithms are adequate for medium and large-sized networks. As a consequence, we develop a GRASP/VND methodology. The VND includes three local searches, that replace special elementary paths or trees, preserving feasibility. Our goal is to find a minimum-cost solution, meeting a reliability threshold, where both nodes and links may fail with given probabilities. We adapted TSPLIB benchmark in order to highlight the effectiveness of our proposal. The results suggest that our heuristic is cost-effective, providing highly-reliable networks.

DOI: 10.1007/978-3-030-69625-2_4

Variable Neighborhood Search for Group Steiner Tree Problem

Tatjana Davidović, Slobodan Jelić, and Luka Matijević

We consider the graph $G = (V,E)$, with a non-negative weight function $w:E \rightarrow R$. Let $G_1, \ldots, G_k$ be arbitrary subsets of $V$ called groups. The main objective in Group Steiner Tree (GST) problem is to find a minimum cost tree $T =(V_T,E_T)$ where $V_T \subseteq V$ and $E_T \subseteq E$ such that it spans at least one vertex from each of the groups. This problem is known to be NP-hard as it generalizes two well-known NP-hard problems: Steiner Tree and Set Cover. Combining different types of neighborhoods, we develop a Variable Neighborhood Descent (VND) algorithm that represents the main ingredient of several local search-based metaheuristics. We also discuss the combination of some standard search techniques to traverse neighbor solutions with an efficient update of the minimum spanning tree on the (dynamically changed) set of vertices. Changes in the set of vertices are the consequence of multiple (stochastic and deterministic) vertex addition/removal. Several preprocessing techniques are applied to GST instances to significantly reduce their size. Experimental results on several benchmark examples evaluate the performance of our approach in comparison with exact approaches based on Integer Linear Programming (ILP) solvers and other metaheuristics, such as genetic programming.