Computational Geometry and Heuristic Approaches for Location Problems

DOI

10.2991/eame-15.2015.152How to use a DOI?

Keywords

computational geometry; location-based service (LBS)

Abstract

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 functions, determining what we consider in these tasks as optimal. While maximizing the coverage of an area by supermarkets, we choose 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 we use a genetic algorithm approach and special attention is paid to implementation of a repair operator for infeasible solutions gen-erated by the operations of crossover and mutation.

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - M. Seda
PY  - 2015/07
DA  - 2015/07
TI  - Computational Geometry and Heuristic Approaches for Location Problems
BT  - Proceedings of the 2015 International Conference on Electrical, Automation and Mechanical Engineering
PB  - Atlantis Press
SP  - 539
EP  - 543
SN  - 2352-5401
UR  - https://doi.org/10.2991/eame-15.2015.152
DO  - 10.2991/eame-15.2015.152
ID  - Seda2015/07
ER  -