A multi-objective dynamic vehicle routing optimization for fresh product distribution: A case study of Shenzhen

1.   Introduction

The market demand for fresh products is growing rapidly with the development of Internet and cold-chain technology in recent years. In China, the market size of the fresh-product e-commerce industry was 363.8 billion RMB in 2022, with a growth of 16.7% compared with 2021 ^[1]. However, the consequent growth in fresh-product distribution poses huge challenges to fast and efficient distribution services provision. Fresh products are perishable, and their freshness is lost with time. Out-of-date fresh products are thrown away after a short expiry date. In the United States, the average losses of fresh products during distribution are approximately 12% of the initial production, while the average loss rate of fresh products is approximately 30% in China ^[2,3]. Therefore, providing fast and efficient distribution services is an important issue for fresh products to keep their freshness and prevent deterioration.

The fresh-product-distribution route optimization problem arises when fresh products must be distributed in cold-temperature conditions and quickly distributed within a short time window to keep their freshness. Fresh products are distributed in cold-chain trucks to avoid freshness loss in the entire distribution and uploading process. The distribution cost of fresh products is increased with the application of cold-chain technology and the deterioration of fresh products. Fresh-product customers are sensitive to the distribution time because freshness could be lost with time. Hence, research on the vehicle routing optimization problem for fast fresh-product distribution to reduce distribution costs and improve customer satisfaction has practical significance for the fresh-product distribution industry.

In addition, the popularity of internet technology allows customers to purchase fresh products through online platforms, which not only expands their purchasing channels but also meets their diverse needs. However, fresh-product orders that could be dynamically placed on an online shopping platform at any time pose tremendous challenges to the distribution-route optimization problem. If the distribution company assigns additional vehicles for new fresh-products distribution, it would largely increase the distribution cost. Therefore, the research on the fresh-product-distribution route optimization problem with dynamic customer orders has both practical and academic significance for the fresh-product industry to efficiently minimize distribution costs.

This study focuses on a multi-objective vehicle routing optimization model establishment for fast fresh-product distribution under dynamic demand conditions with the objectives of maximizing customer time satisfaction and minimizing the total distribution costs, including freshness-loss cost, delay-penalty cost, cold-chain-refrigeration cost, vehicle cost, and travel cost. The main contributions of this research are summarized as follows: 1) We propose a multi-objective vehicle routing optimization model for fast fresh-product distribution considering its freshness and short distribution time window; 2) a two-stage solution combining improved MOGAPSO and dynamic inserting algorithm is designed to quickly solve out the optimized route under dynamic demand circumstances; 3) a case study on a fresh-product distribution company in China is presented to validate the practicality of the proposed model and algorithm.

The structure of the paper is as follows: Section 2 reviews the extant literature on multi-objective fresh-product distribution and dynamic vehicle routing problem (VRP) problem; Section 3 proposes a multi-objective dynamic routing optimization model for fast fresh-product distribution; Section 4 introduces the two-stage solution based on improved MOGAPSO and dynamic inserting algorithm to solve the proposed model; Section 5 conducts a case study to test the practicality of the proposed model and algorithm; Section 6 summarizes the conclusions of the study and suggests future research direction.

2.   Literature review

The vehicle routing problem (VRP) was proposed by Dantzig and Ramser in 1959 ^[4]. The multi-objective VRP is a kind of VRP problem that requires balancing multiple objectives to find an optimal distribution route. For the fresh-product-distribution route optimization problem, multiple objectives could be the distribution cost, freshness-loss cost, rider utilization, or customer satisfaction. For example, Li et al. ^[5] considered the highly perishable nature of fresh products and established a multi-objective optimization model for minimizing the freshness decay and the total costs. Liao et al. ^[6] studied the multi-objective routing problem for green meal delivery to maximize customer satisfaction, balance rider utilization, and minimize carbon footprint. A two-stage strategy was proposed combining non-dominated sorting genetic algorithm Ⅱ (NSGA-Ⅱ) and adaptive large neighborhood search (ALNS) algorithm. Leng et al. ^[7] proposed a bi-objective cold-chain distribution-route model for fresh products that aimed to minimize the total distribution cost and the quality-degradation cost. To obtain the Pareto solutions, a novel multi-objective hyper-heuristic (MOHH) was proposed. Similarly, Hu et al. ^[8] developed a mixed integer programming model over time to minimize the total operational cost of the fresh cold-chain distribution process, including routing, time penalty, cargo damage, and refrigeration cost. They proposed a solution combining the variable neighborhood search and particle swarm algorithm for distribution routing optimization. Differently, we propose a multi-objective VRP considering fast-distribution and freshness-related objectives, including customer time satisfaction, delay-penalty cost, freshness-loss cost, and cold-chain-refrigeration cost under practical dynamic demand conditions.

Heuristics algorithms are mainly used to find the Pareto solution set for multi-objective optimization problems ^[9]. Multi-objective particle swarm optimization algorithm (MOPSO) is a kind of intelligent algorithm with many advantages including its simplicity, fast calculation speed, and easy implementation. MOPSO has been widely used to solve multi-objective problems in many fields. For example, Xu et al. ^[10] studied a multi-objective optimization approach for refined-oil distribution considering station satisfaction, operation cost, and overtime penalty. A robust optimization model was developed to manage uncertainty in demand. A MOPSO algorithm was proposed to effectively solve the mathematical model. Similarly, Kuo et al. ^[11] investigated a multi-objective VRP model in a time window with the two objectives of supply-chain cost and carbon emission minimization. An improved MOPSO algorithm was designed to show the highest hyper-volume and lowest spacing. Wang et al. ^[12] addressed the multi-depot green VRP. They designed a bi-objective mathematical model aimed at minimizing total carbon emission and operation costs. A hybrid heuristic algorithm for vehicle routing optimization, combining the savings heuristic algorithm, sweep algorithm, and MOPSO, was used for local and global solution search. The experiment results indicated a reduction in total travel distance and number of vehicles. The shortest path was observed undermining minimized operation costs and carbon emissions. In summary, existing improvements in the MOPSO algorithm mainly focus on the iteration method of the particle swarm and its searching ability. Extensively, we propose an improved multi-objective GA-based particle swarm optimization algorithm (MOGAPSO) that introduces a genetic algorithm into the standard MOPSO algorithm to improve the diversity of the particle swarm population in this study.

Dynamic demand resulting from online orders on Internet platforms is a crucial factor affecting vehicle routing optimization. Dynamic vehicle routing optimization problems have received increasing attention from the academic area. For example, Huang et al. ^[13] proposed a mixed-integer programming model for bus network design with dynamic demand. The passenger requests were dynamically inserted in an interactive manner by a proposed dynamic insertion method. The model aimed at designing an optimal routing for multiple vehicles to serve a set of fixed or dynamic customers with strict time-deviation constraints. Achamrah et al. ^[14] investigated a dynamic and stochastic inventory routing problem (DSIRP) with flexible transshipment and substitution in a two-level supply chain. The optimal solution was solved by the genetic algorithm and deep-reinforcement learning algorithm. Nguyen et al. ^[15] addressed the dynamic traffic routing problem with multi-source and multi-destination. Their dynamic VRP was solved by an ant colony optimization (ACO) algorithm for the dynamic road network condition in the distribution-process optimization problem. Guo et al. ^[16] established a robust dynamic multi-objective vehicle optimization model with hard time-window constraints and dynamic customers considering three objectives: carbon emission, vehicle waiting time, and number of dispatched vehicles. A MOPSO algorithm was applied to find robust optimal vehicle routes. In conclusion, existing literature on dynamic vehicle routing optimization primarily focuses on circumstances of dynamic customer demand and flexible distribution networks with exact and heuristic methods in the transportation network and supply chain. In this study, we focus on a fast distribution routing optimization problem of fresh products with dynamic customer demand using improved MOGAPSO with the genetic algorithm (GA) and dynamic insertion mechanism.

To sum up, there are some differences between our study and previous research work. First, we propose a fresh-product-distribution vehicle routing optimization model with the fast-distribution and freshness-related objectives of maximizing time-sensitive customer satisfaction and minimizing total distribution costs, including freshness-loss cost and delay-penalty cost, and extending the cost-minimization objective in most existing literature. Second, we differently integrate a genetic algorithm into the standard MOPSO algorithm to improve the convergence performance for the multi-objective VRP problem. Third, we design a two-stage solution with an improved MOGAPSO algorithm and a dynamic insertion algorithm to quickly solve optimal distribution routes under practical dynamic demand conditions. This study provides a practical routing optimization strategy for fresh-product distribution enterprises on fast distribution and customer satisfaction improvement.

3.   Model formulation

3.1.   Problem description

The fresh-product-distribution route optimization problem has its unique characteristics, including (ⅰ) the cold-chain distribution requirement for fresh products to keep their freshness, (ⅱ) fast distribution requirement for fresh products to prevent freshness loss and deterioration, and (ⅲ) time-sensitive customers of fresh products who are sensitive to the distribution arrival time due to freshness. Considering the cold-chain technology application and fast requirements for fresh-product distribution, we established the fresh-product-distribution routing optimization model with multiple objectives of maximizing time-sensitive customers' satisfaction and minimizing distribution costs, including cold-chain-refrigeration cost, freshness-loss cost, delay-penalty cost, vehicle cost, and travel cost.

In our fresh-product company practice, static fresh-product orders from regular customers in retail stores are collected from the previous working day, while still accepting new customer orders dynamically arriving during the distribution process in the current working day. A multi-objective vehicle routing optimization model with static fresh-product demand is established with the multiple objectives of minimizing total distribution costs and maximizing customer time satisfaction. An improved MOGAPSO algorithm is proposed to solve this multi-objective vehicle routing optimization model, which will be discussed in detail in Section 4.1. Furthermore, a dynamic insertion mechanism is designed to dynamically handle newly arrived customer orders during the working day, which will be discussed in detail in Section 4.2 ^[17].

The fresh products are delivered from one distribution center to $n$ customer points by cold-chain distribution vehicles within a certain time window. The customers' orders, location, and distribution time windows are known. This paper focuses on the freshness of the fresh products and the fast-distribution of the dynamic and time-sensitive customer orders to optimize distribution vehicles' routes. To balance the cost and service levels, we develop a multi-objective vehicle routing optimization model to minimize the freshness-loss cost, cold-chain refrigeration cost, and delay-penalty cost, and maximize customer time satisfaction.

Based on realistic scenarios, some assumptions are presented as follows:

(ⅰ) Vehicles are homogeneous cold-chain trucks with different speeds for each time period during the distribution process, while ignoring traffic congestion and other unexpected traffic situations.

(ⅱ) There is only one distribution center where vehicles depart from and eventually return to.

(ⅲ) Each vehicle can serve multiple customers and each customer location can only be visited once.

(ⅳ) Distribution center supplies are sufficient, and all vehicles are loaded before departing.

(ⅴ) The variety of fresh products ordered by customers is the same.

(ⅵ) Fresh products are kept in cold-chain conditions during the distribution process. The freshness of fresh products is reduced during the distribution and uploading processes.

3.2.   Model formulation

To facilitate the construction of the model, the notations and definitions of the model are explained as shown in Table 1. The multi-objective mathematical model of fresh-product-distribution route optimization is presented as follows:

Subject to:

There are two objective functions in the proposed mathematical model: Equation (1) represents the minimum distribution costs, while Eq (2) represents the maximum average customer time satisfaction. The distribution costs include freshness-lost cost ${f_1}$, fixed vehicle cost ${f_2}$, variable travel cost ${f_3}$, cold-chain refrigeration cost ${f_4}$, and delay-penalty cost ${f_5}$. Equations (3)–(5) represent that each customer location needs to be serviced only once by one distribution vehicle. Equation (6) represents the vehicle traversing all customer locations. Equation (7) ensures that the vehicle departs from and returns to the distribution center. Equation (8) indicates that the fresh products loaded in the vehicle cannot exceed its maximum capacity. Equation (9) indicates that the number of customer points served by each vehicle cannot exceed the total number of customer points. Equation (10) represents the customer time satisfaction. Equation (11) is the maximum vehicle-travel-distance constraint. Equation (12) represents that the vehicle travel time is only related to the vehicle speed. Equation (13) represents that the vehicle has to wait if it arrives at the customer point before the customer acceptable time, and immediate service will be provided if it arrives within the acceptable time window. Equation (14) is the decision variables constraint.

The freshness-loss costs of fresh products during the distribution process are divided into two parts in this study. The first part is the natural freshness-loss cost that occurs over time during the distribution process. The second part is the freshness-loss cost due to surface temperature changes of fresh products caused by frequently opening the vehicle doors during the unloading process. Referring to Yu and Nagurney 3, our study applies the freshness loss function $Qua(t) = {e^{ - \sigma t}}$ to determine the freshness loss of fresh products during distribution as shown in Figure 1.

The freshness-loss cost function ${f_1}$ is represented in the following Eq (15) and is embodied in the objective function Eq (1).

Moreover, it is assumed that the fixed vehicle cost ${f_2}$, including driver cost, is dependent on the number of distribution vehicles and will not vary with the number of customers and travel distance, which is represented as the third item in the objective function Eq (1). The variable travel cost consists of the fuel cost and operation expenses of the distribution vehicles that are dependent on the travel cost. The variable travel cost ${f_3}$ is represented as the fourth item in the objective function Eq (1).

The cold-chain technology is applied in the distribution vehicle to keep the freshness of fresh products. The cold-chain refrigeration cost of distribution vehicles for fresh products includes the refrigeration cost in the distribution process and the refrigeration cost increment when the vehicle door is opened to upload the fresh products to the customers. The cold-chain refrigeration cost ${f_4}$ is represented in the following Eq (16) and is embodied in the objective function Eq (1).

where ${\theta _1}$ is the refrigeration cost of vehicles in the distribution process, and ${\theta _2}$is the refrigeration cost in the fresh-product uploading process.

In the objective function Eq (10) on customer time satisfaction ${U_i}(t{}_i)$, the customers' time sensitivity is considered in fresh-product distribution. Combining the actual fresh-product distribution practices, the dual time window model ^[18] is taken for the customer time-satisfaction function. The customer expects the distribution time window to be $[e{t_i}, l{t_i}]$and the actual acceptable distribution time window for customer is $[E{T_i}, L{T_i}]$. Customer time satisfaction ${U_{\text{i}}}({t_i})$ is equal to one if the vehicle arrives at the customer's location within the distribution window $[e{t_i}, l{t_i}]$.

Moreover, we introduce the customers' time sensitivity factors ${\alpha _i}$ and ${\beta _i}$ to describe the tolerance degree of the customer $i$ to early arrival and distribution delay, respectively, as shown in Figure 2; ${\alpha _i}$ represents the customer's sensitivity to early distribution and${\beta _i}$ is the customer's sensitivity to distribution delay. The values of ${\alpha _i}$ and ${\beta _i}$ are within the range of [0, 1]. If both ${\alpha _i}$ and ${\beta _i}$are equal to 1, the satisfaction function graph takes the shape of a standard isosceles trapezoid, which indicates that customers are much more sensitive to distribution time.

Subsequently, a penalty cost will occur if the fresh products are delivered to the customers earlier or later than their expected time window. As shown in Figure 3, if the distribution vehicle arrives earlier than the customer time window$e{t_i}$, it results in penalty cost ${\varphi _1}$. Also, if the vehicle arrives later than $l{t_i}$, it results in a much higher delay-penalty cost ${\varphi _2}$, because customers might be much more sensitive to delayed distribution than earlier arrival. The delay- and early-penalty cost function ${f_5}$ is represented in the following Eq (17) and is embodied in the objective function Eq (1).

4.   Two-stage dynamic algorithm solution design

As an Nondeterministic Polynomial-hard (NP-hard) problem, the multi-objective VRP is difficult to be solved by exact algorithms. Therefore, heuristic algorithms are usually used. Considering fresh-product distribution practices based on the comparison of the performance of different heuristic algorithms in solving VRP, this paper proposes a two-stage algorithm to solve the fresh-product multi-objective dynamic VRP. The flowchart of the two-stage algorithm is shown in Figure 4. In the first static stage, the initial distribution strategy is obtained by an improved MOPSO algorithm with the advantage of a fast calculation capability and simplicity. In the second dynamic stage, the dynamic updated strategy is obtained based on a dynamic insertion mechanism that is used to locally adjust the initial optimal route solution by periodically inserting newly placed customer orders.

4.1.   Proposed MOGAPSO algorithm

In the first static stage, we design an improved MOGAPSO algorithm to solve the vehicle routing optimization model for fast and efficient fresh-product distribution. The MOPSO algorithm is one of the most common algorithms for solving multi-objective optimization problems ^[11,12], having many advantages including its simplicity, fast calculation speed, and easy implementation. However, the MOPSO algorithm is easy to converge to the local optimum. The GA is characterized by rich population diversity and robustness. Therefore, we introduce a GA into the standard MOPSO algorithm to improve the diversity of the particle swarm population. In order to further improve the global search capability of the algorithm, in this paper, an improved MOGAPSO algorithm is proposed by introducing the order crossover (OX) and multiple mutation (MM) operations of the GA into the standard MOPSO.

4.1.1.   Particles encoding and decoding

A swarm of particles are potential solutions for fresh-product-distribution vehicle routes. We use natural number coding to represent the sequence by which distribution vehicles serve customers. Specifically, we assume that the total number of customers served by the fresh-product distribution enterprise is N and the maximum number of distribution vehicles is M; the length of the encoding particle is N + M + 1. The customer points are represented as the natural numbers (2...N) and the distribution center is represented as a natural number 1. For example, the vehicle routing solution 1-3-9-2-5-1-4-7-1-6-8-1 represents distribution routes in which three vehicles distribute fresh products for eight customers. The first vehicle departs from the distribution center and passes through the customer points 3, 9, 2, and 5, and finally returns to the distribution center. The second vehicle departs from the distribution center and passes through the customer points 4 and 7 and then returns to the distribution center. The third vehicle departs from the distribution center and passes through the customer points 6 and 8 and then returns to the distribution center.

4.1.2.   Internal particle swarm updating method

The particle is updated at each iteration to ensure population diversity, which uses the genetic algorithm's OX and MM operations ^[19]. For the personal best particle $pbest$ in each generation, the principle of "accepted based on probability for non-dominated solution" is applied. The personal best particle $pbest$ is updated when there is a new particle that dominates the current $pbest$; otherwise, the decision on whether the new solution is accepted might be based on the probability.

4.1.3.   External archive particle selection and updating

When solving the multi-objective vehicle routing optimization problem for fresh-product distribution, the Pareto optimal solutions have to be obtained, which indicates that none of the objectives can be further improved without deteriorating other objectives ^[11]. The non-dominated solutions are stored in an external archive. All solutions in the Pareto front are calculated by objective functions Z₁ and Z₂. In order to achieve the multiple objectives of minimizing distribution cost Z₁ and maximizing customer time satisfaction Z₂, it is necessary to select a proper particle in the external archive, which could lead the optimal solution set close to the Pareto front. In this paper, the global best particle $gbest$ is selected using the adaptive grid method.

For two objective functions Z₁ and Z₂ in this vehicle routing optimization problem for the J company's fresh-product distribution, the target solution space is divided into n_* n grids as shown in Figure 5. The width of a grid of objective functions Z_i (i = 1, 2, ..., n) is calculated as the following Eq (18).

where $\max \, {Z_i}(x)$ and $\min {Z_i}(x)$ represent the maximization and minimization values of objective functions Z_i. The non-dominated solutions in an external archive are assigned into n_* n grids. The global best particle $gbest$ is selected from a good sparse quality grid, which is calculated on particle quantities in each grid.

Furthermore, the global best particle $gbest$ is updated in each iteration cycle by making a non-inferiority comparison between newly generated populations and the external archive population.

The detailed calculation steps for the proposed MOGAPSO algorithm shown in Figure 4 are as follows, while the dynamic insertion mechanism will be discussed in Section 4.2.

Step 1: Obtain the basic parameters of the algorithm, generate the initial population$P$, calculate the fitness value of the particles in the population under each objective, and determine the global best particle ($gbest$) and the personal best particle ($pbest$).

Step 2: Particle external update operation. Set the algorithm's iteration times $t = 1$ and execute a particle update cycle. All particles in the population are implemented with crossover and mutation operations with $gbest$ and $pbest$ until the iteration times are larger than particle populations N.

Step 3: Compare the non-inferiority relationships within the particle populations. Update the $pbest$ in particle swarm populations and the $gbest$ in the external archive.

Step 4: If the number of particles in the external archive exceeds the maximum limit, trim the external archive.

Step 5: If the number of external iteration times $t$ exceeds the maximum limits, it could output the Pareto front solution, which will be the initial optimized distribution routes for dynamic stage.

4.2.   Dynamic insertion mechanism

In the second dynamic stage, fresh-product orders dynamically placed by online customers are periodically inserted into the initial distribution routing optimization solution by the dynamic inserting mechanism ^[17], as shown in Figure 6. Specifically, the working day T during which new fresh-product orders could be accepted is divided into a series of customer orders processing time slices ${T_i}\, (i = 1, 2, \ldots n)$ with equal length $\left( {{T \mathord{\left/ {\vphantom {T i}} \right. } i}} \right)$. Also, fresh-product orders are collected during each working day. The fresh-product order requirements are periodically processed at the customer order processing times $t{\text{ + }}{T_1}, t + {T_2}...t + {T_n}$. This dynamic insertion mechanism transforms the dynamic VRP for fresh-product distribution into a series of static vehicle routing subproblems ^[17].

The dynamic insertion mechanism is used to insert new orders periodically into the initial routing optimization solution by greedy insertion algorithm and to make local improvements to the selected initial solution. It is necessary to maintain the original customer time satisfaction as much as possible while meeting orders from new customers, and ultimately generating an optimal dynamic solution. The detailed steps of dynamic insertion mechanism in the second dynamic stage of the two-stage algorithm shown in Figure 4 are as follows.

Step 1: Identify the current vehicle routes L and all newly added customer points list G in the current period.

Step 2: Record the current time t and obtain customer order points list K that have been serviced or are being serviced. Remove the customer order points in K from the initial vehicle routes L and obtain the list of available customer order points that could be inserted (L-K).

Step 3: Randomly select an order $i$ from the newly added customer points list G and insert it into the list (L-K). Since the last point is the distribution center, there are L-K available insertion points for newly added customer order points.

Step 4: Record the additional cost added to the distribution route after inserting each newly added customer point. If there is an insertion point that violates the time constraints, it is directly discarded to ensure the arrival time of the distribution vehicle for regular customers. The optimal insertion point with the lowest cost is recorded.

Step 5: Repeat Steps 3 and 4 until newly added customer points list G is empty. Then, we output all the best insertion point schemes and update the initial vehicle route L.

5.   Case study

5.1.   Case description

We conduct a case study on fresh-product-distribution routing optimization for the J fresh-product distribution company in Shenzhen, China, based on the proposed model (3.3) and methods (4.1 and 4.2). The J fresh-product distribution company provides warehousing and distribution of fresh products including frozen meat, frozen seafood, vegetables, fruits, and so on. J company aims to quickly distribute fresh products with cold-chain trucks to their time-sensitive customers to keep the freshness of their fresh products, with the objectives of maximum customer satisfaction and minimum distribution cost. In this section, the practicality of the fresh-product-distribution routing optimization model (3.3) and methods (4.1 and 4.2) proposed in this study are tested in J fresh-product distribution company. As in our trial, the fresh-product demand is dynamically changing during the working day, with J company receiving orders both from regular customers and online customers with heterogeneous time sensitivity. The cold-chain truck can distribute fresh products to several customers at diverse speeds in different traffic conditions.

We used the real fresh-product distribution data of J company from its distribution center in the Guangming district of Shenzhen city in one working day (June 1st, 2016), referring to Chen and Li ^[20]. There are 33 customer data points used in our study in total, including static and dynamic demand as in our trial. The distribution center has 24 regular customers (retail stores), whose fresh-product orders are taken as static demand data in this study. During that working day, another 9 new customers placed fresh-product orders and 4 regular customers changed orders, which are taken as dynamic demand data in this study.

The number of refrigerated vehicles performing distribution services at the J company's distribution center is $m$ = 10, and the maximum capacity of the vehicles $Q$ = 3.0 tons. In the first static stage, vehicle speed was set as a fixed speed of 40 km/h. In the second dynamic stage, the vehicle speed changes with traffic volume in different distribution time periods. The fresh-product distribution period from 4:00 a.m. to 9:00 a.m. was divided into five segments according to the local traffic volume. Vehicle speed$v$was 50 km/h at [4:00, 5:00], 45 km/h at [5:00, 6:00], 40 km/h at [6:00, 7:00], 35 km/h at [7:00, 8:00], and 30 km/h at [8:00, 9:00]. In Table 2, the detailed parameters in the multi-objective distribution routing model are set as practical values in the J company.

We collected fresh-product orders from regular retail stores that are submitted by customers before 12:00 a.m. There are 24 retail stores taken as customer points on the experiment working day. The latitude and longitude of the customer points and the distribution center were obtained from the Gaode map open platform. The relative positions of customer points were correspondingly transformed in the MATLAB coordinate system as shown in Figure 7. The distribution center was represented by a triangle and customer locations were numbered from 1 to 24. The 9 newly added customers during the working day were numbered from 25 to 33.

The fresh-product order data of the 24 regular customers, including order demand for each customer, the expected distribution time window, the acceptable time window, and the service time, are shown in Table 3.

The time sensitivity of customers is different on fast distribution services. Therefore, it is assumed that the time-sensitivity coefficient ${\alpha _i}$, ${\beta _i}$ are equal to 1 for highly time-sensitive customers, who are much more sensitive to the distribution time and have purchased the instant-distribution service. These highly time-sensitive customers desire to receive the fresh products within the expected time window $\left[{e{t_i}, l{t_i}} \right]$. For the highly time-sensitive customers who have not purchased the instant-distribution service, the time-sensitivity coefficient ${\alpha _i}, {\beta _i}$ is set as 0.6. The time-sensitivity coefficient ${\alpha _i}, {\beta _i}$ of customers who are less sensitive to the arrival time of fresh products is set as 0.4. In this case study, the time-sensitivity coefficients are different between the 24 customers, as listed in Table 3.

5.2.   MOGAPSO algorithm results and comparison

To test the effectiveness of the improved MOGAPSO algorithm, we compared its simulation results with the NSGA-Ⅱ (non-dominated sorting genetic algorithm Ⅱ) and standard MOPSO algorithms. The calculation was iterated 500 times for three comparison algorithms. Moreover, the target solution space parameter of the improved MOGAPSO was set as 10 × 10 grids for two objective functions of total cost and customer time satisfaction. We used MATLAB 2018b for programming and ran it on an Intel(R) Core(TM) i5-7300HQ CPU computer. The Pareto front comparison results of three algorithms are shown in Figure 8. The optimal solutions of the improved MOGAPSO algorithm indicate higher density than the standard MOPSO algorithm. These experiment results demonstrate that the OX and MM operations introduced into the improved MOGAPSO algorithm could effectively improve the diversity of the particle swarm population to converge the global optimum. The Pareto optimal solutions of the improved MOGAPSO algorithm are located in the left area of Figure 8, presenting better performance on distribution-cost reduction than the NSGA-Ⅱ and standard MOPSO algorithms. Also, the proposed MOGAPSO algorithm improved by the GA demonstrates good convergence capability by denser global optimums in Figure 8, which is close to the results of NSGA-Ⅱ and greatly better than the optimum results obtained from MOPSO algorithms.

We compared the improved MOGAPSO algorithm with the NSGA-Ⅱ and standard MOPSO algorithms. As shown in Figure 9, the experiment results show that the improved MOGAPSO algorithm is superior to the other two on freshness cost, delay- and early-penalty cost, total distribution costs, and customer time satisfaction. Especially, the delay- and early-penalty cost of optimal distribution routing solution deduced from the improved MOGAPSO algorithm is reduced to 28.2, which is much lower than in the NSGA-Ⅱ (135.77) and MOPSO algorithms (163.77). This indicates that the improved MOGAPSO algorithm could solve the optimal distribution routes, helping to quickly and timely distribute fresh products within a short time window. The runtime of the improved MOGAPSO algorithm is 72.4 s, which is much faster than the NSGA-Ⅱ algorithm (129.72 s) and slower than the MOPSO algorithm (40.90 s). These numerical simulation results show that the improved MOPSO algorithm has the advantage of fast calculation speed. Also, the MOGAPSO algorithm demonstrates better performance on convergence to the global optimum improved by the GA.

5.3.   Sensitivity analysis

The sensitivity analysis was performed to explore the impact of coefficient changes on the performance of the improved MOGAPSO algorithm for fresh-product-distribution routing optimization ^[21]. Considering the characteristics of fresh products, the freshness coefficients in the distribution and uploading processes and order demand changes may have an influence on the performance of fresh-product-distribution routing optimization.

We adjust the freshness coefficient in the distribution process by decreasing from 0.9999 to 0.9600. Specifically, the freshness coefficient in the distribution process is set as 0.9999, 0.9900, 0.9800, 0.9700, and 0.9600. As shown in Figure 10, the results demonstrate that the total fresh-product distribution cost will increase as the freshness coefficient in the distribution process decreases. We adjust the freshness coefficient in the uploading process by increasing from 0.9360 to 0.9700. As shown in Figure 10, the results demonstrate that the total fresh-product distribution cost will decrease as the freshness coefficient in the uploading process increases. Therefore, the sensitivity analysis' results show that the fresh-product distribution cost may increase as the freshness decreases in the distribution and uploading processes. Thus, the cold-chain performance of fresh-product-distribution vehicles on keeping freshness during the distribution process is critical to reduce total fresh-product distribution costs. Moreover, the J company should enhance fast-services training on uploading employees to reduce uploading time and freshness loss, and consequently to reduce total fresh-product distribution costs.

The order demand for fresh products may explode when retail stores make special promotions on shopping festivals like Double Eleven. The sensitivity analysis was performed by setting demand growth as 10, 20, 30 and 40%. As shown in Figure 11, the total distribution cost will increase as the demand increases, and customer satisfaction will decrease as the demand increases. Therefore, the dynamic mechanism that will be designed to optimize distribution routes in Section 5.4 is critical to practical demand-changing scenarios to improve distribution performance.

5.4.   Dynamic insertion mechanism experiment

According to the actual situation, new fresh-product orders are generated online from time to time. In the numerical experiment, on the second dynamic optimization stage, nine newly added customers are dynamically inserted into the initial optimal routes solution for regular customer points obtained from the first static optimization stage. The dynamic inserting algorithm is applied to optimize distribution routing in a series of processing time slices that are set as a fixed time interval of 40 minutes. The dynamic distribution routing optimization is implemented three times every day in three updating time intervals: 4:40, 5:20 and 6:00. The nine customers who placed new fresh-product orders are marked as number 25 to number 33 in Table 4 and Figure 7. In this case study, new orders from customer points 25–27 are received in the time interval 4:40–5:20. New orders from customer points 28–30 are received in the time interval 5:20–6:00. New orders from customer points 31–33 are received in the time interval 6:00–6:40. Moreover, four regular customers who have already placed fresh-product orders in the previous working day dynamically increase or decrease fresh-product orders in the working day, as shown in Table 5.

Initial optimal distribution routes solution for fresh products are solved by the improved MOGAPSO algorithm in the first static stage, as shown in Table 6. The distribution center assigned the fresh-product distribution for 24 customer points to five cold-chain distribution vehicles. The customer time satisfaction reaches 86.3% on the initial optimization solution for five vehicle distribution routes. In the second dynamic stage, nine newly added customer points are inserted into the initial optimal distribution routes. Applying the dynamic inserting algorithm, the dynamic optimization solutions for fresh-product-distribution routing are updated three times at 4:40, 5:20, and 6:00 respectively as shown in Table 7. In Table 7, the italics text in brackets indicates the new customer points that have been inserted into the initial optimal distribution routes. The bold numbers in the third column are customer points whose orders have been delivered before the updating time. The bold numbers in the fourth column demonstrate the arrival time of vehicles that have finished their distribution tasks before the updating time.

For fresh-product-distribution vehicles that have already departed to customer points, the system will subsequently insert newly added customer orders into their initial optimal distribution routes obtained from the first MOGAPSO stage. There are three newly added customer points (25, 26 and 27) at the updating time 4:40 when five distribution vehicles have all departed to serve customer points at the travel speed of 50 km/h. As shown in Table 7, optimized with the dynamic inserting algorithm, the newly added customer point 25 is inserted into the initial distribution route for vehicle 2, which makes its travel cost increase by 147.4 Yuan. Newly added customer points 26 and 27 are also inserted into the initial distribution route for vehicle 5, which makes its travel cost increase by 312.19 Yuan. Similarly, the three newly added customer points 28, 29, and 30 at the updating time 5:20 are inserted into the initial distribution route for vehicle 1 at the speed of 45 km/h, which makes its travel cost increase by 193.04 Yuan. The three newly added customer points 31, 32, and 33 at the last updating time 6:00 are inserted into the initial distribution route for vehicles 1 and 3 at the speed of 40 km/h. The travel costs for vehicle 1 increase by 285.43 Yuan and for vehicle 3 by 159.65 Yuan. Moreover, the travel distance becomes longer for the dynamic optimization solution of vehicle routes after inserting newly added customer points, which makes the customer time satisfaction decrease a little to 82.3%.

5.5.   Dynamic solution comparison

To demonstrate the effectiveness of the dynamic inserting algorithm, we compare the two-stage dynamic distribution routing optimization solution with a static distribution solution for newly added customer orders in the working day. In the static solution, two additional distribution vehicles, 6 and 7, are assigned to deliver fresh-product orders for nine newly added customer points. The distribution routes for the additional vehicles 6 and 7 are listed in Table 8 with their travel distance and cost. Moreover, the comparisons of various costs between the dynamic and the static solutions are shown in Figure 12.

The dynamic solution for fresh-product-distribution routing demonstrates a better performance on the reduction of freshness-loss cost, cold-chain-refrigeration cost, delay- and early-penalty cost, and total distribution cost as shown in Figure 12. Dynamic solutions for fresh-product-distribution routes could save a total distribution cost of RMB 676.73, which makes up a reduction of 12.6%. Therefore, a two-stage strategy combining the improved MOGAPSO algorithm and the dynamic inserting algorithm could efficiently reduce distribution costs for fresh products. Our research in this paper provides a scientific methodology for distribution vehicle routing optimization for fresh-product enterprises.

6.   Conclusions

Considering the freshness requirement and fast distribution characteristics, we proposed a multi-objective vehicle routing optimization model for fresh-product distribution to comprehensively minimize freshness-loss cost, cold-chain-refrigeration cost, delay-penalty cost (including early-penalty cost), and distribution cost, and maximize customer time satisfaction. Moreover, we designed a two-stage solution with an improved MOGAPSO algorithm and dynamic inserting algorithm to quickly solve out optimal vehicle routes for fresh-product distribution under dynamic demand practices. Finally, a case study was conducted on a fresh-product distribution company in Shenzhen, China, to validate the practicality of the proposed vehicle-routing optimization model and improved algorithms.

The numerical simulation results on practical data indicated that the proposed MOGAPSO algorithm could solve optimal distribution routing solutions with lower total distribution costs and higher customer time satisfaction than the NSGA-Ⅱ and MOPSO algorithms. The delay- and early-penalty cost of the optimal distribution routing solution deduced from the proposed MOGAPSO algorithm was reduced to 28.12, which is much lower than the NSGA-Ⅱ (135.77) and MOPSO (163.27) algorithms. The dynamic insertion algorithm can periodically update the optimal distribution routing solution for newly added customer orders with a total distribution cost reduction of 12.6%. Our research provides a practical and efficient solution for fresh-product-distribution enterprises to improve customer satisfaction and reduce distribution costs.

The fresh-product distribution faces complicated scenarios in reality, such as road complexity or extreme weather conditions, which might be taken into account in future research. The cold-chain temperature conditions are different for various types of fresh products. Also, there are diverse types of distribution vehicles on different refrigerated conditions and dimensions in fresh-product distribution. Therefore, mixed fleets with multiple vehicles might be explored in the vehicle routing optimization problem. Furthermore, emerging blockchain technology applications could be analyzed in future research.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (71872038 and 71832001). We are grateful to anonymous reviewers for their valuable comments and suggestions, which greatly improved the presentation of this paper.

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this study.