CN111222667B - Route planning method, device, equipment and storage medium - Google Patents

Abstract

The embodiment of the invention discloses a route planning method, a device, equipment and a storage medium. The method comprises the following steps: obtaining a starting point position, an end point position, a total tour duration of a user and preference degree scores of the user for each scenic spot; determining scenic spots to be inserted and the insertion positions of the scenic spots to be inserted from scenic spots which are not covered by the current route according to the preference degree scores; calculating the tour time length corresponding to the first target route after the scenic spot to be inserted is inserted into the insertion position; if the tour time is not longer than the tour total time, inserting the scenic spot to be inserted into the insertion position; continuously inserting scenic spots; and if the tour time length is longer than the tour total time length, determining the current route as a planned route. According to the route planning method, device, equipment and storage medium, route planning is performed according to the preference degree scores of the users aiming at the scenic spots, and the planned route can meet the preference requirements of the users.

Description

Route planning method, device, equipment and storage medium

Technical field

The present invention relates to the field of computer technology, and in particular to a route planning method, device, equipment and storage medium.

Background technique

Orientation problems are divided into traditional orientation problems and team orientation problems. They are a special type of non-deterministic polynomial-hard (NP-hard) path optimization problems. They are very common in the fields of logistics and tourism and also have Extremely challenging.

The optimization problem of solving personalized travel routes can be simulated as an orientation problem with time windows (OrienteeringProblem with Time Windows, OPTW).

At present, the Iterated Local Search (ILS) algorithm is mainly used to solve the OPTW problem. However, in the process of route planning using the ILS algorithm, locations with high user preference may be excluded, making the planned route unable to meet the user's preference requirements.

Contents of the invention

Embodiments of the present invention provide a route planning method, device, equipment and storage medium, which can enable the planned route to meet the user's preference requirements.

On the one hand, embodiments of the present invention provide a route planning method, which includes:

Obtain the user's starting point location, end point location, total tour time and user's preference score for each attraction;

According to the preference score, from the attractions not covered by the current route from the starting point location to the end location, determine the attractions to be inserted and the insertion positions of the attractions to be inserted in the current route;

Calculate the tour duration corresponding to the first target route after inserting the attraction to be inserted into the insertion position;

If the tour duration is not greater than the total tour duration, the attractions to be inserted will be inserted into the insertion position;

Return according to the preference score, from the attractions not covered by the current route from the starting point to the end location, determine the attractions to be inserted and the attractions to be inserted will continue to be executed for the insertion position in the current route;

If the tour duration is greater than the total tour duration, the current route is determined as the planned route.

On the other hand, an embodiment of the present invention provides a path planning device, which includes:

The acquisition module is used to obtain the user's starting point location, end point location, total tour time and the user's preference score for each attraction;

The first determination module is used to determine the attractions to be inserted and the insertion positions of the attractions to be inserted in the current route from the attractions not covered by the current route from the starting point location to the end location based on the preference score;

A calculation module used to calculate the tour duration corresponding to the first target route after inserting the attraction to be inserted into the insertion position;

The insertion module is used to insert the attraction to be inserted into the insertion position if the tour duration is not greater than the total tour duration; and trigger the determination module;

The second determination module is used to determine the current route as the planned route if the tour duration is greater than the total tour duration.

In another aspect, embodiments of the present invention provide a route planning device, which includes: a memory, a processor, and a computer program stored in the memory and executable on the processor;

When the processor executes the computer program, the route planning method provided by the embodiment of the present invention is implemented.

On the other hand, embodiments of the present invention provide a computer-readable storage medium. A computer program is stored on the computer-readable storage medium. When the computer program is executed by a processor, the route planning method provided by the embodiment of the present invention is implemented.

The route planning method, device, equipment and storage medium of the embodiments of the present invention perform route planning based on the user's preference scores for scenic spots, so that the planned route can meet the user's preference requirements.

Description of drawings

In order to explain the technical solutions of the embodiments of the present invention more clearly, the drawings required to be used in the embodiments of the present invention will be briefly introduced below. For those of ordinary skill in the art, without exerting creative efforts, they can also Additional drawings can be obtained from these drawings.

Figure 1 shows a schematic diagram of the results of route planning provided by the prior art;

Figure 2 shows a schematic flow chart of a route planning method provided by an embodiment of the present invention;

Figure 3 shows a schematic scenario diagram of the route planning method provided by an embodiment of the present invention;

Figure 4 shows a schematic flow chart of route optimization provided by an embodiment of the present invention;

Figure 5 shows a schematic diagram of the results of route planning provided by the embodiment of the present invention;

Figure 6 shows a comparison diagram of the total duration of the route planned by the embodiment of the present invention and the total duration of the route planned by the prior art;

Figure 7 shows a comparison of the time it takes to plan a route according to the embodiment of the present invention and the time it takes to plan a route using the prior art;

Figure 8 shows a schematic structural diagram of a route planning device provided by an embodiment of the present invention;

FIG. 9 shows a structural diagram of an exemplary hardware architecture of a computing device capable of implementing the route planning method and apparatus according to embodiments of the present invention.

Detailed ways

Features and exemplary embodiments of various aspects of the present invention will be described in detail below. In order to make the purpose, technical solutions and advantages of the present invention clearer, the present invention will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are configured only to explain the invention and not to limit the invention. It will be apparent to one skilled in the art that the present invention may be practiced without some of these specific details. The following description of the embodiments is merely intended to provide a better understanding of the invention by illustrating examples of the invention.

It should be noted that in this article, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that these entities or operations are mutually exclusive. any such actual relationship or sequence exists between them. Furthermore, the terms "comprises," "comprises," or any other variations thereof are intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus that includes a list of elements includes not only those elements, but also those not expressly listed other elements, or elements inherent to the process, method, article or equipment. Without further limitation, an element defined by the statement "comprising..." does not exclude the presence of additional identical elements in a process, method, article, or device that includes the stated element.

Figure 1 shows a schematic diagram of the route planning results provided by the prior art. There are a total of 5 scenic spots in Figure 1, and the 5 scenic spots are scenic spots 1, 2, 3, 4 and 5 respectively. Attraction 5 is an attraction with a high degree of user preference. It can be seen from the schematic diagram of the route planning results shown in Figure 1 that the route planned using the existing technology does not include the scenic spot 5, so that the planned route cannot meet the user's preference requirements. Among them, the result of the route planning in Figure 1 is: starting point location—>attraction 2—>attraction 4—>attraction 1—>end point location.

In order to solve the existing technical problems, embodiments of the present invention provide a route planning method, device, equipment and storage medium to perform route planning so that the planned route meets the user's preference requirements. The route planning method provided by the embodiment of the present invention is first described in detail below.

Figure 2 shows a schematic flowchart of a route planning method provided by an embodiment of the present invention. Route planning methods can include:

S201: Obtain the user's starting point location, end point location, total tour time and user's preference score for each attraction.

S202: According to the preference score, determine the scenic spots to be inserted and the insertion positions of the scenic spots to be inserted in the current route from the scenic spots not covered by the current route from the starting point to the end position.

S203: Calculate the tour duration corresponding to the first target route after inserting the scenic spot to be inserted into the insertion position.

S204: If the tour duration is not greater than the total tour duration, insert the attraction to be inserted into the insertion position and continue to execute S202.

S205: If the tour duration is greater than the total tour duration, determine the current route as the planned route.

By way of example, the route planning method provided by the embodiment of the present invention is described below in conjunction with a specific route planning scenario.

Figure 3 shows a schematic scenario diagram of the route planning method provided by an embodiment of the present invention. The scene shown in Figure 3 includes 10 scenic spots, namely scenic spots 1, 2,..., 9 and 10. Among them, the user's preferences for attractions 1, 2, ..., 9 and 10 can be respectively: very much want to go, relatively want to go, relatively don't want to go, relatively don't want to go, must go, very do not want to go, relatively Want to go, really want to go, somewhat don't want to go and relatively don't want to go.

Among them, the corresponding relationship between preference degree and preference degree score is shown in Table 1.

Table 1

degree of preference preference score Don't want to go very much 1 Don't want to go 2 Rather want to go 3 Very much want to go 4 must go MAX

In one embodiment of the present invention, the preference score MAX is much larger than other preference scores, for example, MAX is 10000, 1000000 or 20000, etc.

Correspondingly, based on Table 1, the user's preference scores for attractions 1, 2,..., 9 and 10 are respectively: 4, 3, 2, 2, MAX, 1, 3, 4, 2 and 2 .

In one embodiment of the present invention, if the user does not set a preference level for a certain scenic spot, the user's preference level for the scenic spot can be defaulted to: I would rather like to go there.

Assume that the total tour duration set by the user is 160 minutes.

The starting route is from the starting point to the ending position directly, that is, the current route is: starting point position -> ending position.

Assume that the scenic spot to be inserted is determined to be scenic spot 5 based on the preference score. It can be understood that the current insertion position is between the starting point position and the end position. Calculate the first target route after inserting attraction 5 between the starting point and the end location: starting point location—>attraction 5—>tour duration corresponding to the end location. Assume that the calculated tour duration is 100 minutes, which is less than the user setting The total tour duration is 160 minutes, then insert attraction 5 between the starting point and the end location. At this time, the current route is: starting point location—>attraction 5—>tour duration corresponding to the end location.

Based on the current route: starting point location—>attraction 5—>end location, and then insert the attraction.

Assume that the attraction to be inserted is determined to be attraction 1 based on the preference score. It can be understood that the current insertion position can be between the starting point position and attraction 5, or between the attraction 5 and the end position.

In one embodiment of the present invention, the position with the least time consumption can be used as the best insertion position for inserting the scenic spot.

For example, assuming that before attraction 1 is inserted, the time from the starting point to attraction 5 is 25 minutes. After attraction 1 is inserted between the starting point and attraction 5, the time from the starting point to attraction 5 is 50 minutes. The time consumption is 50-25=25 minutes.

Assume that before attraction 1 is inserted, the time from attraction 5 to the end position is 75 minutes. After inserting attraction 1 between attraction 5 and the end position, the time from attraction 5 to the end position is 85 minutes, and the time consumption is 85-75 =10 minutes.

Then the best insertion position of scenic spot 1 is determined between scenic spot 5 and the end position.

Calculate the first target route after inserting scenic spot 1 between scenic spot 5 and the end location: starting point location—>attraction 5—>attraction 1—>the tour duration corresponding to the end location. The calculated tour duration is 110 minutes, which is less than If the total tour time set by the user is 160 minutes, attraction 1 will be inserted between attraction 5 and the end location. At this time, the current route is: starting point location—>attraction 5—>attraction 1—>end location.

The subsequent insertion process is the same as the insertion process of scenic spot 1. For details, reference can be made to the insertion process of scenic spot 1, which will not be described in detail here in the embodiment of the present invention.

In one embodiment of the present invention, determining the attractions to be inserted from the attractions not covered by the current route from the starting point location to the end location according to the preference score and the insertion location of the attractions to be inserted in the current route may include : For each scenic spot not covered by the current route from the starting point to the end position, calculate the corresponding time consumption between two adjacent scenic spots inserted into the current route; determine the time consumption of the scenic spot based on the time consumption Minimum insertion cost; use the position between two adjacent attractions corresponding to the minimum insertion cost as the insertion location of the attraction; for each attraction, calculate the insertion ratio of the attraction based on the preference score and the minimum insertion cost; use the highest The scenic spots corresponding to the insertion ratio are used as the scenic spots to be inserted.

Assume that the current route from the starting point location to the end location is: starting point location—>attraction 5—>end location.

Then for each scenic spot not covered by the current route: for scenic spot 1, scenic spot 2, scenic spot 3, scenic spot 4, scenic spot 6, scenic spot 7, scenic spot 8, scenic spot 9 and scenic spot 10, calculate the number of attractions inserted into the current route for each scenic spot. The time consumption between the starting point and attraction 5, and between the attraction 5 and the end location. According to the time consumption, the minimum insertion cost of the attraction is determined; the position between two adjacent attractions corresponding to the minimum insertion cost is used as the insertion location of the attraction.

In one embodiment of the present invention, the minimum time consumption corresponding to the attraction can be used as the minimum insertion cost of the attraction.

Illustratively, the above scenic spot 1 is also used as an example for explanation.

The corresponding time consumption between the starting point of attraction 1 and attraction 5 is 25 minutes; the corresponding time consumption of attraction 1 between the insertion of attraction 5 and the end position is 10 minutes. Then the minimum time consumption is 10 minutes, and 10 minutes is determined as the minimum insertion cost of attraction 1.

In one embodiment of the present invention, determining the minimum insertion cost of the scenic spot based on time consumption may include: if the scenic spot is located in the same scenic spot cluster as the previous scenic spot and/or the latter scenic spot among the two adjacent scenic spots, the minimum insertion cost The ratio of time consumption to the attraction cluster parameter value corresponding to the attraction cluster is used as the minimum insertion cost of the attraction; if the attraction is not located in the same attraction cluster as the previous attraction and the next attraction, the minimum time consumption is used as the minimum insertion cost of the attraction.

In one embodiment of the present invention, scenic spots can be clustered to form multiple scenic spot clusters. Attractions belonging to the same attraction cluster are relatively close to each other. The embodiments of the present invention do not limit the algorithm for clustering scenic spots. Any available clustering algorithm can be applied to the embodiments of the present invention, such as the K-means algorithm.

The minimum insertion cost formula provided by the embodiment of the present invention is as follows:

If the attraction is located in the same attraction cluster as the previous attraction and/or the latter attraction among the two adjacent attractions,

If the attraction is not located in the same attraction cluster as the previous attraction and the next attraction,

shiftCluster _p = shift _p (2)

Among them, in formula (1) and formula (2), shiftCluster _p is the minimum insertion cost of attraction P, shift _p is the minimum time consumption of attraction P, and ClusterParamter _P is the attraction cluster parameter. Among them, ClusterParamter _P is greater than 1.

The insertion ratio formula provided by the embodiment of the present invention is as follows:

Among them, ratio _p is the insertion ratio of attraction P, profit _p is the user's preference score for attraction P, and shiftCluster _p is the minimum insertion cost of attraction P.

The attraction to be inserted and the insertion position of the attraction to be inserted are determined through the above formulas (1), (2) and (3).

By clustering scenic spots, the embodiment of the present invention will give priority to inserting other scenic spots located in the same scenic spot cluster when inserting scenic spots, which can reduce the time consumption of the route on the itinerary and can also reduce the transfer of users between scenic spot clusters. frequency.

Usually, attractions have their own corresponding opening hours and closing times, that is, the time window corresponding to the attraction. For example, for attraction 1, its opening hours are: 10:00 am to 13:00 pm. Therefore, in one embodiment of the present invention, the route planning method provided by the embodiment of the present invention may also include: for each scenic spot covered by the first target route, determine the user's target for the scenic spot based on the duration and starting time of the user browsing the scenic spot. Whether the tour meets the requirements of the opening time and closing time of the scenic spot; if for each scenic spot covered by the first target route, it is determined that the user's tour of the scenic spot meets the requirements of the opening time and closing time of the scenic spot, the attraction to be inserted will be inserted Insert position.

For example, it is assumed that the user's departure time from the starting point is 9:00 am. The current route is: starting point location—>attraction 5—>end location. The scenic spot to be inserted is scenic spot 1, and the location to be inserted is: between the starting point position and scenic spot 5. Then the first target route is: starting point location—>attraction 1—>attraction 5—>end location.

The duration from the starting point to attraction 1 is 25 minutes, and the tour time to attraction 1 is 35 minutes. The tour time from Attraction 1 to Attraction 5 is 35 minutes, and the tour time of Attraction 5 is 20 minutes. Then the time when the user arrives at attraction 1 is 9:25, and the estimated departure time from attraction 1 is 10:00. The time when the user arrives at attraction 5 is 10:35, and the time when the user departs from attraction 5 is 10:50.

Assume that the opening hours of attractions 1 and 5 are both 9:00 am and the closing time is 13:00 pm.

For attraction 1, it is determined that the user's tour of attraction 1 meets the requirements of the opening time and closing time of attraction 1.

For the scenic spot 5, it is determined that the user's tour of the scenic spot 5 meets the requirements of the opening time and closing time of the scenic spot 5.

Then insert attraction 1 between the starting point position and attraction 5. The current route is: starting point location—>attraction 1—>attraction 5—>end location.

Assume that the opening time of attraction 1 is 9:00 am and the closing time is 9:30 am. Attraction 5 opens at 9:00 am and closes at 13:00 pm.

The user's estimated departure time of 10:00 from attraction 1 has exceeded the closing time of attraction 1. Therefore, it is determined that the user's tour of attraction 1 does not meet the opening and closing time requirements of attraction 1. Then attraction 1 is not inserted.

Assume that the opening time of attraction 1 is 9:00 am and the closing time is 13:00 pm. Attraction 5 opens at 8:40am and closes at 9:40am.

The user's expected departure time from attraction 5 at 9:50 has exceeded the closing time of attraction 5. Therefore, it is determined that the user's tour of attraction 5 does not meet the opening and closing time requirements of attraction 5. Then attraction 1 is not inserted.

As another example, assume that the opening time of attraction 1 is 9:30 am and the closing time is 12:30 am. Attraction 5 opens at 9:00 am and closes at 13:00 pm.

The user arrived at attraction 1 at 9:25 and did not arrive at the opening time of attraction 1. At this point, the user can wait for 5 minutes. The user's expected departure time from attraction 1 changes to 10:05. The user's arrival time at attraction 5 becomes 10:40, and the departure time from attraction 5 is 10:55.

For attraction 1, it is determined that the user's tour of attraction 1 meets the requirements of the opening time and closing time of attraction 1.

For the scenic spot 5, it is determined that the user's tour of the scenic spot 5 meets the requirements of the opening time and closing time of the scenic spot 5.

Then insert attraction 1 between the starting point position and attraction 5. The current route is: starting point location—>attraction 1—>attraction 5—>end location.

In other words, the conditions for inserting scenic spots are: the total tour time of the route after inserting the scenic spots is less than the total tour time set by the user, and each scenic spot covered by the route after inserting the scenic spots meets their respective opening and closing time requirements, that is, the user You must leave before the attraction closes.

In one embodiment of the present invention, the route planning method provided by the embodiment of the present invention may further include: optimizing the planned route. The specific optimization process is shown in Figure 4. Figure 4 shows a schematic flowchart of route optimization provided by an embodiment of the present invention.

S401: Use the planned route as the intermediate planned route.

S402: Compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route with the preset maximum number of iterations without improvement.

S403: If the number is equal to the maximum number of iterations, determine the intermediate planned route as the final planned route.

S404: If the number of times is less than the maximum number of iterations, delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route to obtain the second target route, and add 1 to the number of times.

S405: According to the preference score, determine the scenic spots to be inserted and the insertion positions of the scenic spots to be inserted for the second target route from the scenic spots not covered by the second target route.

S406: Calculate the tour duration corresponding to the third target route after inserting the scenic spot to be inserted into the insertion position.

S407: If the tour duration is not greater than the total tour duration, insert the attraction to be inserted into the insertion position and continue to execute S405.

S408: If the tour duration is greater than the total tour duration, compare the first total preference score of the attractions covered by the current route with the second total preference score of the attractions covered by the intermediate planned route. If the first total preference score is not greater than the second total preference score, continue to execute S402.

S409: If the first total preference score is greater than the second total preference score, use the current route as the intermediate planned route and clear the times to zero; continue to execute S402.

S410: If the first total preference score is equal to the second total preference score, compare the first total tour time corresponding to the current route and the second total tour time corresponding to the intermediate planned route.

S411: If the total duration of the first tour is not greater than the total duration of the second tour, use the current route as the intermediate planned route and clear the times to zero; continue to execute S402.

S412: If the total duration of the first tour is greater than the total duration of the second tour, continue to execute S402.

In one embodiment of the present invention, a preset number of scenic spots are deleted from the scenic spots covered by the intermediate planned route, and a preset number of consecutive scenic spots can be deleted from the scenic spots covered by the intermediate planned route. At this time, you can specify the starting attraction and number of attractions to delete, and delete attractions continuously from the specified starting attraction.

In one embodiment of the present invention, to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route, you can start from the first scenic spot at the starting point position, then delete M consecutive scenic spots, and then delete the M scenic spots before the end position. Starting from the first scenic spot, delete consecutive N scenic spots forward so that the sum of M and N is equal to the preset number.

In one embodiment of the present invention, a preset number of scenic spots are deleted from the scenic spots covered by the intermediate planned route, and one scenic spot can also be deleted every other scenic spot. If the number of deleted scenic spots is less than the preset number, then the scenic spots obtained after deletion will be deleted. During the route, one attraction is deleted every other attraction until the total number of deleted attractions reaches the preset number.

The route optimization process is explained in detail below with a specific example.

Assume that the planned route is the starting point location -> Attraction 1 -> Attraction 5 -> Ending location, the tour duration corresponding to the planned route is 155 minutes, and the total preference score of the attractions covered by the planned route is 10 points. The preset total tour duration is 160 minutes. The initial value of the number of deletions for deleting a preset number of scenic spots from the scenic spots covered by the intermediate planned route is 0, and the default maximum number of iterations without improvement is 200.

First, the planned route: starting point location—>attraction 1—>attraction 5—>end location is used as the intermediate planned route.

At this time, if the number of deletions 0 is less than the maximum number of iterations 200, then the scenic spots will be deleted from the intermediate planned route: starting point position -> scenic spot 1 -> scenic spot 5 -> end position. Add 1 to the number of deletions. At this time, the number of deletions = 1.

Scenic spots are inserted into the route after the scenic spots are deleted, where the scenic spot insertion process is basically the same as the above-mentioned scenic spot insertion process, and will not be described in detail here in the embodiment of the present invention.

Assume that the current route after deleting and inserting attractions is: starting point location—>attraction 1—>attraction 4—>end location. The tour duration corresponding to the current route is 155 minutes, and the total preference score of the covered attractions is 13 points. . The total preference score of the scenic spots covered by the current route is 13 points, which is greater than the total preference score of the scenic spots covered by the intermediate planned route, which is 10 points. Then the current route: starting point location -> Attraction 1 -> Attraction 4 -> Ending location will be used as the intermediate planned route, and the number of deletions will be cleared.

At this time, if the number of deletions 0 is less than the maximum number of iterations 200, then the scenic spots will be deleted from the intermediate planned route: starting point position -> scenic spot 1 -> scenic spot 4 -> end position. Add 1 to the number of deletions. At this time, the number of deletions = 1.

Insert scenic spots into the route after deleting the scenic spots. Assume that the current route after deleting and inserting attractions is: starting point location—>attraction 2—>attraction 3—>end location. The tour duration corresponding to the current route is 145 minutes, and the total preference score of the covered attractions is 13 points. . The total preference score of 13 points for the attractions covered by the current route is equal to the preference score of 13 points for the attractions covered by the intermediate planned route, but the tour duration of 145 minutes corresponding to the current route is shorter than the 145 minutes of tour duration corresponding to the intermediate planned route. Then the current route: starting point location -> Attraction 2 -> Attraction 3 -> Ending location will be used as the intermediate planned route, and the number of deletions will be cleared.

At this time, if the number of deletions 0 is less than the maximum number of iterations 200, then the scenic spots will be deleted from the intermediate planned route: starting point location—>attraction 2—>attraction 3—>end location. Add 1 to the number of deletions. At this time, the number of deletions = 1.

Insert scenic spots into the route after deleting the scenic spots. Assume that the current route after deleting and inserting attractions is: starting point location—>attraction 1—>attraction 7—>end location. The tour duration corresponding to the current route is 150 minutes, and the preference score of the covered attractions is 13 points. The total preference score of 13 points for the scenic spots covered by the current route is equal to the preference score of 13 points for the scenic spots covered by the intermediate planned route, but the tour time corresponding to the current route of 150 minutes is greater than the tour time of 145 minutes corresponding to the intermediate planned route. . Then the intermediate planned route remains unchanged and is: starting point location—>attraction 2—>attraction 3—>end location.

At this time, if the number of deletions 1 is less than the maximum number of iterations 200, then the scenic spots will be deleted from the intermediate planned route: starting point location—>attraction 2—>attraction 3—>end location. Add 1 to the number of deletions. At this time, the number of deletions = 2.

Insert scenic spots into the route after deleting the scenic spots. Assume that the current route after deleting and inserting attractions is: starting point location—>attraction 2—>attraction 5—>end location. The tour duration corresponding to the current route is 145 minutes, and the preference score of the covered attractions is 12 points. The tour duration of 145 minutes corresponding to the current route is equal to the tour duration of 145 minutes corresponding to the intermediate planned route, but the preference score of the attractions covered by the current route of 12 points is smaller than the preference score of the attractions covered by the intermediate planned route of 13 points. Then the intermediate planned route remains unchanged and is: starting point location—>attraction 2—>attraction 3—>end location.

At this time, if the number of deletions 2 is less than the maximum number of iterations 200, then the scenic spots will be deleted from the intermediate planned route: starting point location—>attraction 2—>attraction 3—>end location. Add 1 to the number of deletions. At this time, the number of deletions = 3. Insert scenic spots into the route after deleting the scenic spots.

If the number of deletions is equal to the maximum number of iterations 200, the intermediate planned route is determined as the final planned route.

For example, assume that for the intermediate planned route: starting point location—>attraction 2—>attraction 3—>end location. The number of deletions has reached 200 times. It is understandable that when the number of deletions reaches 200 times, the total tour time of the route after each deletion and insertion of an attraction is not less than the total tour time corresponding to the intermediate planned route, and each deletion and insertion The total preference score of the scenic spots covered by the route after the scenic spot is not greater than the total preference score of the scenic spots covered by the intermediate planned route. At this time, the intermediate planned route will be: starting point location -> scenic spot 2 -> scenic spot 3 -> The final location is determined as the final planned route.

In one embodiment of the present invention, in the process of optimizing the route using the above process, the scenic spot cluster parameters used to calculate the minimum insertion cost of the scenic spot can be reduced every time 1/4 of the maximum number of iterations is passed. For example, assume that the initial value of the attraction cluster parameter ClusterParamter is 1.2. When the number of deletions = 50, reduce the attraction cluster parameter ClusterParamter by 0.1. At this time, ClusterParamter = 1.1. When the number of deletions = 100, reduce the attraction cluster parameter ClusterPa by 0.1. At this time, ClusterParamter = 1. When the number of deletions = 150, reduce the attraction cluster parameter ClusterParamter by 0.1. At this time, ClusterParamter = 0.9.

In other words, the optimized route needs to satisfy the following condition 1 or condition 2.

Condition 1: The total preference score of the scenic spots covered by the optimized route is higher than the total preference score of the scenic spots covered by the pre-optimized route.

Condition 2: The total preference score of the scenic spots covered by the optimized route is equal to the total preference score of the scenic spots covered by the pre-optimized route. However, the total tour duration corresponding to the optimized route is shorter than the total tour duration corresponding to the route before optimization.

It should be noted that the premise of Condition 1 and Condition 2 is that the total tour duration corresponding to the optimized route is shorter than the tour duration set by the user.

Figure 5 shows a schematic diagram of the route planning results provided by the embodiment of the present invention.

Figure 6 shows a comparison diagram of the total duration of the route planned by the embodiment of the present invention and the total duration of the route planned by the prior art. It can be seen from Figure 6 that when the total tour duration set by the user is short, the total duration of the route planned by the embodiment of the present invention is basically the same as the total duration of the route planned by the prior art. When the total duration of the tour set by the user is long, the total duration of the route planned by the embodiment of the present invention is shorter than the total duration of the route planned by the prior art, which can save the user's tour time. Under normal circumstances, the time required to visit a scenic spot is basically more than two and a half hours. What's more, some scenic spots require at least 4 or 5 hours to visit, such as the Summer Palace and Chengde Summer Resort, etc.

FIG. 7 shows a comparison of the time it takes to plan a route according to the embodiment of the present invention and the time it takes to plan a route using the prior art. It can be seen from Figure 7 that the time taken to plan a route according to the embodiment of the present invention is about 1000 milliseconds (1 second) different from the time taken to plan a route using the prior art, which is acceptable to users.

It should be noted that the above description using 10 scenic spots as examples is only a specific example of the present invention and does not constitute a limitation of the present invention.

The route planning method of the embodiment of the present invention performs route planning based on the user's preference score for scenic spots, so that the planned route can meet the user's preference requirements.

Corresponding to the above method embodiments, embodiments of the present invention also provide a route planning device. As shown in FIG. 8 , FIG. 8 shows a schematic structural diagram of a route planning device provided by an embodiment of the present invention. Route planning devices may include:

The obtaining module 801 is used to obtain the user's starting point location, end point location, total tour time, and the user's preference score for each scenic spot.

The first determination module 802 is used to determine the scenic spots to be inserted and the insertion positions of the scenic spots to be inserted in the current route from the scenic spots not covered by the current route from the starting point position to the end position according to the preference score.

The calculation module 803 is used to calculate the tour duration corresponding to the first target route after inserting the scenic spot to be inserted into the insertion position.

The insertion module 804 is used to insert the attraction to be inserted into the insertion position if the tour duration is not greater than the total tour duration; and trigger the first determination module 802.

The second determination module 805 is used to determine the current route as the planned route if the tour duration is greater than the total tour duration.

In one embodiment of the present invention, the first determination module 802 includes:

An insertion position determination unit is used to calculate, for each scenic spot not covered by the current route from the starting point position to the end position, the corresponding time consumption between two adjacent scenic spots inserted into the current route; according to Time consumption, determine the minimum insertion cost of the attraction; use the position between two adjacent attractions corresponding to the minimum insertion cost as the insertion location of the attraction;

The scenic spot determination unit to be inserted is used to calculate the insertion ratio of the scenic spot according to the preference score and the minimum insertion cost for each scenic spot; the scenic spot corresponding to the highest insertion rate is used as the scenic spot to be inserted.

In one embodiment of the present invention, the position determination unit is inserted, specifically for:

If an attraction is located in the same attraction cluster as the previous and/or next attraction among two adjacent attractions, the ratio of the minimum time consumption to the attraction cluster parameter value corresponding to the attraction cluster will be used as the minimum insertion cost of the attraction;

If the attraction is not located in the same attraction cluster as the previous attraction or the next attraction, the minimum time consumption will be used as the minimum insertion cost of the attraction.

In one embodiment of the present invention, the route planning device provided by the embodiment of the present invention further includes:

The third determination module is used to determine, for each scenic spot covered by the first target route, whether the user's tour of the scenic spot meets the requirements of the opening time and closing time of the scenic spot based on the duration and starting time of the user's browsing of the scenic spot; For each scenic spot covered by a target route, it is determined that the user's visit to the scenic spot meets the opening time and closing time requirements of the scenic spot, and the insertion module is triggered.

In one embodiment of the present invention, the route planning device provided by the embodiment of the present invention further includes:

Route optimization module, used to use the planned route as an intermediate planned route;

Compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route with the preset maximum number of iterations without improvement;

If the number is equal to the maximum number of iterations, the intermediate planned route is determined as the final planned route;

If the number is less than the maximum number of iterations, delete the preset number of scenic spots from the scenic spots covered by the intermediate planned route to obtain the second target route, and add 1 to the number;

According to the preference score, determine the scenic spots to be inserted and the insertion positions of the scenic spots to be inserted for the second target route from the scenic spots not covered by the second target route;

Calculate the tour duration corresponding to the third target route after inserting the attraction to be inserted into the insertion position;

If the tour duration is not greater than the total tour duration, the attractions to be inserted will be inserted into the insertion position;

Return the preference score, determine the attractions to be inserted from the attractions not covered by the second target route, and continue to perform the insertion position of the attractions to be inserted for the second target route until the tour duration is greater than the total tour duration;

Compare the first overall preference score of the attractions covered by the current route with the second overall preference score of the attractions covered by the intermediate planned route;

If the first total preference score is greater than the second total preference score, the current route will be used as the intermediate planned route and the number of times will be cleared; return to compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route. Continue execution with the preset maximum number of iterations line without improvement;

If the first total preference score is equal to the second total preference score, compare the first total tour time corresponding to the current route and the second total tour time corresponding to the intermediate planned route;

If the total duration of the first tour is not greater than the total duration of the second tour, the current route will be used as the intermediate planned route and the number of times will be cleared to zero; return to compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route with the default Execution continues for the maximum number of iterations without improvement;

If the total duration of the first tour is greater than the total duration of the second tour, then return to compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route with the preset maximum number of iterations without improvement and continue execution;

If the first total preference score is not greater than the second total preference score, then return to compare the number of times to delete a preset number of scenic spots from the scenic spots covered by the intermediate planned route with the preset maximum number of iterations without improvement and continue execution.

The route planning device in the embodiment of the present invention performs route planning according to the user's preference score for scenic spots, so that the planned route can meet the user's preference requirements.

FIG. 9 shows a structural diagram of an exemplary hardware architecture of a computing device capable of implementing the route planning method and apparatus according to embodiments of the present invention. As shown in FIG. 9 , computing device 900 includes an input device 901 , an input interface 902 , a central processing unit 903 , a memory 904 , an output interface 905 , and an output device 906 . Among them, the input interface 902, the central processing unit 903, the memory 25 904, and the output interface 905 are connected to each other through the bus 910. The input device 901 and the output device 906 are connected to the bus 910 through the input interface 902 and the output interface 905 respectively, and then to the computing device. 900's other components are connected.

Specifically, the input device 901 receives input information from the outside and transmits the input information to the central processor 903 through the input interface 902; the central processor 903 processes the input information based on computer-executable instructions stored in the memory 904 to generate output. Information, the output information is temporarily or permanently stored in the memory 904, and then the output information is transmitted to the output device 906 through the output interface 905; the output device 906 outputs the output information to the outside of the computing device 900 for use by the user.

That is to say, the computing device shown in Figure 9 can also be implemented as a route planning device. The route planning device can include: a memory storing computer-executable instructions; and a processor, which when executing the computer-executable instructions The route planning method and device described in conjunction with Figures 2 and 8 can be implemented.

Embodiments of the present invention also provide a computer-readable storage medium. Computer program instructions are stored on the computer-readable storage medium; when the computer program instructions are executed by a processor, the route planning method provided by the embodiment of the present invention is implemented.

It is to be understood that this invention is not limited to the specific arrangements and processes described above and illustrated in the drawings. For the sake of brevity, detailed descriptions of known methods are omitted here. In the above embodiments, several specific steps are described and shown as examples. However, the method process of the present invention is not limited to the specific steps described and shown. Those skilled in the art can make various changes, modifications and additions, or change the order between steps after understanding the spirit of the present invention.

The functional blocks shown in the above structural block diagram can be implemented as hardware, software, firmware or a combination thereof. When implemented in hardware, it may be, for example, an electronic circuit, an application specific integrated circuit (ASIC), appropriate firmware, a plug-in, a function card, or the like. When implemented in software, elements of the invention are programs or code segments used to perform the required tasks. The program or code segments may be stored in a machine-readable medium or transmitted over a transmission medium or communications link via a data signal carried in a carrier wave. "Machine-readable medium" may include any medium capable of storing or transmitting information. Examples of machine-readable media include electronic circuits, semiconductor memory devices, ROM, flash memory, erasable ROM (EROM), floppy disks, CD-ROMs, optical disks, hard disks, fiber optic media, radio frequency (RF) links, and the like. Code segments may be downloaded via computer networks such as the Internet, intranets, and the like.

It should also be noted that the exemplary embodiments mentioned in the present invention describe some methods or systems based on a series of steps or devices. However, the present invention is not limited to the order of the above steps. That is to say, the steps may be performed in the order mentioned in the embodiments, or may be different from the order in the embodiments, or several steps may be performed simultaneously.

The above are only specific implementations of the present invention. Those skilled in the art can clearly understand that for the convenience and simplicity of description, the specific working processes of the above-described systems, modules and units can be referred to the foregoing method embodiments. The corresponding process will not be described again here. It should be understood that the protection scope of the present invention is not limited thereto. Any person familiar with the technical field can easily think of various equivalent modifications or substitutions within the technical scope disclosed in the present invention, and these modifications or substitutions should be covered. within the protection scope of the present invention.

Claims (8)

1. A method of route planning, the method comprising:

obtaining a starting point position, an end point position, a total tour duration of a user and preference degree scores of the user for each scenic spot;

determining scenery points to be inserted and the insertion positions of the scenery points to be inserted in the current route from the starting point position to the end point position according to the preference degree score;

calculating the tour time length corresponding to the first target route after the scenic spot to be inserted is inserted into the insertion position;

If the tour time is not longer than the tour total time, inserting the scenic spot to be inserted into the insertion position;

returning the preference degree score, and determining scenic spots to be inserted and the scenic spot to be inserted to be continuously executed for the insertion position in the current route from the starting point position to the end point position in scenic spots which are not covered by the current route;

if the tour time length is greater than the tour total time length, determining the current route as a planned route;

the determining, according to the preference degree score, the scenic spot to be inserted and the insertion position of the scenic spot to be inserted in the current route from the starting point position to the end point position, wherein the scenic spot is not covered by the current route, includes:

for each of the attractions not covered by the current route from the starting point location to the ending point location, calculating a corresponding time consumption between insertion of the attraction into two neighboring attractions in the current route; determining a minimum insertion cost of the attraction according to the time consumption; taking the position between two adjacent scenic spots corresponding to the minimum insertion cost as the insertion position of the scenic spot;

Calculating the insertion ratio of each scenic spot according to the preference degree score and the minimum insertion cost; taking the scenic spot corresponding to the highest insertion rate as the scenic spot to be inserted;

the insertion ratio is expressed as follows:

wherein the ratio _p For the insertion ratio, profit _p For the preference degree score, a shiftCluster _p For the minimum insertion cost;

the determining the minimum insertion cost of the scenic spot according to the time consumption comprises the following steps:

if the scenic spot and the former scenic spot and/or the latter scenic spot in the two adjacent scenic spots are/is located in the same scenic spot cluster, the ratio of the scenic spot cluster parameter values corresponding to the scenic spot cluster with the minimum time consumption is used as the minimum insertion cost of the scenic spot;

and if the scenic spot is not located in the same scenic spot cluster with the previous scenic spot and the next scenic spot, the minimum time consumption is used as the minimum insertion cost of the scenic spot.

2. The method of claim 1, wherein prior to said inserting the point of interest to be inserted into the insertion location, the method further comprises:

for each scenic spot covered by the first target route, determining whether the tour of the scenic spot by the user meets the requirements of the opening time and the closing time of the scenic spot according to the duration and the starting time of the user for browsing the scenic spot; and if each scenic spot covered by the first target route is determined that the tour of the scenic spot by the user meets the requirements of the opening time and the closing time of the scenic spot, inserting the scenic spot to be inserted into the insertion position.

3. The method according to claim 1, wherein the method further comprises:

taking the planned route as an intermediate planned route;

comparing the number of times of deleting a preset number of scenic spots from scenic spots covered by the intermediate planning route with the preset maximum iteration number without improvement;

if the number of times is equal to the maximum iteration number, determining the intermediate planned route as a final planned route;

if the number of times is smaller than the maximum iteration number, deleting a preset number of scenic spots from scenic spots covered by the intermediate planning route to obtain a second target route, and adding 1 to the number of times;

determining scenery points to be inserted and the insertion positions of the scenery points to be inserted to the second target route from scenery points which are not covered by the second target route according to the preference degree scores;

calculating the tour time length corresponding to the third target route after the scenic spot to be inserted is inserted into the insertion position;

if the tour time is not longer than the tour total time, inserting the scenic spot to be inserted into the insertion position;

returning the score according to the preference degree, and determining scenic spots to be inserted from scenic spots which are not covered by the second target route and the insertion positions of the scenic spots to be inserted to the second target route to continue execution until the tour time is longer than the tour total time;

Comparing the first total preference degree score of the scenic spots covered by the current route with the second total preference degree score of the scenic spots covered by the middle planning route;

if the first total preference degree score is larger than the second total preference degree score, taking the current route as the middle planning route, and clearing the times; returning to the comparison, and continuously executing the times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and a preset maximum iteration time line without improvement;

if the first total preference degree score is equal to the second total preference degree score, comparing a first total tour duration corresponding to the current route with a second total tour duration corresponding to the intermediate planning route;

if the first total tour duration is not greater than the second total tour duration, taking the current route as the intermediate planning route, and clearing the times; returning to the comparison, and continuously executing the times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration times without improvement;

if the first total time length of the tour is longer than the second total time length of the tour, returning to the comparison, and continuously executing the comparison of the number of times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration number without improvement;

And if the first total preference degree score is not greater than the second total preference degree score, returning to the comparison, and continuing to execute the comparison of the number of times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration number without improvement.

4. A path planning apparatus, the apparatus comprising:

the acquisition module is used for acquiring the starting point position, the end point position, the total tour duration and the preference degree score of the user for each scenic spot;

the first determining module is used for determining scenery spots to be inserted and the insertion positions of the scenery spots to be inserted in the current route from the starting point position to the end point position according to the preference degree score;

the calculation module is used for calculating the tour time length corresponding to the first target route after the scenic spot to be inserted is inserted into the insertion position;

the inserting module is used for inserting the scenic spot to be inserted into the inserting position if the tour time is not greater than the tour total time; triggering the first determining module;

the second determining module is used for determining the current route as a planned route if the tour time length is greater than the tour total time length;

The first determining module includes:

an insertion position determining unit configured to calculate, for each of the attractions not covered by the current route from the start point position to the end point position, a corresponding time consumption between two neighboring attractions of the attraction insertion in the current route; determining a minimum insertion cost of the attraction according to the time consumption; taking the position between two adjacent scenic spots corresponding to the minimum insertion cost as the insertion position of the scenic spot;

a to-be-inserted scenic spot determining unit, configured to calculate, for each scenic spot, an insertion ratio of the scenic spot according to the preference degree score and the minimum insertion cost; taking the scenic spot corresponding to the highest insertion rate as the scenic spot to be inserted; the insertion ratio is expressed as follows:

wherein the ratio _p For the insertion ratio, profit _p For the preference degree score, a shiftCluster _p For the minimum insertion cost;

the insertion position determining unit is specifically configured to:

if the scenic spot and the former scenic spot and/or the latter scenic spot in the two adjacent scenic spots are/is located in the same scenic spot cluster, the ratio of the scenic spot cluster parameter values corresponding to the scenic spot cluster with the minimum time consumption is used as the minimum insertion cost of the scenic spot;

And if the scenic spot is not located in the same scenic spot cluster with the previous scenic spot and the next scenic spot, the minimum time consumption is used as the minimum insertion cost of the scenic spot.

5. The apparatus of claim 4, wherein the apparatus further comprises:

the third determining module is used for determining whether the tour of the scenic spot by the user meets the requirements of the opening time and the closing time of the scenic spot according to the duration and the starting time of the user for browsing the scenic spot for each scenic spot covered by the first target route; and if each scenic spot covered by the first target route is aimed at, determining that the requirement of the opening time and the closing time of the scenic spot is met by the user for the sightseeing of the scenic spot, and triggering an inserting module.

6. The apparatus of claim 4, wherein the apparatus further comprises:

the route optimization module is used for taking the planned route as an intermediate planned route;

comparing the number of times of deleting a preset number of scenic spots from scenic spots covered by the intermediate planning route with the preset maximum iteration number without improvement;

if the number of times is equal to the maximum iteration number, determining the intermediate planned route as a final planned route;

If the number of times is smaller than the maximum iteration number, deleting a preset number of scenic spots from scenic spots covered by the intermediate planning route to obtain a second target route, and adding 1 to the number of times;

determining scenery points to be inserted and the insertion positions of the scenery points to be inserted to the second target route from scenery points which are not covered by the second target route according to the preference degree scores;

calculating the tour time length corresponding to the third target route after the scenic spot to be inserted is inserted into the insertion position;

if the tour time is not longer than the tour total time, inserting the scenic spot to be inserted into the insertion position;

returning the score according to the preference degree, and determining scenic spots to be inserted from scenic spots which are not covered by the second target route and the insertion positions of the scenic spots to be inserted to the second target route to continue execution until the tour time is longer than the tour total time;

comparing the first total preference degree score of the scenic spots covered by the current route with the second total preference degree score of the scenic spots covered by the middle planning route;

if the first total preference degree score is larger than the second total preference degree score, taking the current route as the middle planning route, and clearing the times; returning to the comparison, and continuously executing the times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and a preset maximum iteration time line without improvement;

If the first total preference degree score is equal to the second total preference degree score, comparing a first total tour duration corresponding to the current route with a second total tour duration corresponding to the intermediate planning route;

if the first total tour duration is not greater than the second total tour duration, taking the current route as the intermediate planning route, and clearing the times; returning to the comparison, and continuously executing the times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration times without improvement;

if the first total time length of the tour is longer than the second total time length of the tour, returning to the comparison, and continuously executing the comparison of the number of times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration number without improvement;

and if the first total preference degree score is not greater than the second total preference degree score, returning to the comparison, and continuing to execute the comparison of the number of times of deleting the preset number of scenic spots from scenic spots covered by the intermediate planning route and the preset maximum iteration number without improvement.

7. A route planning device, the device comprising: a memory, a processor, and a computer program stored on the memory and executable on the processor;

A route planning method according to any one of claims 1 to 3 when the processor executes the computer program.

8. A computer readable storage medium, characterized in that the computer readable storage medium has stored thereon a computer program which, when executed by a processor, implements a route planning method according to any of claims 1 to 3.