Section 4

A Variable Neighborhood Heuristic for Facility Locations in Fog Computing

Thiago Alves de Queiroz, Claudia Canali, Manuel Iori, Riccardo Lancellotti

The current trend of the modern smart cities applications towards a continuous increase in the volume of produced data and the concurrent need for low and predictable latency in the response time has motivated the shift from a cloud to a fog computing approach. A fog computing architecture is likely to represent a preferable solution to reduce the application latency and the risk of network congestion by decreasing the volume of data transferred to cloud data centers. However, the design of a fog infrastructure opens new issues concerning not only how to allocate the data flow coming from sensors to fog nodes and from there to cloud data centers, but also the choice of the number and the location of the fog nodes to be activated among a list of potential candidates. We model this facility location issue through a multi-objective optimization problem. We propose a heuristic based on the variable neighborhood search, where neighborhood structures are based on swap and move operations. The proposed method is tested in a wide range of scenarios, considering a smart city application's realistic setup with geographically distributed sensors. The experimental evaluation shows that our method can achieve stable and better performance concerning other literature approaches, supporting the given application.

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

Variable Neighborhood Descent Branching applied to the Green Electric Vehicle Routing Problem with Time Window and Mixed Fleet

Thiago Stehling, Marcone Jamilson Freitas Souza, Sérgio Ricardo de Souza

This paper deals with the Green Electric Vehicle Routing Problem with Time Window and Mixed Fleet and presents a Mixed Integer Linear Programming formulation for it. Initially, we applied the CPLEX solver in this formulation. Then, to reduce the computational time, we used Local Branching and Variable Neighborhood Descent Branching (VNDB) methods. We did computational experiments with a simple adaptation of the 100-customers Solomon's benchmark instances. The results showed that the three solution strategies reached the optimal solution. However, the running time of the VNDB is considerably smaller than those required by the other two solution methods. Therefore, this fact proves that the VNDB is the more efficient technique in the tested scenario.

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

Sequential and Parallel Scattered Variable Neighborhood Search for Solving Nurikabe

Paul Bass, Aise Sevkli

Japanese pencil games have been the subjects of innumerable papers. However, some problems - like Sudoku - receive far more attention than others - like Nurikabe. In this paper we propose a novel algorithm to solve Nurikabe puzzles. We first introduce a sequential hybrid algorithm that we call Scattered Variable Neighborhood Search. We then propose a method of parallelizing this algorithm, examining the empirical benefits of parallelization. We conclude that our parallel implementation performs best in almost all scenarios.

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