JPH10153445A - Method for searching route in on-vehicle navigation device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To shorten the time for route calculation by storing a plurality of units in a memory area of a size corresponding to each hierarchy of a main storing memory, and reading and using the respective unit data in route calculation. SOLUTION: A main controller 1 calculates a recommended route on the basis of the present position data of one's own vehicle from a own vehicle position processing device 2 and the position data related to the starting point and designation of the vehicle inputted from an input device 6, and the resulting recommended route data is stored in a main storing memory 5. The main controller 1 also reads the recommended route data from the main storing memory 5 and supplies it to an image processing device 7. The image processing device 7 stores the recommended route data in a video RAM 7b by a graphic controller 7a, and supplies the recommended route data read from the video RAM 7b to a display device 7c to display it on a display screen.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search method in a vehicle-mounted navigation device.

[0002]

2. Description of the Related Art In a car navigation system,
The road network data for performing the route search is divided into regions divided by latitude and longitude, and divided into CDs.
-Stored in a recording medium such as a ROM. In the following description, one of the divided areas is referred to as a “unit”. FIG. 7 is a conceptual diagram of a unit, and latitudes i, j, k
And each unit u divided into rectangular areas at the positions of the longitudes m, n, and o, and a road network in the unit u.

Further, in order to speed up the route search operation and suppress memory consumption, a parent unit is created by grouping a plurality of child units. The parent unit U has a larger area than the child unit, but does not have information on minor roads. Usually, this parent-child relationship is created in about three or four layers. Level 0 is the most detailed road network, and levels 1, 2, and 3 are in the order of higher levels.
Call. FIG. 8 is a conceptual diagram of the hierarchical structure of units. For example, a unit u at level 0 and one parent unit U at level 1 having an area in which four child units u at level 0 are shown are shown. I have.

When a route search is carried out by an on-vehicle navigation device, generally, a level 0 is set near the departure point and the destination.
The detailed route network data is used, and a route search is performed at the intermediate point using the higher level road network data. The route search data for one unit is
Since it is composed of a header part and a data part, it is necessary to read data from the recording medium using this unit as one unit. The data size of one unit has an upper limit, and units exceeding this size are divided and created so as not to exceed the upper limit data size.

Conventionally, FIG. 9 shows a conceptual diagram of a hierarchical structure of road network data and an internal area of a memory.
In a part of the memory prepared for the route search in the vehicle-mounted navigation device (for example, on the lower address side),
One buffer area (fixed area) for reading data of the upper limit size is provided, and unit data of each level read from the recording medium is alternately stored in this area. The remaining area of the memory is a work area for path calculation and an area for storing intermediate results of the calculation. When the starting point and the destination are very close, each of them may be located in the same unit, but usually there are a plurality of units between the starting point and the destination. In other words, the route search also needs to perform calculations on a plurality of units and connect the respective routes.

[0006]

However, since each unit is separated by latitude and longitude, the same unit must be read a plurality of times depending on the road shape, and it takes a long time to search for a route. There was sometimes. Further, when realized on the task operating system, the "recording medium read task" and the "path calculation task" which are I / O parts with hardware cannot operate in parallel, and it is impossible to shorten the calculation time. there were.

An object of the present invention is to solve the above-mentioned conventional problems and to provide a route search method in an on-vehicle navigation device capable of shortening a route calculation time.

[0008]

A route search method in a vehicle-mounted navigation device according to the present invention includes a main storage memory having a plurality of variable-size memory areas for storing data of an arbitrary size, and is used for route calculation. A plurality of units each having a hierarchical structure of a road network are stored in a memory area of a size corresponding to each hierarchy of the main storage memory, and each unit data is read and used at the time of route calculation.

A route search method in a vehicle-mounted navigation device according to the present invention sequentially stores a plurality of units in a memory area of a continuous memory space of a main memory.

Further, a route search method in a vehicle-mounted navigation device according to the present invention stores a plurality of units in a memory area of a main memory using a memory allocation function of a task operating system.

[0011]

In a vehicle-mounted navigation device, a plurality of units each having a hierarchical structure of a road network used for route calculation are stored in each hierarchy of a main storage memory having a plurality of variable-size memory areas for storing data of an arbitrary size. The data is stored in a memory area of an appropriate size, and each unit data is read out and used at the time of path calculation. Since all the unit data used for the route calculation is stored in the memory area of the main storage memory, there is no need to read back the data as in the related art, and the calculation for the route search can be performed at high speed.

[0012]

FIG. 1 is a block diagram showing an embodiment of an on-vehicle navigation device for implementing a route search method according to the present invention. In FIG. 1, 1 is a main controller composed of a microcomputer or the like, 2 is a vehicle position processing device, 3 is a map database, 4 is a storage medium reading device, 5 is a main storage memory, 6 is an input device, and 7 is a video processing device. , 8 are audio output devices.

The own-vehicle position processing device 2 comprises an autonomous navigation sensor 2a, a GPS receiver 2b, and an own-vehicle position calculation device 2c. The own vehicle-related sensor information from the autonomous navigation sensor 2a and the GPS from the GPS receiver 2b are used. The own vehicle position is calculated by the own vehicle position calculation device 2c based on the current position information of the own vehicle by the satellite radio wave reception. The storage medium reader 4 is a CD-R
The map data is read from the map database 3 such as OM and supplied to the main controller 1.

The main controller 1 includes unit data of a road network from the storage medium reading device 4 and
The recommended route is calculated based on the current position data of the own vehicle from the own vehicle position processing device 2 and the position data relating to the departure point and the destination of the own vehicle input from the input device 6, and the obtained recommended route data is calculated. It is stored in the main storage memory 5. Further, the main controller 1 reads the recommended route data from the main storage memory 5 and supplies the recommended route data to the video processing device 7. The video processing device 7 includes a graphic controller 7a, a video RA
M7b and a display device 7c. The graphic controller 7 stores recommended route data in the video RAM 7b.
And the recommended route data read from the video RAM 7b is supplied to the display device 7c and displayed on the display screen.

In the above configuration, the route search method of the present invention is performed in the following procedure. Since the density of roads varies greatly depending on the area, the data size of the unit varies. In fact, units of a size close to the upper limit size are rare, and some smaller units are a fraction of the upper limit size. FIG. 2 shows a conceptual diagram of an example of the internal area of the main memory 5 and the hierarchical structure of the road network data used in the route search method of the present invention. In FIG. 2, a memory area corresponding to the size of each unit is allocated in the memory space of the main storage memory 5, and a road network from a recording medium is developed. That is, the memory area for storing each unit data has a variable size. When a plurality of units are required, the expanded memory areas of the respective units are arranged in the memory space without gaps, and data of a required number of units are simultaneously held.

Since the memory space is not fixed but has a variable size and has a plurality of units at the same time, a management table is prepared for the purpose of managing these units. Since this management table increases by one as one unit is read, an upper limit value is not defined and n management tables are created so as to increase from the highest address in a continuous address space toward lower addresses. The information held in the management table includes a number for identifying each unit, a data size of the unit, a stored address, and the like. In order to make the best use of the available memory, an algorithm using less memory is used than an algorithm with a higher calculation speed, and a work area for calculation other than unit data is reduced as much as possible in the memory space.

As a specific method for minimizing the calculation work area, for example, there is a method of writing information necessary for path calculation to an unnecessary portion of unit data stored in the memory area of the main memory 5. The unit data configuration will be described using the road network shown in FIG.
In FIG. 3, A, B, C, D are intersections, and AB, B
A,. . . Is a road, from the intersection data of B,
This means that there are three roads, BA, BC, and BD.
Among them, four types of data regarding the road of the BA, namely, a) the connection destination is the intersection A, b) the length of the BA, c) the road type (expressway, general road, etc.), and d) the characteristics of the road Is included in the data of the unit where the road BA exists. Among these four types of data, d) data is unnecessary data in the route search, and therefore, in the memory arrangement of the main memory 5 shown in FIG. Divert the memory area to the path calculation work area. Due to this diversion, a memory area dedicated to the path calculation work in the main storage memory 5 becomes unnecessary.

Another method for minimizing the calculation work area is to use a value that is equal to or larger than the upper limit of the unit data. The value that can be taken as the upper limit of each data is determined by the upper limit of the unit data size.
Therefore, a special meaning can be given by using a value equal to or more than the upper limit. For example, as shown in FIG. 4, even if the memory area of 1 byte is defined as the upper limit of the unit data, if the possible value is up to 127, the upper 1 bit is always 0 regardless of the change of the unit data.
Writing a value necessary for path calculation to this bit does not affect lower bits.

FIG. 5 is a flowchart of the unit data reading operation in the above-described route search method. First, in step S1, when there is a request for another unit data of the used unit for the route calculation, it is determined in step S2 whether the requested unit is present in the management table. If so, proceed to S3; if yes, proceed to S9. In S3, the management information of the unit in the management table is read, and in S4, the size and storage address of the unit are obtained. Then in S5,
The final address of the memory used is obtained, and in S6,
It is determined whether or not there is a free area of a size to read the unit. If yes, proceed to S7, if no, proceed to S1
Go to 0.

In S7, a management table is created, unit data is read in S8, and then the process proceeds to S9. If the answer to S2 is NO or in S9 following S8, the data after reading the unit is output and used for route calculation. On the other hand, if the answer to S6 is no, the process proceeds to S10, and information indicating an error due to insufficient memory is output. Here, the memory shortage means that the end of the unit data and the end of the management table overlap.

[0021]

FIG. 6 is a conceptual diagram showing another example of the internal area of the main memory 5 and the hierarchical structure of the road network data used in the route search method of the present invention. Using the assignment function,
The figure shows a case where a plurality of unit data required for route calculation are assigned without being limited to a continuous space. In this case, the management table acquires and creates a sufficient area as a fixed area.

As described above, since all the data of the units required for the search calculation are held in the main memory, the recommended route can be obtained at high speed without reading back the same unit data.

Further, since a plurality of units are simultaneously held in the main storage memory, it is possible to calculate another unit while reading data of one unit from a recording medium when realized on a multitasking operating system. Therefore, the calculation can proceed efficiently, and as a result, the path can be calculated at a high speed. In particular, when performing a bidirectional search (a search in which the search from the departure place to the destination and the search in the direction from the destination to the departure place are performed simultaneously), the unit used in each direction is often different, Especially the efficiency is increased.

Further, by providing a management table,
The reading size of the unit can be reduced to a necessary minimum size, and a plurality of units required for the search can be simultaneously held even in the main storage memory having a limited storage capacity of the navigation device.

[0025]

According to the present invention, all the data of the units required for the search calculation are stored in the main memory, so that the same unit data is not read back and the recommended route can be obtained at high speed.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of an in-vehicle navigation device that implements the route search method of the present invention.

FIG. 2 shows a conceptual diagram of an example of an internal area of a main memory 5 and a hierarchical structure of road network data used in the route search method of the present invention.

FIG. 3 shows an example of a road network for explaining a unit data configuration.

FIG. 4 shows an example of a memory area for unit data.

FIG. 5 is a flowchart of a unit data reading operation in the route search method of the present invention.

FIG. 6 is a conceptual diagram showing another example of the internal area of the main memory 5 and the hierarchical structure of road network data used in the route search method of the present invention.

FIG. 7 is a conceptual diagram of a unit.

FIG. 8 is a conceptual diagram of a hierarchical structure of a unit.

FIG. 9 shows a conceptual diagram of a conventional hierarchical structure of road network data and an internal area of a memory.

[Explanation of symbols]

 Reference Signs List 1 main controller 2 own vehicle position processing device 3 map database 4 storage medium reading device 5 main storage memory 6 input device 7 video processing device 8 audio output device 2a Autonomous navigation sensor 2b GPS receiver 2c Own vehicle position calculation device 7a Graphic controller 7b Video RAM 7c Display device

Claims (3)

[Claims] A main storage memory having a plurality of variable-size memory areas for storing data of an arbitrary size;
A plurality of units having a hierarchical structure of a road network used for route calculation are stored in a memory area of a size corresponding to each hierarchy of the main memory, and each unit data is read and used at the time of route calculation. Route search method in a vehicle-mounted navigation device. 2. The method according to claim 1, wherein a plurality of units are sequentially stored in a memory area of a continuous memory space of a main storage memory. 3. The method according to claim 1, wherein a plurality of units are stored in a memory area of a main memory using a memory allocation function of a task operating system. .