Access the full text.
Sign up today, get DeepDyve free for 14 days.
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
Hindawi Journal of Advanced Transportation Volume 2023, Article ID 7651100, 11 pages https://doi.org/10.1155/2023/7651100 Research Article Dynamic Path Optimization Based on Improved Ant Colony Algorithm Juan Cheng Jinling Institute of Technology, Nanjing 211169, China Correspondence should be addressed to Juan Cheng; email@example.com Received 20 June 2022; Revised 19 December 2022; Accepted 18 March 2023; Published 17 April 2023 Academic Editor: Wen Liu Copyright © 2023 Juan Cheng. Tis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Dynamic path optimization is an important part of intelligent transportation systems (ITSs). Aiming at the shortcomings of the current dynamic path optimization method, the improved ant colony algorithm was used to optimize the dynamic path. Trough the actual investigation and analysis, the infuencing factors of the multiobjective planning model were determined. Te ant colony algorithm was improved by using the analytic hierarchy process (AHP) to transform path length, travel time, and trafc fow into the comprehensive weight-infuencing factor. Meanwhile, directional guidance and dynamic optimization were in- troduced to the improved ant colony algorithm. In the simulated road network, the length of the optimal path obtained by the improved ant colony algorithm in the simulation road network is 3.015, which is longer than the length of the optimal path obtained by the basic ant colony algorithm (2.902). Te travel time of the optimal path obtained by the improved ant colony algorithm (376s) is signifcantly shorter than that of the basic ant colony algorithm (416.3s). Te number of iterations of the improved ant colony algorithm (45) is less than that of the basic ant colony algorithm (58). In the instance network, the number of iterations of the improved ant colony algorithm (18) is less than that of the basic ant colony algorithm (26). Te travel time of the optimal path obtained by the improved ant colony algorithm (377.1s) is signifcantly shorter than that of the basic ant colony algorithm (426s) and the spatial shortest distance algorithm (424s). Compared with the basic ant colony algorithm and the spatial shortest distance algorithm, the results of the optimal path obtained by the improved ant colony algorithm were more accurate, and the efectiveness of the improved ant colony algorithm was verifed. trafc, it is impossible to rely on trafc demand management 1. Introduction alone. It is urgent to implement an intelligent transportation In intelligent transportation systems, path optimization is an system to improve the utilization rate of the existing road essential part. Obtaining real-time and accurate trafc in- network. In the face of increasingly serious trafc problems, formation is important for estimating the trafc conditions at trafc managers and trafc participants need to obtain real- the next moment and has a signifcant position in trafc time and accurate trafc information of road sections in time guidance. Path optimization helps the traveler to constantly to provide basis for dynamic management decisions and adjust his driving route according to the actual trafc condi- travel decisions. Because link travel time and dynamic path tions during driving, and reach the destination quickly and optimization can efectively improve travel efciency in the efciently.Teultimategoalofpathoptimizationistooptimize driving process, travel time estimation and prediction and the distribution of trafc fow throughout the road network, dynamic path optimization have become one of the issues in thus solving urban trafc congestion problems fundamentally, the trafc feld. improving road capacity and travel comfort, and alleviating Trough investigation and analysis, the dynamic road environmental pollution caused by automobile exhaust. multiobjective planning model is established with the path To solve the trafc congestion, trafc accidents, trafc length, travel time, andtrafc fow as the targets.Te analytic pollution, and other problems existing in the current road hierarchy process (AHP) is used to transform the path 2 Journal of Advanced Transportation length, travel time, and trafc fow into the comprehensive complex driving conditions, a hierarchical three-layer tra- weight-infuencing factor, and then the ant colony algorithm jectory planning framework was presented by Zhang et al. . Te simulation results showed that the proposed scheme is improved. Te improved ant colony algorithm is used to optimize the dynamic path. is efective in various scenarios. In order to avoid subsequent Te rest of the paper is structured as follows: a brief collisions and stabilize vehicles, Wang et al.  proposed review is given in the next section. Section 3 discussed the a postcollision motion planning and stability control dynamic path multiobjective programming model followed method for autonomous vehicles. Trough the hardware in by Section 4, which describes the improved ant colony al- the loop test, the proposed scheme is verifed in the in- gorithm. Results and discussion are presented in Section 5. tegrated driving scenario. Zhang et al.  made a com- Finally, the conclusions are outlined in Section 6. prehensive and systematic review of chassis-coordinated control methods for full-line control vehicles, summarized the research progress in recent years, and introduced the 2. Literature Review identifcation methods of diferent working conditions under steering and braking conditions. Dynamic path optimization can not only integrate real-time trafc information, but also accurately predict trafc fow In summary, the application of dynamic path optimi- parameters in future time based on detected real-time trafc zation in the trafc feld is more and more mature. Te information. Te dynamic path optimization algorithm dynamic path optimization algorithms include Dijkstra al- provides path planning to the driver, which can be planned gorithm, heuristic algorithm , genetic algorithm, ant before travel or during travel. Researchers have carried out colony algorithm, and so on. Te algorithm used in the a lot of study on dynamic path optimization algorithms and existing literature employed the path length as the weight, achieved fruitful results. Bauer et al.  introduced layering the dynamic travel time calculation generally used the BPR technology and target acceleration technology in the Dijk- function, and the data obtained from the fxed detector data or trafc simulation data. However, the path optimization stra algorithm, which improved the data storage capacity of the road network and the efciency of the algorithm. Wei under a dynamic road network not only requires the optimal path search based on real-time trafc information, but also and Meng  optimized the dynamic path using the im- proved Dijkstra algorithm, a weight function was introduced requires stability, fast convergence, and low complexity of to the improved algorithm, and the weight was determined the algorithms. Terefore, artifcial intelligence algorithms according to the degree of trafc congestion. Te A al- that can realize dynamic characteristics are the development gorithm for the unbalanced search was proposed by Pijls and trend of dynamic path optimization algorithms. Post . Te proposed algorithm improved the path search Te ant colony algorithm has the characteristics of ability and narrowed the search range. However, the stability parallelism, positive feedback, and self-organization ability. of the solution obtained by this method was poor. Atila et al. Terefore, the ant colony algorithm is introduced to opti-  applied the improved genetic algorithms for route mize the dynamic path. To make the ant colony algorithm more suitable for dynamic path optimization, the ant colony guidance with the shortest travel time, which introduced a geneticsearch method in the crossoveroperation of genetic algorithm is improved in this paper. Te novelties in this paper are as follows: (1) path length conversion, (2) add algorithms. Te experimental results showed that the im- proved genetic algorithm enhanced the computational ef- directional guidance, and (3) dynamic optimization. fciency compared with the traditional genetic algorithm. An improved ant colony algorithm was developed by D’Acierno 3. Dynamic Path Multiobjective et al. . Te algorithm divided ants into two categories, one Programming Model for path selection and one for setting signals at intersections. Te improved ant colony algorithm solved the problem of At present, most of the path optimization has a single se- asymmetric trafc assignment. Yu et al.  presented an lection criterion, which is the minimum travel time or the improved ant colony algorithm. In this algorithm, the path shortest travel distance. However, surveys have shown that length, road slope, and trafc condition were equivalent to in London and Paris, 42% of travelers use the combination of the weight of the path, and the improved ant colony algo- the minimum travel time and the shortest travel distance to rithm was applied to the TSP problem. Experimental results select the optimal path, and 56% of travelers use the min- showed that the improved ant colony algorithm was feasible. imum travel time as the standard for the optimal path. In Kobayashi et al.  studied the dynamic path optimization Munich, 71% of travelers use the combined standard with algorithm of the trafc network. Taking the shortest distance the minimum travel time and the shortest travel distance to and the shortest travel time as constraints, a road network select the path, and only 27% of travelers use the minimum with 12 light-controlled intersections was simulated. Che travel time as the path selection criterion . It can be seen et al.  proposed an improved ant colony optimization that travelers prefer multiple criteria rather than a single algorithm based on the particle swarm optimization algo- criterion when optimizing travel routes. rithm. Experiment results demonstrate that improved ant colony optimization algorithm is more efective and feasible in path planning for autonomous underwater vehicles than 3.1. Dynamic Path Multiobjective Programming Model. In the traditional ant colony algorithm. Research on trajectory the dynamic trafc network, the factors afecting the trav- optimization to realize real-time collision avoidance under elers should be considered comprehensively to fnd the Journal of Advanced Transportation 3 od optimal path. In order to understand the factors afecting W � min Q , 3 k travelers, questionnaires were used to investigate the factors od od that infuence path optimization. In the questionnaire, the ⎧ ⎪ Q � q (t)δ , (3) ⎨ i k i,k factors that afect path optimization were path length, road s.t. width, travel time, trafc fow, road slope, road performance, i ∈ A, k ∈ K , od trafc speed, number of intersections, weather, and so on. od where q (t) is the average trafc fow of road i at time t. δ is Te questionnaires issued in the survey were 890. In addition i i,k 1 if road i is on the feasible path k connecting the OD, to the survey conducted by the conventional method, the od otherwise δ is 0. survey was conducted using QQ and WeChat. Finally, 543 i,k Trough the abovementioned analysis, the infuence of valid questionnaires were collected. Trough the analysis of path length, travel time, and trafc fow should be consid- the recovered questionnaire, it was found that the path ered in the dynamic path optimization process. Consistent length, travel time, and trafc fow were the three main with the method used by Yu et al. , the AHP is also used to factors afecting path optimization. Terefore, the infuence calculate the weight of each infuencing factor, and then of path length, travel time, and trafc fow on path opti- transforms the factors afecting the path optimization into mization should be considered comprehensively in the a comprehensive weighting infuencing factor. process of path optimization. Te statistical distribution of various infuencing factors is shown in Figure 1. Te traveler will choose the path with the shortest travel 3.2. Analytic Hierarchy Process. Te AHP was proposed by distance and the minimum travel time in the trafc state of the American operations researcher Professor Saaty in the free-fow. While in the trafc state of transition and con- mid 1970s. AHP can classify various factors that afect the gestion, the traveler will choose the path with less travel time problem, determine the relationship between the various and travel distance relatively short and try to avoid factors, and establish a multilevel structural model of the crowded paths. infuencing factors . 3.1.1. Optimal Path Based on the Shortest Travel Distance. 3.2.1. Establishing the Hierarchy Model. In this paper, the Te shortest travel distance refers to the shortest path chosen structure of the model is divided into two layers, namely, the from the starting point O to the ending point D, as shown in target layer A and the criterion layer B. Te weight of the the following equation: path optimization inthe target layeris w ,andthe weights of ij od the path length, travel time, and trafc fow in the criterion W � min L , 1 k layer are w , w , and w , respectively, as shown in Figure 2. 1 2 3 od od ⎧ ⎪ L � l δ , (1) ⎨ i k i,k s.t. 3.2.2. Constructing the Judgment Matrix. Te uniform i ∈ A, k ∈ K , od matrix method was proposed to determine the weight be- od tween each infuencing factor. a is the comparison result of where l is the geometric length of road i. δ is 1 if road i is ij i i,k od the importance between element i and element j. Table 1 is on the feasible path k connecting the OD, otherwise δ is 0. i,k the nine important levels and assignments given by Saaty. 3.1.2. Optimal Path Based on the Minimum Travel Time. 3.2.3. Hierarchical Single Arrangement. Te eigenvector Te minimum travel time indicates the path with the least corresponding to the maximum eigenvalue λ of the travel time from the starting point O to the ending point D, max judgment matrix is denoted as W after normalization which is shown in the following equation: (making the sum of all elements in the vector equal to 1). Te od W � min T , 2 k element of W is the ranking weight of the same level factor for the relative importance of the previous level factor. Tis od od ⎧ ⎪ T � t (t)δ , (2) ⎨ k i,k process is called hierarchical single arrangement. Te cal- s.t. ⎩ culation steps are presented as follows: i ∈ A, k ∈ K , od Step (1): multiplying element of each row in the od where t (t) is the average travel time of road i at time t. δ is i i,k judgment matrix A, that is, M � a , i � 1,2 · · · n i ij j�1 �� � 1 if road i is on the feasible path k connecting the OD, Step (2): calculating the n − th root of M , w � M od i i i otherwise δ is 0. − − − i,k Step (3): if w is normalized to w � w / w , then i i i j j�1 w is the eigenvector 3.1.3. Optimal Path Based on the Least Trafc Flow. Step (4): calculating the maximum eigenvalue, Trafc fow is an indicator of congestion. Te least trafc λ ≈ (AW) /nw max i�1 i i fow is the path with the minimum trafc fow from the starting point O to the ending point D, that is, the path with the least congestion is selected, as indicated in the following 3.2.4. Consistency Test. Te consistency test is to determine equation: the allowable range of inconsistency in the judgment matrix 4 Journal of Advanced Transportation Figure 1: Statistical distribution diagram of various infuencing factors afecting path optimization. path optimization w target layer A ij path length w travel time w traffic flow w 1 2 3 criterion layer B Figure 2: Te layering diagram of path optimization. A, which the test standard is indicated in the following 3.3. Quantifcation of Infuencing Factors. Te factors af- equation: fecting path optimization in this paper are path length, travel time, and trafc fow, but the dimensions of the three CI infuencing factors are inconsistent. In order to apply the CR � , (4) infuence of diferent factors on path optimization, di- RI mensionless processing of diferent infuencing factors is required. Te extremum method is used to perform di- where CR is the conformance ratio. When its value is less mensionless processing infuencing factors , and the than 0.1, the judgment matrix passes the consistency test; variables are transformed into (0, 1]. Te transformation otherwise, it needs to be corrected. CI is the consistency equation is indicated as follows: index, CI � λ − n/n − 1. RI is the random consistency max index, determined by the order of the judgment matrix, x � , i (5) max x which is shown in Table 2. i Among the 543 valid questionnaires, 291 questionnaires where x is the dimensionless value of x . max x is the i i i were selected with the path length, travel time, and trafc maximum value of x . fow as the top three infuencing factors. Te judgment Te weights of the infuencing factors in the criterion matrix of this paper is determined by 291 questionnaires and layer are obtained through Section 3.2. Ten, the compre- the scale method of Table 1. Te constructed judgment hensive weight-infuencing factor of the path is calculated matrix is shown in Table 3. considering the three factors of path length, travel time, and Te weight of the criterion layer is determined by the trafc fow as follows: eigenvalue method mentioned above. Te maximum eigenvalue is λ � 3.0385. Te con- s � w · d + w · t + w · n , (6) max ij 1 ij 2 ij 3 ij sistency test result is CR � CI/RI � 0.0193 where s is the comprehensive weight-infuencing factor /0.58 � 0.0333 <0.1, indicating that the constructed judg- ij considering path length, travel time, and trafc fow. d is ment matrix passes the consistency test. Te eigenvalue of ij the dimensionless value of path length. t is the the criteria layer is w � 0.637, w � 0.258, and w � 0.105. ij 1 2 3 path length travel time traffic flow traffic speed number of intersections road width road performance road slope weather other factor Journal of Advanced Transportation 5 Table 1: Important scale. Important scale Meaning 1 Te two factors are equally important 3 Te former is slightly more important than the latter 5 Te former is more important than the latter 7 Te former is obviously important than the latter 9 Te former is extremely important than the latter 2, 4, 6, 8 Intermediate value of two adjacent judgments If the ratio of the importance between element i and element j is a , the ratio of ij Reciprocal element j and element i is a � 1/a ji ij Table 2: Average random consistency index. η (t) � , (7) ij d + d ij jD Matrix 1 2 3 4 5 6 7 8 9 10 order where η (t) is the heuristic function, d is the di- ij jD RI 0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 mensionless value of the length between node j and the ending point D, and d is the dimensionless value of the ij length between adjacent nodes iand j. Table 3: Te judgment matrix. Te visibility function is improved comprehensively A C C C considering equations (1) and (2) as follows: 1 2 3 C 1 3 5 η (t) � . (8) ij C 1/3 1 3 s + d ij jD C 1/5 1/3 1 4.1.3. Dynamic Optimization. When the information in the dimensionless value of travel time. n is the dimensionless ij road network changes, the path should be reoptimized value of travel fow. w , w ,andw are the weights of each 1 2 3 according to the changed information. Terefore, when the infuencing factor in the criteria layer, w � 0.637, ant selects the next node, it checks whether the information w � 0.258, and w � 0.105. 2 3 in the road network changes. If the change occurs, the pheromone concentration needs to be updated, as shown in 4. The Improved Ant Colony Algorithm the following equation: Te classic application of the ant colony algorithm is the TSP t+1 τ(t + 1) � · τ(t), (9) problem. In order to make the ant colony algorithm more suitable for dynamic path optimization, the ant colony al- where τ(t + 1) is the pheromone concentration on path ij at gorithm is improved. time t + 1, t is the travel time on path ij at time t + 1, t is t+1 t the travel time on path ij at time t, and τ(t) is the pher- 4.1. Te Improved Ant Colony Algorithm omone concentration on path ij at time t. 4.1.1. Path Length Conversion. Based on Section 3.2, path length, travel time, and trafc fow are comprehensively 4.2. Design of the Improved Ant Colony Algorithm. Te considered, and the comprehensive weight-infuencing improved ant colony algorithm is applied to path factors of each infuencing factor are taken as path length, optimization. which is shown in equation (4). 4.2.1. Ant Transfer Rule. Te ant moves from node i to node 4.1.2. Adding Directional Guidance. In the ant colony al- j according to the following equation: gorithm, η (t) is a heuristic function, representing the ij α β ⎧ ⎪ expectation between city i and city. Among them, η (t) � ⎪ argmaxτ (t) · η (t) , q < q , ij ij ij 0 1/d is the reciprocal of the distance between adjacent j � (10) ij k k nodes. Te smaller the d is, the greater the p (t) is. Te P (t), q ≥ q , ij ij ij 0 smaller the distance is, the more likely the ant is to select the next node. Tis defnition is applicable to unordered TSP where q is a random variable uniformly distributed on [0,1]. problems, but for ordered path optimization problems, this q is the parameter that controls the movement rule, search method will reduce the search efciency. Te A q ∈ [0,1]. Te value of q can be divided into three types 0 0 algorithm is introduced to improve η (t). In order to be according to the scale of the road network, which is generally ij consistent with the abovementioned, equation (7) is di- large, medium, and small, and the values are 0.7, 0.5, and 0.2 mensionless according to the method of Section 3.3 as . η is shown in equation (8). p (t) is indicated in the ij ij follows: following equation: 6 Journal of Advanced Transportation Table 4: Constants and variables in ant colony algorithm. Symbol Meaning n Number of nodes m Number of ants η (t) A heuristic function that represents the expectation between node i and node j ij d Te distance between node i and node j ij τ (t) Te pheromone concentration between node i and node j at time t ij ∆τ Te pheromone concentration of ant k released between node i and node j ij Q Pheromone constant α Pheromone importance factor, or pheromone factor for short β Te importance factor of heuristic function is referred to as heuristic function factor ρ Pheromone volatile factor, where 0 <ρ <1 p (t) Te probability of ant k moving from node i to node j at time t ij allow Search table, representing ant k is looking forward to visiting the node tabu Search tabu table, representing ant k have visited the node α β where Q is the pheromone constant released by the ant ⎧ ⎪ τ (t) · η (t) ij ij , j ∈ allow , during the whole path optimization. L is the total length k k ⎨ α β k τ (t) · η (t) s∈allow is is p (t) � k (11) traveled by ant k. ij ⎪ Te global pheromone update rule is as follows: 0, j ∉ allow . τ (t + 1) � (1 − ζ) · τ (t) +∆τ (t), ij ij ij Te variables in equation (11) are shown in Table 4. It can be seen from equation (8), when q < q , the ant ∆τ (t) � ∆τ (t), ij ij temporarily ignores the existence of the better next node, k�1 and accumulates the pheromone on the path of node i to all ⎧ ⎪ the nodes j to be selected. When q ≥ q , the ant will select the ⎪ , Theoptimalpathof antsinthiscircle, k L k k next node according to p (t), preventing the ant from ij ∆τ � ij ⎪ selecting the path with large pheromone concentration at the ⎪ 0, otherwise, beginning, which is benefcial to the global search and avoids local convergence. (14) where ξ is the pheromone volatile factor, ξ ∈ (0,1). L is the 4.2.2. Pheromone Update. Tere are two ways to update sum of the lengths selected by the ants in this circle. the pheromone, namely, local pheromone updates and global pheromone updates. Local pheromone update 4.2.3. Dynamic Optimization. Trafc information on the means that when the ant completes a path search, the road network is updated every 5–15minutes. When the pheromone is updated on the path. While global pher- vehicle reaches the next node of the road network, it is omone update means that the pheromone is updated of checked whether the pheromone on the road has changed the optimal path in all paths when all ants complete a path according to equation (9). If the pheromone has changed, search. the path is searched according to the changed pheromone, Te local pheromone update rule is as follows: and the path is dynamically optimized. Te fow of the improved ant colony algorithm is as τ (t + 1) � (1 − ρ) · τ (t) +∆τ (t), ij ij ij follows: (12) Step 1: initializing each parameter, set the number of ∆τ (t) � ∆τ (t), ij ij k�1 iterations to NC � 0, and place m ants on the starting point. where ∆τ is the concentration of pheromone left between ij Step 2: the number of iterations set to NC � NC + 1. node i and node j by ant k. ∆τ is the pheromone con- ij Step 3: the ant performs a path search according to centration that all ants increase between node i and node j equation (10). due to the release of pheromones. Te ant cycle model is used for calculating ∆τ as follows : ij Step 4: when an ant reaches the end point, the pher- omone is updated to the path searched by the ant ⎧ ⎪ according to the local pheromone update rule. ⎪ , If theantvisitsnode itonode j, k k Step 5: repeat Step 2–Step 4. When all the ants have ∆τ � (13) ij ⎪ ⎪ reached the end point, the path that all ants passed is 0, otherwise, the optimal path. Journal of Advanced Transportation 7 Step 6: select an optimal path from all paths and O 1 2 perform global pheromone update on the optimal path. Step 7: if NC > NC , the search ends and outputs the max current optimal path, otherwise return to step 2. Step 8: check whether the road network has been 3 4 5 6 updated. If updated, the pheromone is updated according to equation (9). Step 9: if the vehicle has reached the end point at this time, the search is fnished, otherwise return to step 2. 7 8 9 5. Results and Discussion Using the improved ant colony algorithm, the path opti- 10 11 12 13 D mization is carried out for the simulated road network and the instance network. Figure 3: Road network diagram. 5.1. Simulated Road Network Table 5: Table of path length. 5.1.1. Road Network Data. In order to verify the efective- Node-node Path length (m) ness of the improved ant colony algorithm proposed in this O-1 0.549 paper, some sections of Chaoyang Zhou South Road in 1–4 0.704 Nanchang City were selected as the study area. A road 3–10 1.000 5-6 0.282 network with 15 nodes is designed, and the road network 7-8 0.268 contains 21 road segments. Te road network to be opti- 8–13 0.394 mized in this paper is shown in Figure 3, where node O is the 11-12 0.282 starting point of the road section, and node D is the ending O–3 0.718 point of the road section. Te goal of path optimization is to 2–6 0.746 fnd the optimal path from node O to node D. Vehicle 4-5 0.282 arrivals follow the normal distribution. In the road network, 5–7 0.423 the update interval of trafc information is 5minutes. 7–12 0.437 Te length, the travel time at a certain time, and the 9-D 0.423 trafc fow are shown in Tables 5–7, respectively. Te table 12-13 0.310 1-2 0.676 only shows the results of nondimensionalization according 3-4 0.563 to the abovementioned method. 4–11 0.972 6–8 0.451 5.1.2. Parameter Settings. Te parameters in the improved 8-9 0.282 10-11 0.563 ant colony algorithm are shown in Table 4, and the main 13-D 0.282 parameters are set as follows: (1) m represents the number of ants. m afects the calculation results of MATLAB. Te literature re- optimal solution. Te simulation results showed that search and simulation results showed that when the β is 0–5, the efect is better, and this paper takes number of ants is 1.5 times the number of nodes, the β � 5. efect is better. In this paper, the number of nodes is (5) ρ is the pheromone volatilization factor, indicating 15, so the number of ants is set to 23. the level of disappearance of the pheromone. 1 − ρ is (2) n indicates the number of nodes. n � 15. the pheromone residual factor, describing the re- tention level of the pheromone. Trough simulation (3) α denotes the pheromone heuristic factor, which results, it is shown that ρ is 0.2–0.5; the simulation describes the infuence of the pheromone released by efect is better, so ρ is set to 0.3 in this paper. the ant during the path fnding process on the ant path selection. Trough literature research and simulation results, it is known that the efect is better 5.1.3. Results and Analysis. Using the data in Section 5.1.1 when α is 0 to 5, and α � 1 selected in this paper. and the parameters determined in Section 5.1.2, the results (4) β refers to the expected value heuristic factor, in- were inputted into the MATLAB simulation platform to dicating the degree of action expected in the path verify the improved ant colony algorithm proposed in selection. Te larger the β, the easier to fall into the this paper. After the optimized processing of the improved ant local optimal solution. Te smaller the β, the smaller the efect of the expected value, the harder to fnd the colony algorithm, the optimal path is shown in Figure 4, and 8 Journal of Advanced Transportation Table 6: Table of travel time at a certain time. Optimal path Node-node Travel time (s) O-1 0.659 1–4 0.634 3–10 1.000 5-6 0.254 10 7-8 0.241 8–13 0.245 11-12 0.338 O–3 0.462 2–6 0.987 4-5 0.298 5–7 0.634 7–12 0.357 9-D 0.585 12-13 0.254 05 10 15 1-2 0.704 Coordinate X 3-4 0.423 4–11 0.921 Figure 4: Te optimal path of the improved ant colony algorithm. 6–8 0.272 8-9 0.241 10-11 0.441 improved ant colony algorithm proposed in this paper. 13-D 0.220 Figure 6 shows the optimal path of the ant colony algorithm, and Figure 7 shows the convergence curve of the ant colony algorithm. Table 7: Table of trafc fow. As indicated in Figure 6, the optimal path from node O Node-node Trafc fow (vehicle) to node D obtained by the ant colony algorithm is O-1-4-5- O-1 0.533 7-8-13-D, and the optimal path length (comprehensive 1–4 0.615 weight-infuencing factor) is 2.902. 3–10 0.770 A comparison of the improved ant colony algorithm, the 5-6 0.256 basic ant colony algorithm, and the spatial shortest distance 7-8 0.304 algorithm is shown in Table 8. 8–13 0.488 From Figures 4–7 and Table 8, the following conclusions 11-12 0.450 can be drawn: O–3 0.347 2–6 1.000 (1) Te length of the optimal path obtained by the 4-5 0.254 improved ant colony algorithm (3.015) is longer than 5–7 0.464 the length obtained by the basic ant colony algorithm 7–12 0.687 (2.092). Tis is because the improved ant colony 9-D 0.411 algorithm comprehensively considers the infuence 12-13 0.251 of path length, travel time, and trafc fow on the 1-2 0.507 optimal path. Terefore, when choosing the optimal 3-4 0.450 4–11 0.758 path, the road with a shorter travel time and less 6–8 0.303 trafc fow will be considered, which may lead to the 8-9 0.258 selection of the longer path length. However, when 10-11 0.488 the optimal path is simultaneously expressed by the 13-D 0.256 comprehensive weight-infuencing factor, the opti- mal path selected by the basic ant colony algorithms is longer than the optimal path obtained by the the convergence curve is shown in Figure 5. In the improved improved ant colony algorithm, since the two al- ant colony algorithm, the comprehensive weight-infuencing gorithms do not consider the real-time trafc con- factors are used for calculation, and after the optimal path is ditions of the road segment (such as the delay time obtained, the optimal path is described in the actual road caused by trafc congestion). network. (2) Te number of iterations of the improved ant colony As can be seen from Figure 4, the optimal path from algorithm is reduced compared with the basic ant node O to node D is O-3-4-5-7-12-13-D, and the optimal colony algorithm. Because of the directional guid- path length (comprehensive weight-infuencing factor) ance introduced in the improved ant colony algo- is 2.885. rithm, the ant’s search always points to the ending Meantime, the basic ant colony algorithm is used to point, and the convergence speed is accelerated. calculate the optimal path, which is compared with the Coordinate Y Journal of Advanced Transportation 9 Trend of convergence curve 2.5 1.5 0.5 020 40 60 80 100 Iterations Figure 5: Te convergence curve of the improved ant colony algorithm. Optimal path 05 10 15 Coordinate X Figure 6: Te optimal path of the ant colony algorithm. Trend of convergence curve 2.5 1.5 0.5 0 20406080 100 Iterations Figure 7: Te convergence curve of the ant colony algorithm. Length of optimal path Length of optimal path Coordinate Y 10 Journal of Advanced Transportation Table 8: Comparison of various algorithms in Simulated Road Network. Path length Path optimization algorithm Optimal path Travel time (s) Actual length of the Comprehensive path weight-infuencing factor Improved ant colony algorithm O-3-4-5-7-12-13-D 3.015 2.885 376 Ant colony algorithm O-1-4-5-7-8-13-D 2.902 2.911 416.3 Bold valuers represent the optimal values of various path optimization algorithms. Table 9: Comparison of various algorithms in Instance network. Path length Number of Path optimization algorithm Optimal path Travel time (s) Actual length of the Comprehensive iterations path (m) weight-infuencing factor Improved ant colony algorithm 1-2-17-7-11-12-16 2666 4.109 377.1 18 Ant colony algorithm 1-5-6-10-11-15-16 2662 4.240 426 26 Spatial shortest distance algorithm 1-5-9-10-11-12-16 2680 4.243 424 — Bold valuers represent the optimal values of various path optimization algorithms. distance algorithm. Te efectiveness of the improved ant (3) Te travel time of the optimal path obtained by the improved ant colony algorithm is signifcantly colony algorithm in path optimization is further verifed. shorter than that of the basic ant colony algorithm and the spatial shortest distance algorithm, in- 6. Conclusion dicating that the improved ant colony algorithm improves the accuracy when optimizing the path. Te dynamic path optimization method was studied, and the Although the length of the optimal path obtained by application of the dynamic path multiobjective pro- the improved ant colony algorithm is not the gramming model and ant colony algorithm in TSP problem shortest, the improved ant colony algorithm will were analyzed in this paper. Trough the actual investigation bypass relatively congested roads while driving and and analysis, the section length, travel time, and trafc fow can reach the destination more quickly. are converted into comprehensive weight-infuencing fac- tors by using the AHP. At the same time, directional guidance and dynamic optimization are added. Te im- 5.2. Instance Network. In order to verify the efectiveness of proved ant colony algorithm is proposed, which is verifed the proposed method, the road network of  is selected for by the simulation road network and the example road verifcation. Te purpose of path optimization is to fnd the network. Te travel time comparison results of the optimal optimal path from node 1 to node 16. path showed that the accuracy of the optimal path obtained Te comparisons of the optimal paths obtained by the by the improved ant colony algorithm is improved com- improved ant colony algorithm, the basic ant colony algo- pared with the basic ant colony algorithm and the space rithm and the space shortest distance algorithm, the length shortest distance algorithm, which verifed the efectiveness of the path, the travel time, and the number of iterations are of the improved ant colony algorithm. Meanwhile, di- shown in Table 9. rectional guidance is introduced to reduce the number of It can also be seen from Table 9 that the length of the iterations. optimal path obtained by the improved ant colony al- Because of the time and the lack of appropriate data, the gorithm is longer than that obtained by the basic ant paper is verifed with simulation data. Te author hopes to colony algorithm. However, when the optimal path is use real data in future research to verify the accuracy of the simultaneously expressed by the comprehensive weight- model. Besides, in the future research, the author uses PSO, infuencing factors at the same time, the optimal path SSO, WOA [18–20], and other methods to establish a dy- length selected by the basic ant colony algorithm and the namic path optimization model. spatial shortest distance algorithm is obviously longer than the optimal path obtained by the improved ant colony algorithm. Te number of iterations of the im- Data Availability proved ant colony algorithm is less than that of the basic Te data used to support the fndings of the study are ant colony algorithm. Te travel time of the optimal path available from the corresponding author upon request. obtained by the improved ant colony algorithm is sig- nifcantly shorter than that of the basic ant colony al- gorithm and the spatial shortest distance algorithm, Conflicts of Interest indicating that the improved ant colony algorithm has improved accuracy in optimizing the path compared with Te authors declare that there are no conficts of interest the basic ant colony algorithm and the spatial shortest regarding the publication of this paper. Journal of Advanced Transportation 11 ENGINEERING AND INFORMATION TECHNOLOGY, Acknowledgments vol. 5, no. 6, pp. 58–61, 2005.  M. Dorigo and L. M. Gambardella, “Ant colony system: Tis study was supported by the Jiangsu University Phi- a cooperative learning approach to the traveling salesman losophy and Social Science Research Project (no. problem,” IEEE Transactions on Evolutionary Computation, 2021SJA0518). vol. 1, no. 1, pp. 53–66, 1997.  Y. C. Chang, V. C. Li, and C. J. Chiang, “An ant colony References optimization heuristic for an integrated production and distribution scheduling problem [J],” Engineering Optimiza-  R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, tion, vol. 46, no. 4, p. 18, 2014. D. Schultes, and D. Wagner, “Combining hierarchical and  N. Li, A Research in Dynamic Trafc Assignment and Route goal-directedspeed-up techniques for dijkstra’s algorithm,” Guide System Based on Ant colony Algorithm [D], Changsha Journal of Experimental Algorithmics, vol. 15, 2010. University of Science & Technology, Hu Nan Sheng, China,  M. Wei and Y. Meng, “Research on the optimal route choice based on improved Dijkstra,” in Proceedings of the Advanced  A. J. Humaidi and H. M. Badir, “Linear and nonlinear active Research & Technology in Industry Applications, IEEE, Ot- rejection controllers for single-link fexible joint robot ma- tawa, ON, September 2014. nipulator based on PSO tuner,” JOURNAL OF ENGINEER-  W. Pijls and H. Post, “A new bidirectional search algorithm ING SCIENCE AND TECHNOLOGY REVIEW, vol. 13, no. 6, with shortened postprocessing,” European Journal of Oper- pp. 2272–2278, 2018. ational Research, vol. 198, no. 2, pp. 363–369, 2009.  T. Ghanim,A. R.Ajel,and A.J.Humaidi, “Optimalfuzzylogic  U. Atila, I. R. Karas, C. Gologlu, B. Yaman, and I. M. Orak, control for temperature control based on social spider opti- “Design of a route guidance system with shortest driving time mization,” IOP Conference Series: Materials Science and En- based on genetic algorithm,” in Proceedings of the 10th gineering, vol. 745, no. 1, Article ID 012099, 2020. WSEAS international conference on Applied computer and  A. J. Humaidi, H. M. Badr, and A. H. Hameed, “PSO-based applied computational science. World Scientifc and Engi- active disturbance rejection control for position control of neering Academy and Society (WSEAS), pp. 61–66, Beijing magnetic levitation system,” in Proceedings of the 2018 5th China, July 2011. International Conference on Control, Decision and In-  L. D’Acierno, M. Gallo, and B. Montella, “An Ant Colony formation Technologies (CoDIT), Tessaloniki, Greece, April Optimisation algorithm for solving the asymmetric trafc assignment problem,” European Journal of Operational Re- search, vol. 217, no. 2, pp. 459–469, 2012.  M. Yu, G. Yue, Z. Lu, and X. Pang, “Logistics terminal dis- tribution mode and path optimization based on ant colony algorithm,”Wireless PersonalCommunications, vol.102, 2018.  M. A. Kobayashi, H. Shimizu, and Y. Yonezawa, “Dynamic route search algorithms of a trafc network,” in Proceedings of the 36th SICE Annual Conference. International Session Pa- pers, IEEE, Tokushima, Japan, July 2002.  G. Che, L. Liu, and Z. Yu, “An improved ant colony opti- mization algorithm based on particle swarm optimization algorithm for path planning of autonomous underwater ve- hicle,” Journal of Ambient Intelligence and Humanized Computing, vol. 11, no. 8, pp. 3349–3354, 2020.  Z. Zhang, L. Zhang, J. Deng, M. Wang, Z. Wang, and D. Cao, “An enabling trajectory planning scheme for lane change collision avoidance on highways,” IEEE Transactions on In- telligent Vehicles, vol. 12, 2021.  C. Wang, Z. Wang, L. Zhang, and T. Chen, “Post-impact motion planning and tracking control for autonomous ve- hicles[J],” Chinese Journal of Mechanical Engineering, vol. 35, no. 1, pp. 1–18, 2022.  L. Zhang, Z. Zhang, Z. Wang, J. Deng, and D. G. Dorrell, “Chassis coordinated control for full X-by-wire vehicles-A review,” Chinese Journal of Mechanical Engineering, vol. 34, no. 1, pp. 42–25, 2021.  N. Rivera, J. A. Baier, and C. Hernandez, ´ “Incorporating weights into real-time heuristic search,” Artifcial Intelligence, vol. 225, no. 225, pp. 1–23, 2015.  G. K. H. Pang, K. Takabashi, T. Yokota, and H. Takenaga, “Adaptive route selection for dynamic route guidance system based on fuzzy-neural approaches,” IEEE Transactions on Vehicular Technology, vol. 48, no. 6, pp. 2028–2041, 1999.  C. L. Zong, X. Y. Li, and Y. T. Wang, “A multi-objective programming model of route choice before travel [J],” JOURNAL OF TRANSPORTATION SYSTEMS
Journal of Advanced Transportation – Hindawi Publishing Corporation
Published: Apr 17, 2023
Access the full text.
Sign up today, get DeepDyve free for 14 days.