Mathematical modeling for relocation of terminal facilities in location problems
Subject Areas : Application of soft computing in engineering sciences
Mehdi Fazli
1
*
,
somayyeh faraji
2
1 - Department of Mathematics, Ardabil Branch, Islamic Azad University, Ardabil, Iran
2 - 1Department of Mathematics, Islamic Azad University, Tabriz Branch, Tabriz, Iran
Keywords: Simulated Annealing, Migratory Bird Optimization, Terminal Facilities, Optimization, Taboo Search,
Abstract :
The main goal of terminal facility layout is to place parking lots, areas and different units within predefined limits in such a way as to minimize the cost of moving passengers and employees. Especially in ‘large-scale terminals containing several different specialized departments, it is important for the efficiency of the terminal that the interaction units are located close together. Today, meta-heuristic algorithms are often used to solve optimization problems such as facility layout. Organized using three meta-heuristic algorithms which are Migratory Bird Optimization (MBO), Taboo Search (TS) and Simulated Annealing (SA), the results were compared with the existing parking scheme. As a result, the MBO and SA meta-heuristic algorithms have provided similar best results, which improve the efficiency of the existing parking scheme by approximately 58%.’.
[1] J. Tompkins, J. White, W. Bozer, J. Tanchoco, Facilities Planning, John Wiley & Sons, New York, USA, 2003.
[2] Sarma, Sisira, Demand for outpatient healthcare, Appl. Health Econ. Health Policy 7 (4) (2009) 265–277.
[3] R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Appl. Math. 157 (2009) 183–190
[4] M. Mohammadi, K. Forghani, A novel approach for considering layout problem in cellular manufacturing systems with alternative processing routings and subcontracting approach, Appl. Math. Model. 38 (14) (2014) 3624–3640.
[5] A. Barbosa-Povoa, R. Mateus, A. Novais, Optimal two-dimensional layout of industrial facilities, Int. J. Prod. Res. 39 (12) (2001) 2567–2593.
[6] S.P. Singh, R.R. Sharma, A review of different approaches to the facility layout problems, Int. J. Adv. Manuf. Technol. 30 (5–6) (2006) 425–433.
[7] B. Montreuil, A modeling framework for integrating layout design and flow
network design, in: Proceedings of the Material Handling Research Colloquium, 1990, pp. 43–58.
[8] T. Lacksonen, Pre-processing for static and dynamic facility layout problems, Int. J. Prod. Res. 35 (1997) 1095–1106.
[9] F. Azadivar, J. Wang, Facility layout optimization using simulation and genetic algorithms, Int. J. Prod. Res. 38 (17) (2000) 4369–4383.
[10] Y.H. Lee, M.H. Lee, A shape-based block layout approach to facility layout problems using hybrid genetic algorithm, Comput. Ind. Eng. 42 (2) (2002) 237–248.
[11] E. Shayan, A. Chittilappilly, Genetic algorithm for facilities layout problems based on slicing tree structure, Int. J. Prod. Res. 42 (2) (2002) 237–248.
[12] R. Sahin, O. Turkbey, A new hybrid heuristic algorithm for the multi objective facility layout problem, J. Faculty Eng. Archit. Gazi Univ. 25 (1) (2010) 119– 130.
[13] M.Y. Cheng, L.C. Lien, A hybrid AI-based particle bee algorithm for facility layout optimization, Eng. Comput. 28 (1) (2012) 57–69.
[14] Q. Luo, Q. Su, J. Le, L. Lu, in: 10th International Conference on Service Systems and Service Management, IEEE, 2013, pp. 224–227.
[15] Y.Y. Ileri, The Importance of Layout Organization in Hospital Management Efficiency: A Model in S.U. Medical Faculty Hospital, Selcuk University, 2013.
[16] D.T.T. Huyen, N.T. Binh, T.M. Tuan, T.Q. Trung, N.G. Nhu, N. Dey, L.H. Son, Analyzing trends in hospital-cost payments of patients using ARIMA and GIS: case study at the hanoi medical university hospital, Vietnam, J. Med. Imaging
Health Inf. 7 (2) (2017) 421–429.
[17] M.E. Aydin, T.C. Fogarty, A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems, J. Heuristics 10 (3) (2004) 269–292.
[18] A. Kaveh, P. Sharafi, Charged system search algorithm for minimax and minisum facility layout problems, Asian J. Civ. Eng. 6 (12) (2011) 703–718.
[19] A. Kaveh, M.A.A. Shakouri, M.S. Zolfaghari, An adapted harmony search based algorithm for facility layout optimization, Int. J. Civ. Eng. 1 (10) (2012) 37–42.
[20] K.Y. Chan, M.E. Aydin, T.C. Fogarty, Main effect fine-tuning of the mutation operator and the neighbourhood function for uncapacitated facility location problems, Soft. Comput. 10 (11) (2006) 1075–1090.
[21] J. Yang, M.E. Aydin, J. Zhang, C. Maple, UMTS base station location planning: a mathematical model and heuristic optimisation algorithms, IET Commun. 1 (5) (2007) 1007–1014.
[22] E. Duman, M. Uysal, A.F. Alkaya, Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem, Inf. Sci. 217 (2012) 65–77.
[23] V. Tongur, E. Ülker, Migrating birds optimization for flow shop sequencing problem, J. Comput. Commun. 2 (04) (2014) 142.
[24] A. Sioud, C. Gagné, Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times, Eur. J. Oper. Res. 264 (1) (2018) 66–73.
[25] B. Zhang, Q.K. Pan, L. Gao, X.L. Zhang, H.Y. Sang, J.Q. Li, An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming, Appl. Soft Comput. 52 (2017) 14–27.
[26] T. Meng, Q.K. Pan, J.Q. Li, H.Y. Sang, An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem, Swarm Evol. Comput. 38 (2018) 64–78.
[27] Q.K. Pan, Y. Dong, An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation, Inf. Sci. 277 (2014) 643–655.
[28] K.Z. Gao, P.N. Suganthan, T.J. Chua, in: An Enhanced Migrating Birds Optimization Algorithm for No-Wait Flow Shop Scheduling Problem, IEEE, 2013, pp. 9–13.
[29] E. Duman, I. Elikucuk, Solving credit card fraud detection problem by the new metaheuristics migrating birds optimization62–71, International Work- Conference on Artificial Neural Networks, Springer, Berlin, Heidelberg, 2013.
[30] E. Ulker, V. Tongur, Migrating birds optimization (MBO) algorithm to solve knapsack problem, Proc. Comput. Sci. 111 (2017) 71–76.
[31] V. Tongur, E. Ülker, The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem, in: Intelligent and Evolutionary Systems, Springer, Cham, 2016, pp. 227–237.
[32] V. Tongur, E. Ülker, PSO-based improved multi-flocks migrating birds optimization (IMFMBO) algorithm for solution of discrete problems, Soft. Comput. 23 (14) (2019) 5469–5484.
[33] M. Hacibeyoglu, K. Alaykiran, A.M. Acilar, V. Tongur, E. Ulker, A Comparative Analysis of metaheuristic approaches for multidimensional two-way number partitioning problem, Arabian J. Sci. Eng. 43 (12) (2018) 7499–7520.
[34] Z. Li, M.N. Janardhanan, A.S. Ashour, N. Dey, Mathematical models and migrating birds optimization for robotic U-shaped assembly line balancing problem, Neural Comput. Appl. (2019) 1–17.
[35] F. Glover, Tabu search part I., ORSA J. Comput. 1 (3) (1989) 190–206.
[36] F.A.T. Montané, D.G. Roberto, A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res. 33 (3) (2006) 595–619.
[37] J. Grabowski, W. Mieczyslaw, A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Comput. Oper. Res. 31 (11) (2004) 1891–1909.
[38] C.N. Fiechter, A parallel tabu search algorithm for large traveling salesman problems, Discrete Appl. Math. 51 (3) (1994) 243–267.
[39] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Am. Assoc. Adv. Sci. 220 (4598) (1983) 671–680.
[40] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys. 21 (6) (1953) 1087–1092.
[41] H. Bagherlou, A. Ghaffari, A routing protocol for vehicular ad hoc networks using simulated annealing algorithm and neural networks, J. Supercomput. 74 (6) (2018) 2528–2552.
[42] L. Wei, Z. Zhang, D. Zhang, S.C. Leung, A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, Eur. J. Oper. Res. 265 (3) (2018) 843–859.
[43] K. Karagul, Y. Sahin, E. Aydemir, A. Oral, A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption, in: Lean and Green Supply Chain Management, Springer, Cham, 2019, pp. 161–187.
[44] M.M. Mafarja, S. Mirjalili, Hybrid whale optimization algorithm with simulated annealing for feature selection, Neurocomputing 260 (2017) 302– 312.
[45] S.H. Zhan, J. Lin, Z.J. Zhang, Y.W. Zhong, List-based simulated annealing algorithm for traveling salesman problem, Comput. Intell. Neurosci. 2016 (2016) 8.
[46] S. Kulturel-Konak, A. Konak, A large-scale hybrid simulated annealing algorithm for cyclic facility layout problems, Eng. Optim. 47 (7) (2015) 963– 978.
[47] N. Shivasankaran, P.S. Kumar, K.V. Raja, Hybrid sorting immune simulated annealing algorithm for flexible job shop scheduling, Int. J. Comput. Intell. Syst. 8 (3) (2015) 455–466.
[48] S. García, D. Molina, M. Lozano, F. Herrera, A study on the use of nonparametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization, J. Heuristics 15 (6) (2009) 617.
Journal of Optimization of Soft Computing (JOSC) Vol. 3, Issue 1, pp: (42-54), Spring-2025 Journal homepage: https://sanad.iau.ir/journal/josc |
|
Paper Type (Research paper)
Mathematical modeling for relocation of terminal facilities
in location problems
Mehdi Fazli1,* and Somayyeh Faraji Amoogin1
1 Department of Mathematics, Ardabil Branch, Islamic Azad University, Ardabil, Iran
Article Info |
| Abstract |
Article History: Received: 2025/01/07 Revised: 2025/03/17 Accepted: 2025/04/12
DOI: josc.2025.140310181195807 |
| The main goal of terminal facility layout is to place parking lots, areas and different units within predefined limits in such a way as to minimize the cost of moving passengers and employees. Especially in ‘large-scale terminals containing several different specialized departments, it is important for the efficiency of the terminal that the interaction units are located close together. Today, meta-heuristic algorithms are often used to solve optimization problems such as facility layout. Organized using three meta-heuristic algorithms which are Migratory Bird Optimization (MBO), Taboo Search (TS) and Simulated Annealing (SA), the results were compared with the existing parking scheme. As a result, the MBO and SA meta-heuristic algorithms have provided similar best results, which improve the efficiency of the existing parking scheme by approximately 58%.’. |
Keywords: Simulated Annealing, Migratory Bird Optimization, Terminal Facilities, Optimization, Taboo Search |
| |
*Corresponding Author’s Email Address: mehdi.fazli.s@gmail.com
|
1. Introduction
The terminal facility arrangement problem has received less attention than other issues in the literature because many perspectives of customer choice cannot be controlled by transportation directors ‘[1] and demand is highly ambiguous in this area [2]. Therefore, more than presenting the complicacy of the methods used to examine the issue of terminal deployment, determining the subject solving method, preparing appropriate data and obtaining optimal data are other important points to achieve optimal deployment. The issue of arranging terminal facilities is an NP-hard problem in terms of mathematical calculations [3, 4]. There are various methods to solve the facility design problem in this field, whether it is a one-criterion or multi-criteria problem. One of them is the quadratic allocation problem (QAP) if it considers approximately equal regions for each section and different locations [5]. Next are approximate and heuristic processes that are effective in solving multiple design problems simultaneously [6]. Another study is mixed programming (MP), which uses a general distance-based aim function to design facilities for segments of unequal or equal area [8]. The facility allocation problem is defined by managers as placing a predestined number of possibilities in possible neighborhoods and sizes [9]. Lee and Lee assumed different possibilities in nearby areas to amend the efficiency of facilities in a border area [10]. Shayan and Chitilapili assumed the issue of facility allocation as an optimization issue.
They tried to achieve the optimal arrangement of facilities by considering the interactions between facilities and material handling costs [11]. In the research of recent years, methods based on technological innovation and crowded intelligence have been used to optimally solve facility allocation problems. Shahin and Turkabi developed a new hybrid meta-heuristic technique for solving multiple instrument design problems based on the simulated annealing (SA) method and based by tabu list [12]. By integrating the honey bee (BA) technique, Cheng and Lin obtained a hybrid method for multi-criteria facility design problems. Their methods had global search capability with local research benefits of Particle Swarm Optimization (PSO) at the same time [13]. Using the Ant Colony (ACO) method, Lu et al presented a new model for designing the layout of emergency medical facilities in the city [14]. Eiler used the ACO to locate labs, radiology units, and hospital polyclinics specifically for applicants to minimize running costs. Huynh et al. reviewed the cost estimate of the laboratory. In their research, they operated Automatic Integrated Moving Average (ARIMA) to appraise the number of laboratory applicants. GIS is also used to show the running reality or situation for the distribution of applicants and laboratory costs [16]. Aydin and Fogarty designed a new technique in which SA evolutionary method was applied to solve the classical clinic planning problem and the optimal location problem of disabled hospital facilities [17]. Kaveh and Sharfi used the Search Engine Optimization (CSS) technique, which is based on the interaction among charged particles, to solve the problem of facility allocation in distribution network management [18]. A special coordination search method is presented by Kaveh et al. To find the location of the optimal tool in a given problem [19]. Chan et al perused the alteration measure of fine-tuning genetic technique and the neighbor function of the SA method to solve the problem of locating specific facilities. They used changeable change functions instead of fixed change function or accidentally selected genes and increased the efficiency of the technique to an acceptable extent [20]’.
‘Yang et al. modeled the efficiency of several meta-heuristic techniques in terms of theoretical methods. Their problem is considered as a p-median problem for base station routing. As mentioned in the text above, several researches have been done in research activities on the problems of allocation of different possibilities, there are only specific studies on the problems related to the allocation of different terminal locations. The purpose of this study is to create a specific facility design for the terminals in order to minimize the overall costs of the system. The cost of moving travel applicants can be reduced by minimizing travel between different establishments. The optimal arrangement problem of our terminal facilities is to investigate the best possible arrangement of different parts in a hypothetical range. So that the distance between the parts that are logically connected to each other is reduced. In this regard, we created a mathematical method for the optimal location of different parts of the terminal with the lowest possible cost. Different alternative techniques of applied strategies were created and the most possible and best option was used. As a new paper, the simulated annealing (SA) optimization technique is used for the first time to solve the problem of assigning facilities to a terminal. Local search is used in SA method. Aiming to measure the performance of the SA technique in real-world problems, the SA results are measured with effects derived from the Tabu Search (TS) and MBO techniques in the given problem. The MBO technique was chosen due to its simplicity and good application in finding reasonable points. The TS technique avoids local optimization and has a more general search. The results of the assignment of terminal components showed that the MBO technique shows an acceptable performance for solving the problem of assigning components of a single terminal. Also, the rest of the article is organized as follows. The definition of the problem of assigning the components of a terminal and the statistical information of this problem are presented in Section 2. The meta-heuristic techniques of TS, SA and MBO are detailed in Section 3. In the next section, we will solve the problem and in section 5, the calculation results are described. In Section 6’, the paper ends with a conclusion and discussion.
2. Model
The ‘design and layout of office facilities should include all necessary requirements such as entities, mathematical modeling, difficulty of movement, vertical movement and arrangement of sections within the pre-defined limits by Illery [15], in a way that takes into account the distance between different components and takes care of the customer's demand. In order to achieve the efficient and optimal positioning of departments in this matter, the distance and the number of guidelines for the distance between different departments should be considered’, which depends on the distance traveled between the components. The distance between two points determines the connection coefficient, and the parts with high traffic should be placed next to each other, and the parts with the lowest density can be far from each other. We investigated and modeled these factors to reduce the target performance and overall system cost.
1- ‘Multi-station interaction, which depends on the number of passengers moving between two stations, should be considered so that stations with higher traffic are closer to stations that are quieter.
2- The number of customers walking to each station was calculated in such a way that the stations with more customers are closer to the main entrance of the customer stations.
3- The final transportation cost was calculated directly based on the degree of travel difficulty, distance, travel frequency, and basic travel cost, and therefore, changing each of these variables caused a change in the transportation cost.
4- The final acceptable response of the system’ is obtained by performing simulations with the aim of improving one or a number of variables of the problem.
To solve this position allocation problem, we form a special objective function. While paying attention to the physical dimensions of the terminal, the number of kiosks is proportional to the required area, and the average daily data of a season is considered. In the special terminal system, the number of customers and the number of guides is specified.
The physical structure of the terminal shown in Figure 1 includes three blocks, thirty-one applicable parking areas with an area of 800 square meters, and a terminal entrance. There are twenty-six zones of different sizes in the terminal.
Fig. 1. Physical structure of the terminal.
The main ‘structure of the terminal consists of several blocks, a parking lot with a defined area and a main terminal entrance. So, there are several parts of different sizes in the terminal. The size and distance of the main entrance of the terminal to the areas to be located are given in Table 1’.
According to the assumptions explained in the text, Table No. 1 is presented based on the entities of the problem and the objective function of the project is expressed in the form of a special equation.
(1)
In this ‘formula, m is the number of parking spaces, n is the number of zones where the parking lots are located, xi is the distance between the possible zones and the main entrance of the terminal, yi is the number of weekly customers in the parking lot. located up to the ith place. , is the number of customers from the parking lot who were sent to the location j to the parking lot that is placed in the return range.
is the distance between region j and return. The
matrix can be measured as a principal matrix in QAP’ topics. This matrix consists of different service values, which is the number of trips inside the terminal.
Table 1
The size of the areas and the distance to the terminal entrance |
|
| |||
Area Code | Distance to the station | Size
| |||
0 | 20 | 900 | |||
1 | 20 | 900 | |||
2 | 30 | 900 | |||
3 | 30 | 900 | |||
4 | 70 | 900 | |||
5 | 70 | 900 | |||
6 | 80 | 900 | |||
7 | 80 | 900 | |||
8 | 120 | 900 | |||
9 | 120 | 900 | |||
10 | 130 | 900 | |||
11 | 130 | 900 | |||
12 | 170 | 900 | |||
13 | 170 | 900 | |||
14 | 180 | 900 | |||
15 | 180 | 900 | |||
16 | 220 | 900 | |||
17 | 230 | 900 | |||
18 | 230 | 900 | |||
19 | 230 | 900 | |||
20 | 250 | 900 | |||
21 | 260 | 900 | |||
22 | 260 | 900 | |||
23 | 250 | 900 | |||
24 | 270 | 900 | |||
25 | 280 | 900 | |||
26 | 280 | 900 | |||
27 | 270 | 900 | |||
28 | 320 | 900 | |||
29 | 330 | 900 | |||
30 | 330 | 900 | |||
31 | 320 | 900 |
Our problem had two obvious limitations. First, the terminal facility allocation should take into account overall system costs related to customer handling and congestion vehicle handling, ‘but we did not consider the number of vehicles because reliable information was hard to come by. Second, the terminals were not considered by the staff, because their movement directly depends on the needs of the primary’ travel establishments.
3. Methods
3.1 The ‘MBO migratory bird optimization technique
The ‘MBO migratory bird optimization technique for solving problems was investigated by Duman et al. in 2012 [22]. The MBO technique is inspired by the V formation to optimally use the energy of migratory birds in flight. This technique is often designed for discrete problems and has been implemented and investigated on QAP problems that are based on actual-world’ questions.
The most ‘optimal method of migration for migratory birds is the V formation so that they can travel longer distances without getting tired. It is clear that in this technique the main instinct of this formation is to save the total energy. The commander bird is the member that consumes the maximum energy in the V organization. The rest of the members can fly for a longer time due to the wind energy generated by the movement of the bird's wings in front of them.
The ‘MBO technique is used in many problems to solve many cases such as the flow storage problem ‘[23-28]’, also in the backpack problem [33], or in the credit card fraud detection problem [29] and in the case of the traveling salesman [31,32], two-way partitions are used [33], this technique is also used to balance the U-shaped robotic assembly line [34]’.
The ‘MBO method and algorithm starts with the initial answers that are randomly generated and then tries to improve the obtained answers at each step. The permutation, insertion and inversion process is used to generate candidate solutions for neighbors in order to improve existing paths. The resulting candidate close responses are then compared to the response the technique is looking for. Each current answer is checked against the best adjacent answer. If the adjacent answer is better than the running answer, the neighbor's answer is replaced with the running answer. Furthermore, leader displacement is performed at defined times to provide optimal responses to both sides of the population. The MBO’ technique and algorithm include generation of relevant initial community, neighbor sharing operation, and appropriate response descendant and leader displacement steps.
3.1.1. Generation a main solution
The ‘MBO technique and algorithm examines the initial answers that are randomly selected and tries to optimize the current solution. One of the candidate birds is chosen as the commander bird and the other birds are resting on the left and right side of the commander bird. Therefore, the initial population is marked as described in the method. Where the primary congregation of each bird’ represents an initial response.
3.1.2. Generation an acceptable answer
In the ‘MBO technique, an inversion process is used to generate input points for the operation of searching for the appropriate position. In this particular technique, candidate neighboring solutions are obtained completely randomly from the current solution by swapping two selected points. The number of potential suitable answers for the front bird and the number of optimal answers for the candidate bird are different according to the process of the MBO technique. The number of optimal answers is obtained from equation (2) - (4) below [32]’.
| (2) | |||||||||||
| (3) | |||||||||||
| (4) |
1 | 4 | 0 | 2 | 5 | 3 |
| 2 | 4 | 0 | 1 | 5 | 3 |
Fig. 2. Neighbor solution generation.
The ‘remaining q responses are passed to the next bird and other neighboring responses are removed. This action is also performed on the other side or the right side of the group of birds. Neighborhood subscriptions run until the end of the bird collection’.
3.1.4. Replacing the leader bird
In the ‘MBO algorithm, a flap parameter (f) is used to keep indi- viduals in the same sequence for a certain period of time. Then, lea- der replace processing is applied. First replacement is applied to the left side of the flock. While the leader is sent behind the left side of the flock, another bird that follows the leader is replaced by the leader. Thus, a new sequence is created and parameter m is reset. The next replacement is applied to the right side of the flock. This process is continued until the algorithm is terminated. Leader replacement process is shown in Fig. 3’.
Fig. 3. The leader replacement.
In Algorithm a, the pseudocode of the MBO method is presented as follows:
Algorithm a. algorithm MBO
Create a random initial set
repetition
repetition
‘m Create a neighbor point for the leader member
Create neighbors of r for the other answer
Compare the best value of q neighbors with the answer of the posterior member
if (best neighbor answer < current answer value)’
Current answer = Neighborhood answer
up to the input amount
Replace the leader member
until termination
Return the best answer in the set
3.2. Taboo search technique
For use in practical optimization problems, the TS evolutionary technique was first modeled by Glover in 1988 ‘[35]. In the research background, the TS technique has been applied to multitude practical optimization subjects such as the vehicle positioning and routing problem [36] as well as the traveling salesman project [38] or the special flow storage subject [37]’.
In the process related to the ‘TS technique, an initial answer is generated and during the operation, an attempt is made to discover the overall optimal answer using local search methods such as the exchange and insertion operator. In the different memory structure of the TS technique, we have two modes. The structures of short-term memory and long-term memory accept the user to choose the best feasible move to generate the appropriate response and avoid reaching taboo responses. In this method, the TS technique eludes local optimization and seeks the global optimal solution. When the desired amount is attained, the specified taboo is removed and the formerly found answer can be chosen as the new answer. During the search operation for the best point, the optimal answer found by the ‘TS’ technique is stored in the system memory and all the answers produced by the system are measured with the desired answer. If there is an answer more favorable than the maximum answer, the overall system memory is updated’.
In Algorithm b, the pseudocode of the TS method is presented as follows:
Algorithm b. algorithm TS
Generate the initial answer randomly. This answer as Choose the current answer and the best optimal answer.
repetition
Discover neighboring optimal answers using local search techniques.
Choose the answer that is a non-taboo neighbor.
Break the norms, even if it is taboo.
If the resulting answer is better than the existing answer, select the new answer as taboo
If the new answer is better than the best answer, set the new answer as the best optimal answer until termination’
3.3. Simulated annealing technique
To solve the combined and specific problems, the SA technique was investigated by Kirkpatrick et al. [39]. In the ‘SA technique, it is used to find the optimal solution by avoiding local answers for functions with manifold variables. The reason for the name of this technique is that it is an example of the complete arrangement of atoms and the minimization of the potential energy of the system when cooling solids. The method of heating a solid body to its melting point and then slowly cooling it to a complete network structure is known as annealing process.
The ‘simulated annealing technique is performed in three specific steps: heating the desired object or material to a certain degree (heating), maintaining that degree for a certain period of time (waiting) and controlled and gradual reduction of temperature (cooling). In the heating process, the particles of solid matter slowly turn into liquid, and when they are properly and gradually cooled, crystalline particles with a completely regular structure’ are formed.
The structure of this problem and the practical annealing operation are based on the Monte Carlo technique by Metropolis et al. [41]. In the assumed degree of T, the amount of energy of the system is determined based on the following relationship.
| (5) |
| (6) |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 32 |
3 | 1 | 5 | 2 | 4 | 6 | 10 | 8 | 7 | 9 | … | 14 |
station No
Fig. 4. Permutation coding for an answer
‘Example. Suppose that four different stations (1, 2, 3, 4) are located in five specific regions. Tables 2-4’ show the number of station customers, recommendations of inter-station customers, areas to be deployed and main terminal entry time intervals.
In ‘Table 2, the second station is shown as three separate station plots because it has three times the area to be located. The number of customers in Table 2 shows the variable y in relation (1)’.
In ‘table number 3, columns 2 and 3 show the same parts of the station (2) and should be placed in the adjacent area. In this case, a very large number of consultations are done for the applicants (600). Table 3 shows the matrix z in relation (1)’.
According to the sample answer, station ‘5, 3, 1, 2 and 4 are located in different regions 1, 2, 3, 4 and 5’ respectively.
'Table 5 shows matrix t in the Eq (1)’. A sample answer is as follows.
5 | 3 | 1 | 2 | 4 |
5. Variable settings
In order to reach the best possible solution and cover all aspects in the issue of assigning terminal facilities, we perform parameter settings for all methods.
Table 2
The number of customers who come to the station. |
| ||
Parking No (Name) | Number of applicant (y) | Required size (m2) | |
(A) 1 | 14,609 | 900 | |
(B) 2 | 55,406 | 2700 | |
(B) 3 | |||
(C) 4 | 27,421 | 900 | |
(D) 5 | 10,684 | 900 |
Table 3
The number of consultation clients between stations | ||||||||
| station sending consultations | |||||||
| No | 1 | 2 | 3 | 4 | 5 | ||
station accepting consultations | 1 | 0 | 85 | 85 | 25 | 96 | ||
| 2 | 14 | 0 | 500 | 50 | 41 | ||
| 3 | 14 | 500 | 0 | 50 | 41 | ||
| 4 | 40 | 9 | 9 | 0 | 63 | ||
| 5 | 33 | 4 | 4 | 5 | 0 |
Table 4
Distance to the entrance of the station and size of the area |
|
| ||
Area No | Size | Distance to the entrance (x) | ||
1 | 900 | 15 | ||
2 | 900 | 15 | ||
3 | 900 | 25 | ||
4 | 900 | 25 | ||
5 | 900 | 35 |
Table 5
Distance between terminal areas | ||||||
| 1 | 2 | 3 | 4 | 5 | |
1 | 0 | 15 | 20 | 20 | 30 | |
2 | 15 | 0 | 20 | 20 | 30 | |
3 | 20 | 20 | 0 | 15 | 20 | |
4 | 20 | 20 | 15 | 0 | 20 | |
5 | 30 | 30 | 20 | 20 | 0 |
In the parameter settings, the meta-heuristic techniques of this research are implemented 30 times and separately from each other, and the variables are selected according to the efficiency of the best effects.
5.1. Setting the variables of the MBO technique
In the MBO technique, several variables are checked, including: These variables are, population, neighborhood, and subscription, shake.
Table 6 presents the population parameters with values of 71, 61, 51 and 41. Input, neighbor, and share variables are set to 30, 13, and 1, respectively. As you can see in Table 6, the best mean value in the population = 71 is obtained. It can also be seen in Table 7 that the best mean value is obtained in input =30’.
‘Table 7 evaluates the input parameters with values of 60, 50, 40 and 30. The neighborhood, subscription and population parameters are fixed at 1, 13 and 71, respectively.
In Table 8, the neighborhood variables are evaluated with values of 10, 8, 6 and 4. Sharing, shaking, and population parameters are fixed at 1, 30, and 71, respectively.
Based on the performance of MBO technique, the minimum value of the neighboring variable can be attributed to the number 3. According to equation (3), if m = 3, the sharing variable (q) can only be 1. So, the sharing variable does not need to be checked and we set its size to 1.
According to the tables obtained from the analysis of variables and data, the best data of the MBO technique are given in Table No. 9’.
5.2. TS variable setting
'Three different variables are investigated in the TS technique. These numbers and parameters include the length of the taboo, the long-term penalty, and the long-term penalty’.
Table 6
Variable setting of population. | ||||||
Fixed measures | Population Value | Fitness Average | ||||
Parameter | Value |
|
| |||
Input | 30 | 41 | 10347907,36 | |||
Neighbor | 13 | 51 | 10381693,10 | |||
Share | 1 | 61 | 10340936,30 | |||
|
| 71 | 10290422,95 |
Table 7
Variable setting of flap. | |||||||
Fixed measure | Flap Value | Fitness Average | |||||
Parameter | Value |
|
| ||||
Population | 71 | 30 | 10237226,00 | ||||
Neighbor | 13 | 40 | 10276514,80 | ||||
Share | 1 | 50 | 10302385,16 | ||||
|
| 60 | 10256843,93 |
Table 8
Neighborhood variable setting | |||||||
Fixed measures | Neighbor Value | Fitness Average | |||||
Measure | Value |
|
| ||||
Population | 71 | 4 | 10224283,63 | ||||
Input | 30 | 6 | 10275433,16 | ||||
Share | 1 | 8 | 10305913,26 | ||||
|
| 10 | 10269533,46 |
Table 9
The best data for MBO. | |||
Measurers | Value | ||
Population | 71 | ||
Input | 30 | ||
Neighbor | 13 | ||
Share | 1 |
Table 10
Variable setting of tabu length. | |||||||
Fixed measure | Tabu length Value | Fitness Average | |||||
Measure | Value |
|
| ||||
Penalizing long term | 71 | 20 | 11324842,17 | ||||
|
| 30 | 11162677,17 | ||||
long term length | 110 | 40 | 11000656,80 | ||||
|
| 50 | 11293773,77 |
In ‘Table 10, the taboo length data with values of 50, 50, 30 and 20 are tested and evaluated. Long-term fine and long-term data are fixed at 110 and 10 by definition. As you can see from the data in Table 10, the best value of the process is obtained at tabu length = 40.
Based on table number 11, we see that; the long-term penalty data is evaluated at different values of 30, 25, 20 and 15. The long-term and taboo parameters are fixed at 110 and 40, respectively. According to the information in Table 11, the best process value for a long-term penalty is = 30’.
Table 12 evaluates and evaluates different long-term length numbers and data with 120, 110, 100 and 90 test values. The data of taboo length and long-term penalty are fixed at constant values of 30 and 40, respectively. As shown in Table 12, the best mean value is obtained in the long run = 90’.
The best data related to the TS technique according to the observations and results obtained are given in Table No. 13.
Table 11
Measure setting of penalizing long term. | ||||||
Fixed Measure | Penalizing long term | Fitness | ||||
Measure | Value | Value | Average | |||
tabu length | 40 | 15 | 11163603,20 | |||
|
| 20 | 11391634,70 | |||
long term length | 110 | 25 | 11268883,43 | |||
|
| 30 | 11133662,73 |
Table 12
Measure setting of long term length. | |||||||
Fixed measure s | long term length | Fitness | |||||
Measure | Value | Value | Average | ||||
tabu length | 40 | 90 | 10979242,50 | ||||
|
| 100 | 10991153,00 | ||||
long term length | 30 | 110 | 11203683,33 | ||||
|
| 120 | 11203941,57 |
Table 13
Best measures for the TS. | |||
Measures | Value | ||
tabu length | 40 | ||
penalizing long term | 30 | ||
long term length | 90 |
6. Practical results
Considering that the problem of allocation of terminal facilities is a special problem, then the effects of this problem cannot be compared with the effects of standard problems in similar literature. However, this issue is not only solved by ‘MBO but also by TS and SA methods to evaluate performance efficiency. Tests are performed with an Intel (R) Core (TM) i5-3330 @ 3.00 GHz processor, 1 GB of RAM and Ubuntu 14.04 (64-bit) Linux operating system. All techniques and algorithms are coded with QT Creator 3.1.1 gcc compiler and C++ language. For each technique, the algorithms are run 30 times separately to obtain the overall results. Each test runs for 120 seconds. Depending on the data settings, 120 seconds seems sufficient for both techniques. Parking maps obtained from tests, TS, SA and MBO’ and it is given in table number 14.
According to the observations and parameters of Table No. 14, the best effect obtained from the SA algorithm is equal to 10142858, which is about 1.2% worse than the MBO and SA techniques. For system design and current terminal design, the best results of MBO and SA techniques and their algorithms are given in Table 15’.
Based on the data obtained from ‘Table 15, parking lots 0-3 are located on the 0th floor of Z-Block. Also with the number of consultations, people seem to pour into the lounge from every terminal station.. Considering the number of parking spaces of the stations and the distance to the main hall, it seems logical that the halls should be placed on the 0th floor of the block. Stations 6 and 7 are located on the 0th stage without blocks, parking lots 13 and 14 are located on the 0th bottom of Block A, and parking lots 25 and 26 are located on the 1st stage of Block X. It can also be seen from Table No. 15, the layout of the proposed station and the existing parking layout are generally distinct, except for parking lots 10 and 17. Both are located on the 1st stage of Y-Block. Also, the appropriateness and allocation values of the proposed plan are given in Table 15’. According to the proposal, the allocation of the terminal layout has been improved.
The convergence rate of ‘TS and MBO techniques is closer to each other and faster than SA technique. But the efficiency obtained from the SA technique is better than the TS and MBO’ methods according to the worst results and the average.
Table 14
Results from MBO, SA and TS. | ||||
| Method |
|
| |
| MBO | TS | SA | |
Min. | 10142858,0 | 10254993,0 | 10142858,0 | |
Avg. | 10236622,3 | 11054517,2 | 10158826,4 | |
Worst | 0652954,0 | 11872704,0 | 10331548,0 |
Table 15
Existing and proposed station design | ||||||
Block | Floor | Proposed station Layout | Existing station Layout | |||
X-Block | 0 | 13, 15, 29, 9 | 29, 23, 31, 22 | |||
| 1 | 26, 26, 5, 13 | 8, 16, 25, 31 | |||
Y-Block | 0 | 4, 6, 8, 12 | 15, 18, 18, 28 | |||
| 1 | 10, 28, 17, 24 | 10, 11, 19, 21 | |||
Z-Block | -1 | 19, 17, 31, 23 | 12, 21, 4, 5 | |||
| 0 | 2, 0, 4, 1 | 6, 7, 8, 27 | |||
| 1 | 18, 9, 16, 25 | 13, 15, 25, 26 | |||
| 2 | 21, 28, 31, 21 | 0, 1, 4, 3 | |||
Fitness Value | 10, 141, 847 | 17, 423, 012 |
According to the results obtained from all three meta-heuristic techniques that are analyzed and tested practically. To check whether there is a significant difference between the techniques used, we use the Wilcoxon criterion. There is no important difference between the two measured techniques under the assumption of ‘H0. There is a fundamental difference between these two techniques measured by the alternative hypothesis H1. The acceptable value of H0 hypothesis is set at 95%. In this way, if the distance of each technique is less than 5% (a = 0.05), there is not much distance between two techniques. The results of the techniques are recorded in Table No. 16 at a significance level of 5%’.
Table 16
Wilcoxon test results. | |||
p-values | |||
TS&MBO | SA&MBO | TS &SA | |
0.001 | 0,148 | 0.001 |
According to the results obtained in table number 16, there is no important difference between ‘SA and MBO techniques (0.148> 0.05). According to the results obtained from the tests, it can be seen that there is an acceptable difference between TS and MBO techniques with SA and TS techniques (<0.05)’.
7. Conclusion and discussion
In the end, we will examine the optimization issues of urban life that we can face in many areas of our real life. In these cases, ‘meta-heuristic techniques are used to solve practical optimization subjects. Placing different bodies in appropriate areas in the issue of facility allocation increases operational efficiency by improving system costs, implementation and process time. The location of the stations inside the terminal plays an important role in determining the commuting time of customers and terminal employee. The transfer time of a customer is to visit a station without an intermediary for service or to receive service from a station to a secondary station. The lengthening of these transfer times leads to a longer stay in the terminal and a decrease in the terminal's performance. Therefore, the precise designation of these walking stations ensures the optimal use of terminal electricity and minimizes unnecessary separation between customers, employees and tourists, and increases the productivity of the terminal. In this study, we used TS, SA and MBO meta-algorithms to allocate station space for a real-scale terminal. Based on the results obtained from the experiences, the success of TS, SA and MBO techniques in facility allocation problems is tested on a transportation problem and it is observed that the total cost of SA and MBO’ techniques is very better than TS technique. ‘When we compare the fit value generated from the applied results with the fit value available in a system, we see that our method performs well. As a result, technology can be used to allocate terminal stations. For future work, some constraints and assumptions can be added to the problem. As if a customer has several turns at several stations or some passengers need support to move. The re-completion operation of each section can also be considered’.
References
[1] J. Tompkins, J. White, W. Bozer, J. Tanchoco, Facilities Planning, John Wiley & Sons, New York, USA, 2003.
[2] Sarma, Sisira, Demand for outpatient healthcare, Appl. Health Econ. Health Policy 7 (4) (2009) 265–277.
[3] R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Appl. Math. 157 (2009) 183–190
[4] M. Mohammadi, K. Forghani, A novel approach for considering layout problem in cellular manufacturing systems with alternative processing routings and subcontracting approach, Appl. Math. Model. 38 (14) (2014) 3624–3640.
[5] A. Barbosa-Povoa, R. Mateus, A. Novais, Optimal two-dimensional layout of industrial facilities, Int. J. Prod. Res. 39 (12) (2001) 2567–2593.
[6] S.P. Singh, R.R. Sharma, A review of different approaches to the facility layout problems, Int. J. Adv. Manuf. Technol. 30 (5–6) (2006) 425–433.
[7] B. Montreuil, A modeling framework for integrating layout design and flow
network design, in: Proceedings of the Material Handling Research Colloquium, 1990, pp. 43–58.
[8] T. Lacksonen, Pre-processing for static and dynamic facility layout problems, Int. J. Prod. Res. 35 (1997) 1095–1106.
[9] F. Azadivar, J. Wang, Facility layout optimization using simulation and genetic algorithms, Int. J. Prod. Res. 38 (17) (2000) 4369–4383.
[10] Y.H. Lee, M.H. Lee, A shape-based block layout approach to facility layout problems using hybrid genetic algorithm, Comput. Ind. Eng. 42 (2) (2002) 237–248.
[11] E. Shayan, A. Chittilappilly, Genetic algorithm for facilities layout problems based on slicing tree structure, Int. J. Prod. Res. 42 (2) (2002) 237–248.
[12] R. Sahin, O. Turkbey, A new hybrid heuristic algorithm for the multi objective facility layout problem, J. Faculty Eng. Archit. Gazi Univ. 25 (1) (2010) 119– 130.
[13] M.Y. Cheng, L.C. Lien, A hybrid AI-based particle bee algorithm for facility layout optimization, Eng. Comput. 28 (1) (2012) 57–69.
[14] Q. Luo, Q. Su, J. Le, L. Lu, in: 10th International Conference on Service Systems and Service Management, IEEE, 2013, pp. 224–227.
[15] Y.Y. Ileri, The Importance of Layout Organization in Hospital Management Efficiency: A Model in S.U. Medical Faculty Hospital, Selcuk University, 2013.
[16] D.T.T. Huyen, N.T. Binh, T.M. Tuan, T.Q. Trung, N.G. Nhu, N. Dey, L.H. Son, Analyzing trends in hospital-cost payments of patients using ARIMA and GIS: case study at the hanoi medical university hospital, Vietnam, J. Med. Imaging
Health Inf. 7 (2) (2017) 421–429.
[17] M.E. Aydin, T.C. Fogarty, A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems, J. Heuristics 10 (3) (2004) 269–292.
[18] A. Kaveh, P. Sharafi, Charged system search algorithm for minimax and minisum facility layout problems, Asian J. Civ. Eng. 6 (12) (2011) 703–718.
[19] A. Kaveh, M.A.A. Shakouri, M.S. Zolfaghari, An adapted harmony search based algorithm for facility layout optimization, Int. J. Civ. Eng. 1 (10) (2012) 37–42.
[20] K.Y. Chan, M.E. Aydin, T.C. Fogarty, Main effect fine-tuning of the mutation operator and the neighbourhood function for uncapacitated facility location problems, Soft Computing. 10 (11) (2006) 1075–1090.
[21] J. Yang, M.E. Aydin, J. Zhang, C. Maple, UMTS base station location planning: a mathematical model and heuristic optimisation algorithms, IET Commun. 1 (5) (2007) 1007–1014.
[22] E. Duman, M. Uysal, A.F. Alkaya, Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem, Inf. Sci. 217 (2012) 65–77.
[23] V. Tongur, E. Ülker, Migrating birds optimization for flow shop sequencing problem, J. Comput. Commun. 2 (04) (2014) 142.
[24] A. Sioud, C. Gagné, Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times, Eur. J. Oper. Res. 264 (1) (2018) 66–73.
[25] B. Zhang, Q.K. Pan, L. Gao, X.L. Zhang, H.Y. Sang, J.Q. Li, An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming, Appl. Soft Comput. 52 (2017) 14–27.
[26] T. Meng, Q.K. Pan, J.Q. Li, H.Y. Sang, An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem, Swarm Evol. Comput. 38 (2018) 64–78.
[27] Q.K. Pan, Y. Dong, An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation, Inf. Sci. 277 (2014) 643–655.
[28] K.Z. Gao, P.N. Suganthan, T.J. Chua, in: An Enhanced Migrating Birds Optimization Algorithm for No-Wait Flow Shop Scheduling Problem, IEEE, 2013, pp. 9–13.
[29] E. Duman, I. Elikucuk, Solving credit card fraud detection problem by the new metaheuristics migrating birds optimization62–71, International Work- Conference on Artificial Neural Networks, Springer, Berlin, Heidelberg, 2013.
[30] E. Ulker, V. Tongur, Migrating birds optimization (MBO) algorithm to solve knapsack problem, Proc. Comput. Sci. 111 (2017) 71–76.
[31] V. Tongur, E. Ülker, The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem, in: Intelligent and Evolutionary Systems, Springer, Cham, 2016, pp. 227–237.
[32] V. Tongur, E. Ülker, PSO-based improved multi-flocks migrating birds optimization (IMFMBO) algorithm for solution of discrete problems, Soft. Comput. 23 (14) (2019) 5469–5484.
[33] M. Hacibeyoglu, K. Alaykiran, A.M. Acilar, V. Tongur, E. Ulker, A Comparative Analysis of metaheuristic approaches for multidimensional two-way number partitioning problem, Arabian J. Sci. Eng. 43 (12) (2018) 7499–7520.
[34] Z. Li, M.N. Janardhanan, A.S. Ashour, N. Dey, Mathematical models and migrating birds optimization for robotic U-shaped assembly line balancing problem, Neural Comput. Appl. (2019) 1–17.
[35] F. Glover, Tabu search part I., ORSA J. Comput. 1 (3) (1989) 190–206.
[36] F.A.T. Montané, D.G. Roberto, A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res. 33 (3) (2006) 595–619.
[37] J. Grabowski, W. Mieczyslaw, A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Comput. Oper. Res. 31 (11) (2004) 1891–1909.
[38] C.N. Fiechter, A parallel tabu search algorithm for large traveling salesman problems, Discrete Appl. Math. 51 (3) (1994) 243–267.
[39] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Am. Assoc. Adv. Sci. 220 (4598) (1983) 671–680.
[40] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys. 21 (6) (1953) 1087–1092.
[41] H. Bagherlou, A. Ghaffari, A routing protocol for vehicular ad hoc networks using simulated annealing algorithm and neural networks, J. Supercomput. 74 (6) (2018) 2528–2552.
[42] L. Wei, Z. Zhang, D. Zhang, S.C. Leung, A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, Eur. J. Oper. Res. 265 (3) (2018) 843–859.
[43] K. Karagul, Y. Sahin, E. Aydemir, A. Oral, A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption, in: Lean and Green Supply Chain Management, Springer, Cham, 2019, pp. 161–187.
[44] M.M. Mafarja, S. Mirjalili, Hybrid whale optimization algorithm with simulated annealing for feature selection, Neurocomputing 260 (2017) 302– 312.
[45] S.H. Zhan, J. Lin, Z.J. Zhang, Y.W. Zhong, List-based simulated annealing algorithm for traveling salesman problem, Comput. Intell. Neurosci. 2016 (2016) 8.
[46] S. Kulturel-Konak, A. Konak, A large-scale hybrid simulated annealing algorithm for cyclic facility layout problems, Eng. Optim. 47 (7) (2015) 963– 978.
[47] N. Shivasankaran, P.S. Kumar, K.V. Raja, Hybrid sorting immune simulated annealing algorithm for flexible job shop scheduling, Int. J. Comput. Intell. Syst. 8 (3) (2015) 455–466.
[48] S. García, D. Molina, M. Lozano, F. Herrera, A study on the use of nonparametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization, J. Heuristics 15 (6) (2009) 617.
in binary computer arithmetic, ”IEEE Computer Group Repository, Paper R-67-85.
Related articles
The rights to this website are owned by the Raimag Press Management System.
Copyright © 2021-2025