Route planning method and device for navigation system and storage medium

0001The present invention relates to fields spanning intelligent traffic, vehicle networks, location-based services (LBS) and mobile communications, and particularly to methods of route planning for navigation systems, devices and computer storage media.

0002With the development of car networks and mobile communication technology, the demand for city management is increasing day by day, and the navigation technology is also developing. Early route planning methods are based primarily on static Geographic Information System (GIS) maps, using methods such as dynamic planning to calculate routes and are highly dependent on maps. Map surveying, drafting, and publishing require a period of time, so map information is always delayed from the actual situation, and the actual traffic situation is affected by various outbreaks, so the navigation route is accurate. Affects sex and effectiveness. Combining GIS maps with actual road conditions is gradually the direction of development of navigation technology.

0003Currently, road condition data is obtained from the following two data. One is the road condition data of the free Traffic Message Channel (TMC), and the other is the road condition data for commercial use. Here, TMC road condition data is announced by the traffic management department, and real-time data is mainly obtained from road monitoring and police dispatch records, which is good in real time, but it is covered because the TMC system is not set in a certain area. Area and amount of information are limited. Commercial road condition data is mainly obtained from Float Car Data (FCD) and generally collects road condition information through a device set up by a taxi company on a taxi, but commercial and technical. Currently, only a small number of city road condition information can be provided, and the time delay is large, so the real-time property is not good.

0004As described above, the current navigation technology has a problem that it cannot meet strict navigation requirements because the coverage range of road condition data is small and the real-time property is not good. The route planning method, which is entirely based on the GIS map, is larger than the desired route because it is difficult to guarantee the accuracy and effectiveness of the calculated navigation route if the map information is incorrect or the update is not timely. There may be errors and even the wrong route may be provided.

<p num="0005"> To solve existing technical problems, embodiments of the present invention provide navigation system route planning methods, devices and computer storage media that automatically sense actual traffic conditions within the relevant area in real time. Route planning and interactive navigation accurately and effectively in response to real-time changes in road conditions while driving.</p>

<p num="0006"> The technical proposal according to the embodiment of the present invention is realized as follows.</p><p num="0007"> An embodiment of the present invention provides a method of route planning for a navigation system. The actual geospatial space is gridded, the grid is a cell of the cellular network, the cell switching record of the mobile station is acquired, and the cell adjacency model based on the cell switching record of the mobile station. And to establish Corresponding the starting point and the destination in the actual geospatial space to the gridded starting grid and the target grid, respectively, and determining the grid level route from the starting grid to the target grid based on the adjacency model. , Includes transforming the grid-level route into an actual route from origin to destination in actual geospatial space.</p><p num="0008"> In the above-mentioned technical proposal, the method is performed before establishing the cell adjacency model based on the cell switching record of the mobile station. It further includes sorting the cell switching record of the mobile station according to a preset sorting plan.</p><p num="0009"> In the above-mentioned technical proposal, establishing a cell adjacency model based on the cell switching record of the mobile station is not possible. Extracting the movement locus of the mobile station based on the cell switching record of the mobile station, Taking a set of all the movement trajectories within a certain period of time as a snapshot, Includes establishing a cell adjacency model within the time period based on the snapshot.</p><p num="0010"> In the above-mentioned technical proposal, establishing an adjacency model of cells within the fixed time based on the snapshot is not possible. Based on the snapshot, including establishing a weighted directed graph with all cell base stations as vertices, cell-cell adjacencies as edges, and cell-cell adjacencies as edge weights. The adjacent value between cells is the probability of moving between two cells, or the time it takes to move between two cells.</p><p num="0011"> In the above-mentioned technical proposal, converting the grid level route into an actual route from a starting point to a destination in an actual geospatial space may be performed. Includes converting the grid-level route to an actual route from the origin to the destination in the GIS map and / or converting the grid-level route to the actual route from the origin to the destination in the satellite map.</p><p num="0012"> An embodiment of the present invention provides a route planning device for a navigation system, which comprises a grid model establishment module, a grid path search module, and a track conversion module. The grid model establishment module performs grid processing on the actual geospatial space, the grid is a cell of the cellular network, acquires the cell switching record of the mobile station, and is based on the cell switching record of the mobile station. , Configured to establish a cell adjacency model, The grid path search module maps the starting point and the destination in the actual geographical space to the gridded starting grid and the target grid, respectively, and based on the adjacency model, the grid level from the starting grid to the target grid. Configured to determine the route, The route conversion module is configured to convert the grid-level route into an actual route from a starting point to a destination in the actual geospatial space.</p><p num="0013"> In the above-mentioned technical plan, the lattice model establishment module is configured to perform sorting on the cell switching record of the mobile station according to a preset sorting plan.</p><p num="0014"> In the above-mentioned technical proposal, the lattice model establishment module is A locus extraction submodule for extracting the movement locus of the mobile station based on the cell switching record of the mobile station, and A snapshot management submodule for taking a set of all the movement trajectories within a certain period of time as a snapshot, It includes an establishment submodule for establishing an adjacency model of cells within a certain period of time based on a snapshot.</p><p num="0015"> In the above-mentioned technical proposal, the establishment submodule is Based on the snapshot, it is further configured to establish a weighted directed graph with all cell base stations as vertices, cell adjacencies as edges, and cell adjacency values as edge weights. The adjacent value between cells is the probability of moving between two cells, or the time it takes to move between two cells.</p><p num="0016"> In the above-mentioned technical proposal, the path conversion module is A GIS map matching submodule for converting the grid level route into an actual route from the origin to the destination in the GIS map, and / or It includes a satellite map matching submodule for converting the grid level route into an actual route from the starting point to the destination in the satellite map.</p><p num="0017"> An embodiment of the present invention provides a computer storage medium, which stores computer-executable instructions for performing the method of route planning of the navigation system.</p><p num="0018"> An embodiment of the present invention provides a method of route planning for a navigation system, a device, and a computer storage medium, the method performing a gridting process on the actual geographic space, where the grid is a cell of a cellular network. Yes, the cell switching record of the mobile station is acquired, the cell adjacency model is established based on the cell switching record of the mobile station, and the starting point and the destination in the actual geographical space are gridded. To determine the grid level route from the starting grid to the target grid based on the adjacency model, and to make the grid level route from the starting point in the actual geographical space to the purpose. Includes converting to an actual route to the ground. Utilizing embodiments of the present invention, it automatically senses actual traffic conditions in the relevant area, plans routes in real time, and interactively navigates in response to real-time changes in road conditions while driving. Can be done accurately and effectively.</p>

0019<figref num="1">It is a flowchart which realizes the method of the route planning of the navigation system by embodiment of this invention.</figref><figref num="2">It is a schematic diagram of the movement probability directed graph between base stations by one embodiment of the present invention.</figref><figref num="3">It is a schematic diagram of the travel time directed graph between base stations according to another embodiment of the present invention.</figref><figref num="4">It is a structural schematic diagram of the apparatus of the route planning of the navigation system by embodiment of this invention.</figref>

0020In order to clearly explain the embodiment and the technical proposal of the present invention, the technical proposal of the present invention will be described in detail below with reference to the drawings and the embodiments. Obviously, the following embodiments are part, but not all, of the embodiments of the present invention. All other embodiments acquired by those skilled in the art based on the embodiments of the present invention are included in the scope of protection of the present invention.

0021FIG. 1 is a flowchart that realizes a method of route planning for a navigation system according to an embodiment of the present invention, and as shown in FIG. 1, the method includes the following steps.

0022Step 101: Perform a grid processing on the actual geospatial space, the grid is a cell of the cellular network, obtain a cell switching record of the mobile station, and based on the cell switching record of the mobile station, the cell Establish an adjacency model.

0023Specifically, when the navigation system performs gridding processing on the actual geospatial space, the actual geospatial space is divided into a plurality of areas, and one area is regarded as one grid. Then, an adjacency model between each grid is established.

0024In one embodiment, the navigation system grids cells in a cellular network, divides them into actual geospatial space, and establishes a cell adjacency model. Here, the cell is a space covered by the antenna of the base station.

0025In the cellular network, the mobility management signal is a signal that manages the user position of the cellular network, and it is possible to acquire the movement trajectory information of various mobile stations from the mobility management signal, and the cell of the mobile station on the base station side. By observing the position change of, the cell switching record of the mobile station can be acquired, and the locus information of the moving object belonging to the mobile station moving between the lattices can be acquired.

0026Specifically, the signal collection platform of the mobile communication operator collects cell switching records of the mobile station from the base station controller via the Abis / Iub interface, and each record is "mobile station number, cell identifier, entry into cell". The cell switching records of all mobile stations recorded in the "time stamp" within a fixed time interval are stored in a specific storage space in the form of a file. Here, generally, the length of the fixed time interval is set to 15 minutes according to the processing capacity of the signal acquisition platform. The particular storage space may be the storage space in a dedicated file transmission protocol (FTP) server.

0027Other than that, with the spread of mobile smart terminals and mobile internet applications, software that calls taxis in particular has become widespread in the taxi industry, and mobile carriers have been able to obtain specific mobile stations, especially taxis, from the mobile station's net access records. It is possible to acquire the cell switching record in the mobile station of. Specifically, the mobile operator's signal collection platform has a "mobile station number" in the signal recording of the Package Switch (PS) domain, for example, the call recording generated by Deep Package Inspection (DPI). , Cell identifier, cell entry time stamp ", the cell switching record of the mobile station is extracted, and the cell switching record of all mobile stations within a certain time interval is specified in the form of a file. Store in storage space. Here, generally, the length of the fixed time interval is set to 15 minutes according to the processing capacity of the signal acquisition platform. The specific storage space may be the storage space in a dedicated FTP server.

0028In an embodiment of the invention, the mobile operator's signal acquisition platform provides a data basis for the navigation system to establish a cell-to-cell adjacency model based on the mobile station's cell switching records.

0029In one embodiment, the navigation system establishing a grid, i.e. establishing an adjacency model between the cells described above, comprises the following steps.

0030Step A: Get mobile station cell switching records on time.

0031Specifically, the navigation system reads the mobile station switching record file stored in the dedicated FTP server by the signal collection platform of the mobile communication operator on time, and reads the mobile station cell switching record file from the read mobile station switching record file. Acquire the cell switching record.

0032In order to effectively and accurately establish the cell adjacency, the navigation system can perform sorting on the cell switching record of the mobile station by a preset sorting plan. Here, the selection plan is as follows.

0033Sorting plan 1: The navigation system can sort based on the mobile station number.

0034It is possible to delete the related record of the mobile station number that is not mobile. When actually applied, some mobile stations are not mobile, for example, an intersection camera equipped with a user identification module SIM card, and its position does not change. However, the base station still receives the location information of the intersection camera on time, and the signal acquisition platform of the mobile operator also collects and stores the record of the intersection camera accordingly. For such a mobile station, the mobile station number can be acquired in advance, and all the related records of the mobile station number can be deleted.

0035Also, only the relevant records of a particular mobile station number may be stored. For example, keep only the relevant records of taxi mobile station numbers. As is well known, taxi mobile stations are more mobile and have a wider coverage than ordinary users' mobile stations, so obtain the taxi mobile station number in advance and only get information about the taxi mobile station number. save.

0036Sorting plan 2: The navigation system sorts based on the cell identifier.

0037In some cases, it is necessary to refer to the previously acquired cell switching record of the mobile station because the cell switching record of the mobile station currently acquired is small and the adjacency relationship between cells cannot be represented. For example, the cell switching record of the mobile station acquired yesterday. However, if the mobile network operator builds a new base station today, the related record of the cell identifier of the newly built base station cannot be combined with the record of yesterday, so it is necessary to delete the related record of the cell identifier. In this case, since the navigation system loaded the original cell identifier into memory based on the history record, if the cell identifier in the cell switching record of one mobile station does not exist in the cell identifier loaded into memory, the navigation system said Delete the cell switching record of the mobile station.

0038Selection 3: The navigation system ignores the records created by the vibration of the cell.

0039In some cases, the position of the mobile station does not change, but switching cells is called cell vibration. Since the mobile station does not actually move, the mobile station switching record generated by the cell vibration cannot represent the actual adjacency between the cells, so such a record should be ignored.

0040Specifically, after acquiring a new record R, the navigation system searches for the previous record O, which is the same as the mobile station number M in the record, and determines whether the time interval T between the two records exceeds 30 minutes. to decide. If the time interval T is less than 30 minutes, determine if the cell identifier in record R corresponds to one of the two recently camped cell identifiers for mobile station number M stored in the navigation system and record. If the cell identifier in R corresponds to one of the two recently camped cell identifiers for the mobile station number M stored in the navigation system, then the record R is considered to be a record caused by the cell tremor, so navigation. The system ignores the record R.

0041In actual application, one of the above selection proposals can be selected or used in combination.

0042Step B: Establish cell adjacency based on the cell switching record of the mobile station.

0043Specifically, the navigation system extracts the movement locus of the mobile station within a certain period of time based on the cell switching record of the mobile station acquired at a fixed time. Based on this movement locus, the adjacency of cells in this time zone is established. When one or more of the above selection plans are preset in the navigation system, the efficiency of the navigation system extracting the locus of the mobile station from the cell switching record of the mobile station can be improved.

0044In one embodiment, the method by which the navigation system extracts the movement locus of the mobile station based on the cell switching record of the mobile station specifically includes the following.

0045In the navigation system, the cell movement pair may be used to represent the movement trajectory of the mobile station, the cell movement pair is described in "original cell identifier, target cell identifier, camp time", and in the navigation system, each mobile station has recently been described. Stores the two cell identifiers camped in and the time stamp to enter these two cells. For example, in a navigation system, the two recently camped cell identifiers stored for mobile station M are X1 and X2, and the timestamp corresponding to X1 is tt1, where the cell identifier X2 corresponds. The time stamp is tt2, and tt2 is greater than tt1, that is, the previous switching record of the mobile station is "M, X2, tt2". The navigation system reads the cell switching record R of the mobile station M, and R = &lt;M, n1, t1&gt;.

0046The navigation system calculates the time interval T between record R and the previous switching record of mobile station M, i.e. T = t1-tt2.

0047When T 30 minutes, it is recognized that the locus recorded by the record R and the locus before the time interval T are divided into two independent loci, so that the navigation system has recently stored the mobile station M. Clears the two cell identifiers camped in, i.e. deletes the record corresponding to cell identifier X1 and cell identifier X2, and stores cell identifier n1 and timestamp t1 in record R.

0048If T &lt;30 minutes, the navigation system uses the cell movement pair &lt;X2, n1, t1-tt2&gt; as one movement locus of mobile station M, and the two cell identifiers recently camped by mobile station M as X2. And n1, where the time stamp corresponding to the cell identifier X2 is tt2 and the time stamp corresponding to the cell identifier n1 is t1.

0049Based on the above method, all the records related to the mobile station M can be processed to acquire all the movement loci of the mobile station M, and further, the movement loci of all the mobile stations are acquired.

0050In particular, a set of all movement trajectories (that is, cell movement pairs) within a fixed time is called a snapshot, and the fixed time is the snapshot time corresponding to the snapshot. For example, the snapshot time is 15 minutes. A snapshot represents a set of travel trajectories of all mobile stations taken within 15 minutes. The navigation system can maintain multiple historical snapshots and one current snapshot. It is preferable to set the snapshot time from 15 minutes to 1 hour to achieve the real-time sensing characteristics of stronger navigation systems and to ensure that the amount of data collected at the same time meets the demands of model accuracy. The snapshot is stored in the form of a file or memory database, the historical snapshot is persisted in the file system, and the current snapshot and the current day's historical snapshot are stored in the memory database. The memory database may contain an index of one snapshot, which records the time, holiday, holiday, and weather attributes of each snapshot. Here, the time attribute includes a year, a quarter, a month, a week, a day, and a time zone. Holidays and holiday attributes include work days, weekends, holidays, and holidays. Weather attributes include non-poor weather, heavy rain, heavy snow, and freezing frost.

0051The navigation system may establish a cell adjacency model within a certain period of time based on the above snapshot shot, including:

0052Based on the above snapshot shot, we establish a weighted directed graph with all cells as vertices, the adjacency between cells as edges, and the adjacency values between cells as edge weights. Here, the adjacent value between cells is the probability of moving between two cells, or the time of moving between two cells.

0053Specifically, in Plan I, if the snapshot has a cell movement pair record such as &lt;cell 1, cell 2, camp time&gt;, it means that the edges are interconnected between cell 1 and cell 2. .. The movement probability from cell 1 to cell 2 is a value obtained by dividing the number of records moved from the original cell 1 to the target cell 2 by the number of records moved from all the original cells 1. The probability of moving from cell 1 to cell 2 is defined as the weight of the edge from cell 1 to cell 2, and FIG. 2 is a movement probability directed graph between cells in one embodiment.

0054In Plan II, if the snapshot has a cell movement pair record such as &lt;cell 1, cell 2, camp time&gt;, it means that the edges are interconnected between cell 1 and cell 2. The travel time from cell 1 to cell 2 is the average value of "camp time" in all &lt;cell 1, cell 2, camp time&gt; records. The time to move from cell 1 to cell 2 is the weight of the edge from cell 1 to cell 2, and FIG. 3 is a time-directed graph of movement time between cells in one embodiment.

0055An improvement over Proposal II above using related models in higher contexts, for example a quadratic model, in which case &lt;second last cell ID, previous cell ID, current Cell ID, camp time&gt; pairs need to be extracted and recorded, and modeled and solved using a quadratic model. You can use a method that executes a higher-order model, and make an analogy like this.

0056If the quantity of movement trajectories in the current snapshot is small and the accuracy of the adjacency model between established cells is not high, the historical snapshot and the current snapshot may be used to construct the directed graph. When adopting, it is necessary to ensure that the context state and current state of the history snapshot match, so when selecting a history snapshot, use the latest history snapshot, and index features and current. You need to use historical snapshots with similar time index features.

0057Step 102: Correspond the starting point and the destination in the actual geographical space to the starting grid and the target grid after the grid processing for the space, respectively, and based on the adjacency model between the grids, the starting grid to the destination Determine the grid level path to the grid, Specifically, the navigation system receives the departure point and the destination input from the user, makes the departure point correspond to the departure grid, makes the destination correspond to the destination grid, and establishes it in step 101 based on the positional correspondence relationship. The grid level path from the starting grid to the target grid is determined based on the adjacency model between the grids.

0058In particular, when the cells of the cellular network are used as a grid, the cell of the base station closest to the starting point / destination is selected based on the latitude and longitude of the starting point and the destination and the latitude and longitude of the cell, and the starting base station / Let it be the target cell.

0059In one embodiment, when establishing a movement probability directed graph between cells according to the above plan I, the optimum route from the starting cell to the target cell is that all the starting nodes are the starting cell nodes and the ending nodes are the target cell nodes. This is the route with the highest probability. As shown in FIG. 2, the optimum route from the starting cell 1 to the target cell 7 is cell 1-&gt; cell 2-&gt; cell 4-&gt; cell 7, and the probability of generating the route is 0.7 * 0.3 * 0.9 =. It is 0.189, and the probability is greater than the probability of any other route. For example, if the probability of generating a path in cell 1-&gt; cell 2-&gt; cell 5-&gt; cell 6-&gt; cell 7 is 0.7 * 0.2 * 0.4 * 0.1 = 0.0075, the edge weight in the movement probability directed graph is -log ( The original edge weight) can be changed, and the solution can be obtained by converting the calculation of the optimum route into a standard shortest route search problem.

0060In one embodiment, as shown in FIG. 3, when establishing a travel time directed graph between cells according to the above plan II, in the directed graph, finding a solution for the optimum route from the starting cell to the target cell is performed. It may be converted to search for the shortest route. As shown in FIG. 3, the optimum route from the starting cell 1 to the target cell 7 is cell 1-&gt; cell 3-&gt; cell 6-&gt; cell 7, and the travel time of the route is 30 + 60 + 20 =. 110, the travel time of the route is shorter than the travel time of any other route, for example, the travel time of the route of cell 1-&gt; cell 2-&gt; cell 5-&gt; cell 7 is 50 + 25 + 36 = It is 111.

0061Step 103: Convert the grid-level route into an actual route from origin to destination in actual geospatial space.

0062Specifically, the navigation system maps the grid-level route calculated based on step 102 to a GIS map and / or a satellite map to obtain the actual route from the starting point to the destination.

0063In one embodiment, a method of converting cells of a cellular network into a grid and converting a cell-level route into an actual route corresponding to a GIS map is based on the latitude and longitude of the base station of each cell in the cell-level route. Is converted into one polyline in two-dimensional space, and the polyline is smoothed using the least-squares method to obtain one smoothing curve, which is buffered against the curve at a distance of 500 m. Process to obtain one area, select all roads that penetrate or include the area from the GIS map, and use a subset of the map from the starting point based on the dynamic planning algorithm. Includes calculating the route to the destination.

0064In another embodiment, the method of using the cells of the cellular network as a grid, making the cell level route correspond to the satellite map, and converting it into an actual route is to transmit the satellite map to the user and display the cell level route on the satellite map. However, the user includes selecting a route according to the route instruction and the actual road condition represented by the satellite map. This method solves the problem that the information on the GIS map lags behind the actual condition of the road by providing the road that is not displayed on the GIS map for the user. Generally, the newly created road will be updated to the GIS map in 3 months at the earliest, so it cannot be displayed on the GIS map.

0065In the method of route planning of the navigation system provided by the above embodiment, the method of two-step route planning is adopted. First, the cells of the cellular network are used to grid the actual geospatial space, and then the movement locus of the mobile station is extracted from the cell switching record of the mobile station acquired from the mobile communication operator. Therefore, it is possible to detect the movement trajectory information of a plurality of actual mobile stations in real time. By planning the route to the cellular space of the cellular network and matching the route based on the GIS map or satellite map, we reduce the demands on the accuracy and effectiveness of the GIS map. The real-timeness, accuracy, and effectiveness of route planning results can be improved. At the same time, it can assist in finding errors in the GIS map, and at the same time, based on this, it provides the optimum route within the range where the errors are tolerated. Since the technical proposal described in the embodiment of the present invention is based on the mobile communication network, the cost of arrangement is low and the range of application is wide.

0066An embodiment of the present invention provides a computer storage medium, the computer storage medium storing computer executable instructions, the computer executable instructions being used to execute the method of route planning of the navigation system.

0067FIG. 4 is a schematic structural diagram of a route planning device for a navigation system according to an embodiment of the present invention. As shown in FIG. 4, the route planning device includes a grid model establishment module 41, a grid path search module 42, and a grid path search module 42. It includes a track conversion module 43.

0068The grid model establishment module 41 performs a grid processing on the actual geospatial space, the grid is a cell of the cellular network, acquires the cell switching record of the mobile station, and is based on the cell switching record of the mobile station. It is configured to establish a cell adjacency model.

0069The grid path search module 42 maps the starting point and the destination in the actual geographical space to the gridded starting grid and the target grid, respectively, and based on the adjacency model, the grid from the starting grid to the target grid. It is configured to determine the level path.

0070The route conversion module 43 is configured to convert the grid-level route into an actual route from the starting point to the destination in the actual geospatial space.

0071Here, the above-mentioned grid is a cell of the cellular network, and correspondingly, the grid model establishment module 41 in the above-mentioned route planning apparatus is subjected to the cell switching record of the mobile station by a preset selection plan. It is configured to perform sorting.

0072In one embodiment, the grid model establishment module 41 A locus extraction submodule for extracting the movement locus of the mobile station based on the cell switching record of the mobile station, and A snapshot management submodule for taking a set of all the movement trajectories within a certain period of time as a snapshot, It includes an establishment submodule for establishing an adjacency model of cells within a certain period of time based on a snapshot.

0073The establishment submodule Based on the snapshot, it is further configured to establish a weighted directed graph with all cell base stations as vertices, cell adjacencies as edges, and cell adjacency values as edge weights. The adjacent value between cells is the probability of moving between two cells, or the time it takes to move between two cells.

0074Further, in the above-mentioned route planning device, the path conversion module 43 is A GIS map matching submodule for converting the grid level route into an actual route from the origin to the destination in the GIS map, and / or It includes a satellite map matching submodule for converting the grid level route into an actual route from the starting point to the destination in the satellite map.

0075In a practical application, each of the above modules and units is realized by a central processing unit (CPU), microprocessor (MPU), digital signal processing unit (DSP), or field programmable gate array (FPGR) in a navigation system. Ru.

0076Since the principle of the device as shown in FIG. 4 is similar to the method, the execution process and execution principle of the device for the route planning of the navigation system provided in the embodiment of the present invention are the execution process and execution principle of the above-mentioned method. Can be referred to, and detailed description thereof will be omitted here.

0077Those skilled in the art should understand that embodiments of the present invention can be provided as methods, systems, or computer program products. Therefore, the present invention can use a hardware embodiment, a software embodiment, or a combination of a software embodiment and a hardware embodiment. Moreover, the present invention describes the form of a computer program product implemented by a storage medium (including, but not limited to, a magnetic disk storage device and an optical memory) that can be used by one or more computers including a computer-usable program code. Can be used.

0078The present invention will be described with reference to flowcharts and / or block diagrams of methods, devices (systems), and computer program products according to embodiments of the present invention. It should be understood that computer program instructions can implement each process and / block of a flowchart, and a combination of processes and / or blocks of a flowchart and / block. These computer program instructions can be given to a general purpose computer, a dedicated computer, an embedded processor or the processor of another programmable data processor to generate one machine, thereby the processor of the computer or other programmable data processor. The instructions executed in will generate a device to implement the specified function in one process or multiple processes and / block diagrams of the flowchart.

0079These computer program instructions can also be stored in computer-readable memory that can guide the computer or other programmable data processor to operate in a particular mode, thereby storing it in the computer-readable memory. The command produces a product containing the command device, which implements the specified function in one or more processes and / or one or more blocks in the block diagram.

0080These computer program instructions can be loaded into a computer or other programmable data processor, thereby one or more processes and / or one or more processes in the flowchart by instructions executed on the computer or other programmable data processor. Provides steps to achieve a specified function in one or more blocks of a block diagram.

0081The above is merely an optimum embodiment of the present invention, and is not used to limit the scope of protection of the present invention.

0082In the route planning method, device and storage medium of the navigation system provided by the embodiment of the present invention, a two-step route planning method is adopted, and first, the cells of the cellular network are used with respect to the actual geospatial space. Then, by extracting the movement locus of the mobile station from the cell switching record of the mobile station acquired from the mobile communication operator, the movement locus information of a plurality of actual mobile stations is detected in real time. can do. By planning the route to the cellular space of the cellular network and matching the route based on the GIS map or satellite map, we reduce the demands on the accuracy and effectiveness of the GIS map. The real-timeness, accuracy, and effectiveness of route planning results can be improved. At the same time, it can assist in finding errors in the GIS map, and at the same time, based on this, it provides the optimum route within the range where the errors are tolerated. Since the technical proposal described in the embodiment of the present invention is based on the mobile communication network, the cost of arrangement is low and the range of application is wide.