Abstract
Purpose
This study aims to investigate a locating-routing-allocating problems and the supply chain, including factories distributor candidate locations and retailers. The purpose of this paper is to minimize system costs and delivery time to retailers so that routing is done and the location of the distributors is located.
Design/methodology/approach
The problem gets closer to reality by adding some special conditions and constraints. Retail service start times have hard and soft time windows, and each customer has a demand for simultaneous delivery and pickups. System costs include the cost of transportation, non-compliance with the soft time window, construction of a distributor, purchase or rental of a vehicle and production costs. The conceptual model of the problem is first defined and modeled and then solved in small dimensions by general algebraic modeling system (GAMS) software and non-dominated sorting genetic algorithm II (NSGAII) and multiple objective particle swarm optimization (MOPSO) algorithms.
Findings
According to the solution of the mathematical model, the average error of the two proposed algorithms in comparison with the exact solution is less than 0.7%. Also, the algorithms’ performance in terms of deviation from the GAMS exact solution, is quite acceptable and for the largest problem (N = 100) is 0.4%. Accordingly, it is concluded that NSGAII is superior to MOSPSO.
Research limitations/implications
In this study, since the model is bi-objective, the priorities of decision makers in choosing the optimal solution have not been considered and each of the objective functions has been given equal importance according to the weighting methods. Also, the model has not been compared and analyzed in deterministic and robust modes. This is because all variables, except the one that represents the uncertainty of traffic modes, are deterministic and the random nature of the demand in each graph is not considered.
Practical implications
The results of the proposed model are valuable for any group of decision makers who care optimizing the production pattern at any level. The use of a heterogeneous fleet of delivery vehicles and application of stochastic optimization methods in defining the time windows, show how effective the distribution networks are in reducing operating costs.
Originality/value
This study fills the gaps in the relationship between location and routing decisions in a practical way, considering the real constraints of a distribution network, based on a multi-objective model in a three-echelon supply chain. The model is able to optimize the uncertainty in the performance of vehicles to select the refueling strategy or different traffic situations and bring it closer to the state of certainty. Moreover, two modified algorithms of NSGA-II and multiple objective particle swarm optimization (MOPSO) are provided to solve the model while the results are compared with the exact general algebraic modeling system (GAMS) method for the small- and medium-sized problems.
Keywords
Citation
Hashemi, L., Mahmoodi, A., Jasemi, M., Millar, R.C. and Laliberté, J. (2021), "Modeling a robust multi-objective locating-routing problem with bounded delivery time using meta-heuristic algorithms", Smart and Resilient Transportation, Vol. 3 No. 3, pp. 283-303. https://doi.org/10.1108/SRT-08-2021-0008
Publisher
:Emerald Publishing Limited
Copyright © 2021, Leila Hashemi, Armin Mahmoodi, Milad Jasemi, Richard C. Millar and Jeremy Laliberté.
License
Published in Smart and Resilient Transportation. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) licence. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this licence maybe seen at http://creativecommons.org/licences/by/4.0/legalcode
1. Introduction
Some of the most challenging problems in supply chain management (SCM) are facility location problem (FLP) and vehicle routing problem (VRP), a separate review of which increases costs and planning time. So, the location-routing problem (LRP) is proposed by considering FLP and VRP in SCM at the same time. (Misni et al., 2020)
In such problems, coordination between these two factors is the necessary condition for designing an efficient distribution network (Parast et al., 2021).
The problem that has always created many issues for large manufacturing companies to be able to meet the existing demand in a timely manner with the lowest possible transportation costs, both in the number of vehicles used and in the number of shipments, while being as profitable as possible.
In fact, by solving the inventory routing location problem, it is determined how much product, at what time and by what means of transportation and through which route to be sent to each of the retailers (customers).
In most supply chain locating routing models, it is usually assumed that the items can be transported for an indefinite time. While many goods do not follow this rule and over time will be qualitatively or quantitatively spoiled. Therefore, development of time window management concepts for routing locating problems to transfer products to customers is one of the key issues in transportation (Ohmori and Yoshimoto, 2021).
The concepts of time windows determine that each service to each customer must occur at a specific time interval and any important factors such as refueling restrictions, unsafe traffic conditions, vehicle depreciation, etc. that lead to delays in the delivery of products outside that time frame, can limit supply chain managers or logistics system decision makers. Therefore, considering them in locating routing models will bring their nature closer to the existing reality and will have a higher practical application (Yu et al., 2011).
In addition, in reality, factors such as customer demand, delivery time or shipping cost are not deterministic and customers due to running out of stock or untimely delivery or even minor factors such as load capacity restriction or refueling time, face shortages that lead to re-ordering or lost sales.
Many approaches have been proposed to address this uncertainty, which are based on stochastic methods and are referred to as stochastic VRPs. The purpose of such problems is to achieve a set of near-optimal answers that optimize each of the uncertain parameters for a set of worst-case scenarios (Yousefi et al., 2017).
Each of these optimal solutions must meet the limitations of time windows. In a multi-echelon supply chain, the simultaneous optimization of each of these factors at each echelon alone has added to the complexity of routing location problems, and so far the models have tried to facilitate this complexity in accordance with the priorities of decision makers in optimization. For example, in some studies, LRPs are formulated in the form of multi-objective and multi-echelon models, or the fleet of delivery vehicles is defined in a homogeneous and heterogeneous states, with either deterministic or stochastic data. However, reviewing all of them shows that there is a gap in the observance of the dependencies of the variables. For example, providing an optimal location model at the distribution center level certainly has a direct impact on the definition of product delivery time windows, at any echelon.
Therefore, in this study, an attempt has been made to provide an integrated model of a comprehensive and reliable distribution network in a three-echelon supply chain that simultaneously, in addition to locating distribution centers, routing transportation vehicles between supply chain echelons with two objectives of minimizing the operating costs in the first place and the transportation time in the second place, while other variables are selected based on the severity of their impact on each of these objectives. The deterministic variables are based on the historical data average and experts’ opinion. Such a model is rare in literature in which the variables are optimized based on the degree of influence on each other in the objective function. In fact, the innovation of the study can be summarized as follows:
Development of a multi-objective location-routing model in a three-echelon supply chain that includes manufacturers at the highest echelon, distribution centers and retailers (customers) at the lowest echelon as well as considering simultaneous demand of delivery and loading.
Development of a new mixed integer programming model for a heterogeneous transportation fleet with speed, capacity (depreciation cost of each vehicle is a function of its load capacity), fuel consumption (limitation of refueling in some candidate locations) and different purchasing costs.
Transportation time intervals evaluation in hard and soft time windows and showing their impact on the answers.
Using robust optimization considering different traffic scenarios.
Development of modified metaheuristic algorithms of NSGA II and MOPSO for a multi-objective location routing model.
Validation of the model with small and medium size problems by the exact method of GAMS.
Since each of the location and routing problems is an np-hard problem in itself, the LRP, as well as the capacitated LRP (CLRP), are also considered np-hard problems. If an accurate algorithm is used to solve these large problems, the solution time will increase exponentially. Accordingly, these problems cannot be solved definitively in many cases and, therefore, heuristic and metaheuristic approaches must be used
In this study NSGAII algorithm is used due to its more compatibility with discrete LRPs. MOPSO algorithm is used to solve the model and to achieve the optimal set of feasible solutions and to avoid falling into the trap of local optimality. Finally, the performance of each algorithm with the results obtained by the accurate method are compared and evaluated.
The rest of this article is organized as follows. In the second part, studies on VRP, methods of solving them with deterministic and in deterministic data and metaheuristic algorithms are reviewed. The third section describes the details of the multi-objective VRP model and describes its parameters and constraints. The first objective function is to minimize transportation costs, the cost of violating the soft time window, the fixed cost of distributor construction, the fixed cost of the vehicle and the cost of production. The second objective function minimizes the transportation time and finally explains the framework for using the indeterministic methods. In the fourth and fifth sections, the NSGAII and MOPSO algorithms are investigated to solve LRPs and their set of parameters and steps are defined. In the sixth section, the solution and the numerical results obtained are compared and analyzed with the deterministic method results for the sample problems. In the final section, conclusions, limitations and suggestions for the future researches are discussed.
2. Literature review
Over time, different types of VRP issues have developed, each with different models and features but their review, according to the presented model’s features, is done from four perspectives of VRP models with time window constraints, multi-objective VRP models, using random and fuzzy methods and metaheuristic methods to solve them.
In such problems, if a capacity constraint is added to the existing problem, it will become a capacitated VRP (CVRP). In CVRP, the vehicle has a limited capacity. So, it may be necessary to use multiple vehicles or routes instead of one vehicle. However, there is no distance constraint in such problems (Ralphs et al., 2004).
If there is a travel length constraint (in terms of distance or time), the distance constrained VRP (DVRP). Therefore, there are two types of constraints in these problems. One is the vehicle capacity constraint, and the other is the maximum distance the vehicle travels on the route (Toth and Vigo, 2002). Over time, new constraints have been introduced to the problem, one of which is VRP with hard time windows (VRPTW). In VRPTW, the customer is serviced on specific demand by a homogeneous transport fleet in which the capacity of each vehicle is limited. At the beginning and end of each route leading to the depot, customer service is provided within a certain period, and it is not possible to provide service outside this period. (Berger and Barkaoui, 2004). This problem, was suggested by Solomon (Solomon, 1987). Another problem is VRP with the soft time window (VRPSTW). The discussed time window shows the time constraint in a period with the earliest and latest start time of service. If the period is not observed, the cost of not observing the time window will be added to other costs (Beheshti and Hejazi, 2015). One of the new constraints is simultaneous delivery and pickups, which means that after receiving the goods from the vehicle, the customer delivers other goods to the vehicle to return to the depot, which is one of the new issues in VRP. In these problems, the customer receives and sends the goods at the same time (Tasan and Gen, 2012). These types of problems are referred to as VRP with simultaneous delivery and pickup (VRPSDP). Classical VRP involves depots, customers and vehicles to provide customer service. In these problems, the vehicle pickups the goods from the depot, provides service to customers along the route and returns to the depot. The number of vehicles and depots is limited, (Taş et al., 2014), the capacity of each vehicle is limited, and each vehicle can carry a certain amount of goods. Accordingly, the initial loading of the vehicle at each pickup should be less than its capacity. Besides, the weight of the load on the vehicle along the route should be less than its capacity. In the case of perishable food, early and late delivery is prohibited. VRPTW is an attractive and easy single-depot (SD) problem but not suitable for companies with more than one depot, and sometimes more than one depot should be considered for the problems (Karakatič and Podgorelec, 2015). In these problems, called multiple-depot VRP (MDVRP), each customer receives service through only one depot, and each route ends at the same depot that begins (Allahyari et al., 2015) and (Vidal et al., 2015). The goal of solving the problem in VRP is to minimize costs. In many VRPs, the distance traveled between customers or the total travel time between cities is considered a cost and is placed in the objective function. In the real world, however, other costs, such as minimizing vehicle usage, travel time and waiting time, sometimes need to be calculated (Qi, 2015). So, sometimes special techniques must be used to calculate the objective function. Such problems are referred to as multi-objective VRPs (MOVRP), for example reducing the number of vehicles while minimizing the distance traveled by the vehicle. Another type of VRP involves two types of customers. The first type of customers receives the goods from the depot, and the second type of customers includes the suppliers who send the goods to the depot. Such problems are called VRPs with backhauls (VRPB) (Cuervo et al., 2014) and (Mahmoudi et al., 2020).
Some other VRP models are offered in a multi echelon supply chain. (Rahbari et al., 2020) have presented a model of location-routing-inventory problems in a five-echelon supply chain of red meat preparation and delivery. Because its transportation quality requires the management of all the processes from production to delivery, all five echelons are considered in the optimization and numerical results are presented in the form of a case study using GAMS accurate method. (Wang et al., 2021) have proposed a two-echelon location routing model in which the time window constraints are considered and the possibility of sharing transportation vehicles capacity on the same routes is considered during routing. The model is called a two-echelon LRP with time windows and transportation resource sharing (2E-LRPTWTRS) and then the modified MPSO algorithm is used to solve it. (Mohebban-Azad et al., 2021) provide a model of inventory routing location problems at three echelons of the supply chain, considering deterministic risk in all the distribution centers that leads to the reliability and continuity of the flow in that chain. The proposed model is then solved using the Lagrangian relaxation algorithm (Saffarian et al., 2020).
From the perspective of the degree of certainty of data, in some studies, the problem data are not considered to be deterministic but stochastic or fuzzy. In VRP with fuzzy demands (OVRPFD), data can be obtained experimentally. For example, it is said that customer demand is about 40 units, i.e. between 20 and 70 units, which can be a triangular fuzzy number (Cao and Lai, 2010). In some other studies, customer demand is defined as stochastic. For example, it is said that customer demand follows a continuous uniform distribution function (Gauvin et al., 2014). One of the constraints added to VRPs is the heterogeneous vehicle fleet, meaning that vehicle load rates vary (Koç et al., 2014). In some VRPs, vehicle velocities vary on different days and are not always the same (Kuo, 2009). In classical or simple VRP, customer service is provided in one day, but in another type called periodic VRP, service is provided over a period that can be two or more days (Lúcia and Drummond, 2001).
Another type of VRP problems are the Shortest Path (SP) models. For example, Di Caprio et al. (2021) have proposed a routing model in which the weights given to the selected paths are fuzzy and indeterministic, and the proposed model is solved by three algorithms of genetic, particle swarm and ants, and the numerical results are compared. Ebrahimnejad et al. (2021) have presented a model of uncertain SP that estimates the Mixed Interval-Valued Fuzzy interval and solve it using MOPSO algorithm, modified artificial bee colony (MABC) algorithm and NSGAII.
Abbaszadeh et al. (2020) have presented Robot’s Fuzzy constrained shortest route problem (FCSRP) model to find the SP in robots. Data on energy consumption along the path and the distance traveled are considered fuzzy. Then, three algorithms of elite artificial bees' colony (EABC) algorithm, MOPSO algorithm and NSGAII algorithm are used to solve it. The results show that EABC algorithm has been the superior one with shorter time and more convergence. Ebrahimnejad et al. (2015) develop a new model of the SP problem in a network of fuzzy weights of arcs, for which a modified MOPSO algorithm has been developed and applied. In another study by the same researcher in 2016, application of the fuzzy SP (FSP) model to wireless sensor network (WSN) problems is analyzed and solved using an ABC algorithm (Ahmadi et al., 2018).
As mentioned earlier, VRP problems are considered Np-hard and various metaheuristic methods have always been developed and used to solve them. Biuki et al. (2020) studied a routing-location-inventory model for the supply chain of perishable materials. The purpose of this study is to solve the problem of sustainability and integration of the real-world assumptions to minimize environmental costs and pollution. To solve the problem, two algorithms of genetics and PSO have been used to solve the numerical problems in different sizes. Li et al. (2018) developed a green routing location model that minimizes greenhouse gas emissions and is based on the cold location chain. In such problems, the storage temperature of the material during transportation is kept low and PSO algorithm is used to solve it. Peng et al. (2018) presented a metaheuristic approach to simulate particles motion to solve the routing-location problem when the capacity is limited. Moshref-Javadi et al. (2016) presented a model for the problem of location-routing while delays are allowed. Also, two metaheuristic algorithms were designed to solve the numerical problems.
Qin et al. (2021) studied a heterogeneous VRP involving the routing of a predefined fleet with different vehicle capacities to serve a range of customers with the aim of minimizing the maximum vehicle routing time. In this study, they formulated a MILP model to achieve the optimal solutions to the small-scale problems. Numerical experiments showed that the proposed algorithm is better than the MILP solution in the large-scale problems and performs better than existing meta-heuristic algorithms. The summarized of the researches can be seen in Table 1.
3. Problem statement
In this problem, a three-echelon supply chain is examined with factories at the highest level, distributors at the second level and retailers at the lowest level. For the echelon of distributors, there are candidate locations for construction where the distributors will be located. Retailers and vehicles are assigned to these distributors simultaneously, and delivery routes from distributors to retailers are routed. Delivery to customers is done by a heterogeneous transport fleet in which vehicles have different velocities, capacities, fuel consumption, and purchase costs. Distributors that are used and constructed must be assigned to a factory. Each vehicle is assigned to only one distributor, and the start and end of its route will be from the same distributor. Two periods are defined as time constraints for providing services to retailers. The first constraint is the hard time window. In the hard time window, it is not allowed
to provide service to customers i earlier than time αi and later than time αi. The second constraint is the soft time constraint in the period [Esi, Lsi], meaning that if customer service i is performed earlier than time Esi and later than the time Lsi, customer service is provided, but the system will be penalized, and the deviation will continue as long as the hard time window is not violated. In that case, no service will be provided at that time. Each customer has two types of certain demand: the delivery demand based on which the goods are loaded from the depot and delivered to the customer and the pickup demand based on which the goods are picked up from the customer and returned to the depot.
In this study, system costs include the cost of moving and refueling the vehicle along each route, the fixed cost of using the vehicles, the cost of distributors at candidate locations, the cost of not complying with the soft time window, and the cost of production.
Retailers are divided into two types R1 and type R2. R1 retailers are those where vehicles can refuel at their location, and R2 retailers are those where vehicles cannot refuel at their location. Each retailer is serviced once and only once on one route by one vehicle. Each vehicle is used in one route only and is assigned to only one distributor. Another constraint defined in the problem is the time constraint for the vehicle backhaul to a distributor. For each customer, the loading operation is done after the delivery of the goods. In this study, vehicle velocity has different modes according to different traffic conditions. In these cases, the robust optimization method is used. The method proposed by Mulvey is used to take advantage of robust optimization. In this method, the optimized LP model is as follows:
Moreover, a finite set of scenarios φ = {1,2,3,…, s} is assumed for the deterministic parameters of the model, and a set {ds, Bs, Cs, es} is defined as the realization of the performance of each scenario based on each scenario s ∈ φ. PS, on the other hand, indicates the probability of any scenario occurring, which is
4. Mathematical model
4.1 Sets
D = A set of distributor candidate locations
F = A set of factories
R = A set of retailers
K = A set of vehicles
R1 = A set of customer locations where refueling is possible
R2 = A set of customer locations where refueling is not possible
U = A set of different traffic scenarios
4.2 Parameters
RI = The amount of delivery demand of retailer i
Pi = The amount of pickup demand of retailer i
Si = Time to provide service to retailer i
Qk = Loading capacity of each vehicle k
ai = The earliest time allowed to provide service to distributor i in the hard time window
bi = The latest time allowed to provide service to distributor i in the hard time window
M = Optional large number
ESi = The earliest time allowed to provide service to distributor i in the soft time window
LSi = The latest time allowed to provide service to distributor i in the soft time window
W2 = Cost per unit time deviation from the earliest time allowed in the soft time window
W3 = Cost per unit time deviation from the latest time allowed in the soft time window
C = Cost of one fuel unit
AT = Minimum amount of fuel allowed inside the vehicle
Cff = Production cost of a unit in factory f
fixd = Cost of constructing distributor candidate location d
TSi = Time to provide service to retailer i
AT = Minimum amount of fuel allowed in the vehicle
DAY = The length of a working day
cpji = Vehicle fuel consumption from node i to node j
dxij = The distance between node i and node j
full = Fuel tank capacity
pu = The probability of occurrence of event u
Vku = The velocity of vehicle k in event u
capd = The capacity of candidate location of distributor d
4.3 Decision variables
Xijkd = The variables zero and one. If vehicle k belonging to distributor d travels from node i to node j, it is equal to one and otherwise zero.
siu = The time to start providing service to retailer i in event u
L0k = The load on vehicle k when leaving the distributor
Lj = The weight of the load remaining on the vehicle after service to retailer j
Zd = The variables zero and one. If distributor d is constructed, it is equal to one and otherwise zero
Eiu = The time deviation from the earliest time allowed to provide service to retailer i in the soft time window in event u
Liu = The time deviation from the latest time allowed to provide service to retailer i in the soft time window in event u
FCk = The time to end the route of vehicle k
ded: The center demand of distributor d
Ydf = Variables zero and one. If distributor d is assigned to factory f, it is equal to one and otherwise zero.
Ai = The amount of fuel available on the vehicle
The first objective function is to minimize the set of costs. The first part of the objective function represents the cost of transportation, the second and third parts represent the cost of non-compliance with the soft time window, the fourth part represents the fixed cost of constructing a distributor, the fifth part represents the fixed cost of the vehicle, and the sixth part represents the objective function of the cost of production.
In the second objective function, the service time is minimized.
Subject to:
Constraint (1) ensures that a vehicle enters each retailer and meets the retailer's demand.
Constraint (2) ensures that any vehicle leaving the distributor returns to the same distributor at the end of the route.
Constraint (3) ensures that any vehicle that enters a node to provide service to any retailer exits that node.
Constraint (4) ensures that each vehicle is used in only one distributor.
Constraints (5 and 6) ensure that if a vehicle leaves a distributor, that vehicle belongs only to that distributor.
Constraint (7) ensures that there is no edge from each node to itself.
Constraints (8 and 9) calculate the start time of service to each retailer.
Constraint (10) ensures that the start time of the vehicle is zero.
Constraint (11) ensures compliance with the hard time window limit.
Constraint (12) calculates the amount of initial loading of the vehicle.
Constraint (13) examines the capacity constraint of the vehicle for the initial loading.
Constraints (14 and 15) calculate the weight of the load on the vehicle after leaving the first retailer along the route.
Constraints (16 and 17) calculate the weight of the load on the vehicle after leaving other retailers
Constraint (18) examines the capacity constraint of the vehicle for the weight of the load on the vehicle along the route.
Constraint (19) calculates the deviation from the soft time window for retailers.
Constraints (19 and 20) calculate the soft time window deviation for retailers.
Constraint (21) indicates that at the end of the service to retailers where refueling is possible, the amount of fuel in the vehicle fuel tank is full.
Constraint (22) calculates the amount of fuel in the vehicle fuel tank at the end of service to retailers where refueling is not possible.
Constraint (23) ensures that the vehicle fuel constraint is observed.
Constraint (24) identifies constructed distributors.
Constraint (25) ensures that each distributor constructed is assigned to one factory.
Constraint (26) calculates the demand of each distributor.
Constraint (27) examines the demand constraint of each distributor.
Constraint (28) examines the demand constraint of each factory.
Constraint (29) calculates the travel time for each vehicle.
Constraint (30) examines the time constraint of the travel length in a day.
Constraint (31) specifies the variables zero and one.
Constraint (32) specifies variables greater than or equal to zero.
5. Providing solutions by non-dominated sorting genetic algorithm II (NSGA-II)
NSGAII is a well-known algorithm in which a population of solutions is created first, and a proper reproduction process causes parents to be selected at each stage. From the selected parents, new children are formed that have some of the characteristics of a parent and can better reproduce. Some components of the NSGAII algorithm have the following features.
5.1 Showing initial solution
In this study, the initial solution consists of three parts. The first part contains n + k-1 cells. If n is the number of retailers and k is the number of vehicles, the initial solution consists of a row with n + k −1 cells containing ordinal numbers 1 to n + k–1. The numbers 1 to n indicate the number of retailers, and the numbers n + 1 to n + k–1 indicate the arrival of the vehicle to the distributors, in other words, the end of the route and the use of another vehicle. The order of the numbers inside the columns indicates the order of service to retailers. The number n + i represents vehicle i, and the retailers that precede it represent the retailers that are serviced by that vehicle, respectively. If there is no retailer number before the vehicle number, it means that none of the retailers have been assigned to that vehicle and that the vehicle has not been used. All retailers after the last vehicle number are assigned to the last vehicle, respectively. In this part, retailers are assigned to vehicles. The second part consists of k + d–1 cells, where k is the number of vehicles and d is the number of candidate locations for the construction of distributors. Similar to the previous part, this part allocates the vehicles used for distributors. The third part contains d + f–1 cells in which d is the number of distributors and f is the number of factories. Similar to the previous parts, in this part, the distributors used are assigned to the factories.
To understand more, an example of the initial solution is given. This example is shown in Figure 1–4, where there are eight retailers, three vehicles, and three distributor candidate locations. In the first part, the numbers 1 to 8 represent the retailers, and the numbers 9 and 10 represent the first and second distributors, respectively. As can be seen in Figure 1, retailers 4, 6, and 8 are serviced by the first vehicle, retailers 1 and 3 are serviced by the second vehicle and retailers 7, 2, and 5 are serviced by the third vehicle. In the second part, the numbers 1 to 3 indicate the number of vehicles, and the numbers 4 and 5 indicate the first and second distributors. According to the proposed solution, the first and second vehicles are assigned to distributor 1 and the third vehicle is assigned to distributor 2. In this part, distributor 3 is not constructed. In the third part, the numbers 1 to 3 indicate the number of distributors and the number 4 indicates the first factory. According to the solution, distributor 1 is assigned to the second factory and distributor 2 to the second factory. (Table 2)
5.2 Parents selection
In the proposed algorithm, after calculating the fit of the objective functions of each chromosome and sorting the population based on the conditions of domination, new parents are selected to create a new population. The tournament method is used for each parent selection. In this method, the two chromosomes are first randomly selected, and each of the higher-ranking solutions is selected as the first parent. To select the second parent, two chromosomes are first selected randomly and each of the higher-ranking solutions is selected as the second parent.
5.3 The crossover operator to produce new children
After selecting two parents by the tournament method, the two-point crossover method is used to create new children, based on which two crossover points are randomly selected for each part of the initial two-by-two solution. The genes between these two points in the first parent are passed directly to the first child, and the remaining genes in the second parent are copied to the first child (Figure 2).
5.4 Mutation operator
After implementing the crossover operator, each child may change randomly to generate a random number. If this number is less than the mutation rate, the child is changed by the mutation operator. Two genes are randomly selected first, and the numbers inside the two genes are then swapped for a genetic mutation (Figure 3).
6. Numerical results
An example, with eight retailers, three candidate locations for distributors, and two factories, is randomly generated and the solution obtained from GAMS software is analyzed to validate the proposed model. For this purpose, the observance of the constraints and the accuracy of the value of the objective function obtained from GAMS software are checked. Figure 4 shows the schematic solution obtained from GAMS software. In this solution, a distributor is constructed in Locations 1 and 2, and no distributor is constructed in Location 3. In both distributors, two vehicles were used. Figure 7 shows the routes. The best value function obtained from GAMS software is 2323 for the first objective function and 521 for the second objective function. The calculations indicate that the values obtained are quite accurate.
In the step to check the problem constraints, the soft and hard time window constraints are first checked, the results of which are shown in Figures 5 and 6. In each figure, the first and last time of service in the time window and the actual time of service are specified. According to Figures 1 and 2, both constraints are observed.
Figure 7 shows the initial loading constraint; Figure 8 shows the constraint on the weight of the load on the vehicle along the route. In Figure 7, number 1 represents distributor 1 of route 1, number 2 represents distributor 1 of route 2, number 3 represents distributor 2 of route 1 and number 4 represents distributor 2 of route 2. In Figures 7 and 8, the constraint on the weight of the load on the vehicle is not violated.
In the next step to test the proposed NSGAII algorithm, small examples are randomly generated, solved and compared by GAMS software and genetic algorithm, the results of which are presented in Table 5.
The small problem is implemented using GAMS software and the proposed NSGAII algorithm, the results of which are given in Tables 3 and 4. According to Table 3, the value of the exact solution deviation obtained from GAMS software and NSGAII algorithm for the values of the first and second objective functions has an acceptable deviation. Accordingly, it can be argued that the proposed small NSGAII algorithm has good performance.
As the size of the problem increases, the problem cannot be solved using GAMS software or other precise methods. So, to test the performance of the NSGAII algorithm in large sizes, examples are created and the NSGAII and MOPSO algorithms are solved. The results of Tables 5 and 6 show the acceptable deviation between the mean of the solutions obtained from NSGAII and MOPSO and the better values of the NSGAII algorithm.
7. Conclusion and recommendations
The model presented in this study has many constraints and complex conditions. The use of new decision variables makes modeling attractive. At the beginning of the study, a conceptual model for the problem is presented. Accordingly, a mathematical model is proposed, and the accuracy and efficiency of the model are checked and verified by solving a stochastic example using GAMS software. Since the problem is complex and small in size, the NSGAII algorithm is proposed to solve it, and the efficiency of the algorithm in large and small sizes is then proven.
In fact, comprising the values of the fitness functions indicate that, in solving problems with small size, the NSGAII has achieved better performance against the MOPSO algorithm. Although the obtained results have been issued in a shorter time by MOPSO, in terms of optimizing the objectives, and proposing the best non-dominated solutions, the superiority of the NSGA-II is obviously proven. Moreover, the average error of the two proposed algorithms in comparison with the exact solution is less than 0.7% which is one more verification for the efficiency and performance of the algorithms.
Future studies are recommended to consider demand as stochastic, consider candidate areas in the depot as uncertain or continuous, consider the problem as three-objective, or add minimizing greenhouse gas emissions to the objectives of the problem. Moreover, the use of other meta-heuristic methods to solve the problem is recommended.
Figures
Overview of the literature on location-routing problem
| Authors | year | Modeling Approach | No. of echelons | Planning objective | Operational Decision | Transport Fleet | Time windows |
Data | Solving methods | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Single | multiple | logistic | Routing | Inventory | Heterogeneous | Homogeneous | deterministic | Non-deterministic | Exact | Meta-heuristic/ heuristic | |||||
| Erbao Cao | 2010 | MILP | 1 | √ | √ | √ | Stochastic simulation | ||||||||
| Tasan, et al. | 2012 | MILP | 1 | √ | √ | √ | √ | GA* | |||||||
| Taş et al. | 2014 | MILP | 1 | √ | √ | √ | √ | √ | |||||||
| Palhazi Cuervo et al. | 2014 | MILP | 1 | √ | √ | √ | Greedy, k-median | ||||||||
| Koç et al. | 2014 | MILP | 1 | √ | √ | √ | √ | √ | √ | GA | |||||
| Ebrahim nejad et al. |
2015 | MILP | 1 | √ | √ | √ | GA, PSO | ||||||||
| Qi et al. | 2015 | MILP | 1 | √ | √ | √ | √ | MA** | |||||||
| Ebrahim nejad et al. |
2016 | MILP | 1 | √ | √ | √ | ABC***** | ||||||||
| Moshref-Javadi et al. | 2016 | MINLP | 1 | √ | √ | √ | √ | √ | MA, RGA*** | ||||||
| PENG et al. | 2018 | MINLP | 1 | √ | √ | √ | GA | ||||||||
| Li et al. | 2018 | MINLP | 1 | √ | √ | √ | √ | MPSO**** | |||||||
| Abbaszadeh et al. | 2019 | 1 | √ | √ | √ | EABC, MPSO, GA | |||||||||
| Biuki et al. | 2020 | MIP | 1 | √ | √ | √ | √ | √ | GA, PSO | ||||||
| Rahbari et al. | 2020 | MIP | 5 | √ | √ | √ | √ | √ | √ | √ | |||||
| Wang et al. | 2021 | MIP | 2 | √ | √ | √ | √ | √ | √ | MPSO | |||||
| Mohebban-Azad et al. | 2021 | MINLP | 3 | √ | √ | √ | √ | √ | √ | √ | Lagrangian relaxation | ||||
| Qin et al. | 2021 | MILP | 1 | √ | √ | √ | √ | einforcement learning | |||||||
| Caprio et al. | 2021 | MILP | 1 | √ | √ | √ | √ | √ | ABC, PSO, GA | ||||||
| Ebrahim nejad et al. |
2021 | MIP | 2 | √ | √ | ABC, PSO, GA | |||||||||
MINLP = Mixed-integer nonlinear programming *Genetic Algorithm, **Memetic Algorithm, ***Recursive Granular Algorithm, **** Modified Particles Swarm Optimization, *****Elite artificial bees' colony
Solution of example
| Retailers | Distributor | Number of vehicles | Rout |
|---|---|---|---|
| 2 | 1 | 1 | 4–6-8 |
| 2 | 1 | 2 | 1–3 |
| 1 | 2 | 3 | 7–2-5 |
Comparison of the answer of NSGAII with the exact solution in small sizes for the first objective function
| Number of retailers | Mean NSGAII | Gams | Gap(%) | Exact |
|---|---|---|---|---|
| N = 4 | 1160 | 1160 | 0 | 1160 |
| N = 5 | 2061 | 2047 | 0 | 2047 |
| N = 6 | 2124.2 | 2120 | 0.2 | 2120 |
| N = 7 | 2259.7 | 2253 | 0.3 | 2253 |
| N = 8 | 2339.5 | 2329 | 0.5 | 2329 |
| N = 9 | 3342.5 | 3320 | 0.7 | 3320 |
| N = 10 | 3682.4 | 3658 | 0.7 | 3658 |
Comparison of the answer of NSGAII with the exact solution in small sizes for the second objective function
| Number of retailers | NSGAII | Gams | Gap(%) | Exact |
|---|---|---|---|---|
| N = 4 | 153 | 153 | 0 | 1160 |
| N = 5 | 183 | 183 | 0 | 2047 |
| N = 6 | 201 | 201 | 0 | 2120 |
| N = 7 | 225.4 | 225 | 0.2 | 2253 |
| N = 8 | 238.7 | 238 | 0.3 | 2329 |
| N = 9 | 252.8 | 251 | 0.7 | 3320 |
| N = 10 | 306.8 | 304 | 0.9 | 3650 |
Comparison of the answer of NSGAII and MOPSO in large sizes for the first objective function
| Number of retailers | NSGAII | MOPSO | scattering GA(%) |
|---|---|---|---|
| N = 30 | 10251 | 10269 | 0.2 |
| N = 50 | 48351 | 48396 | 0.1 |
| N = 100 | 73896 | 73987 | 0.2 |
Comparison of the answer of NSGAII and MOPSO in large sizes for the second objective function
| Number of retailers | NSGAII | MOPSO | scattering GA(%) |
|---|---|---|---|
| N = 30 | 1236 | 1239 | 0.2 |
| N = 50 | 1538 | 1546 | 0.4 |
| N = 100 | 2369 | 2378 | 0.4 |
References
Abbaszadeh Sori, A., Ebrahimnejad, A. and Motameni, H. (2020), “Elite artificial bees’ colony algorithm to solve robot’s fuzzy constrained routing problem”, Copputational Intelligence, Vol. 36 No. 2, pp. 659-681.
Ahmadi, E., Jasemi, M., Monplaisir, L., Nabavi, M.A., Mahmoodi, A. and Amini Jam, P. (2018), “New efficient hybrid candlestick technical analysis model for stock market timing on the basis of the support vector machine and heuristic algorithms of imperialist competition and genetic”, Expert Systems with Applications, Vol. 94, pp. 21-31, ISSN 0957-4174, doi: 10.1016/j.eswa.2017.10.023.
Allahyari, S., Salari, M. and Vigo, D. (2015), “A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem”, European Journal of Operational Research, Vol. 242 No. 3, pp. 756-768.
Beheshti, A.K. and Hejazi, S.R. (2015), “A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window”, Information Sciences, Vol. 316, pp. 598-615.
Berger, J. and Barkaoui, M. (2004), “A parallel hybrid genetic algorithm for the vehicle routing problem with time windows”, Computers and Operations Research, Vol. 31 No. 12, pp. 2037-2053. October.
Biuki, M., Kazemi, A. and Alinezhad, A. (2020), “An integrated location-routing-inventory model for sustainable design of a perishable products supply chain network”, Journal of Cleaner Production, Vol. 260, p. 120842.
Cao, E. and Lai, M. (2010), “The open vehicle routing problem with fuzzy demands”, Expert Systems with Applications, Vol. 37 No. 3, pp. 2405-2411.
Cuervo, D.P., Goos, P., Sörensen, K. and Arráiz, E. (2014), “An iterated local search algorithm for the vehicle routing problem with backhauls”, European Journal of Operational Research, Vol. 237 No. 2, pp. 454-464, 1 September 2014.
Di Caprio, D., Ebrahimnejad, A., and Alrezaamiri, H. and Santos-Arteaga, F. (2021), “A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights”, Alexandria Engineering Journal, Vol. 61 No. 1, pp. 10-23.
Ebrahimnejad, A., Enayattabr, M. and Motameni, H. (2021), “Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem”, Complex Intell System, Vol. 7, pp. 1527-1545, doi: 10.1007/s40747-021-00278-0.
Ebrahimnejad, A., Karimnejad, Z. and Alrezaamiri, H. (2015), “Particle swarm optimization algorithm for solving shortest path problems with mixed fuzzy arc weights”, International Journal of Applied Decision Sciences (IJADS), Vol. 8 No. 2, pp. 203-222.
Gauvin, C., Desaulniers, G. and Gendreau, M. (2014), “A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands”, Computers and Operations Research, Vol. 50, pp. 141-153.
Karakatič, S. and Podgorelec, V. (2015), “A survey of genetic algorithms for solving multi depot vehicle routing problem”, Applied Soft Computing, Vol. 27, pp. 519-532.
Koç, Ç., Bektaş, T., Jabali, O. and Laporte, G. (2014), “A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows”, Computers and Operations Research, Vol. 64, pp. 11-27.
Kuo, Y., Wang, C.C. and Chuang, P.Y. (2009), “Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds”, Computers and Industrial Engineering, Vol. 57 No. 4, pp. 1385-1392.
Li, Y., Lim, M.K. and Tseng, M.L. (2018), “A green vehicle routing model based on modified particle swarm optimization for cold chain logistics”, Industrial Management & Data Systems, Vol. 119 No. 3, pp. 473-494.
Lúcia, M.A. and Drummond, L.S. (2001), “An asynchronous parallel metaheuristic for the period vehicle routing problem”, Future Generation Computer Systems, Vol. 17 No. 4, pp. 379-386, January 2001.
Mahmoudi, A., Hashemi, L., Jasemi, M. and Pope, J. (2020), “A comparison on particle swarm optimization and genetic algorithm performances in deriving the efficient frontier of stocks portfolios based on a mean-lower partial moment model”, International Journal of Finance & Economics., Vol. 26 No. 4, pp. 4857-6487, doi: 10.1002/ijfe.2086.
Misni, F., Lee, L.S. and Seow, H.V. (2020), “Hybrid harmony search-simulated annealing algorithm for location-inventory-routing problem in supply chain network design with defect and non-defect items”, Applied Sciences, Vol. 10 No. 18, p. 6625.
Mohebban-Azad, E., Abtahi, H., Darestani, A.-R. and Yousefi-Zenouz, H. (2021), “A reliable location-inventory-routing three-echelon supply chain network under disruption risks”, Journal of Modelling in Management, Vol. ahead-of-print No. ahead-of-print.
Moshref-Javadi, M. and Lee, S. (2016), “The latency location-routing problem”, European Journal of Operational Research, Vol. 255, pp. 604-619.
Parast, Z.Z.D., Haleh, H., Darestani, S.A. and Amin-Tahmasbi, H. (2021), “Green reverse supply chain network design considering location-routing-inventory decisions with simultaneous pickup and delivery”, Environmental Science and Pollution Research, pp. 1-22.
Peng, K., Liu, W., Sun, Q., Ma, X., Hu, M., Wang, D. and Liu, J. (2018), “Wide-area vehicle-drone cooperative sensing: opportunities and approaches”, IEEE Access, Vol. 7, pp. 1818-1828.
Ohmori, S. and Yoshimoto, K. (2021), “Multi-product multi-vehicle inventory routing problem with vehicle compatibility and site dependency: a case study in the restaurant chain industry”, Uncertain Supply Chain Management, Vol. 9 No. 2, pp. 351-362.
Qi, Y., Hou, Z., Li, H., Huang, J. and Li, X. (2015), “A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows”, Computers and Operations Research, Vol. 62, pp. 61-77, October 2015.
Qin, W., Zhuang, Z., Huang, Z. and Huang, H. (2021), “A novel reinforcement learning-based hyper-heuristic for heterogeneous vehicle routing problem”, Computers & Industrial Engineering, Vol. 156, p. 107252.
Ralphs, T.K., Kopman, L., Pulleyblank, W.R. and Trotter, L.E. (2004), “On the capacitated vehicle routing problem”, Mathematical Programming, Vol. 94 Nos 2/3, pp. 343-359.
Rahbari, M., Razavi Hajiagha, S.H., Rhahi Dehaghi, M., Moallem, M. and Riahi Dorcheh, F. (2020), “Modeling and solving a five-echelon location–inventory–routing problem for red meat supply chain Case study in Iran”, Kybernetes, Vol. 50 No. 1, pp. 66-99.
Saffarian, S.H., Mahmoudi, A., Mohsen, S.H., Jasemi, M. and Hashemi, L. (2020), “Measuring the effectiveness of AHP and fuzzy AHP models in environmental risk assessment of a gas power plant”, Human and Ecological Risk Assessment: An International Journal, doi: 10.1080/10807039.2020.1816809.
Solomon, M. (1987), “Algorithms for the vehicle routing and scheduling problems with time window constraints”, Operations Research ( Research), Vol. 35 No. 2, pp. 254-265. March–April (2)) (1987).
Taş, D., Jabali, O. and Van Woensel, T. (2014), “A vehicle routing problem with flexible time windows”, Computers and Operations Research, Vol. 52, pp. 39-54. Part A.
Tasan, A.S. and Gen, M. (2012), “A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliverie”, Computers and Industrial Engineering, Vol. 62 No. 3, pp. 755-761.
Toth, P. and Vigo, D. (2002), Book, ‘Vehicle Routing Problem, on Discrete Mathematics and Applications’, 2002, (Chapter 1). An overview of vehicle routing problems, Society for Industrial and Applied Mathematics (SIAM) Monographs, Philadelphia, pp. 1-26, doi: 10.1137/1.9780898718515.
Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C. (2015), “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows”, Computers and Operations Research, Vol. 40 No. 1, pp. 475-489.
Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M. and Wang, Y. (2018), “Two-echelon location-routing optimization with time windows based on customer clustering”, Expert Systems with Applications, Vol. 104, pp. 244-260.
Yousefi, H., Tavakkoli-Moghaddam, R., Oliaei, N., Mohammadi, M. and Mozaffari, A. (2017), “Solving a bi-objective vehicle routing problem under uncertainty by a revised multi-choice goal programming approach”, International Journal of Industrial Engineering Computations, Vol. 8 No. 3, pp. 283-302.
Yu, B., Yang, Z.Z. and Yao, B.Z. (2011), “A hybrid algorithm for vehicle routing problem with time windows”, Expert Systems with Applications, Vol. 38, pp. 411-435.
Further reading
Applegate, D.L. and Bixby, R.E. (2006), “Travelling salesman problem a computational study”, Book Princeton Series in Applied Mathematics, Princeton University Press, Princeton, 8540, ISBN: 978-0- 691-12993-8.
Baker, B.M. and Ayechew, M.A. (2003), “A genetic algorithm for the vehicle routing problem”, Computers and Operations Research, Vol. 30 No. 5, pp. 787-800.
Jin, M., Liu, K. and Eksioglu, B. (2008), “A column generation approach for the split delivery vehicle routing problem”, Operations Research Letters, Vol. 36 No. 2, pp. 265-270.
Psaraftis, H.N. (1980), “A dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem”, Transportation Science, Vol. 14 No. 2, pp. 130-154.