Fuzzy multi-objective location and routing problem

Abstract

The location-routing problem is a research area that simultaneously solves location-allocation and vehicle routing issues. It is critical to delivering emergency goods to customers with high reliability. In this paper, reliability in location and routing problems was considered as the probability of failure in depots, vehicles, and routs. The problem has two objectives, minimizing the cost and maximizing the reliability, the latter expressed by minimizing the expected cost of failure. First, a mathematical model of the problem was presented and due to its NP-hard nature, it was solved by a meta-heuristic approach using a NSGA-II algorithm and a discrete multi-objective firefly algorithm. The efficiency of these algorithms was studied through a complete set of examples and it was found that the multi-objective discrete firefly algorithm has a better Diversification Metric (DM) index; the Mean Ideal Distance (MID) and Spacing Metric (SM) indexes are only suitable for small to medium problems, losing their effectiveness for big problems.

Keywords

Fuzzy optimization location and routing firefly algorithm NSGAII algorithm reliability failure

1 Introduction

Facility location-allocation problems arise in many practical settings from emergency services to telecommunication networks [17]. Supply chain logistics system is one of the key drivers in designing the supply chain whose proper design results in efficiency and profitability [26]. In recent years, designing an integrated logistics system has been the primary goal of many companies, because logistics takes a large part of the costs, while proper supply chain designs can reduce such costs.

The distribution network which is at the end of the supply chain is also very important, as it delivers a number of goods to customers. Designing such a network conduces to combinatorial optimization in which depot locations and vehicle routes are simultaneously determined. LRPs (location and routing problem) are a set of problems pertaining to location, routing and location planning, and it considers routing aspects [39]. In LRP, decisions are made on two different levels, strategic and tactical. The former decisions are usually made once, and cannot be changed later and require a huge investment. Routing decisions are tactical decisions that are changed when needed [15].

In LRP, different parts of the distribution network always run a risk of failure, whereupon the reliability is reduced. If the possible failures in LRP are considered, reliability will be considered in that network as well. The concept of reliability is derived from network reliability theory which tackles computing, estimating and maximizing the possibility of a network connection (electricity and telecommunication networks are usually presented as graphs); any problem in such a network results in disruption, congestion, or blockage [50]. Failure factors are divided into two groups, human such as war and terroristic attacks and natural such as flood, earthquake, and so forth [18]. In real life, there exist certain examples of system failure, such as The September 11 attacks after which many economical and official activities were stopped, or Taiwan earthquake in 1999 which put the semiconductor devices under a severe shock.

So far, LRP has been analyzed from different aspects. LRP has different parts which have been always in danger. Failure in every part causes a great loss in the chain. For example, in a situation where people’s lives are to be saved during a crisis, any kind of failure can put many lives in danger. Nowadays, reliability has become a public concern and analyzed in different parts of a supply chain. This study considered reliability in the location-routing system, modeling and its analysis.

To date, many studies have been done on LRP: Min et al. (1998) and Nagi and Salhi (2007) presented a comprehensive classification of LRP according to solution methods and structure of the problem [34, 37]. W. Xuefeng et al. (2018) presented a novel multi-objective location- routing problem with simultaneous pickup and delivery. The problem seeks to minimize distribution operation cost and maximize service level [54]. The latest classification is presented by Prodhon and Prins (2014). Analyzing these classifications, a general view of the literature of LRP can be extracted. Some of these classifications are models and restrictions, objective functions, parameters, applications and solving methods [43].

Considering the different restrictions, different mathematical models are proposed for location-routing. In order to reduce all expenses, Geoffrion and Graves (1974) presented a two-phase model for a multiple-production system in which goods are primarily sent to depots from factories, and then from the depots to the customers [14]. Perl and Daskin (1985) also presented a model of LRP for warehouses and as there was no restriction of shipping in their model, fixed expenses were ignored [39]. Wu et al. (2002) suggested yet another model of LRP considering fixed shipping expenses [56]. Special circumscription, such as a location-routing problem with simultaneous pickup and delivery [44, 58] or removing the restriction of vehicle capacity by considering the auxiliary vehicle assignment [3] have also been proposed.

In terms of literature and according to the objective function, the LRPs are divided into mono-objective and multi-objective. In mono-objective problems, the objective function is to minimize expenses, and in multi-objective problems, the objective function is firstly to minimize expenses and secondly to do the following: Minimizing environmental impacts [16], minimizing the distance of extra trips [15], maximizing the covered demands [45], minimizing the risk for those people who are close to waste disposal [46] and maximizing the service level.

An exact predication of circumstances is impossible and unreal, hence the term “unreliability” considered in such parameters. The parameters of LRPs are either fixed and known or stochastic. Unreliability has various types, such as unreliability in supply and demand resulting from customers’ efficiency and behavior, and unreliability in production, distribution, collection, delivery times and production expenses [52]. Supply and parameters and traveling time can possible definite distribution or phase-based [1 , 60].

In terms of application, LRP problem has been used in real life conditions, such as emergency organization aids [45], industrial waste disposal [46] food distribution [8, 55], and newspaper distribution [23].

According to Prodhon and Prins’s (2014) classification, LRP solving methods are divided into 4 groups: Exact, heuristic, meta-heuristic and mathematical-heuristic [43].

Exact methods are applicable in small problems, and so far the methods being used are as follows: Cutting planes [28], branch and cut [4], branch-cut and price [6], and branch and bound [28]. According to Nagy and Salhi (2007), heuristic methods are cluster-based ordinal, repetitive and hierarchical methods [37].

Meta-heuristic methods which are usable in big problems may not result in optimized output, but they can come close. So far, many meta-heuristic methods have been applied such as stimulated annealing [13], tabu search [1], iterative local search [11], genetic-iterative local search [12], genetic [32], variable neighborhood search [24], greedy randomized adaptive search procedure [41], variable neighborhood descent [22], memetic algorithm [40] and multiple ant colony optimizations [51].

Integrative mathematical-heuristic methods have been also applied to problem-solving. The first method of this type was presented by Prins et al. (2007), which was a combination of Lagrangian relaxation granular and Tabu search [42]. Contrado et al. (2014) presented a method which was a combination of greedy randomized adaptive search procedure and integer linear programming (GRASP+ILP) [7].

Reliability and failure have been analyzed from different aspects. In this part, the focus is on the literature and its analysis of reliability in supply chain and LRPTo the best of our knowledge, the first study in reliability and locating was a doctoral dissertation by Snyder (2003) and also Snyder and Daskin (2005) who applied forwarded reliability models to mapping problems and demonstrated that a practical example of reliability and mapping entails high costs [49]. They presented models for PMP and UFLP problem in which merely the probability of failure in facilities was considered. Facilities are divided into two groups: Fallible and non-fallible and the customer has a primary and backup assignment. In their model, they only considered failure in depots, where the objectives were to minimize the costs of the failure of other costs.

Lim et al. (2010) studied a reliable supply chain network in the presence of random facility disruptions with the option of hardening selected facilities [30]. He considers two types of facilities, inexpensive and slightly reliable and expensive and highly reliable. Berman et al. (2007) dealt with locating p-median problem considering failure in a network whose optimum point depends on the probable failure of facility [5]. The more the probability of failure, the more co-located and centered the facilities will be. Hong et al. (2015) present multi-objective programming in order to design an emergency logistics network with reliability in which facilities can be destroyed or damaged [21].

Through the use of fuzzy parameters, Miao et al. (2009) studied the reliability of problems related to auxiliary agencies and presented a method for evaluating supply chain reliability [33]. Vahdani et al. (2013) also stated the reliability of closed-loop supply chain under conditions of uncertainty in the steel industry, considering the probability of failure in collection centers [52]. Kamalahmadi et al. (2016) considered supply risk and environmental risk in the demand allocation of supply chain [27].

Sanso et al. (1991) studied reliability in routing problem in order to minimize the costs; they calculated the lower and upper bound of reliability, considered failure in paths and nodes, and solved the model with branch and bound method [47]. Li et al. (2009) discussed vehicle breakdown in vehicle routing considering time windows so as to minimize the sum of operational costs [29]. In such a model, if a vehicle breaks down another (provided it is accessible in the distribution center), will be sent for further service. Using the Lagrange relaxation algorithm to minimize the delivery time and costs, Wang et al. (2010) developed a model for vehicle routing considering vehicle breakdown. Via a metaheuristic method, Mu et al. (2011) appraised vehicle failure during operation with the objective of minimizing costs, meaning that in case of failure, customers are reassigned [36, 53].

Helender et al. (1997) studied LRP in industrial hazardous materials, aiming to minimize the expected number of accidents through considering reliability as a probability of failure for traveling without failure [20].

Nowadays, the world is full of unreliability in which changing may occur at any moment. In this paper, reliability in LRP has been considered in order to design a network that can continue its best performance in case of disruption or failure in each part of the system. This problem is important because these kinds of failures are always costly for the system, especially when it comes to human lives. For example, when earthquake or war happens, delivering first aid and food for people with high reliability is so vital. So in this paper, we try to model and solve the problem considering reliability in LRP problem.

Based on the literature review and the hiatuses existing in location-routing reliability discussions, the present paper aimed at minimizing the cost and maximizing reliability through minimizing the expected cost of failure. Given the NP-hard nature of the research problem, meta-heuristic algorithms were made use of. Primarily, the firefly discrete multi-objective algorithm is presented to provide the Pareto solution; the research problems were solved with Firefly and Non-dominated Sorting Genetic Algorithm II (NSGA-II), considered as the main algorithms in several researches [38, 48]; these two algorithms were further compared as regards problem-solving. As the accurate estimation of costs is impossible in the real world, triangular fuzzy numbers were employed; in order to compare the fuzzy numbers, the radius gyration method was utilized [10].

The rest of the paper is organized as follows: The second section deals with the problem statement and a precise definition of the mathematical model with an accurate description of variables, parameters, and constraints of the problem. In Section 3, both Firefly and NSGA-II algorithms are used and making a movement and putting distance between the fireflies is also presented in this section. In section 4, sample problems are delineated, and the computational results of Firefly and NSGA-II algorithms are compared based on certain indicators. The final part is related to the conclusion and suggestions for future research.

2 Problem statement and modeling

In this section, the problem statement and objectives are precisely expressed, variables and parameters of the problem are presented, mathematical modeling is performed, and the constraints and objective functions are investigated.

2.1 The problem statement

In a supply chain, depots, vehicles and communication routes always run a risk of failure and removal from customer service. In this research, three types of failure are considered: Failure of depots or facilities, vehicles and communication paths; on the basis of each type, additional costs, as the expected cost of failure, were imposed on the system.

So as to calculate the expected failure cost, the cost of transportation was considered. The existing depots were divided into two groups: Non-fallible and fallible, with the former located in favorable weather areas that are either emergency centers or served by unions with which the firm has a particularly strong relationship, or have a negligible probability of failure. Each fallible depot may be damaged by q probability of failure which is assumed to be identical for all depots because it is a necessity for computing the probability that a customer is served by its level-r facility without knowing its assignments in lower-level, only that there are r of them and that they are fallible. The failures in depots are independent of each other, and the depots may meet several failures simultaneously. In certain cases, q may be estimated based on the historical data, while in others, q must be estimated subjectively. In the event of a failure in a depot, customers who receive service from the depot, are served by the backup depot.

If the demand of customer i is satisfied by a non-fallible depot u, the system is incurred by a cost proportional to the traveled distance (it can be assumed as a lost opportunity cost if a customer receives service from a non-fallible depot). The fixed cost of establishing non-fallible depots is zero; however, in order to ensure that these canters are established, z_u = 1 is also considered. If I depots are opened, each customer has an I assignment level, the first level is zero and it is the main assignment for the customer while other levels are backup assignments.

If a client is assigned to a non-fallible depot in a level, there is no need for backup assignment in other levels. When a client receives service from a depot in a level, it means that the failure probability in the previous level was q^r, and the probability of service reception in this level is (1-q) which is equal to 1 if allocated to a non-fallible depot.

In the event of a failure in the vehicle, δ cost is added as an additional cost which is equal to the fees paid for a vehicle rental for service continuation. In the event of road failure, the vehicle must choose another way to keep track. Each path has a probability of failure and whenever it is more likely to fail, the failure cost is increased; in the case where the probability is 1, the path is impassable. Therefore, to model the problem, the paths with the highest probability of failure must not be selected since as they entail much more exponential costs. For instance, if the probability failure of a path is 1, it imposes a huge amount of cost and becomes unsuitable for service. To tackle such a problem, a coefficient is selected to increase the costs, so that as the failure probability increases, the coefficient increases exponentially.

2.2 Mathematical Modelling

Problem parameters may include:

J: a set of customers (j)

I: a set of candidate depots

K: a set of vehicles (k)

d_j: Customer demand in location j

O_i: The fixed cost of opening depot

${\tilde{c}}_{ij}$ : Fuzzy transportation costs between points i and j (i, j ∈ I ∪ J)

N: Numbers of customers

d_ij: Distance between nodes i and j

v_i: Capacity of depot i

Q_k: Vehicle Capacity (path) k

F_k: Fixed costs of using vehicle k

q: Failure probability of depot

p_ij: Failure probability of the path between nodes i and j

pr_k: Failure probability of vehicle k

Variables may include: $\begin{matrix} x_{ijkr} = \\ {\begin{matrix} 1 if in allocation level r, vehicle k moves from node i to j \\ 0 other wise \end{matrix} \end{matrix}$ $\begin{matrix} z_{i} = \\ {\begin{matrix} 1 if in candidate location i, a depot is established \\ 0 otherwise \end{matrix} \end{matrix}$ $\begin{matrix} y_{ijr} = \\ {\begin{matrix} 1 if cilent j is allocated to depot i in level r \\ 0 other wise \end{matrix} \end{matrix}$

u_jkr: Ancillary variable to remove sub-tours

w₁: Total costs is to preclude any kind of failure

w₂₁: The expected cost of failure

w₂₂: The cost of vehicle failure

w₂₃: The cost of failure in the paths

w₂: The total cost of failure

Model:

$\begin{matrix} Min w_{1} = \sum_{i \in I} z_{i} o_{i} + \sum_{k \in K} F_{k} \sum_{i \in I} \sum_{j \in J} x_{ijk 0} \\ + \sum_{i \in v} \sum_{j \in v} \sum_{k \in K} x_{ijk 0} \tilde{c_{ij}} \end{matrix}$ (1)

$\begin{matrix} w_{21} = \sum_{r = 0} \sum_{i \in ((I \cap F) \cup J),} \sum_{j \in ((I \cap F) \cup J)} \sum_{k \in K} q^{r} (1 - q) x_{ijkr} \tilde{c_{ij}} \\ + \sum_{r = 0} \sum_{i \in ((I \cap NF) \cup J),} \sum_{j \in ((I \cap NF) \cup J)} \sum_{k \in K} q^{r} x_{ijkr} \tilde{c_{ij}} \end{matrix}$ (2) $w_{22} = \sum_{k \in K} \sum_{i \in V \cap F} \sum_{j \in V \cap F} δ p_{rk} x_{ijk 0} \tilde{c_{ij}}$ (3) $w_{23} = \sum_{i \in V} \sum_{j \in V \cap F} \sum_{k \in K} - \frac{p_{ij}}{ln (p_{ij})} x_{ijk 0} \tilde{c_{ij}}$ (4) $Min w_{2} = w_{21} + w_{22} + w_{23}$ (5) $\begin{matrix} s . t . \\ \sum_{i \in V} \sum_{k \in K} x_{ijkr} = 1 \forall j \in J, r = 0, \dots, | I | - 1 \end{matrix}$ (6) $\sum_{i \in V} \sum_{j \in J} d_{j} x_{ijkr} \leq Q_{k} \forall k \in K, r = 0, \dots, | I | - 1$ (7)

$\begin{matrix} U_{lkr} - U_{jkr} + {Nx}_{ljkr} \\ \leq N - 1 \forall l, j \in J, k \in K, r = 0, \dots, | I | - 1 \end{matrix}$ (8)

$\begin{matrix} \sum_{j \in V} x_{ijkr} - \sum_{j \in V} x_{jikr} \\ = 0 \forall i \in V, \forall k \in K, r = 0, \dots, | I | - 1 \end{matrix}$ (9) $\sum_{i \in I} \sum_{jeJ} x_{ijkr} \leq 1 \forall k \in K, r = 0, \dots, | I | - 1$ (10) $\sum_{r = 0}^{| I | - 1} \sum_{j \in J} d_{j} y_{ijr} \leq p_{i} z_{i} \forall i \in I$ (11)

$\begin{matrix} \sum_{j \in J} y_{ijr} + \sum_{j \in NF} \sum_{s = 0}^{r - 1} y_{ijs} = 1 \\ \forall j \in J, r = 0, \dots, | I | - 1 \end{matrix}$ (12)

$\begin{matrix} \sum_{m \in V} x_{imkr} + \sum_{m \in V} x_{mjkr} \leq 1 \\ + y_{ijr} \forall i \in I, \forall j \in J, \forall k \in K, \forall r \in {0, \dots, | I | - 1} \end{matrix}$ (13) $z_{NF} = 1$ (14) $z_{i} \in {0, 1} \forall i \in I$ (15) $y_{ijr} \in {0, 1} \forall i \in I, j \in J, r = 0, . . | I | - 1$ (16) $x_{ijkr} \in {0, 1} \forall i \in I, j \in J, k \in K, r = 0, . . | I | - 1$ (17) $u_{jkr} \geq 0 \forall j \in J, k \in K, r = 0, \dots ., | I | - 1$ (18)

The first objective function for total costs is to preclude any kind of failure; the first part of this function is to calculate the fixed costs of opening the depots. The second part pertains to the fixed costs of the vehicles, and part III further calculates the shipping costs. The second objective function is to minimize the expected cost of failure, itself comprised of three parts: In the first part, equation 2 calculates the expected cost of failure, while depots facing failure. Each customer has a primary and a backup allocation. In the first part of the equation, only fallible depots and in the second part, non-fallible depots are intended.

The second part, Equation 3 shows the cost of vehicle failure calculated only level zero in which no failure has occurred. Equation 4 demonstrates the cost of failure in the paths, which is also calculated only at level zero. The second objective function, Equation 5 is the total cost of failure and Equation 6 ensures that every customer at every assignment level is placed on a single path and Equation 7 is the vehicle’s capacity which the total demand of a path should not exceed. Equation 8 is to remove a set of sub-tours that only pass a client’s set. Equation 9 ensures that each vehicle enters and exit the same node. Equation 10 means that in each path, there has to be only one depot. Equation 11 ensures that the demand assigned to each depot does not exceed the total capacity of the depot.

Equation 12 means that every customer at every level must be assigned to a depot unless the customer has already been assigned to a non-fallible depot. Equation 13 states that if k∈K leaves both customer node j∈J and depot node i∈I, then customer j∈J should be assigned to the depot i∈I in level r, a constraint which connects routing variable of vehicles to the allocation variables. Equation 14 ensures that the non-fallible depot is established, and Equation 15 to 18 are the decision variables.

3 Problem-solving

Given a large number of variables and problem constraints, only exact methods and software like GAMS are able to solve this problem with small size, and by increasing the size of the problem, such methods are no more effective. In order to show the validity of the problem model, different examples with small-sized are given which are solved by GAMS software and Epsilon method. The optimum value of each objective function has been shown in Table 1.

Table 1
GAMS

Number of customer # number of depots W₁ W₂

10#3 7295.71 226.158

15#4 7300.02 235.01

15#5 7305.08 237.153

20#6 7323.01 272.31

Number of customer # number of depots	W₁	W₂
10#3	7295.71	226.158
15#4	7300.02	235.01
15#5	7305.08	237.153
20#6	7323.01	272.31

3.5 Crossover and mutation

To solve the problem, the firefly algorithm, using the concept of non- dominated-sorting, and NSGA-II algorithm are considered.

3.1 Firefly algorithm

Firefly algorithm (FA) is one of the most important tools in swarm intelligence which has a wide range of applications in the context of optimization. This algorithm was proposed and applied by Yang (2010) for the first time, and it inspired by the behavior of the Firefly [57]. Firefly appears in hot weather and night. These insects emit energy using chemical mechanisms in the form of light patterns, known as flash. Each species of fireflies has their own flash pattern and they respond only to patterns similar to theirs. In the process of absorption, a firefly is absorbed by another with a more powerful flash. In this algorithm, flashlight intensity is proportional to the value of the objective function which has to be optimized.

A series of artificial fireflies are considered so that each firefly has a suitability measure which is equal to its attractiveness measure. A firefly with more attractiveness attracts that with less attractiveness, meaning that weaker solutions move towards stronger solutions. In a problem, maximizing the light intensity can be proportional to the objective function which has to be optimized. Because the problem is multi-objective, a two-objective and discrete firefly algorithm were employed in the present study. In order to find Pareto solution, non-dominated sorting method and congestion distance were used. Since cost parameters are assumed as fuzzy numbers, they were compared and sorted based on the gyration radius method. This Non-dominated Sorting Discrete Firefly Algorithm (NSDFA) is shown in Fig. 1.

Fig. 1

NSDFA algorithm.

3.2 NSGAII algorithm

The NSGA-II algorithm is a generalized form of genetic algorithm, with the difference that it is used for multi-objective optimization problems. It was proposed by Deb et al. (2002) [9]. In a genetic algorithm, multi-objective problems cannot be sorted with ordinary sorting operations. Hence, in this algorithm, non-dominated sorting method and crowding distance are used in order to compare and rank final answers. NSGA-II offers a range of solutions, and it tries to find a good trade-off between some conflicting objectives. NSGA-II procedure has three features. It uses an elitist principle, emphasizes on non-dominated solutions and uses an explicit diversity preserving mechanism. In 2013 NSGA-III is provided as an evolutionary algorithm for solving many-objective (four and more) optimization problems. As the proposed problem in this paper has two objectives, NSGA-II has chosen for solving the problem.

The steps of the algorithm are:

Initialize Population

Selecting parents and performing crossover and creating a population of children

Selecting parents, making mutations and creating a mutated population

Selecting new members of the population from the main population, children and mutated people

If the termination conditions are not fulfilled, go to step 2.

Finish

Flowchart of the algorithm is shown in Fig. 2.

Fig. 2

NSGAII algorithm.

3.3 How to display answers

One of the major factors in each algorithm is expressing the answers so that the algorithm can be implemented. As shown in Fig. 3, in LRP, each firefly is presented as a matrix, a method also used to express each answer in NSGA-II algorithm. Solution presentation method is considered as a matrix in which the numbers of the last row indicate the number of customers. Other rows indicate the assignment levels that are from zero level to r level.

Fig. 3

Display of answer.

For example, Fig. 4 demonstrates a possible answer for a problem with two fallible depots and a non-fallible one. The first row shows the assignment at level two, and the next rows show the assignment at levels one and zero, respectively.

Fig. 4

Example for 6 customers and 3 depot.

Numbers of all rows are connected with the last row which means that if the first row and the last row are considered with the numbers of their columns, simultaneously, each customer in a level is allocated to a certain depot. For example, the following matrix at level zero of clients 6, 5, 1 and 3 are allocated to depot 1, and clients 4 and 2 to depot 2, Also, the service order of customers is determined by considering the order of depots in the last row. For instance, the order for depot 1 is equal to 1, 6, and 5 in case of no failure in depots. If a customer in a level is allocated to a non-fallible depot, there is no need for backup assignment in other levels. Zero means that in the related level, the allocation is not performed.

3.4 The light intensity, distance, and movement

Since the research question has two objective functions, Firefly has two different parameters to indicate the intensity of its light. The light intensity is inversely proportional to the inverse amount of each objective function for each firefly. As the light intensity in the problem has two values, non-dominant sorting and congestion distance method were utilized to compare the ranking results. $I_{1} = \frac{1}{{object}_{1}}, I_{2} = \frac{1}{{object}_{2}}$ (19)

One of the most important parameters in the firefly algorithm is the distance between two fireflies, obtained by Euclidean distance between two solutions in continuous optimization problems. To calculate the distance between two fireflies, the concept of the firefly algorithm in the traveling salesman problem was specified by Jati et al. (2011) [25]. In this method, if the distance between the two solutions is greater than 10, e^-γr² tends to zero which means that the attractiveness of firefly in this distance is close to zero. In the present case, firstly a parameter named M is calculated whose amount between each two solutions is equal to the difference of the path matrix of a firefly in a level with another firefly in the same level. Primarily, for each level, the path matrix is obtained and the same procedure is repeated for all rows of the matrix. Thus, the first two elements i and j in the first path matrix are considered, then the element i in the second path matrix is found and its following number read, if matrix [i j] and matrix [i next (i)]) are not equal, 1 unit will be added to the difference of the two matrix (M). This trend will continue until all elements of the first matrix are examined for the rest of the levels. If the number of levels is not the same, the comparison is done on the same levels; the distance between the two solutions is obtained as follows:

$\begin{matrix} r = round (\frac{M}{distribution centers * client numbers} \\ + \frac{diffrences numbers between levels}{maximum level number}) \end{matrix}$ (20)

To move the firefly with weaker (e1) to higher intensity (e1), and in order to get it closer to the other fireflies, first a random number is generated, based on which, the firefly is changed. To make a change in the firefly, a random number is considered which will create the first column number of the primary firefly. For example, if the randomly generated number is 2, then the client number will be 4, which is dedicated to depots 2 and 3 according to their level numbers, respectively. Next, number 4 among the clients will be found in the second firefly matrix. The next path at level zero and the depot to which it is going to be assigned will be determined by its related path matrix. For instance, 4 moves to 1, and is assigned to depots 1, 2 and 3. First, 4 is found in matrix e1 and its previous columns are checked with previous columns of 4 in e1 and if consecutive numbers are the same, then they are considered as numbers attached to e1. If not, only 4 will be considered and it will be assigned to depots 1, 2 and 3. Then 1 in (e1) will be found and assigned to depots 1, 2 and 3, and the next consecutive columns will be checked with columns after 2 in the matrix (e2) and these numbers which are attached to 1 will be determined. Now, in the new matrix, the place of 4 and 2 will be changed so that 1 will be placed after 4, a displacement shown in Figs. 5 8. Another movement in the firefly algorithm is random movement; in the present paper, swap mutation was used.

Fig. 5

Finding random point in e₁.

Fig. 6

Find 4 and next number in e2.

Fig. 7

Change the columns fits e2.

Fig. 8

The modified e1.

3.5 Crossover and mutation

Crossover and mutation are operators that search in the solution area for exploring new solutions and exploiting good solutions. In order to do a crossover, 2 parents (solution) are selected by roulette wheel operators. After the selection of parents, two integer random numbers between 1 and the number of columns are produced. After that, two points crossover is done. For example, for doing a crossover on e1 and e3, the first random generated numbers which are 2 and 5 are produced. Then the children (new solution) are produced. For generating child 1, columns number 1, 2, 5 and 6 are generated from parent 1 and columns number 3 and 4 are generated from parent 2. Columns number 1, 2, 5 and 6 are generated from parent 2 and columns number 3 and 4 are generated from parent 1 for generating child 2. This procedure is shown in Fig. 9.

Fig. 9

Crossover and Mutation.

There are several mutation operators such as reverse, insertion, and swap mutation operators for exploring new solutions. In this paper, we used swap mutation. The first algorithm produces two integers random number between 1 and number of columns then swap mutation is done on it. For example, for doing a crossover on parent1 and parent2, randomly generated numbers are produced first. If the random numbers are 2 and 4, columns 2 and 4 are displaced. This procedure is shown in Fig. 9.

4 The sample problems

In this section, for certain parameters of the problems, a series of numerical examples of Prodhon (http://prodhonc.free.fr/Instances/instances_us.htm.) were used in LRP. The non-fallible depot is assumed as a center in all examples. Transportation cost parameter is considered as a fuzzy number. For other parameters of the model in the field of reliability, values are considered. Failure probability of each depot which is independent of others was selected from (0.03 and 0.001) randomly with the same probability for all depots. The probability of failure in vehicles was selected from (0.5, 0), assumed the same for all vehicles because of the transport system homogeneity. The probability of failure in connection paths and between every two nodes in the network was selected randomly from a uniform distribution. In order to have a complete set of example, these numbers were generated randomly and used as examples for examining the algorithms. Depot numbers 2 to 35 and customer numbers 8 to 350 were considered. The problems are divided into 3 groups: Small (less than 40 customers), medium (between 40 and 80 customers) and big (more than 80 customers).

4.1 Computation results

In order to set parameters affecting the algorithms, the response surface methodology (RSM) was used, and to compare the performance of the algorithms, three indexes were made use of that are proposed by Yu and Gen and has been used by many for comparing the algorithms [19 , 59], Number one being Spacing Metric (SM) that shows the uniform distribution of the Pareto’s solutions in the solution space. Another index is the Diversification Metric (DM) that indicates the extent of Pareto’s solutions of an algorithm. The higher the Diversification Metric, the better the algorithm will be. The third indicator is Mean Ideal Distance (MID) which measures the distance of Pareto’s solutions of the algorithm from the ideal point. Calculation methods of these indicators are given in relations (21) to (23). $SM = \frac{\sum_{i = 1}^{n - 1} | \bar{d} - d_{i} |}{(n - 1) \bar{d}}$ (21) $DM = \sqrt{{(\frac{{maxf}_{1 i} - {minf}_{1 i}}{f_{1 . total}^{\max} - f_{1 . total}^{\min}})}^{2} + {(\frac{{maxf}_{2 i} - {minf}_{2 i}}{f_{2 . total}^{\max} - f_{2 . total}^{\min}})}^{2}}$ (22) $MID = \frac{\sum_{i = 1}^{n} \sqrt{{(\frac{f_{1 i} - f_{1}^{best}}{f_{1, total}^{\max} - f_{1, total}^{\min}})}^{2} + {(\frac{f_{2 i} - f_{2}^{best}}{f_{2, total}^{\max} - f_{2, total}^{\min}})}^{2}}}{n}$ (23)

The result of the algorithm implementation is shown in Table 2. As it is shown in Figs. 10 17, answers in the firefly algorithm in most cases have a better DM index, meaning that the answers are more diverse. Regarding MID indices, however, the performance of discrete firefly algorithm is only suitable for small to medium problems; for problems bigger than that, it loses its effectiveness. Enlargement of the problem entails higher indexes in the firefly algorithm. In the case of SM index, NSGA-II algorithm has better indicators. Moreover, its execution speed is better than that of the firefly algorithm. In terms of the time required for the implementation of the algorithm, the speed of the NSGA-II algorithm is higher. The Table 3 shows the statistical hypothesis test used in the comparison of these methods. The normalizing test was done by MINITAB and at 95% confidence level.

Table 2

Result of algorithms

Problem number	DM		MID		SM
	NSGA-II	NSDFA	NSGA-II	NSDFA	NSGA-II	NSDFA
2#8	0.5554	0.6972	0.3187	0.4007	0.9654	0.7254
2#10	0.8049	0.8345	0.322	0.2874	0.6473	0.7851
3#10	0.3033	0.9615	0.3419	0.2735	0.8602	1.7988
3#15	0.0982	0.3347	0.359	0.0530	0.6336	0.8808
4#15	0.1477	0.8491	0.0477	0.2918	0.6588	0.9446
4#20	0.686	0.5182	0.3242	0.2302	0.9236	1.0215
5#20	0.3698	0.5339	0.1566	0.2426	1.3916	1.5702
6#30	0.2723	0.323	0.0882	0.004	1.1790	1.001
7#35	0.5976	0.9950	0.1288	0.1049	0.6883	0.8441
8#40	0.1361	0.1152	0.0947	0.1070	0.8692	2.0352
8#45	0.3285	0.3862	0.0467	0.1213	1.258	1.3064
9#55	0.3705	0.4170	0.063	0.1844	1.1975	1.4997
10#65	0.3639	0.4565	0.0653	0.1174	1.0543	1.745
12#75	0.3547	0.4024	0.0742	0.1596	1.1422	1.3778
14#85	0.2123	0.3439	0.0933	0.2043	0.9114	0.9968
15#90	0.1862	0.6550	0.0786	0.4138	0.3567	0.9737
17#100	0.1954	0.189	0.0291	0.0165	0.1512	1
20#150	0.145	0.2374	0.0501	0.1460	0.7584	0.7031
22#200	0.028	0.8253	0.1417	0.5711	0.6753	0.9219
25#250	0.1122	0.4269	0.3953	0.4947	0.5416	1.2788
30#300	0.6015	0.7965	0.1865	0.5011	1.1715	1.2855
35#350	0.2281	0.6745	0.0945	0.6532	1.0907	1.32

Fig. 10

Comparison of two algorithms based on DM.

Fig. 11

Comparison of two algorithms based on MID.

Fig. 12

Comparison of two algorithms based on SM.

Fig. 13

DM box plot.

Fig. 14

MID Boxplot for small problems.

Fig. 15

MID Boxplot for medium and big problems.

Fig. 16

SM Boxplot for small problems.

Fig. 17

SM Boxplot for medium and big problems.

Table 3

Statistical hypothesis test

H₀ (assumption)	t-test	P-value	result
NSGAII algorithm DM index ≤ NSDFA algorithm DM index	–3.56	0.99	H₀ is not rejected
NSGAII algorithm MID index ≥ NSDFA MID index (in small- and medium problems)	0.51	0.690	H₀ is not rejected
in NSGAII algorithm MID index ≥NSDFA MID index (in medium and big problems)	–3.58	0.002	H₀ is rejected
NSGAII algorithm SM index ≤ NSDFA in small- and medium- problems	–1.64	0.93	H₀ is not rejected
NSGAII algorithm SM index ≤ NSDFA SM index (in medium- and big problems)	–2.8	0.992	H₀ is not rejected

5 Concluding

The location-routing problem (LRP) have been considered from different points of view. It is important to deliver goods to customers with high reliability, hence the significance of reliability in LRPs. Reliable delivery of goods in emergency situations like delivering ammunition in war or first aid after a natural disaster is critical, and the possible failure has led decision makers to select alternatives with high reliability. In this paper, a multi-objective LRP considering reliability was presented. Reliability in LRP is considered as the probability of failure occurrence in depots, vehicles, and routes.

The proposed multi-objective model enables decision makers to locate their depots and routes for serving customers by considering the probability of failure. In this research, the problem had two objectives, minimizing the cost and maximizing the reliability, the latter expressed by minimizing the expected cost of failure. Transportation costs were uncertainty so the fuzzy numbers were used. A meta-heuristic algorithm (NSDSFA) was introduced for solving fuzzy multi-objective location and routing problem. A firefly algorithm by non-dominated sorting method and a new method for calculating distances and making movement between fireflies was also introduced.

The result of running algorithms for problems finally has shown a Pareto front. Each point of this front shows the calculated objectives of the answer matrix in Y and X axes. The answer matrixes show the location of depots and customer service routes. These points do not dominate each other and each point could be the final answer.

Finally, the comparisons of NSDSFA and NSGA-II results indicate that NSDFA has a better DM, but NSDFA is proper for small to medium problems as indicated by MID and SM metrics. It means the diversity of final answers in NSFDA is better than NSGA-II. The final answer of NSDFA for the small and medium-size problem have higher quality than NSGAII. NSGA-II is better for the large size problem. A direction for future research is to solve the problem by other meta-heuristic algorithms, or considering other important decision parameters like inventory control or delivering a different type of goods.

References

Albareda-Sambola

, Díaz

J.A.

and Fernández

, A compact model and tight bounds for a combined location-routing problem, Computers & Operations Research 32(3) (2005), 407–428.

Albareda-Sambola

, Fernández

and Laporte

, Heuristic and lower bound for a stochastic location-routing problem, European Journal of Operational Research 179(3) (2007), 940–955.

Bashiri

, Rasoulinejad

and Fallahzade

, A new approach on auxiliary vehicle assignment in capacitated location routing problem, International Journal of Systems Science 47(4) (2016), 886–902.

Belenguer

J.-M.

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

Berman

, Krass

and Menezes

M.B.

, Facility reliability issues in network p-median problems: strategic centralization and co-location effects, Operations Research 55(2) (2007), 332–350.

Contardo

, Cordeau

J.-F.

and Gendron

, An exact algorithm based on cut-and-column generation for the capacitated location-routing problem, INFORMS Journal on Computing 26(1) (2013), 88–102.

Contardo

, Cordeau

J.-F.

and Gendron

, A GRASP+ILP-based metaheuristic for the capacitated location-routing problem, Journal of Heuristics 20(1) (2014), 1–38.

De Angelis , et al., Multiperiod integrated routing and scheduling of World Food Programme cargo planes in Angola, Computers & Operations Research 34(6) (2007), 1601–1615.

Deb

, et al., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6(2) (2002), 182–197.

10.

Deng

, Zhenfu

and Qi

, Ranking fuzzy numbers with an area method using radius of gyration, Computers & Mathematics with Applications 51(6-7) (2006), 1127–1136.

11.

Derbel

, et al., An iterated local search for solving a location-routing problem, Electronic Notes in Discrete Mathematics 36 (2010), 875–882.

12.

Derbel

, et al., Genetic algorithm with iterated local search for solving a location-routing problem, Expert Systems with Applications 39(3) (2012), 2865–2871.

13.

Doulabi

S.H.H.

and Seifi

, Lower and upper bounds for location-arc routing problems with vehicle capacity constraints, European Journal of Operational Research 224(1) (2013), 189–208.

14.

Geoffrion

A.M.

and Graves

G.W.

, Multicommodity distribution system design by Benders decomposition, Management Science 20(5) (1974), 822–844.

15.

Ghaffari-Nasab

, Ahari

S.G.

and Ghazanfari

, A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands, Scientia Iranica 20(3) (2013), 919–930.

16.

Govindan

, et al., Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food, International Journal of Production Economics 152 (2014), 9–28.

17.

Hajipour

, et al., Multi-objective multi-layer congested facility location-allocation problem optimization with Pareto-based meta-heuristics, Applied Mathematical Modelling 40(7) (2016), 4948–4969.

18.

Hassan-Pour

, Mosadegh-Khah

and Tavakkoli-Moghaddam

, Solving a multi-objective multi-depot stochastic location-routing problem by a hybrid simulated annealing algorithm, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture 223(8) (2009), 1045–1054.

19.

Hassanzadeh

, Rasti-Barzoki

and Khosroshahi

, Two new meta-heuristics for a bi-objective supply chain scheduling problem in flow-shop environment, Applied Soft Computing 49 (2016), 335–351.

20.

Helander

M.E.

and Melachrinoudis

, Facility location and reliable route planning in hazardous material transportation, Transportation Science 31(3) (1997), 216–226.

21.

Hong

J.-D.

, Jeong

K.-Y.

and Xie

, A Multi-objective approach to planning in emergency logistics network design, International Journal of Industrial Engineering 22(4) (2015),

22.

Jabal-Ameli

, Aryanezhad

and Ghaffari-Nasab

, A variable neighborhood descent based heuristic to solve the capacitated location-routing problem, International Journal of Industrial Engineering Computations 2(1) (2011), 141–154.

23.

Jacobsen

S.K.

and Madsen

O.B.

, A comparative study of heuristics for a two-level routing-location problem, European Journal of Operational Research 5(6) (1980), 378–387.

24.

Jarboui

, et al., Variable neighborhood search for location routing, Computers & Operations Research 40(1) (2013), 47–57.

25.

Jati

G.K.

, Evolutionary discrete firefly algorithm for travelling salesman problem, in Adaptive and Intelligent Systems. (2011), Springer. 393–403.

26.

Javid

A.A.

and Azad

, Incorporating location, routing and inventory decisions in supply chain network design, Transportation Research Part E: Logistics and Transportation Review 46(5) (2010), 582–597.

27.

Kamalahmadi

and Mellat-Parast

, Developing a resilient supply chain through supplier flexibility and reliability assessment, International Journal of Production Research 54(1) (2016), 302–321.

28.

Laporte

and Nobert

, An exact algorithm for minimizing routing and operating costs in depot location, European Journal of Operational Research 6(2) (1981), 224–226.

29.

J.-Q.

, Mirchandani

P.B.

and Borenstein

, Real-time vehicle rerouting problems with time windows, European Journal of Operational Research 194(3) (2009), 711–727.

30.

Lim

, et al., A facility reliability problem: Formulation, properties, and algorithm, Naval Research Logistics (NRL) 57(1) (2010), 58–70.

31.

Maghsoudlou

, Afshar-Nadjafi

and Niaki

S.T.A.

, A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem, Computers & Chemical Engineering 88 (2016), 157–169.

32.

Marinakis

and Marinaki

, A bilevel genetic algorithm for a real life location routing problem, International Journal of Logistics: Research and Applications 11(1) (2008), 49–65.

33.

Miao

, Yu

and Xi

, The uncertainty evaluation method of supply chain reliability, Transport 24(4) (2009), 296–300.

34.

Min

, Jayaraman

and Srivastava

, Combined location-routing problems: A synthesis and future research directions, European Journal of Operational Research 108(1) (1998), 1–15.

35.

Mokhtari

N.-a.

and Ghezavati

, Integration of efficient multi-objective ant-colony and a heuristic method to solve a novel multi-objective mixed load school bus routing model, Applied Soft Computing 68 (2018), 92–109.

36.

, et al., Disruption management of the vehicle routing problem with vehicle breakdown, Journal of the Operational Research Society 62(4) (2011), 742–749.

37.

Nagy

and Salhi

, Location-routing: Issues, models and methods, European Journal of Operational Research 177(2) (2007), 649–672.

38.

Niakan

, et al., A new multi-objective mathematical model for dynamic cell formation under demand and cost uncertainty considering social criteria, Applied Mathematical Modelling 40(4) (2016), 2674–2691.

39.

Perl

and Daskin

M.S.

, A warehouse location-routing problem, Transportation Research Part B: Methodological 19(5) (1985), 381–396.

40.

Prins

, Prodhon

and Calvo

R.W.

, A Memetic Algorithm with Population Management (MA| PM) for the Capacitated Location-Routing Problem, Lecture Notes in Computer Science 3906 (2006), 183–194.

41.

Prins

, Prodhon

and Calvo

R.W.

, Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking, 4OR: A Quarterly Journal of Operations Research 4(3) (2006), 221–238.

42.

Prins

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

43.

Prodhon

and Prins

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

44.

Rahmani

, Ramdane Cherif-Khettaf

and Oulamara

, The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches, International Journal of Production Research 54(4) (2016), 999–1019.

45.

Rath

and Gutjahr

W.J.

, A math-heuristic for the warehouse location–routing problem in disaster relief, Computers & Operations Research 42 (2014), 25–39.

46.

Samanlioglu

, A multi-objective mathematical model for the industrial hazardous waste location-routing problem, European Journal of Operational Research 226(2) (2013), 332–340.

47.

Sansó

and Soumis

, Communication and transportation network reliability using routing models, IEEE Transactions on Reliability 40(1) (1991), 29–38.

48.

Singh

, et al., Shape optimization of a cyclone separator using multi-objective surrogate-based optimization, Applied Mathematical Modelling 40(5) (2016), 4248–4259.

49.

Snyder

L.V.

, Supply chain robustness and reliability: Models and algorithms, Northwestern University Evanston, IL. (2003).

50.

Snyder

L.V.

and Daskin

M.S.

, Reliability models for facility location: the expected failure cost case, Transportation Science 39(3) (2005), 400–416.

51.

Ting

C.-J.

and Chen

C.-H.

, A multiple ant colony optimization algorithm for the capacitated location routing problem, International Journal of Production Economics 141(1) (2013), 34–44.

52.

Vahdani

, et al., Reliable design of a closed loop supply chain network under uncertainty: An interval fuzzy possibilistic chance-constrained model, Engineering Optimization 45(6) (2013), 745–765.

53.

Wang

, Wu

and Hu

, A study of urgency vehicle routing disruption management problem, in Information Engineering (ICIE), 2010 WASE International Conference on. 2010. IEEE.

54.

Wang

, Yang

and Lu

, Multi-objective location-routing problem with simultaneous pickup and delivery for urban distribution, Journal of Intelligent & Fuzzy Systems 35(4) (2018), 3987–4000.

55.

Watson-Gandy

and Dohrn

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

56.

T.-H.

, Low

and Bai

J.-W.

, Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10) (2002), 1393–1415.

57.

Yang

X.-S.

, Nature-inspired metaheuristic algorithms. 2010: Luniver press.

58.

V.F.

and Lin

S.-Y.

, Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing, International Journal of Production Research 54(2) (2016), 526–549.

59.

and Gen

, Introduction to evolutionary algorithms, 2010 Springer Science & Business Media.

60.

Zarandi

M.H.F.

, et al., Capacitated location-routing problem with time windows under uncertainty, Knowledge-Based Systems 37 (2013), 480–489.

Fuzzy multi-objective location and routing problem

Abstract

Keywords

1 Introduction

2 Problem statement and modeling

2.1 The problem statement

2.2 Mathematical Modelling

Table 1 GAMS Number of customer # number of depots W1 W2 10#3 7295.71 226.158 15#4 7300.02 235.01 15#5 7305.08 237.153 20#6 7323.01 272.31

3.1 Firefly algorithm

4.1 Computation results

References

Table 1
GAMS

Number of customer # number of depots W₁ W₂

10#3 7295.71 226.158

15#4 7300.02 235.01

15#5 7305.08 237.153

20#6 7323.01 272.31