Detail publikace
Minimalizace sítě pokrývající služby do prahové vzdálenosti
ŠEDA, M. ŠEDA, P.
Český název
Minimalizace sítě pokrývající služby do prahové vzdálenosti
Anglický název
A Minimisation of Network Covering Services in a Threshold Distance
Typ
kapitola v knize
Jazyk
en
Originální abstrakt
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. However, this has 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 find the optimal solution in a reasonable amount of time. In the paper, we present a solution by means of two stochastic heuristic methods – genetic algorithms and simulated annealing – and, using a test instance from OR-Library, we present the parameter settings of both methods and the results achieved.
Český abstrakt
V tomto příspěvku se zabýváme speciální verze problému pokrýtí, který spočívá v nalezení minimálního počtu servisních středisek zajišťujících specializované služby pro všechny zákazníky (nebo větší celky, jako jsou městské oblasti) v přiměřené vzdálenosti do dané horní meze. Jestliže je nalezena vhodná prahová hodnota, která umožňuje určit přípustné řešení úlohy, pak se úloha transformuje na obecný problém pokrytí. Avšak vzhledem ke kombinatorické povaze úlohy a skutečnosti, že patří do třídy NP-těžkých problémů, pro velké instance problému, nelze najít optimálního řešení v rozumném čase. V příspěvku je uvádíme řešení pomocí dvou stochastických heuristických metod – genetických algoritmů a simulovaného žíhání – a s využitím benchmarků z OR-Library, a prezentujeme nastavení parametrů obou metod a jimi dosažené výsledky.
Anglický abstrakt
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. However, this has 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 find the optimal solution in a reasonable amount of time. In the paper, we present a solution by means of two stochastic heuristic methods – genetic algorithms and simulated annealing – and, using a test instance from OR-Library, we present the parameter settings of both methods and the results achieved.
Klíčová slova česky
problém pokrytí, problém s jednotkovými vahami, matice dostupnosti, genetický algoritmus, opravný operátor
Klíčová slova anglicky
Set covering, unicost problem, threshold, reachability matrix, genetic algorithm, repair operator
Rok RIV
2015
Vydáno
01.06.2015
Nakladatel
Springer
Místo
Heidelberg, Germany
ISBN
978-3-319-19823-1
Kniha
Recent Advances in Soft Computing
Číslo edice
1.
Strany od–do
159–169
Počet stran
11
BIBTEX
@inbook{BUT119299,
author="Miloš {Šeda} and Pavel {Šeda},
title="A Minimisation of Network Covering Services in a Threshold Distance",
booktitle="Recent Advances in Soft Computing",
year="2015",
month="June",
pages="159--169",
publisher="Springer",
address="Heidelberg, Germany",
isbn="978-3-319-19823-1"
}