A hybridisation of linear programming and genetic algorithm to solve the capacitated facility location problem

Abstract

This paper introduces a cooperative approach of a swarm intelligence algorithm and a linear programming solver to solve the capacitated facility location problem (CFLP). Given a set of potential locations to open facilities, the aim in CFLP is to find the minimum cost, which is the sum of facility opening costs and transportation costs. The developed solution strategy decomposes CFLP into two sub-problems. The former sub-problem has a binary domain. Although most of the swarm intelligence algorithms employ additional procedures such as sigmoid function to deal with binary domains, the proposed algorithm does not require for such methods. An adaptive mutation operator enhances this algorithm. The aim of the latter sub-problem is to generate a policy that optimally assigns customers to the opened facilities. In this regard, the generated binary vectors by the proposed algorithm are passed to a solver to optimise the generated linear model. Commonly used instances available in the literature are solved by the proposed strategy. Comprehensive experimental study includes comparisons with the sate-of-the-art. According to the statistically verified results, the proposed strategy is found as promising in solving CFLP.

KEYWORDS:

• Capacitated facility location problem
• evolutionary algorithms
• swarm intelligence
• genetic algorithm
• particle swarm optimisation

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

All data used in this study can be accessed through the web site: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/capinfo.html. If requested, authors agree to share the used dataset.

Notes

1 http://people.brunel.ac.uk/∼mastjjb/jeb/orlib/capinfo.html

Additional information

Notes on contributors

Fehmi Burcin Ozsoydan

Fehmi Burcin Ozsoydan received his Ph.D. degree in Industrial Engineering from Dokuz Eylül University, Turkey in 2016. He worked as a research assistant during his MSc and PhD training at Eskişehir Osmangazi University and Dokuz Eylül University, respectively. He is currently an Associate Professor in Operations Research Major Science at the Industrial Engineering Department of Dokuz Eylül University. His research areas include soft computing, evolutionary computation, machine learning, artificial intelligence, dynamic optimisation and industrial manufacturing systems.

İlker Gölcük

İlker Gölcük received his Ph.D. degree in Industrial Engineering from Dokuz Eylül University, Turkey in 2019. He worked as a research assistant during his MSc and PhD training at the same university, respectively. He is currently an Associate Professor at the Industrial Engineering Department of İzmir Bakırçay University. His research areas include multi-criteria decision making, soft computing, fuzzy logic, machine learning, artificial intelligence and industrial manufacturing systems.