KR100678307B1 - Method For Finding The Shortest Path Including Restriction Condition - Google Patents

Abstract

1. TECHNICAL FIELD OF THE INVENTION

The present invention can be read by a computer that records a method for calculating an optimal route applying constraints such as left turn prohibition, U-turn, and P-turn in general urban road conditions and a program for realizing the method. To recordable media.

2. Technical problem to be solved by the invention

The present invention modifies the conventional Floyd-Warshall algorithm to restrict left turn, modern U-turn at intersection, allow U-turn at intersection, P-turn, etc. An object of the present invention is to provide a method for calculating an optimal path for accommodating conditions and a computer readable recording medium storing a program for realizing the method.

3. Summary of the Solution of the Invention

According to an aspect of the present invention, there is provided a method for calculating an optimal path using constraints applied to an optimal path calculating system, the method comprising: a first step of obtaining initial optimal distance matrices having an infinite distance value of a left turn prohibition section; Performing a trigonometric operation on each of the obtained initial optimum distance matrices to obtain an optimum distance matrix and an optimal path matrix; And a third step of selecting an optimal distance matrix having a minimum value among the obtained optimal distance matrices and obtaining an optimal path from the corresponding optimal path matrix.

4. Important uses of the invention

The present invention is used in a comprehensive logistics information system.

Best Distance, Best Path, Floyd-Warshall Algorithm, Trigonometry, Virtual Intersection

Description

Method for Finding The Shortest Path Including Restriction Condition}             

1 is an example of a network configuration for applying a conventional Floyd-Warshall algorithm.

Figure 2 is a configuration diagram of an embodiment of the optimum path calculation system to which the present invention is applied.

FIG. 3 is an exemplary diagram of a network configuration for applying a modified Floyd-Warshall algorithm considering a left turn prohibition according to the present invention. FIG.

4 is an exemplary diagram of a network configuration for applying a modified Floyd-Warshall algorithm considering a left turn prohibition, a U-turn, and a P-turn according to the present invention.

FIG. 5 is a flowchart illustrating a method for calculating an optimum path in consideration of a prohibition of left turn, a U-turn, and a P-turn according to the present invention. FIG.

The present invention can be read by a computer that records a method for calculating an optimal route applying constraints such as left turn prohibition, U-turn, and P-turn in general urban road conditions and a program for realizing the method. A recording medium that can be used.

According to the traffic situation in Korea, the road traffic congestion cost is more than 10 trillion won a year due to chronic traffic congestion, and the cost is increasing more than 2 trillion won every year, and the national competitiveness of the industry is weakened due to excessive logistics costs. It is becoming a factor.

In particular, the Global Positioning System (GPS) and Geographic Information System (GIS) technology, wireless communication, to improve the operational efficiency of the existing roads and the driver's convenience due to the recent increase in traffic congestion in populated cities. Advanced Vehicle Information System (CVO) and Advanced Traveler Information System (ATIS), which combines technologies, have been developed as part of the Intelligent Transport System (ITS), and are in practical use.

In particular, the most important function of the advanced traffic information system (ATIS) is the optimal route guidance function, and various algorithms for calculating the optimal route have been developed since the late 1950s.

One of these algorithms is the Floyd-Warshall algorithm, which has proven its suitability and has the advantage of being simple to implement and easy to implement.

으로 정의한다.The Floyd-Warshall algorithm is an algorithm that finds the optimal path between all two nodes of a network. That is, it is possible to calculate the optimal path from m nodes (m is a natural number) to the remaining m-1 nodes. First, a symbol representing the shortest distance estimate from intersection i to intersection j

It is defined as

로 표현되며 동일한 노드로의 최적경로는

으로 표현된다.In this equation, only intermediate points constituting the shortest path from the intersection point i to the intersection point j are allowed to the intersection points 1,2,3, ..., m, except for the intersection point i and the point j. If this path does not exist, that is, if there is no line (or arc) connecting the node

Best path to the same node

It is expressed as

The Floyd-Warshall algorithm is briefly described using the above symbols.

이 된다.That is, in a network with nodes, if the intermediate intersection constituting the optimal path from any node i to node j consists of only 1,2,3, ..., m-1, The new optimal path may or may not pass through the intersection m. If the calculated best path does not pass the intersection m

Becomes

이 된다. 이를 수식으로 표현하면 아래의 [수학식 1]과 같다.If the calculated optimal path passes the intersection m,

Becomes If this is expressed as an expression, Equation 1 below.

은 네트워크 내의 교점 간의 거리 d_ij로 주어진다. 상기 [수학식 1]로 표현되는 삼각연산을 네트워크 내의 모든 교점 즉, m에 대해 수행한다. 이러한 연산의 결과로 최적거리행렬

과 최적경로행렬

이 구해진다. 이상과 같은 플로이드-바쉘(Ployd-Warshall) 알고리듬의 연산을 프로그래밍 언어 형태로 표현하면 아래의 [수학식 2]와 같다.The operation represented by [Equation 1] is called trigonometric operation (Triangle operation),

Is given by the distance d _ij between the points in the network. The trigonometric operation represented by Equation 1 is performed for all intersection points, that is, m in the network. Optimal distance matrix as a result of these operations

And optimal path matrix

Is obtained. When the operation of the Floyd-Warshall algorithm is expressed in a programming language form, Equation 2 below.

1 is an exemplary diagram of a network configuration for applying a conventional Floyd-Warshall algorithm.

행렬을 구한다. 이미 전술한 바와 같이 이 행렬은 각 교점들 사이의 거리로 구성되는 행렬이다.First, in order to find the shortest path for the network shown in the drawing, Equation 3

Find the matrix. As mentioned above, this matrix is a matrix consisting of the distances between the respective intersections.

은 최단경로행렬을 나타내며, 교점과 교점을 잇는 중간교점에 관한 정보를 갖고 있다. 상기 [수학식 3]의 행렬을 시작으로 하여 [수학식 2]에 표현된 반복적인 방법으로 연산을 수행하면 아래의 [수학식 4] 내지 [수학식 7]과 같은 결과를 얻을 수 있다.At this time, [Equation 3]

Represents the shortest path matrix and contains information about the intersection with the intersection. Starting with the matrix of Equation 3, the operation is performed by the iterative method expressed in Equation 2, and the following Equations 4 to 7 can be obtained.

First, looking at the result of m = 1, it can be expressed as shown in Equation 4 below.

The calculation result of m = 2 to m = 5 is shown in Equations 5 to 7 below.

However, since the conventional Floyd-Warshall algorithm described above simply deals with the shortest path on a graph connecting a point and a line, it is necessary to use the road according to the complicated situation of modern roads, in particular, the prohibition of turning left. There was a problem that the use of bypass could not be indicated.

The present invention has been proposed to solve the above problems, by modifying the conventional Floyd-Warshall algorithm to prevent left turn, modern U-turn at the intersection, avoid U-turn at the intersection, avoid An object of the present invention is to provide a method for calculating an optimal path for accommodating a constraint such as a P-turn and a computer-readable recording medium having recorded thereon a program for realizing the optimal path.

According to an aspect of the present invention, there is provided a method for calculating an optimal path applying a constraint applied to an optimal path calculating system, the method comprising: a first step of obtaining initial optimal distance matrices having an infinite distance value of a left turn prohibition section; Performing a trigonometric operation on each of the obtained initial optimum distance matrices to obtain an optimum distance matrix and an optimal path matrix; And a third step of selecting an optimal distance matrix having a minimum value among the obtained optimal distance matrices and obtaining an optimal path from the corresponding optimal path matrix.

On the other hand, the present invention provides a first function for calculating the initial optimal distance matrix having an infinite distance value of the left turn prohibition section in the optimal path estimation system having a large capacity processor for calculating the optimal path to which the constraint is applied; A second function of performing trigonometric operations on each of the obtained initial optimal distance matrices to obtain respective optimum distance matrices and optimal path matrices; And a computer readable recording medium having recorded thereon a program for realizing a third function of selecting an optimum distance matrix having a minimum value among the obtained optimum distance matrices and obtaining an optimum path from the corresponding optimum path matrix.

The present invention proposes a new algorithm that has already been proved in its suitability and is modified based on the Floyd-Warshall algorithm which is easy to implement and easy to implement. That is, the modified Ployd-Warshall algorithm can obtain an optimal route for a road in a city including a left turn prohibited zone.

Hereinafter, a preferred embodiment according to the present invention will be described in detail with reference to FIGS. 2 to 5.

2 is a configuration diagram of an embodiment of an optimal path calculation system to which the present invention is applied.

As shown in FIG. 2, the optimal path calculation system to which the present invention is applied includes a main memory device 201 for storing a predetermined program and data, and an auxiliary memory device 202 for assisting the functions of the main memory device 201. , An input / output device 203 in charge of input / output, and a central processing unit 204 for managing and controlling the operations of all the devices.

3 is an exemplary view illustrating a network configuration for applying a modified Floyd-Warshall algorithm considering a left turn prohibition according to the present invention, and FIG. 5 is a left turn prohibition and U-turn according to the present invention. ) Is a flowchart illustrating an optimal path estimation method considering P-turns.

과 최적경로행렬

을 구해보면 아래의 [수학식 8] 및 [수학식 9]와 같다.That is, as shown in FIG. 3, it is assumed that the entire network is composed of 11 intersections and the left turn prohibition is applied to a path connected to 2-3-4 intersections. First, the optimal distance matrix without considering the left turning prohibition factor

And optimal path matrix

To obtain the same as [Equation 8] and [Equation 9] below.

As shown in the calculation results of Equations 8 and 9, the optimum path from the intersection point 1 to the intersection point 7 is 1-2-3-4-7, and the distance at this time is 4.

Now, when the left turn prohibition is applied to a path passing through 2-3-4 to such a network, the optimal distance matrix and the optimal path matrix obtained from Equations 8 and 9 above are used. Cannot get its value. Therefore, the prohibition of left turn for the section 2-3-4 is expressed by two initial optimal path matrices as shown in Equations 10 and 11 below.

That is, two initial values having infinite distances of the paths 2-3 and 3-4 to reflect the prohibition of the left turn applied to the paths 2-3-4 as shown in Equations 10 and 11 above. Create an optimal distance matrix (501). In this case, the number of initial optimal distance matrices is 2 ⁿ when the number of left turn prohibition sections is n. That is, since the left turn prohibition section is one in the network of FIG. 3, the number of initial optimal distance matrices is two.

과

, 및 최적경로행렬

과

를 구한다(503). 즉, 도 3에서는 유턴 및 피턴은 고려하지 않았으며(502), 그 결과는 아래의 [수학식 12] 내지 [수학식 15]와 같다.Next, by performing trigonometric operations on the two matrices of Equations 10 and 11, respectively, an optimum distance matrix is obtained.

and

, And best fit matrix

and

Obtain (503). That is, in FIG. 3, the U-turn and the piton are not considered (502), and the results are shown in Equations 12 to 15 below.

행렬과 구간 3-4를 무한대로 둔

행렬이 나타내는 구간 1-7의 최적거리행렬을 비교해 보면 두 행렬들 중

의 값이

에 비해 적은 값을 갖고 있다.That is, as can be seen from the result as described above, the interval 2-3 is left at infinity.

Leaving the matrix and intervals 3-4 infinity

If you compare the optimal distance matrix of the interval 1-7 represented by the matrix,

Has a value of

It has a smaller value than.

로부터 1-2-3-8-7로 구할 수 있다.Therefore, the optimal distance value constituting the path 1-7 is 4, and the optimal path at this time is the optimal path matrix

It can be obtained from 1-2-3-8-7.

That is, the minimum value is selected from the results of the calculation of the two optimum distance matrices configured to express the left turn prohibition, and the optimal path for this is obtained from the optimal path matrix obtained together with the corresponding optimal distance matrix (504). If the left turn prohibition period is n, the optimum distance matrix is 2 ^n. Therefore, the optimal distance matrix having the minimum value is selected and the optimal path is obtained from the corresponding optimum path matrix.

4 is an exemplary diagram of a network configuration for applying a modified Floyd-Warshall algorithm in consideration of a prohibition of left turn, U-turn, and P-turn according to the present invention. 5 is a flowchart illustrating an optimal path calculation method considering a left turn prohibition, a U-turn, and a P-turn according to the present invention.

That is, FIG. 4 illustrates a method of calculating an optimal path using a left turn prohibition section when a P-turn and a U-turn are allowed at a specific intersection.

First, before applying the virtual intersection point, simply apply the left turn prohibition to obtain the optimum distance matrix and the optimal path matrix as shown in [Equation 16] and [Equation 17] below.

As can be seen from the results shown in [Equation 16] and [Equation 17], the left turn prohibition is applied to the section 1-2-3 and U-turn is allowed at the intersection point 4 and the intersection point 6, but this is reflected. If the calculation is performed without the calculation, the optimal path from the intersection points 1 to 3 does not exist, and the calculation result is derived.

In practice, however, only a left turn was forbidden, but a P-turn through 1-2-4-5-6-2-3 and 1-2-4-2-3 and 1-2-6-2- U-turns through 3 are possible. The present invention adds a virtual intersection 2 'to represent this case (505).

In other words, the existing Floyd-Warshall algorithm, like other optimal path algorithms, does not allow passing through the intersection once passed. Therefore, the virtual intersection 2 'is added and the relationship with the surrounding intersections 4, 6, 3, and 1 is expressed as a weight as follows.

First of all, the relationship between the virtual intersection 2 'and the intersection 1 and 3 is forbidden to turn left through the intersection 2 from the intersection 1, so that the intersection 1 is infinite and the intersection 3 and the distance between the intersection 2 and the intersection 3 Has the same 1

In the intersection 4 and 6, U-turns of 2-4-2 and 2-6-2 are allowed, and thus have the same value as the distance value of the intersection 2 and 4 and the intersection 2 and 6 .

That is, the two optimal distance matrices shown in Equation 18 are the distance between the virtual intersection point 2 'and the remaining intersection points added to the last row of the initial optimal distance matrix created by considering only the left turning prohibition section (506). . The triangular calculation is performed on the two matrices of Equation 18 to obtain the optimum distance matrix and the optimal path matrix, as shown in Equations 19 and 20 below (503).

이며, 이때의 최적경로는

로부터 1-2-6-2-3임을 알 수 있다. From the results of Equation 19 and Equation 20, the optimum distance from the intersection point 1 to the intersection point 3 is

Where the best path is

It can be seen from 1-2-6-2-3.

That is, the minimum value is selected among the results of the calculation of the two optimal distance matrices, and the optimal path for this is obtained from the optimal path matrices obtained together with the corresponding optimal distance matrices (504). If the left turn prohibition period is n, the optimum distance matrix is 2 ^n. Therefore, the optimal distance matrix having the minimum value is selected and the optimal path is obtained from the corresponding optimum path matrix.

As demonstrated by the above results, the modified Floyd-Warshall algorithm is designed to prevent left turn, U-turn, and P-turn on urban roads that the existing algorithm cannot handle. Provide an effective method for estimating the optimal path.

Hereinafter, the method for calculating the optimal path described above will be described with reference to FIG. 5.

That is, as described above, if two intersections are connected to each other, the corresponding distance value is used. If the two intersections are not connected to each other, such as when the left turn prohibition section is specified, the initial optimal distance matrix is set by leaving the distance value at infinity. Obtain (501).

After that, if the U-turn and the piston are not considered, the process proceeds directly to step 503, and if the U-turn and the piston are considered, the virtual intersection is added as described above for the left turn prohibition section existing on the network. In operation 505, a modified initial optimal distance matrix having a distance value between the virtual intersection and the adjacent intersection is obtained. The initial optimal distance matrix is 2 ⁿ when the number of left turn prohibition sections is n.

The optimal distance matrix is obtained by performing trigonometric operations on the 2 ⁿ initial optimal distance matrices and the shortest distance matrices. In this case, the optimal path matrix is also obtained along with the optimal distance matrix (503).

Among the calculation results, the matrix having the smallest value for the corresponding interval is selected as the optimal distance matrix, and the optimal path is obtained from the corresponding optimal path matrix (504).
As described above, the method of the present invention may be implemented as a program and stored in a recording medium (CD-ROM, ROM, RAM, floppy disk, hard disk, magneto-optical disk, etc.) in a computer-readable form. Since this process can be easily implemented by those skilled in the art will not be described in more detail.

The present invention described above is capable of various substitutions, modifications, and changes without departing from the spirit of the present invention for those skilled in the art to which the present invention pertains, and the above-described embodiments and accompanying It is not limited to the drawing.

The present invention as described above is a chronic path by calculating the optimum path by accepting the constraints such as left turn prohibition, U-turn and P-turn at the intersection, which is a modern complex road situation. In addition to reducing the burden of road traffic congestion due to traffic congestion, there is an excellent effect to improve the operational efficiency of the road and to improve driver convenience.

Claims (6)

In the optimal path estimation method applying the constraints applied to the optimal path estimation system, A first step of obtaining initial optimal distance matrices having an infinite distance value of a left turn prohibition interval; Performing a trigonometric operation on each of the obtained initial optimum distance matrices to obtain an optimum distance matrix and an optimal path matrix; And A third step of selecting an optimal distance matrix having a minimum value among the obtained optimal distance matrices and obtaining an optimal path from the corresponding optimal path matrix; Optimal path calculation method comprising a. The method of claim 1, Considering the u-turn and the p-turn, a fourth step of modifying the obtained initial optimal distance matrix by adding a virtual intersection point for the left turn prohibition interval; Optimal path calculation method further comprising. The method of claim 2, The fourth step, A fifth step of adding a virtual intersection point for the left turn prohibition section when considering a u-turn and a p-turn; And A sixth step of modifying the obtained initial optimal distance matrix in consideration of the distance value between the added virtual intersection point and adjacent intersection points; Optimal path calculation method comprising a. The method according to any one of claims 1 to 3, The number of initial optimal distance matrices obtained in the first step is The method for calculating the optimum route, characterized in that it has 2 ⁿ when the left turn prohibition period is n (n is a natural number). In order to calculate the optimal path with constraints, the optimal path estimation system with a large processor, A first function of obtaining initial optimal distance matrices having an infinite distance value of a left turn prohibition interval; A second function of performing trigonometric operations on each of the obtained initial optimal distance matrices to obtain respective optimum distance matrices and optimal path matrices; And A third function of selecting an optimal distance matrix having a minimum value among the obtained optimal distance matrices and obtaining an optimal path from the corresponding optimal path matrix A computer-readable recording medium having recorded thereon a program for realizing this. The method of claim 5, A fourth function of modifying the obtained initial optimum distance matrices by adding a virtual intersection point for the left turn prohibition section when considering a u-turn and a p-turn; A computer-readable recording medium having recorded thereon a program for further realization.

Images