Genetic algorithm based approach for serving maximum number of customers using limited resources

Soumen Atta (Avtor), Priya Ranjan Sinha Mahapatra (Avtor)

Povzetek

It is often needed to install limited number of facilities to address the demand of customers due to resource constraints and thus the requirement to provide service to all customers is not possible to meet. In such situation, the facilities are installed (placed) so that the maximum demand can be met. The problem of installing (locating) such facilities are known as Maximal Covering Location Problem (MCLP) [2] in facility location [1]. We assume that (i) all facilities are in a plane, and (ii) all customers can be considered as a point set on the same plane. The type of covering area (or range) of a facility depends on the facility to be installed. We consider the MCLP where the covering area (or range) of each facility is the area of a square with fixed size. In other words here, each facility is installed at the center of the square. The problem considered in this article is defined as follows: given a set P of n input points (customers) on the plane and k squares (facilities) each of fixed size, the objective is to find a placement of k squares so that the union of k axis parallel squares covers (contains) the maximum numbers of input points where k (1≤k≤n) is a positive integer constant. This problem is known to be NP-hard [5]. We have proposed a genetic algorithm (GA) to solve this problem.

Ključne besede

maximal covering location problem;facility location;genetic algorithm;

Podatki

Jezik:	Angleški jezik
Leto izida:	2013
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UNG - Univerza v Novi Gorici
UDK:	004
COBISS:	154452995
ISSN:	2212-0173
Št. ogledov:	50
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

URN:	URN:SI:UNG
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 492-497
Zvezek:	ǂVol. ǂ10
Čas izdaje:	2013
DOI:	https://doi.org/10.1016/j.protcy.2013.12.387.
ID:	19159997