JP4492382B2 - Link travel time estimation device and navigation device - Google Patents

Description

  The present invention relates to a device and a method for estimating a travel time of a link for which travel time information of a road link is not provided, and a navigation device including the link travel time estimation device.

  A road link for which travel time information is not provided (hereinafter referred to as a non-service link) is a road link that exists within a predetermined distance from the non-service link and that is substantially parallel to the non-service link. When there are two road links for which travel time is provided (hereinafter referred to as service links), the travel time of non-service links is calculated based on the average travel time per unit distance of the two service links. There is known a link travel time estimation device that estimates (see, for example, Patent Document 1).

Prior art documents related to the invention of this application include the following.
Japanese Patent Laid-Open No. 11-037778

However, in the above-described conventional apparatus, the travel time of the non-service link is estimated based on the travel time of two service links that are substantially parallel to the non-service link across the non-service link. The estimated time is approximately the same as the travel time of the service link.
As a result, even if the route search to the destination is performed using the travel time estimated value of the non-service link, the actual travel time of the non-service link is shorter than the travel time of the service link. There is a problem that the service link is not selected as a substitute link for the service link, and it is not possible to search for an optimum route with no traffic jam and a short travel time.

The travel time of each road link is stored, and the connection form and the number of connection links between one link and the links existing around the link are classified and stored as connection patterns, and the peripheral links for each connection pattern The degree of influence of the travel time of one link on the travel time of the link is stored, and the connection pattern between the link where the travel time is not stored and the link where the travel time existing around the non-service link is stored Is compared with the stored connection pattern, and the travel time of the non-service link is estimated based on the influence level corresponding to the matched connection pattern and the travel time of the service link.

  According to the present invention, it is possible to accurately estimate the travel time of a non-service link.

  FIG. 1 is a diagram showing a configuration of an embodiment. The computing device 1 is composed of a CPU and its peripheral components, and executes a processing program described later to estimate the travel time of a non-service link for which no road traffic information is provided. The computing device 1 is connected to four databases (DB). Database 2 is a database for storing road map data provided by the Japan Digital Road Map Association. The stored data includes the length, position, connection status, road standard (road type), etc. of each road link. Link attribute information is included. The database 2 is also used as a working memory for storing various data generated by the link travel time estimation process by the arithmetic device 1.

  The database 3 is a database that stores travel time information of each road link. As for the link travel time, the latest road traffic information provided from the VICS (Vehicle Information and Communication System road traffic information communication system) center via FM multiplex broadcasting, radio wave beacon and optical beacon is stored in the database 3. Note that the VICS travel time data for a certain period may be statistically processed into a database.

  The database 4 is a database for storing “connection patterns” obtained by patterning “connection forms” of road links. The “connection form” and “connection pattern” of the road link will be described later. The relational expression database 5 is a database that stores a calculation formula for calculating travel time of a non-service link, and an influence coefficient α and a weight coefficient Weight used in the calculation formula. The influence coefficient α and the weight coefficient Weight will be described later.

  Next, the “connection form” and “connection pattern” of the road link will be described. FIG. 2 is a diagram showing a road map of a small area represented by links (indicated by band lines in the figure) and nodes (indicated by circles in the figure). Each link is given a link number L1, L2,. Currently, the travel time of the link L7 (indicated by a hatched band in FIG. 2) is not provided in the link travel time database 3, and as shown by the arrows in FIG. 2, the right side of the non-service link L7 is the upstream side and the left side. Is the downstream side.

  When attention is paid to the connection method of the non-service link L7 and its peripheral links, that is, "connection form", the link L1 is a link located upstream of the non-service link L7, and the links L2 and L4 are upstream of the non-service link L7. Link L13 is a link located downstream of the non-service link L7, links L9 and L11 are links crossing the non-service link L7 on the downstream side, and links L5, L8 and L16 are predetermined from the non-service link L7 The link is in the vicinity of the distance and parallel to the non-service link L7.

  In addition to the connection form shown in FIG. 2, this link connection form includes a link that merges with a certain link upstream, a link that merges with a certain link and downstream, a link that branches with a certain link and upstream, and a certain link. There are links that diverge downstream.

  In this embodiment, the type of link connection form is represented by a variable “n”, which is nine types. That is, the connection form of the link located on the upstream side is n = 1, the connection form of the link joining on the upstream side is n = 2, the connection form of the link intersecting on the upstream side is n = 3, and the connection branching on the upstream side The form is n = 4, the connection form of the parallel links is n = 5, the connection form of the links located downstream is n = 6, the connection form of the links joining downstream is n = 7, and the downstream crosses Assume that the link connection form is n = 8, and the link connection form branched downstream is n = 9.

  When the road link shown in FIG. 2 is represented by a connection form n, the peripheral link of the non-service link L7 includes n = 1 link L1 located upstream, n = 3 links L2 and L4 intersecting upstream, There are n = 6 links L13 located on the downstream side, n = 8 links L9 and L11 intersecting on the downstream side, and parallel n = 5 links L5, L8, and L16. These peripheral links of the non-service link L7 are links that affect the travel time of the non-service link L7.

  In this embodiment, the connection form of all links existing around a certain link and the number of links for each connection form are regarded as a pattern and stored in the database 4 as the “connection pattern” of the link. In this embodiment, the connection pattern type is represented by a variable “m”, and the number of links for each connection type n is represented by a variable “i”.

  FIG. 3 shows an example of a connection pattern stored in the database 4. There are many connection patterns m according to the connection form n and the number of links i for each connection form n. The non-service link L7 shown in FIG. 2 includes the number of links i = 1 in the connection mode n = 1, the number of links i = 2 in the connection mode n = 3, the number of links i = 3 in the connection mode n = 5, and the connection mode n =. Since the number of links i = 1 in 6 and the number of links i = 2 in connection mode n = 8, this corresponds to the connection pattern m = 6 in FIG.

  In this embodiment, an example is shown in which the connection pattern m is classified according to the connection form n and the number of links i for each connection form n. The connection pattern m is classified according to the classification of this embodiment. It is not limited to. For example, the classification may be further finely classified according to the road standard (road type) of the link of interest, or may be further classified according to the road standard difference between the link of interest and the surrounding link. Alternatively, the number of links i may be classified in a certain range such as 1-3, 4-6, 7-9,.

  Next, the link travel time influence coefficient α and the weight coefficient Weight will be described. The link travel time influence coefficient α is a coefficient indicating the degree of influence that the travel time of a link has on the travel time of another link. In this embodiment, the travel time of a service link is given to the travel time of a non-service link. Used as a coefficient indicating the degree of influence. The influence coefficient α is set by actually verifying the road link of the connection form n and the connection pattern m formed only by the service link, and the link travel time influence coefficient α (n, m) of the connection form n and the connection pattern m is set. Store in database 5.

  The weight coefficient Weight is used to adjust the influence degree of the influence coefficient α by giving a weight according to the number of peripheral links connected to the upstream side and the downstream side of a certain link and the number of links parallel to a certain link. In this embodiment, the degree of influence of the influence coefficient α according to the number of peripheral service links connected to the upstream side and downstream side of the non-service link and the number of service links parallel to the non-service link is calculated. Used as a coefficient for adjustment. The road link of the connection form n and the connection pattern m formed only by the service link is actually verified and the weight coefficient Weight is set, and the weight coefficient Weight (n, m) of the connection form n and the connection pattern m is stored in the database 5. Store.

Next, a method for calculating the travel time Tlink (x) of the non-service link will be described. In this embodiment, the service link connected to the upstream side and the downstream side of the non-service link and the service link parallel to the non-service link are distinguished by attaching a variable “k”. The travel time Tlink (x) of the non-service link x is the travel time Tlink (k) of the surrounding service link k (k = 1, 2,...) And the link travel time influence coefficient for the connection pattern m and the connection form n. Based on α (n, m) and the weight coefficient Weight (n, m), it can be obtained by the following equation.
Tlink (x) = ΣWeight (n, m) · α (n, m) · Tlink (k) (1)
In the equation (1), Σ represents the total sum for all peripheral service links k.

The link travel time Tlink (7) of the non-service link L7 shown in FIG. 2 is obtained by applying the above equation (1). As described above, the connection pattern of the non-service link L7 is m = 6, and the connection form is n = 1, 3, 5, 6, 8. The total number of the peripheral service links k is a total of 9 including L1, L2, L4, L5, L8, L16, L13, L9, and L11. Therefore, the travel time Tlink (7) of the non-service link L7 is
Tlink (7) = Weight (1,6) ・ α (1,6) ・ Tlink (1)
＋ Weight (3,6) ・ α (3,6) ・ Tlink (2)
＋ Weight (3,6) ・ α (3,6) ・ Tlink (4)
＋ Weight (5,6) ・ α (5,6) ・ Tlink (5)
＋ Weight (5,6) ・ α (5,6) ・ Tlink (8)
＋ Weight (5,6) ・ α (5,6) ・ Tlink (16)
＋ Weight (6,6) ・ α (6,6) ・ Tlink (13)
+ Weight (8,6) ・ α (8,6) ・ Tlink (9)
+ Weight (8,6) ・ α (8,6) ・ Tlink (11) (2)

  FIG. 4 is a flowchart showing a travel time estimation processing program for non-service links. In step 1, a map area for estimating the link travel time is set. This map area is set according to the use of the link travel time estimation device, the installation location, and the like. For example, when this link travel time estimation device is built in an in-vehicle navigation device and the shortest travel time route to the destination is searched, it is set as a region around the straight route from the current position of the vehicle to the destination. On the other hand, when this link travel time estimation device is installed in a road traffic information center and road traffic information is provided to each vehicle, the link travel time estimation device is set to a considerably wide area centering on the position of the information center.

  Next, in step 2, the non-service link x existing in the setting area is extracted. Specifically, the non-service link x in which the travel time information is not stored in the link travel time database 3 is read from the link in the setting area stored in the link database 2 and is temporarily stored in the working memory area of the database 2. To remember.

  In step 3, the service link k around the non-service link x is extracted. Specifically, the travel time information is stored in the link travel time database 3 with links connected to the upstream and downstream sides of the non-service link x stored in the link database 2 and links substantially parallel to the non-service link x. The stored service link k is read out and temporarily stored in the working memory area of the database 2.

  When extracting the service link k around the non-service link x, only the service link of the road standard equal to or higher than the road standard (road type) of the non-service link may be extracted. In general, road traffic is propagated in order from a wide, high-standard road to a narrow, low-standard road, so the travel time of peripheral service links with lower standards than the non-service link road standards is the travel time of non-service links. It is considered that the impact on Therefore, by extracting only the peripheral service links of the road standard equal to or higher than the road standard (road type) of the non-service link, the estimation processing time can be shortened without reducing the link travel time estimation accuracy.

  In step 4, the connection pattern m of the service link k extracted from the periphery of the non-service link x is specified. Specifically, the connection pattern n according to the connection form n of the service link k extracted around the non-service link x and the number of links i for each connection form is collated with the connection pattern stored in the link pattern database 4; A connection pattern m between the non-service link x and the peripheral service link k is specified.

  In step 5, the travel time Tlink (k) of the service link k extracted from the periphery of the non-service link x is read from the travel time database 3 and the link travel influence coefficient α () corresponding to the connection pattern m and the connection form n as a specific result. n, m) and the weight coefficient Weight (n, m) are read from the relational expression database 5.

  In step 6, the travel time Tlink (k) of the service link k extracted from the periphery of the non-service link x, the link travel time influence coefficient α (n, m) and the weight according to the connection pattern m and the connection form n of the specific result Based on the coefficient Weight (n, m), the link travel time Tlink (x) of the non-service link x is calculated by Equation (1).

  In step 7, it is confirmed whether or not the travel time estimation process described above has been completed for all non-service links in the set area. If not, the process returns to step 2 for unprocessed non-service links. The above-described processing is performed. When the travel times of all the non-service links in the setting area have been estimated, the process ends.

  As described above, according to the embodiment, the travel time of each road link is stored, and the relationship of the travel time between one link and links around the link is stored and stored. The relationship of travel time between one link and its surrounding links is expressed as follows: a non-service link in which travel time is not stored and a service link in which travel time existing around the non-service link is stored Since the travel time of the non-service link is estimated by applying to the relationship of the travel time between, the travel time of the non-service link can be accurately estimated.

  According to one embodiment, the connection form and the number of connection links between one link and its peripheral links are classified and stored as connection patterns, and the travel time of the peripheral links for each connection pattern is one link. The degree of influence on travel time (link travel time weighting factor α and weighting factor Weight) is stored, and the connection pattern between the non-service link and the surrounding service links is compared with the stored connection pattern, and the matching connection pattern Since the travel time of the non-service link is estimated based on the degree of influence corresponding to the travel time of the service link and the travel time of the service link, it is possible to further improve the estimation accuracy of the travel time of the non-service link.

  According to one embodiment, the peripheral links of one link include a link that exists in the vicinity of one link and is parallel to the one link. The travel time of the non-service link can be accurately estimated based on the travel time relationship with the link.

  The correspondence between the constituent elements of the claims and the constituent elements of the embodiment is as follows. That is, the databases 2 to 5 constitute storage means, and the arithmetic device 1 constitutes estimation means. The above description is merely an example, and when interpreting the invention, the correspondence between the items described in the above embodiment and the items described in the claims is not limited or restricted.

  As described above, the link travel time estimation device according to one embodiment can be used by being incorporated in an in-vehicle navigation device, or installed in a road traffic information center to provide link travel time information to many vehicles. You can also

  Using the road map data stored in the road map storage device while the travel time estimation device of the embodiment described above is built in the navigation device and the travel time of the non-service link is estimated by the link travel time estimation device. By searching for the shortest travel time route to the set destination, the shortest travel time route to the destination can be accurately searched.

It is a figure which shows the structure of one embodiment. It is a figure which shows an example of the road map containing a non-service link. It is a figure which shows an example of the connection pattern stored in a database. It is a flowchart which shows the link travel time estimation process of one Embodiment.

Explanation of symbols

1 Computing Device 2 Link Database 3 Link Travel Time Database 4 Link Pattern Database 5 Relational Expression Database

Claims (5)

The travel time of each road link (hereinafter simply referred to as a link) is stored, and the connection form and the number of connection links between one link and a link existing around the link (hereinafter referred to as a peripheral link) are used as a connection pattern. Storage means for classifying and storing, and storing the degree of influence of the travel time of the peripheral links for each connection pattern on the travel time of one link;
A connection pattern between a link in which travel time is not stored (hereinafter referred to as a non-service link) and a link in which the travel time existing around the non-service link is stored (hereinafter referred to as a service link) is stored in the storage unit. Link travel comprising: an estimation means for collating a stored connection pattern and estimating the travel time of a non-service link based on the degree of influence corresponding to the matched connection pattern and the travel time of a service link Time estimation device. The link travel time estimation device according to claim 1 ,
The link travel time estimation device according to claim 1, wherein the peripheral links of the one link include a link that exists in the vicinity of the one link and is parallel to the one link. In the link travel time estimation device according to claim 1 or 2 ,
The estimation means uses a service link of a road standard equal to or higher than the road standard of the non-service link among the service links around the non-service link for estimating the travel time of the non-service link. . The link travel time estimation device according to any one of claims 1 to 3 ,
Map storage means for storing road map data;
Destination setting means for setting a destination;
Route search means for searching for the shortest travel time route to the destination using the road map data of the map storage means while estimating the travel time of the non-service link by the link travel time estimation device, Navigation device. The travel time of each road link (hereinafter simply referred to as a link) is stored, and the connection form and the number of connection links between one link and a link existing around the link (hereinafter referred to as a peripheral link) are used as a connection pattern. Links that are classified and stored, and the degree of influence of the travel time of the surrounding links for each connection pattern on the travel time of one link is stored , and the travel time is not stored (hereinafter referred to as a non-service link). And the degree of influence corresponding to the matched connection pattern by comparing the connection pattern of the travel time existing in the vicinity of the non-service link with the stored connection pattern (hereinafter referred to as the service link). based on the travel time of the service link with the link travel time estimation method and estimating the travel time of the non-service link

Images