CN109726852A - Based on route planning method, device, terminal and the medium for improving ant group algorithm - Google Patents
Based on route planning method, device, terminal and the medium for improving ant group algorithm Download PDFInfo
- Publication number
- CN109726852A CN109726852A CN201811451979.9A CN201811451979A CN109726852A CN 109726852 A CN109726852 A CN 109726852A CN 201811451979 A CN201811451979 A CN 201811451979A CN 109726852 A CN109726852 A CN 109726852A
- Authority
- CN
- China
- Prior art keywords
- road
- travel
- node
- route planning
- colony algorithm
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Business, Economics & Management (AREA)
- Theoretical Computer Science (AREA)
- Economics (AREA)
- Human Resources & Organizations (AREA)
- Strategic Management (AREA)
- General Physics & Mathematics (AREA)
- Health & Medical Sciences (AREA)
- Biomedical Technology (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Marketing (AREA)
- General Business, Economics & Management (AREA)
- Entrepreneurship & Innovation (AREA)
- Game Theory and Decision Science (AREA)
- Development Economics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Artificial Intelligence (AREA)
- Operations Research (AREA)
- Biophysics (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- General Health & Medical Sciences (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Navigation (AREA)
- Traffic Control Systems (AREA)
Abstract
The invention belongs to machine learning techniques fields, it discloses a kind of based on the route planning method for improving ant group algorithm, device, terminal and medium, the present invention is requested by receiving the route planning of user's input, the route planning request packet includes beginning-of-line and travel destination, obtain each road between beginning-of-line and travel destination out, and the safety coefficient of each road, according to the beginning-of-line out, travel destination and each road, construct node matrix equation, according to the safety coefficient for improving ant group algorithm and each road, the shortest path from the beginning-of-line out to the travel destination is searched in the node matrix equation, as destination path, while considering to go on a journey safety, stroke is most short or distance is most short, solve the technical issues of prior art digital map navigation lacks the safety for considering user's trip.
Description
Technical Field
The invention relates to the technical field of machine learning, in particular to a route planning method, a route planning device, a route planning terminal and a route planning medium based on an improved ant colony algorithm.
Background
With the rapid development of the internet technology, more and more application software of intelligent terminal products appear in the life of people, such as various electronic maps, and a user can acquire a travel route planned for the user by an electronic map server only by inputting a travel place and a destination in an electronic map client, so as to provide navigation service for the user.
However, most map navigation software on the market is based on shortest distance or shortest time, and does not consider the safety of user travel.
The above is only for the purpose of assisting understanding of the technical aspects of the present invention, and does not represent an admission that the above is prior art.
Disclosure of Invention
The invention mainly aims to provide a route planning method, a route planning device, a route planning terminal and a route planning medium based on an improved ant colony algorithm, and aims to solve the technical problem that the safety of user travel is not considered in map navigation in the prior art.
In order to achieve the above object, the present invention provides a route planning method based on an improved ant colony algorithm, comprising the following steps:
receiving a route planning request input by a user, wherein the route planning request comprises a travel starting point and a travel terminal point;
acquiring each road between the travel starting point and the travel terminal point and the safety coefficient of each road;
constructing a node matrix according to the travel starting point, the travel destination and each road;
and searching the shortest path from the travel starting point to the travel end point in the node matrix according to an improved ant colony algorithm and the safety factor of each road to serve as a target path.
Preferably, the step of searching for the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road includes:
correcting the probability of all ants accessing the next node from the current node in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road until all the nodes are accessed by the ants;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; wherein the improved ant colony algorithm is as follows:
wherein,probability of selecting j node for ant k; allowedkIndicating the destination of ant k that may be selected nextSet, α represents information heuristic factor, β represents expectation heuristic factor, i represents current node, j represents next target node, s represents node combination, ηij(t) represents a heuristic function; tau isij(t) represents a pheromone; lambda [ alpha ]ijThe safety factor of the road corresponding to the next target node.
Preferably, the step of searching for the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road includes:
according to the improved ant colony algorithm, all ants visit the next node from the current node in the node matrix;
according to the safety coefficient and the correction function of each road, correcting the distance from the current node to the next node until the ant has visited all the nodes;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; wherein,
the correction function is:
the improved ant colony algorithm comprises the following steps:
wherein,probability of selecting j node for ant k; allowedkRepresenting the set of destination locations that ant k may pick next, α representing the information heuristics, β representing the expected heuristics, i representing the current node, j representing the next target node, s representing the node combination, ηij(t) represents a heuristic function,dijrepresenting the distance between two nodes; tau isij(t) represents a pheromone; lambda [ alpha ]ijThe safety factor of the road corresponding to the next target node.
Preferably, the step of obtaining each road between the travel starting point and the travel ending point and the safety factor of each road includes:
acquiring each road between the travel starting point and the travel ending point and information of each road;
and determining the safety factor of each road according to the information of each road.
Preferably, the road information includes accident information, vehicle speed information and road factor information;
correspondingly, the step of determining the safety factor of each road according to the information of each road comprises the following steps:
respectively determining an accident index, a vehicle speed index and a road factor index according to the accident information, the vehicle speed information and the road factor information;
and determining the safety factor of each road according to the accident index, the vehicle speed index and the road factor index.
Preferably, the accident information comprises the number of police, the number of road traffic accidents in the area, the number of dead people in the area, the number of motor vehicles in the area and the number of people in the area;
correspondingly, the step of respectively determining an accident index, a vehicle speed index and a road factor index according to the accident information, the vehicle speed information and the road factor information comprises the following steps:
and determining the accident index according to the police number, the number of road traffic accidents in the area, the number of dead people in the road traffic accidents in the area, the number of motor vehicles in the area and the number of people in the area.
Preferably, the step of determining the accident index according to the number of police officers, the number of road traffic accidents in the area, the number of dead people in the road traffic accidents in the area, the number of motor vehicles in the area and the number of population in the area includes:
according to the formulaCalculating the accident index;
wherein γ represents an accident index;
n represents the weight of the death number of the road traffic accident in the area;
n1 represents the number of police calls;
n2 represents the number of road traffic accidents in the area;
n3 represents the number of road traffic accident deaths in the area;
m1 represents the number of vehicles in the zone;
m2 indicates the number of people in the area.
Based on the above object, the present invention further provides a route planning device based on the improved ant colony algorithm, including:
the system comprises a receiving module, a route planning module and a route planning module, wherein the receiving module is used for receiving a route planning request input by a user, and the route planning request comprises a travel starting point and a travel terminal point;
the obtaining module is used for obtaining each road between the travel starting point and the travel terminal point and the safety coefficient of each road;
the construction module is used for constructing a node matrix according to the travel starting point, the travel end point and each road;
and the searching module is used for searching the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road, and taking the shortest path as a target path.
Based on the above object, the present invention further provides a terminal, including: a memory, a processor and a modified ant colony algorithm based routing program stored on the memory and executable on the processor, the modified ant colony algorithm based routing program configured to implement the steps of the modified ant colony algorithm based routing method as described above.
Based on the above object, the present invention further provides a storage medium, on which a route planning program based on the improved ant colony algorithm is stored, and the route planning program based on the improved ant colony algorithm, when executed by a processor, implements the steps of the route planning method based on the improved ant colony algorithm as described above.
According to the method, a route planning request input by a user is received, the route planning request comprises a trip starting point and a trip end point, each road between the trip starting point and the trip end point and the safety coefficient of each road are obtained, a node matrix is constructed according to the trip starting point, the trip end point and each road, the shortest path from the trip starting point to the trip end point is searched in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road to be used as a target path, the trip safety is considered, the shortest stroke or the shortest distance is simultaneously considered, and the technical problem that the travel safety of the user is not considered in map navigation in the prior art is solved.
Drawings
Fig. 1 is a schematic structural diagram of a terminal in a hardware operating environment according to an embodiment of the present invention;
fig. 2 is a schematic flow chart of a first embodiment of the route planning method based on the improved ant colony algorithm according to the present invention;
FIG. 3 is a schematic flow chart of a second embodiment of the route planning method based on the improved ant colony algorithm according to the present invention;
FIG. 4 is a schematic flow chart of a third embodiment of the route planning method based on the improved ant colony algorithm according to the present invention;
FIG. 5 is a schematic flow chart of a fourth embodiment of the route planning method based on the improved ant colony algorithm according to the present invention;
fig. 6 is a block diagram of a first embodiment of a route planning device based on an improved ant colony algorithm according to the present invention.
The implementation, functional features and advantages of the objects of the present invention will be further explained with reference to the accompanying drawings.
Detailed Description
It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.
Referring to fig. 1, fig. 1 is a schematic terminal structure diagram of a hardware operating environment according to an embodiment of the present invention.
As shown in fig. 1, the terminal may include: a processor 1001, such as a Central Processing Unit (CPU), a communication bus 1002, a user interface 1003, a network interface 1004, and a memory 1005. Wherein a communication bus 1002 is used to enable connective communication between these components. The user interface 1003 may include a Display screen (Display), an input module such as a Keyboard (Keyboard), and the optional user interface 1003 may also include a standard wired interface, a wireless interface. The network interface 1004 may optionally include a standard wired interface, a WIreless interface (e.g., a WIreless-FIdelity (WI-FI) interface). The Memory 1005 may be a Random Access Memory (RAM) Memory, or may be a Non-Volatile Memory (NVM), such as a disk Memory. The memory 1005 may alternatively be a storage device separate from the processor 1001.
Those skilled in the art will appreciate that the configuration shown in fig. 1 is not intended to be limiting and may include more or fewer components than those shown, or some components may be combined, or a different arrangement of components.
As shown in fig. 1, a memory 1005, which is a kind of storage medium, may include therein an operating system, a data storage module, a network communication module, a user interface module, and a route planning program based on the improved ant colony algorithm.
In the terminal shown in fig. 1, the network interface 1004 is mainly used for data communication with a network server; the user interface 1003 is mainly used for data interaction with a user; the processor 1001 and the memory 1005 in the terminal of the present invention may be disposed in the terminal, and the terminal invokes the route planning program based on the improved ant colony algorithm stored in the memory 1005 through the processor 1001 and executes the route planning method based on the improved ant colony algorithm provided by the embodiment of the present invention.
An embodiment of the present invention provides a route planning method based on an improved ant colony algorithm, and referring to fig. 2, fig. 2 is a schematic flow diagram of a first embodiment of the route planning method based on the improved ant colony algorithm.
In this embodiment, the route planning method based on the improved ant colony algorithm includes the following steps:
step S10: receiving a route planning request input by a user, wherein the route planning request comprises a travel starting point and a travel terminal point;
it should be noted that the main execution body of the method of the present embodiment is the terminal. The route planning request input by the user is generally that the user inputs a travel starting point and a travel end point of a travel on the electronic map.
The electronic map is a modern information product which takes a visual digital map as a background, takes multimedia such as texts, pictures, icons, sounds, animations, videos and the like as expression means, and takes hardware equipment as a processing platform to show comprehensive appearances of areas such as cities, enterprises, tourist attractions and the like.
Step S20: acquiring each road between the travel starting point and the travel terminal point and the safety coefficient of each road;
it should be noted that there may be several passable routes from the trip starting point to the trip end point, and each route is composed of many roads, and after determining each road from the trip starting point to the trip end point, based on the safety factor of each road, a route with the shortest distance, that is, a target route is found, and the target route combines the safety factor, not only considering the distance problem.
The safety factor of each road may be obtained according to user evaluation, or may be obtained based on street view image analysis, and street view image analysis mainly analyzes congestion rate, greening rate, and width of the road, for example, an excessively narrow road with little smoke is generally considered as a road with a low safety factor. The street view image can be obtained in a conventional obtaining mode, and can also be obtained from a camera file by receiving the camera file sent by a collecting vehicle.
Step S30: constructing a node matrix according to the travel starting point, the travel destination and each road;
during specific implementation, a node matrix is constructed, a travel starting point and a travel end point are respectively used as a starting node and a stopping node, and then the node when the ant selects is determined according to the end points of roads from the starting node to the stopping node. For example, starting at a and ending at B, a to B may be on the way C to D, and C, D acts as a node that ants may select.
Step S40: and searching the shortest path from the travel starting point to the travel end point in the node matrix according to an improved ant colony algorithm and the safety factor of each road to serve as a target path.
In a specific implementation, the step of searching the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road includes:
correcting the probability of all ants accessing the next node from the current node in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road until all the nodes are accessed by the ants;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; the improved ant colony algorithm model is as follows:
wherein,probability of selecting j node for ant k;
allowedkrepresenting a set of destination nodes that ant k may pick next;
α denotes information heuristics;
β denotes expected heuristic factors;
i represents a current node;
j represents the next target node;
s represents a node junction;
ηij(t) represents a heuristic function;
τij(t) represents a pheromone;
λijthe safety factor of the road corresponding to the next target node.
The improved ant colony algorithm modifies the probability that all ants visit the next node from the current node in the node matrix by introducing a safety factor into the conventional ant colony algorithm.
In another aspect, a conventional ant colony algorithm may be used, and the distance between nodes is considered by combining a safety factor, and in a specific implementation, the step of searching for the shortest path from the travel starting point to the travel ending point in the node matrix according to the improved ant colony algorithm and the safety factors of the roads includes:
according to the improved ant colony algorithm, all ants visit the next node from the current node in the node matrix;
according to the safety coefficient and the correction function of each road, correcting the distance from the current node to the next node until the ant has visited all the nodes;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; wherein,
the correction function is:
the improved ant colony algorithm comprises the following steps:
wherein,probability of selecting j node for ant k;
allowedkrepresenting a set of destination nodes that ant k may pick next;
α denotes information heuristics;
β denotes expected heuristic factors;
i represents a current node;
j represents the next target node;
s represents a node junction;
ηij(t) represents a heuristic function,
dijrepresenting the distance between two nodes;
τij(t) represents a pheromone;
λijthe safety factor of the road corresponding to the next target node.
In the scheme, the ant colony improvement algorithm is to correct the distance between two nodes by combining the side length (distance) of the current node and the next target node with the safety factor, and before the correction, the distance is dijModified to beThe higher the safety factor is, the smaller the corrected distance is, and the probability of selection is increased; conversely, the lower the safety factor, the larger the corrected distance. The probability of being selected will decrease.
It is often necessary to deal with a factor of safety, for example a factor of safety default value of 1.
The improved ant colony algorithm is used for solving the optimization problem, and the basic principle of the ant colony algorithm is roughly as follows:
1. ants release pheromone on the path;
2. and randomly selecting a path to walk when the crossing which is not walked is touched. At the same time, the pheromone related to the path length is released;
3. the pheromone concentration is inversely proportional to the path length, and when later ants touch the intersection again, a path with higher pheromone concentration is selected;
4. the concentration of pheromones on the optimal path is increased;
5. and finally finding the optimal food searching path by the ant colony.
The scheme adds a safety coefficient lambda to the basic ant colony algorithmijThe selection probability of the ant selecting the next target node is selected by combining the safety coefficient, and the safety coefficient lambda of the road is selected by the ant selecting the next target nodeijThe larger the probability is, for example, the probability of selecting the next node a according to the basic ant colony algorithm is 0.8, the probability of selecting the next node B is 0.5, the probability of selecting the next node C is 0.2, the safety factor of the road from the current node to the next node a is 0.1, the safety factor of the road from the current node to the next node B is 0.8, and the safety factor of the road from the current node to the next node C is 0.2, and then the probabilities of actually selecting A, B, C by the ant after considering the safety factors are 0.08, 0.4, and 0.04 respectively.
In general, in solving the TSP problem, it is assumed that each ant in the ant colony algorithm has the following characteristics:
each shift, each ant leaves a pheromone on the branch (i, j) it passes through.
The probability of ants selecting cities is related to the distance between cities and the pheromone margin contained in the current connecting branches.
In order to force an ant to move legally, it is not allowed to walk the visited city until one movement is completed (this can be controlled by a tabu list); for example: recording the city that ant k currently walks through with tabu (j ═ 1, 2, 3, … …, m), the set is dynamically adjusted as the tabu evolves. In the searching process, ants calculate the state transition probability according to the information quantity on each path and the heuristic information of the path.
In combination with the present solution,representing the state transition probability of the ant k from the current node i to the target access node j after considering the safety factor at the time t,
τij(t) is the amount of information on the side (i, j) at time t;
allowedk＝{C-tabukrepresents the node that ant k allows to select next;
α are information heuristic factors representing the relative importance of the trajectory;
β is an expected heuristic factor, which reflects the degree of importance of the heuristic information of ants in the course of movement;
dijthe distance between two nodes is represented, and the value range can be quantized to (1-10).
Preferably, in the present scheme, d may be set after considering the safety factorijModified, e.g. after modificationThe larger the safety factor of the same road is, the corrected dijThe smaller the' the more likely it will be selected.
Further, in order to ensure that the finally obtained route is optimal, the method performs iteration of the improved ant colony algorithm according to the actual situation until the iteration number reaches a preset iteration number (which is adjustable, for example, 50 times, 100 times, and the like), and then takes the last obtained route as the final target route, namely, the route which combines the safety factor and has the shortest distance.
According to the method, a route planning request input by a user is received, the route planning request comprises a trip starting point and a trip end point, each road between the trip starting point and the trip end point and the safety coefficient of each road are obtained, a node matrix is constructed according to the trip starting point, the trip end point and each road, the shortest path from the trip starting point to the trip end point is searched in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road to be used as a target path, the trip safety is considered, the shortest stroke or the shortest distance is simultaneously considered, and the technical problem that the travel safety of the user is not considered in map navigation in the prior art is solved.
Referring to fig. 3, fig. 3 is a schematic flow chart of a second embodiment of the route planning method based on the improved ant colony algorithm according to the present invention.
Based on the first embodiment, in this embodiment, the step S20 includes:
step S201: acquiring each road between the travel starting point and the travel ending point and information of each road;
it should be noted that, the route planning request input by the user is usually a travel starting point and a travel ending point input by the user on the electronic map. Each road information may be accident information, vehicle speed information, road factor information, user evaluation information, or street view image of the road.
Step S202: and determining the safety factor of each road according to the information of each road.
In specific implementation, the safety factor of each road is determined according to the information of each road, the safety factor of each road can be determined by comprehensively considering the accident information, the vehicle speed information and the road factor information, the safety factor of each road can be corrected by combining the evaluation information of a user, the safety factor can be determined by analyzing the congestion rate, the greening rate and the like of the road by combining the street view image of the road, and the safety factor of each road can be comprehensively analyzed by simultaneously considering the information.
Referring to fig. 4, fig. 4 is a schematic flow chart of a third embodiment of the route planning method based on the improved ant colony algorithm according to the present invention.
Based on the second embodiment, the road information includes accident information, vehicle speed information, and road factor information, in this embodiment, the step S202 specifically includes:
step S2021: respectively determining an accident index, a vehicle speed index and a road factor index according to the accident information, the vehicle speed information and the road factor information;
it should be noted that, the general accident information includes the number of deaths of people in the preset time period of the road and the number of accidents of vehicles in the preset time period, and because the number of people and the number of vehicles in the area to which the road belongs are different, the accident index is generally determined by combining the number of people and the number of vehicles in the area to which the road belongs.
Number of people died in traffic accident preset time in road area/(number of people in road area x number of motor vehicles in road area)1/2。
Generally, when other conditions are consistent, the higher the accident index of the area to which the road belongs, the lower the safety factor of the road.
The vehicle speed information usually includes the average vehicle speed v1 and the design vehicle speed v of various cars in the free flow traffic state, and may also be the average vehicle speed v2 and the design vehicle speed v of more than 75% of various cars in the free flow traffic state.
Correspondingly, the vehicle speed index is | v1-v | or | v2-v |. Generally, the higher the vehicle speed index, the lower the road safety factor, if other conditions are consistent.
The road factor information includes the flatness of the road, which affects the comfort and safety of the vehicle. Generally, under the condition that other conditions are consistent, the flatness of the road is better, the road factor index is higher, and the road safety factor is higher.
Step S2022: and determining the safety factor of each road according to the accident index, the vehicle speed index and the road factor index.
During specific implementation, the safety coefficient of each road is inversely proportional to the accident index, inversely proportional to the vehicle speed index and directly proportional to the road factor index. Safety factor of each roadGamma is an accident index, tau is a vehicle speed index, and delta is a road factor.
In addition, the safety factor of each road can also comprise historical evaluation of road safety, and the safety factor of the road is corrected by obtaining the evaluation of the user on the road safety; the method also can comprise the steps of determining the congestion rate, the greening rate and the like by acquiring street view images and analyzing the street view images so as to judge the safety factor; or the street view image and the road safety evaluation are combined, and the safety factor is comprehensively considered.
Referring to fig. 5, fig. 5 is a schematic flow chart of a fourth embodiment of the route planning method based on the improved ant colony algorithm according to the present invention.
Based on the third embodiment, the accident information includes the number of police, the number of road traffic accidents in the area, the number of dead people in the area, the number of motor vehicles in the area and the number of people in the area; in this embodiment, the step S2021 specifically includes:
step S2021 a: determining the accident index according to the number of police officers, the number of road traffic accidents in the area, the number of dead people of the road traffic accidents in the area, the number of motor vehicles in the area and the number of people in the area;
specifically, the step of determining the accident index according to the police number, the number of road traffic accidents in the area, the number of dead people in the road traffic accidents in the area, the number of motor vehicles in the area and the number of people in the area comprises the following steps:
according to the formulaCalculating the accident index;
wherein γ represents an accident index;
n represents the weight of the death number of the road traffic accident in the area;
n1 represents the number of police calls;
n2 represents the number of road traffic accidents in the area;
n3 represents the number of road traffic accident deaths in the area;
m1 represents the number of vehicles in the zone;
m2 indicates the number of people in the area.
Furthermore, an embodiment of the present invention further provides a storage medium, where a route planning program based on an improved ant colony algorithm is stored, and the route planning program based on the improved ant colony algorithm, when executed by a processor, implements the steps of the route planning method based on the improved ant colony algorithm as described above.
Referring to fig. 6, fig. 6 is a block diagram illustrating a first embodiment of a route planning device based on an improved ant colony algorithm according to the present invention.
As shown in fig. 6, a route planning device based on an improved ant colony algorithm according to an embodiment of the present invention includes:
a receiving module 601, configured to receive a route planning request input by a user, where the route planning request includes a travel starting point and a travel ending point;
it should be noted that, the route planning request input by the user is usually a travel starting point and a travel ending point input by the user on the electronic map.
The electronic map is a modern information product which takes a visual digital map as a background, takes multimedia such as texts, pictures, icons, sounds, animations, videos and the like as expression means, and takes hardware equipment as a processing platform to show comprehensive appearances of areas such as cities, enterprises, tourist attractions and the like.
An obtaining module 602, configured to obtain each road between the trip starting point and the trip ending point, and a safety factor of each road;
it should be noted that there may be several passable routes from the trip starting point to the trip end point, and each route is composed of many roads, and after determining each road from the trip starting point to the trip end point, based on the safety factor of each road, a route with the shortest distance, that is, a target route is found, and the target route combines the safety factor, not only considering the distance problem.
The safety factor of each road may be obtained according to user evaluation, or may be obtained based on street view image analysis, and street view image analysis mainly analyzes congestion rate, greening rate, and width of the road, for example, an excessively narrow road with little smoke is generally considered as a road with a low safety factor. The street view image can be obtained in a conventional obtaining mode, and can also be obtained from a camera file by receiving the camera file sent by a collecting vehicle.
A building module 603, configured to build a node matrix according to the trip starting point, the trip end point, and each road;
during specific implementation, a node matrix is constructed, a travel starting point and a travel end point are respectively used as a starting node and a stopping node, and then the node when the ant selects is determined according to the end points of roads from the starting node to the stopping node. For example, starting at a and ending at B, a to B may be on the way C to D, and C, D acts as a node that ants may select.
The searching module 604 is configured to search, according to the improved ant colony algorithm and the safety factors of the roads, the shortest path from the travel starting point to the travel destination in the node matrix as a target path.
According to the method, a route planning request input by a user is received, the route planning request comprises a trip starting point and a trip end point, each road between the trip starting point and the trip end point and the safety coefficient of each road are obtained, a node matrix is constructed according to the trip starting point, the trip end point and each road, the shortest path from the trip starting point to the trip end point is searched in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road to be used as a target path, the trip safety is considered, the shortest stroke or the shortest distance is simultaneously considered, and the technical problem that the travel safety of the user is not considered in map navigation in the prior art is solved.
Other embodiments or specific implementation manners of the route planning device based on the improved ant colony algorithm may refer to the above method embodiments, and are not described herein again.
It should be noted that, in this document, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or system that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or system. Without further limitation, an element defined by the phrase "comprising an … …" does not exclude the presence of other like elements in a process, method, article, or system that comprises the element.
The above-mentioned serial numbers of the embodiments of the present invention are merely for description and do not represent the merits of the embodiments.
Through the above description of the embodiments, those skilled in the art will clearly understand that the method of the above embodiments can be implemented by software plus a necessary general hardware platform, and certainly can also be implemented by hardware, but in many cases, the former is a better implementation manner. Based on such understanding, the technical solutions of the present invention may be embodied in the form of a software product, which is stored in a storage medium (e.g., a rom/ram, a magnetic disk, an optical disk) and includes instructions for enabling a terminal device (e.g., a mobile phone, a computer, a server, an air conditioner, or a network device) to execute the method according to the embodiments of the present invention.
The above description is only a preferred embodiment of the present invention, and not intended to limit the scope of the present invention, and all modifications of equivalent structures and equivalent processes, which are made by using the contents of the present specification and the accompanying drawings, or directly or indirectly applied to other related technical fields, are included in the scope of the present invention.
Claims (10)
1. A route planning method based on an improved ant colony algorithm is characterized by comprising the following steps:
receiving a route planning request input by a user, wherein the route planning request comprises a travel starting point and a travel terminal point;
acquiring each road between the travel starting point and the travel terminal point and the safety coefficient of each road;
constructing a node matrix according to the travel starting point, the travel destination and each road;
and searching the shortest path from the travel starting point to the travel end point in the node matrix according to an improved ant colony algorithm and the safety factor of each road to serve as a target path.
2. The improved ant colony algorithm-based route planning method according to claim 1, wherein the step of searching the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road comprises:
correcting the probability of all ants accessing the next node from the current node in the node matrix according to an improved ant colony algorithm and the safety coefficient of each road until all the nodes are accessed by the ants;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; wherein the improved ant colony algorithm is as follows:
wherein,probability of selecting j node for ant k; allowedkRepresenting the set of destination nodes that ant k may pick next, α representing the information heuristics, β representing the expected heuristics, i representing the current node, j representing the next destination node, s representing the node combination, ηij(t) represents a heuristic function; tau isij(t) represents a pheromone; lambda [ alpha ]ijThe safety factor of the road corresponding to the next target node.
3. The improved ant colony algorithm-based route planning method according to claim 1, wherein the step of searching the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road comprises:
according to the improved ant colony algorithm, all ants visit the next node from the current node in the node matrix;
according to the safety coefficient and the correction function of each road, correcting the distance from the current node to the next node until the ant has visited all the nodes;
calculating the length of a path passed by each ant, and taking the shortest path from the travel starting point to the travel end point as a target path; wherein,
the correction function is:
the improved ant colony algorithm comprises the following steps:
wherein,probability of selecting j node for ant k; allowedkRepresenting the set of destination nodes that ant k may pick next, α representing the information heuristics, β representing the expected heuristics, i representing the current node, j representing the next destination node, s representing the node combination, ηij(t) represents a heuristic function,dijrepresenting the distance between two nodes; tau isij(t) represents a pheromone; lambda [ alpha ]ijThe safety factor of the road corresponding to the next target node.
4. The improved ant colony algorithm-based route planning method according to claim 1, wherein the step of obtaining roads between the travel starting point and the travel ending point and safety factors of the roads comprises:
acquiring each road between the travel starting point and the travel ending point and information of each road;
and determining the safety factor of each road according to the information of each road.
5. The improved ant colony algorithm-based route planning method according to claim 4, wherein the road information comprises accident information, vehicle speed information, road factor information;
correspondingly, the step of determining the safety factor of each road according to the information of each road comprises the following steps:
respectively determining an accident index, a vehicle speed index and a road factor index according to the accident information, the vehicle speed information and the road factor information;
and determining the safety factor of each road according to the accident index, the vehicle speed index and the road factor index.
6. The improved ant colony algorithm based route planning method according to claim 5, wherein the accident information comprises a number of police officers, a number of road traffic accidents in the area, a number of dead people from road traffic accidents in the area, a number of motor vehicles in the area and a number of people in the area;
correspondingly, the step of respectively determining an accident index, a vehicle speed index and a road factor index according to the accident information, the vehicle speed information and the road factor information comprises the following steps:
and determining the accident index according to the police number, the number of road traffic accidents in the area, the number of dead people in the road traffic accidents in the area, the number of motor vehicles in the area and the number of people in the area.
7. The improved ant colony algorithm based route planning method according to claim 6, wherein the step of determining the accident indicator according to the number of police officers, the number of road traffic accidents in the area, the number of road traffic accident deaths in the area, the number of motor vehicles in the area and the number of people in the area comprises:
according to the formulaCalculating the accident index;
wherein γ represents an accident index;
n represents the weight of the death number of the road traffic accident in the area;
n1 represents the number of police calls;
n2 represents the number of road traffic accidents in the area;
n3 represents the number of road traffic accident deaths in the area;
m1 represents the number of vehicles in the zone;
m2 indicates the number of people in the area.
8. A route planning device based on an improved ant colony algorithm, comprising:
the system comprises a receiving module, a route planning module and a route planning module, wherein the receiving module is used for receiving a route planning request input by a user, and the route planning request comprises a travel starting point and a travel terminal point;
the obtaining module is used for obtaining each road between the travel starting point and the travel terminal point and the safety coefficient of each road;
the construction module is used for constructing a node matrix according to the travel starting point, the travel end point and each road;
and the searching module is used for searching the shortest path from the travel starting point to the travel destination in the node matrix according to the improved ant colony algorithm and the safety factor of each road, and taking the shortest path as a target path.
9. A terminal, characterized in that the terminal comprises: a memory, a processor and a modified ant colony algorithm based routing program stored on the memory and executable on the processor, the modified ant colony algorithm based routing program configured to implement the steps of the modified ant colony algorithm based routing method of any one of claims 1 to 7.
10. A storage medium, characterized in that the storage medium stores thereon a route planning program based on the improved ant colony algorithm, and the route planning program based on the improved ant colony algorithm realizes the steps of the route planning method based on the improved ant colony algorithm according to any one of claims 1 to 7 when being executed by a processor.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811451979.9A CN109726852A (en) | 2018-11-30 | 2018-11-30 | Based on route planning method, device, terminal and the medium for improving ant group algorithm |
| PCT/CN2018/122837 WO2020107583A1 (en) | 2018-11-30 | 2018-12-21 | Improved ant colony algorithm-based path planning method, apparatus, terminal and medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811451979.9A CN109726852A (en) | 2018-11-30 | 2018-11-30 | Based on route planning method, device, terminal and the medium for improving ant group algorithm |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109726852A true CN109726852A (en) | 2019-05-07 |
Family
ID=66295178
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811451979.9A Withdrawn CN109726852A (en) | 2018-11-30 | 2018-11-30 | Based on route planning method, device, terminal and the medium for improving ant group algorithm |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN109726852A (en) |
| WO (1) | WO2020107583A1 (en) |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109726851A (en) * | 2018-11-30 | 2019-05-07 | 平安科技（深圳）有限公司 | Based on route planning method, device, terminal and the medium for improving ant group algorithm |
| CN110909670A (en) * | 2019-11-21 | 2020-03-24 | 江苏理工学院 | An Unstructured Road Recognition Method |
| CN112347313A (en) * | 2020-11-10 | 2021-02-09 | 中国科学院、水利部成都山地灾害与环境研究所 | A method of location dominance path analysis based on big data |
| CN112396228A (en) * | 2020-11-16 | 2021-02-23 | 西安宇视信息科技有限公司 | Target path determination method, device, electronic equipment and medium |
| CN113094859A (en) * | 2021-04-20 | 2021-07-09 | 嘉兴泰豪装备技术有限公司 | Electric control box line wiring optimization method, system and storage medium |
| CN113280828A (en) * | 2021-05-17 | 2021-08-20 | 建信金融科技有限责任公司 | Path planning method, device, equipment and storage medium |
| CN115203795A (en) * | 2022-07-11 | 2022-10-18 | 三明学院 | Building streamline generation method, device, equipment and storage medium |
| CN115265572A (en) * | 2022-07-25 | 2022-11-01 | 中国银行股份有限公司 | Path generation method, device, equipment and medium |
| CN115294791A (en) * | 2022-07-29 | 2022-11-04 | 广州市粤迅特数码技术有限公司 | An intelligent traffic guidance system for smart cities |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113326980A (en) * | 2021-05-25 | 2021-08-31 | 汕头大学 | Regional scenery spot one-way route multi-target planning method for improving ant colony algorithm |
| CN121119330A (en) * | 2025-09-04 | 2025-12-12 | 南兴装备股份有限公司 | A method and system for wire-wrap cutting based on ant colony hybrid path optimization |
| CN121140833B (en) * | 2025-11-19 | 2026-02-06 | 浙江理工大学 | Automobile path planning method based on dynamic pheromone punishment coefficient and application |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105589461A (en) * | 2015-11-18 | 2016-05-18 | 南通大学 | Parking system path planning method on the basis of improved ant colony algorithm |
| CN106779212A (en) * | 2016-12-13 | 2017-05-31 | 南京邮电大学 | A kind of city tour's route planning method based on improvement ant group algorithm |
| CN106971245A (en) * | 2017-03-30 | 2017-07-21 | 广东工业大学 | A kind of determining method of path and system based on improvement ant group algorithm |
| WO2018176595A1 (en) * | 2017-03-31 | 2018-10-04 | 深圳市靖洲科技有限公司 | Unmanned bicycle path planning method based on ant colony algorithm and polar coordinate transformation |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9057622B2 (en) * | 2012-02-08 | 2015-06-16 | Here Global B.V. | Method and system for routing using uncertainty data |
| CN106708063A (en) * | 2017-03-22 | 2017-05-24 | 江南大学 | Route planning method for search and rescue robot in chemical disaster scene |
| CN108180914B (en) * | 2018-01-09 | 2021-06-18 | 昆明理工大学 | A Path Planning Method for Mobile Robots Based on Ant Colony Improvement and Spike Smoothing |
-
2018
- 2018-11-30 CN CN201811451979.9A patent/CN109726852A/en not_active Withdrawn
- 2018-12-21 WO PCT/CN2018/122837 patent/WO2020107583A1/en not_active Ceased
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105589461A (en) * | 2015-11-18 | 2016-05-18 | 南通大学 | Parking system path planning method on the basis of improved ant colony algorithm |
| CN106779212A (en) * | 2016-12-13 | 2017-05-31 | 南京邮电大学 | A kind of city tour's route planning method based on improvement ant group algorithm |
| CN106971245A (en) * | 2017-03-30 | 2017-07-21 | 广东工业大学 | A kind of determining method of path and system based on improvement ant group algorithm |
| WO2018176595A1 (en) * | 2017-03-31 | 2018-10-04 | 深圳市靖洲科技有限公司 | Unmanned bicycle path planning method based on ant colony algorithm and polar coordinate transformation |
Non-Patent Citations (2)
| Title |
|---|
| 崔玉胜;: "利用加权法改进的蚁群算法在车载导航中的应用", 闽江学院学报, no. 02, pages 74 - 78 * |
| 王辉;王景良;朱龙彪;邵小江;王恒;: "基于改进蚁群算法的泊车系统路径规划", 控制工程, no. 02, pages 73 - 78 * |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109726851A (en) * | 2018-11-30 | 2019-05-07 | 平安科技（深圳）有限公司 | Based on route planning method, device, terminal and the medium for improving ant group algorithm |
| CN110909670A (en) * | 2019-11-21 | 2020-03-24 | 江苏理工学院 | An Unstructured Road Recognition Method |
| CN112347313A (en) * | 2020-11-10 | 2021-02-09 | 中国科学院、水利部成都山地灾害与环境研究所 | A method of location dominance path analysis based on big data |
| CN112396228A (en) * | 2020-11-16 | 2021-02-23 | 西安宇视信息科技有限公司 | Target path determination method, device, electronic equipment and medium |
| CN113094859A (en) * | 2021-04-20 | 2021-07-09 | 嘉兴泰豪装备技术有限公司 | Electric control box line wiring optimization method, system and storage medium |
| CN113280828A (en) * | 2021-05-17 | 2021-08-20 | 建信金融科技有限责任公司 | Path planning method, device, equipment and storage medium |
| CN115203795A (en) * | 2022-07-11 | 2022-10-18 | 三明学院 | Building streamline generation method, device, equipment and storage medium |
| CN115265572A (en) * | 2022-07-25 | 2022-11-01 | 中国银行股份有限公司 | Path generation method, device, equipment and medium |
| CN115294791A (en) * | 2022-07-29 | 2022-11-04 | 广州市粤迅特数码技术有限公司 | An intelligent traffic guidance system for smart cities |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2020107583A1 (en) | 2020-06-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109726852A (en) | Based on route planning method, device, terminal and the medium for improving ant group algorithm | |
| CN112766607B (en) | Travel route recommendation method and device, electronic device and readable storage medium | |
| US9200910B2 (en) | Ranking of path segments based on incident probability | |
| US9964410B2 (en) | System and method for the calculation and use of travel times in search and other applications | |
| US20210341300A1 (en) | Method, apparatus, and system for providing a personally relevant navigation route comparison | |
| US10424202B1 (en) | Parking strategy recommendation based on parking space availability data | |
| CN112801399B (en) | Path generation method and device, terminal equipment and storage medium | |
| CN111326015A (en) | Parking spot recommendation method and device | |
| US11761772B2 (en) | Method and apparatus for providing speculative navigation routing in incomplete offline maps | |
| US12123726B2 (en) | Method and apparatus for ridesharing pickup wait time prediction | |
| CN115273524B (en) | How to reserve a time-sharing parking lot | |
| US10209088B2 (en) | Method and apparatus for route calculation considering potential mistakes | |
| US11346683B2 (en) | Method and apparatus for providing argumentative navigation routing | |
| CN117521937A (en) | Dynamic path induction method and system suitable for multi-dimensional collaborative sensing environment | |
| RU2664034C1 (en) | Traffic information creation method and system, which will be used in the implemented on the electronic device cartographic application | |
| CN115691203A (en) | A method, device, equipment and readable storage medium for inducing berths on urban roads | |
| CN110363358B (en) | Prediction method of public transportation sharing rate based on multi-agent simulation | |
| CN106949899A (en) | A kind of bicycle transfer public transport combined type Route Generation device and route generation method | |
| CN109726851A (en) | Based on route planning method, device, terminal and the medium for improving ant group algorithm | |
| WO2022163366A1 (en) | Information processing method, information processing device, information processing program, and display device | |
| JP2019078687A (en) | Information processing apparatus, information providing system, information providing method, and program | |
| JP2026505786A (en) | Utilizing transition times to intelligently select transition locations for autonomous vehicles - Patents.com | |
| CN114791732B (en) | Path planning method, device, equipment and computer readable storage medium | |
| CN114295144B (en) | DIKW-based vehicle path planning method | |
| JP5322080B2 (en) | Map information display device and map information display method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WW01 | Invention patent application withdrawn after publication |
Application publication date: 20190507 |
|
| WW01 | Invention patent application withdrawn after publication |