Přístupnostní navigace
E-application
Search Search Close
Publication detail
ŠEDA, M. ŠEDA, P.
Original Title
Minimisation of Network Covering Services with Predefined Centres
Type
conference paper
Language
English
Original Abstract
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.
Keywords
Set covering, unicost problem, threshold, reachability matrix, genetic algorithm, repair operator
Authors
ŠEDA, M.; ŠEDA, P.
Released
22. 5. 2018
Publisher
European Council for Modelling and Simulation
Location
Wilhelmshaven (Germany)
ISBN
978-0-9932440-6-3
Book
Proceedings of the 32nd European Conference on Modelling and Simulation ECMS 2018
2522-2414
Periodical
ECMS
Year of study
2018
Number
1
State
Federal Republic of Germany
Pages from
282
Pages to
287
Pages count
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", journal="ECMS", volume="2018", number="1", pages="282--287", publisher="European Council for Modelling and Simulation", address="Wilhelmshaven (Germany)", doi="10.7148/2018-0282", isbn="978-0-9932440-6-3", issn="2522-2414" }