|
1.INTRODUCTIONIn transportation, optimal path planning refers to the planning process with the minimum total cost from the starting point to the target point. It is one of the important directions in the field of intelligent transportation. The commonly used algorithms for optimal path planning include Dijkstra algorithm and breadth first search method1. In recent years, with the continuous emergence of intelligent technology, many scholars use the swarm bionic theory to help solve the optimal path planning problem. The algorithms adopted mainly include ant colony algorithm, genetic algorithm and other combinations of algorithms2. Ant colony algorithm is to simulate the cooperative foraging behavior of ants3. The disadvantage of ant colony algorithm is that it is easy to fall into local optimal solution. In view of its shortcomings, many scholars have improved the algorithm. For example, Reference4 is an improved ant colony algorithm with adaptive path selection and dynamic updating pheromone. Reference5 improves the algorithm efficiency by improving the heuristic function. Reference6 is to optimize multiple objectives. The author improves the heuristic function in ant colony algorithm, neighborhood search, pheromone and other related information to quickly obtain the optimal path in traffic logistics. 2.ESTABLISH THE OPTIMAL PATH OPTIMIZATION MODEL2.1Problem optimizationThe essence of the transportation optimal path optimization problem is a scientific and reasonable logistics transportation path7, 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 = {m0, m1, m2, ⋯ mn}; The directed arc between the user and the transportation point is expressed by P = {(mx, my)|mx, my, x ≠ y}. The structure of the optimal path optimization problem of transportation is shown in figure 1 below. 2.2Model optimizationThe 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 px. Then the total demand is required to be controlled within the maximum capacity of all vehicles in the transportation and distribution center, then Σ(px, kzx) < P, and the directed arc weight on J is expressed as Jxy, when the z-th vehicle passes the directed arc (mx, my), it is expressed as ixyz=1, when ixyz=1, it means that the z-th vehicle passes through the directed arc, when ixyz=0, it means that the z-th vehicle has not passed the directed arc. 3.AN IMPROVED ANT COLONY ALGORITHM FOR TRANSPORTATION OPTIMAL PATH OPTIMIZATION MODEL3.1Traditional ant colony algorithm and modelSuppose 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; [pij(t)]α Represents the pheromone concentration of the ant’s corresponding path between road nodes I and j, Ak = {N – tk} 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.2Improved heuristic functionThe heuristic function in the traditional ant colony algorithm ignores the guidance of the direction of ant traversal8. Therefore, it will fall into the local optimum and cannot reach the overall optimum9. Therefore, Reference10 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), dje is the Euclidean distance from node j to node e, and dij 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.3Improved ant colony algorithm pheromoneTransportation time, transportation cost and average road smoothness are important factors affecting the optimal route selection11. 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.1Transportation Cost Pheromone.The transportation cost pheromone can be expressed by equation (4): In equation (4), W1 (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, Ci represents the cost of transportation at node i, Cimax represents the estimated maximum cost, where, Ci = Ai + Ti + Fi, Ai, Ti and Fi represent road transportation loss cost, toll cost and fuel cost respectively. 3.3.2Transport 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. Ti time required for transportation, Timax is the maximum time allowed in transportation. 3.3.3Smooth Transportation Environment Pheromone.The pheromone of smooth transportation environment can be expressed by equation (6): In equation (6), W3 (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, Si represents the smoothness of the transportation path at node i, Simax 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.4Improve 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。 Lbest represents the best path traversed, |Lbest| represents the path length; Lworst represents the worst path traversed|Lworst| represents the path length. 3.3.5Implementation Steps of Improved Ant Colony Algorithm.The steps of improving ant colony algorithm are as follows: Step 1: Pheromone and related parameters are initialized. Step 2: Selection principle is set. Each ant selects the next node in the sink that is not in the tabu table according to the transition probability, and puts the selected node into the tabu table. After each ant completes a circle, the comprehensive coefficient value of the path taken by the ant is calculated. Step 3: Local update principle is set. When the ant selects the path (i, j), it updates the pheromone concentration on the path (i, j) according to equation (8) to increase the probability of the ant selecting the path. Step 4: Local optimal path is solved. When k ants complete the search from the starting point to the end point, k solutions are obtained. In the neighborhood of these K solutions, local search algorithms are used to find the local optimal solution. Step 5: Path impedance is updated. When k local optimal solutions are obtained, the path pheromone quantity is updated globally, the path impedance is updated, and the comprehensive coefficient values obtained from all the tours are compared to find the optimal path. Step 6: Through continuous iteration, the minimum value is found from all local optimal solutions as the global optimal solution. Step 7: The algorithm ends. When the number of iterations reaches the maximum value set by the algorithm, the operation is terminated. 4.EXPERIMENTAL SIMULATION AND RESULTS4.1Problem descriptionSuppose 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. Table 1.Location coordinates of chain stores and cargo demand.
4.2Simulation results and analysisIn 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. 5.CONCLUDING REMARKSThis paper describes the transportation optimization problem in detail, builds a mathematical model, and lists the constraint conditions and corresponding formulas, which lays a foundation for ant colony algorithm to solve the transportation path optimization problem. The algorithm improves the heuristic function and pheromone. The experimental results show that this algorithm has certain advantages, and provides a reference for the research of optimal path planning of transportation logistics. REFERENCESLi, X. and Yu, D.,
“Study on an optimal path planning for a robot based on an improved ANT colony algorithm,”
Automatic Control and Computer Sciences,
(3), 165
–171
(2019). Google Scholar
Ma, G. and Pan, F.,
“Logistics transportation route research based on improved ant colony algorithm,”
Computer Engineering & Science,
(3), 524
–528
(2020). Google Scholar
Yao, X., Li, Z. and Cheng, X.,
“Research on Robot path planning based on improved ant colony algorithm,”
Computer Simulation,
(11), 379
–383
(2021). Google Scholar
Li, X. and Yu, D.,
“Study on an optimal path planning for a robot based on an improved ANT colony algorithm,”
Automatic Control & Computer Sciences, 53
(3), 236
–243
(2019). https://doi.org/10.3103/S0146411619030064 Google Scholar
Zheng, X., Zhou, S. and Xu, R.,
“Energy-efficient scheduling for multi-objective two-stage flow shop using a hybrid ant colony optimisation algorithm,”
International Journal of Production Research,
(13), 58
–64
(2020). Google Scholar
Zhang, Q. and Lu, X.,
“Research on vehicle routing problem with return and replacement in e-commerce environment and its solution to ant colony algorithm,”
Computer Engineering and Applications, 54
(22), 239
–245
(2018). Google Scholar
Wang, L. and Cai, C.,
“Research on optimal route of multi-pick-up vehicles in logistics distribution based on improved ant colony algorithm,”
Highway Traffic Science and Technology,
(5), 17
–32
(2018). Google Scholar
Viswanathan, S., Ravichandran, K. S., Tapas, A. M. and Shekhar, S.,
“An intelligent gain based ant colony optimisation method for path planning of unmanned ground vehicles,”
Defence Science Journal,
(2), 106
–111
(2019). Google Scholar
Xiong, H. O.,
“Research on cold chain logistics distribution route based on ant colony optimization algorithm,”
Discrete Dynamics in Nature and Society,
(03), 187
–196
(2021). Google Scholar
Deng, Y., Liu, Y. and Zhou, D.,
“An improved genetic algorithm with initial population strategy for symmetric TSP,”
Mathematical Problems in Engineering,
(03), 1
–6
(2015). Google Scholar
Xiong, H. O.,
“Research on cold chain logistics distribution route based on ant colony optimization algorithm,”
Discrete Dynamics in Nature and Society,
(03), 187
–196
(2021). Google Scholar
|