CN104008666B - A kind of fingerpost distribution method towards point of interest - Google Patents

Abstract

The invention relates to a point-of-interest-oriented method for laying out guide signs. The method includes extracting the indicating road network of points of interest on the road network model; defining a path optimization index for measuring the convenience of the guiding path, and the path optimizing index includes path length, traffic flow and intersection turning; Network traversal, calculate and dynamically update the path optimization index, obtain the optimal guidance path in the indicated road network; determine the content of the guidance information and the position of the guidance signboard according to the optimal guidance path. The present invention considers the influence of the path length and traffic flow on the travel time and the increase of the travel time through the intersection, and optimizes the path index in combination with the breadth optimization search method, so as to obtain a fast and convenient route guidance with high economic efficiency The sign layout scheme can satisfy the short-distance and detailed instructions of the points of interest, and can also meet the key guidance on the backbone road network at the far end.

Description

A point-of-interest-oriented waypoint layout method

technical field

The invention relates to the field of road traffic planning and design, and more specifically, to a point-of-interest-oriented road sign layout method.

Background technique

In recent years, my country's social economy has developed rapidly, and urban infrastructure has entered a period of vigorous development. Especially as a pioneer of economic development, urban road traffic construction has entered a peak period, and a large number of roads, new development areas, and commercial centers have been put into use. As the most important road traffic facilities for static path guidance and traffic diversion, urban road guide signs also urgently need to be updated and upgraded. How to enable road users to reach their destinations quickly and conveniently on the new traffic road network and realize the diversion of traffic flow is an important topic that road managers need to study. The main factors affecting travel time are: path length, path traffic flow, intersection turning, etc. Therefore, the comprehensive path length, path traffic flow and intersection turning conditions have important practical significance for the layout of guiding signs.

The current research status at home and abroad on the layout of road signs is as follows:

First, in terms of research on the data model of road signs, Huang Min, Sha Zhiren and others proposed a road network data model for road signs, and proposed an intersection characteristic function in the model, which can express the turning, Road network topology data for road signs such as connectivity status. Huang Min proposed a three-layer data model of road signs: road sign points, road sign boards, and road sign items. The three-layer guide sign data model provides a solution for the digitization of the guide information of the guide signs and the geography and traffic information of the guide signs.

Second, the waypoint layout method can be divided into research objects: intersection-oriented waypoint layout method and point-of-interest-oriented waypoint layout method research. The intersection-oriented guide sign layout method refers to taking the intersection as the research object, dividing the guidance information of the guide signs at the intersection into connectivity signs and direction signs, and setting a series of directional sign screening rules, such as The road is layered according to function, from far to near, and from high level to low level to filter directional guidance information. This method is suitable for the setting of guide signs at intersections, but it cannot make the guide signs of adjacent intersections be connected in series to form regional guidance, and the continuous accessibility of the guide objects is difficult to guarantee. The point-of-interest-oriented road sign layout method takes the point of interest as the guiding object, and starts from a specific entrance and exit to plan a convenient and fast path for laying out the road signs. This method conforms to the path of the road signs to a certain extent Inductive function, and ensure the continuous accessibility of the guidance object, but this method is only suitable for point-to-point path guidance, it is difficult to meet the regional guidance.

The above-mentioned layout method is mainly for the guidance sign layout method of a single guidance path for a single intersection or a single point of interest. The screening of guidance information can consider the characteristics of road attributes and points of interest, but the guidance path only considers the length of the guidance path, and does not consider The impact of traffic flow and intersection turning on travel time, and it cannot meet the demand for point-of-interest-oriented signposting in designated areas.

Contents of the invention

In order to overcome at least one defect (deficiency) of the above-mentioned prior art, the present invention provides a point-of-interest-oriented road sign layout method that comprehensively considers the three factors of path length, path traffic flow, and intersection turning.

In order to solve the problems of the technologies described above, the technical solution of the present invention is as follows:

A point-of-interest-oriented waypoint layout method, comprising

Extract the indicative road network of points of interest on the road network model;

Defining route optimization metrics to measure the convenience of guiding routes, said route optimization metrics including path length, traffic flow, and intersection turning;

Traverse the indicated road network in breadth-first order, calculate and dynamically update the path optimization index, and obtain the optimal guiding path in the indicated road network;

Determine the content of setting guidance information and the position of setting guidance signs according to the optimal guidance route.

As a preferred solution, the road network indicating points of interest extracted on the road network model specifically includes:

On the basis of the road network model, the indication range R of the point of interest is divided according to the level of the point of interest and the amount of traffic attraction;

Extraction of indicated road networks for points of interest using the double-circle covering method.

As a further preferred solution, the indicated road network for extracting points of interest using the double-circle coverage method specifically includes:

Extract the detailed road network of the inner circle and the backbone road network of the outer circle respectively;

Preset a circle with the point of interest as the center and the radius r _c to cover the detailed road network to obtain the core indication area G _c of the point of interest;

Taking the point of interest as the center, preset a ring between the core indication area _Gc and the indication range R to cover the backbone road network to obtain the peripheral indication area _Gp of the interest point;

The core indication area G _c and the peripheral indication area G _p are seamlessly and closely connected to obtain the point of interest indication road network G _g .

As a further preferred solution, in the indicated road network, the path from node k to node d is represented by P _kd ={v _k ,...v _h ,(v _h ,v _i ),v _i ,(v _i ,v _j ),v _j ,…v _d }, where v _k , v _h , v _i , v _d indicate nodes in the road network, and (v _i , v _j ) indicates the road section from node i to node j , the weight W(v _k ,v _d ) of the path P _kd is equal to the weight sum of all road sections on the path plus the weighted sum of the path turning; when traversing the indicated road network in the order of breadth first, the optimization goal is to minimize the path weight value, Dynamically update the path optimization index to obtain the optimal path from each intersection node in the double circle to the point of interest.

As a further preferred solution, the path steering weighted sum is calculated by the following formula:

T(P _kd )＝f _l ×T _l (P _kd )+f _r ×T _r (P _kd )+f _s ×T _s (P _kd )+f _u ×T _u (P _kd ) (1)

In formula (1), T _l (P _kd ), T _s (P _kd ), T _r (P _kd ), and Tu (P _kd ) represent the number of left turns, straight lines, right turns, and _U -turns on the path P _kd , respectively. f _l , f _s , f _r , and f _u represent the weighting coefficients for turning left, going straight, turning right, and turning around, respectively;

The link weight sum is calculated by the following formula:

$\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The weight w(v _i , v _j ) of the link (v _i , v _j ) in formula (2) is the normalized weight, which contains two parts, where is the length of the normalized road section, l _ij is the road section length of the road section (v _i , v _j ), l _min is the minimum road section length in the indicated range R, and l _max is the maximum road section length in the indicated range R; is the normalized link flow, q _ij is the link flow of link (v _i , v _j ), q _min is the minimum link flow in the indicated range R, q _max is the maximum link flow in the indicated range R, α ₁ and α ₂ are The weighting coefficient of link flow and link length, and α ₁ +α ₂ =1;

The weight calculation formula of path P _kd is: $W(v_k,v_d)={\mathrm{\&lambda;}}_1\&times;T\left(P_{\mathrm{kd}}\right)+{\mathrm{\&lambda;}}_2\&times;\underset{P_{\mathrm{kd}}}{\mathrm{\&Sigma;}}w(v_i,v_j)$ $\left(3\right)$

In Equation ( ₃ ), λ1 and _λ2 are the weighting coefficients of the route turning and the flow sum of road section length respectively, which are calculated according to the driver's driving cost at intersections and road sections.

As a preferred solution, the guidance information includes the name of the indicated object, the indicated direction and the distance.

As a preferred solution, the location of the guide sign board includes indicating nodes and road sections in the road network, wherein the road section is the road section that enters the most convenient path by turning after entering the intersection.

Compared with the prior art, the beneficial effects of the technical solution of the present invention are:

(1) The present invention considers the impact of path length and traffic flow on travel time, and considers the increase of travel time brought by the intersection, and optimizes the path index in combination with the breadth optimization search method, because the breadth optimization search method is in the While breadth-first traverses the road network, it calculates and adjusts the guidance path. On the premise of ensuring that the guidance path is continuously accessible, it improves the search efficiency, approaches the regional boundary faster, and can obtain a high-efficiency, fast and convenient guidance sign Layout plan, the layout plan can meet the short-distance and detailed instructions of points of interest, and can also meet the key guidance on the backbone road network at the far end.

(2) The present invention combines the breadth optimization search with the double-circle coverage method. When the distance is far from the point of interest, the outer circle indicates that the road network only includes roads with higher grades. When the distance from the point of interest is closer, the inner circle indicates The road network also includes lower-level roads. The division of the double-circle indication road network makes the indication area more in line with the driver's wayfinding habits, and the driver's experience is better, more scientific, and can meet engineering needs.

Description of drawings

FIG. 1 is a flow chart of a specific embodiment of a point-of-interest-oriented wayfinding sign layout method according to the present invention.

Fig. 2 is a schematic diagram of an indicating road network obtained in a specific embodiment of the present invention.

Fig. 3 is a specific flow chart of obtaining the final path from all nodes in the indicated road network to the point of interest by using the breadth optimization search algorithm.

Fig. 4 is a schematic diagram of the layout of some guide signs in a specific example of the present invention.

detailed description

The accompanying drawings are for illustrative purposes only and cannot be construed as limiting the patent;

In order to better illustrate this embodiment, some parts in the drawings will be omitted, enlarged or reduced, and do not represent the size of the actual product;

For those skilled in the art, it is understandable that some well-known structures and descriptions thereof may be omitted in the drawings.

In the description of the present invention, unless otherwise specified, "plurality" means two or more.

The technical solutions of the present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Example 1

As shown in FIG. 1 , it is a flowchart of a specific embodiment of a point-of-interest-oriented wayfinding sign layout method according to the present invention. Referring to Fig. 1, the concrete steps of a kind of point-of-interest-oriented wayfinding sign layout method in this specific embodiment include:

S101. Extracting the indicating road network of the point of interest on the road network model;

S102. Define a path optimization index for measuring the convenience of the guiding path, the path optimization index includes path length, traffic flow and intersection turning;

S103. Traverse the indicated road network in the order of breadth first, calculate and dynamically update the path optimization index during the traversal process, and obtain the optimal guidance path in the indicated road network;

S104. Determine the content of setting guidance information and the location of setting guidance signs according to the optimal guidance route.

In this specific embodiment, by extracting the indicated road network, with the goal of maximizing the driving convenience of the guiding route, comprehensively considering the length of the route, traffic flow and the number of turns at the intersection, an optimization index for measuring the convenience of the route is defined; The order of the indicated road network is traversed, and the path optimization index is calculated and dynamically updated. While the breadth-first traverses the road network, the guiding path is calculated and adjusted. On the premise of ensuring that the induced path is continuously accessible, each path is the most Optimizing the guiding path; according to the calculation results, determine the location and content of the guiding information on the indicating road network, so as to obtain the optimal guiding sign layout plan for the point of interest, and achieve the scientific layout goal.

In step S101, the extraction of the indicated road network can be performed in the following manner:

Step S1011. On the basis of the road network model, divide the indication range R of the point of interest according to the level of the point of interest and the amount of traffic attraction; wherein, the road network model can be represented by a directed graph G=(V, A), V={v _i |i=1, 2,..., n} is the node set of G, A={a _ij =(v _i ,v _j )|i, j=1, 2,...,n; v _i , v _j ∈V} is the arc set of G, and the arc in the directed graph represents a road segment in the actual path; the division of the indication range R can be obtained according to the level of the point of interest and the amount of traffic attraction, specifically, the point of interest D can be used as the center of the circle 1. The radius is r _p to delineate a circle as the indication range R, the radius as shown in Figure 2 is the indication range R marked as the point of interest D inside the radius r _p ;

Step S1012. Using the double-circle covering method to extract the indicating road network of the point of interest. Specifically, the detailed road network and the backbone road network are extracted respectively, and the detailed road network is covered by a circle with the point of interest D as the center and a radius of r _c to obtain the core indicator area G _c of the point of interest D; the radius between r _c and r The ring of _p covers the backbone road network to obtain the peripheral indication area G _p of the point of interest D; the core indication area G _c and the peripheral indication area G _p are closely connected to obtain the indication road network G _g of the point of interest D. Using the double-circle coverage method to lay out the indicating road network around the point of interest can not only cover the detailed road network, but also cover the backbone road network. guiding target.

In the specific implementation process, the three factors of path length, traffic flow and intersection turning are considered comprehensively, so the path length, traffic flow and intersection turning are taken as the optimization indicators for guiding the convenience of the path. In the indicated road network, the path from node k to node d is defined by P _kd ={v _k ,…v _h ,(v _h ,v _i ),v _i ,(v _i ,v _j ),v _j ,… v _d } means, among them, v _k , v _h , v _i , v _d indicate nodes in the road network, (v _i , v _j ) means the road section from node i to node j, and the road section (v _i , The length of v _j ) is l _ij , and the flow rate is q _ij ; the turn of the road (v _h , v _i ) to the intersection v _i to reach the road (v _i , v _j ) is t(v _i ), and the path P _kd The weight W(v _k , v _d ) is equal to the weight sum of all road sections on the path plus the weighted sum of path turning; when traversing the indicated road network in breadth-first order, the optimization goal is to minimize the path weight, and the path optimization index is dynamically updated , to obtain the optimal path from each intersection node in the double circle to the point of interest, where the dynamic update path optimization index refers to: the parent node of the node is updated each time, and the updated path from the node to the point of interest The weight value becomes smaller.

Among them, the path steering weighted sum is calculated by the following formula:

T(P _kd )＝f _l ×T _l (P _kd )+f _r ×T _r (P _kd )+f _s ×T _s (P _kd )+f _u ×T _u (P _kd ) (1)

In formula (1), T _l (P _kd ), T _s (P _kd ), T _r (P _kd ), and Tu (P _kd ) represent the number of left turns, straight lines, right turns, and _U -turns on the path P _kd , respectively. f _l , f _s , f _r , and f _u denote the weighting coefficients of turning left, going straight, turning right, and turning around, respectively. Each weighting coefficient can be set according to prior knowledge. For example, the weights of the four steering can be defined from large to small The order is f _u , f _l , f _r , f _s , that is, the weight of turning around is the largest, and the weight of going straight is the smallest.

The link weight sum is calculated by the following formula:

$\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The weight w(v _i , v _j ) of the link (v _i , v _j ) in formula (2) is the normalized weight, which contains two parts, where is the length of the normalized road section, l _ij is the road section length of the road section (v _i , v _j ), l _min is the minimum road section length in the indicated range R, and l _max is the maximum road section length in the indicated range R; is the normalized link flow, q _ij is the link flow of link (v _i , v _j ), q _min is the minimum link flow in the indicated range R, q _max is the maximum link flow in the indicated range R, α ₁ and α ₂ are The weighting coefficient of link flow and link length, and α ₁ +α ₂ =1;

The weight calculation formula of path P _kd is: $W(v_k,v_d)={\mathrm{\&lambda;}}_1\&times;T\left(P_{\mathrm{kd}}\right)+{\mathrm{\&lambda;}}_2\&times;\underset{P_{\mathrm{kd}}}{\mathrm{\&Sigma;}}w(v_i,v_j)---\left(3\right)$

In Equation ( ₃ ), λ1 and _λ2 are the weighting coefficients of the route turning and the flow sum of road section length respectively, which are calculated according to the driver's driving cost at intersections and road sections.

In the specific implementation process, the specific process of using the breadth optimization search algorithm to obtain the final path from all nodes in the indicated road network to the point of interest can be shown in FIG. 3 .

First define the five-tuple of attributes of node v _k , {f _p (v _k ),t(f _p (v _k )),W(f _p (v _k ),v _d ),w(v _k ,f _p ( v _k )),W(v _k ,v _d )};

Where f _p (v _k ) represents the parent node of v _k ;

t(f _p (v _k )) represents the arc segment between node v _k and its parent node f _p (v _k ) at node f _p (v _k ) (v _k ,f _p (v _k ) ) relative to the arc segment between f _p (v _k ) and the ancestor node (the parent node of the parent node) f _p (f _p (v _k )) (f _p (v _k ), f _p (f _p (v _k ))) turning;

W(f _p (v _k ), v _d ) represents the weight of the path from the parent node f _p (v _k ) of v _k to the indicated node v _d ;

w(v _k ,f _p (v _k )) is the weight of the link from v _k to the parent node f _p (v _k ), W(v _k ,v _d ) represents the weight of the path from v _k to the starting node v _d The weight value obviously has W(v _k ,v _d )=W(f _p (v _k ),v _d )+λ ₁ ×f _i +λ ₂ ×w(v _k ,f _p (v _k )), where f _i can take the value according to t(f _p (v _k )), f _l , f _s , f _r , f _u respectively.

Referring to Figure 3, the method for dynamically calculating the optimal guidance path in the indicated road network can be realized by the following process:

1) Initialization: create three node lists FList, PList and TList, FList is the list of all nodes within the indicated range R, PList is the optimal path list, TList is the traversal list, the initial value of PList is the starting node v _d , the adjacent nodes whose TList initial value is v _d clockwise from the true north direction are respectively where n represents the number of v _d adjacent nodes;

2) Take the node v _k with the minimum weight W(v _k , v _d ) in TList, and add v _k to PList;

3) Get the adjacent nodes of v _k from FList

4) Determine whether there is i<n, if so, enter 5); if not, enter 9);

5) Judgment Whether it is in the PList, if so, then i=i+1, enter 4); if not, enter 6);

6) Whether it is in TList, if not, go to 7); if yes, go to 8);

7) Calculate of and and put Join in TList, i=i+1, enter 4);

8) Calculate Weights to reach v _d through v _k Is there less than the original weight which is $W(v_k^i,v_d)<{W(v_k^i,v_d)}^{\&prime;}.$ yes, modify of and i=i+1, go to 4); No, i=i+1, go to 4).

9) Move v _k out of TList;

10) Whether the TList is empty, if yes, end; if not, return 2);

Finish.

According to the above process, the optimal path list PList can be obtained.

In the specific implementation process, through step S103, it can be obtained that the optimal path from any node v _k on the road network to the point of interest v _d is P _kd , then it can be judged that v _k is connected to the parent node f _p (v _k ) Whether the road section (v _k ,f _p (v _k )) needs to set up a guide sign at the intersection f _p (v _k ), and the content of the guide information: get the attribute t(f _p (v _k )) of v _k ,like To turn left, turn right or turn around, you need to set up road signs at the node f _p (v _k ), and turn to , indicating that the content is the name of the point of interest. Generally, the guidance information includes the name of the indicated object, the indicated direction and the distance, and the location of the guide sign board includes the nodes and road sections indicated in the road network, where the road section is the road section that enters the most convenient path by turning after entering the intersection.

The above process will be described below in combination with specific examples.

As shown in Figure 4, the indicated road network is shown. The initial value of PList is v _d , and the initial value of TList is {v ₆ , v ₈ }; enter the above process 2) get v ₆ and add it to PList; process 3) get v The adjacent nodes of ₆ are v _d , v ₉ , v ₅ , and v ₁₀ ; after judging 4) and judging 5), it is obtained that v _d is in the PList, and returning to judging 4); entering into judging 5), it is found that v ₉ is not in the PList, Go to Judgment 6) If v ₉ is not in _TList , calculate f _p (v ₉ ), t(f _p (v ₉ )), W(f _p (v ₉ ),v _d ), w(v ₉ , f _p (v ₉ )) and W(v ₉ ,v _d ) get the parent node of v ₉ as v ₆ , that is, f _p (v ₉ )=v ₆ , enter the intersection through the road section (v ₉ ,v ₆ ) The turn t(f _p (v ₉ )) from v ₆ to (v ₆ , v _d ) is a right turn, and the weight of the road segment (v ₉ , v ₆ ) is $w(v_9,v_6)={\mathrm{\&alpha;}}_1\&times;\frac{l_{96}-l_{\min }}{l_{\max }-l_{\min }}+{\mathrm{\&alpha;}}_2\&times;\frac{q_{96}-q_{\min }}{q_{\max }-q_{\min }},$ The optimization weight of path P _9d is W(v ₉ ,v _d )=W(v ₆ ,v _d )+λ ₁ ×f _l +λ ₂ ×w(v ₉ ,v ₆ ); add v ₉ into TList , so that TList={v ₆ , v ₈ , v ₉ }; return to 4), start to judge v ₅ , and repeat this until TList is empty, and the optimal instruction path from all nodes to v _d can be obtained.

As shown in Figure 4, the node v ₃ on the indicated road network, the optimal path from v ₃ to the point of interest D is P _3d ={v ₃ ,(v ₃ ,v ₄ ),v ₄ ,(v ₄ ,v ₅ ),v ₅ ,(v ₅ ,v ₆ ),v ₆ ,(v ₆ ,v _d )}, v ₃ ’s parent node f _p (v ₃ )=v ₄ , t(v ₄ ) is a right turn, Then on the road section (v ₃ , v ₄ ) of the v ₄ intersection, a guiding signboard pointing to the right turn and forecasting the point of interest D should be set up.

In the core indication area, the installation of some guide signs is shown in Figure 4. In Figure 4, using this method, the optimal path from v ₁ to pointing node v _d is path 1{v ₁ ,(v ₁ ,v ₃ ),v ₃ ,(v ₃ ,v ₄ ),v ₄ ,(v ₄ ,v ₅ ),v ₅ ,(v ₅ ,v ₆ ),v ₆ ,(v ₆ ,v _d )}. Obviously, path 1 and path 2 {v ₁ ,(v ₁ ,v ₃ ),v ₃ ,(v ₃ ,v ₇ ),v ₇ ,(v ₇ ,v ₁₂ ),v ₁₂ ,(v ₁₂ ,v ₅ ),v ₅ ,(v ₅ ,v ₆ ),v ₆ ,(v ₆ ,v _d )} are the best candidate paths, path 1 and path 2 are similar in length, but path 1 only passes through 4 intersections, where One turns right, three go straight; Path 2 needs to go through 5 intersections, one turns left, two turns right, and two goes straight; obviously path 1 passes through fewer intersections and goes straight more than light weight, so path 1 best. The path length between the node on path 1 and the pointing object v _d is 2 kilometers, so a guiding signboard as shown in Fig. 4 can be set at v ₄ .

The present invention divides the indication range of the interest point according to the level of the interest point, the amount of traffic attraction and other indicators, combines the road network topology, and uses the double-circle coverage method to extract the indication road network of the interest point, so as to realize the short-distance and detailed guidance around the interest point , focusing on the peripheral backbone road network; aiming at maximizing the driving convenience of the guiding path, comprehensively considering the path length, traffic flow and turning times, defining the optimization index to measure the convenience of the path; Perform traversal, calculate and dynamically update the path optimization index, so that each path is the optimal guiding path; according to the calculation results, determine the location and content of the guiding information on the indicating road network, so as to obtain the optimal guiding sign layout plan for points of interest . The laying scheme of the point of interest guide signs obtained by the invention is a scientific method and has guiding significance for engineering applications.

The same or similar reference numerals correspond to the same or similar components;

The positional relationship described in the drawings is only for illustrative purposes and cannot be construed as a limitation to this patent;

Apparently, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, rather than limiting the implementation of the present invention. For those of ordinary skill in the art, on the basis of the above description, other changes or changes in different forms can also be made. It is not necessary and impossible to exhaustively list all the implementation manners here. All modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (7)

1. A point-of-interest-oriented waypoint layout method, characterized in that, comprising Extract the indicative road network of points of interest on the road network model; Defining route optimization metrics to measure the convenience of guiding routes, said route optimization metrics including path length, traffic flow, and intersection turning; Traverse the indicated road network in breadth-first order, calculate and dynamically update the path optimization index during the traversal process, and obtain the optimal guiding path in the indicated road network; Determine the content of setting guidance information and the position of setting guidance signs according to the optimal guidance route. 2. the point-of-interest-oriented wayfinding sign laying method according to claim 1, is characterized in that, extracting the indicating road network of point-of-interest on the road network model specifically comprises: On the basis of the road network model, the indication range R of the point of interest is divided according to the level of the point of interest and the amount of traffic attraction; Extraction of indicated road networks for points of interest using the double-circle covering method. 3. the point of interest-oriented road sign layout method according to claim 2, is characterized in that, extracting the instruction road network of point of interest with double-circle coverage method specifically comprises: Extract detailed road network and backbone road network respectively; Preset a circle with the point of interest as the center and the radius r _c to cover the detailed road network to obtain the core indication area G _c of the point of interest; Taking the point of interest as the center, preset a ring between the core indication area _Gc and the indication range R to cover the backbone road network to obtain the peripheral indication area _Gp of the interest point; Closely connect the core indication area _Gc and the peripheral indication area _Gp to obtain the point of interest indication road network _Gg . 4. The point-of-interest-oriented wayfinding sign layout method according to claim 2, characterized in that, in the indicated road network, the path from node k to node d is P _kd ={v _k ,...v _h , (v _h ,v _i ),v _i ,(v _i ,v _j ),v _j ,…v _d } means, among them, v _k , v _h , v _i , v _j , v _d indicate the road network Node, (v _i , v _j ) represents the road section from node i to node j, and the weight W(v _k , v _d ) of the path P _kd is equal to the weight sum of all road sections on the path plus the weighted sum of the path steering; When traversing the indicated road network in breadth-first order, the optimization goal is to minimize the path weight, and the path optimization index is dynamically updated to obtain the optimal guidance path from each intersection node in the double circle to the point of interest. 5. the point-of-interest-oriented wayfinding sign laying method according to claim 4, is characterized in that, path turning weighted sum is calculated by following formula: T(P _kd )＝f _l ×T _l (P _kd )+f _r ×T _r (P _kd )+f _s ×T _s (P _kd )+f _u ×T _u (P _kd ) (1) In formula (1), T _l (P _kd ), T _s (P _kd ), T _r (P _kd ), and Tu (P _kd ) represent the number of left turns, straight lines, right turns, and _U -turns on the path P _kd , respectively. f _l , f _s , f _r , and f _u represent the weighting coefficients for turning left, going straight, turning right, and turning around, respectively; The link weight sum is calculated by the following formula: $\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&times;</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$ The weight w(v _i , v _j ) of the link (v _i , v _j ) in formula (2) is the normalized weight, which contains two parts, where is the length of the normalized road section, l _ij is the road section length of the road section (v _i , v _j ), l _min is the minimum road section length in the indicated range R, and l _max is the maximum road section length in the indicated range R; is the normalized link flow, q _ij is the link flow of link (v _i , v _j ), q _min is the minimum link flow in the indicated range R, q _max is the maximum link flow in the indicated range R, α ₁ and α ₂ are The weighting coefficient of link flow and link length, and α ₁ +α ₂ =1; The weight calculation formula of path P _kd is: $W(v_k,v_d)={\mathrm{\&lambda;}}_1\&times;T\left(P_{kd}\right)+{\mathrm{\&lambda;}}_2\&times;\underset{P_{kd}}{\&Sigma;}w(v_i,v_j)---\left(3\right)$ In formula (3), λ ₁ and λ ₂ are the weighting coefficients of the route turning and the flow sum of road section length respectively, which are calculated according to the driver's driving cost at intersections and road sections. 6. The point-of-interest-oriented wayfinding method according to any one of claims 1 to 5, wherein the guidance information includes the name of the indicated object, the indicated direction and the distance. 7. The point-of-interest-oriented wayfinding sign layout method according to any one of claims 1 to 5, wherein the location of the set up wayfinding signboard includes indicating nodes and road sections in the road network, wherein the road sections It is the road segment that enters the most convenient path by turning after entering the intersection.