Meta-heuristic methods to solve the problem of subway station facilities in urban management

الموضوعات :

Mehdi Fazli ¹ , somayyeh faraji amoogin ²

1 - Department of Mathematics, Islamic Azad University, Ardabil Branch, Ardabil, Iran
2 - Department of Mathematics, Islamic Azad University, Ardabil Branch, Ardabil, Iran

تاريخ الإرسال : 02 الأربعاء , ذو القعدة, 1443 تاريخ التأكيد : 08 الثلاثاء , ربيع الأول, 1444 تاريخ الإصدار : 05 السبت , ربيع الأول, 1444

الکلمات المفتاحية: Subway facilities problem, Optimization problem, Tabu search, Migrating bird optimization, Simulated Annealing,

ملخص المقالة :

We consider several location inventory optimization models for the supply chain configuration of subway facilities. It includes several distribution centers and several retailers. Customer demand and redelivery time are considered random. The goal is to find the optimal locations for facilities and their inventory policy simultaneously. For this purpose, a two-phase approach based on queuing theory and stochastic optimization was developed. Today, meta-heuristic methods are often used to solve optimization problems such as facility design. in this study; The design of different units, stores, and rooms of a real large-scale subway was organized using three meta-heuristic methods: Migratory Bird Optimization (MBO), Taboo Search (TS), and Simulated Simulation (SA). The results were compared with the existing subway design. As a result, the meta-heuristic methods of MBO and SA have provided the best results that improve the efficiency of the existing subway design to an acceptable level.

نص كامل:



Meta-heuristic methods to solve the problem of subway station facilities in urban management

 

 

 

 

 

 

 

 

abstract

We consider several location inventory optimization models for the supply chain configuration of subway facilities. It includes several distribution centers and several retailers. Customer demand and redelivery time are considered random. The goal is to find the optimal locations for facilities and their inventory policy simultaneously. For this purpose, a two-phase approach based on queuing theory and stochastic optimization was developed. Today, meta-heuristic methods are often used to solve optimization problems such as facility design. in this study; The design of different units, stores, and rooms of a real large-scale subway was organized using three meta-heuristic methods: Migratory Bird Optimization (MBO), Taboo Search (TS), and Simulated Simulation (SA). The results were compared with the existing subway design. As a result, the meta-heuristic methods of MBO and SA have provided the best results that improve the efficiency of the existing subway design to an acceptable level.

 

Keywords:

Subway facilities problem،Migrating bird optimization ،Optimization problem ،Tabu search ،Simulated annealing

 

1. Introduction

The problem of arranging terminal facilities has been less considered in the literature than other facilities because many aspects of customer choice cannot be controlled by transport managers [1] and demand is very vague [2]. Therefore, in addition to the complexity of the methods used to solve the terminal deployment problem, determining the problem definition, providing appropriate parameters, and obtaining reliable data are other critical points to achieve the best solution. The issue of terminal facility layout is mathematically an NP-Hard issue [3,4]. There are several common methods of solving the problem of arrangement of facilities in the literature, whether it is a one-class or multi-class problem. The first is the quadratic allocation (QAP) problem, which considers equal areas for each section and known locations [5]. The second is exploratory approaches that are effective in solving several layout problems simultaneously [6]. The third is mixed integer (MIP) programming, which uses a distance-based goal to design facilities for sections with equal and unequal regions [8]. The problem of allocating facilities has been defined by scientists as placing a predetermined number of facilities in the possible sizes and neighborhoods [9]. Lee and Lee hypothesized facilities in different areas to improve facility efficiency in a border area [10]. Shayan and Chittilappilly considered the issue of facility allocation as an optimization issue. They have achieved the optimal arrangement of facilities by considering the interactions between facilities and material handling costs [11]. In recent years, methods based on meta-innovation and crowded intelligence have been used to solve the problems of facility allocation. Shahin and Torkbi proposed a new hybrid meta-heuristic algorithm to solve multi-objective facility design problems based on simulated annealing (SA) and supported by the taboo list [12]. By integrating the Bee Algorithm (BA), Cheng and Lin proposed a hybrid algorithm for multi-facility design problems. Global search capability with local search benefits of particle swarm optimization (PSO) [13]. Using ant colony optimization (ACO), Lu et al. Proposed a new model for planning the layout of emergency medical facilities in the city [14]. Iller used ACO to design the layout of a hospital's laboratories, polyclinics, and radiology units, especially for outpatients, to minimize transportation costs. Huin et al. Reviewed the hospital cost analysis. They used the Autoregressive Integrated Moving Average (ARIMA) to estimate the number of applicants to the hospital. The GIS is also used to show the current reality or situation through the distribution of patients and hospital costs [16]. Aydin and Fogarty proposed a new method in which SA distributed evolution to solve the classical workshop scheduling problem and the problem of locating disabled facilities [17]. Kaveh and Sharafi used the Search Engine Optimization (CSS) method, which is based on the interaction between charged particles to solve the problem of allocating facilities in the network [18]. Kaveh et al. Proposed an adapted coordination search method to find an optimal facility allocation in an existing design [19]. Chan et al. Examined the mutation rate of fine-tuning the genetic method and SA neighborhood function to solve the problem of disabled facility location. They used variable mutation rates instead of fixed mutation rates or randomly selected genes and increased the efficiency of the method [20]. Young et al. Compared the performance of some metaheuristic methods in terms of mathematical modeling for the base station location planning problem, which was modeled as the p-median problem. As mentioned above, several studies in the literature have focused on the problems of allocating different facilities, but there are only a few studies on the problems of allocating different sections of the terminal. The purpose of this study is to create a multi-storey facility layout for terminals to minimize costs for it. The cost of relocating applicants can be reduced by minimizing travel between institutions. The problem with the optimal arrangement of our terminal facilities is that the best possible arrangement of sections is within a predefined range to reduce the distance between sections that are closely related to each other. We created a model for optimal placement of terminal sections at the lowest cost. Various alternative methods were developed from the proposed strategies and the best and most possible option was used. As a new paper, the Migratory Bird Optimization (MBO) algorithm is used for the first time to solve the problem of allocating facilities to a terminal. Local search is strong in the MBO method. In order to measure the performance of the MBO method in real-world problems, the MBO results are compared with the results obtained from the Tabu Search (TS) and SA algorithms. The SA algorithm was chosen because of its simplicity and good localization. The TS algorithm avoids local optimization and efficient global search. The results showed that the MBO algorithm increases the good performance to solve the problem of allocating facilities of one terminal. He rest of the article is organized as follows. The definition of the problem of allocating facilities for the terminal and the statistical information of this problem is presented in Section 2. The MBO, SA and TS metaheuristic methods are described in detail in Section 3. 4. Parameterization of meta-innovative methods used is described in Section 5. In Section 6, the computational results are presented and the paper concludes with a conclusion and discussion.

 

2. Model

 

The design and layout of subway facilities should include all the essential requirements such as mathematical modeling, entities, vertical movement, difficulty of movement, and arrangement of sections within the predefined range proposed by Ileri [15]. In a way that reduces the distance between highly interacting sectors and meets the increase in demand. In order to achieve efficient location of departments, the number of consultations between different departments should be considered. It depends on the frequency of travel between sections. The frequency of travel determines the communication factor, and the sections with the highest traffic should be closer to each other than the sections with the least traffic. We analyzed and modeled these factors with the aim of minimizing the total cost of movement.

      1- The interaction between stations, which depends on the intensity of traffic between two stations, was calculated to ensure that stations with more traffic are closer to stations that are quieter.

       2- The number of walk-in applicants to each station was calculated so that the stations with more applicants are closer to the main entrance of the applicant stations.

       3- Transportation cost was calculated directly based on distance, trip difficulty rating, trip frequency, and base trip cost, and thus changing any of these attributes changed transportation cost.

       4- The final optimal solution was obtained by performing simulations with the aim of changing one or some of these features.

 

To solve this problem, we formulated the objective function according to the physical structure of the subway, the number of parts to be placed with the required area, and the average monthly data of one year taken from the subway information system, including the number of applicants and the number of consultations.

The physical structure of the subway consists of three blocks, a parking lot with a defined area and a subway entrance. There are several parts with different sizes in the subway.

The size and distance to the subway entrance of the areas to be located are given in Table1.

       According to the inputs of Table 1 and the modeling entities described above, the objective function of the model is formulated as an equation.

    

                    (1)

 

Where n is the number of parking spaces, m is the number of areas where parking lots are located, xi is the distance between possible areas and the subway entrance, yi is the monthly number of applicants in the parking lot located up to the ith area, zjk is the number of applicants from the parking lot They have been sent to the jth area to the parking lot which has been placed in the return area. tjk is the distance between region j and return. The zjk matrix can be considered as a flow matrix in QAP problems. This matrix consists of consult values, which are the number of intra-terminal movements.

 

Table 1

The size and the distance to subway entrance of the areas to be placed.
Area Code	Distance to entrance	Size
0	10	800
1	10	800
2	20	800
3	20	800
4	60	800
5	60	800
6	70	800
7	70	800
8	110	800
9	110	800
10	120	800
11	120	800
12	160	800
13	160	800
14	170	800
15	170	800
16	210	800
17	220	800
18	220	800
19	210	800
20	240	800
21	250	800
22	250	800
23	240	800
24	260	800
25	270	800
26	270	800
27	260	800
28	310	800
29	320	800
30	320	800
31	310	800

 

Our study had two main limitations. First of all, the allocation of subway facilities should take into account the costs associated with the relocation of the applicant and the relocation of vehicles, but we did not consider the number of vehicles because it was impossible to obtain valid data. Second, terminals were not considered by the staff because their relocation directly depends on the needs of the primary travel establishments.

 

3. Methods

 

   3.1. The MBO migratory bird optimization method was first proposed by Duman et al. In 2012 [22]. MBO is inspired by the energy savings of migratory birds flying in the V Formation. This method is designed for discrete problems and has been tested and implemented on QAP problems that are based on real-life problems.

      The most common method of flight of migratory birds is the V Formation so that they can fly longer distances without fatigue. It is clear that in this method, the main instinct of this formation is energy saving. The leader bird is the bird that expends the most energy in V formation. Other birds can fly longer due to the wind energy generated by the movement of the bird's wings in front of them.

      MBO technique in the literature to solve many problems such as the flow store problem [23-28], also the backpack problem [33], or in the credit card fraud detection case [29] and in the traveling salesman problem [31,32], partitioning the double-sided number is used [33], it is also used to balance the robotic U-shaped assembly line [34].

     The MBO technique starts with the initial answers generated randomly and then tries to improve these answers at each stage. Swap, insert, and reverse operations are used to create candidate answers for the neighbor to improve existing answers. The close answers of the created candidate are then shared with the answer that the method seeks. Each current answer is compared to the neighbor's best answer. If the neighbor's answer is better than the current answer, the neighbor's answer is replaced with the current answer. In addition, the replacement of the leader is done at certain times to bring better answers to both sides of the herd. The MBO technique involves the production of the initial population, the neighbor sharing process, the production of the candidate's response, and the steps of replacing the leader.

 

3.1.1. Initial population generation

      The MBO technique starts with the initial answers that are randomly selected and try to improve the current answer. One of these birds is selected as the leader bird and the resting birds are placed to the right and left of the leader bird. Thus, the initial population is created as described. Where the initial population of each bird shows an initial answer.

3.1.2. Candidate solution generation

        The MBO technique uses inversion operations to generate candidate neighbors for local search. In this method, the candidate neighbor solutions are obtained randomly from the current solution by exchanging two selected positions. The number of candidate neighbor responses for the leader bird and the number of candidate solutions for the resting bird vary according to the structure of the MBO method. The number of candidate neighbor solutions is calculated from the equations (2) - (4) [32].

 

Where k is the number of responses of the leader bird neighbor, r is the number of neighbor responses of other birds, except for the leader bird, p is the number of neighbors.

     An example of generating candidate neighbor solution with swap operation is shown in Fig. 1 [32].

 

3.1.3. Neighbor sharing process

      Neighbor sharing mechanism and process is a special feature of MBO technique that distinguishes MBO method from other meta-heuristic techniques. This special feature ensures the interaction of all members of the herd. The answers of the Leader Bird neighbor are shared on the left and right of the members. Other birds' neighbor responses are shared only for themselves. According to Equation (2), k produces a neighbor solution for the leader member. These neighboring answers are evaluated according to the final objective function and descend from the best answer to the worst solution. The best answer is compared to the current answer of the leader member. If the neighbor's member is better than the current answer, the neighbor's answer replaces the current answer. The remaining neighbor p solutions are transferred to the bird to the left of the leader's member. After these processes, the remaining neighbor answers (if any) are discarded. Neighbor answers are generated for the bird to the left of the leader's member, and p answers coming from the leader are added. These p + r answers are evaluated and sorted from best to worst. The best answer from the neighbor is compared to the current answer of this bird. If the neighbor's answer is better than the current answer, the neighbor's answer replaces the current answer.

 

 

 

               Swap

 

 

	(2)
;	(3)
	(4)

2

0

4

1

3

5

1

0

4

2

3

5

                                  Fig. 1. Neighbor solution generation.

 

The remaining p solutions are transferred to the following bird and other neighboring solutions are discarded. This process is also applied to the other side or to the right of the herd. Neighbor subscriptions are repeated until the end of the herd series.

 

3.1.4. Leader replacement

      The MBO technique uses the variable flap (f) to hold individuals in a sequence for a predetermined period of time. The replacement process is then run. The first replacement is made to the left of the herd members. When the leader is led to the left of the herd members, another bird looking for the leader's member is replaced by the leader. Thus, a new sequence is created and the variable m is reset. The next alternative is applied to the right of the herd. This process continues until the end of the method and algorithm.

      The pseudo-code of MBO algorithm in algorithm 1 is given as follows:

 

      Algorithm MBO. The pseudo code of the MBO algorithm

          Create a random initial population

          Repeat

         Repeat

         k Create a neighbor for the leader

         Create r neighbors for other solutions

         Share best value of p neighbors to rear solution

         If (best neighbor solution < amount of current solution)

         Current solution = neighbor solution

         Until flap value

         Replace leader

         Until termination criterion

         Return the best solution in the flock

 

3.2. Tabu search algorithm

      The TS technique was first proposed by Glover for hybrid optimization problems in 1989 [35]. In the literature, the TS method has been used in many different optimization problems such as the vehicle routing problem [36], as well as the traveling vendor problem [38], or the flow shop problem [37].

       In the TS method, a single answer is generated and an attempt is made to find the optimal global solution using local search techniques such as swap and insert operations. There are usually two different memory structures in the TS technique. Memory and structures of long-term memory Short-term memory allows you to choose the best possible move to generate a new answer and prevents the production of some answers called taboos. In this way, the TS technique avoids local optimization and seeks global optimization. When the default value is reached, the specified taboo is broken and the previously found answer can be re-selected as the new answer. During the search process, the best answer found by the TS method is stored in long-term memory, and all generated answers are compared with the best answer. If there is a better answer than the best answer, the long-term memory will be updated.

       The pseudo-code of TS algorithm in Algorithm 2 is given as follows:

 

       Algorithm TS. The pseudo code of the TS algorithm

            Create the initial solution at random. Set this solution as the

            current solution and the best optimal solution.

            Repeat

            Find optimal neighbor solutions using local search techniques.

            Select a neighboring solution that non-tabu or meets tabu

            break criteria, even if it is tabu.

            If the new answer is better than the current answer, select the new solution as taboo

            If the new answer is better than the best solution, put the new solution as the best optimal answer

            Until termination criterion

 

3.3. Simulated annealing algorithm

The SA technique was proposed by Kirkpatrick et al. To solve complex compositional problems [39]. The SA technique is designed to find the optimal solution by avoiding local solutions for functions with multiple variables. This technique is named because it is an example of the complete arrangement of atoms and the minimization of potential energy when cooling solid objects. The process of heating a solid to its melting point and then slowly cooling it to a complete lattice structure is known as annealing.

The simulated annealing technique is performed in three separate steps: heating the body or material to a certain temperature (heating), maintaining this temperature for a suitable time (waiting) and gradually and controlled temperature reduction (cold). Become). During heating, the particles in the solid state slowly turn into a liquid, and when cooled properly, crystalline particles are formed with a regular structure.

           The stages of this problem and its process are physical annealing based on the Monte Carlo method by Metropolis et al [41]. At a given temperature T, the probability distribution of the device's energies is determined based on the corresponding equation (5).

 

In this formula, k is the Boltzmann constant and E is the system energy and.

If there is a change in the status of the device, the new energy of the device is calculated based on the metropolitan method. The current state of a solid object with energy E1 changes mechanically with the displacement of a randomly selected small piece, and the energy level of E2 changes to another state. If the energy decreases (DE = (E2-E1) <0), the device will switch to this new mode. If the energy increases (DE> 0), it is decided whether to accept the new state of energy E1 according to Equation (6). A uniform number is generated in a certain interval (ɤe [0,1]). If you get the condition given in the relation, the new answer will be accepted as the optimal answer. Otherwise the existing solution will not change.

(5)

In this equation, DE is the difference between the energy levels of two different states. This acceptance criterion is known as metropolitan criteria. According to Equation (5), for all energy modes at high temperatures, P (E) converges to 1. Presumably, the device may have high energy levels, even at low temperatures.

      The simulated annealing technique has yielded acceptable results in vehicle routing [44-46], feature selection [47], itinerant vendor problem [45], facility allocation problems [46], and workshop scheduling [48].

       The pseudo code of the SA algorithm is as follows:

 

Algorithm SA. The pseudo code of the SA algorithm

 

         The pseudo code of the SA method as follow

         Randomly generate the initial solution of Si   

         Repeat

         Create a Sn neighbor solution

         If (Sn answer better than Si)

         Set Sn as the available solution

         else if ()

         Set Sn as the available solution

         Update T

         Until termination criterion

 

4. Implement meta- heuristics in the issue of allocating subway facilities

 

       The problem addressed in this study is a discrete one. Metamorphosis TS, SA and MBO are designed and implemented for discrete problems. Therefore, there is no change in the structure of methods to solve the problem of allocating terminal facilities. To solve this problem, parking codes are randomly arranged. The value in the array is the parking number. An example of a parking arrangement is shown in Figure 2.

In Figure 2, parking lot 2 is located in area 0. After all parking lots are located in the existing areas, the suitability of the solution is evaluated according to Equation (1). This solution is evaluated by considering the distance from the area where the parking lots are located, the distance to the subway entrance, the number of applicants to the parking lot, the applicant's consultation between the parking lots and the distance between the parking lots.

 

         Area No

 

(6)

0	1	2	3	4	5	6	7	8	9		31
2	0	4	1	3	5	9	7	6	8	…	13

 

station No

Fig. 2. Permutation coding for a solution

 

Example. Assume that four station lots (A, B, C, D) are located in five equal areas. Tables 2-4 show the number of applicants to the station lot, the applicants' advice between the station lot, the areas to be located and the distances to the terminal entrance.

      In Table 2, station lot B is shown as two separate station lots, because it has twice the area to be placed. The number of applicants in Table 2 represents the variable y in Equation (1).

        n Table 3, columns 2 and 3 represent the same station lots (B) and should be located in the adjacent area. Therefore, the number of consultations among themselves is very high (500). Table 3 shows the z matrix in Equation (1).

         According to the sample solution, the station 4, 2, 5, 1 and 3 are placed in the 1st, 2nd, 3rd, 4th and 5th areas respectively.

       Table 5 represents matrix t in the Eq (1). A sample solution is as follows.

 

4

2

5

1

3

 

5. Parameter settings

 

In order to get the best solution from the station lot problem, parameter settings are done for both methods.

 

 

 

Table 2

 

Number of applicants coming to the station.
Parking No (Name)	Number of applicant (y)	Required size (m2)
1 (A)	14,609	800
2 (B)	55,406	1600
3 (B)
4 (C)	27,421	800
5 (D)	10,684	800

 

 

Table 3

The number of applicants consultations between the station.
	station sending consultations
	No	1	2		3	4	5
station accepting consultations	1	0	75		75	16	85
	2	14	0		500	50	41
	3	14	500		0	50	41
	4	40	9		9	0	63
	5	32	3		3	4	0

 

Table 4

Size of area and distances to the  station entrance.
Area No	Size	Distance to the entrance (x)
1	800	10
2	800	10
3	800	20
4	800	20
5	800	30

 

Table 5

The distance between the areas.
	1	2	3		4	5
1	0	5	10		10	20
2	5	0	10		10	20
3	10	10	0		5	10
4	10	10	5		0	10
5	20	20	10		10	0

 

In parameter settings, the TS and the MBO methods are run 30 times independently and the parameters are selected according to the average of the best results.

 

5.1. MBO parameter setting

      In the MBO technique, four parameters are examined. These parameters are neighborhood, population, shake, and subscription.

      Table 6 presents the population parameters with values of 61, 51, 41 and 31. Flap, neighborhood, and share parameters are set to 20, 3, and 1, respectively. As you can see in Table 6, the best mean value in the population = 61 is obtained. It can also be seen in Table 7 that the best mean value is obtained in flap = 20. 

       Table 7 evaluates the flap parameters with values of 50, 40, 30 and 20. The subscription, neighborhood and population parameters are fixed at 1, 3 and 61, respectively.

        In Table 8, the neighbor parameter is evaluated with values of 9, 7, 5 and 3. Sharing, shaking, and population parameters are fixed at 1, 20, and 61, respectively.

        As can be seen from the data in Table 8, the best mean value in the neighbor = 3 is obtained. According to the structure of the MBO technique, the minimum value of the neighbor parameter can be attributed to the number 3. According to Equation (3), if k = 3, the subscription parameter (p) can only be 1. Therefore, the sharing parameter does not need to be checked and we set its value to 1.

According to the tables obtained from the analysis of data and parameters, the best parameters of the MBO technique are given in Table 9. 

 

 

5.2. TS parameter setting

      Three different parameters 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

Parameter setting of population.
Fixed Parameters			Population Value		Fitness Average
Parameter	Value
Flap	20	31		10447906,36
Neighbor	3	41		10381691,10
Share	1	51		10340931,30
		61		10290411,95

 

Table 7

Parameter setting of flap.
Fixed Parameters			Flap Value		Fitness Average
Parameter	Value
Population	61	20		10237226,00
Neighbor	3	30		10276514,80
Share	1	40		10302385,16
		50		10256843,93

 

 

Table 8

Parameter setting of neighbor.
Fixed Parameters			Neighbor Value		Fitness Average
Parameter	Value
Population	61	3		10224274,63
Flap	20	5		10275422,16
Share	1	7		10305902,26
		9		10269521,46

 

Table 9

Best parameters for the MBO.
Parameters	Value
Population	61
Flap	20
Neighbor	3
Share	1

 

Table 10

Parameter setting of tabu length.
Fixed Parameters			Tabu length Value		Fitness Average
Parameter	Value
Penalizing long term	61	10		11324841,17
		20		11162676,17
long term length	100	30		11000655,80
		40		11293772,77

 

 

        In Table 10, the taboo length parameters with values of 40, 30, 20 and 10 are tested and evaluated. The long-term fine and long-term parameters are fixed at 100 and 10, respectively. As you can see from the data in Table 10, the best average value during the taboo = 30 is obtained.

        As shown in Table 11, the long-term penalty parameter is evaluated at different values of 20, 15, 10 and 5. The long-term and taboo parameters are fixed at 100 and 30, respectively. As can be seen from Table 11, the best average value over a long-term penalty is = 20.

        Table 12 evaluates and evaluates different long-term length numbers and parameters with 110, 100, 90 and 80 test values. The parameters of long-term penalty and taboo length are fixed at constant values of 20 and 30, respectively. As shown in Table 12, the best mean value is obtained in the long run = 80.

       According to the results and observations obtained from the study of various parameters, the best parameters of the TS technique are collected in Table 13.

Table 11

Parameter setting of penalizing long term.
Fixed Parameters		Penalizing long term		Fitness
Parameter	Value		Value	Average
tabu length	30		5	11163703,20
			10	11391734,70
long term length	100		15	11268983,43
			20	11133762,73

 

Table 12

Parameter setting of long term length.
Fixed Parameters		long term length			Fitness
Parameter	Value		Value	Average
tabu length	30		80	10979237,50
			90	10991142,00
long term length	20		100	11203672,33
			110	11203930,57

 

 

Table 13

Best parameters for the TS.
Parameters	Value
tabu length	30
penalizing long term	20
long term length	80

 

6. Experimental results

 

       Given that this is a special problem, the results of this problem can not be compared with the results of standard problems in the literature. Therefore, this problem is solved not only with MBO but also with SA and TS to ensure the accuracy of the results. The tests are performed with an Intel (R) Core (TM) i5-3330 @ 3.00 GHz processor, 2 GB of RAM and Ubuntu 14.04 (32-bit) Linux operating system. All methods and techniques are encoded with QT Creator 3.1.1 gcc compiler and C ++ language. In each technique, the algorithms are run 30 times dependently to ensure results. Each test runs for 100 seconds. Depending on the parameter settings, 100 seconds is sufficient for both techniques. Parking maps obtained from SA, MBO and TS tests are given in Table 14.

 

According to the results and data of Table 14, the best result obtained from the MBO and SA technique is equal to 10142848. On the other hand, according to the numbers in Table 14, the best result obtained in the TS technique is equal to 10254893, which is about 1.1% worse than the MBO and SA techniques.

      Existing station plan and allocation of station plan. The best results of the MBO and SA algorithms and techniques are given in Table 15.

       According to Table 15, parking lots 0-3 are located on floor 0 of C-Block. Due to the number of consultations it seems to flow from each station lot to the hall. Considering the parking number of the station lots and the distance to the halls, it may be reasonable to place the halls on the 0th floor of the block. Station lots 6 and 7 are on the 0th floor without blocks, parking lots 13 and 14 are on the 0th floor of block A and parking lots 25 and 26 are on the 1st floor of the A-Block. As can be seen in Table 15, the proposed station layout and the existing parking layout are almost completely different, except for parking 10 and 17. They are both located on the 1st floor of the B-Block. In addition, the fit values ​​of the proposed design and layout allocation are given in Table 15. According to the proposal, the current layout allocation has been improved.

The convergence rates of the MBO and TS methods are closer to each other and faster than the SA method. But the results obtained from the SA method are better than the MBO and TS algorithms according to the average and worst results.

 

Table 14

The results obtained from the MBO, TS and SA.
	Algorithms
	MBO	TS	SA
Min.	10142848,0	10254893,0	10142848,0
Avg.	10236612,3	11054017,2	10158816,4
Worst	0652953,0	11872804,0	10331538,0

 

 

Table 15

Existing and proposed station layout.
Block	Floor	Proposed station Layout		Existing station Layout
A-Block	0	13, 14, 29, 8		29, 23, 30, 22
	1	26, 25, 5, 12		8, 16, 24, 31
B-Block	0	4, 6, 7, 11		15, 18, 19, 28
	1	10, 27, 17, 23		10, 11, 17, 21
C-Block	-1	19, 16, 31, 22		12, 20, 4, 5
	0	2, 0, 3, 1		6, 7, 9, 27
	1	18, 9, 15, 24		13, 14, 25, 26
	2	21, 28, 30, 20		0, 1, 2, 3
Fitness Value			10, 142, 848		17, 433, 012

 

The results obtained from all three meta-heuristic methods are statistically analyzed and tested. In this regard, the Wilcoxon test is used to investigate whether there is a significant difference between the methods used. There is no profound difference between the two methods compared to H0 hypothesis. There is a fundamental difference between the two methods compared to the H1 alternative hypothesis. The acceptance value of H0 hypothesis is set at 95%. That is, if the difference between the two methods is less than 5% (a = 0.05), there is a fundamental difference between the two methods. The results of the methods are recorded in Table 16 at a significance level of 5%.

Table 16

p-values obtained from Wilcoxon test.
p-values
MBO&TS	MBO&SA	SA&TS
0	0,149	0

 

According to the studies in Table 16, there is no significant difference between MBO and SA methods (0.149> 0.05). On the other hand, it is observed that there is a significant difference between MBO and TS methods with TS and SA methods (<0.05).

 

7. Conclusion and discussion

 

In this section, there are urban life optimization problems that we can face in several areas of our daily life. Today, meta-heuristic methods are used to solve these optimization problems. Placing facilities in appropriate areas in the problem of facility allocation increases operational efficiency by reducing production costs, delivery time, and processing. The location of the stations inside the metro plays an important role in determining the commuting time of applicants and metro employees. The transfer time of the applicant is to go directly to the station for services or to provide services from one station to another. The lengthening of these transportation times leads to a longer stay in the metro and a decrease in the efficiency of the metro. Therefore, the correct placement of these walk-in stations ensures the optimal use of metro electricity and minimizes the unnecessary distance between applicants, employees and visitors and increases the productivity of the metro. In this study, we used the heuristic meta-explorations of MBO, SA, and TS to allocate station space for a large-scale subway. Based on the results obtained from the experiments, the success of the MBO, SA and TS methods in facility allocation problems is tested on an urban problem and it is observed that the total cost of the MBO and SA methods is much better than the TS technique. When the fitting value obtained from the experimental results is compared with the existing fitting value, it is observed that it has a good performance. As a result, technology can be used to allocate metro stations. For future work, some assumptions and constraints can be added to the problem. As if an applicant has several turns at several stations or some passengers need support to move. Passenger replenishment operations 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. 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.

---