KR100485867B1 - System for route searching of car and method thereof - Google Patents

Abstract

The present invention relates to a route search system and a method of a vehicle. To this end, the present invention is connected to a traffic information server and receives traffic information for a route request between a route requester's origin and a destination through a mobile communication network. The method includes a method of performing a route search reflecting map information, calculating an optimal route using a weight vector reflecting road characteristics within a predetermined search distance between a starting point and a destination, and transmitting the optimal route to a route requester, and a system using the same.

Therefore, the present invention processes the traffic information collected in real time and uses it as the basic cost of route search, and provides the route requester through the mobile communication network with the route generated by applying the weight vector to the traffic information to meet the characteristics of the rotation and the road. It provides the effect of improving the accuracy of route search using traffic information.

Description

System for route searching of car and method

The present invention relates to a vehicle route search system and method, and more particularly, to a vehicle route search system and method for improving the accuracy of the route search by applying the traffic information collected in real time as a weight vector.

The route that the driver chooses from the origin to the destination is very important for the driver's convenience or economics.

As communication technology develops, a driver may request a route from a desired starting point to a destination through a mobile terminal to a traffic center for providing a route.

In response to the driver's route request, the traffic center uses the traffic information and the map information to provide a route suitable for the driver by applying route search techniques such as the shortest route, multipath, and optimal route.

However, since the traffic information used in the traffic center is collected toward the straight center of the driving vehicle, the information about the turn, the right turn, and the U-turn, such as the left turn, is not reflected at all, so that the accuracy of the route search is poor. There is a problem.

In addition, traffic information is collected irrespective of the characteristics of driving roads such as highways, national roads, bridges, overpasses, underground roads, and facilities such as tunnels. Has a problem.

The present invention is to solve the above problems, an object of the present invention is to provide a route search system and method of a vehicle that can improve the accuracy of the route search by performing a route search by reflecting traffic information on the rotation and road characteristics To provide.

Features of the route search method of a vehicle according to the present invention for realizing the above object are a) collecting traffic information to prepare a basic cost, and a route search between a starting point and a destination in a terminal having a vehicle navigation program; Starting a route search between a starting point and a destination by using map information and traffic information when requested; b) if a route search is started in step a), determining a search level according to the distance between the starting point and the destination, and selecting a candidate node at the search level; c) performing a forward path search from the candidate node selected in step b) to a destination, and searching for a rear path from the candidate node to a starting point within a predetermined range of the destination; And d) connecting the front path and the rear path searched in step c) to complete the path search.

The determining of the search level in the step b) may include performing a single level search when the search distance between the starting point and the destination is a short distance, and performing a multilevel search when the search distance is a long distance. The multilevel search selects candidate nodes at a higher level by setting only intercity main roads within a search distance as a search area.

In the step c), the route search is performed by applying an optimal route algorithm that searches the shortest distance using the priority of the route cost between the source and the destination.

The optimal path algorithm,

A) recording, for all candidate nodes between the source and destination, a temporary beacon that is the estimated shortest distance from the source to each node; B) recording the permanent label which is the actual shortest distance from the starting point to each node by selecting a minimum value from the temporary signs recorded in step a); C) modify the temporary markers of all neighboring nodes of the node permanently marked in step b), compare the temporary marker with the value of the cost of the link, and select the minimum value, and then return to step b). Grinding step; And d) terminating the algorithm if no temporary cover is found through steps b) and c).

The step of performing the path search in step c),

A search limit algorithm for setting two circles whose radius is a result of adding a constant value to the straight line distance between the starting point and the destination, and applying a search limiting algorithm for limiting the overlapping portions of the two circles to the path search range.

The step of performing the path search in step c),

Using the current traffic information collected within the search distance between the starting point and the destination, a route search is performed by applying a weight vector of traffic information such as rotation weights, link property weights, facility weights, and road type weights.

The rotation weight among the weight vectors of the traffic information is calculated based on the rotation type, the congestion of the entry / exit link, the road type of the entry link, the number of lanes of the entry link, and the node type. The rotation weight Wt is calculated using Equation 1 below.

Among the weight vectors of the traffic information, link attribute weights are classified by link types such as main line separation / non-separation, connection path (JC / IC), service area layer, and passageway, and apply constant weight to each. do.

Among the weight vectors of the traffic information, the facility weight is a constant weight applied to the property of the facility that passes through the intersection such as general road, bridge, tunnel, overpass, and underground without signal.

Among the weight vectors of the traffic information, road weights apply constant weights to highways, urban highways, national highways, nationally supported local roads, provincial roads, main roads, and other roads so as to carry out road-oriented guidance for driver convenience.

The step of performing the path search in step c),

Apply a search limiting algorithm that limits the search distance by using the area distance between the starting point and the destination, and applies a weight vector reflecting the characteristics of the road by using the traffic information collected within the search distance. The optimal path algorithm is applied to search the shortest distance using the priority of the path cost of each candidate node of the search distance.

On the other hand, the feature of the vehicle route search system according to the present invention, traffic information server for collecting the current traffic information in real time to process the data suitable for the route search; And a route search reflecting the traffic information and the map information for the route request between the originator and the destination of the route requester through a mobile communication network by receiving the traffic information connected to the traffic information server. It includes a route search server for calculating the optimum route to which the weight vector reflecting the characteristics of the road within a constant search distance between the distance and transmitting it to the route requester.

The route search server includes: a shared memory for managing an old version of a map database and a new version of a map database; A path search engine in which a path search algorithm is embedded to perform a path search process when the path request of the path requester is transmitted through middleware; And modify / view / manage the map information of the shared memory through a resident program to modify / view / manage the map information of the administrator, and receive the traffic information update signal of the server of the traffic information, It includes a processor for updating information.

The route search server sets an optimal route algorithm that searches the shortest distance by using the priority of the route cost between the origin and destination, and sets two circles whose radius is the result of adding a constant value to the linear distance between the origin and the destination. A search limit algorithm for limiting the overlapping portions of the two circles to a route search range, and using the current traffic information collected within the search distance between the starting point and the destination, rotation weights, link property weights, facility weights, facility weights, The route search is performed by selectively applying the route search applying the weight vector of traffic information such as the weight of each road type.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

It is apparent to those skilled in the art that the information mentioned in any one embodiment can be applied to other embodiments even if it is not specifically mentioned in the other embodiments.

1 illustrates a configuration of a route search system for a vehicle according to an embodiment of the present invention.

As shown in FIG. 1, the system of the embodiment according to the present invention includes a traffic information server 100, a route search server 200, a terminal 300, and a manager computer 400.

The traffic information server 100 collects and processes general information on the current traffic situation through a traffic information collecting device such as an image detector or a probe car.

The route search server 200 performs the route search reflecting the traffic information and the map information with respect to the route request of the terminal 300 and transmits the route search result to the terminal 300 in response. The path search server 200 includes a shared memory 220, a path search engine 210, and a processor 230.

The shared memory 220 stores route search map information, and manages an old version map database and a new version map database.

The path search engine 210 includes a path search algorithm so that the path request of the terminal 300 is received through the middleware, and the path search is performed by referring to the map information of the shared memory 220.

The processor 230 modifies / views / manages the map information of the shared memory 220 through the orpman daemon (Daemon) as a signal for modifying / viewing / managing the map information of the manager computer 400.

The processor 230 may update the traffic information by receiving an update signal from the traffic information server 100 through the orpman daemon, and the update period of the traffic information is updated every 5 minutes.

2 is a flowchart illustrating a path searching method of a vehicle according to an exemplary embodiment of the present invention.

As shown in FIG. 2, in the vehicle route searching method according to the embodiment of the present invention, a route requester requests a route between a starting point and a destination by accessing a mobile communication network using the terminal 300 (S10). The route request is transmitted to the route search engine 210 through the middleware of the route search server 200, and the route search engine 210 maps the traffic information transmitted from the traffic information server 100 and the shared memory 220. The route search is started with reference to the information (S20, S30).

The route search engine 210 checks whether the search section distance between the starting point and the destination is short or long distance. (S40) At this time, the route search engine 210 determines the search level by referring to the table 1 below for the search section distance. do.

Search section distance (km) Highest search level 25 or less 7-single level navigation 25-70 5-multilevel navigation 70-100 4-multilevel navigation 100 or more 3-multilevel navigation

If the search interval is shorter than 25 km, the path search engine 210 performs a single level search (S51), and selects candidate nodes at the corresponding level (S52).

The path search engine 210 searches the forward path from the selected candidate node to the destination (S53), and after searching the rear path from the candidate node to the starting point (S54), the forward path search result and the backward path search result. Combine to complete the path search (S55, S70).

On the other hand, when the search section distance is longer than 25km, the path search engine 210 performs a multilevel search corresponding to the search section distance with reference to Table 1 (S61).

The path search engine 210 applies a top-down method of starting a path search at a higher level in the multilevel search (S62).

In the case of a long distance of the search section, roads existing in the search area search for a considerable number of roads including a longitudinal road in addition to the main road. Indeed, the driver often uses major intercity roads such as highways and national highways for long distances.

Therefore, the route search using the top-down method sets only the interstate main connecting road as the search area without having to search all the roads in the search area.

3 illustrates a multilevel search process using a top-down method.

As shown in FIG. 3, the path search engine 210 selects candidate nodes at a higher level during the path search by applying a top-down method (S63), and performs a forward path search from the candidate node to the destination G ( In S64), candidate paths are searched backward from the candidate nodes to the starting point S within a predetermined range of the destination. (S65)

The path search engine 210 combines the front path search result with the rear path search result to complete the path search process (S66, S70).

In the above, when the search section distance is short or long distance, the path search engine 210 applies the Dijkstra algorithm, search limit algorithm, and weight vector of traffic information to the forward path search and the backward path search. You can increase the accuracy.

In the embodiment of the present invention, the optimal path algorithm, search limit algorithm, and weight vector of traffic information are all applied to the path search. However, an appropriate algorithm or method may be selected and applied to the path search in some cases.

The optimal path algorithm is based on the existing Dijkstra's algorithm, which is a Tree Building Algorithm, the shortest cost tree from any point using the Priority Queue. Is to create a Tree.

The best path algorithm terminates the algorithm when the destination is included in the search tree when calculating the path between two points of origin and destination.

Hereinafter, the procedure of the optimal path algorithm, first, d _hj (j = 1, 2, .., N-1) is recorded as a temporary label π _i for all the nodes j on the network. ), If there is no link connecting j, then d _hj = ∞ (π _{i ←} d _hj, π _h ^＊ ← 0)

The marker is a record of each node's shortest distance estimate from the source node to all nodes in the network, where π _i is the estimated shortest distance from the source node to each node, and π _i ^* is the actual shortest distance from the source node to each node. to be.

d _hj is the path length from nodes h to j and N is the total number of nodes on the network.

Next, select the minimum value among all temporary markers (π _i) and make it a permanent marker (π _i ^＊ ), and if the permanent labeled node is i, then π _{i ←} min _j (π _i ), π _h ^＊ ← π _i .

The temporary markers of all adjacent nodes j of the permanently marked node I are modified, and a small value is selected by comparing the permanent marker (π _i ^＊ ) with the cost d _ij of the link and the existing temporary marker π _j . (π _j ← min (π _j, π _i ^＊ + d _ij ))

If there is no longer a temporary mark, the optimal path algorithm terminates.

The search limiting algorithm, on the other hand, limits the search range in order to improve the search speed because the electrode road network is so large that the search time is long.

4 illustrates a search area limited by applying a search limit algorithm.

The general search limiting technique uses an A * algorithm, but the search limiting algorithm used in the embodiment of the present invention uses two circles whose radius is obtained by adding a constant value to the linear distance between the search points as shown in FIG. Then, the area where the two circles overlap is defined as the search range.

At this time, the administrator can change the constant value added to the straight line distance between the search points.

The route search using the weight vector of the traffic information currently uses traffic information collected through the traffic information server 100. The traffic information used for the route search collects link information between each node and passes through each link. It consists of speed, travel time and congestion.

 In the embodiment according to the present invention, the weight is calculated by applying various weight vectors and rotation weight vectors reflecting the characteristics of the road when searching for a route.

First, (a) the rotation weight is passed through the node because traffic information about the rotation passing through the node during the progress from the link to the link is excluded when the traffic information collected by the traffic information server 100 is still used without processing. Is to apply a weight to the rotation.

The rotation weighting application calculates travel time on the basis of turn / congestion / road type in order to reflect the turn travel time between links such as the delay time of intersection crossing.

The rotation weight vector is the type of rotation (straight, left, right, u-turn, etc.), the congestion of the entry / exit link, the road type of the exit link, the number of lanes of the exit link, and the node type (rotation weight is applied only to nodes with intersection attributes). .

Rotation weight Wt is calculated using Equation 1 below.

here, Is the reference rotation weight and the rotation weight when the road type of the entry / exit link is the same and the congestion is both smooth. Wow Is the weight according to the congestion of the entry and exit links, Is the weight according to the road type of the exit link, Denote weights according to the number of lanes of the exit link, respectively.

Above, the reference rotation weight value is a value that considers the travel time and stop signal in the case of ignoring the stop signal at the intersection and applies 13 seconds straight, 33 seconds left, 15 seconds right, and 33 seconds U-turn. Can be adjusted according to the signal of intersection.

Since the rotation greatly affects the congestion degree of the link through which the vehicle is going, the congestion weight for the entry / exit link is applied as shown in Table 2 below.

Weight according to congestion of entry link division weight Smoothly One going slow 1.2 Identity 2

Weight based on congestion of exit link division weight Smoothly One going slow One Identity 2

Weight based on lane number of exit link division weight More than 4 lanes round trip One 4 lanes round trip 1.1 2 lanes or less round trip 1.3

Weight according to road type of exit link division weight High speed / city express One Route One Local road One National Support Map One Main road 1 One Main road 2 1.1 Main road 3 1.1 Kita Road 1/2 1.2

(b) The link attribute weight is applied to reflect the characteristics that link roads such as ICs on general roads and JCs on high speed roads do not have speed compared to the main road.

Link types are classified into main line separation, main line non-separation, JC, IC, SA (Service Area), passageway of intersection, and the like, and apply constant weight to each as shown in Table 6.

The new travel time with link attribute weighting results from the original travel time multiplied by the link attribute weighting.

Link attribute weights One Main Line (Non-Separated) - Road with no up / down line 2 Main Line (Separate) - Road with separated up / down line (ex. Highway) 3 Connection line (JC) 1.3 4 Crosswalk - Right turn road divided into common island at the intersection 5 Connection path (IC) 1.5 6 SA layer 1.7 Service areas such as highway rest areas

(c) Facility weights reflect the characteristics of road facilities that pass through intersections such as overpasses and underground roads as shown in Table 7, and traffic facilities include general roads, bridges, tunnels, overpasses, and underground roads.

The new travel time with facility weights is the product of the original travel time times the facility weights.

Facility weight code facility weight One General road - 2 Bridges 1.2 3 tunnel - 4 Overpass 0.9 5 Underground road 0.9

(d) Road classification weights consider that drivers are driven primarily on large roads such as highways and national highways for convenience and safety, and no actual travel time difference applies.

In other words, road weights are weights that are applied to guide the route to comfortable and safe highways and are not calculated in the travel time.

The new travel time with road weights is the result of multiplying the road weight by the original travel time.

Road weight code Road type weight Normal optimal High speed priority 0 highway One One 0.5 One Urban highway One One 0.5 2 Route One 1.5 1.5 3 National Support Map One 1.7 1.7 4 Local road One 1.7 1.7 5 Main road 1 One 2.0 2.0 6 Main road 2 One 2.5 2.5 7 Main road 3 One 5.0 5.0 8 Other Road 1 2 5.0 5.0 9 Other road 2 2 5.0 5.0

In this way, the traffic information weight vector is calculated by applying the weight while the route search engine 210 performs the route search. The procedure is that when the traffic information (travel time) is input, the rotation weight (a) and the link attribute weight ( b) New facility time is calculated by applying facility weight (c) and road type weight (d).

Meanwhile, each constant value applied to the rotation weight, the link property weight, the facility weight, and the road type weight is statistically calculated and can be changed by the manager.

The drawings and detailed description of the invention are merely exemplary of the invention, which are used for the purpose of illustrating the invention only and are not intended to limit the scope of the invention as defined in the appended claims or claims. Therefore, those skilled in the art will understand that various modifications and equivalent other embodiments are possible from this. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

The route search system and method of the vehicle according to the present invention process the traffic information collected in real time and use it as the basic cost of route search, and apply the weight vector to the traffic information to the route requester through the mobile communication network. By providing the traffic information suitable for the characteristics of the turn and the road, it is possible to improve the accuracy of the route search.

1 illustrates a configuration of a route search system for a vehicle according to an embodiment of the present invention.

2 is a flowchart illustrating a path searching method of a vehicle according to an exemplary embodiment of the present invention.

3 illustrates a multilevel search process using a top-down method.

4 illustrates a search area limited by applying the present search limit algorithm.

Claims (16)

a) preparing a basic cost by collecting traffic information, and starting a route search between the starting point and the destination using the map information and the traffic information when a terminal having a vehicle navigation program requesting a route searching between the starting point and the destination; b) if a route search is started in step a), determining a search level according to the distance between the starting point and the destination, and selecting a candidate node at the search level; c) performing a forward path search from the candidate node selected in step b) to a destination, and searching for a rear path from the candidate node to a starting point within a predetermined range of the destination; And d) completing the path search by connecting the forward path and the backward path searched in step c). Route search method of a vehicle comprising a. The method of claim 1, Determining the search level in step b), A single level search is performed when the search distance between the starting point and the destination is a short distance, and a multilevel search is performed when the search distance is a long distance. The method of claim 2, The multi-level search method of selecting a candidate node at a higher level by setting only the interstate main roads within the search distance as a search area. The method of claim 1, The step of performing the path search in step c), And an optimum path algorithm for searching the shortest distance using the priority of the route cost between the starting point and the destination. The method of claim 4, wherein The optimal path algorithm, A) recording, for all candidate nodes between the source and destination, a temporary beacon that is the estimated shortest distance from the source to each node; B) recording the permanent label which is the actual shortest distance from the starting point to each node by selecting a minimum value from the temporary signs recorded in step a); C) modify the temporary signs of all neighboring nodes of the node permanently marked in step b), compare the temporary label with the value of the cost of the link, and select the minimum value, and then return to step b). Grinding step; And D) terminating the algorithm if no temporary cover is found through steps b) and c); Route search method of a vehicle comprising a. The method of claim 1, The step of performing the path search in step c), A route search of a vehicle, characterized by setting two circles having a radius as a result of adding a constant value to a straight line distance between the starting point and the destination, and applying a search limiting algorithm to limit a portion where the two circles overlap to a route search range. Way. The method of claim 1, The step of performing the path search in step c), Using the current traffic information collected within the search distance between the starting point and the destination, a route search is performed by applying a weight vector of traffic information such as rotation weights, link property weights, facility weights, and road type weights between links. The route search method of the vehicle. The method of claim 7, wherein The rotation weight among the weight vectors of the traffic information is calculated based on the rotation type, the congestion of the entry / exit link, the road type of the entry link, the number of lanes of the entry link, and the node type. The method of claim 8, The rotation weight Wt is calculated using the following equation; here, Is the reference rotation weight, Wow Is the weight according to the congestion of the entry and exit links, Is the weight according to the road type of the exit link, Denote weights according to the number of lanes of the exit link, respectively; Route search method of a vehicle, characterized in that. The method of claim 7, wherein Among the weight vectors of the traffic information, link attribute weights are classified by link types such as main line separation / non-separation, connection path (JC / IC), service area layer, and passageway, and apply constant weight to each. Route search method of a vehicle, characterized in that. The method of claim 7, wherein The facility weighting method among the weight vectors of the traffic information is a constant weighting method of the vehicle characterized in that the constant weight is applied to the property of the facility to pass through the intersection, such as general roads, bridges, tunnels, overpasses, underground roads without a signal. The method of claim 7, wherein Among the weight vectors of the traffic information, the weight of each road type is a constant weight applied to highways, urban highways, national highways, nationally supported local roads, provincial roads, main roads, and other roads for the purpose of large-scale guidance for driver convenience. The route search method of the vehicle. The method of claim 1, The step of performing the path search in step c), Apply a search limiting algorithm that limits the search distance by using the area distance between the starting point and the destination, and applies a weight vector reflecting the characteristics of the road by using the traffic information collected within the search distance. And applying an optimal path algorithm for searching the shortest distance by using the priority of the path cost of each candidate node of the search distance. A traffic information server that collects current traffic information in real time and processes the current traffic information into data suitable for route searching; And In response to the traffic information server connected to the traffic information server, a route search reflecting the traffic information and map information is performed on the route request between the originator and the destination of the route requester through the mobile communication network, and the route search is performed between the origin and the destination. A route search server that calculates an optimal route using a weight vector reflecting road characteristics and transmits it to the route requester within a certain search distance. Route navigation system of a vehicle comprising a. The method of claim 14, The route search server Shared memory for managing the old version of the map database, the new version of the map database; A path search engine in which a path search algorithm is embedded to perform a path search process when the path request of the path requester is transmitted through middleware; And Correct / view / manage the map information of the shared memory through the resident program to modify / view / manage the map information of the administrator, and receive the traffic information update signal of the server of the traffic information and transmit the traffic information at regular intervals. Processor to update Route navigation system of a vehicle comprising a. The method of claim 14, The route search server, The optimal path algorithm that searches the shortest distance using the priority of the route cost between the starting point and the destination, sets two circles whose radius is the result of adding a constant value to the straight line distance of the starting point and the destination, and the two circles Search limiting algorithm that limits the overlapping part to the range of route search, and traffic such as rotation weight, link property weight, facility weight, road type weight among each link using current traffic information collected within the search distance between origin and destination A route search system for a vehicle, characterized in that the route search is performed by selectively applying a route search applied a weight vector of information.