Detail publikačního výsledku

A Minimisation of Network Covering Services in a Threshold Distance

ŠEDA, M.; ŠEDA, P.

Originální název

A Minimisation of Network Covering Services in a Threshold Distance

Anglický název

A Minimisation of Network Covering Services in a Threshold Distance

Druh

Kapitola, resp. kapitoly v odborné knize

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.

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

Set covering, unicost problem, threshold, reachability matrix, genetic algorithm, repair operator

Klíčová slova v angličtině

Set covering, unicost problem, threshold, reachability matrix, genetic algorithm, repair operator

Autoři

ŠEDA, M.; ŠEDA, P.

Rok RIV

2016

Vydáno

01.06.2015

Nakladatel

Springer

Místo

Heidelberg, Germany

ISBN

978-3-319-19823-1

Kniha

Recent Advances in Soft Computing

Edice

Advances in Intelligent Systems and Computing

Strany od

159

Strany do

169

Strany počet

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",
  publisher="Springer",
  address="Heidelberg, Germany",
  series="Advances in Intelligent Systems and Computing",
  edition="1.",
  pages="159--169",
  isbn="978-3-319-19823-1"
}