Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.20 No.4 pp.629-636
DOI : https://doi.org/10.7232/iems.2021.20.4.629

Application of Meta-Heuristic Algorithms in Solving a Supply Chain Model

Anjali Chaudhary*, Dinesh Mavaluru
Department of Business Administration, College of Business and Administration, Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia
College of Computing and Informatics, Saudi Electronic University, Riyadh, Saudi Arabia
*Corresponding Author, E-mail: ARChaudhary@pnu.edu.sa
August 10, 2021 September 19, 2021 September 27, 2021

ABSTRACT


Over the last three decades, the integrated optimization approach to logistics systems has become one of the most important aspects of supply chain management optimization. This approach simultaneously examines the relationships between facility locations, supplier / customer allocation to facilities, transportation route structure, and inventory planning and control. One of the most important issues in logistics decisions is location-routing. In this case, the number and location of facilities, the size of the transport fleet, and the structure of the routes are determined according to the location and characteristics of suppliers and customers. In this paper, a mathematical model of the problem with consideration of product decay time constraints and solving with efficient meta-heuristic methods based on ant colony optimization (ACO) and particle swarm optimization (PSO) is presented. The comparison of the results of the two algorithms shows that the ant colony optimization (ACO) is faster in terms of convergence rate and the number of solution iterations is less than the particle swarm algorithm.



초록


    1. INTRODUCTION

    In most logistic environments, the managers must make decisions regarding the distribution centers and the allocation of customers to service areas, and these decisions are crucial considering that they affect the level of rendering services to the customers to conduct a transportation plan for providing services for the customers. The price of finding a location and routing is crucial since it affects the whole logistic system. Problems and defining the optimal quantity and the distribution centers (warehouses), besides, planning the vehicles and distribution routes are used in minimizing the total cost of the system.

    The fact that several customers, most mathematical models are used to solve such problems for location of the warehouses, can use the same route may increase the possibility of total demand exceeding the capacity of the tour. This indicates the necessity to unify the problem of location and routing. However, this dependence has not too been specified until 1970. The problems of locationrouting can be defined as the routing problem, in which the locations and the optimal number of warehouses are determined simultaneously with the plan for vehicles and distribution routes in order to minimize the total cost of the system. The research in this regard in comparison to the broad literature in the field of location-routing, mere location, routing problem, and other types are limited and three sub-problems can be stated as follows: 1. Facility location (LRP) the steps for resolving a location-routing problem, 2. Demand allocation, 3. Vehicle’s routing. Separate optimization of each of these problems can lead to a non-optimal decision. However, the combination of these three problems is impractical in terms of computation.

    2. LITERATURE REVIEW

    The dependence between location and routing problems was not specified up to 1970, and including the problem of routing in location seemed impractical. The research by Dwivedi et al. (2020), was the first effort for determining the vehicle in a single-product market, which can be considered as one cost that minimizes the total transportation and inventory cost.

    Goodarzian et al. (2021), developed a new inventory model for combining the costs of transportation and order return. This model minimized the cost of transportation and inventory by constantly determining the repeated location of the inventory order, the quantity of order, and the vehicle for transportation.

    Mokhtarzadeh et al.(2021), modeled the one-echelon location-routing problem with a limited capacity of transportation fleet, one. Ghiani and Improta (2000), designed a two-phase Tabu search for the metaheuristic algorithm. The one-echelon location-routing problem with the limited capacity of the transportation fleet, a new mathematical model on the basis of capacitated-strain routing problem.

    In Turkey, Alumur and Kara (2007), conducted research and used a new model for the location-routing problem to find an appropriate solution for the problem of hazardous wastes management. This model aimed at locating treatment centers, incineration centers, and routing the transportation of the hazardous waste to the treatment centers in order to minimize the total cost and the risk of transportation.

    Yu et al. (2010), proposed a simulated annealing algorithm to solve the location-routing problem with limited capacity. To solve and validate the proposed algorithm, the classic trial examples in the literature of the locationrouting problem were used. The results indicated that the suggested simulated annealing algorithm is better than other proposed algorithms in the literature. Besides suggesting new solutions, new assumptions were considered from the real world for the problem of location-routing.

    Ngueveu et al. (2010), introduced a cumulative capacitated vehicle routing, which aimed at minimizing the total distribution costs. Agrawal (2014), proposed a tripleobjective optimal model with the section of the arrival time of the vehicle to the customer. Ke and Feng (2013), suggested a two-step innovative method to resolve the problem of cumulative capacitated vehicle routing. Behnke et al. (2020), proposed a model of multi-objective location planning and tri-level allocation in a fuzzy state. Then, used an appropriate genetic algorithm to solve it.

    Agrawal (2014), studied the form of relationship between the suppliers of the raw materials and the company, plus, their relationship with one another (in case there is a relationship). By transforming the problem into a mathematical model, an analysis was obtained with three different scenarios. Marikanis et al. (2015), investigated a capacitated location-routing problem and a location-routing problem. The stochastic demands were solved using the improved particle swarm optimization algorithm. When compared with the results of other different algorithms, it was revealed that the particle swarm algorithm is an appropriate algorithm for location-routing problems.

    Fatehi Kivi et al. (2021), transformed a model of bilevel necessary materials supply problem into a singlelevel and tried to shorten the time of solving the problem. Furthermore, a location-routing problem with a different time window was proposed and it was optimized using the genetic algorithm. Nazari et al. (2018), optimized the problem of routing and vehicle by considering the assumption of a split delivery. To assess this problem, disparate benchmarks were used. Wang and Sheu (2019), optimized the problem of drone routing. An integer planning model was developed and the index and cost algorithm was used to solve it. Behnke et al. (2020), optimized the problem of routing vehicles by considering the reduction of environmental pollutions in a multigraph state. Therefore, the column generation method was used and samples with more than 100 customers in the approximate time of 90 seconds were optimized. Florio et al. (2021), proposed a branch-and-price algorithm for vehicle routing by considering the stochastic demands and probabilistic duration constraints, and travel fuzzy uncertainty. This problem was optimized in different confidence levels and the results were analyzed.

    3. MATHEMATICAL MODELING

    In this section, a linear integer model was suggested for the problem of location-routing. The required assumptions, parameters, and decision variables were provided for this problem:

    The conditions and assumptions include:

    • 1. Every customer can be allocated to more than one route. In other words, each demand node is viewed more than once, and more than one center supplies the distribution.

    • 2. The number of homogeneous distribution center must be selected from the distribution centers and the capacity of distribution centers are limited.

    • 3. All vehicles are the same and they all are limited in terms of both time and load capacity (transportation).

    • 4. Every vehicle starts from one distribution center, meets one collection of customers (receivers) in its route. Then, returns to the same load distribution centers.

    • 5. Multiple uses of vehicles in the working range of the vehicle (temporal limit) is possible.

    • 6. In the definite state, the objective function includes reduction of the total fixed cost (cost of establishment of distribution centers and cost of sending vehicles) and variable cost (transportation cost).

    In this section, first, to understand the problem, the parameters and variables of the model are described as follows.

    • L : Total Supply Points (Factory)

    • I : Total Points Candidate for Establishment of Distribution Centers

    • J : Total Receiving Points (Customers)

    • X l j       m a x : Maximum Volume of Products Transferred from the Factory I to Distribution Center i

    • X i j       m a x : Maximum Volume of Products Transferred from the Distribution Center i to Customer j

    • Dlj : Matrix of Distance from the Factory I to Distribution Center i

    • Dij : Matrix of Distance from the Distribution Center i to Customer j

    • Mi : Total Volume of Product Stored at Distribution Center i

    • Ui : Total Capacity of Distribution Center i

    • Uj : Total Capacity of Customer j

    • Mj : Total Volume of Product Stored at Customer j

    • Ci : Total Volume of Product Exported from Distribution Center i

    • Cj : Total Volume of Product Exported to Customer j

    • Tmax : Maximum Storage Time of Product

    • a : Cost of Transportation of Product per each Unit of Kilogram

    • Qi: Fixed Cost of Distribution Center i

    • I: Fixed Cost of Factory QI

    Definition of Variables of Problem

    • Xli : Quantity of Product Transferred from Factory I to Distribution Center i

    • Xij : Quantity of Product Transferred from Distribution Center i to customer j

    • tli : Time of Product Transferred from Factory I to Distribution Center i

    • tij : Time of Product Transferred from Distribution Center i to customer j

    Proposed Mathematical Model

    The following is the mathematical model of the problem:

    min z = i = 1 I ( j = 1 J   D i j X i j + Q i ) + l = 1 L ( i = 1 I D l i X l i + Q I ) + i = 1 I j = 1 J t i j + l = 1 L i = 1 I t l i
    (1)

    S.t:

    X i j X i j m a x ( i l , j J )
    (2)

    X l i X l i m a x ( i l , l L )
    (3)

    M j = i I = 1 X i j ( j J )
    (4)

    M i = l L = 1 X l i ( i l )
    (5)

    M j = U j ( j J )
    (6)

    M i = U i ( i l )
    (7)

    C I = i I = 1 X I i ( l L )
    (8)

    C i = j J = 1 X i j ( i l )
    (9)

    t i j T m a x   X i j 0 i I , j J
    (10)

    t l i T m a x   X l i 0 i I , l L
    (11)

    In the mathematical model of the problem, in relation (1), the objective is to minimize the cost of installation of the facilities, product transportation and distribution centers, and the time of product transportation.

    Equation (2) guarantees that the quantity of the transaction product from the distribution center must be less than its maximum authorized value.

    Equation (3) guarantees that the quantity of the transaction product from the factory must be less than its maximum authorized value.

    Equation (4) shows the quantity of the product imported to the customers, which were sent from all distribution centers.

    Equation (5) shows the quantity of the product imported to the distribution centers, which were sent from all factories.

    Equation (6) guarantees that the quantity of the product imported to customers is not higher than its capacity.

    Equation (7) guarantees that the quantity of the product imported to distribution centers is not higher than its capacity.

    Equation (8) shows the quantity of the product exported from the supply point (factory) j to all distribution centers.

    Equation (9) shows the quantity of the product exported from the distribution center i to all customers.

    Equations (10) and (11) guarantee the maintenance of products that decay.

    3.1 Proposed Method

    In the current paper, as all transportations are outsourced to the third-party logistics providers and they offer all-unit quantity discounts on transportation costs, transportation costs are the lowest when the age quantities of products are shipped between the stages of the supply chain. However, the total delivery time of the supply chain which is made up of the time devoted to producing and transporting products from manufacturers to customers through distributors often can be reduced if products are shipped immediately after they are produced at manufacturers. Therefore, there is a tradeoff between holding products until enough of them are accumulated to reduce transportation costs and shipping them immediately to reduce delivery time. Accordingly, since our proposed model consists of two objectives conflicting in nature, we have taken advantage of the classical methods of multiobjective optimization, namely Ant Colony Algorithm and Particle Swarm Algorithm methodology and desirability function approach to transform the two objective functions into a single one.

    4. DATA ANALYSIS & RESEARCH FINDINGS

    Using collective intelligence is a relatively new approach that is used in solving problems and it was inspired by the social behavior of insects and other animals. A variety of methods and techniques are inspired on the basis of ants and several studies are carried out in this regard. The multi-purpose optimization technique was the most successful of all, which is also known as ant colony optimization, and was developed based on the behavior of ants that were looking for food. Ant Colony Optimization These ants release a pheromone to the ground, which is suitable for routing. Ant colony optimization uses a mechanism similar to solving the optimization plan and specifies for other members of the colony.

    Kennedy and Eberhart first proposed the optimization swarm particle in 1995. This method was inspired by nature and it is based on iterative processes like other metaheuristic algorithms. The source of inspiration of this algorithm is the social and collective behavior of some animals such as the collective movement of birds and fish. In this algorithm, each bird or fish (i.e. particle) besides its simple individual behavior has a complex collective behavior as well, which is called collective intelligence.

    Description of Taguchi Method. The main body of knowledge pertinent to the science of quality was developed in England as designing tests and, in the US, as statistical quality control. When Japan started its reconstruction after World War II, it faced a shortage of raw materials, high-quality equipment, and proficient engineers. Then, it started the competition for manufacturing high-quality products and continually improving the quality. Dr. Genichi Taguchi was assigned to the task to develop a methodology for dealing with the problem of competition.

    Regulating the Parameters of the Proposed Algorithm. Regulating and allocating appropriate algorithms is considerably effective on the quality of the solution of metaheuristic algorithms. In the present research, the Taguchi method was employed to determine the appropriate level for each parameter. In accordance with this method, when the quantity of S problems is optimized and the solution is as small as possible, here, the objective is to find the quantity of parameters of ant and particle swarm algorithms. The test for resulting the parameters of the algorithm. The algorithms of ant and particle swarm were carried out in three levels.

    Taking into account the data of Tables 1 and 2, for the execution of tests, the respective problem was conducted in the small, medium, and large scales, three times for each as appropriate-L9(32), orthogonal arrays using 16 Minitab. By referring to the standard table of Taguchi arrays and the software design was selected for regulating the parameters of the algorithm.

    S/N was demonstrated for the ant and particle swarm algorithm. In Figures 1 and 2 the quantities of different levels of parameters in ratio

    The appropriate quantities of S/N parameters with respect to relation 1, ration of ant algorithm includes the pheromone evaporation rate of 0.000005, the population number of 20, and iteration number of 200. Furthermore, appropriate quantities for algorithms of particle swarm include individual intelligence coefficient of 6, collective intelligence coefficient of 3, population number of 40, and iteration number of 50.

    4.1 Numerical Results

    In this section, a hypothetical example from the industry of animal products is stated.

    Tables 3 and 4, show the distance between the point of supply (factory) and the total points candidate for the establishment of distribution centers and the distance between the candidate points for the establishment to the collection of points for receiving (customers). The distances are in kilometers. Besides, the maximum time for each route was considered to be 30 minutes.

    Tables 5 and 6 show the maximum quantity of product receivable by the customer and the maximum supply by the distribution centers. Besides, the quantity of product measurement is in kilogram.

    Tables 7 and 8 show results pertinent to transportation of products from points of distribution centers to collection of all customers and factory to points of distribution centers.

    When the quantity of parameters of the mathematical model is obtained, this problem was coded by MATLAB R2010a software using algorithms of the ant colony and swarm particle. Then, the results were extracted. The duration of solving this problem in the algorithm of the ant colony amounted to 10.64 seconds and in the algorithm of swarm particle amounted to 9.93 seconds. Therefore, the performance of both algorithms can be considered equal. However, in terms of convergence, these two algorithms have different performances. In Figures 1 and 2 the convergence of each of the algorithms is manifested.

    According to Figure 2, in the ant algorithm, the maximum improvement in solutions has occurred in 10 iterations. And the full convergence is obtained in 20 iterations. Afterward, there was no improvement in the solutions of these algorithms. While in Figure 3, in the par-ticle swarm algorithm, the improvement of solutions has occurred in 20 iterations and the full convergence is achieved in 30 iterations. Accordingly, it can be concluded that the ant colony algorithm can create the full convergence in the solutions in a fewer number of iterations. In other words, the convergence rate in the ant algorithm is stronger than particle swarm, which approves the efficiency of this algorithm.

    5. CONCLUSION

    In the present article, the location-routing problem was investigated considering the constraint of the decay time, which is an indication of the real and practical condition of this problem. After the description of the respective problem, its parameters and variables are defined and its mathematical model is developed.

    Therefore, the metaheuristic algorithms are employed to solve such problems NP-Hard since this problem is considered as problems. The model was coded by an ant colony optimization algorithm. Then, to assess the validity of the model, its results were compared to the results particle swarm optimization algorithm. The results of both algorithms were the same. However, the ant colony optimization algorithm is better than the particle swarm optimization algorithm with respect to its Iteration and the speed of convergence.

    The followings are suggestions for future studies:

    • - Development of the proposed model for multiproduct problems

    • - Considering the discussion of inventory in a problem

    • - Studying the problem in disparate periods of time

    ACKNOWLEDGMENT

    This research was funded by the Deanship of Scientific Research at Princess Nourah bint Abdulrahman University through the Fast-track Research Funding Program.

    Figure

    IEMS-20-4-629_F1.gif

    Comparison of the algorithms performance in integrated objective function.

    IEMS-20-4-629_F2.gif

    Convergence of ACO.

    IEMS-20-4-629_F3.gif

    Convergence of PSO

    Table

    Levels and quantities of ant algorithm in the Taguchi method

    Levels and quantities of particle swarm algorithm in taguchi method

    Distance between candidate points for establishment of distribution centers to the collection of all customers

    Distance between supply points (factory) to candidate points for establishment of distribution centers

    The maximum quantity of products that can be received by the customer

    Maximum supply of distribution centers

    Results pertinent to transportation of products from points of distribution centers to collection of all customers

    Results pertinent to transportation of products from supply point (factory) to points of distribution centers

    REFERENCES

    1. Agrawal, A. (2014), Managing raw material in supply chains, European Journal of Operational Research, 239(3), 685-698.
    2. Alumur, S. and Kara, B. Y. (2007), A new model for the hazardous waste location-routing problem, Computers & Operations Research, 34(5), 1406-1423.
    3. Behnke, M. , Kirschstein, T. , and Bierwirth, C. (2020), A column generation approach for an emission-oriented vehicle routing problem on a multigraph, European Journal of Operational Research, 288(3), 794-809.
    4. Dwivedi, A. , Jha, A. , Prajapati, D. , Sreenu, N. , and Pratap, S. (2020), Meta-heuristic algorithms for solving the sustainable agro-food grain supply chain network design problem, Modern Supply Chain Research and Applications, 2(3), 161-177.
    5. Fatehi Kivi, A. , Mehdizadeh, E. , Tavakkoli-Moghaddam, R. , and Najafi, S. E. (2021), Solving a multi-item supply chain network problem by three metaheuristic algorithms, Journal of Optimization in Industrial Engineering, 14(2), 145-151.
    6. Florio, A. M. , Hartl, R. F. , Minner, S. , and Salazar- González, J. J. (2021), A branch-and-price algorithm for the vehicle routing problem with stochastic demands and probabilistic duration constraints, Transportation Science, 55(1), 122-138.
    7. Ghiani, G. and Improta, G. (2000), An efficient transformation ofthe generalized vehicle routing problem, European Journal of Operational Research, 122(1), 11-17.
    8. Goodarzian, F. , Kumar, V. , and Abraham, A. (2021), Hybrid meta-heuristic algorithms for a supply chain network considering different carbon emission regulations using big data characteristics, Soft Computing, 25(11), 7527-7557.
    9. Ke, L. and Feng, Z. (2013), A two-phase metaheuristic for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 40(2), 633- 638.
    10. Marikanis, Y. (2015), An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands, Applied Soft Computing, 37, 680-701.
    11. Mokhtarzadeh, M. , Tavakkoli-Moghaddam, R. , Triki, C. , and Rahimi, Y. (2021), A hybrid of clustering and meta-heuristic algorithms to solve a p-mobile hub location–allocation problem with the depreciation cost of hub facilities, Engineering Applications of Artificial Intelligence, 98, 104121.
    12. Nazari, M. , Oroojlooy, A. , Snyder, L. V. , and Takáč, M. (2018), Reinforcement learning for solving the vehicle routing problem, Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada.
    13. Ngueveu, S. U. , Prins, C. , and Calvo, R. W. (2010), An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers & Operations Research, 37(11), 1877-1885.
    14. Wang, Z. and Sheu, J. B. (2019), Vehicle routing problem with drones, Transportation Research Part B: Methodological, 122, 350-364.
    15. Yu, V. F. , Lin, S. W. , Lee, W. , and Ting, C. J. (2010), A simulated annealing heuristic for the capacitated location- routing problem, Computers and Industrial Engineering, 58(2), 288-299.
    Do not open for a day Close