Abstract
We present an in-depth computational study of two local search metaheuristics for the classical uncapacitated facility location problem. We investigate four problem instance models, studied for the same problem size, for which the two metaheuristics exhibit intriguing and contrasting behaviours. The metaheuristics explored include a local search (LS) algorithm that chooses the best moves in the current neighbourhood, while a randomised local search (RLS) algorithm chooses the first move that does not lead to a worsening. The experimental results indicate that the right choice between these two algorithms depends heavily on the distribution of coefficients within the problem instance. This is also put further into context by finding optimal or near-optimal solutions using a mixed-integer linear programming problem solver.
| Original language | English |
|---|---|
| Book series | IFAC-PapersOnLine |
| Volume | 52 |
| Issue number | 13 |
| Pages (from-to) | 2219-2224 |
| Number of pages | 6 |
| ISSN | 2405-8963 |
| DOIs | |
| Publication status | Published - Sept 2019 |
| Event | 9th IFAC Conference on Manufacturing Modelling, Management and Control, MIM 2019 - Berlin, Germany Duration: 28 Aug 2019 → 30 Aug 2019 |
Conference
| Conference | 9th IFAC Conference on Manufacturing Modelling, Management and Control, MIM 2019 |
|---|---|
| Country/Territory | Germany |
| City | Berlin |
| Period | 28/08/2019 → 30/08/2019 |
| Sponsor | et al., IFAC TC 1.3. Discrete Event and Hybrid Systems, IFAC TC 3.2. Computational Intelligence in Control, IFAC TC 4.3. Robotics, IFAC TC 5.1. Manufacturing Plant Control, International Federation of Automatic Control (IFAC) - Technical Committee on Manufacturing Modelling for Management and Control, TC 5.2 |
Keywords
- Algorithm efficiency
- Combinatorial optimisation
- Facility location problem
- Integer linear programming
- Local search