JP2005345114A - Route search method for navigation system - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To search for a recommending route, taking both a travel distance and a travel time into account. <P>SOLUTION: This navigation system has a storage device 3 for storing link data in each link constituting a road on a map, and statistical data of the each link, and an arithmetic processing part 1. The arithmetic processing part 1 sets a start point and a destination, and searches for the recommending route between the start point and the destination, using the data in the storage device 3. A value in response to a total value of the travel time in a candidate link included in the statistical data, and a correction time that is a time found from the travel time in a candidate link included in the link data is determined as a cost for the route search for the candidate link, in each of the candidate links of the links constituting the recommending route. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a navigation device, and more particularly to a route search technique for an in-vehicle navigation device.

  Patent Document 1 discloses a technique for changing a display form of a predetermined road on a map displayed on a display in accordance with the degree of congestion in a navigation device. For example, when the predetermined road is included in the route searched by the route search, the road included in the route of the predetermined road is determined by the traffic information collected in the past predetermined period. Display format according to the degree of traffic congestion. Here, the traffic information collected in the past predetermined period may be classified for each predetermined time zone. In this way, by changing the traffic information of the road adopted to determine the display form of the road according to the time, the display form of the road can be changed according to the traffic congestion that changes in real time. .

Japanese Patent Laid-Open No. 10-82644

  By the way, the technique described in Patent Document 1 does not consider using traffic information collected in the past for route search. Usually, the navigation apparatus searches for a recommended route between the departure point and the destination using link data including travel times of the links constituting the road on the map. Specifically, the travel time of the link included in the link data is used as the cost of the link, and the route that minimizes the total cost of each link constituting the route connecting the starting point and the destination is the Dijkstra method, etc. Use to search. Here, as the travel time of the link, instead of the travel time of the link data (usually proportional to the travel distance of the link), the travel time specified by the traffic information collected in the past is used. It is possible to search for the route with the shortest travel time as a recommended route in consideration of actual traffic conditions such as the above.

  However, when the travel time of the link specified by the traffic information collected in the past is used as the cost of the link instead of the travel time of the link included in the link data, the link cost is shorter than the shortest distance route. Since the total cost is slightly small, there may be a case where a route that is far away from the shortest distance route is searched for as a recommended route. In this case, considering the accuracy of traffic information, the actual travel time of the recommended route may be longer than the route with the shortest distance. In addition, it is generally considered that the user desires to travel on the shortest distance route that is easy to move if a significant time reduction cannot be expected.

  The present invention has been made in view of the above circumstances, and an object of the present invention is to enable a recommended route to be searched in consideration of both travel distance and travel time. For example, a route that makes a long detour with respect to the route with the shortest distance is prevented from being searched as a recommended route when a significant time reduction cannot be expected with respect to the route with the shortest distance.

  In order to solve the above-described problem, in the route search method of the present invention, link data including travel distance of each link constituting a road on the map is collected in the storage device of the navigation device and the past of each link. And statistical data including travel time determined from the statistical value of the traffic information. Then, using the setting step of setting the starting point and destination of the route to be searched for in the navigation device, and the link data and statistical data stored in the storage device, the recommendation between the starting point and the destination is made. And a route search step for searching for a route. Here, the route search step includes a travel time of the candidate link included in the statistical data and a candidate link included in the link data for each candidate link of the link constituting the recommended route. A value corresponding to the total value of the correction time, which is the time obtained from the travel distance, is determined as the cost for route search for the candidate link.

  In the present invention, for each candidate link of the links constituting the recommended route, the correction time is obtained from the travel distance of the candidate link included in the link data. Then, the correction time is added to the travel time of the candidate link included in the statistical data, and a value corresponding to the addition result is set as a cost for route search of the candidate link. Therefore, according to the present invention, the recommended route can be searched in consideration of both the travel time determined from the traffic information and the actual travel distance. This prevents, for example, a route that makes a large detour with respect to the route with the shortest distance from being searched as a recommended route even though it cannot be expected to significantly reduce the time with respect to the route with the shortest distance. Can do.

  Hereinafter, embodiments of the present invention will be described.

  FIG. 1 is a schematic configuration diagram of an in-vehicle navigation device to which an embodiment of the present invention is applied. As shown in the figure, the in-vehicle navigation device of the present embodiment includes an arithmetic processing unit 1, a display device 2, a storage device 3, a voice input / output device 4, an input device 5, a wheel speed sensor 6, and a geomagnetism. A sensor 7, a gyro sensor 8, a GPS (Global Positioning System) receiver 9, and an in-vehicle LAN device 11 are included.

  The arithmetic processing unit 1 is a central unit that performs various processes. For example, the current location is detected based on information output from the various sensors 6 to 8 and the GPS receiver 9, and map data necessary for display is read from the storage device 3 based on the obtained current location. Also, the read map data is developed in graphics, and a mark indicating the current location is displayed on the display device 2 over the map data, or the map data and statistical traffic data stored in the storage device 3 are used to instruct the user. The optimal route (recommended route) connecting the destination and the departure place (for example, the current location) is searched, and the user is guided using the voice input / output device 4 and the display device 2.

  The display device 2 is a unit that displays graphics information generated by the arithmetic processing unit 1, and is configured by an LCD, a CRT, or the like. The arithmetic processing unit 1 and the display device 2 are generally connected by RGB signals or NTSC (National Television System Committee) signals.

  The storage device 3 includes a storage medium such as a CD-ROM, DVD-ROM, HDD, or IC card. This storage medium stores map data and statistical traffic data.

  FIG. 2 is a diagram illustrating a configuration example of map data stored in the storage device 3. As shown in the figure, map data 31 is stored for each mesh region obtained by dividing the map into a plurality of parts. The map data 31 includes a mesh area identification code (mesh ID) 311 and link data 312 of each link constituting a road included in the mesh area. The link data 312 includes a link identification code (link ID) 3121, coordinate information 3122 of two nodes (start node and end node) constituting the link, attribute information (including type and road width) 3123 of a road including the link, It includes link length information 3124 indicating the link length, link travel time information 3125, link ID (connection link ID) 3126 of a link connected to each of the two nodes, and the like. Here, by distinguishing the start node and the end node for the two nodes constituting the link, the upward direction and the downward direction of the same road are managed as different links. Further, the map data 31 includes information (name, type, coordinate information, etc.) of map components other than roads included in the corresponding mesh area, although not shown.

  FIG. 3 is a diagram illustrating a configuration example of statistical traffic data stored in the storage device 3. As shown in the figure, statistical traffic data 32 is stored for each mesh area described above. The statistical traffic data 32 is management data for managing the mesh ID 321 of the mesh area and the traffic information statistical value (statistical value of the traffic information collected in the past) of each link constituting the road included in the mesh area. 322. The mesh ID 321 is the same as the mesh ID 311 of the map data 31. The management data 322 is composed of a plurality of tables 3221 to 3223 having a hierarchical structure.

  The table 3221 is a table for registering the day type. The type of day may be determined for each unit indicating a tendency of different traffic information statistics. Here, weekdays before holidays, “weekdays (before holidays)”, weekdays after holidays, “weekdays (after holidays)”, weekdays before special days such as Bon, New Year, etc. Weekdays of the daylight “Weekdays (after the singular days)”, Other weekdays “Weekdays (general)”, the first days of the singular days “holidays (beginning of the singular days)”, the end of the singular days “holidays (end of the singular days)” The holiday “holiday (general)” is included.

  The table 3222 is a table for registering the link ID of each link constituting the road included in the mesh area registered by the mesh ID 321, and is provided for each type of day registered in the table 3221. The same link ID as the link ID 3121 of the map data 31 is used.

  The table 3223 is a table for registering traffic information statistics for each time zone, and is provided for each link ID registered in the table 3222. The traffic information statistical value for each time zone includes the link travel time, the link travel time variation degree, and the link traffic congestion degree specified by the plurality of pieces of traffic information as a basis. In addition, the traffic information statistics for each time zone are classified according to the traffic information collection conditions (the type of day when the traffic information is collected) and the target link. That is, the target link of the traffic information statistical value for each time zone registered in a certain table 3223 is a link specified by the link ID of the table 3222 associated with this table 3223, and these statistical values The original traffic information is traffic information collected on the day specified by the type of day in the table 3221 associated with the table 3222 in which the link ID is registered.

  In addition to the above map data and statistical traffic data, the storage device 3 includes a first conversion that is a conversion table for specifying a mesh ID of a mesh region including a point specified by the coordinate information from the coordinate information. A table and a second conversion table, which is a conversion table for specifying the type of day managed in the table 3221 from the date, are stored.

  Returning to FIG. 1, the description will be continued. The voice input / output device 4 converts the message to the user generated by the arithmetic processing unit 1 into a voice signal and outputs it, and recognizes the voice uttered by the user and transfers the content to the arithmetic processing unit 1.

  The input device 5 is a unit that receives an instruction from a user, and includes a hardware switch such as a scroll key and a scale change key, a joystick, a touch panel pasted on a display, and the like.

  The sensors 6 to 8 and the GPS receiver 9 are used for detecting the current location (own vehicle position) by the in-vehicle navigation device. The wheel speed sensor 6 measures the distance from the product of the wheel circumference and the measured number of rotations of the wheel, and further measures the angle at which the moving body is bent from the difference in the number of rotations of the paired wheels. The geomagnetic sensor 7 detects the magnetic field held by the earth and detects the direction in which the vehicle is facing. The gyro 8 is configured by an optical fiber gyro, a vibration gyro, or the like, and detects an angle at which the vehicle rotates. The GPS receiver 9 receives a signal from a GPS satellite and measures the distance between the vehicle and the GPS satellite and the rate of change of the distance with respect to three or more satellites to measure the current location, traveling direction, and traveling direction of the vehicle. To do.

  The in-vehicle LAN device 11 receives various information of the vehicle on which the in-vehicle navigation device of the present embodiment is mounted, such as door opening / closing information, light lighting state information, engine status and failure diagnosis result.

  FIG. 4 is a diagram illustrating a hardware configuration example of the arithmetic processing unit 1. As illustrated, the arithmetic processing unit 1 has a configuration in which devices are connected by a bus 32. The arithmetic processing unit 1 includes a central processing unit (CPU) 21 that executes various processes such as numerical calculation and control of each device, and a RAM (RAM) that stores map data, statistical traffic data, and arithmetic data read from the storage device 3. Random Access Memory (ROM) 22, ROM (Read Only Memory) 23 for storing programs and data, DMA (Direct Memory Access) 24 for executing data transfer between the memories and between the memory and each device, and graphics drawing , And a display controller 25 for performing display control, a video random access memory (VRAM) 26 for storing graphics image data, a color palette 27 for converting image data into RGB signals, and converting analog signals into digital signals. A / D converter 28 and SCI (Serial Co) that converts serial signals into parallel signals synchronized with the bus mmunication interface) 29, a PIO (Parallel Input / Output) 30 that puts a parallel signal on the bus in synchronization with the bus, and a counter 31 that integrates the pulse signal.

  FIG. 5 is a diagram illustrating a functional configuration of the arithmetic processing unit 1. As illustrated, the arithmetic processing unit 1 includes a user operation analysis unit 41, a route search unit 42, a route storage unit 43, a route guidance unit 44, a map display processing unit 45, a current location detection unit 46, and a map. A match processing unit 47, a data reading unit 48, a locus storage unit 49, a menu display processing unit 50, and a graphics processing unit 51 are included.

  The current position detection unit 46 uses distance data and angle data obtained as a result of integrating the distance pulse data measured by the wheel speed sensor 6 and the angular acceleration data measured by the gyro sensor 8, and integrates the data on the time axis. As a result, the current position (X ′, Y ′), which is the position after the host vehicle travels, is periodically calculated from the initial position (X, Y), and is output to the map match processing unit 47. Here, in order to match the relationship between the rotation angle of the vehicle and the traveling direction, referring to the direction data obtained from the geomagnetic sensor 7 and the angle data obtained by integrating the angular acceleration data obtained from the gyro sensor 8, Estimate the absolute direction of the direction in which the vehicle is traveling. Since the error accumulates when the data of the wheel speed sensor 6 and the data of the gyro sensor 8 are integrated, the accumulated error is canceled based on the position data obtained from the GPS receiver 9 in a certain time period. The current location information is output to the map match processing unit 47.

  For example, the map match processing unit 47 periodically compares the map data around the current location read by the data reading unit 48 with a travel locus stored in a locus storage unit 49 described later, and the correlation of the shapes is compared. Map matching processing is performed in which the current location output from the current position calculation unit 46 is matched with the highest road (link). Since the current position information obtained by the current position calculation unit 46 includes a sensor error, map matching processing is performed for the purpose of further improving the position accuracy. As a result, the current location often coincides with the traveling road.

  The trajectory storage unit 49 stores information on the current location on which the map match processing has been performed by the map match processing unit 47 as trajectory data every time the vehicle travels a predetermined distance. The trajectory data is used to draw a trajectory mark on the road on the map corresponding to the road that has been traveled so far.

  The user operation analysis unit 41 receives a request from the user input to the input device 5, analyzes the request content, and controls each unit of the arithmetic processing unit 1 so that processing corresponding to the request content is executed. To do. For example, when the user requests a search for a recommended route, the map display unit 45 is requested to display a map on the display 2 in order to set a departure point and a destination, and further, from the departure point to the destination. Requests the route search unit 42 to calculate a route.

  The route search unit 42 uses a Dijkstra method or the like to search for a route that can reach the destination at a desired cost (travel time) among the routes connecting the two specified points (departure point, destination) with map data. And the route obtained as a result is stored in the route storage unit 43 as a recommended route. In this embodiment, in order to calculate the cost of a route connecting two points, the statistical traffic data 32 stored in the storage device 3, that is, the time zone of each link classified for each day type. The travel time and the correction time obtained from the travel distance registered in the link data 312 are used.

  The route guidance unit 44 compares the recommended route information stored in the route storage unit 43 with the current location information output from the map match processing unit 47 and determines whether the vehicle should go straight before passing an intersection or the like. The voice input / output device 4 is used to inform the user by voice, or the direction to travel is displayed on the map displayed on the display device 2 to notify the user of the recommended route.

  The data reading unit 48 stores map data and statistical traffic data in an area required to be displayed on the display device 2 and an area required for route search (an area including a departure place and a destination). It operates to prepare for reading from 3.

  The map display processing unit 45 receives the map data in the area where the display on the display device 2 is requested from the data reading unit 48, and the graphics processing unit 51 uses the designated scale and drawing method, roads, and the like. A map drawing command is generated so as to draw a map component, a current location, a destination, and a mark such as an arrow for a guide route.

  Upon receiving a command output from the user operation analysis unit 41, the menu display processing unit 50 generates a menu drawing command so that the graphics processing unit 51 draws various types of menus and graphs.

  The graphics processing unit 51 receives the commands generated by the map display processing unit 45 and the menu display processing unit 50, and develops image data to be displayed on the display device in the VRAM 26.

  Next, the recommended route searching operation of the in-vehicle navigation device having the above-described configuration will be described. FIG. 6 is a flowchart for explaining the recommended route search operation of the navigation device to which this embodiment is applied.

  First, when receiving a conversion coefficient setting request from the user via the voice input / output device 4 or the input device 5 (S11), the user operation analysis unit 41 outputs a conversion coefficient reception screen display request to the menu display processing unit 50. In response to this, the menu display processing unit 50 controls the graphics processing unit 51 to display a conversion coefficient reception screen for receiving the conversion coefficient and the correction coefficient from the user on the display device 2. Here, the conversion coefficient is a coefficient used to calculate the correction time included in the cost (travel time) of the link used for route search. The correction coefficient is a coefficient for correcting the conversion coefficient. By multiplying the travel distance of the link registered in the link data 312 by the conversion coefficient corrected with the correction coefficient, the correction time included in the cost of the link can be obtained.

  FIG. 7 shows an example of the conversion coefficient reception screen. Reference numeral 201 is a conversion coefficient input field, reference numeral 202 is a correction coefficient input field corresponding to the road width, and reference numeral 203 is a correction coefficient input field corresponding to the road type. In the example shown in FIG. 7, an input field 202 is provided for each of the case where the road width is 2 lanes and the case where the road width is 3 lanes. In addition, an input field 203 is provided for each of the case where the road type is a prefectural road, the case of a national road, and the case of a toll road. In addition, initial values are registered in these input fields 201 to 203. The initial value of the input field 202 is set so that the correction time is reduced in the order of 3 lanes and 2 lanes. The initial value in the input field 203 is set so that the correction time is reduced in the order of toll road, national road, and prefectural road. The user can change these initial values to desired values using the input device 5. When the user operation analysis unit 41 detects that the confirmation button 204 has been selected using the input device 5, the conversion coefficient displayed in the input fields 201 to 203 at that time, and the road attribute (road width, A correction coefficient corresponding to the type is set in the route search unit 42 (S12).

  When the user operation analysis unit 41 receives a route search request from the user via the voice input / output device 4 or the input device 5 (S13), the user operation analysis unit 41 sets the departure point, the destination, and the departure time in the route search unit 42 ( S14).

  Here, the starting point and the destination to be set are read from the storage device 3 by the user operation analysis unit 41 into the display device 2 through the menu display processing unit 50 and the graphics processing unit 51 through the data reading unit 48. The information of the map components registered in the map data 31 is displayed, and the user can select from the information of the displayed map components via the voice input / output device 4 or the input device 5. Also good. Alternatively, information on a point (registered place) registered in advance in the RAM 22 or the like by the user is displayed, and selected from the information on the registered place being displayed by the user via the voice input / output device 4 or the input device 5 You may make it make it. Further, the map specified by the user operation analysis unit 41 from the map data 32 read from the storage device 3 via the data reading unit 48 to the display device 2 via the map display processing unit 45 and the graphics processing unit 51. May be displayed by selecting designation of a spot on the map from the user via the voice input / output device 4 or the input device 5. When the current location is set as the departure location, the designation of the departure location by the user may be omitted. Also, when the current time is set as the departure time, the designation of the departure time by the user may be omitted. When the departure point, destination, and departure time are set in the route search unit 42 as described above, the user operation analysis unit 41 outputs a route search instruction to the route search unit 42.

  In response to this, the route search unit 42, from the storage device 3 via the data reading unit 48, the first conversion table for specifying the mesh ID of the mesh region including the point specified by the coordinate information from the coordinate information. Is read. And using this 1st conversion table, mesh ID of each mesh area | region contained in the area | region containing the set departure place and the destination is specified. Next, each link data 312 registered in each map data 31 having the specified mesh ID is obtained from the storage device 3 via the data reading unit 48 (S15). Next, the second conversion table for specifying the type of day managed in the table 3221 of the statistical traffic data 32 is read from the storage device 3 via the data reading unit 48. Then, using the second conversion table, the type of today (departure date) is specified (S16).

  Next, the route search unit 42 is set in advance with each link data 312 read in S15 and statistical traffic data 32 corresponding to the type of day specified in S16 of each link specified by these link data 312. The recommended route from the starting point to the destination set in S14 is searched using the conversion factor and the correction factor that are set (S17). Then, the route search unit 42 controls the menu display processing unit 50 or the map display processing unit to display the searched recommended route information on the display device 2 (S18).

  Next, the recommended route search process in S17 of FIG. 6 will be described. FIG. 8 is a flowchart for explaining the recommended route search processing in S17 of FIG.

  First, the route search unit 42 uses the link data 312 read from the storage device 3 in S15 of FIG. 6 as an end node of the link (referred to as an extracted link) extracted from the heap table in S1709 described later. The link to be selected is selected as a link candidate (referred to as a candidate link) constituting the recommended route.

  However, when the processing in S1709 is not performed, that is, in the initial stage in which no link is registered in the heap table, instead of selecting a link having the end node of the extracted link as a start node as a candidate link, the departure place Is selected as a candidate link (S1701).

  Here, the heap table is a table for registering the link data of the candidate link together with the total cost from the departure place to the end node of the candidate link, and is stored in a storage device such as a memory. FIG. 9 is a diagram illustrating an example of a heap table. As illustrated, a record 4300 is registered for each candidate link in the heap table. The record 4300 includes a field 4301 for registering the link ID of the candidate link, a field 4302 for registering the cost of the candidate link, and a field for registering the link ID of the connection source link that connects the end node to the start node of the candidate link. 4303, a field 4304 for registering the total cost from the departure point to the candidate link, a field 4305 for registering the total travel time from the departure point to the candidate link, and whether the extraction link has been set in S1709 to be described later And a field 4306 for registering an extraction flag indicating whether or not.

  Next, the route search unit 42 calculates the estimated arrival time at the end node of the extracted link. This can be calculated by identifying the candidate link record 4300 currently set for the extracted link from the heap table and adding the total travel time registered in the field 4305 of this record 4300 to the departure time. Then, the route search unit 42 identifies the time zone to which the calculated estimated arrival time belongs from the time zones in which the traffic information statistical values are registered in the statistical traffic data 32, and uses this time zone as the attention time zone. (S1702).

  Next, the route search unit 42 specifies the mesh ID of the mesh region to which the end node of the extraction link belongs using the first conversion table. Then, the statistical traffic data 32 having the identified mesh ID is read from the storage device 3 via the data reading unit 48. Then, using the management data 322 of the read statistical traffic data 32, the traffic information statistical value of the attention time zone is specified for each candidate link (S1703).

  Then, the route search unit 42 determines the above correction coefficient for each candidate link using the road attribute 3123 of the link data 312 (S1704). For example, it is assumed that the correction coefficient shown in FIG. In this case, if the road attribute of the candidate link is road width: 2 lanes, road type: national road, the multiplication result of the coefficient 0.9 corresponding to the road width: 2 lanes and the coefficient 0.9 corresponding to the road type: national road 0. 81 is the correction coefficient of the candidate link.

  Next, the route search unit 43 calculates a correction time for each candidate link using the link length 3124 of the link data 312, the correction coefficient determined in S 1704, and a preset conversion coefficient (S 1705). . For example, the link length is multiplied by a correction coefficient and a conversion coefficient, and the result is used as the correction time.

  Next, the route search unit 42 calculates a cost for each candidate link by using the travel time included in the traffic information statistical value of the attention time zone and the correction time calculated in S1705 (S1706). . For example, the total value of the travel time and the correction time is multiplied by a predetermined coefficient, and the result is used as the cost.

  Next, the route search unit 42 calculates the total travel time and the total cost from the departure point to the candidate link for each candidate link. Specifically, the travel time included in the traffic information statistical value of the attention time zone of the candidate link is added to the total travel time of the extracted link registered in the heap table, and the addition result is added to the candidate link. Total travel time. Further, the total cost calculated in S1706 is added to the total cost of the extraction link registered in the heap table, and the addition result is set as the total cost of the candidate link. Then, the route search unit 42 adds a record 4300 for each candidate link to the heap table. Then, in the fields 4301 to 4304 of each added record 4300, the link ID of the corresponding candidate link, the cost of the candidate link calculated in S1706, the link ID of the extracted link (connection source link), and the departure place calculated in S1706 Register the total cost and total travel time to the candidate link. Further, “not yet” indicating that the extraction link has not been set yet is registered in the field 4306 (S1707).

  Next, the route search unit 42 includes a link where the destination exists or is close to the destination (referred to as a destination link) among the candidate links newly added to the heap table in S1707 performed immediately before. It is checked whether or not (S1708).

  If it is determined in S1708 that there is no destination link, the route search unit 42 sorts the records 4300 of the candidate links registered in the heap table in ascending order of the total cost, and the extraction flag in the field 4306 is “not yet”. Among the candidate links (referred to as unextracted links), the unextracted link with the lowest total cost is extracted from the heap table, for example, by extracting the unextracted link located at the top. Then, the current extracted link is changed to the unextracted link, and the extraction flag registered in the field 4306 of the record 4300 of the unextracted link is changed from “not yet” to “completed” (S1709). Then, the process returns to S1701.

  On the other hand, if it is determined in S1708 that there is a destination link, the route search unit 42 performs recommended route determination processing. Specifically, the connection source link of the destination link (candidate link whose link ID is registered in the field 4303 of the destination link record 4300) is searched from the heap table, and the searched link constitutes a recommended route. Determine a link (referred to as a configuration link). Next, it is checked whether or not there is a connection source link of the configuration link. If there is a connection source link, this connection source link is determined as the configuration link, and it is further checked whether or not there is the connection source link. The recommended route is configured by repeating this process until there is no connection source link of the configuration link, that is, the configuration link is a link that exists or is close to the departure location (called a departure location link). Determine each component link. Then, the route search unit 42 stores the link information 312 of each constituent link constituting the recommended route and the traffic information statistical value obtained in S1703 as the recommended route information in the route storage unit 43 together with the departure time information. (S1710).

  With the above processing, the cost of each constituent link constituting the recommended route is as follows. That is, as the travel time of the first link constituting the recommended route, the travel time obtained from the traffic information statistical value corresponding to the time zone including the departure time, and the correction time obtained from the link length and the road attribute of the first link A value corresponding to the total value is used. In addition, the travel time of the nth (n ≧ 2) link constituting the recommended route corresponds to a time zone including an expected arrival time at the end node of the n−1th link connected to the nth link. A value corresponding to the total value of the travel time obtained from the traffic information statistical value and the correction time obtained from the link length and road attribute of the n-th link is used.

  Next, the recommended route display process in S18 of FIG. 6 will be described. FIG. 10 is a flowchart for explaining the recommended route display processing in S18 of FIG.

  First, the route search unit 42 uses the recommended route information registered in the route storage unit 43 to determine the expected travel time of the recommended route and the expected arrival time at the destination. Specifically, the travel time included in the traffic information statistical value of each link constituting the recommended route registered in the route storage unit 43 is summed up, and this is used as the expected travel time of the recommended route. . Further, the time obtained by adding the estimated arrival time to the departure time is set as the estimated arrival time at the destination. Furthermore, the route search unit 42 uses the map data 31 to specify a node to be set as a passing point such as an intersection from the start node or the end node of each link constituting the recommended route. Then, the estimated travel time and the expected arrival time to this node are obtained in the same manner as the expected travel time and the expected arrival time to the destination (S1801).

  Next, the route search unit 42 obtains the reliability / estimation error of the expected travel time of the recommended route obtained in S1801 and the expected arrival time to the destination (S1802). Specifically, the error of the travel time of each link is calculated using the degree of variation included in the traffic information statistical value of each link constituting the recommended route registered in the route storage unit 43. For example, when the degree of variation is “small”, the error rate is 3%, when the degree of variation is “medium”, the error rate is 5%, and when the degree of variation is “large”, the error rate is 10%. Then, the link travel time is multiplied by an error rate corresponding to the degree of variation in the travel time of the link to calculate an error of the link. This process is performed for each link constituting the recommended route. Next, the sum of errors of each link is calculated, and this is used as the estimated error of the expected travel time and the expected arrival time. Further, the ratio of the estimated error to the estimated travel time (error rate) is obtained, and the reliability of the estimated travel time and the estimated arrival time is determined according to the value. For example, the reliability is determined as “high” if the ratio is less than 5%, “medium” if it is less than 10%, and “low” if it is 10% or more.

  When the estimated travel time to the destination, the estimated arrival time, the estimated travel time to the passing point, the estimated arrival time, the reliability of the recommended route, and the estimation error are obtained as described above, the route search unit 42 Passes these pieces of information to the menu display processing unit 50 to instruct recommended route display. In response to this, the menu display processing unit 50 displays the recommended route on the display device 2 via the graphics processing unit 51 so that the estimated travel time, the estimated arrival time, the reliability, and the estimation error can be understood. (S1803). FIG. 11 shows a general display example of the recommended route. In this example, the time (departure time, arrival time, passage time) 224 and the elapsed time 225 from the departure point 221 for each of the departure point 221, the destination point 222, and the at least one passing point 223 are the recommended route. The estimated travel time (expected arrival time) reliability 226 and the estimated error 227 are displayed. Here, the passing point 223 corresponds to the passing point specified in S1801.

  When the general display of the recommended route is performed, when the user operation analysis unit 41 receives an instruction to change to the map display mode from the user via the voice input / output device 4 or the input device 5 (YES in S1804). ) And inform the route search unit 42 to that effect. The route search unit 42 stores the estimated travel time to the destination, the estimated arrival time, the estimated travel time to the passing point, the estimated arrival time, the reliability of the recommended route, and the estimation error in the route storage unit 43. Along with the link data of each link constituting the recommended route, it is passed to the map display processing unit 45 to instruct display of the recommended route. In response to this, the map display processing unit 45 displays the recommended route on the map via the graphics processing unit 51 so that the recommended travel time, the predicted arrival time, the reliability, and the estimation error can be understood. (S1805). FIG. 12 shows a map display example of the recommended route. In this example, the recommended route 231 is displayed on the map together with the reliability 235 and the estimated error 236 of the expected travel time (expected arrival time) of the recommended route 231. The recommended route 231 is marked with a departure point, a passing point, and a destination, and an estimated arrival time and an estimated travel time to each point are displayed near each point (232 to 234).

  If the user operation analysis unit 41 receives an instruction to change to the general display mode from the user via the voice input / output device 4 or the input device 5 while the recommended route is being displayed on the map (YES in S1806). ), That is notified to the route search part 42, and it transfers to S1804.

  This flow ends when the user operation analysis unit 41 receives an end instruction from the user via the voice input / output device 4 or the input device 5.

  The embodiment of the present invention has been described above.

  In the present embodiment, the correction time is obtained from the link length of the candidate link included in the link data for each candidate link of the link constituting the recommended route. Then, the correction time is added to the travel time of the candidate link included in the statistical data, and a value corresponding to the addition result is set as a cost for route search of the candidate link. Therefore, according to the present embodiment, the recommended route can be searched in consideration of both the travel time determined from the traffic information statistics and the actual travel distance. This prevents, for example, a route that makes a large detour with respect to the route with the shortest distance from being searched as a recommended route even though it cannot be expected to significantly reduce the time with respect to the route with the shortest distance. Can do.

  Moreover, in this embodiment, the conversion coefficient which calculates | requires correction time from link length is changed according to a road attribute using a correction coefficient. For example, a conversion coefficient is corrected with a correction coefficient so that the correction time is shortened for a road that is easy to travel, such as a wide road or a national road. As a result, it is possible to increase the possibility that an easy-to-run road is searched as a recommended route. In this embodiment, since the conversion coefficient and the correction coefficient can be set by the user, the conversion coefficient and the correction are adjusted so that the user is more likely to search for a recommended route as a recommended route. The coefficient can be adjusted.

  In addition, this invention is not limited to said embodiment, Many deformation | transformation are possible within the range of the summary.

  For example, in S14 (search condition setting) shown in FIG. 6, whether or not a priority mode for performing route search with priority given to a predetermined type of road (for example, a toll road) is applied may be received from the user. . When the priority mode application instruction is received, a correction coefficient for the predetermined type of road is set to a value that is set in advance so that the correction time is shorter than that of the case other than the predetermined type of road. By performing S17 (recommended route search) shown in FIG. 6, the possibility that a route using the predetermined type of road is searched as a recommended route may be increased.

  Further, in S14 (setting search conditions) shown in FIG. 6, an instruction as to whether or not to perform a plurality of searches with different search conditions may be received from the user. When a multiple search instruction is received, the search condition may be changed according to a predetermined rule, and S17 (recommended route search) shown in FIG. 6 may be performed a plurality of times. For example, each of the case where the above-described priority mode is applied, the case where the above-described priority mode is not applied, and the case where the conversion coefficient is “0”, that is, the correction time of all the links is set to 0 are shown in FIG. May be executed.

  In this case, S18 (recommended route display) shown in FIG. 6 is as follows. That is, S1801 and 1802 in FIG. 10 are executed for the recommended routes searched under the respective search conditions. Then, S1803 in FIG. 10 is executed, and the menu display processing unit 50 sends each recommended route to the display device 2 via the graphics processing unit 51, the estimated travel time, the estimated arrival time, the reliability, and the estimation error. Display as you can see. FIG. 13 shows a modification of the general display example of the recommended route. In this example, for each of a plurality of recommended routes with different search conditions 228, the time 224 and the elapsed time 225 at the departure point 221, the destination 222, and the passing point 223 are the estimated travel time (expected arrival time) of the recommended route. A reliability 226 and an estimation error 227 are displayed.

  Moreover, in said embodiment, the search conditions used in order to determine the traffic information statistical value used for cost calculation are not limited to the kind of day. For example, the type of weather may be used instead of the type of day, or a combination thereof may be used.

  In the above embodiment, the travel time of the traffic information statistical value of the link is used for the cost calculation of the link. However, the present invention is not limited to this. For example, a reception device that receives real-time traffic information such as VICS information may be connected to the navigation device, and the travel time indicated by the traffic information received from the reception device may be used as the travel time of the link.

  In the above embodiment, an example in which the present invention is applied to a vehicle-mounted navigation device has been described. However, the present invention can also be applied to a navigation device other than a vehicle-mounted navigation device.

FIG. 1 is a schematic diagram of an in-vehicle navigation system to which an embodiment of the present invention is applied. FIG. 2 is a diagram illustrating a configuration example of map data stored in the storage device 3. FIG. 3 is a diagram illustrating a configuration example of statistical traffic data stored in the storage device 3. FIG. 4 is a diagram illustrating a hardware configuration of the arithmetic processing unit 1. FIG. 5 is a diagram showing a functional configuration of the arithmetic processing unit 1. FIG. 6 is a flowchart for explaining the recommended route search operation of the in-vehicle navigation device to which the present embodiment is applied. FIG. 7 is a diagram illustrating an example of the conversion coefficient reception screen. FIG. 8 is a flowchart for explaining the recommended route search processing in S18 of FIG. FIG. 9 is a diagram illustrating an example of a heap table. FIG. 10 is a flowchart for explaining the recommended route display processing in S19 of FIG. FIG. 11 shows a general display example of the recommended route. FIG. 12 shows a map display example of the recommended route. FIG. 13 shows a modification of the general display example of the recommended route.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 ... Arithmetic processing part, 2 ... Display apparatus, 3 ... Memory | storage device, 4 ... Voice input / output device, 5 ... Input device, 6 ... Wheel speed sensor, 7 ... Geomagnetic sensor, 8 ... Gyro sensor, 9 ... GPS receiver, 11 ... In-vehicle LAN device, 21 ... CPU, 22 ... RAM, 23 ... ROM, 24 ... DMA, 25 ... Drawing controller, 26 ... VRAM, 27 ... Color palette, 28 ... A / D converter, 29 ... SCI, 30 ... PIO, 31 ... counter, 41 ... user operation analysis unit, 42 ... route search unit, 43 ... route storage unit, 44 ... route guidance unit, 45 ... map display processing unit, 46 ... current position calculation unit, 47 ... map match processing 48, data reading unit, 49 ... locus storage unit, 50 ... menu display processing unit, 51 ... graphics processing unit

Claims (9)

A navigation device route search method,
The navigation device stores link data including a travel distance of each link constituting a road on a map and statistical data including a travel time determined from a statistical value of traffic information collected in the past of each link. A storage device,
A setting step for setting the starting point and destination of the route to be searched;
Using the link data and statistical data stored in the storage device, searching for a recommended route between the departure place and the destination, and
The route search step includes:
For each candidate link of the link that constitutes the recommended route, a correction that is a time obtained from the travel time of the candidate link included in the statistical data and the travel distance of the candidate link included in the link data A route search method for a navigation device, wherein a value corresponding to a total value with time is determined as a cost for route search for the candidate link. A navigation device route search method according to claim 1,
The statistical data includes a travel time for each link time zone,
The setting step sets a departure time in addition to the departure place and the destination,
The route search step calculates an expected arrival time zone of the candidate link using the departure time and a travel time in each expected arrival time zone of each link from the departure place to the candidate link, and the candidate link The route search method for a navigation device, wherein the calculated travel time in the predicted arrival time zone is adopted as the travel time of the candidate link included in the statistical data. A route search method for a navigation device according to claim 1 or 2,
The link data includes road attributes of the links,
The route search step calculates a correction time from a travel distance of the candidate link included in the link data using a conversion coefficient corresponding to a road attribute of the candidate link included in the link data. A route search method of a navigation device characterized by the above. A navigation device route search method according to claim 3,
The route search method for a navigation device, wherein the conversion coefficient is set so as to change a correction time according to a road width indicated by the road attribute. A navigation device route search method according to claim 4,
The route search method for a navigation device, wherein the conversion factor is set such that the correction time decreases as the road width indicated by the road attribute increases. A navigation device route search method according to claim 3,
The navigation device further performs a mode designation receiving step of receiving a designation of a priority mode for performing a route search by giving priority to a predetermined type of road from the user via the input device,
In the route search step, when the priority mode is designated in the mode designation step, the road type indicated by the road attribute of the candidate link included in the link data is the predetermined type. The correction time is calculated from the travel distance of the candidate link included in the link data using a conversion coefficient set so that the correction time is shorter than that of a road of a type other than the type. A route search method for a navigation device. A route search method for a navigation device according to claim 3,
The navigation device further performs a coefficient receiving step of receiving a conversion coefficient from the user via the input device,
The route search method of the navigation device, wherein the route search step calculates a correction time from a travel distance of the candidate link included in the link data, using the conversion coefficient received in the coefficient reception step. . A navigation device,
Storage means for storing link data including travel distance of each link constituting a road on a map, and statistical data including travel time determined from statistical values of traffic information collected in the past of each link;
Setting means for setting the starting point and destination of the route to be searched;
Using the link data and statistical data stored in the storage means, and a route search means for searching for a recommended route between the departure place and the destination set by the setting means,
The route search means includes
For each candidate link of the link that constitutes the recommended route, a correction that is a time obtained from the travel time of the candidate link included in the statistical data and the travel distance of the candidate link included in the link data A navigation device characterized in that a value corresponding to a total value with time is determined as a cost for route search of the candidate link. A navigation device,
Storage means for storing link data including travel distance and road attributes of each link constituting a road on a map, and statistical data including travel time determined from statistical values of traffic information collected in the past of each link; ,
A conversion coefficient for calculating a correction time from the travel distance of the link data and a coefficient input screen for receiving a correction coefficient for correcting the conversion coefficient according to a road attribute are displayed, and the conversion coefficient is displayed by the user. And coefficient receiving means for receiving the setting of the correction coefficient,
For each candidate link of the link constituting the recommended route, the travel time of the candidate link included in the statistical data, the travel distance of the candidate link included in the link data, received by the coefficient receiving unit Using the conversion coefficient and the correction coefficient according to the road attribute of the candidate link included in the link data received by the coefficient receiving means, the cost of the candidate link is calculated, and each candidate link is calculated. And a route search means for determining each link constituting the recommended route using the cost of the navigation device.

Images