Skip to main content

Research Repository

Advanced Search

Performance analysis of GA and PBIL variants for real-world location-allocation problems.

Ankrah, Reginald; Regnier-Coudert, Olivier; McCall, John; Conway, Anthony; Hardwick, Andrew

Authors

Reginald Ankrah

Olivier Regnier-Coudert

Anthony Conway

Andrew Hardwick



Abstract

The Uncapacitated Location-Allocation problem (ULAP) is a major optimisation problem concerning the determination of the optimal location of facilities and the allocation of demand to them. In this paper, we present two novel problem variants of Non-Linear ULAP motivated by a real-world problem from the telecommunication industry: Uncapacitated Location-Allocation Resilience problem (ULARP) and Uncapacitated Location-Allocation Resilience problem with Restrictions (ULARPR). Problem sizes ranging from 16 to 100 facilities by 50 to 10000 demand points are considered. To solve the problems, we explore the components and configurations of four Genetic Algorithms [1], [2], [3] and [4] selected from the ULAP literature. We aim to understand the contribution each choice makes to the GA performance and so hope to design an Optimal GA configuration for the novel problems.We also conduct comparative experiments with Population-Based Incremental Learning (PBIL) Algorithm on ULAP. We show the effectiveness of PBIL and GA with parameter set: random and heuristic initialisation, tournament and fined grained tournament selection, uniform crossover and bitflip mutation in solving the proposed problems.

Citation

ANKRAH, R., REGNIER-COUDERT, O., MCCALL, J., CONWAY, A. and HARDWICK, A. 2018. Performance analysis of GA and PBIL variants for real-world location-allocation problems. In Proceedings of the 2018 IEEE congress on evolutionary computation (CEC 2018), 8-13 July 2018, Rio de Janeiro, Brazil. Piscataway, NJ: IEEE [online], article number 8477727. Available from: https://doi.org/10.1109/CEC.2018.8477727

Conference Name 2018 IEEE congress on evolutionary computation (CEC 2018)
Conference Location Rio de Janeiro, Brazil
Start Date Jul 8, 2018
End Date Jul 13, 2018
Acceptance Date Mar 15, 2018
Online Publication Date Jul 8, 2018
Publication Date Oct 4, 2018
Deposit Date Jun 22, 2018
Publicly Available Date Mar 29, 2024
Publisher Institute of Electrical and Electronics Engineers (IEEE)
Article Number 8477727
DOI https://doi.org/10.1109/CEC.2018.8477727
Keywords Uncapacitated facility location problem; Uncapacitated facility location resilience problem; Uncapacitated facility location resilience problem with restrictions; Genetic algorithm; Population based incremental learning algorithm
Public URL http://hdl.handle.net/10059/2960

Files




You might also like



Downloadable Citations