Minimisation of Network Covering Services with Predefined Centres

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F18%3APU128638" target="_blank" >RIV/00216305:26210/18:PU128638 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.7148/2018-0282" target="_blank" >http://dx.doi.org/10.7148/2018-0282</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.7148/2018-0282" target="_blank" >10.7148/2018-0282</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Minimisation of Network Covering Services with Predefined Centres

Popis výsledku v původním jazyce

In this paper, we deal with a special version of the set covering problem, which consists in finding the minimum number of service centres providing specialized services for all customers (or larger units, such as urban areas) within a reasonable distance given by a threshold. If a suitable threshold is found that makes it possible to determine a feasible solution of the task, the task is transformed into a general set covering problem. In order to reflect the importance of the centers, we assign weights to them and, if some centers must be contained in the result, we can either add columns in the reachability matrix with link to these centres or add special constraints in the mathematical model. However, this is of a combinatorial nature and, because it belongs to the class of NP-hard problems, for a large instance of the problem, it cannot be used to and the optimal solution in a reasonable amount of time. In the paper, we present a solution that uses two heuristic methods: genetic algorithm and tabu search.

Název v anglickém jazyce

Minimisation of Network Covering Services with Predefined Centres

Popis výsledku anglicky

In this paper, we deal with a special version of the set covering problem, which consists in finding the minimum number of service centres providing specialized services for all customers (or larger units, such as urban areas) within a reasonable distance given by a threshold. If a suitable threshold is found that makes it possible to determine a feasible solution of the task, the task is transformed into a general set covering problem. In order to reflect the importance of the centers, we assign weights to them and, if some centers must be contained in the result, we can either add columns in the reachability matrix with link to these centres or add special constraints in the mathematical model. However, this is of a combinatorial nature and, because it belongs to the class of NP-hard problems, for a large instance of the problem, it cannot be used to and the optimal solution in a reasonable amount of time. In the paper, we present a solution that uses two heuristic methods: genetic algorithm and tabu search.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 32nd European Conference on Modelling and Simulation ECMS 2018

ISBN

978-0-9932440-6-3

ISSN

2522-2414

e-ISSN

—

Počet stran výsledku

6

Strana od-do

282-287

Název nakladatele

European Council for Modelling and Simulation

Místo vydání

Wilhelmshaven (Germany)

Místo konání akce

Wilhelmshaven, Germany

Datum konání akce

22. 5. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000656119000041