Fuzzy c-means and simulated annealing for planar location-routing problem

Abstract

Location-routing problem (LRP) contains two Np-hard problems as, facility location (FL) and vehicle routing problem (VRP), in the same content. Since both problems directly affect the cost of distributions of the products and supply chain, the decision of location and routing is important for the success of companies. Therefore, many attempts are made to solve LRP problem in the literature. Researchers proposed exact and heuristic methods for LRP. However, exact methods cannot provide solutions for considerably large instances. In this paper, a new heuristic method is proposed for continuous or planar LRP. The proposed method contains fuzzy c-means for continuous location problem and simulated annealing algorithm for vehicle routing problem, respectively. The proposed method is applied to both capacitated and uncapacitated LRP instances that are widely used in the literature. Results of the proposed method are compared with successful researches that are made on this problem in terms of the total cost.

Keywords

Location-routing problem simulated annealing algorithm fuzzy c-means

1 Introduction

Logistics decisions are crucial for companies since logistics expenditures account for a significant portion of their budget. The costs of logistics can be reduced by effective supply chain design. The design of a supply chain that involves a flow of products is directly affected by the locations of the facilities and the route of the vehicles. Previously, in the literature, many approaches were made to solve these problems separately.

However, thanks to the development of optimization tools, these two problems are considered together simultaneously as the name of the location and routing problem (LRP) [6]. Furthermore, because of its significant role in the success of companies, this problem has gained interest in the academic area.

Since the location problem-routing problem is an NP-hard problem and LRP considers both problems as integrated, different solution approaches are proposed to solve LRP by researchers. Both discrete and continuous location-routing problem are studied by researchers. Especially there are many different approaches made in a discrete location-routing problem, such as exact and heuristic solutions provided for this particular problem. The reason why in the literature, LRP can be classified into two different categories as exact and heuristics methods [11]. In this part of the paper, the literature review of the LRP is divided into discrete and continuous LRP. Since the continuous or planar LRP approaches in the literature include only heuristic algorithms, discrete LRP research papers are detailed in exact and heuristic methods.

1.1 Discrete location-routing problem

A discrete location-routing problem contains facility location decisions made among candidate facilities. Locations of candidate facilities are known at the beginning of the problem. Researchers make the decision to open the correct number of facilities and their coordinates with the routing decisions in the light of customers and candidate facilities information. The first attempt to model LRP is suggested by Watson-Gandy and Dohrn [9]. Visits of customers to the facility are considered in facility location problem. Branch-and-bound algorithm, which is used as the first exact method for LRP, is proposed by Laporte and Nobert [13]. Belenguer et al. [16] applied a branch and cut algorithm to LRP. A branch-and-cut algorithm is developed by Laporte et al. [14] to solve a multi-depot LRP model with vehicle capacity constraints. Akca et al. [42] suggested a branch-price algorithm to solve capacitated LRP with multiple depots and trucks. Baldacci et al. [27] proposed a new exact algorithm for capacitated FLP. Contardo et al. [4] developed a branch-and-cut-and-price algorithm for the capacitated location-routing problem. Xie et al. [39] proposed integer programming for LRP. Panboon et al. [32] developed a branch-and-price algorithm for LRP with time windows. However, it is discussed by researchers that in large instances, exact methods of LRP can be inefficient [1, 2].

Several different heuristic methods are employed for discrete LRP. The motivation of the heuristic approaches is the inefficiency of exact methods in considerably large instances. A GRASP+ILP-based metaheuristic algorithm is proposed by Contardo et al. [5]. A two-phase tabu search algorithm is applied by Tuzun and Burke [10]. The algorithm starts with a random facility location and routing process initialized with this point. Location decision is employed as phase I, and routing decision is applied as phase II. Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking is developed by Prins et al. [7]. Memetic Algorithm with Population Management is applied by Prins et al. [8]. Clustering analysis is proposed by Baretto et al. [34] for capacitated LRP. Lagrangian Relaxation (LR) and Granular Tabu Search (GTS) is developed by Prins et al. [8]. A hybrid of greedy randomized adaptive search procedure (GRASP) and variable neighbourhood descent (VND) algorithm is adopted for capacitated LRP with a single truck by Villegas et al. [15]. Escobar et al. [17] proposed a two-phase hybrid algorithm for the capacitated LRP. In the first phase of the study, a modified granular tabu search is applied, while different diversification strategies are employed in the second phase. Approximation algorithms are applied by Harks et al. [38]. Escobar et al. [18] proposed a granular variable tabu neighbourhood search for capacitated LRP. The two-stage heuristic algorithm for large instances is developed by Guemri et al. [25]. A large composite neighborhoods algorithm is proposed by Schneider and Löffler [23]. Akpunar and Akpinar [26] developed a hybrid adaptive large neighbourhood search algorithm for the capacitated LRP. The new hybrid metaheuristic algorithm that combines an adaptive large neighbourhood search (ALNS) and the variable neighbourhood search (VNS) algorithms is proposed and compared with the well-known instances in terms of the total cost. Nucamendi-Guillén et al. [31] proposed new formulations and solution approaches for the latency LRP. Branch and check algorithm with rounded capacity (B&CK-RC) and Branch and check algorithm with no good cut (B&CK-NG) are proposed in their paper. The results of the proposed exact algorithms are compared with the branch and cut algorithm (BC) in terms of total cost and computation time. Ferreira and Queiroz [19] proposed a hybrid heuristic algorithm that applies Simulated Annealing (SA) and Artificial Algae Algorithm (AAA) for the LRP with two-dimensional loading constraints (2L-LRP).

1.2 Continuous/Planar location-routing problem

As opposed to a discrete location-routing problem, a continuous or planar location-routing problem contains a facility location problem where the facilities can be located anywhere on the plane. Studies that are made in continuous LRP are listed in Table 1.

Table 1
Continuous/Planar location-routing problem literature survey

Reference Model Solution Vehicle type Facility type Number of facility Facility location problem

Manzour-al-Ajdad et al. [30] A hierarchical algorithm Heuristic Capacitated Capacitated Single Continuous

Rybickova et al. [3] Genetic Algorithm Heuristic Capacitated Uncapacitated Multiple Continuous

Schwardt and Fischer [22] Neural network approach on self-organising maps Heuristic Capacitated Capacitated Single Continuous

Schwardt and Dethloff [21] A self-organizing map Heuristic Capacitated Capacitated Single Continuous

Salhi and Nagy [33] The end-point algorithm Heuristic Capacitated Uncapacitated Single and Multiple Continuous

Carnes and Syhmos [37] Primal-Dual Schema and Lagrangian Relaxation Heuristic Capacitated Uncapacitated Multiple Continuous

Ghodsi and Amiri [28] Variable Neighborhood Search algorithm Heuristic Capacitated Capacitated Single and Multiple Continuous

Reference	Model	Solution	Vehicle type	Facility type	Number of facility	Facility location problem
Manzour-al-Ajdad et al. [30]	A hierarchical algorithm	Heuristic	Capacitated	Capacitated	Single	Continuous
Rybickova et al. [3]	Genetic Algorithm	Heuristic	Capacitated	Uncapacitated	Multiple	Continuous
Schwardt and Fischer [22]	Neural network approach on self-organising maps	Heuristic	Capacitated	Capacitated	Single	Continuous
Schwardt and Dethloff [21]	A self-organizing map	Heuristic	Capacitated	Capacitated	Single	Continuous
Salhi and Nagy [33]	The end-point algorithm	Heuristic	Capacitated	Uncapacitated	Single and Multiple	Continuous
Carnes and Syhmos [37]	Primal-Dual Schema and Lagrangian Relaxation	Heuristic	Capacitated	Uncapacitated	Multiple	Continuous
Ghodsi and Amiri [28]	Variable Neighborhood Search algorithm	Heuristic	Capacitated	Capacitated	Single and Multiple	Continuous

A self-organizing map heuristic algorithm is applied for capacitated and continuous LRP with a single depot by Schwardt and Dethloff [21]. In this paper, vehicles and depot have capacity constraints. However, the proposed method contains solutions for only one depot. The end-point algorithm is developed by Salhi and Nagy [33]. This heuristic algorithm gives a solution for continuous LRP when there is a capacity constraint on vehicles and no capacity constraint on depots. Solutions are provided for both single and multiple depots. Multiple depot solutions include only two depots. There is no solution for the problems where depots are more than two. A hybrid heuristic algorithm that combines neural network and self-organizing maps is proposed by Schwardt and Fischer [22]. The algorithm gives results for continuous LRP with a single depot where vehicles and depot have capacity constraints. A variable neighborhood search algorithm is developed by Ghodsi and Amiri [28]. Solutions are made for continuous capacitated LRP with single and multiple depots. There are capacity constraints on both vehicles and depots. However, multiple depot solutions are made for two depots. There is no solution for the problems where depots are more than two. A hierarchical heuristic algorithm is applied by Manzour-al-Ajdad et al. [30]. The proposed algorithm gives solutions for continuous and capacitated LRP with a single depot. Vehicles and depot have capacity constraints. A genetic algorithm is utilized by Rybickova et al. [3] for multiple depots continuous LRP where there is a capacity constraint on vehicles and no capacity constraints on depots.

All of the studies in Table 1 propose solutions for continuous LRP. However, only Rybickova et al. [3] developed solutions for the problem with multiple depots. The rest of the studies in Table 1 apply heuristics for the problem where the number of depots is one or two. This situation encouraged us to develop a heuristic algorithm that can provide solutions for continuous LRP with and without capacity constraints on multiple depots.

To the best of our knowledge, no research has been proposed combining the simulated annealing technique and fuzzy c-means for continuous and capacitated LRP with multiple depots.

In the literature, most of the researches have been made about this problem focus on discrete location problem. However, the continuous location problem is also one of the most studied topics among researchers. There are limited studies about the continuous LRP in the literature as opposed to the location problem. Since LRP has essential impacts on the success of the companies and not necessarily in all real problems contain discrete LRP, we strongly believe that the proposed algorithm is one of the successful attempts to fill this gap. The main objective of this paper is to present an efficient algorithm for continuous LRP.

The motivation of this study depends on some reasons. First of all, the research on planar LRP is open to development. There are very limited researches on planar LRP. In addition, the real applications of LRP are increased in the last years. Some of them can be counted as follows: First, since governments and companies nowadays have started planning to use electric vehicles, the locations of electric charging stations are needed to be determined with considering the routing of the vehicles. Second, with the COVID-19 pandemic, the problem of collecting medical disposals with vehicles to disposal centers, which can be considered as LRP, is faced as a problem to be solved. Exact algorithms might not find a solution when applied to large instances as opposed to the proposed algorithm. Since real-life applications might have large instances, the proposed algorithm might be used as an efficient solution procedure for these applications.

The motivation of the study is to develop a heuristic algorithm that can provide quick and near-optimal solutions for continuous LRP with and without capacity constraints on multiple depots, even with large instances.

The rest of the paper is organized as follows. Definition and detailed explanation of location and routing problem is given in Section 2. Section 3 contains details of the proposed algorithm. Results and comparisons of the performance of the proposed algorithm against benchmarking methods are discussed in Section 4. Conclusion and suggestions for future studies are presented in the last section.

2 Problem definition

Equations of planar single facility location and routing problem (PSFLRP), developed by Salhi and Nagy [33], are given in Equations (1)–(8): $Min \sum_{v \in V} \sum_{j \in I \cup J} \sum_{i \in I \cup J} X_{ijv} ∥ x_{i} - y_{j} ∥$ (1) Subject to: $\sum_{i \in I} d_{i} \sum_{j \in I \cup J} X_{ijv} ⩽ C, v \in V$ (2) $\sum_{v \in V} \sum_{j \in I \cup J} X_{ijv} = 1, i \in I$ (3) $\sum_{v \in V} \sum_{j \in S} \sum_{j \in (I \cup J ∖ S)} X_{ijv} ⩾ 1, S \subseteq I$ (4) $\sum_{i \in I \cup J} X_{ijv} - \sum_{i \in I \cup J} X_{jiv} = 0, v \in V, j \in I \cup J$ (5) $\sum_{j \in J} \sum_{i \in I \cup J} X_{ijv} ⩽ 1, v \in V$ (6) $X_{ijv} = 0, 1, i \in I \cup J, j \in I \cup J, v \in V$ (7) $y_{j} \in R^{2}, j \in J$ (8)

Where I is the customer set (i = 1,2, . . . .,n), J is the depot set (j = n+1, . . . . . . ,n+p), V is the vehicle set, x_i is the customer i coordinates, y_j is the coordinates of depot j, d_i is the demand of customer i, v is the number of vehicles, C is the vehicle capacity, X_ijv is a decision variable of depot if the depot j serve to customer i with vehicle v, the value is one otherwise zero. Equation (1) is the objective function that minimizes the total transportation cost. Equation (2) ensures that the capacity of vehicles is not violated. Equation (3) denotes that each customer is assigned to exactly one tour. Equation (4) guarantees that each customer is on a route belonging to the set of depots. Equation (5) ensures that the same vehicle enters and exits from the visited depot. Equation (6) provides that each vehicle can only depart the depot once. X_ijv is a binary variable, and y_j is a real number, according to Equations (7) and (8).

Note that the proposed algorithm is developed not only for (PSFLRP) but also for planar multiple facility location and routing problem in this study.

2.1 Fuzzy c-means algorithm

The fuzzy C-Means algorithm is a different version of the K-Means algorithm where fuzzy logic is applied and aims to reach the minimum objective function value.

FCM algorithm and its hybrid algorithms are adapted to multi-facility location problem (MFLP) by [20 , 41] in the literature. These studies suggested that the FCM algorithm might give efficient results for MFLP in terms of total cost and computational time. In addition, clustering analysis, proposed by Baretto et al. [34], is one of the successful heuristic algorithms for discrete LRP in the literature. In this paper, it is demonstrated that assigning customers to clusters increases the efficiency of vehicle routing problem. Depending on the results maintained by these researches, the FCM algorithm is utilized for the planar facility location part of the problem.

Steps of the Fuzzy C-Means algorithm are given in Equations (9)–(11) [12]: $O_{μ} (M, y) = \sum_{i = 1}^{n} \sum_{j = 1}^{k} d_{i} {(m_{ij})}^{μ} ∥ x_{i} - y_{j} ∥^{2}$ (9)

Step 1: Assign membership matrix randomly M⁽⁰⁾=[m_ij].

Step 2: Calculate cluster centers using Equation (10): $y_{j} = \frac{\sum_{i = 1}^{n} {(m_{ij})}^{μ} x_{i}}{\sum_{i = 1}^{n} {(m_{ij})}^{μ}}$ (10)

Step 3: Update membership values using Equation (11): $m_{ij} = \frac{1}{\sum_{j = 1}^{k} {(\frac{x_{i} - y_{i}}{x_{i} - y_{j}})}^{\frac{2}{μ - 1}}}$ (11)

Step 4: The algorithm stops if the differences between total costs (O_μ) are calculated by consecutive membership matrixes M_k, M_k +1 less than the stopping criteria. Here, k and n number of clusters and customers, respectively. xi is the coordinates of the customer i, while y_j is the coordinates of cluster j. μ is the coefficient of membership. M or [m_ij] is the membership matrix. Oμ(M_y) is the total cost function of the algorithm. |x_i-y_j| is the Euclidean distance between cluster j and customer i.

2.2 Simulated annealing algorithm

Simulated annealing is first developed by Kirkpatrick et al. [29] and Cerny [40]. It is a probabilistic method applied to find the global minimum by using the cost function. This algorithm has gained interest in the academic field because of its successful capability of avoiding local optima.

Simulated annealing algorithm steps are given below:

Step 1: Set random initial state and initial temperature.

Step 2: Until maximum iteration is reached by algorithm or/and the number of required states are generated, generate new solutions and evaluate the change in energy. If the difference in energy is less than zero, accept the move and update configurations. Else, check the condition α ≤ e^(-ΔE)/T. If the condition is satisfied, update configurations. If not, increase the iteration value by one and continue.

Step 3: Until the stopping criteria is satisfied, update the temperature.

Step 4: When the maximum number of iteration is reached or/and the number of required states are generated, the algorithm stops with the best possible solution.

3 Proposed algorithm

In this study, fuzzy c-means and simulated annealing algorithm is developed for solving continuous location and routing problem. The main idea of the proposed model is to divide LRP into two main parts: facility location problem and vehicle routing problem and use efficient algorithms to solve both problems. Since the FCM algorithm is suggested as the efficient algorithm in facility location problem and the simulated annealing algorithm might be efficient in vehicle routing problem because of its capability of avoiding local optima, these algorithms are adopted as the proposed algorithm. In the proposed algorithm, depot locations are determined using the FCM algorithm and by the results of the FCM algorithm, vehicle routing is calculated by a simulated annealing algorithm. Detailed explanations of the proposed algorithm are given in Section 3.

3.1 Fuzzy c-means and simulated annealing algorithm

Facility location determination steps with fuzzy c-means:

Step 1: Divide n number of customers into (y_j) sub-clusters. To achieve this:

Step 1.1: Determine the location of k number of cluster centers.

Step 1.2: Assign customers to the closest cluster center.

Step 2: Using the membership matrix, the final value of the objective function is calculated.

Step 3: Calculate total cost (Oμ) using the membership matrix. Stop the algorithm when the differences between total costs (Oμ) calculated by consecutive membership matrixes M_j, M_j +1 are less than the stopping criteria.

When the algorithm stops, the final version of cluster centers is determined. So, n number of customers are assigned to k number of sub-clusters with a minimum total cost.

Vehicle routing determination steps with simulated annealing algorithm:

Step 1: Location of depots and assignment of customers to depots are determined by fuzzy c-means. The rest of the problem can be considered k number of independent vehicle routing problems.

Fig. 1

Fuzzy c-means and simulated annealing algorithm with uncapacitated depots.

Step 2: In the case of the capacitated depot problem, each depot’s capacity constraints are checked. If capacity constraints are satisfied by all depots, the algorithm continues. Otherwise, customers with minimum membership values are assigned to another cluster until capacity constraints are satisfied.

Step 3: The number of vehicles needed for each depot is calculated using customer demands.

Step 4: Each vehicle routing problem is calculated by a simulated annealing algorithm with minimum total travelled distance.

Step 5: The capacity constraints of each vehicle are checked. If capacity constraints are satisfied by all vehicles, the algorithm continues. Otherwise, the number of vehicles is increased by one and the simulated annealing algorithm starts again.

Step 6: If the difference between consecutive total costs is less than the stopping criteria, the algorithm stops and the minimum total travelled distance is found.

Step 7: When the simulated annealing algorithm stops, the total cost of the problem is calculated.

3.1.1 Fuzzy c-means and simulated annealing algorithm with uncapacitated depots

A flow chart of the proposed algorithm used for the planar multiple facility location and routing problem with uncapacitated depots is given in Fig. 1.

In the proposed algorithm for LRP with uncapacitated depots, the algorithm gets the coordinates of customers and the fuzzy c-means algorithm is applied to determine the locations of depots. Once the determinations of depots locations are maintained, the demands of customers are utilized to calculate the number of trucks needed for each depot. Then, using the results of facility locations, customer locations and customer demands, a simulated annealing algorithm is applied for vehicle routing determination. If each truck’s capacity constraint is satisfied, the cost of the simulated annealing algorithm is calculated and the total cost of the problem is calculated. Otherwise, the simulated annealing algorithm starts again with the increasing number of tucks with one to satisfy the capacity constraints of trucks.

3.1.2 Fuzzy c-means and simulated annealing algorithm with capacitated depots

The flow chart of the proposed algorithm that is used for the planar multiple facility location and routing problem with capacitated depots is given in Fig. 2.

Fig. 2

Fuzzy c-means and simulated annealing algorithm with capacitated depots.

For LRP with capacitated depots, first and fuzzy c-means algorithm is applied to determine the locations of depots using the coordinates of customers. Once depot location determination is maintained, customers are assigned to depots. If depot capacity constraints are violated, customers with the smallest membership values are assigned to another depot and clusters are updated. When depot capacity constraints are satisfied, customers’ demands are utilized to calculate the number of trucks needed for each depot. Using the results of facility locations, customer locations and customer demands, the simulated annealing algorithm is applied to determine vehicle routing. If the capacity constraint of each truck is satisfied, the cost of the simulated annealing algorithm and the total cost of the problem is calculated. If the vehicle constraint is violated in any depot, the simulated annealing algorithm starts again with the increasing number of tucks with one to satisfy the capacity constraints of trucks.

4 Results

In this section, results obtained by the proposed algorithm are given and compared with the benchmarking algorithms applied in the literature. The results of the proposed algorithm are divided into three sections. In the first section, the results of the proposed algorithm for dataset 112112 are given with figures to explain the nature of the problem and algorithm. In the second section, the proposed algorithm results for LRP with uncapacitated depots are shared. Finally, in the third section, results obtained with the proposed algorithm for LRP with capacitated depots are given and compared with benchmarking algorithms.

4.1 Illustrative example

Results obtained from fuzzy c-means and simulated annealing algorithm using dataset 123222 are given in Figs. 3–8.

Fig. 3

Fuzzy c-means algorithm results of dataset 123222.

Fig. 4

Vehicle routing results of simulated annealing algorithm for depot 1 in dataset 123222.

Fig. 5

Vehicle routing results of simulated annealing algorithm for depot 2 in dataset 123222.

Fig. 6

Vehicle routing results of simulated annealing algorithm for depot 3 in dataset 123222.

Fig. 7

Vehicle routing results of simulated annealing algorithm for depot 4 in dataset 123222.

Fig. 8

Vehicle routing results of simulated annealing algorithm for depot 5 in dataset 123222.

Figure 3 represents facility location determination results obtained using a fuzzy c-means algorithm. In addition to that, customers are assigned to facilities as a result of the fuzzy c-means algorithm. Vehicle routing result obtained from the simulated annealing algorithm for depot 1-5 is given in Figs. 4–8, respectively.

Results of the proposed algorithm for illustrative example Dataset 123222 are given in Table 2.

Table 2

Results of the proposed algorithm for an illustrative example

Cluster	Coordinates of cluster centers	Opening cost of depots	Cost of simulated annealing	Capacity of vehicles	Cost of vehicles	Total cost of the dataset
1	44.8491	100	93.6665	150	40	1200.21
	34.6843
2	8.0940	100	87.9746	40
	43.2698
3	75.1914	100	93.0932	40
	13.6147
4	17.9453	100	106.0443	40
	90.7851
5	94.4181	100	99.4331	40
	50.1887

Table 2 includes information about the coordinates of depots that are proposed by the fuzzy c-means algorithm, the cost of simulated annealing for vehicle routing in each depot, the number of vehicles used to serve customers in each depot and the total cost of the problem.

4.2 Results of the proposed algorithm with uncapacitated depots

Data in use for LRP with uncapacitated depots are adopted from benchmarking dataset provided by Tuzun et al. [10]. The results of the proposed algorithm are compared with the best-known results (BKR) in the literature, the hybrid ALNS algorithm which was provided by Akpunar and Akpinar [26] and the genetic algorithm which was developed by Rybickova et al. [3]. Results of the proposed algorithm and benchmarking results are given in Table 3.

Table 3
Results of proposed algorithm and comparisons with benchmarking algorithms for LRP with uncapacitated depots

Dataset Number of Customers Candidate Facilities BKR Hybrid ALNS GA FCM-SA

112112 100 10 1167.16 1167.16 1082 1113.67

112122 100 20 1102.24 1102.24 1004 996.99

112212 100 10 791.66 791.66 705 694.03

112222 100 20 728.30 728.30 703 696.14

113112 100 10 1238.49 1238.49 1127 1137.62

113122 100 20 1245.30 1245.42 1189 1162.48

113212 100 10 902.26 902.26 833 877.45

113222 100 20 1018.29 1018.29 888 882.19

122212 200 10 1449.93 1456.63 1189 1151.07

122222 200 20 1082.46 1082.78 1063 1038.94

123112 200 10 1942.23 1945.70 1733 1713.25

123122 200 20 1910.80 1918.16 1784 1778.65

123212 200 10 1760.99 1760.84 1213 1187.72

123222 200 20 1390.86 1395.48 1240 1200.21

132112 150 10 1443.32 1445.68 1312 1258.09

132122 150 20 1429.30 1431.40 1283 1328.34

132212 150 10 1204.42 1204.42 895 876.31

131212 150 10 1960.02 1969.40 1888 1871.86

132222 150 20 924.68 924.68 902 880.17

133112 150 10 1694.18 1694.18 1431 1429.01

133122 150 20 1392.00 1396.34 1357 1370.77

133212 150 10 1197.95 1198.31 1056 1037.42

133222 150 20 1151.37 1152.30 1096 1069.01

Dataset	Number of Customers	Candidate Facilities	BKR	Hybrid ALNS	GA	FCM-SA
112112	100	10	1167.16	1167.16	1082	1113.67
112122	100	20	1102.24	1102.24	1004	996.99
112212	100	10	791.66	791.66	705	694.03
112222	100	20	728.30	728.30	703	696.14
113112	100	10	1238.49	1238.49	1127	1137.62
113122	100	20	1245.30	1245.42	1189	1162.48
113212	100	10	902.26	902.26	833	877.45
113222	100	20	1018.29	1018.29	888	882.19
122212	200	10	1449.93	1456.63	1189	1151.07
122222	200	20	1082.46	1082.78	1063	1038.94
123112	200	10	1942.23	1945.70	1733	1713.25
123122	200	20	1910.80	1918.16	1784	1778.65
123212	200	10	1760.99	1760.84	1213	1187.72
123222	200	20	1390.86	1395.48	1240	1200.21
132112	150	10	1443.32	1445.68	1312	1258.09
132122	150	20	1429.30	1431.40	1283	1328.34
132212	150	10	1204.42	1204.42	895	876.31
131212	150	10	1960.02	1969.40	1888	1871.86
132222	150	20	924.68	924.68	902	880.17
133112	150	10	1694.18	1694.18	1431	1429.01
133122	150	20	1392.00	1396.34	1357	1370.77
133212	150	10	1197.95	1198.31	1056	1037.42
133222	150	20	1151.37	1152.30	1096	1069.01

For the uncapacitated LRP, FCM-SA is applied to 23 datasets. Out of 23 datasets, in 19 datasets, FCM-SA shows superiority in genetic algorithm, hybrid ALNS algorithm and BKR (best-known results). Only in four datasets which are 112112, 113212, 132122 and 133122, genetic algorithm gives better results than FCM-SA. Note that best-known results and hybrid ALNS algorithm results are maintained for discrete LRP and the genetic algorithm solutions are for the continuous LRP.

4.3 Results of the proposed algorithm with capacitated depots

The results of fuzzy c-means and simulated annealing algorithm for the LRP problem with capacitated depots are given in Table 4. The proposed model is applied to the Barreto benchmark dataset. The results of the proposed algorithm are compared with the best-known results (BKR) in the literature, the heuristic that was developed by Barreto et al. [34], the hybrid ALSN algorithm which was provided by Akpunar and Akpinar [26], Simulated Annealing (SA) and Artificial Algae Algorithm (AAA) that was proposed by Ferreira and Queiroz [19].

Table 4
Results of proposed algorithm and comparisons with benchmarking algorithms for LRP with capacitated depots

Dataset Number of customers Candidate facilities BKR Barreto Heuristic Hybrid ALNS SA+AAA Avg SA+AAA Best FCM-SA

Gaskell67— 21X5 21 5 424.9+ 435.9 424.9+ 424.9+ 424.9+ 427.5

Gaskell67— 22X5 22 5 585.1+ 591.5 585.1+ 585.1+ 585.1+ 565.7

Gaskell67— 29X5 29 5 512.1+ 515.1 512.1+ 512.1+ 512.1+ 471.9

Gaskell67— 32X5-1 32 5 562.2 571.7 562.2 562.2 562.2 525.5

Gaskell67— 32X5-2 32 5 504.3+ 511.4 504.3+ 504.3+ 504.3+ 500.5

Gaskell67— 36X5 36 5 460.4+ 470.7 460.4+ 460.4+ 460.4+ 456.2

Christofides69-50X5 50 5 565,6+ 582,7 565,6+ 565,6+ 565,6+ 581.8

Christofides69-75x10 75 10 844.4 886.3 848.9 854.8 848.85 842.5

Christofides69-100x10 100 10 833.4 889.4 833.4 844.9 833.4 866.2

MIN27 27 5 3062.0 3062.0 3062.0 3062.0 3062.0 3039.6

MIN134 134 8 5709.0 6238.0 5709.0 5842.1 5726.7 5788.4

Dataset	Number of customers	Candidate facilities	BKR	Barreto Heuristic	Hybrid ALNS	SA+AAA Avg	SA+AAA Best	FCM-SA
Gaskell67— 21X5	21	5	424.9+	435.9	424.9+	424.9+	424.9+	427.5
Gaskell67— 22X5	22	5	585.1+	591.5	585.1+	585.1+	585.1+	565.7
Gaskell67— 29X5	29	5	512.1+	515.1	512.1+	512.1+	512.1+	471.9
Gaskell67— 32X5-1	32	5	562.2	571.7	562.2	562.2	562.2	525.5
Gaskell67— 32X5-2	32	5	504.3+	511.4	504.3+	504.3+	504.3+	500.5
Gaskell67— 36X5	36	5	460.4+	470.7	460.4+	460.4+	460.4+	456.2
Christofides69-50X5	50	5	565,6+	582,7	565,6+	565,6+	565,6+	581.8
Christofides69-75x10	75	10	844.4	886.3	848.9	854.8	848.85	842.5
Christofides69-100x10	100	10	833.4	889.4	833.4	844.9	833.4	866.2
MIN27	27	5	3062.0	3062.0	3062.0	3062.0	3062.0	3039.6
MIN134	134	8	5709.0	6238.0	5709.0	5842.1	5726.7	5788.4

Since the data in use are applied on only discrete LRP in the literature, to have an unbiased comparison, only the datasets which have fixed opening costs on depots are adopted in the proposed algorithm and compared with successful results in the literature. Otherwise, the continuous solution procedure can create biased comparisons because of variable facility opening costs in candidate depots. Eleven datasets widely used in the literature are applied to the proposed algorithm for capacitated LRP. Out of eleven datasets, FCM-SA gives better results in seven datasets. In four datasets which are Gaskell67— 21X5, Christofides69-50X5, Christofides69-100x10 and MIN134 best-known results in the literature provide better results than the proposed algorithm. In addition, the proposed algorithm performs superiority on the Barretto heuristic in all datasets. As a result, FCM-SA gives successful results compared with the BKR (best-known results), Baretto Heuristic which was provided by Barreto et al. [34], hybrid ALSN algorithm which was provided by Akpunar and Akpinar [26], Simulated Annealing (SA) and Artificial Algae Algorithm (AAA) that was proposed by Ferreira and Queiroz [19]. Note that the values in Table 4, including (+), imply that they are optimal.

5 Conclusion

In this study, a new heuristic algorithm that combines fuzzy c-means and a simulated annealing algorithm is developed for continuous LRP. The proposed algorithm is applied to datasets with multiple depots. In these datasets, solutions are presented for both capacitated and uncapacitated depots. All datasets in use contain capacity constraints on vehicles. The results are compared with successful researches in the literature about the problem. After solutions are gathered, it is noted that the proposed algorithm performs well in continuous LRP with both capacitated and uncapacitated depots according to the total cost.

In the literature, most of the researches have been made about this problem focus on discrete location problem. However, the continuous location problem is also one of the most studied topics among researchers. There are very limited studies about the continuous LRP in the literature as opposed to the location problem. Since LRP has essential impacts on the success of the companies and not necessarily in all real problems contain discrete LRP. We strongly believe that the proposed algorithm is one of the successful attempts to fill this gap.

In future studies, instead of a simulated annealing algorithm, different metaheuristic algorithms can be utilized for the vehicle routing problem and performances can be compared with the proposed algorithm. Furthermore, facility location and vehicle routing can be solved simultaneously. In addition to that, to increase the performance of the facility location solution, metaheuristic algorithms might be combined with a fuzzy c-means algorithm such as Nelder-Mead and Particle Swarm Optimization algorithms. Moreover, the proposed algorithm can be used in location or routing problem (LORP), a special version of the LRP where customers in a specific range visit facilities without vehicles and the rest visit the facility by vehicles. Finally, since governments and companies nowadays have started to use electric vehicles, the proposed algorithm might be applied for the case where the locations of electric charging stations need to be determined considering the vehicle routing of the vehicles.

References

Diabat

, Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain, European Journal of Operational Research 238 (2014), 114–121.

Nia

A.R.

, Far

M.H.

and Niaki

S.T.A.

, A hybrid genetic andimperialist competitive algorithm for green vendor managed inventoryof multi-item multi constraint EOQ model under shortage, , Applied Soft Computing 30 (2015), 353–364.

Rybickova

, Mocková

and Teichmann

, Genetic algorithm forthe continuous location-routing problem, Neural Network World 29 (2019), 173–187.

Contardo

, Cordeau

J.F.

, Gendron

A branch-andcut-and-price algorithm for the capacitated location-routing problem, INFORMS Journal on Computing (2013a).

Contardo

, Cordeau

J.F.

, Gendron

AGRASP+ILPbased metaheuristic for the capacitated location-routing problem, Journal of Heuristics (2013b).

Prodhon

and Prins

, A survey of recent research on location-routing problems, , European Journal of Operational Research 238 (2014), 1–17.

Prins

, Prodhon

and Wolfler

, Calvo, Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking, European Journal of Operational Research 4(3) (2006), 221–238.

Prins

, Prodhon

, Ruiz

, Soriano

and WolflerCalvo

, Solving the capacitated location-routing problem by a cooperative lagrangean relaxation granular tabu search heuristic, Transportation Science 41(4) (2007), 470–483.

Watson-Gandy

and Dohrn

, Depot location with van salesmen — A practical approach, , Omega 1 (1973), 321–329.

10.

Tuzun

and Burke

, A two-phase tabu search approach to the location routing problem, European Journal of Operational Research 116(1) (1999), 87–99.

11.

Guimarans

, Dominguez

, Panadero

and Juan

A.A.

, A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times, , Simul. Model. Pract. Theory 89 (2018), 1–14.

12.

Baytürk

, Esnaf

Ş.

and Küçükdeniz

, Two-phase fuzzy c-means and genetic algorithm for food distribution, Digital Conversion on the Way to Industry 4.0 (2021), 453–460.

13.

Laporte

and Nobert

, An exact algorithm for minimizing routingand operating cost in depot location, , European Journal ofOperational Research 6 (1981), 224–226.

14.

Laporte

, Nobert

and Arpin

, An exact algorithm for solving a capacitated location-routing problem, , Annals of Operations Research 6 (1986), 293–310.

15.

Villegas

J.G.

, Prins

, Prodhon

, Medaglia

L.A.

and Velasco

, GRASP/VND and multi start evolutionary local search for the single truck and trailer routing roblem with satellite depots, –, Engineering Applications of Artificial Intelligence 23 (2010), 780–794.

16.

Belenguer

J.M.

, Benavent

, Prins

, Prodhon

and Wolfler-Calvo

, A branch-and-cut method for the capacitated location-routing problem, Computers and Operations Research 38(6) (2011), 931–941.

17.

Escobar

J.W.

, Linfati

and Toth

, A two-phase hybrid heuristicalgorithm for the capacitated location-routing problem, Computers & Operations Research 40(1) (2014), 70–79.

18.

Escobar

J.W.

, Linfati

, Baldoquin

M.G.

and Toth

, A granular variable tabu neighborhood search for the capacitated location-routing problem, , Transportation Research Part B: Methodological 67 (2014), 344–356.

19.

Ferreira

K.M.

and de Queiroz

T.A.

, A simulated annealing based heuristic for a location-routing problem with two-dimensional loading constraints, , Applied Soft Computing 118 (2022).

20.

Zalik

K.R.

Fuzzy c-means clustering and facility location problems, Proceedings of the 10th IASTED Conference Artificial Intelligence and Soft Computing (2006).

21.

Schwardt

and Dethloff

, Solving a continuous location-routingproblem by use of a self-organizing map, International, Journalof Physical Distribution & Logistics Management 35 (2005), 390–408.

22.

Schwardt

and Fischer

, Combined location-routing problems— a neural network approach, Annals of Operations Research 167(1) (2009), 253–269.

23.

Schneider

and Löffler

, Large composite neighborhoods for the capacitated location-routing problem, Transportation Science 53(1) (2019), 301–318.

24.

Ayoub

, Martins

, Wang

, Seki

and Noka

, Two levels decision system for efficient planning and implementation of bioenergy production, , Energy Conversion and Management 48 (2007), 709–723.

25.

Guemri

O.B.

and Beldjilali

, Bekrar and G. Belalem, Two-stage heuristic algorithm for the large-scale capacitated location routing problem, International Journal of Mathematical Modelling and Numerical Optimisation 7(97) (2016).

26.

Akpunar

Ö.Ş

and Akpinar

Ş.

, A hybrid adaptive largeneighbourhood search algorithm for the capacitated location routingproblem, , Expert Systems with Applications 168 (2021).

27.

Baldacci

, Mingozzi

and Wolfler-Calvo

, An exact method for the capacitated location-routing problem, Operations Research 59(5) (2011), 1284–1296.

28.

Ghodsi

, Amiri

A.S.

A variable neighborhood search algorithm for continuous location routing problem with pickup and delivery, Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation (2010), 199–203.

29.

Kirkpatrick

, Gelatt

C.D.

and Vecchi

M.P.

, Optimization by simulated annealing, , Science 220 (1983), 671–680.

30.

Manzour-al-Ajdad

S.M.H.

, Torabi

S.A.

and Salhi

, A hierarchicalalgorithm for the planar single-facility location routing problem, Computers & Operations Research 39(2) (2012).

31.

Nucamendi-Guillén

, Martínez-Salazar

, Khodaparastiand

and Bruni

M.E.

, New formulations and solution approaches for thelatency location routing problem, , Computers & OperationsResearch 143 (2022).

32.

Ponboon

, Qureshi

A.G.

and Taniguchi

, Branch-and-price algorithm for the location-routing problem with time windows, , Transp. Res. Part E Logist. Transp. Rev 86 (2016), 1–19.

33.

Salhi

and Nagy

, Local improvement in planar facility location using vehicle routing, , Annals of Operations Research 167 (2009), 287–296.

34.

Barreto

, Ferreira

, Paixao

and Santos

B.S.

, Using clustering analysis in a capacitated location-routing problem, European Journal of Operational Research 179(3) (2007), 968–977.

35.

Esnaf

Ş.

and Küçükdeniz

, A fuzzy clustering-basedhybrid method for a multi-facility location problem, Journal ofIntelligent Manufacturing 20 (2009), 259–265.

36.

Esnaf

Ş.

and Küçükdeniz

, Solving uncapacitatedplanar multi-facility location problems by a revised weighted fuzzyc-means clustering algorithm, Journal of Multiple-valued Logicand Soft Computing 21 (2013), 147–164.

37.

Carnes

, Shmoys

D.B.

Primal-dual schema and lagrangian relaxation for the k-location-routing problem, Lecture Notes in Computer Science (2011), 6845.

38.

Harks

, Koenig

and Matuschke

, Approximation algorithms for capacitated location routing, , Transportation Science 47 (2013).

39.

Xie

, Ouyang

and Wong

S.C.

, Reliable location-routing design under probabilistic facility disruptions, , Transportation Science 50(3) (2015), 1128–1138.

40.

Cerny

, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, Journal of Optimization Theory and Applications 45(1) (1985), 41–51.

41.

Chepoi

and Dimitrescu

, Fuzzy clustering with structural constraints, , {Fuzzy Sets and Systems 105 (1999), 91–97.

42.

Akca

, Berger

R.T.

, Ralphs

T.K.

A branch-and- price algorithm for combined location and routing problems under capacity restrictions, Operations Research and Cyber-Infrastructure (2009), 309–330.