Research on time-varying path optimization for multi-vehicle type fresh food logistics distribution considering energy consumption

The model discussed in this paper is characterized by its NP-hard nature and is designed as an optimization model for fresh food logistics distribution with time windows, damage rates, and time-varying transportation speeds. It involves numerous variables, objectives, and constraints, with a large solution scale and multiple objective functions. Given these complexities, a heuristic search algorithm suitable for solving this model is proposed.

The Genetic Algorithm (GA) is a population-based search algorithm inspired by the concept of “survival of the fittest”, known for its strong parallel computing and global search capabilities, and its ease of implementation in large-scale combinatorial optimization problems. However, when applied to the layout optimization model for shared bicycle parking zones with multiple constraints, the basic GA encounters several issues due to the increased complexity from the additional constraints in formulas (2) through (17):

1.

Poor Local Search Capability: After several generations of evolution, the similarity between individuals increase, leading to new individuals that are highly similar and thus failing to generate truly new solutions.
2.

Premature Convergence: GA tends to converge prematurely, often struggling to reach the optimal solution.

Tabu Search (TS) starts with an initial feasible solution and explores a series of specific search directions, selecting the move that maximizes changes in the objective function. The key feature of TS is its strong local search capability, achieved through local neighborhood search and the introduction of tabu lists and aspiration criteria, which prevent redundant searches and allow rapid convergence to a local optimum. To address the limitations of the traditional GA, this study introduces a TS mechanism into the GA framework, creating a TS-GA Hybrid Algorithm that combines GA’s global search capability with TS’s neighborhood search capability. By incorporating local search improvements and tabu strategies, the hybrid algorithm avoids the drawbacks of getting trapped in local optima, thereby enhancing global optimization capability. This approach reduces the reliance on an optimal initial population, effectively preventing premature convergence, and is more suitable for solving large-scale, complex multi-constraint combinatorial optimization problems. Consequently, this paper proposes a TS-GA Hybrid Algorithm with K-means clustering to solve the previously constructed model. The algorithm steps are shown in Fig. 4.

Table of Contents

Design of time-varying path

In practical distribution processes, road network traffic speed often has time-varying characteristics. However, for simplicity and feasibility of calculation, the total daily time is subdivided into $\rho$ periods, denoted as $P=\ d_p$. The start and end times for period $d_p$ are $[O_p – 1,O_p]$. During the p–th period, the driving speed $v_p$ of all vehicles is constant, calculated as $v_p={v_o \mathord{\left/ \vphantom v_o \gamma _p \right. \kern-0pt} \gamma _p}$, where $v_o$ is the ideal vehicle speed and $\gamma _p$ is the traffic congestion delay coefficient for the p-th period. The relationship between speed and time is depicted in Fig. 5.

If the total duration of period p is $H_p$, then the feasible driving time for that period is $K_p$, satisfying$K_p=O_p – O_p – 1$, and the feasible driving distance is $L_p$. The shortest distance between delivery points i and j during period p is $d_ij^p$, satisfying $d_ij\text=\sum\nolimits_p d_ij^p$, where $d_ij^p$ is the effective driving distance for period p. Additionally, $D_ij^p$ represents the remaining distance to be covered after period p along the route $(i,j)$, and $T_ij^p$ is the effective driving time within period p. The steps for calculating the travel time in a time-varying road network are as follows.

Step 1 Calculate the initial travel distance for the vehicle during its initial period as $d_ij^p=v_pK_p$. If $d_ij^p \geqslant d_ij$, then $T_ij^p={d_ij \mathord{\left/ {\vphantom d_ij v_p} \right. \kern-0pt} v_p}$ and proceed to Step 4. Otherwise, $D_ij^p=d_ij – d_ij^p$ and $T_ij^p=K_p$.

Step 2 Set a constant $\zeta =1$.

Step 3 The vehicle travels during period $p+\zeta$ with $d_ij^p+\zeta =K_p+\zeta \cdot v_p+\zeta $. If $d_ij^p+\zeta \leqslant D_ij^p+\zeta – 1$, then $T_ij^p=K_p+\zeta $, $D_ij^p+\zeta =D_ij^p+\zeta – 1 – d_ij^p+\zeta $, iterate $\zeta$ by setting $\zeta =\zeta +1$, and repeat Step 3. Otherwise, $T_ij^p+\zeta ={{D_ij} \mathord{\left/ {\vphantom {{{D_ij}} v_p}} \right. \kern-0pt} v_p}$ and proceed to Step 4.

Step 4 Calculate the total travel time T for the entire route, denoted as $T=\sum\limits_p \in P {T_{ij}^p}$.

Clustering design of Tabu search

To address the challenge of searching through a large number of customer nodes in VRP studied in this paper, and to further improve the solution quality, the tabu Search algorithm incorporates the K-means clustering algorithm. This clustering technique groups customer nodes that are close in spatial location and time windows, allowing the delivery route planning process to consider clusters of customers as a single delivery unit.

Based on the design of the TS-GA hybrid algorithm, the tabu search component is constructed utilizing a tabu search algorithm based on K-means clustering. The specific implementation process is as follows:

Utilizing an enhanced K-means algorithm based on penalty functions associated with customer spatial location, time window constraints, and freshness, we conduct clustering operations on customer points. Determine q clustering units. Taking into account customer spatial location and time constraints, construct the customer point clustering graph as illustrated in Fig. 6. Divide the delivery timeline into 4 time slots, denoted as$t_1,t_2,t_3,t_4$ (representing $A^allow,A^best,B^best,B^allow$ respectively). Represent geographical locations and temperature control ranges on the X-axis and Y-axis, respectively. Establish a tabu set R containing customer time windows. When a customer does not satisfy the tabu set R, consider conducting customer clustering operations. Within each layer of ellipses’ spatial regions, if the customer’s time window requests fall within the same time slot, consider clustering the customers into a single delivery unit.

The enhanced K-means algorithm process is described as follows:

Step 1: Establish an initial taboo set R. Customers whose attributes do not satisfy the conditions of set R are eligible to participate in clustering.
Step 2: Import the relevant customer data.
Step 3: Convert the data matrix into a data vector.
Step 4: Determine the initial number of clustering units q, based on the K-means clustering algorithm and select q initial clustering centers.
Step 5: Assess whether the clustering criteria between prospective and already clustered customers meet the conditions of the taboo set R. If the conditions are not fully met, assign each customer to the clustering unit whose center is closest to that customer; otherwise, proceed to Step 7.
Step 6: Update the centers of each clustering unit.
Step 7: Increase the number of clustering units to $q \to q+1$ and generate new clustering units and centers.
Step 8: Repeat Steps 6 and 7 until the cluster affiliations of each customer no longer change.

Algorithm design for the genetic part

Encoding method

In general, the solution is typically encoded as a natural array with specific design rules, when applying genetic algorithms to optimization problems.

This paper uses an integer sequence vector to represent the fresh food logistics delivery route scheme. The initial chromosome, denoted as ‘$chrom$’, is designed as follows:

$$chrom=[x_1,x_2, \ldots ,x_i, \ldots x_n]$$

Where, each gene locus in the chromosome takes on a random integer value between 1 and n, with the constraint that no two gene loci have the same value, i.e., $x_i \ne x_j,i \ne j$. Since a single chromosome ‘$chrom$’ contains the routes for multiple vehicles, during decoding, it is possible to decompose the chromosome into several segments based on the cargo demands of different customer sites and the load capacities of various vehicle types. Each segment represents the route of a delivery vehicle, and the number of segments corresponds to the number of deployed delivery vehicles.

Fitness function

The fitness of a chromosome is determined by the combined costs of transportation, energy consumption, carbon emissions, refrigeration, freshness-related cargo loss, and penalties for violating delivery deadlines. During the execution of the genetic algorithm, some chromosomes in the population may not satisfy all constraints. To account for such cases, a penalty function is introduced in the fitness function of the chromosome.

In this paper, when calculating the fitness value of a chromosome, a penalty coefficient M and a step function $J(x)$ are introduced for gene values that exceed limits or are infeasible. Specifically, if the delivery route scheme x corresponding to the chromosome satisfies all constraints, then $J(x)=0$. Otherwise, $J(x)=1$.

The penalty coefficient and the step function are incorporated into the objective function as follows:

$$F(x)=M \cdot J(x)+C(x)$$

(18)

Genetic operators

The selection operator is based on the roulette wheel principle, where high-quality individuals are selected to be carried over to the next generation.

The crossover and mutation operators are illustrated in Fig. 7. Specifically, the crossover operator uses an inversion mechanism with a predefined crossover probability $P_c$. The mutation operator employs a swapping mechanism with a predefined mutation probability $P_m$.

TS-GA hybrid algorithm steps

The fundamental steps of the TS-GA Hybrid Algorithm are as follows:

Step 1 Utilize an improved K-means algorithm based on factors such as customer coordinates, demand, and time windows to cluster customer points, thereby assigning all customers into q cluster units.
Step 2 Generate an initial population through chromosomal encoding derived from the clustering process, specifying the population size as $inn$, the maximum number of iterations as $maxgen$, crossover probability $P_c$, mutation probability $P_m$, and the length of the Tabu list as l.
Step 3 Calculate the fitness values of individuals within the population. The objective functions in this study aim to minimize transportation costs for delivery vehicles, minimize penalty costs for exceeding time windows, and reduce delivery mileage. The fitness function $f(x)$ is defined accordingly.
Step 4 Account for the time window constraints of customer points. Select elite individuals from the population to serve as parents for the next generation using a roulette wheel selection method.
Step 5 Perform crossover and mutation operations on the population according to the defined probabilities Pc and Pm to form a new population. For offspring that violate time window constraints, generate new fitness values $f(x)$ incorporating penalty costs.
Step 6 Apply the Genetic Algorithm (GA) procedures to the chromosomes, conduct Tabu Search to generate initial neighborhood solutions, identify candidate solutions, and update the Tabu list, iterating to optimize the solutions.
Step 7 Repeat the processes in Steps 3 and 6 in a cycle. Continue iterations until the algorithm reaches the maximum number of iterations $maxgen$. Conclude the algorithm and output the optimal results.

Time complexity analysis

In this paper, the time complexity of the algorithm is expressed as a function of the number of nodes nn, which describes the number of basic operations required to complete the computational tasks when the number of nodes is nn. Traditional genetic algorithms often struggle to converge to the global optimum and are typically assumed to terminate when the maximum number of iterations is reached. Therefore, the time complexity of traditional genetic algorithms can be approximately described as $O(maxgen \times inn)$, indicating that it is constant with respect to the number of iterations allowed.

In the paper, the Tabu Search algorithm mainly includes operations such as generating initial solution, creating neighborhoods, assessing Tabu list, and lifting bans. Each step’s time complexity is listed in Table 3 as follows:

Table 3 Tabu search algorithm operation.

In the TS-GA hybrid algorithm, the time spent on generating neighborhoods and evaluating fitness values significantly exceeds the time consumed by other operations. As such, the computational time required for generating initial solutions, forming candidate sets, and updating the Tabu list can be disregarded. The TS-GA algorithm employs genetic mutation operators to generate neighborhoods for the initial solutions. These mutation operators are inherently stochastic, and the time complexity of the TS-GA algorithm is determined using methods suitable for analyzing the complexity of random algorithms, resulting in a time complexity of $O[maxgen \times (inn^2+inn+l)]$³⁰.

link