Abstract
Cold supply chains produce and distribute goods that perish and deteriorate over time. To keep such goods fresh, the temperature must be constantly and continuously controlled, which in turn requires more fuel consumption. In this study, a mixed-integer optimization model is presented in which the goal is to minimize costs assuming that vehicle speed can be variable and considering the traffic congestion. In addition, it is assumed that the travel time and fuel consumption of each route depend not only on the distance travelled but also on the time of day when that route is travelled. In the proposed model, minimizing costs including the fixed cost, transportation, damage to new products, the refrigerator cost, carbon emissions, and penalties is considered. By solving the proposed model, the optimal route and travel time of vehicles are determined. A hybrid method based on Benders decomposition and PSO algorithms is applied to solve the proposed model. Finally, in addition to solving several test instances with different sizes to investigate the performance of the algorithm, a relatively comprehensive sensitivity analysis has been performed on the model. The obtained results indicate that the proposed algorithm can obtain the optimal solution for all small-size cases, and the average optimality gap ranges for medium sizes are from 0 to 0.12. For larger size cases, an optimal solution is not available, by the CPLEX within the given time limit. In most of these cases, the proposed algorithm introduces a better solution to the upper bound provided by CPLEX.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Today, due to the improvement in people's living standards, the demand for fresh goods and materials such as fresh food has increased. It is difficult to keep these products fresh at environmental temperature, hence cold supply chain logistics networks are needed to distribute these goods [31]. The specific characteristics of cold chain products make many effective factors to be considered in the transportation process [5]. Unfortunately, in cold chain logistics, as the temperature must be constantly controlled, energy consumption and consequently greenhouse gas emissions are high. The accumulation of greenhouse gases is one of the main causes of global warming caused by human activities [17]. Global warming and greenhouse fuel emissions are the century's most pressing problems. Since transportation is one of the most important factors in pollutant production in greenhouse gas emissions, researchers have continuously focused on vehicle routing (VRP) to maximize environmental impact [26]. About 20% of total global emissions are related to the carbon emission of the transportation industry [8].
To reduce the emissions of environmental pollution caused by transportation activities, cold chain logistics companies should also consider reducing the emission of harmful gases to provide better services in satisfying customers' demands. In cold chain transportation, the temperature is controlled continuously so that the quality and safety of materials and goods are not compromised. Unexpected temperature changes in cold chains can cause a loss of safety or quality of products, which ultimately leads to a loss of customer trust [18]. Therefore, cold chain routing requires more fuel to maintain the temperature than conventional routing. This, in turn, emits more greenhouse gases. Refrigerated trucks are estimated to emit 30% more greenhouse gases than other trucks [12]. Proper distribution channel planning can effectively improve sales efficiency and reduce energy consumption and carbon emissions. [1].
In recent years, cold chain logistics has developed rapidly. Numerous authors have proposed various improvements for vehicle routing problems (VRP) in green cold chain logistics, both in terms of modeling and solution methods, taking into account different hypotheses. Wang et al. [30] investigated the effect of carbon taxation on carbon emissions in a cold chain routing problem. A comprehensive mathematical optimization model has been proposed by Qin et al. [20] to coordinate cost reduction and carbon emissions and increase customer satisfaction in the cold chain VRP. Liu et al. [13] have proposed a cooperative distribution-green VRP, in which distribution companies can work together to reduce carbon taxes on the servicing of goods. Their results indicate that cooperative distribution is an effective rule to reduce total costs and carbon emissions. Wang and Wen [31] investigated the problem of low-carbon VRP in a real cold-chain logistics network. In the case study, the vehicles were heterogeneous and of course, two-layered, and customer service with a mixed time window was considered. The authors have proposed a comparative genetic-based algorithm method and evaluated the performance of the algorithm, which was done by some numerical benchmark tests. Li et al. [12] proposed a model for green cold VRP in which many factors involved in greenhouse gas (GHG) emissions were investigated.
While distance and cost reductions have a major impact on achieving low carbon emissions, there are other important factors in transportation, including vehicle speed, vehicle load, traffic congestion, uncertain demand, and time window [27]. Ma et al. [15], developed the stochastic model for the distribution of perishable goods based on uncertain customer demand. In the model presented by Sun et al. [25], a hard time window for service is considered to satisfy the customer and keep the products fresh. Bao and Zhang [2] examined the optimal path of a cold supply chain in joint distribution, they concluded that joint distribution works better in reducing distribution costs and pollution emission costs than segmentation distribution. Based on considering customer consent for cold chain distribution, Ren et al. [22], restricted the vehicle load, customer time window, and deterioration rate to build a cold chain VRP model with the least carbon emission as the objective inside the customer benefit time frame. Zhang et al. [33], under two different time constraints, the cold chain logistics distribution problem was considered. Based on the specs of high energy consumption when transporting cold chain goods, Wang et al. [29], developed a VRP model for cold chain logistics, taking into account product freshness and quality loss costs during the delivery process. Song et al. [24], proposed a metaheuristic algorithm for VRP with time windows, different types of vehicles, and different energy consumption in cold chain logistics. Tsang et al. [28], investigated food quality and arrival times windows and proposed a multi-temperature delivery planning system based on the Internet of Things.
Because of the particularity of cold chain logistics, the necessities for time are very strict. The freshness of the goods will be significantly reduced if they are kept in cold storage for a long time, hence it is significantly impacted by traffic congestion. According to relevant statistics, in the carbon emissions from transportation, traffic congestion leads to an increase in energy consumption, resulting in additional carbon emissions. The increase in carbon emissions due to road congestion is more than 20% [14]. Therefore, when the distribution for cold chain logistics is investigated, it is necessary to account for traffic congestion. Some researchers combined the traffic congestion with the actual road conditions in a cold VRP model [4]. Zhao et al. [34], geared toward the effect of traffic congestion on vehicle operating costs, the cold chain logistics vehicle route optimization model was incorporated with road congestion factors. The problem was then solved using an improved ant colony algorithm, genetic algorithms, and a two-stage optimization algorithm. A multi-objective nonlinear dynamic green vehicle routing problem of perishable products was presented by Talouki et al. [27], wherein green traffic conditions are considered. In this dynamic case, the randomness of the traffic congestion and considering the average speed for a vehicle have been the main hypotheses of the problem. The authors developed a robust model based on uncertainty demands and then proposed a heuristic approach to solve it. Despite some nonlinearity terms from the model, there was no effort to linearize them.
Chen et al. [4] studied the cold chain logistics of front warehouses and proposed a traffic congestion green vehicle routing problem with an approach of low-carbon based on the economy. To solve the model, a hybrid algorithm based on a simulated annealing and tempering algorithm was applied. It is worth mentioning that, the addressed model was nonlinear and the speed vehicle of each period was supposed to be constant. To study the vehicle routing optimization of urban cold chain logistics based on the real-time traffic of the Internet of Things, Huang and Pan [10] divided the road sections. Bai et al. [1] proposed a multi-objective nonlinear model for cold chain logistics by considering the complexity of the road network, the time-varying traffic conditions, and optimizing the distribution cost and carbon emission. The non-dominated Sorting Genetic Algorithm II algorithm was modified to solve the mathematical model. Cui et al. [5], studied the problem of optimizing the multi-distribution center cold chain route considering the traffic congestion index. Also, they analyzed the total cost of cold chain transport vehicles, the traffic congestion index, and the improved particle swarm algorithm introduced to solve the mathematical model. Zhang et al. [32] developed a model to optimize distribution routes in cold chain logistics by considering road impedance, to minimize the overall cost. An improved PSO algorithm is used to solve the model.
Traffic congestion in urban areas is a common phenomenon, and speeds usually decrease significantly in the morning and evening. This means that the travel time between two points depends not only on the travel distance but also on the speed of the vehicle and the time of day [21]. Some products, such as food and medicine, have a limited lifespan and must be transported as soon as possible. In this sense, time constraints and existing traffic conditions make the cost of this system prohibitive. Therefore, optimizing the vehicle speed for the supply of perishable products by considering traffic volume is necessary [27]. Pollution, time window, and traffic congestion are integral factors in the cold chain problem. According to the literature review, cold chain logistics is addressed with time window, with traffic congestion, or both time window and traffic congestion. However, the most important factor influencing pollution, time window, and traffic congestion, which is ignored in the literature, is the speed of vehicles. By adjusting the speed of the vehicle properly, it is possible to reduce the pollution of the vehicle, and customers can be served according to the traffic congestion on time.
Table 1 summarizes the findings of this study. Accordingly, it can be observed that there is no mathematical model for a Time-dependent cold chain with a time window to consider the variable speed in a different time-dependent congested urban area.
In this study, a new optimization model for the cold chain green VRP is presented by considering the traffic and variable speed of vehicles. The hypotheses considered in the proposed model are closer to reality and include consideration of periodic traffic and the variability of vehicle speed in each traffic period. In traffic congestion, there is usually an interval range of speed limits. In the proposed model, the fixed cost of vehicles, the losing quality cost, the keeping the product fresh cost, the penalty costs, the fuel consumption, and the emissions costs are minimized simultaneously. Since the speed of the vehicles is variable, so the model is nonlinear. To solve the model in large-scale tests, first, we try to linearize the model by presenting linearization techniques, and then a solution hybrid method based on Benders decomposition and Binary Particle Swarm Optimization (BPSO) algorithms is presented to solve the obtained mixed-integer problem. The main contributions of this work are as follows:
(1) Providing a nonlinear mixed-integer model for the cold chain VRP, which includes vehicle load constraints, traffic time congestion, variable speed, and time window simultaneously.
(2) Calculate the pollution caused by fuel consumption in a general and comprehensive way and try to minimize it.
(3) By using some linearization techniques, an equivalent mixed integer linear programming (MILP) model is delivered.
(4) Developing the hybrid method (based on Benders decomposition and BPSO algorithms) for solving the linearized model.
(5) Computational analyses of the model to evaluate the performance of the hybrid method and some sensitive analysis to verify the effect of some factors of the model are conducted.
The organization of this research paper is described in this paragraph. Section 2 is assigned to the definition and explanation of the problem and then the proposed model will be stated. Section 3 is dedicated to the solution method for the proposed model so that firstly the linearization part of the model will be presented and then the hybrid Benders Decomposition and PSO method will be adopted for solving the linearized model. In Sect. 4, computational results are presented to show the efficiency of the model and solution method. Finally, in the final section, conclusions and future suggestions are stated.
2 Problem formulation
In this section, the green VRP in a cold chain considering traffic congestion is described. For this purpose, first, a general description of the problem is given, then how to calculate the travel time, formulate the problem, and calculate the relevant costs that exist in the target function are described.
2.1 Problem description and formulation
A complete network with the main depot and a set of customers I (with indexes I, j) with deterministic demands is considered for the problem of cold chain time-dependent green VRP. The demand of the customers must be met by the number (at most m) of homogeneous refrigerated vehicles with limited capacity in a soft time window. No more than one vehicle can serve a customer. If the vehicle serves the customer outside the time window, then a penalty must be paid for this delayed or early arrival. The central depot is indicated by index 0. Each vehicle must start its journey from the depot and return to it after serving the visited customers. The set including customers and depot is shown with \(I_{0} = \{ 0\} \cup I\). The duration traveled time by each vehicle (including travel time and service) cannot exceed the specified time \(T_{\max }\) (in minutes or hours) that indicates the duration time of the service activity. For the time windows and service time at the node \(i \in I\) the notations \(\left[ {L_{i} ,U_{i} } \right]\) and \(s_{i}\) are applied respectively. Stopping at each node involves spending time. These stops are for customer service, unloading, or waiting if the customer node arrives early. The distance from the node \(i \in I_{0}\) to node \(j \in I_{0}\) is denoted by \(d_{ij}\). Since traffic is an unavoidable phenomenon, the speed of the vehicle will not be constant during the day and it will inevitably have to move at different speeds level at different times of the day. Furthermore, each arc has its speed limitations. So, in addition, to consider the vehicle speed as a variable, the restrictions on the speed of vehicles during the day are taken into account. In this paper similar to Hooshmand and MirHassani [9], three planning horizon periods are considered for traffic hours; i.e., morning traffic peak, free flow, and evening traffic peak periods. In each period there are different permissible speed levels. The first and third periods are for the peak hours of morning and evening traffic, in which the speed is relatively low. In the second period, which is in the middle of the day, the traffic congestion is lower and the speed can be relatively high.
In Fig. 1. the planning horizon time for any arc \((i,j)\) is denoted by \(\left[ {0,T_{\max } } \right]\) and \(a_{1}\) and \(a_{2}\) with \(0 < a_{1} < a_{2} < T_{\max }\) are the breakpoints of \(\left[ {0,T_{\max } } \right]\).
different speed levels on three planning horizon periods for the arc \((i,j)\)
It should be noted that the departure time of vehicles from the depot may start from a non-zero time. This is because, given the existence of early and late service penalties, it makes sense for the vehicle to have a non-zero travel time. The main assumptions of the optimization model are as follows:
1. There is a main depot and each vehicle must start its journey from the depot and return to it after serving the customers.
2. There are a certain number of homogeneous refrigerated vehicles with limited capacity.
3. The rate of perishability of products in a closed refrigerator is different from an open refrigerator.
4. The departure time of vehicles from the depot, as well as the time of their entry and exit to the customer points is variable. Also, the duration traveled time by each vehicle (including travel time and service) cannot exceed the specified time.
5. There is a soft time window for each customer. If the vehicle serves the customer outside the time window, then a penalty must be paid for this delayed or early arrival.
6. Three planning horizon periods are considered for traffic hours; i.e., morning traffic peak, free flow, and evening traffic peak periods.
7. The vehicle speed in each traffic period is variable and has a minimum and maximum limit for speed in each traffic period.
8. The cost of fuel consumption and the cost of pollution are calculated and considered separately.
To present the proposed model, first, the symbols used in it are introduced:
The Indexes.
\(I\) | The set of Customers \(I = \left\{ {1,2,...,n} \right\}\) with the indexes i, j |
\(\left\{ 0 \right\}\) | The node corresponding to the depot |
\(I_{0}\) | A set of nodes corresponding to customers and depot \(I_{0} = I \cup \{ 0\}\) |
\(A\) | The set of all arcs \((i,j)\) which \(i,j \in I_{0}\) |
\(K\) | The set of vehicles \(K = \left\{ {1,2, \ldots ,m} \right\}\) with the index \(k\) |
\(P\) | The set of periods \(P = \left\{ {1,2,3} \right\}\) with the index \(p\) |
Parameters and notations
\(q_{i}\) | The amount of demand from customer \(i\) |
\(Q\) | Capacity for each vehicle |
\(d_{ij}\) | distance on arc \((i,j)\) |
\(T_{\max }\) | Duration of availability of each vehicle during the day |
\(s_{i}\) | The customer service time \(i \in I\) which is equal to the amount of demand divided by the unloading speed |
\(\left[ {L_{i} ,U_{i} } \right]\) | The acceptable time window for servicing the customer \(i \in I\) |
\(\left[ {0,a_{1} } \right)\) | Morning traffic time interval |
\(\left[ {a_{1} ,a_{2} } \right)\) | In the middle of the day when the speed is faster |
\(\left[ {a_{2} ,T_{\max } } \right]\) | Evening traffic time interval |
\(v_{1} ,\,v_{2} ,\,v_{3}\) | Vehicle speed in 3 time periods |
\(\partial_{1}\) | The rate of the perishability of products in the closed refrigerator when the vehicle is moving |
\(\partial_{2}\) | The rate of the perishability of products in the opened refrigerator when the vehicle is stopped |
\(\alpha_{1}\) | The fuel consumption of the stopping vehicle per unit of time |
\(c_{ij}\) | Transportation cost of the vehicle from point i to point j |
\(M\) | The Big number |
\(F_{1}\) | Fixed cost of using the vehicle |
\(F_{2}\) | The damage cost unit of products for a vehicle in the cold supply chain |
\(F_{3}\) | The refrigerating cost unit of products during the path for a vehicle |
\(F_{4}\) | The Keeping fresh cost unit of products during the unloading of a vehicle |
\(F_{5}\) | The penalty cost unit for vehicle acceleration |
\(F_{6}\) | The penalty cost unit for vehicle delay |
\(F_{7}\) | Fuel cost unit |
\(E_{R}\) | The unit of combining fuel consumption and pollution emission costs |
Variables: | |
\(x_{ij}^{k}\) | The binary variable equals 1 if a vehicle travels on an arc \(\left( {i,j} \right) \in A\), and 0 otherwise |
\(w_{ij}^{k}\) | The nonnegative variable indicates the volume of the load carried by the vehicle travels on an arc \(\left( {i,j} \right) \in A\) |
\(v_{ij}^{pk}\) | Nonnegative variable speeds of the vehicle \(k\) on the arc \(\left( {i,j} \right) \in A\) regarding the period \(p\) |
\(t_{ij}^{pk}\) | The variable travel time of the vehicle \(k\) regarding variable speed \(v_{ij}^{p}\) on the arc \(\left( {i,j} \right) \in A\) |
\(z_{ij}^{pk}\) | The variable covered the distance with speed \(v_{ij}^{pk}\) is associated with a period \(p\) via vehicle \(k\) on the arc \(\left( {i,j} \right) \in A\) |
\(\delta_{ij}^{1k} ,\delta_{ij}^{2k}\) | The binary variable is associated with the period \(p = 1,2\) and it means that if \(\delta_{ij}^{p} = 1\), then \(z_{ij}^{p + 1} \ge 0\) |
\(\tau_{i}^{k}\) | The nonnegative variable service start time of the vehicle \(k\) at a node \(i \in N\) |
\(\tau_{i0}^{{k^{\prime}}}\) | The nonnegative variable indicates the return time of the vehicle \(k\) from the node \(i \in N\) to the node depot |
According to the explanations given, the problem model is expressed as:
Function (1) is the objective function of the problem, which includes fixed use costs of the vehicles, quality loss costs of products, keeping products fresh costs, energy costs, pollution emission costs, and transportation costs. Equality (2) shows that each customer is serviced by a vehicle. Constraint (3) states that the number of vehicles entering a node must be the same as the number of vehicles leaving that node. Inequality (4) indicates the maximum number of active vehicles in the network that starts from the depot. Constraint (5) shows that each vehicle can only start moving from the depot only once. The sixth constraint is about the total distance traveled by the vehicle, in different traffic periods on the arc (i, j). And the seventh constraint shows the travel distance passed by the vehicle, in different traffic periods. Inequality (8) indicates the minimum and maximum speed allowed in each time traffic period. Constraints (9)–(16) specify the time spent in each period to travel the distance of an arc (i, j). Relation (17) indicates the arrival time of vehicle k from customer node i to customer node j in the network, and relation (18) determines the arrival time of vehicle k from the depot to customer node j in the network. Constraint (19) indicates the maximum travel time allowed on an arc. Constraint (20) indicates the return time of the vehicle to the depot. Inequality (21) indicates the maximum admissible time for the return of the vehicle to the depot. The hard period is demonstrated by constraint (22). Constraints (23)–(25) indicate that customer demand will be met. Constraints (26) and (27) specify the sign of the variables.
2.2 The objective function costs
In the presented model, 7 types of costs are considered. These costs are divided into 3 separate categories. Logistics costs (the fixed and transportation cost and penalty), refrigerator and refrigeration costs (quality to loss, keeping fresh cost), fuel and pollution emissions costs (Energy cost).
1. The fixed cost of vehicles: A fixed cost can be considered the cost of buying vehicles or renting them also the depreciation cost, and the drivers’ salary which has been shown by \(C_{1}\).
The above formula assumes that if a vehicle starts moving from the depot, a fixed cost must be paid.
2. Transportation costs directly affect variable costs, such as labor costs and fuel consumption costs. Distance traveled plays an important role in determining shipping costs. The transportation cost of the products is considered as follows:
3. The quality loss cost: Over time, products that need a cold environment lose their quality, even if it is stored in the refrigerator and maintained at the proper temperature. There are two general modes for products before they reach their final destination. The first condition is when the refrigerator door is closed and the vehicle is moving; in this case, the degree of quality is specified as follows.
Another situation in which products may lose their quality is when the vehicle stops to unload and the truck's refrigerator door opens. In this case, the cost of losing product quality is considered as follows:
As a result, the total cost of losing product quality is estimated by \(C_{3} = C_{3}^{\prime } + C_{3}^{\prime \prime }\).
4. The cost of keeping fresh: This cost is related to the refrigeration of products by refrigerators. It depends on how long the products stay in the refrigerator, while the vehicle is moving, and when they are unloaded, which varies depending on the type of refrigerator.
In which \(\hat{t}_{ij}^{pk} = t_{ij}^{pk} + \max \{ L_{i} - \tau_{i}^{k} ,0\}\).
5. Penalty: In cold chain logistics, the condition of the product when received from the customer is very important. If the vehicles arrive too early, they have to wait until customers start receiving the products. The product's condition may deteriorate in the meantime. If the vehicle arrives too late, customers may encounter replenishment and sales problems. Therefore, a penalty will be imposed if the vehicle arrives outside of the customer's time window [13]. The cost of the late or early arrival of the vehicle to customer nodes is expressed as follows:
6. Energy cost: To calculate the energy cost, some preliminary is required, which are stated below.
Calculation of the fuel consumption and pollution In this section, based on reference [7] calculation of the fuel consumption and pollution rate is presented. Since the amount of pollution is directly related to fuel consumption, calculating emissions is done after calculating fuel consumption. The preeminent model in the literature for calculating emissions takes into account other more precise parameters of the vehicles such as the engine friction coefficient, engine speed, and the speed of the moving vehicle. Dukkanci et al. [7] used a comprehensive modal emission model (CMEM) to calculate emissions. In this model, we tried to take into account all the factors that influence fuel consumption and emissions. To present and display the CMEM model, it is necessary to define the following symbols:
\(\xi\) | The fuel-to-air mass ratio |
\(\eta\) | The efficiency parameter for diesel engines |
\(\kappa\) | The heating value of a typical diesel fuel |
\(n_{tf}\) | The efficiency of the vehicle drive train is related to the overall efficiency of all engine transmission components to the wheels |
\(p_{acc}\) | The engine power demand is related to engine losses and the performance of vehicle accessories such as the use of air conditioning |
\(p_{tract}\) | The total tensile power required (in kW) |
\(\omega\) | Weight of vehicle |
\(a\) | The instantaneous acceleration |
\(S\) | The frontal surface area (in m2) |
\(g\) | The gravitational constant (in m/s2) |
\(\theta\) | The road angle |
\(C_{d}\) | The coefficient of aerodynamic drag |
\(C_{r}\) | The coefficient of rolling resistance |
\(\rho\) | The air density (in kg/m3) |
\(\psi\) | The conversion factor of fuel |
\(V\) | The engine displacement (in L) |
\(K\) | The engine friction factor |
\(\Upsilon\) | The engine speed |
It can be said that the main measure of CMEM is fuel consumption. So the fuel consumption per cycle is almost a linear function of the work output per cycle for the power level of less than two-thirds of the power at open throttle. This is directly related to the engine power demand (\(p\)) and engine speed (\(\Upsilon\)). According to the symbols used and based on [6], the basic fuel consumption module is introduced as follows:
\(F_{r} = \xi {{\left( {K\Upsilon V + \frac{P}{\eta }} \right)} \mathord{\left/ {\vphantom {{\left( {K\Upsilon V + \frac{P}{\eta }} \right)} \kappa }} \right. \kern-0pt} \kappa }\) in which, \(p = {{p_{tract} } \mathord{\left/ {\vphantom {{p_{tract} } {n_{tf} }}} \right. \kern-0pt} {n_{tf} }} + p_{acc}\) and \(p_{tract}\) where \(p_{tract}\) is obtained from the following relationship:
Now the new parameters are defined to simplify the above formula of \(F_{r}\)(in L). It is assumed that the vehicle with a speed \(v\) travels a distance of \(d\) units (in meters), and \(\lambda = {\zeta \mathord{\left/ {\vphantom {\zeta {\kappa \psi }}} \right. \kern-0pt} {\kappa \psi }}\), \(\gamma = {1 \mathord{\left/ {\vphantom {1 {1000n_{tf} \eta }}} \right. \kern-0pt} {1000n_{tf} \eta }}\), \(\alpha = a + g\sin \theta + gC_{r} \cos \theta\), \(\beta = 0.5C_{d} \rho S\), then:
The above function \(F_{r}\) is a double differentiable function in terms of \(v\) and also has a mean point \(v\) according to the values \(K\). Therefore, if the speed of the vehicle increases to an acceptable level, fuel consumption will decrease, and if it exceeds this value, it will increase fuel consumption. Now, the energy emissions cost is defined as:
The cost of pollution emissions is as:
Some nonlinear expressions exist in the objective functions and constraints (7). In the next section, firstly, some linearization techniques are applied to linearize the model, and then the solution procedure will be described.
3 Solution method
The proposed model is nonlinear and also belongs to NP-hard problems that cannot be solved by exact methods. Below we first try to use some linearization techniques to linearize \(P_{1}\). The purpose of this work is to prepare the structure of the problem in a form suitable for the application of Bender's solution method. Then, the Benders decomposition algorithm and BPSO are combined to obtain the optimal or near-optimal solution. This method can be applied to other models with the same structure. The calculation results obtained in Sect. 5 confirm the superiority of this method over other methods in terms of the quality of the solution in the appropriate time.
3.1 Linearization phase
This section deals with the linearization of the model. In the objective function and the expressions related to the costs of quality loss, keeping fresh the products, the pollution emissions, and the penalties, as well as the constraint (7), exist non-linear terms.
Without loss of generality, the speed of the vehicle can be considered discretely [7], and the linearization procedure is applied based on this hypothesis. Among all the different methods that exist for linearizing expressions containing integer variables, it can be said that the use of binary variables is the most common. There are two important widely used ways to represent a discrete variable based on binary variables. In one of the methods, for each possible value that the discrete variable can take, a binary variable is defined and a constraint is added to the problem. And only one of these binary variables is allowed to take the value of 1. The problem with this method is increasing the number of binary variables. The second method is to display integers in base 2. For the variable \(v_{ij}^{pk}\) that is considered as discrete, finite sets with \(S_{ij}^{pk} = \left\{ {1,2,3,...r,..} \right\}\) which \(r \in R\), for speed levels are defined to correspond to a fixed value,\(v_{ijr}^{pk}\), i.e., \(v_{ij}^{pk} \in \left\{ {v_{ij1}^{pk} ,v_{ij2}^{pk} ,...,v_{ijr}^{pk} ,...} \right\}\). If \(\Omega\) be the smallest number (\(\Omega = \left[ {\frac{{\ln v_{iju}^{pk} }}{\ln 2}} \right] + 1\)) that applies to the relation \(v_{iju}^{pk} \le 2^{\Omega }\), then \(v_{ij}^{pk}\) can be written as \(v_{ij}^{pk} = \sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } \Psi_{ij\theta }^{pk} }\) wherein \(\Psi_{ij\theta }^{pk}\) are binary variables.
Now, consider the nonlinearity term \(v_{ij}^{pk} t_{ij}^{pk} = z_{ij}^{pk}\) which can be rewritten as \(\sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } t_{ij}^{pk} \Psi_{ij\theta }^{pk} } = z_{ij}^{pk}\). By defining the new nonnegative continuous variable \(\kappa_{ij\theta }^{pk}\), \(\sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } \kappa_{ij\theta }^{pk} } = z_{ij}^{pk}\) is obtained, in which \(\kappa_{ij\theta }^{pk} = t_{ij}^{pk} \Psi_{ij\theta }^{pk}\) for every \(i,j,p,k,\theta\). And according to the definitions made, the equivalent constraints to these definitions are also added to the model:
To linearize the cost of quality loss \((1 - e^{{ - \gamma_{1} \left( {\tau_{j}^{k} - \tau_{0}^{k} } \right)}} )\) the first order of the tailor series is used. Therefore the function \(C^{\prime}_{3}\) is approximated as \(F_{2} \sum\nolimits_{k \in K} {\sum\nolimits_{{i \in I_{0} }} {\sum\nolimits_{\begin{subarray}{l} j \in I \\ j \ne i \end{subarray} } {q_{j} \gamma_{1} x_{ij}^{k} \tau_{j}^{k} - q_{j} \gamma_{1} x_{ij}^{k} \tau_{0}^{k} } } }\) which contains the nonlinear multiplication expressions \(x_{ij}^{k} \tau_{j}^{k}\) and \(x_{ij}^{k} \tau_{0}^{k}\). In this case, two new variables \(\zeta_{ij}^{k}\) and \(\zeta_{ij}^{^{\prime}k}\) are considered as \(\zeta_{ij}^{k} = x_{ij}^{k} \tau_{j}^{k}\) and \(\zeta_{ij}^{^{\prime}k} = x_{ij}^{k} \tau_{0}^{k}\), and the next equivalent relations are also added.
And so, \(C^{\prime}_{3}\) approximated as \(F_{2} \sum\nolimits_{k \in K} {\sum\nolimits_{{i \in I_{0} }} {\sum\nolimits_{\begin{subarray}{l} j \in I \\ j \ne i \end{subarray} } {q_{j} \gamma_{1} \zeta_{ij}^{k} - q_{j} \gamma_{1} \zeta_{ij}^{^{\prime}k} } } }\).
Now, consider nonlinear terms \(x_{ij}^{k} t_{ij}^{pk}\) and \(x_{ij}^{k} \max \{ L_{i} - \tau_{i}^{k} ,0\}\) in function \(C_{4}\). To linearize the first multiplication function, we have to define the new continuous variable \(R_{ij}^{pk} = x_{ij}^{k} t_{ij}^{pk}\) and new constraints as:
For the second term firstly, the new continuous variable \(WL_{i}^{k} = \max \{ L_{i} - \tau_{i}^{k} ,0\}\) is defined and then the new continuous variable \(R_{ij}^{^{\prime}k} = x_{ij}^{k} WL_{i}^{k}\) and the following equivalent constraints are applied in the model.
As a result, the keeping fresh cost-function changes as \(C_{4} = \sum\nolimits_{k \in K} {\sum\limits_{{i \in I_{0} }} {\sum\nolimits_{\begin{subarray}{l} j \in I \\ j \ne i \end{subarray} } {\sum\nolimits_{p \in P} {F_{3} \left( {R_{ij}^{pk} + R_{ij}^{^{\prime}k} } \right) + F_{4} x_{ij}^{k} s_{j} } } } }\).
In the case of linearization of early and late penalties, the process is similar to the previous case. Thus, continuous variables \(WL_{i}^{k} = \max \{ L_{i} - \tau_{i}^{k} ,0\}\) and \(WU_{i}^{k} = \max \{ \tau_{i}^{k} - U_{i} ,0\}\) as well as the following constraints are used.
Finally, it is time to linearize the pollution emission cost function. To linearize \((v_{ij}^{pk} )^{2}\), a new integer variable \(v_{ij}^{p} \Psi_{ij\theta }^{pk} = \sigma_{ij\theta }^{pk}\) is applied in the following way:
Then because of substitution \(v_{ij}^{p} \Psi_{ij\theta }^{pk} = \sigma_{ij\theta }^{pk}\), the next constraints are applied in the model:
For linearizing \(\frac{1}{{\sum\nolimits_{p} {v_{ij}^{pk} } }}\), the new continuous variable is defined. Regarding this definition, the \(1 = \sum\nolimits_{p} {h_{ijk} v_{ij}^{pk} }\), so \(h_{ijk} v_{ij}^{pk} = h_{ijk} \sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } \Psi_{ij\theta }^{pk} } = \sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } h_{ijk} \Psi_{ij\theta }^{pk} } = \sum\nolimits_{\theta = 0}^{\Omega } {2^{\theta } \pi_{ij\theta }^{pk} }\) is hold,
where in \(\pi_{ij\theta }^{pk} = h_{ijk} \Psi_{ij\theta }^{pk}\) for every \(i,j,k,p,\theta\). The following related constraints are applied:
Therefore, the problem will be changed as follows \(P_{1}^{\prime }\):
3.2 Solving the linearized model:
In this section, a heuristic hybrid method based on Benders Decomposition and PSO algorithms is presented.
3.2.1 Benders decomposition phase
The structure of the linearized model is such that Benders decomposition can be applied to solve it. In the Benders decomposition method, the mixed integer programming problem is decomposed into two sub-problems called a master problem and a sub-problem. And each of these sub-problems is solved iteratively until reaching the optimal solution [3]. The sub-problem is a continuous linear model involving continuous variables and their constraints from the main problem. The master problem is a mixed-integer model that includes the integer variables of the main problem and their constraints as well as a continuous variable that links the two sub-problems. The optimal solution obtained from solving the master problem is a lower bound for the main problem. Also, by using the solution obtained from the master problem placing the obtained values of the integer variables of this problem in the sub-problem, and solving the dual problem of the sub-problem, an upper bound can be obtained for the main problem. In the next iteration, one or more cuts are generated. These cuts are added to the master problem, and the master problem is solved again with new constraints, to obtain a new and better lower bound. This process continues until the upper and lower bound gaps are reduced to an acceptable value or a zero. It is worth mentioning that, in several finite iterations, the Benders decomposition algorithm finds an optimal solution. Next, the main problem \(P^{\prime}_{1}\) that is used to create the master problem and the sub-problem is presented:
In which \(H(.)\) is the Benders’ sub-problem and how to develop it are presented in the next section.
3.2.2 Benders sub-problem
The Benders sub-problem \(H(.)\) includes continuous variables \(h_{ijk} ,\pi_{ij\theta }^{pk} ,WL_{i}^{k} ,WU_{i}^{k} ,R_{ij}^{pk} ,R_{ij}^{^{\prime}k} ,\zeta_{ij}^{k} ,\zeta_{ij}^{^{\prime}k} ,\kappa_{ij\theta }^{pk}\) and an optimal value of them is obtained by solving the sub-problem with the fixed values \(\tilde{v}_{ij}^{pk} ,\tilde{\sigma }_{ij\theta }^{pk} ,\tilde{x}_{ij}^{k} ,\tilde{\delta }_{ij}^{0k} ,\tilde{\delta }_{ij}^{1k} ,\tilde{\delta }_{ij}^{2k} ,\tilde{\Psi }_{ij\theta }^{pk}\). This problem can be represented as:
It is worth mentioning that solving the \(P_{2}\), it decomposed into \(|I|\) independent sub-problems for each \(i \in I\).
3.2.3 Benders master problem
Let are the dual variables of constraints from the sub-problem \(P_{2}\), Whose optimal value is specified by \(\tilde{\varpi }_{ijk}^{1^{\prime}} ,\tilde{\varpi }_{ijk}^{1} ,\tilde{\varpi }_{ijpk}^{2} ,...,\tilde{\varpi }_{ij\theta pk}^{36}\). Then the Benders master problem is presented as:
The Eq. (54) shows the objective function of the Benders master problem. The Eq. (55) demonstrated the optimality cut and added to the master problem when the sub-problem is solved. Also, the Benders master problem is solved by the BPSO algorithm.
3.2.4 Binary PSO phase
Particle Swarm Optimization is a population intelligence-based optimization algorithm. PSO algorithm is reasonable for high dimensional optimization models, with information-sharing components fast convergence speed, and straightforward and helpful parameter settings [5]. Kennedy and Eberhart [11] proposed the BPSO method. Let the particle’s length and N's population size be named by D and N respectively and \(XP_{n} = (xp_{n}^{1} ,xp_{n}^{2} ,...,xp_{n}^{d} ,...,xp_{n}^{D} )\),\(VP_{n} = (vp_{n}^{1} ,vp_{n}^{2} ,...,vp_{n}^{d} ,...,vp_{n}^{D} )\) which are the position vector and velocity vector of the nth particle. Also, let \(Pbest_{n} = (Pbest_{n}^{1} ,Pbest_{n}^{2} ,...,Pbest_{n}^{D} )\) and \(Gbest = (gbest_{{}}^{1} ,gbest_{{}}^{2} ,...,gbest_{{}}^{D} )\) specifies the best position of the nth particle and the best position of the group until now respectively. The other notations are defined below:
\(\varepsilon\) | Known as inertia weight which is applied as a speed parameter factor to create a better search capability and it's usually valued between 0.4 to 0.9 |
\(\begin{array}{*{20}l} {c_{1} (c_{2} } \hfill \\ \end{array} )\) | Acceleration coefficients which represent the rating trust in the particle's own experience |
\(\begin{array}{*{20}l} {r_{1} (r_{2} } \hfill \\ \end{array} )\) | Random values in the range \(\left[ {0,1} \right]\) |
So, based on these notations the position and velocity of each particle are updated regarding the following equations:
Regarding the decoding scheme in [16] the above velocity equation remains unchanged until the following equation of the position updating is replaced:
In that sigmoid function \(S(vp_{n}^{d} (t)) = 1/(1 + \exp ( - vp_{n}^{d} (t))\) is applied to determine the probability of the d-th element of the n-th particle swarm.
Now, it is time to adapt the BPSO algorithm to solve the master problem.
In the first step, initial values of \(\varepsilon ,c_{1} ,c_{2} ,r_{1} ,r_{2}\) are set and the initial values of particle binary variables \(XP_{n} = (x_{ij}^{k} ,\,\delta_{ij}^{0k} ,\delta_{ij}^{1k} ,\delta_{ij}^{2k} ,\,\Psi_{ij\theta }^{pk} )_{n}\) are randomly initialized by using the equation of the updating position. It is worth mentioning that the value of \(v_{ij}^{pk}\) and then \(\sigma_{ij\theta }^{pk}\) are determined according to equations \(v_{ij}^{pk} = \sum\limits_{\theta = 0}^{\Omega } {2^{\theta } \Psi_{ij\theta }^{pk} }\) and \(v_{ij}^{p} \Psi_{ij\theta }^{pk} = \sigma_{ij\theta }^{pk}\). Then the value of the fitness function at the current position n-th particle is calculated via \(Z_{3} (XP_{n} )\). According to the fitness values of particles, the best personal position of each particle named \(Pbest_{n}\), and the best collection of all particles is considered to be \(Gbest\). In the second step \(XP_{n}\) will be updated and in the third step, the best personal position is updated if the current position of the particle is better than \(Pbest_{n}\). In the next fourth step, the best global position is updated if the current positions are better than the solutions \(Gbest\). The algorithm should be repeated from the second step until the specified iteration.
4 Performance analysis and results
To evaluate the performance of the proposed model and proposed solution algorithm, some experiments were carried out. At first, the proposed model was tested on a real case study model. Implementing a real model makes it possible to see the results in a concrete example. In the following, some practical examples and randomly generated samples are considered to evaluate the proposed solution method. Finally, sensitivity analysis on changes in the main parameters of the model is to be done in the best possible way. All calculations have been performed using GAMMS 25.2 software on a system with Intel (R), Core (TM) 2 specifications, 2.40 GHz CPU, and 3.00 GB RAM.
4.1 Validation of the proposed model via a real case study
In this subsection, to show the efficiency of the proposed model, experiments were run using a network from the literature (i.e. a simple version of the Chongqing city Fig. 2. from [12]). This is the cold distribution chain case for a Chongqing city. This system distributes fresh vegetables from DC (depot center) to its customers in 16 central areas (1 to 16) of the city. Table 2 shows the location and coordinates of these 16 points as well as the amount of demand and time window for them, respectively. The other related parameters of the model are extracted from [12].
Customer distribution point location
Three allowed speed periods \([v_{ijl}^{p} ,v_{iju}^{p} ] = [20,40],[45,80]\) and \([20,40][20,40]\) are considered for 3 time periods \(\left[ {4:30,5:30} \right),\,[5:30,6:30),\,\left[ {6:30,7:30} \right]\) of traffic. Supposed that the service time to each customer is 2 min and the shipping cost for each arc is a fixed unit (\(c_{ij} = 1\)). The capacity of vehicles is the same and equal to 1.7. The obtained results from the proposed model are compared with the best solution reported in [12] which solved their model with constant speed. For a better comparison, 5 types of objective function costs considered in both models, as well as the length of the route traveled and the load capacity moved by each vehicle, have been reported. These 5 types of costs include fixed vehicle costs, losing quality, refrigeration, penalty, and environmental costs. It is worth mentioning that emissions cost only includes CO2 emissions. The results are given in Table 3.
The results show that 3 vehicles have been used and 3 service routes have been created in the network. The presented model has been able to serve customers with the lowest cost by observing the speed of the vehicle in any traffic period and related time window. Note that considering the variable speed in traffic periods, in addition to being close to reality, led to reduced costs. The proposed model identifies the most optimal route to prevent traffic jams and reduce pollution, which is different from the obtained routes in [12]. The optimal paths obtained from solving the model are shown in Fig. 3.
Optimal routes based on the proposed model
4.2 Comparison and validation of the hybrid method
This section tries to evaluate the performance of the proposed solution algorithm. For this purpose, several test instances from [23] are considered. These samples are categorized based on the number of customers. There are 9 categories of instances with different sizes and 5 samples from each category. Eight modes of 10, 15, …, 200 are considered for the number of customers, and corresponding to each of these cases, several vehicle devices from 2 to 25 are considered. In the considered samples, the service time (unloading) and time windows are known, for each customer. The horizon time starts at time 0, points a1, a2, and Tmax are set as 2, 7, and 9, hours respectively, and allowable speed periods are considered and \([20,40]\).
Table 4 reports the calculation results. For each category, the average solution of 5 samples is reported. The first column indicates the name of each instance, for example, UK10 means a network with 10 clients. The maximum number of vehicles used is shown in the second column.
Now, to show the quality of the obtained solution from the proposed method, a comparison has been made with the software optimization CPLEX. The best objective value corresponding to the feasible solution obtained by CPLEX for the \(P^{\prime}_{1}\) within a time limit of 9000s is considered. CPLEX solver can be obtained to the desired optimal solution for small instances up to UK25. For medium-size tests up to UK100, CPLEX could not complete the solving process promptly (9000 s) and therefore the best value obtained from the objective function was reported as the best solution detected. Of course in large-scale cases, no optimal solution is obtained by CPLEX. Indeed, by increasing the size of the problem, the computing time performed by CPLEX increases too rapidly.
So, for doing better evaluation a Benders decomposition method, a Meta heuristic FA algorithm [21], and an artificial intelligence SA algorithm [19] are applied, and they enable solving larger-scale problems. Let \(Z_{CP}\), \(Z_{BP}\), \(Z_{B}\), \(Z_{FA}\) and \(Z_{SA}\) are the best-obtained solution by CPLEX, the proposed method, Benders decomposition, and the firefly algorithm respectively. Based on these symbols the label \(Gap_{CP\& BP}\)(\(Gap_{CP\& B}\),\(Gap_{CP\& FA}\) and \(Gap_{CP\& SA}\)) demonstrates the gap between \(Z_{CP}\) and the \(Z_{BP}\)(\(Z_{B}\),\(Z_{FA}\) and \(Z_{SA}\)) which is calculated by \(\frac{{Z_{BP} (Z_{B} \,or\,Z_{FA} \,or\,Z_{SA} ) - Z_{CP} }}{{Z_{CP} }}\), and the min, max, and average gaps from 5 solved tests of each category are reported in Table 4. The labels \(T_{CP}\),\(T_{BP}\), \(T_{B}\), \(T_{FA}\) and \(T_{SA}\), show the average time required for solving the model by the five methods.
According to the achieved results, the proposed algorithm can obtain the optimal solution for small cases (up to UK25), which is proof of the effectiveness of the proposed algorithm in obtaining the optimal solution for these cases. For some medium cases in particular, for size instances with 50 and 75 nodes, an optimal solution is not available, by the CPLEX within the given time limit. In most of these cases, the proposed algorithm introduces a better solution to the upper bound provided by CPLEX. For larger sizes instances (especially larger than the UK100), a feasible solution with CPLEX is not available within 9,000 s. In most of these cases, the proposed method, Benders Decomposition, Firefly algorithm, and Simulated annealing algorithm obtained a better solution compared to the upper bound which they are obtained by the CPLEX solver. Of course, the obtained negative gaps reflect this fact. However, the results show that the quality of the obtained solution from the proposed and Benders methods is higher than the FA. The quality of the solution obtained by the SA algorithm is better than the Benders and FA methods and lower than the proposed solution method. At the same time, the calculation time of the proposed hybrid method is reasonable and less than the Benders method, and it's more than the FA and SA methods, but it is not much different from them. If we want to make a general comparison between the proposed method, FA, and SA methods, we can say that the SA method works relatively faster, but the proposed method obtains more accurate solutions. Remarkably, the existing time difference (albeit small) is related to the additional operation of the solution of Benders' master problem. Generally, the time required increases as expected but is still reasonable.
4.3 Sensitive analysis of the model
This section is dedicated to the sensitivity analysis of the model from the point of view of changes in the main assumptions regarded in the model that have been investigated. For this reason, we will provide a summary of the results for some examples (based on the example in 4.1) that differ in only one parameter that has been considered.
4.3.1 The effect of capacity vehicles
This evaluation tries to show the effect of capacity vehicles concerning the different costs as well as average speed. To this end, several test examples with different load capacities have been considered and the calculation results are reported in Table 5.
According to Table 5, it can be said that by increasing the capacity of vehicles, regarding the shipping cost, the vehicles may choose a better route with more volume. Therefore, the total distance between these cases has decreased. This route may be delayed or even accelerated to serve some customers in the promised time window and it in turn causes to increase in the penalties. Of course, the total cost should be reduced. Because the model identifies the optimal solution, if changes in routing lead to increasing the overall cost, the model considers the same path as the lower capacity. Based on the results, when the vehicle's capacity increases, a smaller number of vehicles can be used to cover customer demand, which will reduce the environmental, refrigeration, and fixed costs (the cost of keeping the material). But by reducing the number of vehicles, the penalty cost and cost of losing the quality of material increases. On the other hand, by increasing the number of vehicles (to more than 4), the penalty cost is zero, but environmental costs reach their maximum value. These results indicate that meeting only one particular purpose cannot maximize the interest of the company. So, to obtain the best performance, optimization should be considered for several goals. As you can see, with increasing vehicle load capacity, the number of vehicles used is reduced from 5 to 2. This gives the direct relationship between the maximum load capacity, the number of vehicles, and the total cost. The results and the relationship between the cost functions are shown in Fig. 4. Based on this figure, increasing the load capacity, losing quality (C3), and penalties (C5) costs have increased, but the costs of refreshing (C4) and environmental (C6) have decreased. Finally, it is suggested that companies should check all distribution conditions in the process of routing paths with the appropriate maximum load capacity and number of vehicles.
Sensitivity analysis based on vehicle capacity on objective costs
4.3.2 The impact of variable speeds at traffic periods:
This subsection is dedicated to the effect of variable speed. For this reason, the previous example with different constant speeds in time traffic period and variable speed is considered. The computational results are shown in Table 6. It should be noted that in each example, the capacity of all vehicles is the same and equal to 1.7, so the optimal number of vehicles in all scenarios is 3.
From Table 6, it can be concluded that having a constant and low speed of the vehicle leads to an increase in fuel consumption, emission costs, and an increase in the number of penalties for early or late servicing, and in general, it can be said that the total cost is far from the optimal cost. Meanwhile, the high speed reduces the early or late service penalty. Note that increasing the speed to a certain extent leads to a reduction in fuel consumption and emission costs, and if the speed increases too much, fuel consumption and emission costs will increase. According to the results, it can be said that the closest solution to the optimal solution is obtained with speed (35, 70, 35), but again, in no case with constant speed, the optimal value obtained with variable speed was not achieved. These results show that considering the variable speed, the model seeks to find a balance between the cost of penalties, emissions, and other costs. The results and the relationship between the cost functions are shown in Fig. 5.
Comparison of variables speed vs. different fixed speed
4.3.3 The impact of congestion periods
One of the factors influencing the costs related to early or late penalties, fuel costs, and pollution is traffic periods which we will verify in this section. So, 5 different scenarios on the network related to the example are considered. The two first cases are related to free-of-traffic periods with free speed and constant speed, respectively. The other 3 modes are shown in Table 7.
The results show that considering traffic congestion intervals can lead to different results. Free speed and constant speed lead to two completely different solutions that in the first case imposes the lowest possible cost and in the second case the highest possible cost to the objective function. Considering the traffic intervals, the results seem more logical.
In the case where the free traffic period has more time, the average speed is higher and as a result, the penalties, the cost of losing quality, and the cost of refrigeration are reduced. On the other hand, because a longer path may be chosen to reduce the penalties, the distance traveled is longer than in the fourth case, and the cost of fuel consumption and environmental pollution is higher. Also, for the case where the second period is smaller (fifth case), the average speed has decreased and as a result, the costs of penalties, losing quality, refrigeration, fuel consumption, and environmental pollution have increased in comparison to the fourth case.
4.3.4 The impact of time windows
In this part, the impact of time windows has been investigated. To this end, expanding and narrowing the time windows up to 20% are considered. That is the distance from the upper and lower time bounds decreases or increases by this percentage. The computational results are reported in Table 8.
The computational results confirm that narrowing or expanding up to 10% has the minimum effect on solutions, such that it had a maximum 1% effect on total costs. While, narrowing or expanding time windows by 20%, have a considerable effect on the objective function. If time windows are expanded by 20%, the penalty will be zero, while narrowing the time window by 20%, leads to an increase in the penalty significantly. Also, it can be concluded from the output results that, narrowing the time window causes to increase in the average speed of the vehicle to avoid paying penalties, and vice versa.
4.3.5 The effect of penalty cost
In this section, the effect of penalty cost of late or early time windows has been considered. For this purpose, increasing and decreasing the penalty by up to 50% has been examined. The calculation results are reported in Table 9.
The results show that increasing or decreasing the penalty up to 10% does not have much effect on the solutions. While increasing or decreasing the penalty by 50% has a significant effect on the solution and the objective functions. If the lateness or early arrival penalty is reduced by 50%, the penalty cost is significantly reduced. In this case, the cars are not in a hurry to arrive at a certain time, and the average speed of the car is lower than in other cases. While increasing the penalty up to 50% leads to a significant increase in the cost. It can also be concluded from the results that increasing the penalty rate increases the average speed to avoid paying the penalty and vice versa.
4.3.6 The effect of the fuel consumption cost
In the previous analysis, it was shown that determining an appropriate speed causes it to go down fuel consumption and greenhouse gas emissions and hence the related costs. In this section, we try to check the sensitivity of the resulting solutions to changes in fuel consumption costs. For this reason, we consider different amounts of costs in the range that we have an increase or decrease of up to 50%. Table 10 reports a summary of the results, the results show that minor changes in unit fuel consumption do not significantly change the emission cost, penalty cost, and overall solutions obtained.
The more drastic changes in fuel cost may lead to significant differences in the solution obtained. The higher fuel cost leads to a decrease in average speed, a decrease in fuel consumption, and consequently a decrease in emission cost, an increase in the amount of late and early penalties, and the total increase in the objective function value. Also, the lower fuel cost leads to an increase in average speed, an increase in fuel consumption, and consequently an increase in emission cost, a decrease in the amount of late penalties, and a total increase in the objective function value. Of course, it can also be inferred that the effect of fuel consumption on the objective function is almost less than the soon and late penalty. In fact, in some cases to serve customers within the soft time windows (with high penalties for delayed and early), vehicles are forced to increase their speed even if it leads to the need for more fuel and so emissions.
4.3.7 The impact of the cost of keeping fresh
In this section, the effect of the cost of keeping fresh has been investigated. Since the customer service time, i.e. the time when the refrigerator is open is considered as fixed, increasing or decreasing the fresh cost for the refrigerator to be open does not affect the solutions. So, only increases and decreases the total cost of refrigerating during the path has been investigated and its change has been considered up to 50%. The calculation results are reported in Table 11.
The results show that increasing or decreasing the refrigerating cost has a significant effect on the answers. although, by increasing or decreasing the cost of keeping fresh up to 10%, the path has not been changed, it affects the cost of refrigerating and the average speed. When the increase or decrease is 50%, we have a significant effect on the answers. If we reduce the cost of refrigerating by 50%, the costs of penalty, fuel, and quality will increase, but the average speed and cost of refrigerating will decrease significantly. The increase in refrigerating cost by up to 50% leads to a significant increase in all costs except the cost of quality. When the cost of refrigerating increases, to pay cost less, the vehicle moves faster.
4.3.8 The impact of departure time
In the model presented, the time of departure from the depot is considered as a variable. In this part, we examine the effect of constant departure time. Assume that all vehicles start moving at the initial time. Table 12 shows the obtained results.
The results show that if the start time is constant, it affects lateness and earliness penalties, and as a result, the speed of the car increases, which leads to an increase in emissions.
5 Conclusion and discussion
This work presented a green VRP model for a cold chain with traffic intervals and variable speed. The main objective is to minimize the total costs including the fixed cost of using vehicles, the transportation, and the quality loss, the keeping refreshing cost of products, the penalties, the energy, and greenhouse emissions costs. Fuel consumption and travel time on each route depend on the distance traveled as well as the speed of the vehicle at the time of day that route is traveled. Traffic is different at different times of the day and it is not always possible to move at a constant speed. Therefore, the optimal distribution path by the objective model considering vehicle speed is closer to reality. In this study, three traffic periods are considered based on traffic congestion. The proposed model is nonlinear, which has been transformed into a mixed-integer linear optimization one, by using some linearization techniques. To solve the linearized model, a hybrid solution method based on the Benders decomposition method and PSO algorithm was proposed.
The presented model was implemented as a practical example. The results showed that considering all GHG emission costs is better for target performance and can reduce total costs. The sensitivity analysis was also checked out based on the change in some existing parameters and assumptions. The overall results show how much the fuel consumption, emissions, and objective functions are affected by these parameters.
The results showed that increasing the maximum load capacity of the vehicle led to increasing both penalties and the loss of quality costs, and the other costs were decreased. Also, reducing or increasing the speed of the vehicle too much will increase the emission costs and fuel consumption. Changes in traffic intervals have the conclusion that if the free speed traffic period has more time, the average vehicle speed will increase, and as a result penalty, the losing quality cost, and the cost of refrigeration will be reduced. On the other hand, for the case where the free speed traffic interval is smaller, the average speed decreases, and as a result, all costs (except transportation) increase. Furthermore, expanding or narrowing the time window up to 10% had no significant effect on solutions other than the penalties. While increasing or decreasing the time window further than 10% increases the fuel consumption and emission costs. The more drastic changes in fuel cost, refrigerating cost, and departure time may lead to significant differences in the solution obtained. A higher fuel cost leads to a decrease in average speed, a decrease in fuel consumption, and consequently a decrease in emission cost, an increase in the amount of late and early penalties, and the total increase in the objective function value and vice versa. If we reduce the refrigerating cost by 50%, the costs of penalty, fuel, and quality will increase, but the speed and cost of refrigerating will decrease significantly. In the end, to examine the proposed hybrid algorithm, a sample set with different sizes that are available in the literature was evaluated. Also, the results of the proposed method have been compared with four other methods, namely the CPLEX method, Benders decomposition, firefly algorithm, and Simulated annealing algorithm in terms of solution quality and time. The results showed that the proposed hybrid method obtains optimal and near-optimal solutions in a reasonable time. By overall comparison between the methods, the SA method performs relatively faster and the proposed method obtains more accurate solutions.
For future work, as a suggestion, the model can be brought closer to the real problems by considering the conditions of uncertainty. There are uncertainty factors such as road and weather conditions, as well as customer demand patterns that cannot always be considered constant. In addition, a wider network with several types of services or several depots can be considered. Also, it seems that the proposed model can be used for problems with alternative fuels, which can be considered as a suggested work for future research. The discussion of the competitive market and the two-level model can also be considered on the problem.
Data availability
The data available in the literature of the subject have been used, and the relevant references have been fully addressed in the text.
References
Bai, Q., Yin, X., Lim, M.K., Dong, C.: Low-carbon VRP for cold chain logistics considering real-time traffic conditions in the road network. Ind. Manag. Data Syst. 122(2), 521–543 (2022)
Bao, C.L., Zhang, S.B.: Route optimization of cold chain logistics in joint distribution: With consideration of carbon emission. Ind. Eng. Manag. 23, 95–107 (2018)
Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962)
Chen, J., Liao, W., Chengwei, Yu.: Route optimization for cold chain logistics of front warehouses based on traffic congestion and carbon emission. Comput. Ind. Eng. 161, 107663 (2021)
Cui, S., Xiaoyan, Gu., Xie, W., Dengsheng, Wu.: Research on cold chain routing optimization of multi-distribution center considering traffic performance index. Proc. Comput. Sci. 221, 1343–1350 (2023)
Demir, E., Bektas, T., Laporte, G.: A review of recent research on green road freight transportation. Eur. J. Oper. Res. 237(3), 775–793 (2014)
Dukkanci, O., Kara, B.Y., Bektas, T.: The Green Location-Routing Problem. Comput. Oper. Res. 105, 187–202 (2019)
Fang, W.T., Ai, S.Z., Wang, Q., Fan, J.B.: Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm. Chin. J. Manag. Sci. 27(11), 107–115 (2019)
Hooshmand, F., MirHassani, S.A.: Time-dependent green VRP with alternative fuel-powered vehicles. Energy Syst. 10(3), 721–756 (2019)
Huang, Y., Pan, L.: Urban cold chain logistics vehicle path optimization based on IOT real-time traffic. In: 2022 4th International Conference on Data-driven Optimization of Complex Systems (DOCS) (pp. 1–6). IEEE. 2022, October
Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: IEEE International Conference on Systems, Man, and Cybernetics. 5, 4104–4108 (1997)
Li, Y., Lim, M.K., Tseng, M.-L.: A green vehicle routing model based on modified particle swarm optimization for cold chain logistics. Ind. Manag. Data Syst. 119(3), 473–494 (2019)
Liu, G., Hu, J., Yang, Y., Xia, S., Lim, M.K.: Vehicle routing problem in cold Chain logistics: a joint distribution model with carbon trading mechanisms. Resour. Conserv. Recycl. 156, 104715 (2020)
Liu, S.: Multimodal transportation route optimization of cold chain container in time-varying network considering carbon emissions. Sustainability. 15(5), 4435 (2023)
Ma, X., Liu, T., Yang, P., Jiang, R.: Vehicle routing optimization model of cold chain logistics based on stochastic demand. J. Syst. Simul. 28(8), 1824 (2016)
MirHassani, S.A., Raeisi, S., Rahmani, A.: Quantum binary particle swarm optimization-based algorithm for solving a class of bi-level competitive facility location problems. Optim. Methods Softw. 30(4), 756–768 (2015)
Montoya, A., Guéret, C., Mendoza, J.E., Villegas, J.G.: A multi-space sampling heuristic for the green vehicle routing problem. Transport. Res. Part C Emerg. Technol. 70, 113–128 (2016)
Ndraha, N., Hsiao, H.-I., Vlajic, J., Yang, M.-F., Lin, H.-T.V.: Time-temperature abuse in the food cold chain: review of issues, challenges, and recommendations. Hong-Ting Victor Lin. 89, 12–21 (2018)
Nowakowski, P., Szwarc, K., Boryczka, U.: Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms. Res. Part D Transp. Environ. 63, 1–22 (2018)
Qin, G., Tao, F., Li, L.: A vehicle routing optimization problem for cold chain logistics considering customer satisfaction and carbon emissions. Int. J. Environ. Res. Public Health 16(4), 576 (2019)
Rahmani, A., Hosseini, M.: A time-dependent green location-routing problem with variable speed of vehicles. Opsearch 59(3), 945–973 (2022)
Ren, T., Chen, Y., Xiang, Y.C.: Optimization of low-carbon cold chain vehicle path considering customer satisfaction. Comput. Integr. Manuf. Syst. 26(4), 1108–1117 (2020)
Salimifard, K., Raeesi, R.: A green routing problem: optimizing CO2 emissions and costs from a bi-fuel vehicle fleet" The Pollution-Routing Problem Instance Library. Int. J. Adv. Oper. Manag. 6, 27–57 (2014)
Song, M.X., Li, J.Q., Han, Y.Q., Han, Y.Y., Liu, L.L., Sun, Q.: Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics. Appl. Soft Comput. 95, 106561 (2020)
Sun, S., Xie, R., Chen, B.: The front-end collection transportation optimization of cold chain logistics for fresh fruits and vegetables. Log. Eng. Manag. 39, 55–60 (2017)
Sureeyatanapas, P., Poophiukhok, P., Pathumnakul, S.: Green initiatives for logistics service providers: an investigation of antecedent factors and the contributions to corporate goals. J. Clean. Prod. 191, 1–14 (2018)
Talouki, R.Z., Javadian, N., Movahedi, M.M.: Optimization and incorporating of green traffic for dynamic vehicle routing problem with perishable products. Environ. Sci. Pollut. Res. 27, 36415–36433 (2021)
Tsang, Y.P., Wu, C.H., Lam, H.Y., Choy, K.L., Ho, G.T.: Integrating Internet of Things and multi-temperature delivery planning for perishable food E-commerce logistics: a model and application. Int. J. Prod. Res. 59(5), 1534–1556 (2021)
Wang, S.Y., Sun, H., Mou, J.J., Jin, H.: Optimization and efficiency of multi-Temperature joint distribution of cold chain products: comparative study based on cold accumulation mode and mechanical refrigeration mode. J. Highw. Transport. Res. Dev. 33(3), 146–153 (2016)
Wang, S., Tao, F., Shi, Y.: Optimization of location-routing problem for cold chain logistics considering carbon footprint. Int. J. Environ. Res. Public Health 15, 86 (2018)
Wang, Z., Wen, P.: Optimization of a low-carbon two-echelon heterogeneous-fleet vehicle routing for cold chain logistics under mixed time window. Sustainability. 12, 1967 (2020)
Zhang, A., Zhang, Y., Liu, Y.: Low-carbon cold-chain logistics path optimization problem considering the influence of road impedance. IEEE Access 11, 124055–124067 (2023)
Zhang, Y., Hua, G., Cheng, T.C.E., Zhang, J.: Cold chain distribution: How to deal with node and arc time? Ann. Oper. Res. 291, 1127–1151 (2020)
Zhao, Z.X., Li, X.M., Zhou, X.C., Liu, C.S.: Research on green vehicle routing problem of cold chain distribution: considering traffic congestion. Comput. Eng. Appl. 56(1), 224–231 (2020)
Funding
This work was not supported by any financial organization.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
No potential conflict of interest was reported by the author(s).
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Hosseini, M., Rahmani, A. The green cold vehicle routing problem with traffic congestion and variable speed. Energy Syst (2024). https://doi.org/10.1007/s12667-024-00689-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s12667-024-00689-1