Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods
| Autor: | Diptesh Ghosh, Ravi Kothari |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
Information Systems and Management Speedup General Computer Science Brute-force search Management Science and Operations Research 2-opt Industrial and Manufacturing Engineering Tabu search Modeling and Simulation Single row Line (geometry) Benchmark (computing) Guided Local Search Mathematics |
| Zdroj: | European Journal of Operational Research. 224:93-100 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2012.07.037 |
| Popis: | The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and the other involving an exhaustive search of the insertion neighborhood. We also present techniques to significantly speed up the search of the two neighborhoods. Our computational experiments show that the speed up techniques are effective, and our tabu search implementations are competitive. Our tabu search implementations improved previously known best solutions for 23 out of the 43 large sized SRFLP benchmark instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect