Detail publikace
Minimalizace sítě servisních středisek s předdefinovanými centry
ŠEDA, M. ŠEDA, P.
Český název
Minimalizace sítě servisních středisek s předdefinovanými centry
Anglický název
Minimisation of Network Covering Services with Predefined Centres
Typ
článek ve sborníku ve WoS nebo Scopus
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. 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.
Český abstrakt
V tomto příspěvku se zabýváme speciální verzí problému pokrytí, 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ší jednotky, jako jsou městké části) v přiměřené vzdálenosti do dané horní meze. Jestliže lze najít prahovou hodnotu, pro niž lze najít přípustné řešení, problém se nabývá obecné podoby. Avšak vzhledem ke kombinatorické povaze problému a jeho přískušnosti do třídy NP-těžkých problémů pro velké instance nelze najít otpimální řešení v dostupném čase. V příspěvku je prezentováno řešení, které využívá dvě heuristické metody: genetický algoritmus a zakázané prohledávání.
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. 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.
Klíčová slova česky
problém pokrytí, problém bez zohlednění vah, práh, matice dostupnosti, genetický algoritmus, opravný operátor
Klíčová slova anglicky
Set covering, unicost problem, threshold, reachability matrix, genetic algorithm, repair operator
Vydáno
22.05.2018
Nakladatel
European Council for Modelling and Simulation
Místo
Wilhelmshaven (Germany)
ISBN
978-0-9932440-6-3
ISSN
2522-2414
Kniha
Proceedings of the 32nd European Conference on Modelling and Simulation ECMS 2018
Ročník
2018
Číslo
1
Strany od–do
282–287
Počet stran
6
BIBTEX
@inproceedings{BUT149158,
author="Miloš {Šeda} and Pavel {Šeda},
title="Minimisation of Network Covering Services with Predefined Centres",
booktitle="Proceedings of the 32nd European Conference on Modelling and Simulation ECMS 2018",
year="2018",
volume="2018",
number="1",
month="May",
pages="282--287",
publisher="European Council for Modelling and Simulation",
address="Wilhelmshaven (Germany)",
isbn="978-0-9932440-6-3",
issn="2522-2414"
}