2.1

Problem optimization

The essence of the transportation optimal path optimization problem is a scientific and reasonable logistics transportation path⁷, such as the shortest transportation time, the shortest path, the lowest distribution cost, and to a certain extent, it meets the constraints, such as the maximum load of vehicles, the completion time of transportation, etc. The optimal path optimization problem of logistics transportation can be described by the directed graph f= (m, n). Users and transportation points are M = {m₀, m₁, m₂, ⋯ m_n}; The directed arc between the user and the transportation point is expressed by P = {(m_x, m_y)|m_x, m_y, x ≠ y}. The structure of the optimal path optimization problem of transportation is shown in figure 1 below.

Figure 1.

Optimal path optimization of transportation.

2.2

Model optimization

The mathematical model of transportation optimal path optimization can be expressed by equation (1):

In the formula, n is the number of users, u is the number of vehicles, Z is the number of vehicles, and the constraints of the transportation optimal path optimization problem are as follows:

If the vehicle accesses user x only once, then ΣΚ_zx = 1; The demand for goods at the user point is p_x. Then the total demand is required to be controlled within the maximum capacity of all vehicles in the transportation and distribution center, then Σ(p_x, k_zx) < P, and the directed arc weight on J is expressed as J_xy, when the z-th vehicle passes the directed arc (m_x, m_y), it is expressed as i_xyz=1, when i_xyz=1, it means that the z-th vehicle passes through the directed arc, when i_xyz=0, it means that the z-th vehicle has not passed the directed arc.

3.1

Traditional ant colony algorithm and model

Suppose m is the number of ants and ρ_ij (t) is the pheromone concentration on path(i,j) at time t. All ants start from the starting point of path planning, and each ant calculates the transition probability according to the pheromone concentration on each path adjacent to the node i when selecting its travel path. The transition probability of ant K (k=1, 2, 3⋯, n) from node i to node j at time t:

In equation (2), represents the transition probability of ant K between road nodes I and j at time t; [σ_ij(t)]^β Represents heuristic function; [p_ij(t)]^α Represents the pheromone concentration of the ant’s corresponding path between road nodes I and j, A_k = {N – t_k} indicates ant a_ K represents the set of road nodes that ants want to visit; α, β represent the relatively important measurement factor of heuristic function factor and pheromone quantity in the transfer rule.

3.2

Improved heuristic function

The heuristic function in the traditional ant colony algorithm ignores the guidance of the direction of ant traversal⁸. Therefore, it will fall into the local optimum and cannot reach the overall optimum⁹. Therefore, Reference¹⁰ introduces the Euclidean distance between the next node and the target node in the heuristic function, so as to strengthen the connection between the current node and the target node.

The improved heuristic function is:

In equation (3), d_je is the Euclidean distance from node j to node e, and d_ij is the Euclidean distance between node i and the next node j. in this way, setting the heuristic function strengthens the directionality of the search path and shortens the search time.

3.3

Improved ant colony algorithm pheromone

Transportation time, transportation cost and average road smoothness are important factors affecting the optimal route selection¹¹. Therefore, this paper establishes a mathematical model of multi condition constraints based on three factors: transportation time, transportation cost and road smoothness, and combines ant colony algorithm to realize the optimal path selection under multi condition constraints.

3.3.1

Transportation Cost Pheromone.

The transportation cost pheromone can be expressed by equation (4):

In equation (4), W₁ (i) stands for transportation into pheromone, which refers to the ratio between the cost required for transportation at node i and the estimated maximum cost. The larger its value is, the higher the actual transportation cost is, C_i represents the cost of transportation at node i, C_imax represents the estimated maximum cost, where, C_i = A_i + T_i + F_i, A_i, T_i and F_i represent road transportation loss cost, toll cost and fuel cost respectively.

3.3.2

Transport Time Pheromone.

The transport time pheromone can be expressed by equation (5):

In equation (5), represents the transportation time pheromone, which refers to the ratio between the time required for transportation at node i and the expected maximum time. The larger the value, the longer the transportation time. T_i time required for transportation, T_imax is the maximum time allowed in transportation.

3.3.3

Smooth Transportation Environment Pheromone.

The pheromone of smooth transportation environment can be expressed by equation (6):

In equation (6), W₃ (i) represents the smooth pheromone of the transportation environment, which refers to the ratio between the smoothness of the path of transportation at node i and the minimum tolerance of the smoothness of the road. The larger its value, the smoother the selected path of the transportation vehicle, and the higher the actual transportation cost, S_i represents the smoothness of the transportation path at node i, S_imax represents the minimum tolerance of road patency.

Therefore, the constraint function is:

In equation (7), τ, φ, ω Respectively represent the actual proportion of the cost, time and road smoothness of transportation at node I.

3.3.4

Improve the Best and Worst Path.

In this algorithm, some penalty factors are added to reduce the probability of poor path selection, so as to strengthen the concentration of better path pheromones and let ants choose the path with the best quality. The pheromone updating improvement of this algorithm is shown in equation (8):

In equation (8), ρRepresents the pheromone enhancement factor of the improved ant colony algorithm and introduces parameters ϕ, ϕ ∈ [0,1] is used to strengthen the pheromone on the traversed optimal path。 L_best represents the best path traversed, |L_best| represents the path length; L_worst represents the worst path traversed|L_worst| represents the path length.

4.1

Problem description

Suppose there is a transportation center with 20 customers who need to transport goods, numbered 1-20. The location of the transportation center (numbered 0, coordinates (5, 30) needs to transport goods to these customers every day. The number of vehicles that can be dispatched by the transportation center every day is 3. For the convenience of testing, the location of the transportation center and the location coordinates of 20 customers are mapped to the xoy plane, as shown in Figure 2. The location coordinates of each customer and the volume of goods transported every day are shown in Table 1.

Figure 2.

Coordinate diagram of chain stores and warehouses.

Table 1.

Location coordinates of chain stores and cargo demand.

4.2

Simulation results and analysis

In order to verify whether this algorithm has some advantages over other algorithms in terms of optimal path length and iteration times. Figures 3-5 are the experimental results of genetic algorithm, ant colony algorithm and this algorithm respectively. From the experimental results, the optimal path obtained by this algorithm is the shortest and the number of iterations is the least.

Figure 3.

Optimal path and iteration times of genetic algorithm.

Figure 4.

Optimal path and iteration times of traditional ant colony algorithm.

Figure 5.

The optimal path and iteration times of the improved algorithm.