CN109781132B - A kind of empirical route replacement method, device, electronic device and storage medium - Google Patents

Abstract

The invention discloses an empirical route replacement method, device, electronic device and storage medium. The method includes: acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the road segment to be replaced; The starting point and ending point of the replacement section are determined; the section of the replacement section in the planned route is replaced with the replacement section; wherein the starting point of the to-be-replaced section is different from the starting point of the replacement section, and/or the The end point of the road section to be replaced is different from the end point of the replacement road section. Through the above technical solution, the excavation of more public experience routes is realized, and the replacement route and the to-be-replaced route do not need to be strictly overlapped, which improves the effect of navigation route planning and travel efficiency.

Description

A kind of empirical route replacement method, device, electronic device and storage medium

technical field

Embodiments of the present invention relate to a navigation path planning technology, and in particular, to an empirical route replacement method, apparatus, electronic device, and storage medium.

Background technique

At present, the navigation terminal mostly adopts the shortest path planning algorithm to realize the planning of the navigation route, that is, the distance or time is used as the weight of the directed weighted graph, and the shortest path algorithm is used, such as Dijkstra's Algorithm or Contraction Hierarchies, solve the shortest route, find one or the first few routes with the smallest weight, so as to plan one or several reasonable routes for the user.

The biggest problem with existing route planning methods is that roads are isolated from each other. For example, going from road A to road B or road C depends entirely on the selection of optimal weights, and the concept of empirical route cannot be introduced, that is, empirical route. It cannot be expressed through a weight system. However, in real life, there are many route planning needs that require human experience intervention. For example, during the peak holiday season, local experienced drivers or traffic police can often know in advance which road will become a traffic bottleneck, and at the same time know the optimal route. What is the detour route? If the route planning algorithm can express this kind of human experience as the result of route planning, then this will be of great help to the improvement of travel efficiency. Aiming at the above problems, a traditional empirical route replacement algorithm is proposed, which extracts the routes that need to be replaced into the pattern of the following route set by mining or artificially specifying:

Start->A->B->->J->K->L->M->N->O->End

Start->C->D->E->F->G->H->End

By strictly matching the start point (Start) and end point (End) of the route to be replaced with the start point (Start) and end point (End) of the replacement route, the purpose of replacement is achieved, and the planned route is finally generated.

It can be seen that the replacement method of the above-mentioned traditional empirical route replacement algorithm is too strict, and the starting point and end point of the replacement route need to be completely consistent with the starting point and end point of the route to be replaced before the replacement can be performed, which leads to the inability to excavate more alternatives for the to-be-replaced route. The popular experience route of the route.

SUMMARY OF THE INVENTION

The invention provides an experience route replacement method, device, electronic device and storage medium, which realizes the mining of more public experience routes, and the replacement route and the route to be replaced do not need to be strictly overlapped, thereby improving the effect of navigation route planning and travel efficiency.

In a first aspect, an embodiment of the present invention provides a method for replacing an empirical route, the method comprising:

acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the to-be-replaced road segment;

Determine the replacement interval based on the planned route, the starting point and the ending point of the road section to be replaced, and the starting point and the ending point of the replacement road section;

replacing the road segment of the replacement section in the planned route with the replacement road segment;

Wherein, the starting point of the road section to be replaced is different from the starting point of the replacing road section, and/or the end point of the road section to be replaced is different from the end point of the replacing road section.

In a second aspect, an embodiment of the present invention also provides a device for replacing an empirical route, the device comprising:

an obtaining module, configured to obtain a planned route, a road section to be replaced in the planned route, and a replacement road section corresponding to the to-be-replaced road section;

a determining module, configured to determine a replacement interval based on the planned route, the starting point and the ending point of the road section to be replaced, and the starting point and the ending point of the replaced road section;

a replacement module, configured to replace the road segment of the replacement interval in the planned route with the replacement road segment;

Wherein, the starting point of the road section to be replaced is different from the starting point of the replacing road section, and/or the end point of the road section to be replaced is different from the end point of the replacing road section.

In a third aspect, an embodiment of the present invention further provides an electronic device, the electronic device comprising:

one or more processors;

storage means for storing one or more programs,

The one or more programs, when executed by the one or more processors, cause the one or more processors to implement the empirical route replacement method of any one of claims 1-7.

In a fourth aspect, an embodiment of the present invention further provides a computer-readable storage medium on which a computer program is stored, and when the program is executed by a processor, implements the empirical route replacement method according to any one of claims 1-7 .

The present invention obtains the planned route, the road segment to be replaced in the planned route, and the replacement road segment corresponding to the to-be-replaced road segment, based on the planned route, the starting point and the end point of the to-be-replaced road segment, and the starting point of the replaced road segment , the end point determines the replacement section, and replaces the section of the replacement section in the planned route with the replacement section; wherein, the starting point of the section to be replaced is different from the starting point of the replacement section, and/or the section to be replaced is The technical means that the end point of the replacement road section and the end point of the replacement road section are different, so that the replacement route and the to-be-replaced route do not need to be strictly overlapped, realizing the excavation of more public experience routes, and improving the replacement efficiency of the replacement route. Improve the effect of navigation route planning and travel efficiency.

Description of drawings

1 is a schematic flowchart of a method for replacing an empirical route in Embodiment 1 of the present invention;

2 is a schematic diagram of an empirical route replacement in Embodiment 1 of the present invention;

3 is a schematic flowchart of an empirical route replacement method in Embodiment 2 of the present invention;

4 is a schematic diagram of an entry road set and an exit road set in Embodiment 2 of the present invention;

Fig. 5 is a kind of route replacement schematic diagram in the second embodiment of the present invention;

6 is a schematic flowchart of an empirical route replacement method in Embodiment 3 of the present invention;

7 is a schematic diagram of an empirical route replacement in Embodiment 3 of the present invention;

8 is a schematic flowchart of a method for replacing an empirical route in Embodiment 4 of the present invention;

Fig. 9 is a kind of experience route replacement schematic diagram in Embodiment 4 of the present invention;

10 is a schematic structural diagram of an empirical route replacement device in Embodiment 5 of the present invention;

FIG. 11 is a schematic structural diagram of an electronic device in Embodiment 6 of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention. In addition, it should be noted that, for the convenience of description, the drawings only show some but not all structures related to the present invention.

Example 1

FIG. 1 is a schematic flowchart of a method for replacing an empirical route provided in Embodiment 1 of the present invention. This embodiment can be applied to the situation of replacing a road section that cannot be passed smoothly in a planned route, and the method can be performed by an empirical route replacement device. , wherein the device can be implemented by software and/or hardware, and can generally be integrated in a navigation server corresponding to a navigation client. 1 , the empirical route replacement method includes the following steps:

Step 110: Obtain a planned route, a road section to be replaced in the planned route, and a replacement road section corresponding to the to-be-replaced road section.

The planned route specifically refers to a navigation route recommended by the navigation system for the user according to the user's travel plan. The road section to be replaced in the planned route refers to the road section that cannot be passed smoothly, including the road section where traffic jams often occur, and may also include the road section temporarily closed due to road construction, or the road section under traffic control due to political activities, etc.

Exemplarily, the obtaining the planned route includes:

Generate a planned route according to the starting and ending location information input by the user and the set route planning algorithm;

Wherein, the user's starting point position information can be obtained directly through GPS positioning, or can be obtained through a user's input operation; the user's end position information can be obtained through a user's input operation. Here, the user's input can be either the user's manual input or the user's historical input, that is, if the starting point location information and/or the ending location information that the user needs to input is the location information that the user has used before, the user can The interactive interface directly clicks on the corresponding start position and/or end position to complete the input of the start and end position information. When the starting point that the user needs to navigate is the current position of the user, preferably, the current position information of the user can be obtained through GPS positioning as the starting point position information of the algorithm planning route, so as to reduce the operation steps required by the user and improve the generated planning. The accuracy of the route improves the user experience. The set path planning algorithm can use the shortest path algorithm (such as Dijkstra algorithm) to generate the planned route, wherein the Dijkstra algorithm, also known as the single-source shortest path algorithm, is derived from a The shortest path algorithm from vertices to other vertices solves the shortest path problem in directed graphs.

Exemplarily, acquiring the road section to be replaced in the planned route and the replacement road section corresponding to the to-be-replaced road section includes:

Obtaining at least a set of experience-replaceable road segment pairs set in advance;

For each of the experience replaceable road segment pairs, if one road segment included in the current experience replaceable road segment pair is on the planned route, the road segment is determined as the road segment to be replaced, and the other road segment in the current experience replaceable road segment pair is determined as the road segment to be replaced. segment as a replacement segment.

Wherein, each set of experience-replaceable road segment pairs includes a road segment with frequent traffic jams obtained based on experience and a road segment that can be replaced without frequent traffic jams. Since the existing navigation path planning algorithms usually use the shortest path algorithm (such as Dijkstra's algorithm) to generate the planned route, there are often road sections where traffic jams often occur in the planned route. Each road segment in the alternative road segment pair is matched with the road segment in the planned route, and if a road segment included in the current experience replaceable road segment pair is on the planned route, the road segment is determined as the to-be-replaced road segment , taking the other road segment in the current experience replaceable road segment pair as the replacement road segment. Preferably, in order to reduce the calculation amount of obtaining the road sections to be replaced in the planned route and the replacement road sections corresponding to the to-be-replaced road sections, the preset experience-replaceable road sections may be centered on the frequently-occurring traffic jams based on experience summarization. The road segment is defined as the first road segment, the first road segment can be replaced, and the road segment where traffic congestion does not occur frequently is defined as the second road segment, when acquiring the road segment to be replaced in the planned route and the replacement road segment corresponding to the road segment to be replaced , only the first road segment in each group of experience-replaceable road segment pairs is matched with the road segment in the planned route.

It should be noted that, the preset experience-replaceable road segment pair may be obtained through manual designation or big data mining, which is not limited in this embodiment.

Step 120: Determine a replacement interval based on the planned route, the starting point and the ending point of the road section to be replaced, and the starting point and the ending point of the replacement road section.

Among them, in order to realize the mining of more public experience routes, so that more public experience routes are applied to the navigation route planning, so as to improve the effect of navigation route planning and the travel efficiency of users, the embodiment of the present invention does not limit the to-be-replaced The starting point of the road segment is exactly the same as the starting point of the replacement road segment, and the end point of the road segment to be replaced is strictly consistent with the end point of the replacement road segment; that is, the starting point of the road segment to be replaced is different from the starting point of the replacement road segment, and/or, The end point of the road section to be replaced is different from the end point of the road section to be replaced, which includes three possible situations, namely: the start point of the road section to be replaced is different from the start point of the road section to be replaced, and the The end point is different from the end point of the replacement road segment; or, the start point of the to-be-replaced road segment is different from the start point of the replacement road segment, and the end point of the to-be-replaced road segment is the same as the end point of the replacement road segment; The start point of the replacement road segment is the same as the start point of the replacement road segment, and the end point of the to-be-replaced road segment is different from the end point of the replacement road segment.

Exemplarily, referring to a schematic diagram of an empirical route replacement shown in FIG. 2, it can be seen from FIG. 2 that if the starting point of the road section to be replaced and the starting point of the replacement road section are not limited, and the end point of the to-be-replaced road section and the The end points of the replacement sections are strictly the same, and there are multiple replacement sections (c->d->e->f->F->G->H->X or C->D->E->F-> G->H->X) can be used to replace section 1 to be replaced (Start->A->B->J->K->L->M->N->O->End), the actual traffic road The net also follows the above rules. Further, an optimal road segment can be selected from the plurality of replacement road segments as the replacement road segment of the road segment 1 to be replaced. For example, if the replacement road segment 2 has the best usual road conditions and the shortest time based on experience, the replacement road segment can be replaced. 2 is used as the replacement road segment of the road segment 1 to be replaced, then the empirically replaceable road segment pair corresponding to Fig. 2 is:

Section 1 to be replaced = Start->A->B->J->K->L->M->N->O->End

Replacement section 2=C->D->E->F->G->H->X

Suppose the planned route is:

I->Z->Y->Start->A->B->J->K->L->M->N->O->End->P->X->Q, refer to Figure 2 As shown, the corresponding replacement interval is determined as [Y, X] based on the planned route, the starting point and the ending point of the road segment 1 to be replaced, and the starting point and the ending point of the replacement road segment 2 .

Step 130: Replace the road section of the replacement section in the planned route with the replacement road section.

Continuing to take Figure 2 as an example, it is assumed that the planned route is:

I->Z->Y->Start->A->B->J->K->L->M->N->O->End->P->X->Q

Section 1 to be replaced = Start->A->B->J->K->L->M->N->O->End

Replacement section 2=C->D->E->F->G->H->X

The corresponding replacement interval is [Y, X], then the planned route after replacement is:

I->Z->C->D->E->F->G->H->X->Q

In the technical solution of this embodiment, a person's experience route is preset as an experience replaceable road segment pair, and when planning a navigation path, the to-be-replaced road segment in the planned route and the The replacement road section corresponding to the road section to be replaced, and the replacement route and the route to be replaced do not need to strictly overlap the beginning and the end, which realizes the mining of more public experience routes, improves the replacement efficiency of the replacement route, and improves the effect of navigation route planning. travel efficiency.

Embodiment 2

FIG. 3 is a schematic flowchart of a method for replacing an empirical route according to Embodiment 2 of the present invention. On the basis of the above-mentioned embodiment, this embodiment optimizes step 120 "determining a replacement interval based on the planned route, the starting point and the ending point of the road section to be replaced, and the starting point and ending point of the replaced road section", and gives If the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, the specific determination method of the replacement section is as shown in FIG. 3 . As shown, the empirical route replacement method includes the following steps:

Step 310: Acquire a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the road segment to be replaced.

Step 320: Determine the set of incoming roads at the start point of the replacement road segment and the set of exit roads at the end point of the replacement road segment.

Wherein, the set of incoming roads at the start point of the replacement road segment refers to all roads leading to the start point of the replacement road segment, and the set of exit roads at the end point of the replacement road segment refers to all roads leading to the end point of the replacement road segment. For details, please refer to a schematic diagram of a set of entering roads and a set of exiting roads shown in FIG. 4 . As shown in FIG. 4 , assuming that the starting point of the replacement road section is A and the ending point is B, the set of entering roads from the starting point A, that is, the starting point leading to the starting point. All the roads of A are {a, b, c}, and the escape roads of the destination B are set, that is, all the roads to the destination B are {d, e, f}.

Step 330: Perform a reverse search on the planned route along the entry direction of the starting point of the road section to be replaced, and when a road belonging to the entry road set is searched, determine the road as the replacement starting point road.

The essence of performing a reverse order search on the planned route along the entry direction of the starting point of the road section to be replaced is to search for the road leading to the starting point of the road section to be replaced on the planned route. If there is a road belonging to the set of incoming roads, the road belonging to the set of incoming roads is determined as a replacement starting point road. Taking a schematic diagram of an empirical route replacement shown in FIG. 2 as an example, the above-mentioned determination process of the replacement starting point road is described: Assume that the road section to be replaced in FIG. 2 1=Start->A->B->J->K->L ->M->N->O->End, replace section 2=C->D->E->F->G->H->X, the planned route is: I->Z->Y-> Start->A->B->J->K->L->M->N->O->End->P->X->Q, then replace the entry road set of the starting point C of road segment 2 and The set of exit roads at the end point X are respectively {Z} and {Q}. On the planned route, a reverse order search is performed along the entry direction of the starting point Start of the road section 2 to be replaced, and the search result obtained first is road Y. If the search continues , then the obtained search result is road Z, and if the search is continued, the obtained search result is road I; when searching for the road belonging to the described entry road set, the road is determined as the replacement starting point road, and the reverse order search ends, In this embodiment, when the road Z is searched, it is determined that the road Z belongs to the road of the entry road set ({Z}), so the road Z is determined as the replacement starting point road, and the reverse order search ends.

Step 340: Perform sequential search along the exit direction of the end point of the road section to be replaced on the planned route, and when a road belonging to the escape road set is searched, determine the road as the replacement destination road.

Wherein, the essence of performing sequential search along the exit direction of the end point of the road section to be replaced on the planned route is to sequentially search all roads leading to the end point of the road section to be replaced on the planned route, and continue with Taking the example in the above step 330 as an example, in the planned route (I->Z->Y->Start->A->B->J->K->L->M->N->O- >End->P->X->Q) along the exit direction of the end point End of the road section 1 to be replaced, and the obtained search results are road P, road X and road Q in turn. In the case of road Q, it is determined that the road Q belongs to the road of the escape road set ({Q}), so the road Q is determined as the replacement destination road, and the sequential search ends.

Step 350: Determine the replacement start point road and the replacement end road as the start point and the end point of the replacement interval, respectively.

Continuing to take the example in the above step 340 as an example, the starting point and the ending point of the replacement interval are the road Z and the road Q, respectively.

Step 360: Replace the road segment between the replacement starting point road and the replacement destination road in the planned route with the replacement road segment.

Exemplarily, refer to a schematic diagram of route replacement shown in FIG. 5 , wherein road segment 1 is the road segment to be replaced, road segment 2 is the replacement road segment, and the set of access roads at the starting point A of the replacement road segment is {a, b, c}, and the replacement The set of exit roads at the end point B of the road segment is {d, e, f}. A reverse order search is performed on the planned route along the entry direction of the starting point of the road segment to be replaced, and the searched road belonging to the entry road set is road {a}, so road a is the replacement starting point road. On the planned route, a sequential search is performed along the escape direction of the end point of the road section to be replaced, and the searched road belonging to the escape road set is road e, so road e is the replacement end road, so road a and road a in the planned route and The segment between road e is replaced with the replacement segment 2 to generate the final route.

In the technical solution of this embodiment, if the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, the starting point of the replacement road section is first determined The set of entry roads and the set of exit roads at the end of the replacement road section; then the reverse order search is performed on the planned route along the entry direction of the starting point of the to-be-replaced road section, when a road belonging to the set of entry roads is searched , determine the road as the replacement starting point road; carry out sequential search along the exit direction of the end point of the road section to be replaced on the planned route, when the road belonging to the set of escaped roads is searched, determine the road as the replacement road end road, and finally replace the road section between the replacement starting point road and the replacement destination road in the planned route with the replacement road section, realizing the excavation of more public experience routes and improving the navigation route planning. effectiveness and travel efficiency.

Embodiment 3

FIG. 6 is a schematic flowchart of a method for replacing an empirical route according to Embodiment 3 of the present invention. On the basis of the above-mentioned embodiment, this embodiment continues to optimize step 120 of “determining a replacement interval based on the planned route, the starting point and ending point of the road section to be replaced, and the starting point and ending point of the replaced road section”, giving If the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is the same as the end point of the replacement road section, the specific determination method of the replacement interval is shown in Fig. 6 for details. As shown, the empirical route replacement method includes the following steps:

Step 610: Acquire a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the road segment to be replaced.

Step 620: Determine the access road set of the starting point of the replacement road segment.

Step 630: Search in reverse order along the entry direction of the starting point of the road section to be replaced on the planned route, and when a road belonging to the entry road set is searched, determine the road as the replacement starting point road.

Step 640: Determine the next road of the replacement starting point road on the planned route and the end point of the road section to be replaced as the start point and the end point of the replacement interval, respectively.

Wherein, the next road of the replacement starting point road on the planned route refers to the road that is on the planned route, and is the nearest neighbor to the replacement starting point road, which the replacement starting point road leads to. Specifically, refer to a schematic diagram of an empirical route replacement shown in FIG. 7 , wherein the road sections to be replaced are:

Start->A->B->J->K->L->M->N->O->End

The replacement section is: C->D->E->F->G->H->End,

The planned route is: Z->Y->Start->A->B->J->K->L->M->N->O->End->P->X->Q

Then the set of access roads at the starting point C of the replacement road segment (C->D->E->F->G->H->End) is {Z}, and in the planned route (Z->Y->Start- >A->B->J->K->L->M->N->O->End->P->X->Q) along the section to be replaced (Start->A-> B->J->K->L->M->N->O->End) and the entry direction of the starting point Start) are searched in reverse order, and the search results obtained are {Z, Y}, where road Z belongs to the Enter the road of the road set, so road Z is determined as the replacement starting point road, and the next road on the planned route of the replacement starting point road Z is road Y, therefore, road Y and the end point End of the to-be-replaced road section are respectively determined are the start and end points of the replacement interval, that is, the corresponding replacement interval is [Y, End].

Step 650: Replace the road segment from the next road of the replacement starting point road to the end point of the to-be-replaced road segment in the planned route with the replacement road segment.

Continuing to use the example in step 640 above, the replaced planned route is:

Z->C->D->E->F->G->H->End->P->X->Q

In the technical solution of this embodiment, if the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is the same as the end point of the replacement road section, only the starting point of the replacement road section is determined. the entry road set; then perform reverse order search along the entry direction of the starting point of the road section to be replaced on the planned route, when a road belonging to the entry road set is searched, determine the road as the replacement starting point road, and Finally, the road section from the next road of the replacement starting point road to the end point of the to-be-replaced road section in the planned route is replaced with the replacement road section, which realizes the mining of more public experience routes and improves the navigation route planning. effect and travel efficiency.

Embodiment 4

FIG. 8 is a schematic flowchart of a method for replacing an empirical route according to Embodiment 4 of the present invention. On the basis of the above-mentioned embodiment, this embodiment continues to optimize step 120 of “determining a replacement interval based on the planned route, the starting point and ending point of the road section to be replaced, and the starting point and ending point of the replaced road section”, giving If the starting point of the road section to be replaced is the same as the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, the specific determination method of the replacement section is shown in FIG. 8 . As shown, the empirical route replacement method includes the following steps:

Step 810: Acquire a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the road segment to be replaced.

Step 820: Determine the set of exit roads at the end point of the replacement road segment.

Step 830: Perform sequential search along the exit direction of the end point of the road section to be replaced on the planned route, and when a road belonging to the escape road set is searched, determine the road as the replacement destination road.

Step 840: Determine the start point of the road section to be replaced and the last road of the replacement destination road on the planned route as the start point and the end point of the replacement section, respectively.

Wherein, the last road of the alternative destination road on the planned route refers to the road leading to the alternative destination road, on the planned route, and closest to the alternative destination road. Specifically, refer to a schematic diagram of an empirical route replacement shown in FIG. 9 , wherein the road sections to be replaced are:

Start->A->B->J->K->L->M->N->O->End

The replacement section is: Start->C->D->E->F->G->H->X,

The planned route is: Z->Y->Start->A->B->J->K->L->M->N->O->End->P->X->Q

Then the set of escape roads at the end point X of the replacement road segment (Start->C->D->E->F->G->H->X) is {Q}, and in the planned route (Z->Y- >Start->A->B->J->K->L->M->N->O->End->P->X->Q) along the section to be replaced (Start-> A->B->J->K->L->M->N->O->End) and the exit direction of the end point End) are searched sequentially, and the obtained search results are {P, X, Q}, where The road Q belongs to the road of the set of escaped roads, so the road Q is determined as the replacement end road, and the last road on the planned route of the replacement end road Q is the road X, therefore, the starting point Start of the road segment to be replaced, and The last road X of the replacement destination road on the planned route is respectively determined as the start point and the end point of the replacement interval, that is, the corresponding replacement interval is [Start, X].

Step 850: Replace the road segment from the starting point of the road segment to be replaced to the last road of the replacement destination road in the planned route with the replacement road segment.

Continuing to use the example in step 840 above, the replaced planned route is:

Z->Y->Start->C->D->E->F->G->H->X->Q

In the technical solution of this embodiment, if the starting point of the road section to be replaced is the same as the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, only the end point of the replacement road section is determined. Then, on the planned route, a sequential search is performed along the exit direction of the end point of the road section to be replaced, and when a road belonging to the set of escape roads is searched, the road is determined as the replacement destination road, and Finally, the road segment of the previous road from the starting point of the road segment to be replaced to the replacement destination road in the planned route is replaced with the replacement road segment, which realizes the mining of more public experience routes and improves the navigation route planning. effect and travel efficiency.

On the basis of the above-mentioned embodiment, the method for replacing the empirical route further includes: if no road belonging to the set of entering roads is searched, and/or no road belonging to the set of exit roads is searched, issuing an inability to proceed. Tips for road replacement to improve user experience.

Embodiment 5

FIG. 10 is a schematic structural diagram of an empirical route replacement device according to Embodiment 5 of the present invention. Referring to FIG. 10 , the device includes: an acquisition module 1010 , a determination module 1020 , and a replacement module 1030 ;

Wherein, the obtaining module 1010 is used to obtain the planned route, the road section to be replaced in the planned route, and the replacement road section corresponding to the to-be-replaced road section; the determining module 1020 is used to obtain the planned route, the road section to be replaced based on the The starting point, the ending point, and the starting point and ending point of the replacement road section determine the replacement section; the replacement module 1030 is configured to replace the section of the replacement section in the planned route with the replacement section; wherein, the to-be-replaced road section is The start point is different from the start point of the replacement road segment, and/or the end point of the road segment to be replaced is different from the end point of the replacement road segment.

Further, if the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, the determining module 1020 is specifically configured to: determine the replacement road section. The entry road set of the starting point and the exit road set of the end point of the replacement road segment; the reverse order search is performed on the planned route along the entry direction of the starting point of the to-be-replaced road segment, when a road belonging to the entry road set is searched for , determine the road as the replacement starting point road; carry out sequential search along the exit direction of the end point of the road section to be replaced on the planned route, when the road belonging to the set of escaped roads is searched, determine the road as the replacement road the end road; the replacement starting point road and the replacement ending road are respectively determined as the starting point and the ending point of the replacement interval; correspondingly, the replacement module 1030 is used for: comparing the replacement starting point road and the replacement starting point road in the planned route with the The link between the replacement destination roads is replaced with the replacement link.

Further, if the starting point of the road section to be replaced is different from the starting point of the replacement road section, and the end point of the road section to be replaced is the same as the end point of the replacement road section, the determining module 1020 is specifically configured to: determine the replacement road section. The entry road set of the starting point; perform reverse order search along the entry direction of the starting point of the to-be-replaced road section on the planned route, and when a road belonging to the entry road set is searched, determine the road as the replacement starting point road; The next road of the replacement starting point road on the planned route and the end point of the road section to be replaced are respectively determined as the starting point and the ending point of the replacement interval; correspondingly, the replacement module 1030 is used for:

A road segment from the next road of the replacement starting point road to the end point of the to-be-replaced road segment in the planned route is replaced with the replacement road segment.

Further, if the starting point of the road section to be replaced is the same as the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section, the determining module 1020 is specifically configured to: determine the replacement The set of exit roads at the end of the road segment; perform sequential search along the exit direction of the end point of the road segment to be replaced on the planned route, and when a road belonging to the set of exit roads is found, the road is determined as the replacement destination road ; Determine the starting point of the road section to be replaced and the last road of the replacement destination road on the planned route as the starting point and the end point of the replacement interval respectively; Correspondingly, the replacement module 1030 is specifically used for: In the planned route, the road segment of the previous road from the starting point of the road segment to be replaced to the replacement destination road is replaced with the replacement road segment.

Further, the obtaining module 1010 includes: an obtaining unit and a determining unit,

Wherein, the obtaining unit is used to obtain at least one set of preset experience-replaceable road segment pairs;

The determining unit is used for each of the experience replaceable road segment pairs, if a road segment included in the current experience replaceable road segment pair is on the planned route, then the road segment is determined as the road segment to be replaced, and the current experience replaceable road segment is determined as the road segment to be replaced. Another segment in the pair is used as a replacement segment.

Further, the device further includes a reminder module for issuing a reminder message that the road cannot be replaced if the road belonging to the set of entry roads is not searched, and/or the road belonging to the set of exit roads is not searched. .

Further, the obtaining module 1010 further includes: a route generating unit, configured to generate a planned route according to the starting and ending location information input by the user and the set route planning algorithm.

In the technical solution of this embodiment, a person's experience route is preset as an experience replaceable road segment pair, and when planning a navigation path, the to-be-replaced road segment in the planned route and the The replacement road section corresponding to the road section to be replaced, and the replacement route and the route to be replaced do not need to strictly overlap the beginning and the end, which realizes the mining of more public experience routes, improves the replacement efficiency of the replacement route, and improves the effect of navigation route planning. travel efficiency.

The empirical route replacement device provided by the embodiment of the present invention can execute the empirical route replacement method provided by any embodiment of the present invention, and has corresponding functional modules and beneficial effects of the execution method.

Embodiment 6

FIG. 11 is a schematic structural diagram of an electronic device according to Embodiment 6 of the present invention. Figure 11 shows a block diagram of an exemplary apparatus 12 suitable for use in implementing embodiments of the present invention. The device 12 shown in FIG. 11 is only an example, and should not impose any limitations on the functions and scope of use of the embodiments of the present invention.

As shown in FIG. 11, device 12 takes the form of a general-purpose computing device. Components of device 12 may include, but are not limited to, one or more processors or processing units 16, system memory 28, and a bus 18 connecting various system components including system memory 28 and processing unit 16.

Bus 18 represents one or more of several types of bus structures, including a memory bus or memory controller, a peripheral bus, a graphics acceleration port, a processor, or a local bus using any of a variety of bus structures. By way of example, these architectures include, but are not limited to, Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MAC) bus, Enhanced ISA bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect ( PCI) bus.

Device 12 typically includes a variety of computer system readable media. These media can be any available media that can be accessed by device 12, including volatile and non-volatile media, removable and non-removable media.

System memory 28 may include computer system readable media in the form of volatile memory, such as random access memory (RAM) 30 and/or cache memory 32 . Device 12 may further include other removable/non-removable, volatile/non-volatile computer system storage media. For example only, storage system 34 may be used to read and write to non-removable, non-volatile magnetic media (not shown in FIG. 11, commonly referred to as a "hard drive"). Although not shown in Figure 11, a disk drive for reading and writing to removable non-volatile magnetic disks (eg "floppy disks") and removable non-volatile optical disks (eg CD-ROM, DVD-ROM) may be provided or other optical media) to read and write optical drives. In these cases, each drive may be connected to bus 18 through one or more data media interfaces. The memory 28 may include at least one program product having a set of (eg, the acquisition module 1010, the determination module 1020, and the replacement module 1030 of the empirical route replacement apparatus) program modules configured to perform the functions of various embodiments of the present invention. Function.

A program/utility 40 having a set of program modules 42 (acquisition module 1010, determination module 1020, and replacement module 1030 of the empirical route replacement apparatus) may be stored, for example, in memory 28, such program modules 42 including, but not limited to, an operating system , one or more applications, other program modules, and program data, each or some combination of these examples may include an implementation of a network environment. Program modules 42 generally perform the functions and/or methods of the described embodiments of the present invention.

Device 12 may also communicate with one or more external devices 14 (eg, keyboards, pointing devices, display 24, etc.), may also communicate with one or more devices that enable a user to interact with device 12, and/or communicate with Device 12 can communicate with any device (eg, network card, modem, etc.) that communicates with one or more other computing devices. Such communication may take place through input/output (I/O) interface 22 . Also, the device 12 may communicate with one or more networks (eg, a local area network (LAN), a wide area network (WAN), and/or a public network such as the Internet) through a network adapter 20 . As shown, network adapter 20 communicates with other modules of device 12 via bus 18 . It should be understood that, although not shown, other hardware and/or software modules may be used in conjunction with device 12, including but not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and Data backup storage system, etc.

The processing unit 16 executes various functional applications and data processing by running the programs stored in the system memory 28, for example, implementing the empirical route replacement method provided by the embodiments of the present invention.

Embodiment 7

Embodiment 7 of the present invention further provides a computer-readable storage medium on which a computer program is stored, and when the program is executed by a processor, implements the empirical route replacement method described in any of the embodiments of the present invention. The empirical route replacement method includes:

acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the to-be-replaced road segment;

Determine the replacement interval based on the planned route, the starting point and the ending point of the road section to be replaced, and the starting point and the ending point of the replacement road section;

replacing the road segment of the replacement section in the planned route with the replacement road segment;

Wherein, the starting point of the road section to be replaced is different from the starting point of the replacing road section, and/or the end point of the road section to be replaced is different from the end point of the replacing road section.

The computer storage medium in the embodiments of the present invention may adopt any combination of one or more computer-readable media. The computer-readable medium may be a computer-readable signal medium or a computer-readable storage medium. The computer-readable storage medium can be, for example, but not limited to, an electrical, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus or device, or a combination of any of the above. More specific examples (a non-exhaustive list) of computer readable storage media include: electrical connections having one or more wires, portable computer disks, hard disks, random access memory (RAM), read only memory (ROM), Erasable programmable read only memory (EPROM or flash memory), optical fiber, portable compact disk read only memory (CD-ROM), optical storage devices, magnetic storage devices, or any suitable combination of the foregoing. In this document, a computer-readable storage medium can be any tangible medium that contains or stores a program that can be used by or in conjunction with an instruction execution system, apparatus, or device.

A computer-readable signal medium may include a propagated data signal in baseband or as part of a carrier wave, with computer-readable program code embodied thereon. Such propagated data signals may take a variety of forms, including but not limited to electromagnetic signals, optical signals, or any suitable combination of the foregoing. A computer-readable signal medium can also be any computer-readable medium other than a computer-readable storage medium that can transmit, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device .

Program code embodied on a computer readable medium may be transmitted using any suitable medium, including - but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations of the present invention may be written in one or more programming languages, including object-oriented programming languages—such as Java, Smalltalk, C++, but also conventional Procedural programming languages—such as C or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer, or entirely on the remote computer or server. In the case of a remote computer, the remote computer may be connected to the user's computer through any kind of network, including a local area network (LAN) or a wide area network (WAN), or may be connected to an external computer (eg, using an Internet service provider through Internet connection).

Note that the above are only preferred embodiments of the present invention and applied technical principles. Those skilled in the art will understand that the present invention is not limited to the specific embodiments described herein, and various obvious changes, readjustments and substitutions can be made by those skilled in the art without departing from the protection scope of the present invention. Therefore, although the present invention has been described in detail through the above embodiments, the present invention is not limited to the above embodiments, and can also include more other equivalent embodiments without departing from the concept of the present invention. The scope is determined by the scope of the appended claims.

Claims (15)

1. an experience route replacement method, is characterized in that, comprises: acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the to-be-replaced road segment; If the starting point of the to-be-replaced road segment is different from the starting point of the replaced road segment, and the end point of the to-be-replaced road segment is different from the end point of the replaced road segment, then determine the access road set of the starting point of the replaced road segment and the replacement road segment. The set of exit roads at the end of the road segment, the reverse order search is performed on the planned route along the entry direction of the starting point of the road segment to be replaced, and when a road belonging to the set of entry roads is searched, the road is determined as the replacement starting point road ; Carry out sequential search along the exit direction of the end point of the road section to be replaced on the planned route, and when searching for the road belonging to the set of exit roads, determine the road as the replacement destination road; The replacement starting point road and the replacement destination road are respectively determined as the starting point and the end point of the replacement interval; replacing the road segment of the replacement section in the planned route with the replacement road segment; Wherein, the set of incoming roads refers to all roads leading to the starting point of the replacement road segment, and the set of exit roads refers to all roads leading to the end point of the replacement road segment. 2. The method according to claim 1, wherein obtaining the road section to be replaced in the planned route and the replacement road section corresponding to the road section to be replaced, comprising: Obtaining at least a set of experience-replaceable road segment pairs set in advance; For each of the experience replaceable road segment pairs, if one road segment included in the current experience replaceable road segment pair is on the planned route, the road segment is determined as the road segment to be replaced, and the other road segment in the current experience replaceable road segment pair is determined as the road segment to be replaced. segment as a replacement segment. 3. The method according to claim 1, further comprising: if no road belonging to the set of entering roads is searched, and/or no road belonging to the set of exit roads is searched, sending a message that cannot be Hint for road replacement. 4. The method according to any one of claims 1-3, wherein the acquiring a planned route comprises: The planned route is generated according to the starting and ending location information input by the user and the set route planning algorithm. 5. an empirical route replacement method, is characterized in that, comprises: acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the to-be-replaced road segment; If the starting point of the road segment to be replaced is different from the starting point of the replacement road segment, and the end point of the road segment to be replaced is the same as the end point of the replacement road segment, then determine the access road set of the starting point of the replacement road segment; in the Perform reverse order search along the entry direction of the starting point of the road section to be replaced on the planned route, and when a road belonging to the entry road set is searched, determine the road as the replacement starting point road; place the replacement starting point road in the planning The next road on the route and the end point of the road section to be replaced are respectively determined as the start point and the end point of the replacement interval; replacing the road segment of the replacement section in the planned route with the replacement road segment; Wherein, the set of incoming roads refers to all roads leading to the starting point of the replacement road segment. 6. The method according to claim 5, wherein obtaining the road section to be replaced in the planned route and the replacement road section corresponding to the road section to be replaced, comprising: Obtaining at least a set of experience-replaceable road segment pairs set in advance; For each of the experience replaceable road segment pairs, if one road segment included in the current experience replaceable road segment pair is on the planned route, the road segment is determined as the road segment to be replaced, and the other road segment in the current experience replaceable road segment pair is determined as the road segment to be replaced. segment as a replacement segment. 7 . The method according to claim 5 , further comprising: if no road belonging to the set of incoming roads is searched, sending a prompt message that the road cannot be replaced. 8 . 8. an empirical route replacement method, is characterized in that, comprises: acquiring a planned route, a road segment to be replaced in the planned route, and a replacement road segment corresponding to the to-be-replaced road segment; If the starting point of the road segment to be replaced is the same as the starting point of the replacement road segment, and the end point of the road segment to be replaced is different from the end point of the replacement road segment, then determine the set of exit roads of the end point of the replacement road segment; in the On the planned route, a sequential search is performed along the exit direction of the end point of the road section to be replaced, and when a road belonging to the escape road set is searched, the road is determined as the replacement end road; the starting point of the road section to be replaced, and The last road of the replacement destination road on the planned route is respectively determined as the start point and the end point of the replacement interval; replacing the road segment of the replacement section in the planned route with the replacement road segment; Wherein, the set of escaped roads refers to all roads leading to the end point of the replacement road segment. 9 . The method according to claim 8 , wherein obtaining the road section to be replaced in the planned route and the replacement road section corresponding to the road section to be replaced, comprising: 10 . Obtaining at least a set of experience-replaceable road segment pairs set in advance; For each of the experience replaceable road segment pairs, if one road segment included in the current experience replaceable road segment pair is on the planned route, the road segment is determined as the road segment to be replaced, and the other road segment in the current experience replaceable road segment pair is determined as the road segment to be replaced. segment as a replacement segment. 10 . The method according to claim 8 , further comprising: if no road belonging to the set of escaped roads is searched, sending a prompt message that the road cannot be replaced. 11 . 11. An experience route replacement device, characterized in that, comprising: an obtaining module, configured to obtain a planned route, a road section to be replaced in the planned route, and a replacement road section corresponding to the to-be-replaced road section; A determination module, configured to determine the access road of the starting point of the replaced road segment if the starting point of the to-be-replaced road segment is different from the starting point of the replaced road segment, and the end point of the to-be-replaced road segment is different from the end point of the replaced road segment set and the set of exit roads at the end of the replacement road segment, perform a reverse search on the planned route along the entry direction of the starting point of the to-be-replaced road segment, and when a road belonging to the set of entry roads is searched, the road Determine as the replacement starting point road; perform sequential search along the exit direction of the end point of the to-be-replaced road section on the planned route, and when a road belonging to the set of escaped roads is searched, determine the road as the replacement destination road; The replacement start point road and the replacement end road are respectively determined as the start point and the end point of the replacement interval; a replacement module, configured to replace the road segment of the replacement interval in the planned route with the replacement road segment; Wherein, the set of incoming roads refers to all roads leading to the starting point of the replacement road segment, and the set of exit roads refers to all roads leading to the end point of the replacement road segment. 12. An empirical route replacement device, characterized in that, comprising: an obtaining module, configured to obtain a planned route, a road section to be replaced in the planned route, and a replacement road section corresponding to the to-be-replaced road section; A determination module, configured to determine the access road of the starting point of the replaced road segment if the starting point of the to-be-replaced road segment is different from the starting point of the replaced road segment, and the end point of the to-be-replaced road segment is the same as the end point of the replaced road segment set; perform reverse order search along the entry direction of the starting point of the road section to be replaced on the planned route, when a road belonging to the entry road set is searched, determine the road as the replacement starting point road; set the replacement starting point The next road of the road on the planned route and the end point of the road section to be replaced are determined as the start point and the end point of the replacement interval, respectively; a replacement module, configured to replace the road segment of the replacement interval in the planned route with the replacement road segment; Wherein, the set of incoming roads refers to all roads leading to the starting point of the replacement road segment. 13. An empirical route replacement device, characterized in that it comprises: an obtaining module, configured to obtain a planned route, a road section to be replaced in the planned route, and a replacement road section corresponding to the to-be-replaced road section; A determination module, configured to determine the exit road of the end point of the replacement road section if the starting point of the road section to be replaced is the same as the starting point of the replacement road section, and the end point of the road section to be replaced is different from the end point of the replacement road section set; perform sequential search along the exit direction of the end point of the road section to be replaced on the planned route, and when a road belonging to the set of exit roads is found, determine the road as the replacement destination road; set the to-be-replaced road The starting point of the road section and the previous road of the replacement destination road on the planned route are respectively determined as the starting point and the ending point of the replacement section; a replacement module, configured to replace the road segment of the replacement interval in the planned route with the replacement road segment; Wherein, the set of escaped roads refers to all roads leading to the end point of the replacement road segment. 14. An electronic device, characterized in that the electronic device comprises: one or more processors; storage means for storing one or more programs, The one or more programs, when executed by the one or more processors, cause the one or more processors to implement the empirical route replacement method of any one of claims 1-10. 15. A computer-readable storage medium on which a computer program is stored, characterized in that, when the program is executed by a processor, the empirical route replacement method according to any one of claims 1-10 is implemented.

Images