Minimalizace sítě pokrývající služby do prahové vzdálenosti

A Minimisation of Network Covering Services in a Threshold Distance

book chapter

en

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.

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.

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.

problém pokrytí, problém s jednotkovými vahami, matice dostupnosti, genetický algoritmus, opravný operátor

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

2015

01.06.2015

Springer

Heidelberg, Germany

978-3-319-19823-1

Recent Advances in Soft Computing

1.

159–169

11