Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Journey planning method based on graph clustering and iterative local search

A technology of iterative local search and itinerary planning, applied to computer components, instruments, characters and pattern recognition, etc., can solve the problem of long traffic transfer time, improve accuracy, reduce complexity and calculation time, and improve speed The effect of stickiness and accuracy

Pending Publication Date: 2021-02-26
NORTHEASTERN UNIV
View PDF0 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

Vansteenwegen P et al. proposed the Iterated Local Search (ILS) algorithm to solve the orientation problem with a time window. This algorithm can calculate a better route in a short time, but the planned route There is still the disadvantage of a long time for transportation transfer between attractions

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Journey planning method based on graph clustering and iterative local search
  • Journey planning method based on graph clustering and iterative local search
  • Journey planning method based on graph clustering and iterative local search

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0026] The method of the present invention will be further described below in conjunction with the accompanying drawings and specific embodiments.

[0027] like figure 1 As shown, the itinerary planning method based on graph clustering and iterative local search of the present invention is carried out according to the following steps:

[0028] Step 1: In the offline stage, all POI points are regarded as nodes, and if there is correlation between any two nodes, an edge is established to construct a graph structure. The information content of the nodes is shown in Table 1. The structure of the node information data is divided into location name, latitude and longitude, and rating. These information are the information that needs to be obtained in advance before the specific implementation, and provide data information for the planning method. similarity relationship such as figure 2 As shown, the September 18th History Museum and the Liaoning Provincial Museum are both museum...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

A journey planning method based on graph clustering and iterative local search belongs to the field of journey planning, and comprises the following steps of: performing graph clustering before a journey planning task, constructing a graph by using position information and similarity information of all scenic spots through a graph clustering method, fusing the position and similarity information of each node. The complexity and the calculation time of an iterative local search algorithm are reduced, and compared with a common kmeans clustering algorithm, the clustering effect can be better, and the accuracy of travel planning is improved. Through an iterative local search algorithm, when a high POI point is encountered in a cluster of a POI point sparse graph, the situation that the POI point is trapped in the cluster can be avoided, so that a journey planning function can be realized, and the robustness and accuracy of journey planning are improved.

Description

technical field [0001] The invention belongs to the field of travel planning, in particular to a travel planning method based on graph clustering and iterative local search. Background technique [0002] Travel itinerary planning is one of the common problems in TDP (Trip Design Problems, itinerary planning problem). Too long question. The problem of travel itinerary planning is defined as: knowing the location information of all scenic spots, setting a starting travel location, and calculating the minimum time spent visiting all scenic spots. The main reasons for the excessive time loss of the entire travel itinerary are as follows: 1) In the real situation, there will be high-scoring POIs, but this area is a sparse POI area; 2) Because of the high-scoring POI points, there will be priority Therefore, when planning, priority will be given to visiting high-scoring POI points without considering the entire traffic transfer time and the number of regional transfers, resultin...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06Q10/04G06K9/62
CPCG06Q10/047G06F18/2323G06F18/22G06F18/2453
Inventor 于瑞云韩柏周伟航苏鹏
Owner NORTHEASTERN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com