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.2 pp.315-321
DOI : https://doi.org/10.7232/iems.2021.20.2.315

A Mathematical Model of the Vehicles Routing Problem of Perishable Materials Using Genetic Algorithm

Anastasia A. Kurilova*
Togliatti State University, Russia
*Corresponding Author, E-mail: kurilovaaa@mail.ru. anas.kurilova@mail.ru
March 12, 2021 April 12, 2021 May 14, 2021

ABSTRACT


Transportation is one of the major and important sectors of the economy of any country and its related costs are among the most important costs that constitute the cost of final products. Nowadays, as the business market becomes more competitive, organizations are required to reduce some costs, including transportation costs in their distribution systems and supply chain, in order to reduce the final selling price of their products. Moreover, due to the growing trend of urbanization and industrialization, the need for systems that can perform the transportation of goods and people as efficiently as possible has been considered more than ever by organizations. Meanwhile, due to the reduction of fuel reserves in the world and the growing need to optimize energy consumption in all organizations, transportation planning to reduce energy consumption and costs, as well as reducing pollution, which in turn reduces treatment costs and social problems, is extremely important. Therefore, in this study, it is assessed to present a mathematical model to examine the costs incurred in this area and optimize these costs to take an effective step in this regard.



초록


    1. INTRODUCTION

    While in reality a wide variety of goods fall in the category of perishables, most existing models in the inventory control literature have been developed for nonperishable products. Indeed, controlling and maintaining the stock of perishable goods is a major challenge for many businesses and organizations. Since letting goods spoil will cause massive economic losses, businesses and organizations that that store or trade in such products need to utilize the inventory management concepts and principles and adopt suitable inventory policies for perishable goods. As a result, a large number of researchers have shown interest in this subject (Tirkolaee et al., 2020;Goli et al., 2019a).

    Integration and coordination of distributors of perishable goods in the form of joint investment in a common warehouse could be a good strategy because ideally it can turn the supply chain of perishable goods to a supply chain of ordinary goods. Integration of distributors can benefit inventory holding as well as service delivery. In the case of inventory, this integration can create one stock of inventory throughout the distribution network, thereby reducing total inventory costs while also improving service level. In this integration, inventory holding in the upper components of the supply chain is managed with a level of risk sharing so that good can be distributed when needed. In this system, each distributor can check the inventory of other distributors. According to their contract, vendors are obliged to exchange products with an agreed fee under certain conditions. This system improves the service level of each distributor and reduces the size of inventory required by the entire system (Goli et al., 2019b;Alinaghian and Goli, 2017;Daryakenari and Nasiri, 2021).

    Location routing is a branch of research in the field of location that also takes into account the underlying issues related to vehicle routing. While there have been many studies on all aspects of location problem, the subject of location routing has not been given the same level of attention. In the present study, we have modeled and studied the transportation of perishable products by combining it with another concept called combined transport, which is a new subject in the field of transportation.

    In the rest of this article, section 2 reviews the previous works on the subject, section 3 presents the proposed mathematical model, section 4 presents the genetic algorithm designed to solve the model, section 5 presents the numerical results, and finally section 6 concludes the article.

    In a study carried out by Thomas and Griffin (1996), they modeled the transport of dairy products, including the routing problem for collecting milk from farms and delivering it to processing plants. In this study, it was assumed that the demand of plants may change from week to week, but the amount of milk collected from farms remains at the same level that is specified in the contract. They showed that while the routes are decided by the average demand of processing plants, the detailed information about demand could help achieve significant time saving. They developed a two-step approach based on the neighborhood search, where the first step was to solve the transportation problem and the second step meant to ensure optimal allocation to processing plants. They also reported that additional time-based clustering analyses would prolong the solution time.

    In a study by Stevens (2015), it was stated that growing concerns about energy consumption, greenhouse gas emissions as well as food waste require an advanced model for food logistics management. The main purpose of their research was to analyze the logistics of perishable products, energy consumption (CO emission) in these transportation operations, and logistics costs in the location- inventory problem with multiple suppliers and customers and ultimately develop a decision support model with these concerns taken into account. The proposed model allows the user to analyze the benefits of horizontal cooperation in IRP while considering several key factors such as greenhouse gas emissions, driving time, total routing cost (fuel cost and wage), inventory, and product loss under uncertain demand.

    According to Hwang and Sohn (1983) real-time distribution programs encounter many problems when implemented and solved on a large scale. Usually these problems are related to limited capacity of vehicles and the considered time windows. To address this issue, they developed an optimization system for combining such programs with ERP without imposing high costs on the current program.

    Kulkarni and Bhave (1985) studied the problem of location routing with multiple trips and cumulative capacity in its single-vehicle mode. In this problem, it is assumed that during a crisis, a single vehicle can make several successful trips to cover a series of affected areas, thus minimizing the total time of service delivery to these areas. They proposed a mixed-integer linear program for solving this model for 20 sites, and then developed an exact algorithm for solving larger problems in the presence of resource constraints with the goal of achieving the shortest time between two nodes. The results showed that the described problem could be solved with the Bellman- Ford algorithm.

    In a study by Laporte (1992) on the vehicle routing problem (VRP), they also discussed the VRP for the delivery of perishable foods with ordinary and refrigerated vehicles. They assumed that the location and size of orders placed by customers are known and the maximum capacity, delivery times, and the number of available vehicles of both types are predetermined. Based on these assumptions, they developed a nonlinear model and a heuristic algorithm for maximizing customer satisfaction, which was defined as a function of the freshness of delivered products.

    Gavish and Srikanth (1986) studied the process of transition to sustainable supply chain management as a main goal of modern logistics, in addition to minimizing traditional costs, product loss, and environmental impacts of the supply chain. Traditional costs of the supply chain include fixed costs due to product distribution among nodes, unconstrained inventory holding, and definite demand in inventory routing problem.

    Hu et al. (2018) developed a model for optimizing inventory routing decisions for perishable products. In this study, a local search algorithm was developed to optimize routing and inventory decisions simultaneously. Numerical results showed that the proposed heuristic method performs better than sequential methods.

    In a study by Yaghoubi and Akrami (2019), they proposed a new mathematical model for location-routing problem for perishable products. In this study, perishable products were assumed a set of raw materials sent by suppliers to manufacturers. Particle swarm optimization (PSO) and ant colony optimization (ACO) algorithms were used to optimize this problem. The results showed that ACO performed significantly better than PSO in solving this problem (Abdollahbeigi, 2021;Gaikwad, 2021).

    Yavari et al. (2020) integrated the location, routing, and inventory decisions for perishable products in one mathematical model. The product was a mixed-integer nonlinear programming model, which, because of high complexity, had to be solved with meta-heuristic methods. The results showed that the genetic algorithm could solve the designed problem with an average error of 2%.

    Dai et al. (2020) developed a heuristic method for solving the inventory-routing problem of perishable products. In this study, which used the vendor-managed inventory (VMI) system, the Clarke-Wright algorithm was expanded and combined with the cuckoo search algorithm. The computational results showed the effectiveness of the used hybrid method.

    Liu et al. (2021) investigated the impact of demand uncertainty on the production-distribution of perishable products. This study presented a mathematical model with the objective function of reducing total cost and a heuristic method for solve this model. The results showed that the reduction of production and distribution capacity leads to encountering shortages in the entire chain network.

    2. METHODOLOGY

    Considering the subject of interest, modeling should be done with due attention to all aspects of the process and all constraints that may play a role in the real world condition to make sure that the resulting model is practical. For this purpose, it is also necessary to examine and model the costs concerning the subject and measures of product deterioration. After these examinations, all of these issues should be considered in the formulation of the mathematical model.

    2.1 Model Assumptions

    • 1. The mathematical model is single-period.

    • 2. The cost and time of transportation depend on the distance.

    • 3. Each customer has a certain delivery window.

    • 4. The freshness level that is considered acceptable by customers is known.

    • 5. Customer dissatisfaction is penalized by a discount on the purchase price.

    • 6. Vehicle fleet is homogeneous.

    2.2 Indices and Sets

    • NL : Set of vehicles

    • K : Index of available vehicles

    • N : Set of nodes

    • I, j : Index of nodes

    2.3 Parameters

    • C : Vehicle capacity

    • Si : Customer service time i

    • CTi,j : Cost of transport between customer i and customerj

    • Ti,j : Time of transport between customer i and customer j

    • ai : Start time of the time window of customer i

    • bi : End time of the time window of customer i

    • di : Demand of customer i

    • SLi : Minimum freshness level acceptable to customer i

    • SCi : Cost due to customer dissatisfaction on account of receiving a product with a low freshness level

    • Mi,j : The largest value among the sum of end times and start times, and the time of transport from customer i to customer j

    • P : A large number

    2.4 Variables

    • FRi : Freshness level of the product upon delivery to customer i

    • wki : Start time of service delivery by vehicle k to customer i

    • Xkij : Equals 1 if vehicle k travels from node i to node j

    M I N z = i j k X k i j × c T i j + i F R k × s c i
    (1)

    j = 1 n k = 1 m X k i j = 1 i
    (2)

    j = 1 n X k 0 j = 1 A k
    (3)

    i n X k i j i n X k , j , i = 0 k , j
    (4)

    i n X k , i , n + 1 = 1 k
    (5)

    W k j W k i + S i + t i j m i j ( 1 X k i j ) k , i , j
    (6)

    a i × j n X k , i , j W k i b i × j n X k i j k , i
    (7)

    i n j N l d i X k i j C k
    (8)

    F R i W k 0 + s l i W k i + p ( 1 j X k i j ) s l i k , i
    (9)

    W k 0 + S l i W k i 0 k , i , j = 0
    (10)

    2.5 Mathematical Model

    The objective function of the model consists of two components: the first component minimizes the transport costs and the second component minimizes the cost resulting from customer dissatisfaction due to receiving products with unacceptable freshness level.

    Constraint 2 states that each customer must be visited exactly once.

    Constraints 3 to 5 state that no loop should be created between customers and the first node must be the supply depot.

    Constraints 6 and 7 define the time window for product delivery to customers.

    Constraint 8 defines the capacity of the vehicle.

    Constraint 9 defines how fresh product should be sent to customers.

    Constraint 10 guarantees that the products received by customers are fresh (not spoiled).

    2.6 Model Validation

    To test the validity of the proposed model, a smallscale numerical example was solved with the help of the operations research software GAMS. The numerical example used for this purpose has 3 points and three vehicles (K1, K2, and K3). The capacity of the vehicles was considered 100 units. The service time was assumed to follow a uniform distribution between 5 to 10 minutes. The time window was considered to be between 0 and 3 minutes, and demand was assumed to follow a uniform distribution between 10 and 15 units.

    Solving the problem in GAMS with the above inputs, the value of the objective function was calculated to Z=264 in 0.1 seconds

    In all meta-heuristic algorithms, it is necessary to first define how the solutions are structured. This structure is called solution representation. In this study, the solutions are in the form of a single-row matrix with N+2*V columns, where N is the number of customers and V is the number of vehicles. All vehicles must travel to at least one customer and each route starts at one node and ends at one node. Thus, the start and end nodes of each route must be specified. The following matrix is a solution of the problem with 10 customers, 3 vehicles and 3 nodes shown in Table 1.

    In this example, customers 1, 4 and 5 receive service from the first vehicle, which starts its route from node 1 and ends it at node 3 after serving the customers. The route of the second vehicle starts at node 3 and ends at node 2 after going through customers 2, 3, 7, 8 and 10. The route of the third vehicle starts from node 2, goes through customers 6 and 9 and ends at node 3. More specifically, the problem can be analyzed as shown in table 2.

    To obtain high-quality solutions, it is necessary to define an appropriate fitness measure for solutions. Here, this measure is the value of the objective function. In other words, each chromosome will be converted into its corresponding solution and placed in the objective function, and the chromosome of the solution with the highest objective function value will be chosen as the best chromosome. The proposed objective function seeks to minimize transportation costs as well as the cost due to customer dissatisfaction.

    M I N z = i j k X k i j × c T i j + i F R i × s c i
    (11)

    To describe how the crossover operator is used in the algorithm, we use the following two random chromosomes as parents. For crossover, we select two random cut points on the chromosomes and then swap the genes between these two cut points to produce a child.

    Then, starting from the beginning of the chromosome of the first parent, we copy any gene that is not among the genes of the first child at its own place and leave an empty space for any gene that is repeated. Then, we do the same for the second child. To fill the empty spaces in the first child, we start from the beginning of the chromosome of the second parent, copying any gene that is not present in the first child in its own place. We then do the same for the second child, copying in the empty spaces the genes of the first parent that are not present in the second child (starting from the beginning of the chromosome).

    The mutation operator of the proposed algorithm functions as follows:

    Here, we have used the Insert Mutation variant of the mutation operator, which is described below.

    • Step 1: ***

    • Step 2: Choose a route at random.

    • Step 3: Randomly select two customer-related genes from the route selected in the previous step.

    • Step 4: Move the second gene (or number) to the position immediately after the first gene, shifting the following genes by one cell.

    3. RESULTS AND DISCUSSION

    The generated data include the data related to the dimensions of the problem and other input variables such as the size of demand of each customer, customer service time, and the transport cost factor in the cost function. The method of generating these data is described below.

    In the proposed model, the dimensions of the problem depend on the number of customers (i) and the number of available vehicles (k). To investigate the performance of algorithms in solving problems of different dimensions, three groups of problems with small, medium and large dimensions were produced. These problems are given in Table 3.

    In this study, demand of each customer for each product in each period was a randomly generated value following a normal distribution with an average of 100 and a standard deviation of 50. The service time of each customer in each period was also generated randomly by following a uniform distribution in the interval (0, 5). Transport costs were generated based on the modified total discount model with five breakpoints.

    In problem instances, the coordinates of each customer were known and in the range [-100,100], the demand of each customer was in the range [1, 30], the average service time for each customer was known and in the range [1, 25], and the time window of every customer was known. In each problem, the maximum load of each vehicle and the coordinates of each warehouse were also known and predetermined.

    It was assumed that using each vehicle imposes a cost that depends on the distance traveled. In addition, each instance of tardy service delivery in a period imposes a cost (penalty) due to customer dissatisfaction. Giving greater weights to the objective function or the costs associated with vehicles leads to higher tendency to minimize costs or maximize customer satisfaction, respectively.

    Meta-heuristic algorithms tend to be very sensitive to their parameter settings. In other words, solutions of these algorithms very much depend on the values given to their parameters. In the following, the parameter values used in the algorithm to solve the proposed model are described. As mentioned, this model has been solved with a genetic algorithm. Table 4 shows the parameter values considered for this genetic algorithm. In this table, pm is the rate of mutation and pc is the rate of crossover.

    The table below shows the transport costs obtained for a small-scale problem with the given specifications.

    The meta-heuristic method was implemented in MATLAB software and executed on a computer with 2.10GHz CPU and 4GB RAM running on Windows 8 operating system. Each problem was run 10 times at random. In the following, we present the computational results of larger problems. Since GAMS was not able to solve large-scale problems, we used the proposed algorithm for this purpose. The purpose of this test was to determine how the proposed algorithm functions in different conditions.

    As shown in Figure 2, GAMS was able to solve only 6 problems. For these 6 problems, the solutions produced by the genetic algorithm are very close to the results of GAMS. For the larger problems, the genetic algorithm has been able to produce near-optimal solutions within reasonably short times. However, it takes a longer time for the genetic algorithm to solve smaller problems compared to GAMS. In Figure1, it can be seen that as the dimensions of the problem increases, the computation time of the genetic algorithm does not increase as sharply as that of GAMS. Therefore, for these larger problems, the genetic algorithm has been able to produce acceptable solutions in much shorter times compared to GAMS.

    Figure 2 also shows that for small problems, the objective function values and solution times are quite close, but for larger problems, the genetic algorithm has yielded higher objective function values than GAMS. This can be because in small-scale problems, the algorithm must cover a smaller search space to find a suitable solution.

    4. CONCLUSION

    Given the conditions of the supply chain considered in this study, the mathematical model developed for this chain minimizes the cost of transporting products to customers and the cost of customer dissatisfaction with the freshness of product. The constraints formulated in this model include the number of visits made by vehicles (one of the main assumptions of vehicle routing models), the time windows for delivering products to maintain their freshness, and the capacity of available vehicles. To validate the model, it was coded and executed for a number of small problems in GAMS. After validating the developed model, two groups of larger problems were designed and solved through approximation with a genetic algorithm and the results were compared with the solutions produced by GAMS. It was observed that the exact solution method was very efficient in solving small problems and produced optimal solutions in a good time. In addition, there were very small differences between the results of the genetic algorithm and the exact method for these problems. For medium-scale problems, the exact solution method gradually lost its time efficiency, needing increasingly longer times to produce an accurate solution. Finally, for large-scale problems, the exact solution could not generate a solution with optimal results within the defined time limit, whereas the genetic algorithm could efficiently explore the large solution space and reach good solutions within an acceptable time.

    Considering the work carried out in this area, future studies are recommended to consider the customer demand as probabilistic or fuzzy for expanding the model or Formulating the objective function with multiple objectives, including the minimization of product transport time. Moreover, developing other meta-heuristic algorithms for solving the model in order to evaluate their performance in this area and comparing the results with the results of the genetic algorithm can be other recommendations for future work.

    Figure

    IEMS-20-2-315_F1.gif

    Comparison of the objective function values produced by different solution methods Objective function value - Problem No.

    IEMS-20-2-315_F2.gif

    Comparison of the solution time of different solution methods Solution time - Problem No.

    Table

    Solution representation matrix

    Another form of the solution representation matrix

    Classification of problem instances

    Parameter values of the used genetic algorithm

    Transport costs obtained for a small-scale problem

    Parameters used in the algorithm evaluation process

    Comparison of the results of GAMS and genetic algorithm

    REFERENCES

    1. Abdollahbeigi, M. (2021), An overview of the paper recycling process in Iran, Journal of Chemical Reviews, 3(1), 1-19.
    2. Alinaghian, M. and Goli, A. (2017), Location, allocation and routing of temporary health centers in rural areas in crisis, solved by improved harmony search algorithm, International Journal of Computational Intelligence Systems, 10(1), 894-913.
    3. Dai, Z. , Gao, K. , and Giri, B. C. (2020), A hybrid heuristic algorithm for cyclic inventory-routing problem with perishable products in VMI supply chain, Expert Systems with Applications, 153, 113322.
    4. Daryakenari, F. A. and Nasiri, H. R. (2021), Management of urban energy system based on the use of train model in CHP systems, Journal of Engineering in Industrial Research, 2(3), 119-128.
    5. Gaikwad, M. V. (2021), Regioselective one-pot transformation of 2’-Hydroxy chalcones to 3,5-dipheny¬lisoxazole via dehydrogenation of dihydroisoxazolines using copper salt in DMF, Journal Appllied Organometallic Chemistry,1(2), 59-65.
    6. Gavish, B. and Srikanth, K. (1986), An optimal solution method for large-scale multiple traveling salesman problems, Operations Research, 34(5), 698-717.
    7. Goli, A. , Zare, H. K. , Tavakkoli-Moghaddam, R. , and Sadeghieh, A. (2019a), Application of robust optimization for a product portfolio problem using an invasive weed optimization algorithm, Numerical Algebra, Control & Optimization, 9(2), 187-200.
    8. Goli, A. , Zare, H. K. , Tavakkoli-Moghaddam, R. , and Sadeghieh, A. (2019b), Hybrid artificial intelligence and robust optimization for a multi-objective product portfolio problem case study: The dairy products industry, Computers & Industrial Engineering, 137, 106090.
    9. Hu, W. , Toriello, A. , and Dessouky, M. (2018), Integrated inventory routing and freight consolidation for perishable goods, European Journal of Operational Research, 271(2), 548-560.
    10. Hwang, H. and Sohn, K. (1983), Management of deteriorating inventory under inflation, Engineering Econnomics, 28(3), 191-204.
    11. Kulkarni, R. V. and Bhave, P. R. (1985), Integer programming formulations of vehicle routing problems, European Journal of Operational Research, 20(1), 58-67.
    12. Laporte, G. (1992), The vehicle routing problem an overview of exact and approximate algorithms, European Journal of Operational Research, 59(3), 345-358.
    13. Liu, P. , Hendalianpour, A. , Razmi, J. , and Sangari, M. S. (2021), A solution algorithm for integrated production-inventory-routing of perishable goods with transshipment and uncertain demand, Complex & Intelligent Systems, 316-327.
    14. Stevens, G. C. (2015), Integrating the supply chain, International Journal of Physical Distribution and Logistics Management, 19(8), 3-8.
    15. Thomas, D. J. and Griffin, P. M. (1996), Coordinated supply chain management, European Journal of Operations Research, 94(1), 1-15.
    16. Tirkolaee, E. B. , Goli, A. , Faridnia, A. , Soltani, M. , and Weber, G. W. (2020), Multi-objective optimization for the reliable pollution-routing problem with cross-dock selection using Pareto-based algorithms, Journal of Cleaner Production, 276, 122927.
    17. Yaghoubi, A. and Akrami, F. (2019), Proposing a new model for location-routing problem of perishable raw material suppliers with using meta-heuristic algorithms, Heliyon, 5(12), e03020.
    18. Yavari, M. , Enjavi, H. , and Geraeli, M. (2020), Demand management to cope with routes disruptions in location-inventory-routing problem for perishable products, Research in Transportation Business & Management, 37, 100552.
    Do not open for a day Close