Detail publikace

Computational Geometry and Heuristic Approaches for Location Problems

ŠEDA, M.

Originální název

Computational Geometry and Heuristic Approaches for Location Problems

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

In this paper we deal with two problems, whose common basis is to find the location of a service center for potential customers, but with different criterion function, determining what we consider in these tasks as optimal. While maximizing the coverage of an area by supermarkets, we choose for a new supermarket the location that minimises interaction (and thus competition) with existing supermarkets. On the contrary, if we want to provide the availability of certain services for all customers within a reasonable distance, and yet we know in advance where it would be possible to set up servicing points, the goal is to minimize their number. We show that the first type of problem can be solved in polynomial time using the Voronoi diagram, the task of the second type leads to the set covering problem, which is an NP-hard problem, and it is therefore necessary to solve larger instances of a task by heuristics. It is proposed using a genetic algorithm approach and special attention is paid to implementation of a repair operator for infeasible solutions generated by the operations of crossover and mutation.

Klíčová slova

location problem, Voronoi diagram, set covering, stochastic heuristics, genetic algorithm

Autoři

ŠEDA, M.

Rok RIV

2015

Vydáno

1. 5. 2015

Nakladatel

Atlantis Press

Místo

Phuket, Thailand

ISBN

9789462520714

Kniha

K. Chan, J. Yeh (eds.): Proceedings of the International Conference of Electrical, Automation and Mechanical Engineering EAME 2015

Edice

Advances in Engineering Research

Číslo edice

1.

Strany od

545

Strany do

549

Strany počet

5

URL

Plný text v Digitální knihovně

BibTex

@inproceedings{BUT119406,
  author="Miloš {Šeda}",
  title="Computational Geometry and Heuristic Approaches for Location Problems",
  booktitle="K. Chan, J. Yeh (eds.): Proceedings of the International Conference of Electrical, Automation and Mechanical Engineering EAME 2015",
  year="2015",
  series="Advances in Engineering Research",
  number="1.",
  pages="545--549",
  publisher="Atlantis Press",
  address="Phuket, Thailand",
  doi="10.2991/eame-15.2015.152",
  isbn="9789462520714",
  url="https://www.atlantis-press.com/proceedings/eame-15/22364"
}