An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem
In the bidirectional loop layout problem (BLLP), we are given a set of machines, a set of locations arranged in a loop configuration, and a flow cost matrix. The problem asks to assign machines to locations so as to minimize the sum of the products of the flow costs and distances between machines. T...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/1/5 |
| _version_ | 1827699529311322112 |
|---|---|
| author | Gintaras Palubeckis |
| author_facet | Gintaras Palubeckis |
| author_sort | Gintaras Palubeckis |
| collection | DOAJ |
| description | In the bidirectional loop layout problem (BLLP), we are given a set of machines, a set of locations arranged in a loop configuration, and a flow cost matrix. The problem asks to assign machines to locations so as to minimize the sum of the products of the flow costs and distances between machines. The distance between two locations is calculated either in the clockwise or in the counterclockwise direction, whichever path is shorter. We propose a hybrid approach for the BLLP which combines the simulated annealing (SA) technique with the variable neighborhood search (VNS) method. The VNS algorithm uses an innovative local search technique which is based on a fast insertion neighborhood exploration procedure. The computational complexity of this procedure is commensurate with the size of the neighborhood, that is, it performs <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula> operations per move. Computational results are reported for BLLP instances with up to 300 machines. They show that the SA and VNS hybrid algorithm is superior to both SA and VNS used stand-alone. Additionally, we tested our algorithm on two sets of benchmark tool indexing problem instances. The results demonstrate that our hybrid technique outperforms the harmony search (HS) heuristic which is the state-of-the-art algorithm for this problem. In particular, for the 4 Anjos instances and 4 <i>sko</i> instances, new best solutions were found. The proposed algorithm provided better average solutions than HS for all 24 Anjos and <i>sko</i> instances. It has shown robust performance on these benchmarks. For 20 instances, the best known solution was obtained in more than <inline-formula><math display="inline"><semantics><mrow><mn>50</mn><mo>%</mo></mrow></semantics></math></inline-formula> of the runs. The average time per run was below 10 s. The source code implementing our algorithm is made publicly available as a benchmark for future comparisons. |
| first_indexed | 2024-03-10T13:51:59Z |
| format | Article |
| id | doaj.art-19e1647be6344667aaadd2c0605da51b |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T13:51:59Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-19e1647be6344667aaadd2c0605da51b2023-11-21T02:01:15ZengMDPI AGMathematics2227-73902020-12-0191510.3390/math9010005An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout ProblemGintaras Palubeckis0Faculty of Informatics, Kaunas University of Technology, Studentu 50-408, 51368 Kaunas, LithuaniaIn the bidirectional loop layout problem (BLLP), we are given a set of machines, a set of locations arranged in a loop configuration, and a flow cost matrix. The problem asks to assign machines to locations so as to minimize the sum of the products of the flow costs and distances between machines. The distance between two locations is calculated either in the clockwise or in the counterclockwise direction, whichever path is shorter. We propose a hybrid approach for the BLLP which combines the simulated annealing (SA) technique with the variable neighborhood search (VNS) method. The VNS algorithm uses an innovative local search technique which is based on a fast insertion neighborhood exploration procedure. The computational complexity of this procedure is commensurate with the size of the neighborhood, that is, it performs <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula> operations per move. Computational results are reported for BLLP instances with up to 300 machines. They show that the SA and VNS hybrid algorithm is superior to both SA and VNS used stand-alone. Additionally, we tested our algorithm on two sets of benchmark tool indexing problem instances. The results demonstrate that our hybrid technique outperforms the harmony search (HS) heuristic which is the state-of-the-art algorithm for this problem. In particular, for the 4 Anjos instances and 4 <i>sko</i> instances, new best solutions were found. The proposed algorithm provided better average solutions than HS for all 24 Anjos and <i>sko</i> instances. It has shown robust performance on these benchmarks. For 20 instances, the best known solution was obtained in more than <inline-formula><math display="inline"><semantics><mrow><mn>50</mn><mo>%</mo></mrow></semantics></math></inline-formula> of the runs. The average time per run was below 10 s. The source code implementing our algorithm is made publicly available as a benchmark for future comparisons.https://www.mdpi.com/2227-7390/9/1/5combinatorial optimizationfacility layoutbidirectional loop layoutsimulated annealingvariable neighborhood search |
| spellingShingle | Gintaras Palubeckis An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem Mathematics combinatorial optimization facility layout bidirectional loop layout simulated annealing variable neighborhood search |
| title | An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem |
| title_full | An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem |
| title_fullStr | An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem |
| title_full_unstemmed | An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem |
| title_short | An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem |
| title_sort | approach integrating simulated annealing and variable neighborhood search for the bidirectional loop layout problem |
| topic | combinatorial optimization facility layout bidirectional loop layout simulated annealing variable neighborhood search |
| url | https://www.mdpi.com/2227-7390/9/1/5 |
| work_keys_str_mv | AT gintaraspalubeckis anapproachintegratingsimulatedannealingandvariableneighborhoodsearchforthebidirectionallooplayoutproblem AT gintaraspalubeckis approachintegratingsimulatedannealingandvariableneighborhoodsearchforthebidirectionallooplayoutproblem |