GASUB: finding global optima to discrete location problems by a genetic-like algorithm |
| |
Authors: | Blas Pelegrín Juani L. Redondo Pascual Fernández Inmaculada García Pilar M. Ortigosa |
| |
Affiliation: | (1) Department of Statistics and Operational Research, University of Murcia, Murcia, Spain;(2) Department of Computer Architecture and Electronics, University of Almería, Almeria, Spain |
| |
Abstract: | In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided. |
| |
Keywords: | Combinatorial optimization Discrete location problems Stochastic algorithms Multimodal genetic algorithms |
本文献已被 SpringerLink 等数据库收录! |
|