JP5925354B2 - Route search system, route search method, and program - Google Patents

Description

  The present invention relates to a route search device, a route search system, a server device, a terminal device, a route search method, and a program.

  Conventionally, there is a technique for searching for a stopover along the route.

  For example, Patent Documents 1 and 2 disclose a technique for searching for a stopover location existing within a predetermined distance or a predetermined time range from a route from a departure place to a destination.

  Further, in Patent Document 3, a technique for calculating a loss time by comparing a detour time required to reach a destination from a current position via a stop and a required time when not passing through the stop. Is disclosed.

Japanese Patent No. 3242968 JP 2002-257567 A Japanese Patent No. 3161276

  However, the conventional technique for searching for a stopover point (a stopover point in the middle of the route) has a problem that an appropriate stopover point cannot be searched efficiently.

  For example, the techniques of Patent Documents 1 and 2 have a problem that a route point with a short loss time is not searched although it is outside a predetermined range from the route from the starting point to the destination.

  Further, the technique of Patent Document 3 has a problem that the processing time becomes longer in proportion to the number of stop-by places because the route to the destination is searched for each stop-off place. More specifically, as exemplified in Patent Document 3, when the route search is performed using the Dijkstra method, the nodes and links that are sequentially reached are expanded while calculating the link cost with the stop-by point as the reference point. The diffusion process will be performed. When the route search to the destination is executed for each stop, the diffusion process has to be repeated as many times as there are stop points, which increases the processing time.

  The present invention has been made in view of the above problems, and provides a route search device, a route search system, a server device, a terminal device, a route search method, and a program capable of efficiently searching for an appropriate waypoint. The purpose is to provide.

  In order to achieve such an object, in the route search device including at least the storage unit and the control unit of the present invention, the storage unit includes network data storage means for storing network data defining a traffic network, The control unit, based on the network data, the search route from the departure point to a plurality of waypoint candidates of the route search condition including at least a departure point and a destination, and the destination from the destination of the route search condition A route search means for searching for a route by diffusing each search route to a plurality of waypoint candidates one by one, and the destination from the departure point to the destination via the route point candidate searched by the route search means And search result information generating means for generating search result information including the above route.

  In the route search device according to the present invention, in the route search device described above, the storage unit further includes a point information storage unit that stores point information regarding the point, and the control unit includes the point information storage unit. Route point search means for searching for the plurality of route point candidates from the point information, and the route search means is configured to search the route point candidate search means based on the network data. For waypoint candidates, the search route from the starting point of the route search condition to the plurality of waypoint candidates, and the search route from the destination of the route search condition to the plurality of waypoint candidates, It is characterized by diffusing once each.

  The route search device according to the present invention is the route search device described above, wherein the waypoint search means diffuses the search route from the departure place and the search route from the destination by the route search means. In this case, the waypoint candidates in the vicinity of the search route to be diffused are searched from the point information storage means.

  The route search device according to the present invention is the route search device described above, wherein the network data storage means includes the network data in a lower hierarchy that defines the detailed traffic network of the traffic network, and the main data Storing the layered network data including the upper layer network data defining a traffic network, and the route search means includes the search route from the departure point to the plurality of waypoint candidates and the purpose Before the search route from the ground to the plurality of waypoint candidates is diffused, the search route is diffused from the plurality of waypoint candidates based on the network data of the lower layer.

  The route search device of the present invention is the route search device described above, wherein the route search means further searches for a route by diffusing the search route from the starting point to the destination in the route search condition. The search result information generation means includes the route searched from the departure place to the destination, and the route from the departure place to the destination via the waypoint candidate. The search result information including a comparison result obtained by comparing, is generated.

  In the route search device according to the present invention, in the route search device described above, the control unit further includes current position information acquisition means for acquiring current position information indicating a current position of the moving body, and the route search means. Performs a route search using the current position of the current position information acquired by the current position information acquisition means as the starting point of the route search condition.

  Further, the route search device according to the present invention is the route search device described above, wherein the control unit further includes traffic information acquisition means for acquiring traffic information indicating occurrence of traffic jams expected for each time point, The route search means calculates an expected arrival time to the destination based on the searched route from the departure point to the waypoint candidate and the route from the destination to the waypoint candidate, and the congestion information Based on the above, the expected arrival time is corrected.

  The route search device according to the present invention further includes an output unit in the route search device described above, wherein the control unit sets a route search condition for setting the route search condition including at least the departure place and the destination. And a search result output means for outputting the search result information generated by the search result information generation means to the output unit.

  Further, the route search system of the present invention is a route search system in which a server device including at least a storage unit and a control unit, and a terminal device including at least an output unit and a control unit are connected to be able to communicate with each other. The storage unit of the server device includes network data storage means for storing network data defining a traffic network, and the control unit of the server device transmits at least a starting point and a destination transmitted from the terminal device. A route search condition receiving means for receiving a route search condition including the search route from the starting point to a plurality of waypoint candidates of the route search condition received by the route search condition receiving means based on the network data; And the search route from the destination of the route search condition to the plurality of waypoint candidates is spread once each. Route search means for searching for a route; search result information generation means for generating search result information including the route from the departure place to the destination via the waypoint candidate searched by the route search means; Search result information transmitting means for transmitting the search result information generated by the search result information generating means to the terminal device, wherein the control unit of the terminal device sets the route search condition to the server device. The search result information transmitted by the server device, the search result information receiving means for receiving the search result information transmitted from the server device, and the search result information received by the search result information receiving means And a search result information output means for outputting to the section.

  Further, the route search system of the present invention includes a network data storage means for storing network data defining a traffic network, and a plurality of route search conditions including at least a departure place and a destination based on the network data. A route search means for searching for a route by diffusing each of the search route to the route point candidate and the search route from the destination of the route search condition to the plurality of route point candidates, and the route Search result information generating means for generating search result information including the route from the starting point to the destination via the waypoint candidate searched by the searching means.

  The server device of the present invention is a server device including at least a storage unit and a control unit, which is communicably connected to a terminal device including at least an output unit, wherein the storage unit is a network that defines a traffic network. Network data storage means for storing data, and the control section receives route search condition receiving means for receiving a route search condition transmitted from the terminal device and including at least a starting point and a destination, and the network data Based on the search route from the departure point to the plurality of waypoint candidates of the route search condition received by the route search condition receiving unit, and from the destination of the route search condition to the plurality of waypoint candidates The route search means for searching for the route by diffusing each of the search routes once and the above-mentioned route search means for searching for the route. Search result information generating means for generating search result information including the route from the ground to the destination via the waypoint candidate, and the search result information generated by the search result information generating means, the terminal device And a search result information transmitting means for outputting to the output unit of the terminal device.

  The terminal device according to the present invention is a terminal device including at least an output unit and a control unit, which is communicably connected to a server device including at least a storage unit, wherein the storage unit is a network that defines a traffic network. Network data storage means for storing data, and the control unit is transmitted from the server device, route search condition transmission means for transmitting a route search condition including at least a starting point and a destination to the server device, The search route from the starting point to the plurality of waypoint candidates of the route search condition received by the route search condition receiving means, and the search route from the destination to the plurality of waypoint candidates of the route search condition , Each of which is searched based on the network data once, and then the purpose from the starting point through the way point candidate Search result information receiving means for receiving the search result information including the route up to, and search result information output means for outputting the search result information received by the search result information receiving means to the output unit. It is characterized by having.

  The route search method of the present invention is a route search method executed in a route search device having at least a storage unit and a control unit, and the storage unit stores network data that defines a traffic network. A search route from the starting point to a plurality of waypoint candidates in a route search condition including at least a starting point and a destination based on the network data, the data storing unit, and executed in the control unit; and A route search step for searching for a route by diffusing each of the search routes from the destination of the route search condition to the plurality of waypoint candidates one by one, and the departure place searched in the route search step A search result information generating step for generating search result information including the route from the route point to the destination via the waypoint candidate. The features.

  The route search method of the present invention is executed in a route search system in which a server device including at least a storage unit and a control unit and a terminal device including at least an output unit and a control unit are communicably connected. A route search method, wherein the storage unit of the server device includes network data storage means for storing network data defining a traffic network, and is executed in the control unit of the terminal device, A route search condition transmitting step for transmitting a route search condition including at least a destination to the server device, and a route for receiving the route search condition transmitted from the terminal device, executed in the control unit of the server device Based on the network data executed in the search condition receiving step and the control unit of the server device, The search route from the departure place to the plurality of waypoint candidates of the route search condition received in the route search condition reception step, and the search from the destination to the plurality of waypoint candidates of the route search condition The route search step for searching for a route by diffusing the route once each and the route point candidate searched from the departure location, which is searched for in the route search step executed in the control unit of the server device. The search result information generation step for generating search result information including the route to the destination via the search result information generated in the search result information generation step executed in the control unit of the server device A search result information transmission step for transmitting information to the terminal device, and transmission from the server device executed in the control unit of the terminal device The search result information receiving step for receiving the search result information and the search result information received in the search result information receiving step executed in the control unit of the terminal device are output to the output unit. And a search result information output step.

  The route search method of the present invention is a route search executed in a route search system comprising network data storage means for storing network data defining a traffic network, route search means, and search result information generation means. The route search means includes, based on the network data, a search route from the departure place to a plurality of waypoint candidates in the route search condition including at least a departure place and a destination, and the route search condition. The route search step for searching the route by diffusing each of the search routes from the destination to the plurality of waypoint candidates once and searching for the route, and the search result information generating means were searched in the route search step. A search result information generation step for generating search result information including the route from the departure point to the destination via the route candidate. Characterized in that it comprises a flop, a.

  The route search method of the present invention is a route search method executed in a server device having at least a storage unit and a control unit, which is communicably connected to a terminal device having at least an output unit, The storage unit includes network data storage means for storing network data that defines a traffic network, and transmits route search conditions including at least a departure point and a destination transmitted from the terminal device, which are executed in the control unit. A route search condition reception step to be received, a search route from the departure place to a plurality of waypoint candidates of the route search condition received in the route search condition reception step based on the network data, and the route The search route from the destination in the search conditions to the plurality of waypoint candidates is searched once by diffusing each time once. A search step, a search result information generation step for generating search result information including the route from the departure point to the destination via the waypoint candidate, searched in the route search step, and the search result A search result information transmitting step of transmitting the search result information generated in the information generating step to the output unit of the terminal device by transmitting the search result information to the terminal device.

  The route search method of the present invention is a route search method executed in a terminal device having at least an output unit and a control unit, which is communicably connected to a server device having at least a storage unit. The storage unit includes network data storage means for storing network data that defines a traffic network, and is configured to execute a route search for transmitting a route search condition including at least a starting point and a destination to the server device, which is executed in the control unit. A search route from the departure point to a plurality of waypoint candidates of the route search condition received at the route search condition reception step, transmitted from the server device, and the route search condition The search route from the destination to the plurality of waypoint candidates is diffused once each based on the network data. The search result information including the route from the departure place to the destination via the waypoint candidate is received, and the search result information reception step and the search result information reception step receive the search result information. And a search result information output step of outputting search result information to the output unit.

  The program of the present invention is a program for causing a route search device including at least a storage unit and a control unit to execute the network data storage unit that stores network data defining a traffic network. In the control unit, based on the network data, a search route from the departure place to a plurality of waypoint candidates of the route search condition including at least a departure place and a destination, and the route search condition A route search step for searching for a route by diffusing each of the search routes from the destination to the plurality of route point candidates once, and the route point candidates from the departure point searched in the route search step. A search result information generation step for generating search result information including the route to the destination via To.

  Further, the program of the present invention is a program for causing a server device including at least a storage unit and a control unit, connected to a terminal device including at least an output unit to be communicable, the storage unit including: Network data storage means for storing network data defining a traffic network, and receiving route search conditions received at the control unit from the terminal device, the route search conditions including at least a departure place and a destination And a search route from the departure point of the route search condition received in the route search condition reception step to a plurality of waypoint candidates based on the network data, and the destination of the route search condition Route search step for searching for a route by diffusing each of the search routes from the route point candidates to the plurality of waypoint candidates once A search result information generation step for generating search result information including the route from the departure point to the destination via the waypoint candidate, searched in the route search step, and the search result information generation step Transmitting the search result information generated in step S1 to the terminal device, thereby causing the output unit of the terminal device to output the search result information transmission step.

  Further, the program of the present invention is a program for causing a terminal device including at least an output unit and a control unit connected to a server device including at least a storage unit to be able to communicate, wherein the storage unit includes: A network data storage means for storing network data defining a traffic network, and in the control unit, a route search condition transmitting step for transmitting a route search condition including at least a starting point and a destination to the server device; and A search route from the starting point of the route search condition received in the route search condition receiving step to a plurality of waypoint candidates transmitted from the server device, and the plurality of destinations from the destination of the route search condition The search route to the waypoint candidates of the above is searched by diffusing once each based on the above network data. The search result information including the search result information including the route from the departure point to the destination via the waypoint candidate, and the search result information received in the search result information reception step. And a search result information output step for outputting to the output unit.

  According to the present invention, network data defining a traffic network is stored, and based on the network data, a search route from a starting point of a route search condition including at least a starting point and a destination to a plurality of waypoint candidates, and The search route from the destination of the route search condition to the plurality of waypoint candidates is searched once by diffusing each time, and the route from the departure point to the destination via the waypoint candidate is searched. The search result information including is generated. Thereby, this invention has an effect that it can search an appropriate waypoint efficiently. More specifically, even if the route is not within a predetermined distance or predetermined time range from the route from the departure point to the destination, an appropriate waypoint with a short loss time, an additional distance, or the like can be searched. Also, instead of performing a route search for each waypoint, it is possible to execute a route search for a plurality of waypoints by spreading the search route once, so that the processing time can be shortened and efficiently searched. Can do.

  Further, according to the present invention, in the above, the point information regarding the point is further stored, a plurality of waypoint candidates are searched from the point information, and the route information is searched for the plurality of waypoint candidates searched based on the network data. The search route from the starting point of the search condition to the plurality of waypoint candidates and the search route from the destination of the route search condition to the plurality of waypoint candidates are each diffused once. Thereby, this invention has an effect that a suitable waypoint candidate can be selected from the point information memorize | stored beforehand.

  Further, according to the present invention, when the search route from the departure place and the search route from the destination are diffused by the route search in the above, the waypoint candidates near the spread search route are searched from the point information. To do. Accordingly, the present invention has an effect that a suitable waypoint candidate can be searched along the searched route while searching for a route from the departure place to the destination.

  Further, according to the present invention, in the above, a hierarchical layer including lower layer network data that defines a detailed traffic network and upper layer network data that defines a main traffic network in the traffic network. Before storing the network data and spreading the search route from the departure point to a plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates, the network data of the lower layers from the plurality of waypoint candidates The search route is spread based on As a result, the present invention directly connects the route to the main traffic network when searching the route using the main traffic network using the network data of the upper layer from the periphery of the departure place to the periphery of the destination. Even if it is not done, there is an effect that it is possible to connect to the main transportation network around the transit point using a detailed transportation network.

  Further, according to the present invention, in the above, the search route from the starting point to the destination in the route search condition is further diffused to further search the route, and the searched route from the starting point to the destination, and from the starting point Search result information including a comparison result comparing the route to the destination via the waypoint candidate is generated. As a result, the present invention can provide the user with easy-to-understand comparison results such as distance and required time in the route from the departure point to the destination depending on whether or not the route is routed. There is an effect.

  Further, according to the present invention, in the above, the current position information indicating the current position of the moving body is acquired, and the current position of the acquired current position information is used as a starting point of the route search condition. There is an effect that an appropriate waypoint candidate can be presented to the user in real time according to the update of the current position.

  Further, according to the present invention, in the above, traffic information indicating the occurrence of traffic jams predicted for each point of time is acquired, and the route from the searched departure point to the waypoint candidate and the destination to the waypoint candidate An expected arrival time to the destination is calculated based on the route, and the expected arrival time is corrected based on the traffic jam information. As a result, the present invention determines the expected arrival time that does not take into account the traffic jam that is necessary to calculate the expected arrival time that takes into account the traffic jam based on the traffic jam information, and spreads the bidirectional search route between the departure point and the destination. And the expected arrival time can be calculated accurately.

  Further, according to the present invention, in the above, the route search condition including at least the departure place and the destination is further set, and the generated search result information is output to the output unit. There is an effect that the search result information generated based on the route search condition can be output by setting the route search condition including the route search condition.

FIG. 1 is a block diagram illustrating an example of a configuration of a route search system according to the first embodiment. FIG. 2 is a flowchart illustrating an example of basic processing of the route search system according to the first embodiment. FIG. 3 is a diagram schematically showing a route search result by bidirectional diffusion and a normal route search result. FIG. 4 is a diagram schematically illustrating an example in which route search is performed using hierarchical network data. FIG. 5 is a flowchart illustrating an example of a specific process of the route search system according to the first embodiment. FIG. 6 is a diagram illustrating an example of an entry point search condition input screen displayed by the route search condition setting unit 102b. FIG. 7 is a diagram showing an example of an input screen for a transit point (POI) search condition (area search condition) displayed by the route search condition setting unit 102b. FIG. 8 is a diagram showing an example of an input screen for a transit point (POI) search condition (neighboring search condition) displayed by the route search condition setting unit 102b. FIG. 9 is a flowchart showing an example of route search processing by bidirectional diffusion. FIG. 10 is a diagram illustrating an example of a display screen generated by the search result information generation unit 202d. FIG. 11 is a diagram illustrating an example of a display screen on which a plurality of waypoint candidates generated by the search result information generation unit 202d are superimposed. FIG. 12 is a block diagram illustrating an example of a configuration of the route search apparatus 400 according to the second embodiment. FIG. 13 is a flowchart illustrating an example of processing of the route search apparatus 400 according to the second embodiment.

  Hereinafter, embodiments of a route search system, a server device, a terminal device, a route search device, a route search method, and a program according to the present invention will be described in detail with reference to the drawings. Note that the present invention is not limited to the embodiments.

  Hereinafter, the configuration and processing of the present invention will be described in detail in the order of the first embodiment (route search system) and the second embodiment (route search device (stand-alone type)).

[First Embodiment]
First, a first embodiment (route search system) of the present invention will be described below with reference to FIGS. However, the first embodiment described below exemplifies a route search system for embodying the technical idea of the present invention, and is not intended to specify the present invention as this route search system. In addition, the present invention is equally applicable to the route search systems of other embodiments included in the claims. For example, the form of function distribution on the server side and the terminal side in the route search system exemplified in the first embodiment is not limited to the following, and may be functional or physical in arbitrary units as long as similar effects and functions can be achieved. Can be distributed and integrated.

[Configuration of route search system]
First, an example of the configuration of the route search system according to the first embodiment will be described below with reference to FIG. Here, FIG. 1 is a block diagram showing an example of the configuration of the route search system in the first embodiment, and conceptually shows only the portion related to the present invention in the configuration. In the first embodiment, a route search system that provides communication-type navigation will be described as a specific example. However, the present invention is not limited to this, and can also be applied to a stand-alone type route search system. .

  As shown in FIG. 1, the route search system of the first embodiment is generally configured by connecting a server device 200, a terminal device 100, and an external device 600 so that they can communicate with each other. Here, as shown in FIG. 1, the communication includes, as an example, remote communication such as wired / wireless communication via a network 300.

  As illustrated in FIG. 1, in the route search system according to the first embodiment, the server device 200 schematically includes at least a control unit 202 and a storage unit 206, and the terminal device 100 includes a position acquisition unit 112. An output unit 114, an input unit 116, a storage unit 106, and a control unit 102. Each part of the route search system is communicably connected via an arbitrary communication path.

[Configuration of Server Device 200]
Here, in FIG. 1, the server device 200 receives a route search condition including at least a departure place and a destination transmitted from the terminal device 100, and starts from the departure place of the received route search condition based on network data. The search route to a plurality of waypoint candidates and the search route from the destination of the route search condition to the plurality of waypoint candidates are each diffused once to search for a route, It has functions such as generating search result information including a route to a destination via a waypoint candidate and transmitting the generated search result information to the terminal device 100. The server device 200 is connected to the terminal device 100 and the external device 600 via the communication control interface unit 204 via the network 300 so as to be able to communicate with each other, and includes a control unit 202 and a storage unit 206. The network 300 has a function of mutually connecting the terminal device 100, the server device 200, the external device 600, and the like. For example, the Internet, a telephone line network (such as a mobile terminal line network and a general telephone line network), It may be an intranet or power line communication (PLC).

  The control unit 202 is a control unit that performs various processes. The communication control interface unit 204 is an interface connected to a communication device (not shown) such as an antenna or a router connected to a communication line or a telephone line, and performs communication control between the server device 200 and the network 300. Has the function to perform. That is, the communication control interface unit 204 has a function of communicating data with the terminal device 100, the external device 600, and the like via a communication line. The storage unit 206 is a storage unit such as a fixed disk device such as an HDD (Hard Disk Drive) or an SSD (Solid State Drive), and includes various databases and tables (a network database 206a, a map database 206b, a POI database 206c, and A traffic jam information database 206d, etc.).

  Among these components of the storage unit 206, the network database 206a is a network data storage unit that stores network data that defines a traffic network. Here, the network data stored in the network database 206a may be traffic network data of transportation such as route network data in addition to road network data. Here, the network data stored in the network database 206a may be hierarchical network data. For example, in the traffic network, lower-layer network data that defines a detailed traffic network and main traffic Network data of an upper layer that defines a network. As an example, the hierarchized road network data stored in the network database 206a specifies lower-level network data that defines a detailed traffic network including a narrow alley and the main traffic network including a main road. It may also include higher layer network data. The hierarchies may be classified by road thickness (width, etc.), speed limit, etc., and are not limited to two hierarchies, and there may be a plurality of three or more hierarchies. Further, the upper and lower levels of the hierarchy are relative to each other in a plurality of hierarchies, and are not absolute. That is, the middle hierarchy is a lower hierarchy when viewed from the upper hierarchy, and is an upper hierarchy when viewed from the lower hierarchy. These network data are stored in advance in the network database 206a, and the control unit 202 of the server device 200 periodically and / or according to processing by the control unit 202 (for example, data is required in the control unit 202). The latest data is downloaded from the external device 600 (for example, a network data server that provides network data) via the network 300, and the network data stored in the network database 206a is updated. Good.

  Here, the road network data stored in the network database 206a is network data that defines the road network. For example, the node data of nodes that are nodes on the road network representation such as intersections and branch points, and between nodes Network data expressed by a combination with link data of a link that is a road section. The node data may include node coordinates, position coordinates such as latitude and longitude, node type, the number of links to be connected, connection node numbers, vehicle stop positions such as traffic lights and stop signs, intersection names, and the like. The link data includes link number, type of road to be connected, route number of national road, prefectural road, city road, etc., important route information, attribute information of administrative area where link exists, link length, road service status, abnormal Traffic restrictions such as traffic restrictions, vehicle weight restrictions, vehicle height restrictions, width, road width classification, number of lanes, speed limit, vehicle stop positions immediately before stop signs and railroad crossings, links such as overpasses, tunnels and bridges An internal attribute, required time, name, and the like may be included. In particular, the link data may include the link cost of the link. For example, the link data may include data related to charges such as time, distance, and usage fee data required to pass the road link. . The road network data may include traffic regulation data, usage fee data, and the like. Here, the traffic regulation data is data that defines various traffic regulations. For example, traffic regulation data such as roads that are damaged or road construction, traffic zones, and community zones that are installed to ensure traffic safety. Information such as prohibition of entry of vehicles and prohibition of entry of ordinary vehicles due to a connection path to private land may be included. In addition, the usage fee data may be information indicating fuel charges consumed when traveling by car, motorcycle, etc., tolls for toll roads such as national highways and roads for automobiles, and the like. Further, the road network data may store position information such as latitude and longitude information of points such as facilities existing on a route when moving by car, motorcycle, bicycle, walking, or the like. In the network data, evaluation information may be stored in association with the node number, the link number, or the like in order to evaluate each guide route composed of nodes and links. As an example, traffic regulation data as information for evaluation is data that defines various traffic regulations. For example, it is a community installed to ensure vehicle safety due to road damage or road construction, traffic safety, etc. This includes information such as the prohibition of entry of ordinary vehicles by zones, etc., and the prohibition of entry of ordinary vehicles due to being connected to private land.

  The traffic network data stored in the network database 206a is network data that defines a route network of a transportation facility such as a train or a bus. As an example, the traffic network data may be route network data defining a train route network or route network data defining a bus route network. For example, the traffic network data stored in the network database 206a is network data that defines a route network of each transportation facility such as a train, an airplane, a bus, a tram, a ropeway, a monorail, a cable car, and a ship. Node data of nodes that are nodes on the route network representation such as stop positions such as stations, airports, ports, and stops (bus stops), and railway lines, air routes, routes, and buses connecting the nodes This is network data expressed by a combination with link data of a link such as a route. The node data may include a node number, position coordinates such as latitude and longitude, a node type, the number of links to be connected, a connection node number, and a station name at which a track intersects. Link data includes link number, type of station to be connected, route number of train, etc., important route information, attribute information of administrative area where the link exists, link length, road service status, abnormal weather traffic regulation It may include traffic restrictions such as sections, vehicle weight restrictions, vehicle height restrictions, width, road width classification, number of lanes, speed limit, in-link attributes such as overpasses, tunnels and bridges, and names. Moreover, the traffic network data may include transportation fare fee data, boarding position data, and the like. Here, the use fare charge data is, for example, information indicating the use charge, etc. generated when using each transportation such as a train, an airplane, a bus, a streetcar, a ropeway, a monorail, a cable car, and a ship. May be.

  The map database 206b is map data storage means for storing map data. As an example, the map data stored in the map database 206b may be map data such as road maps of the whole country and each region. For example, the map data stored in the map database 206b includes features displayed on the map (for example, buildings such as buildings, houses and stations, roads, railroads, bridges, tunnels, contour lines, coast lines, lake shore lines, etc. Shape data on the shape of water lines, seas, rivers, lakes, ponds, swamps, places such as parks and outdoor facilities, administrative boundaries, administrative districts, and city blocks, etc., and notes displayed on the map (eg, place names) , Address, telephone number, facility name of shops, parks, stations, etc., names including landmarks, historic sites, rivers, lakes, bays, mountains, forests, etc., names of roads, bridges, tunnels, route names, point information , And word-of-mouth information, etc., and symbols displayed on the map (for example, map symbols such as mountains, historic sites, temples, schools, hospitals, factories and cemeteries, gas stations, convenience stores, supermarkets, restaurants) Store symbols such as banks and post offices, road signals, toll road entrances, toll gates, service areas, parking areas and interchange symbols, parking lots, station, hotel, museum and facility symbols, and It may include data such as symbol data of a review point symbol). The map data is not limited to map data such as a road map, but may be map data such as a route map. Here, the map data may be map data meshed according to a scale (for example, JIS standard first to third region division mesh data, 100 m mesh data, etc.) and the like. Further, the map data may be map drawing image data such as a raster format or a vector format. These map data are stored in advance in the map database 206b, and the control unit 202 of the server device 200 periodically and / or according to processing by the control unit 202 (for example, data is required in the control unit 202). Update the map data stored in the map database 206b by downloading the latest data from the external device 600 (external device such as a map providing server that provides the map data) via the network 300. May be.

  The POI database 206c is point information storage means for storing point information related to POI and the like. Here, in the present embodiment, a POI (point of interest) is a specific point, facility, area, or the like perceived by a person as a convenient place or a place of interest, such as a building, facility, or store. It may be a point such as a company, office, public facility, entertainment facility, outdoor facility, sightseeing spot or scenic spot, or a feature or area. In other words, in the present embodiment, the POI database 206c stores POI information including POI point information. The POI information includes at least POI point information (latitude and longitude, etc.), POI name (point name), attributes such as category (type), address, telephone number, URL, business hours information, handling product information, and photo data. , Coupon information, word-of-mouth information, use conditions, availability, facility scale information, latitude / longitude altitude of POI, POI ID, and update date / time of the POI information may be included. Here, the stores include, for example, restaurants, grocery stores, liquor stores, tobacco stores, department stores, shopping centers, supermarkets, convenience stores, gas stations, financial institutions, post offices, multi-storey parking lots, hotels and inns, etc. It may be an accommodation facility. The public facility may be, for example, a government office, a police station, a police box, a fire station, a station, a medical institution, a museum, a museum, a school, and the like. The entertainment facility may be, for example, a movie theater, a theater, an amusement park, a pachinko parlor, a casino, a racetrack or the like. The outdoor facility may be a bus terminal, a park, an amusement park, a campsite, a communication passage, an outdoor parking lot, a zoo, or the like. The POI information is stored in advance in the POI database 206c, and the control unit 202 of the server apparatus 200 periodically and / or according to processing by the control unit 202 (for example, data is required in the control unit 202). Update the POI information stored in the POI database 206c by downloading the latest data from the external device 600 (for example, a facility information providing server that provides POI information) via the network 300. Also good.

  The traffic jam information database 206d is traffic information storage means for storing traffic jam information. Here, the traffic jam information is information indicating the occurrence of traffic jam expected for each point at every time. As an example, the traffic jam information may include a time when traffic congestion is predicted to occur in association with a link ID on the road. Further, the traffic jam information may include traffic jam information such as a traffic jam occurrence point, a traffic jam distance, and a transit time between two locations on the road (that is, travel time, etc.). Here, the traffic jam information may include traffic obstacle information, traffic regulation information, and operation information of transportation facilities such as railways. Here, the traffic regulation information is data defining various traffic regulations.For example, traffic regulation during abnormal weather such as precipitation regulation, snow cover / freezing regulation, ultrasonic regulation, wind speed regulation, visibility regulation, etc., height Vehicle traffic regulations such as regulations and weight regulations, road construction and work, regulations during construction around roads, traffic zones that regulate traffic zones that can pass by time zone and vehicle type, and vehicle traffic due to road damage, etc. It may also include information such as a general vehicle entry prohibition by a community zone or the like installed to ensure traffic safety, and a general vehicle entry prohibition due to a connection path to private land. Further, the traffic regulation information may be traffic regulation information that makes it impossible or impossible for the vehicle lane to travel due to construction, an accident, or a vehicle failure. Further, the traffic jam information is stored in advance in the traffic jam information database 206d, and the control unit 202 (traffic jam information acquisition unit 202f described later) of the server device 200 periodically scans the network 300 (for example, every 5 minutes). Via the external device 600 (for example, National Police Agency, VICS (registered trademark) (Vehicle Information and Communication System), and ATIS (Advanced Traffic Information Service) (registered trademark), Japan Road Traffic Information Center (JARTIC) (Registered trademark), railway company, traffic information distribution server (service), etc.) and the like, and the traffic information stored in the traffic information database 206d may be updated.

  The control unit 202 has an internal memory for storing a control program such as an OS (Operating System), a program that defines various processing procedures, and necessary data. And the control part 202 performs the information processing for performing various processes with these programs. The control unit 202 functionally conceptually includes a route search condition reception unit 202a, a waypoint candidate search unit 202b, a route search unit 202c, a search result information generation unit 202d, a search result information transmission unit 202e, and a traffic jam information acquisition unit 202f. Is provided.

  Among these, the route search condition reception unit 202a is route search condition reception means for receiving a route search condition transmitted from the terminal device 100 and including at least a departure place and a destination. The route search condition received by the route search condition receiving unit 202a may include current position information. For example, the route search condition receiving unit 202a may acquire the current position based on the current position information of the terminal device 100 received by the current position information receiving unit 202a as the starting point of the route search condition. Further, when the updated current position information transmitted from the terminal device 100 is received, the route search condition receiving unit 202a resets the current position based on the latest current position information as the starting point of the route search condition. May be.

  The waypoint candidate search unit 202b is a waypoint candidate search means for searching a plurality of waypoint candidates from POI point information (POI information) stored in the POI database 206c. Here, the route search unit 202c diffuses the search route from the departure point and the search route from the destination of the route search condition, and at the same time, the waypoint candidate search unit 202b performs POI based on the spread search route. A plurality of POIs near the search route may be searched from the database 206c as a plurality of waypoint candidates. That is, when the route search unit 202c spreads the search route, the waypoint candidate search unit 202b is located on or near the search route being spread based on the POI point information stored in the POI database 206c. An existing POI may be acquired as a waypoint candidate. In addition to the above, the waypoint candidate search unit 202b may be configured such that the starting point of the route search condition, the current position (may be the predicted current position after a predetermined time), the vicinity of the destination (for example, within a predetermined shape range) ) May be retrieved from the POI database 206c. For example, the waypoint candidate search unit 202b may search for a POI located within an ellipse with two points of the starting point and the destination as a waypoint candidate. In addition, when a POI category is specified as a route search condition, the waypoint candidate search unit 202b may perform a search by narrowing down to a POI corresponding to the category.

  The route search unit 202c is route search means for executing a route search based on network data stored in the network database 206a. For example, the route search unit 202c includes a search route from the starting point of the route search condition received by the route search condition reception unit 202a to a plurality of waypoint candidates, and a plurality of waypoints from the destination of the route search condition. The search route to the candidate may be diffused once each to search for the route (in the tree structure data such as network data, the search route may be called a search tree). Looking from the direction from the departure point to the destination, the forward direction is from the departure point to the waypoint, and the reverse direction is from the destination to the waypoint.Therefore, in this embodiment, the route search method is This is called route search by “bidirectional diffusion”. Note that the route search unit 202c is not limited to the route search by bidirectional diffusion, and may perform a normal route search by diffusing the search route from the starting point to the destination of the route search condition. As described above, the route searching unit 202c, when performing a route search by bidirectional diffusion, uses the waypoint candidate searching unit 202b to obtain a POI existing on or near the searched route. You may search as.

  Here, “diffusion” by the route search unit 202c, which is executed in the present embodiment, will be described. In the present embodiment, “diffusion” means that nodes, links, etc. that have arrived sequentially spread in a known route search method such as Dijkstra method or A * (Aster) search algorithm. For example, in the Dijkstra method, from a reference point (generally, a node close to the departure point), the connected link is sequentially traced to reach the next node, and the link cost (distance and required transit) of the traced link is reached. Time), and the search route is expanded to the target point (generally a node close to the destination) while managing the next link group (search route) so that the link cost is minimized. However, expanding this search path is called diffusion. Of course, there are cases where there are branches and three or more links may be connected to one node. Therefore, the search path is not usually one, but a plurality of links whose accumulated link costs are the same (same level). The number of search paths will increase with diffusion. In the above description, as an example of a general search method, an example of performing a route search by normal diffusion from the departure point to the destination has been described. However, in this embodiment, the route search unit 202c is bidirectional. In the route search by diffusion, one diffusion from the departure point (reference point) to a plurality of waypoint candidates (target points) and one time from the destination (reference point) to the plurality of waypoint candidates It is characterized in that each diffusion is performed. Normally, since the target point is one point, the diffusion is terminated when the one point is reached. However, the route search unit 202c does not search until it reaches all the points of the plurality of waypoint candidates. To expand. The diffusion termination condition is not limited to this, and the diffusion link has reached the opposite point (for example, the destination in the case of diffusion from the departure side, the departure point in the case of diffusion from the destination side). It is also possible when a predetermined amount of link cost (time, distance, fee, etc.) is calculated by diffusion after reaching the destination or departure place according to the calculated link cost. May be. Thereby, more POIs etc. can be made into a candidate link.

  In addition, when performing a route search by the Dijkstra method or the like, it is necessary to calculate the link cost for each of the search routes that are spread, and the processing time becomes longer depending on the number of search routes, There is a problem that the processing load of the server apparatus 200 increases. Therefore, around the points such as the starting point, destination, and waypoint candidates, the search route is expanded using lower-layer network data (which defines a detailed road network to narrow alleys). The route search may be performed by extending the search route using the upper layer network data (which defines only the main road network). In particular, when performing a route search by bidirectional diffusion in the present embodiment, the route search unit 202c diffuses a search route from a plurality of waypoint candidates based on lower layer network data before performing bidirectional diffusion. You may let them.

  In addition, the route search unit 202c adds the required time from the departure point to the waypoint calculated by bidirectional diffusion and the required time from the destination to the waypoint, thereby passing the route (candidate) from the departure point. The time required to reach the destination can be calculated. Further, the route search unit 202c may calculate the required time in consideration of the stay time at the waypoint (candidate). For example, when the waypoint (candidate) is a restaurant, one hour may be added to the required time.

  In addition, the route search unit 202c may separately perform a recalculation process of the required time for the route from the departure point to the destination calculated by the bidirectional search. In the case of diffusion from the destination side in the bidirectional diffusion, the time of traffic information to be referred to in each link is unknown, and the accuracy of the required time calculated thereby becomes low. By recalculating “the time required from the departure point to the target node” in order from the departure point side for all the nodes constituting the route from the departure point to the destination point, the passing time at each node can be obtained with high accuracy ( The value obtained by adding “the required time from the departure place to the target node” to the departure time is the passing time of the target node). As a result, it becomes possible to refer to traffic information at an appropriate time in each link, and the accuracy of the required time from the departure point to the destination and the expected arrival time can be increased.

  In addition, the route search unit 202c may predict the predicted transit time of each link from other information when diffusing from the destination side of bidirectional diffusion. As an example, the predicted passage time of the diffusion target link may be determined by subtracting “the required time from the destination to the diffusion target link” from the temporarily estimated arrival time to the destination calculated separately. As an example of a method for calculating the provisional predicted arrival time at the destination, a route search without a stopover from the departure place to the destination is separately performed, and the obtained arrival time is used as the provisional predicted arrival time. Conceivable. As another example, the required time from the departure point to the destination can be calculated by dividing the linear distance from the departure point to the destination by the average travel speed, and the provisional predicted arrival time can be calculated therefrom. Conceivable. Further, the route search unit 202c may calculate a provisional predicted arrival time in consideration of the stay time at the waypoint (candidate). For example, when all the waypoint candidates are restaurants, it may be possible to add one hour to the estimated predicted arrival time.

  The search result information generation unit 202d is search result information generation means for generating search result information including a route from the departure point to the destination via the waypoint candidate searched by the route search unit 202c. For example, the search result information generation unit 202d connects the route from the departure point to the waypoint candidate and the route from the destination to the waypoint candidate, which are searched by bidirectional diffusion, from the departure point. A route to the destination via the waypoint candidate may be generated, and search result information indicating the route may be generated. Here, the search result information generation unit 202d compares the route from the departure point to the destination searched by the route search unit 202c and the route from the departure point to the destination via the waypoint candidate. Search result information including the result may be generated. For example, the search result information generation unit 202d compares the required time of both routes (the required time (that is, loss time) increased compared to the case where the route point candidate is not routed), the distance of both routes, the charge, etc. Search result information indicating the comparison results (difference, ratio, ratio, etc.) may be generated. The search result information generation unit 202d sorts these comparison results in descending or ascending order and displays them in the determined display order (for example, POIs are displayed in order of short loss time). Result information may be generated. In addition, when the number of candidates is a predetermined number or more, the search result information generation unit 202d may generate search result information by performing a filtering process so that only the upper rank is displayed according to the comparison result. In addition, the search result information generation unit 202d may generate search result information including a display screen in which a waypoint candidate is superimposed on the map data stored in the map database 206b. At that time, the search result information generation unit 202d superimposes the starting point, the destination, the route from the starting point to the destination, the route from the starting point to the destination via the waypoint candidate, etc. on the map data. Also good.

  The search result information transmission unit 202e is search result information transmission means for transmitting the search result information generated by the search result information generation unit 202d to the terminal device 100.

  The traffic jam information acquisition unit 202f is traffic jam information acquisition means for acquiring traffic jam information. For example, the traffic jam information acquisition unit 202f periodically (for example, every 5 minutes) sends the latest data via the network 300 to an external device 600 (for example, a traffic jam information distribution server such as the National Police Agency or VICS (registered trademark)). ) Etc., and the traffic information stored in the traffic jam information database 206d may be updated.

[Configuration of Terminal Device 100]
In FIG. 1, the terminal device 100 transmits route search conditions to the server device 200, receives search result information transmitted from the server device 200, and outputs the received search result information to the output unit 114. It has the function of. The terminal device 100 is, for example, a commercially available information processing device such as a desktop or laptop personal computer, a mobile terminal device such as a mobile phone, PHS, or PDA, and a navigation terminal that performs travel route guidance or the like. . Here, the terminal device 100 may be equipped with an Internet browser or the like, or may be equipped with a route guidance application or a transfer guidance application. Further, the terminal device 100 includes a position acquisition unit 112 having a GPS function, an IMES function, and the like so that the current position can be acquired in real time. The terminal device 100 includes at least an output unit 114, an input unit 116, and a control unit 102. Here, the output unit 114 displays search result information received from the server device 200 in addition to display means for displaying a display screen such as display guidance data (for example, a display or a monitor composed of a liquid crystal or an organic EL). Audio output means (for example, a speaker or the like) for outputting as audio may be used. The input unit 116 may be, for example, a key input unit, a touch panel, a keyboard, a microphone, or the like. The input / output control interface unit 108 controls the position acquisition unit 112, the output unit 114, the input unit 116, and the like.

  Here, the position acquisition unit 112 may be, for example, a position acquisition unit that receives a position information signal transmitted from the position transmission device 500. Here, the position transmitting device 500 may be a GPS device that transmits a position information signal (GPS signal), and IMES that enables indoor positioning using a position information signal having characteristics similar to those of the GPS signal. It may be an IMES device that implements (Indoor Message System) technology. The IMES technology is a system developed from the framework of the quasi-zenith satellite, which is a positioning satellite system. Further, the position transmission device 500 may be a GPS repeater that transmits a GPS signal received outdoors indoors. Further, the position transmission device 500 may be a small transmission device that is arbitrarily installed on each floor of a building (for example, a multilevel parking lot) or an underground structure (for example, a tunnel, an underground parking lot). Good. In addition, self-position information (position ID etc.) according to an installation place is allocated to this small transmitter. When the terminal device 100 enters the communicable range, the terminal device 100 receives the self-position information transmitted from the small transmitter as a position information signal. The communication method at this time may be, for example, various short-range wireless methods such as an RFID (Radio Frequency Identification) tag system and Bluetooth (registered trademark), an infrared communication method, and the like. Further, the position transmission device 500 may be a wireless LAN access point. In the present embodiment, the location acquisition unit 112 may receive wireless LAN signals and acquire access point identification information. Then, the control unit 102 may acquire the position information by specifying the position of the access point from the identification information unique to the access point acquired by the position acquisition unit 112. In the present embodiment, the control unit 102 may calculate position information including latitude, longitude, and height information from the position information signal acquired by the position acquisition unit 112. Here, the position information may indicate a relative position from a reference position in addition to the absolute position specified by the latitude and longitude.

  Further, the position acquisition unit 112 detects, for example, the acceleration information of the terminal device 100 detected by the acceleration sensor of the position acquisition unit 112, the direction information such as the traveling direction of the terminal device 100 detected by the direction sensor, and the distance sensor. Position information indicating the current position of the user of the terminal device 100 may be acquired based on the distance information and the map data. Here, a geomagnetic sensor that detects the absolute traveling direction of the terminal device 100 and an optical gyro that detects the relative traveling direction of the terminal device 100 may be used as the direction sensor. In addition, the direction sensor may be an electronic compass that can acquire information on the direction and inclination by combining a geomagnetic sensor and an acceleration sensor.

  The communication control interface unit 104 is an interface connected to a communication device (not shown) such as an antenna or a router connected to a communication line, a telephone line, etc., and communicates between the terminal device 100 and the network 300. It has a function to perform control. That is, the communication control interface unit 104 has a function of communicating data with the server device 200 or the like via a communication line.

  The storage unit 106 is a storage unit such as a large-capacity storage unit such as an HDD or an SSD and / or a small-capacity high-speed memory (for example, a cache memory) configured using an SRAM (Static Random Access Memory) or the like. Various databases, files, and tables may be stored. Here, the storage unit 106 may temporarily store various files such as map information received from the external device 600 or the like, search result information received from the server device 200, or the like.

  The guide data file 106a is guide data storage means for storing guide data. The guidance data stored in the guidance data file 106a is data such as voice guidance data and display guidance data output on the guidance route. Here, the voice guidance data is associated with “turning to the left at the next intersection” associated with the direction of travel at the branching point on the guidance route, or when the current position approaches the destination, The voice guidance data may be based on the route information stored in the search result information by the search result information output unit 102e of the terminal device 100. It may be used when performing route guidance such as voice guidance. The display guidance data is data for display guidance such as a turn-by-turn (TBT) associated with the traveling direction at a branch point on the guidance route or a guidance that the current position is close to the selected facility. The display guidance data may be used when the search result information output unit 102e of the terminal device 100 executes the display guidance. Here, the TBT is an arrow navigation that displays guidance such as a right or left turn on the screen. These guidance data may be received as search result information, or may be stored in advance in the guidance data file 106a. The control unit 102 of the terminal device 100 updates the latest guidance data via the network 300 periodically and / or according to processing by the control unit 102 (for example, when data is required in the control unit 102). May be downloaded from an external device 600 (for example, a guide data providing server that provides guide data) or the like, and the guide data stored in the guide data file 106a may be updated.

  The control unit 102 includes an internal memory for storing a control program such as an OS, a program defining various processing procedures, and necessary data. And the control part 102 performs the information processing for performing various processes by these programs. In terms of functional concept, the control unit 102 includes a current position information acquisition unit 102a, a route search condition setting unit 102b, a route search condition transmission unit 102c, a search result information reception unit 102d, and a search result information output unit 102e.

  Among these, the current position information acquisition unit 102a is current position information acquisition means for acquiring the current position information of the user of the terminal device 100. Here, the current position information acquisition unit 102a may acquire the current position information of the user of the terminal device 100 every predetermined period (for example, every second). Here, the current position information acquisition unit 102a may transmit the acquired current position information to the server device 200 periodically or every update. In addition, the current position information acquisition unit 102 a may acquire the position information calculated from the position information signal received from the position transmission device 500 by the position acquisition unit 112 as the current position information of the user of the terminal device 100. Furthermore, the orientation information such as the traveling direction of the terminal device 100 detected by the orientation sensor of the position acquisition unit 112 and the acceleration information of the terminal device 100 detected by the acceleration sensor of the position acquisition unit 112 are used. May be acquired as the current position information of the person. In addition, the current position information acquisition unit 102a may acquire the position coordinates and the like of the current position input by the user via the input unit 116 as the current position information of the user of the terminal device 100. Here, the current position input by the user via the input unit 116 may be a position where the user actually exists, and a virtual current position arbitrarily selected by the user (for example, Tokyo It may be an arbitrary point such as a station or an airport in Osaka selected by a user in the area. Specifically, the current position information acquisition unit 102a designates on the display screen of the map data displayed on the output unit 114 to the user via the input unit 116 (for example, designation operation on the touch panel type display unit, etc. ) Coordinates may be acquired as the current position information of the user of the terminal device 100. Furthermore, the orientation information specified on the display screen of the map data displayed on the output unit 114 by the user via the input unit 116 may be acquired as the current position information of the user of the terminal device 100. Here, the current position information acquisition unit 102a may acquire the date and time information of acquiring the current position information together with the current position information of the user.

  The route search condition setting unit 102b is route search condition setting means for setting a route search condition including at least a departure place and a destination. Here, the route search condition setting unit 102b may control the user to input route search conditions such as a departure place and a destination via the input unit 116. The route search condition may further include a departure time or an arrival time. Here, the departure time may be the current time. The route search condition may be added with the preference of the waypoint and the route time. For example, the route search condition setting unit 102b allows the user to search for a POI category that is searched as a waypoint candidate via the input unit 116. Etc. may be controlled so as to be designated. The route search condition setting unit 102b may add the current position of the current position information acquired by the current position information acquisition unit 102a to the route search condition, and set the current position as the destination of the route search condition. May be.

  The search result information receiving unit 102d is search result information receiving means for receiving search result information transmitted from the server device 200.

  The search result information output unit 102 e is search result information display means for outputting the search result information received by the search result information receiving unit 102 d to the output unit 114. For example, the search result information output unit 102e may display the search result information on the output unit 114 such as a monitor, or may output the sound to a speaker or the like according to the search result information. The search result information output unit 102e may perform route guidance such as voice guidance by referring to the guidance data stored in the guidance data file 106a in accordance with the route information included in the search result information.

  Above, description of an example of a structure of the route search system in this embodiment is finished.

[Route search system processing]
Next, an example of the basic processing of the route search system according to the present embodiment configured as described above will be described in detail with reference to FIGS. FIG. 2 is a flowchart illustrating an example of basic processing of the route search system according to the first embodiment.

  As shown in FIG. 2, first, the route search condition setting unit 102b of the terminal device 100 allows the user to set a route search condition including at least a departure place and a destination via the input unit 116 (step SA-1). ). Here, the departure location may be the current location of the user of the terminal device 100 based on the current location information acquired by the current location information acquisition unit 102a, and the current location separately from the departure location in the route search condition. These conditions may be added. The route search condition setting unit 102b may allow the user to specify a waypoint preference (for example, a POI category searched as a waypoint candidate) as the route search condition.

  Then, the route search condition transmission unit 102c of the terminal device 100 transmits the route search condition set by the route search condition setting unit 102b to the server device 200 (step SA-2).

  Then, the route search condition receiving unit 202a of the server device 200 receives the route search condition that is transmitted from the terminal device 100 and includes at least the departure place and the destination (step SA-3).

  Then, the waypoint candidate search unit 202b of the server device 200 searches for a plurality of waypoint candidates from the spot information (POI information or the like) stored in the POI database 206c (step SA-4). Here, the waypoint candidate search unit 202b includes predetermined points including a starting point, a current position (may be an expected current position after a predetermined time) of a route search condition received by the route search condition reception unit 202a, a destination, and the like. POIs existing within the shape range of the POI database 206c may be searched. As an example of the predetermined shape range, the waypoint candidate search unit 202b may search for a POI located within an ellipse range with two points of the departure point and the destination as a waypoint candidate. In addition, when a POI category or the like is designated as a route search condition, the waypoint candidate search unit 202b may perform a narrowed search to a POI corresponding to the designated category or the like.

  Then, the route search unit 202c of the server device 200 executes a route search by bidirectional diffusion for a plurality of route point candidates searched by the route point candidate search unit 202b based on the network data stored in the network database 206a. (Step SA-5). Specifically, the route search unit 202c determines the search route from the starting point of the route search condition received by the route search condition reception unit 202a to a plurality of waypoint candidates, and the plurality of destinations from the destination of the route search condition. The search route to the route point candidate is diffused once each, and the route search by bidirectional diffusion is performed. In addition to the route search by bidirectional diffusion, the route search unit 202c may perform a normal route search that diffuses the search route from the departure point to the destination. Here, FIG. 3 is a diagram schematically showing a route search result by bidirectional diffusion and a normal route search result. In FIG. 3, S indicates a departure place, G indicates a destination, and an asterisk indicates a waypoint candidate. In addition, the arrow in the figure indicates the route of the search result, the solid line arrow indicates the route (for example, the shortest route) by the normal route search from the departure point to the destination, and the broken line arrow indicates the bidirectional diffusion. The route from the starting point or destination to the waypoint candidate is shown by the route search.

  As illustrated in FIG. 3, when three waypoint candidates (stop candidate points A to C) are searched by the waypoint candidate search unit 202b, the route search unit 202c determines from the departure point to three waypoint candidates. The route search is performed by diffusing the search route once. That is, the route search unit 202c continues the diffusion process until the search route reaches all three waypoint candidates, and searches for the routes R10 to R12 from the departure point to each waypoint candidate with one diffusion process. Complete. Similarly, the route search unit 202c diffuses the search route once from the destination to three waypoint candidates to obtain routes R20 to R22 from the destination to each waypoint candidate. Note that any of the diffusion processing from the departure point to each waypoint candidate and the diffusion processing from the destination to each waypoint candidate may be performed first, or parallel processing may be performed simultaneously. As shown in FIG. 3, a normal route search may be performed in addition to the route search by bidirectional diffusion, and the route search unit 202c obtains a route R1 by diffusing the search route from the departure point to the destination. May be. If the link cost calculated in the route search is the required time, each shortest time route can be obtained as shown in the time (minutes) attached to each route in FIG. The required link cost may be a distance, a fee, or the like.

  Further, as described in the balloon of FIG. 3, the route search unit 202c searches for the route from the starting point of the route search condition to the waypoint candidate and the destination to the waypoint candidate searched as a result of bidirectional diffusion. The estimated arrival time at the destination may be calculated on the basis of the route (specifically, by adding the time required for both). In addition, when searching for a route from the destination to the waypoint candidate in the reverse direction, the route search unit 202c does not know the time of the traffic jam information to be referred to, and thus calculates the expected arrival time considering the traffic jam as it is. I can't. Therefore, the route search unit 202c recalculates the expected arrival time to the destination by sequentially obtaining the passing time for the nodes from the departure point to the destination for the obtained route. Also good. That is, since the passage time of the target node can be calculated from the departure time and “the required time of the route from the departure place to the target node”, it is possible to obtain traffic information at the correct time from the traffic information database 206d, and as a result A high expected arrival time can be calculated.

  Here, the route search unit 202c may perform route search using hierarchical network data stored in the network database 206a in order to shorten the processing time. That is, in the route search, it is necessary to calculate the link cost for each of the search routes that are diffused. Therefore, if network data that defines all detailed road networks is used, the number of search routes Will explode and increase the processing time. Therefore, the route search unit 202c expands the search route using the network data of the lower layer (specifying a detailed road network up to a narrow alley) in the vicinity of points such as a departure point, a destination, and a waypoint candidate, Between points, the route search may be executed by expanding the search route using network data of the upper layer (specifying only the main road network). In particular, when performing a route search by bidirectional diffusion, the route search unit 202c may diffuse a search route from a plurality of waypoint candidates based on network data of lower layers before performing bidirectional diffusion. . Here, FIG. 4 is a diagram schematically illustrating an example in which a route search is performed using hierarchical network data. As in FIG. 3, S indicates a departure place, G indicates a destination, and a star indicates a waypoint candidate.

  FIG. 4 shows the positional relationship between the departure point, the destination, and the three waypoint candidates, and the relationship between the layers L1 to L3 of the network data used in this positional space. L1 is a relatively lower hierarchy, and L3 is a relatively higher hierarchy. As shown in FIG. 4, the route search unit 202c first spreads the search route from each of the departure point, destination, and waypoint candidates using the network data of L1. Next, the route search unit 202c spreads the search route using the network data of L2 following the search route diffused in L1. When the above preparation is completed, the route search unit 202c attaches a label “search target” to the arrived link (link group constituting the search route). Then, the route search unit 202c diffuses the search route using the network data to be searched in addition to the L3 network data such as the main road when performing the route search by bidirectional diffusion. As a result, even when there is no waypoint candidate near the link of L3, the search route from the starting point or the destination is determined using the network data of the relatively lower layers of L1 and L2, respectively. You can get to the waypoint candidates. In other words, it is possible to reduce the possibility that it becomes impossible to search from the departure point or destination to the waypoint candidate because the level of the road connected to the waypoint candidate is low. On the other hand, since route search is performed using network data of major road networks such as main roads between points other than the starting point, waypoint candidates, and destinations, the route required for the route is short. Candidates can be discovered.

  Returning to FIG. 2 again, the search result information generation unit 202d of the server device 200 generates search result information including the route from the departure point to the destination via the waypoint candidate searched by the route search unit 202c ( Step SA-6). For example, the search result information generation unit 202d connects the route from the departure point to the waypoint candidate and the route from the destination to the waypoint candidate, which are searched by bidirectional diffusion, from the departure point. A route to the destination via the waypoint candidate may be generated, and search result information indicating the route may be generated. In addition, the search result information generation unit 202d may generate search result information including a display screen in which a waypoint candidate is superimposed on the map data stored in the map database 206b. At that time, the search result information generation unit 202d superimposes the starting point, the destination, the route from the starting point to the destination, the route from the starting point to the destination via the waypoint candidate, etc. on the map data. Search result information may be generated.

Here, the search result information generation unit 202d compares the route from the departure point to the destination searched by the route search unit 202c and the route from the departure point to the destination via the waypoint candidate. Search result information including the result may be generated. For example, as shown in FIG. 3 described above, the search result information generation unit 202d determines the difference in required time between both routes, that is, the required time that increases by passing through each waypoint candidate as compared with the case of not passing through ( That is, the loss time may be calculated using the following formula. Then, search result information including a display screen for displaying the loss time as shown in FIG. 3 may be generated.
(Loss time) = (Time required from departure point to waypoint candidate) + (Time required from destination to point candidate)-(Time required from departure point to destination)

  In addition, the search result information generation unit 202d may generate search result information indicating comparison results (difference, ratio, ratio, etc.) of the distances and charges between the two routes. The search result information generation unit 202d sorts these comparison results in descending order or ascending order, and so on, so that the list is displayed in the determined display order (for example, POIs are displayed in order of short loss time). Result information may be generated. The search result information generation unit 202d is not limited to determining the display order based on the comparison result with the route from the departure point to the destination (not via the route point candidate), but from the departure point to the destination. Without searching the route, sort the routes from the departure point to the destination via each waypoint candidate based on the required time, distance, fee, etc., and determine the display order. May be. The search result information generation unit 202d is not limited to sorting, and the search result information generation unit 202d performs a filtering process so that only the higher rank is displayed according to the comparison result when the number of candidates is equal to or greater than a predetermined number. It may be generated.

  Then, the search result information transmission unit 202e of the server device 200 transmits the search result information generated by the search result information generation unit 202d to the terminal device 100 (step SA-7).

  Then, the search result information receiving unit 102d of the terminal device 100 receives the search result information transmitted from the server device 200 (step SA-8).

  Then, the search result information output unit 102e of the terminal device 100 outputs the search result information received by the search result information receiving unit 102d to the output unit 114 (step SA-9). Here, the search result information output unit 102e causes the output unit 114 to display a display screen in which the current position information updated by the current position information acquisition unit 102a is superimposed on the map data or the route included in the search result information. May be. In addition, the search result information output unit 102e is configured so that the current position of the current position information updated by the current position information acquisition unit 102a is within a predetermined range of waypoint candidates included in the search result information or to a route via the waypoint candidate. When approaching a branch point, it may be output by voice or display that there is a candidate for the waypoint. Here, when one waypoint is selected from among a plurality of waypoint candidates via the input unit 116 by the user, the search result information output unit 102e selects the route point selected based on the search result information. Route guidance may be executed according to the route passing through. Note that if the search result information does not store information indicating a route passing through the route, the terminal device 100 requests the information indicating the route (selects the selected route point) by the route search condition transmission unit 102c. Further, a route search condition including the route search condition may be transmitted to the server device 200, and search result information including information indicating the route may be received from the server device 200. At that time, the route search unit 202c of the server device 200 may perform the route search again for the selected waypoint in order to increase the accuracy of the route search. That is, as described above in the route search (SA-5) by bidirectional diffusion described above, the route search is performed in the opposite direction from the destination toward the waypoint candidate. If the route is not recalculated, the accuracy is inferior. Therefore, the route search unit 202c obtains the transit time in order for the nodes from the departure point to the destination with respect to the searched route from the departure point to the destination via the selected waypoint, The predicted arrival time to the destination with higher accuracy may be recalculated. At that time, the staying time at the waypoint may be taken into account. For example, when the waypoint is a restaurant, one hour may be added to the required time.

  In the present embodiment, control may be performed so that the processes in steps SA-1 to SA-9 described above are repeated. For example, the route search condition transmission unit 102c of the terminal device 100 includes the route search condition including the current position information reset by the route search condition setting unit 102b every time the current position information is updated by the current position information acquisition unit 102a. May be controlled so that the processing of Step SA-1 to Step SA-9 described above is repeated. Accordingly, the search result information output by the search result information output unit 102e is updated in real time according to the update of the current position information. In addition, when the traffic information acquisition unit 202f of the server device 200 detects the update of traffic information (when new traffic information is received from the external device 600 or the like) or at regular intervals, the already acquired route search condition is set. Based on this, processing may be performed so as to repeat the processing of step SA-4 to step SA-9.

  The above is an example of the basic processing of the route search system in the first embodiment.

[Implementation process]
Next, an example of a specific process of the route search system in the present embodiment will be described with reference to FIGS. In this embodiment, the details of the process on the server device 200 side in the basic process described above will be described. Here, FIG. 5 is a flowchart illustrating an example of a specific process of the route search system according to the first embodiment.

  As shown in FIG. 5, the terminal device 100 sets a route search condition including at least a departure place and a destination by the route search condition setting unit 102b, and sets the route search condition by the route search condition transmission unit 102c. , The route search condition receiving unit 202a of the server device 200 acquires the route search condition transmitted from the terminal device 100 (step SB-1). Here, the route search condition may include a waypoint search condition, and may be a waypoint preference (POI category or the like), for example. Here, FIG. 6 is a diagram illustrating an example of a route point search condition input screen displayed by the route search condition setting unit 102b. In this example, it may be assumed that the route search conditions for the departure point and the destination are input.

  As illustrated in FIG. 6, the route search condition setting unit 102 b causes the user to input a search condition for searching for a POI from the POI database 206 c based on an attribute such as a category (type) via the input unit 116. An input screen may be displayed on the output unit 114. For example, as shown in FIG. 6, the input screen has a My genre selection button for selecting a category (in this example, ramen or gasoline) that suits the user's preference set in advance by the user. MA-1 may be included. Further, the input screen may include a free word input field MA-2 for inputting a keyword for searching for POI information such as a POI name and attribute. Further, the input screen may include a priority radar chart MA-3 for allowing the user to input a priority in a GUI (Graphical User Interface) format for a plurality of items (in this example, reputation, loss time, arrival time). . As shown in FIG. 6, for the item of arrival time, the options such as “Now”, “around 12:30 (every 30 minutes)”, “until XXIC” are displayed in the drop list MA-4 (or Dialog) to be selected on the input screen. The items of the priority radar chart MA-3 can be selected from the item list displayed by pressing “list” in the figure. Here, FIG. 7 is a diagram illustrating an example of an input screen for a transit point (POI) search condition (area selection condition) displayed by the route search condition setting unit 102b.

  As shown in FIG. 7, in this example, the terminal device 100 displays the area selection screen MB-1 for performing POI search, and inputs the area (each prefecture or the surrounding area) for searching the POI to the user. The selection is controlled via the unit 116. In this example, when the user selects the first 50-sound row (A row to Wa row) of the prefecture name, the terminal device 100 displays the name of the prefecture corresponding to the selected row. Is realized. Here, FIG. 8 is a diagram showing an example of an input screen for a transit point (POI) search condition (neighboring search condition) displayed by the route search condition setting unit 102b.

  As illustrated in FIG. 8, the terminal device 100 may cause the output unit 114 to display a peripheral search selection screen MB-2 including a current position peripheral search button MB-21 and a route midway search button MB-22. When the user presses the route search button MB-22 by clicking or the like, the route search condition setting unit 102b sets a condition for searching for a POI around the searched route, while the user is in the vicinity of the current position. When the search button MB-21 is clicked by clicking or the like, the route search condition setting unit 102b sets a condition for searching for a POI around the current position. In order to allow the user to further select a POI category or the like to be searched, the terminal device 100 may display an entry point search condition input screen as described above with reference to FIG.

  Returning to FIG. 5 again, when the route search condition is acquired as described above (step SB-1), the route search unit 202c of the server device 200 searches for the route based on the network data stored in the network database 206a. The route search from the starting point to the destination of the route search condition received by the condition receiving unit 202a is started (step SB-2). That is, the route search unit 202c spreads the search route from the departure point to the destination until the destination is reached. Note that the route search unit 202c may calculate an expected arrival time for the searched route because it is used for the diffusion processing from the destination side (step SB-43) in the bidirectional diffusion processing described later.

  Then, the waypoint candidate search unit 202b of the server device 200 starts a search using the POI as a waypoint candidate from the POI database 206c (step SB-3). For example, the waypoint candidate search unit 202b has a predetermined shape range such as the starting point of the route search condition, the current position (may be the predicted current position after a predetermined time), the destination, etc., as described above in step SA-4. The POI existing in the server may be searched from the POI database 206c. In addition, before performing the bidirectional diffusion process (step SB-4) as described above, the present invention is not limited to searching for a waypoint candidate. The search process (step SB-3) may be performed.

  In other words, the waypoint candidate search unit 202b simultaneously stores the POI point information stored in the POI database 206c according to the search route to be diffused at the same time as the route search processing by bidirectional diffusion described later (step SB-4). On the basis of this, a POI existing on or near the search route being spread may be acquired as a waypoint candidate. More specifically, the waypoint candidate search unit 202b searches the POI database 206c for a POI adjacent to the link for each link spread by the processing of the route search unit 202c based on the network data, and sets it as a waypoint candidate. to add. In addition, even when the route search unit 202c performs diffusion using a relatively higher-level link when using the hierarchical network data as described above with reference to FIG. The unit 202b may search not only for the POI adjacent to the upper hierarchical link but also for the POI adjacent to the lower hierarchical link around the upper hierarchical link. That is, the stopover point candidate search unit 202b may be included in the stopover point candidates as long as it is a POI that is associated with higher-layer network data even though it is not directly connected to the POI. Further, in the POI search, the waypoint candidate search unit 202b may narrow down the acquired POIs based on the POI search conditions (such as the category specified by the user) included in the route search conditions.

  And the route search part 202c of the server apparatus 200 performs the route search by bidirectional | two-way spreading | diffusion (step SB-4). Here, details of the route search processing by bidirectional diffusion will be described below with reference to FIG. FIG. 9 is a flowchart showing an example of route search processing by bidirectional diffusion.

  As shown in FIG. 9, first, the route search unit 202c uses a known route search method such as the Dijkstra method or the A * algorithm to spread the search route in the forward direction from the departure point to the destination direction. Sequentially, link costs are accumulated and determined (step SB-41).

  Then, for example, each time the route search unit 202c reaches a new node, the route search unit 202c determines whether or not the link cost has been fixed to all the plurality of waypoint candidates (step SB-42). Note that the diffusion termination condition on the departure side is not limited to this, and it may be that the diffusion link has reached the destination. Also, according to the calculated link cost, the point on the opposite side (for example, the departure point) When the link cost (time, distance, fee, etc.) is increased by a predetermined amount after reaching the destination in the case of diffusion from the side and the departure point in the case of diffusion from the destination side) There may be.

  If the link cost has not been determined for all the waypoint candidates (step SB-42, No), the route search unit 202c continues the diffusion of the search route and the associated link cost determination processing (step SB-41). .

  On the other hand, when the link cost is determined for all the waypoint candidates (step SB-42, Yes), the route search unit 202c is now forward from the destination to the departure direction (in the opposite direction to the previous one). Then, the search route is diffused and the link costs are sequentially added and fixed (step SB-43). Here, when diffusion from the destination side is performed, unlike the diffusion from the departure side, there is a problem that the expected arrival time cannot be calculated because the time of traffic information to be referred to is unknown. Therefore, the route search unit 202c may calculate the expected arrival time by acquiring the traffic information at the corresponding time from the traffic information database 206d using the predicted arrival time calculated in Step SB-2. That is, the route search unit 202c determines the route from the temporary predicted arrival time from the departure point to the destination calculated separately in step SB-2 to the destination via the waypoint candidate in step SB-4. The predicted transit time of the diffusion target link may be determined by subtracting “the required time from the destination to the diffusion target link” with respect to the target node that constitutes. The method of calculating the provisional predicted arrival time at the destination is not limited to this, and the route search unit 202c divides the straight line distance from the departure point to the destination by the average traveling speed to obtain the distance from the departure point to the destination. The required time may be calculated, and a temporary predicted arrival time may be calculated therefrom. The route search unit 202c may calculate a provisional predicted arrival time in consideration of the stay time at the waypoint candidate. For example, when all the waypoint candidates are restaurants, 1 hour may be added to the temporary predicted arrival time.

  Similarly, the route search unit 202c determines whether or not the link cost has been determined for all the plurality of waypoint candidates (step SB-44). Note that the diffusion termination condition on the destination side is not limited to this, and may be when the diffusion link reaches the destination. It may be the time when a predetermined number of link costs (time, distance, fee, etc.) are calculated.

  If the link cost has not been determined for all the waypoint candidates (step SB-44, No), the search route diffusion and the associated link cost determination process (step SB-43) are continued.

  When the link cost is determined for all the waypoint candidates in both directions (step SB-44, Yes), the route search unit 202c determines the route from the departure point obtained in step SB-41 to the waypoint candidate. The required time for each route point candidate is calculated by adding the required time and the required time for the route from the destination determined in step SB-43 to the route point candidate (step SB-45). ).

  Returning again to FIG. 5, the search result information generation unit 202 d of the server device 200 starts from the departure time calculated in Step SB-2 from the required time when passing through each waypoint candidate calculated in Step SB-45. By subtracting the time required for the route to the destination (not via the transit point), a loss time when passing through each transit point candidate is calculated (step SB-5).

  Then, the search result information generation unit 202d of the server device 200 sorts the plurality of waypoint candidates in the order of the degree of match with the POI search condition (user preference or the like) (step SB-6). For example, the search result information generation unit 202d may rearrange the waypoint candidates in descending order of match degree (in descending order of match degree). Here, the search result information generation unit 202d is not limited to sorting based on the degree of matching or the like, but may perform a filtering process that limits the number to be output when the waypoint candidates are equal to or greater than a predetermined value. For example, the search result information generation unit 202d may select a predetermined number of waypoint candidates in descending order of the matching degree, and exclude the rest from the search result information generation target. Note that the search result information generation unit 202d may arrange the POI of the store that places the advertisement based on the POI information in the rearrangement upper level. In addition, the search result information generation unit 202d may increase the rank of a specific category such as a station in accordance with a user's desire (search condition) such as assisting passengers to pick up. Note that the search result information generation unit 202d may be linked with real-time information such as traffic jam information, vacant seats, inventory, and prices.

  Then, the search result information generation unit 202d of the server device 200 generates search result information including a display screen in which each waypoint candidate is superimposed on the map data of the map database 206b based on the POI point information. (Step SB-7). Here, FIG. 10 is a diagram illustrating an example of a display screen generated by the search result information generation unit 202d.

  As shown in FIG. 10, when the current position information is included in the route search condition, the search result information generating unit 202d has a map in which a current position mark (a triangle mark in the figure) indicating the current position of the current position information is superimposed. A display screen including the display area MC-1 may be generated. At that time, the search result information generation unit 202d extracts a stopover candidate close to the current position from the stopover candidates, and POI information of the stopover candidate (in this example, genre: “ramen”, name: “ Pop-up display area MC-2 showing destination arrival time “12:30 arrival” and loss time “+3 minutes” when passing through KT noodles ”, evaluation: 4 stars) Also good. In this example, the terminal device 100 periodically transmits a route search condition including the current position information to be updated, and steps SB-1 to SB-7 are performed in the background according to the update of the current position information. It is also possible to presuppose that the above process is repeated and the display screen transitions (a pop-up is displayed when the current position approaches one waypoint candidate). Further, the pop-up display timing may be determined based on an expected position after traveling for a predetermined time based on a history of current position information. As a result, it is possible to give the user time to determine whether or not to stop at the waypoint candidate displayed in a pop-up, and the user can leave the currently traveling route with a margin. In addition, when the route for reaching the recommended POI is deviated, the terminal device 100 may hide the displayed pop-up. When a plurality of waypoint candidates are displayed, the search result information generation unit 202d may be controlled so as to be highlighted from the sorted head. For example, the size of a star indicating a waypoint candidate is changed in the sort order. May be. Here, FIG. 11 is a diagram illustrating an example of a display screen on which a plurality of waypoint candidates generated by the search result information generation unit 202d are superimposed. In FIG. 11, S indicates a departure place, G indicates a destination, and each black circle on the map indicates a waypoint candidate. The degree of match with the POI search condition (user's preference, etc.) is represented by the size of a black circle. Further, the solid line in the figure indicates the route from the departure point searched for in step SB-2 to the destination, and the broken line passes through the route point candidate from the departure point searched for in step SB-4. The route to the destination is shown. The number of stars in the balloon indicates a high reputation based on word of mouth.

  As shown in FIG. 11, as a result of sorting in step SB-7, the upper ones may be represented by large black circles, and the store name, reputation, and arrival time (loss time) may be displayed in a balloon. In addition, the lower sort result is represented by a small black circle. Then, the search result information including this display screen is displayed on the output unit 114 of the terminal device 100, and when the user selects one waypoint by touch operation or the like via the input unit 116 such as a touch panel (in this example, , POI of the store name “KT noodle” is selected.), And the balloon is superimposed on the highest hierarchy, and the route via the route point stored in the search result information is displayed. The search result information generation unit 202d may generate search result information. In addition, when the “stop” button in the balloon is pressed by a touch operation such as double touch, the route search condition setting unit 102b can reset the route search condition using the selected waypoint candidate as a waypoint. Good.

  Then, the route search unit 202c of the server device 200 performs route search again using the waypoint candidates as route points (step SB-8). Note that the waypoint candidates as the waypoints may be set based on the route search condition including the waypoints retransmitted from the terminal device 100 as described above, and for all of the plurality of waypoint candidates, Re-searching may be performed using as a waypoint. That is, in the route search by bidirectional diffusion (step SB-4) described above, the route search is performed in the reverse direction from the destination toward the waypoint candidate. Although the accuracy may be inferior, such as referring to the calculated predicted arrival time, the route search unit 202c searches for the search route from the departure point to the selected waypoint and the search from the selected waypoint to the destination. By diffusing each route, the search route is diffused in the forward direction from the departure point to the destination, and the highly accurate route and required time are calculated in consideration of the traffic information stored in the traffic information database 206d. Also good. Since the process of step SB-8 is a process for calculating an accurate route, a required time, and the like, it may be omitted to speed up the process. In addition, the predicted arrival time, required time, and the like calculated in step SB-8 or step SB-4 are notified to the user via the output unit 114. Further, the search result information including the display screen and the route search result by the above-described Step SB-7 and Step SB-8 is transmitted and output to the terminal device 100. Since it is the same as that of FIG. Further, the above-described processing of Step SB-1 to Step SB-8 may be repeatedly executed periodically or in accordance with update of a search condition, a current position, or the like. In particular, when the search condition is input again by the user via the input screen shown in FIG. 6 (for example, when the priority for the user category or the like is changed), the server apparatus 200 performs step SB- Only the processing from 6 to step SB-8 may be repeatedly executed.

  The above is an example of the materialization process of the route search system in the first exemplary embodiment. This makes it possible to search for sightseeing spots that stop by the inn at the destination, find restaurants that can be used without loss time between high-speed ICs, and automatically select recommended stop points according to usage history, genre designation, and advertisements. It can meet various demands such as pop display.

[Second Embodiment]
Next, a second embodiment (route search device 400 (stand-alone type)) of the present invention will be described below with reference to FIGS. 12 and 13. Here, FIG. 12 is a block diagram showing an example of the configuration of the route search apparatus 400 in the second embodiment, and conceptually shows only the portion related to the present invention in the configuration.

  In the second embodiment, all functions are aggregated in the route search device 400, and based on network data defining the traffic network, a plurality of points from the start point of the route search condition including at least a start point and a destination point are used. A route is searched by diffusing each of the search route to the waypoint candidate and the search route from the destination of the route search condition to the plurality of route point candidates one by one. The search result information including the route to the destination is generated. As described above, the second embodiment is different from the first embodiment in that the route search apparatus 400 is configured as a stand-alone type and performs processing alone.

[Configuration of route search apparatus 400 (stand-alone type)]
First, an example of the configuration of the route search apparatus 400 (stand-alone type) in the second embodiment will be described below with reference to FIG.

  As illustrated in FIG. 12, the route search apparatus 400 according to the second exemplary embodiment of the present invention includes at least a position acquisition unit 412, an output unit 414, an input unit 416, a control unit 402, and a storage unit 406. Each unit of the route search apparatus 400 is connected to be communicable via an arbitrary communication path. For example, the route search device 400 includes a commercially available information processing device such as a desktop or laptop personal computer, a portable terminal device such as a mobile phone, a PHS, or a PDA, and a PND (Portable Navigation) that performs travel route guidance and the like. A navigation terminal such as Device).

  12, each function of the input / output control interface unit 408, the communication control interface unit 404, the position acquisition unit 412, the output unit 414, the input unit 416, the network 300, the position transmission device 500, and the external device 600 is illustrated. Since this is the same as in the first embodiment, a description thereof will be omitted. Further, each part of the storage unit 406 (network database 406a, map database 406b, POI database 406c, traffic jam information database 406d, etc.) Since the function is the same as that of the first embodiment, description thereof is omitted. The storage unit 406 may further store the guide data stored in the guide data file 106a in the first embodiment.

  As for each part of the control unit 402 (route search condition setting unit 402a to current position information acquisition unit 402g, etc.), the route search device 400 of the present embodiment is a stand-alone type, and the control unit 402 includes each transmission / reception unit. Except for this point, each function is basically the same as that of the route search system of the first embodiment.

  In FIG. 12, the control unit 402 has an internal memory for storing a control program such as an OS, a program defining various processing procedures, and necessary data. And the control part 402 performs the information processing for performing various processes with these programs. The control unit 402 functionally conceptually includes a route search condition setting unit 402a, a waypoint candidate search unit 402b, a route search unit 402c, a search result information generation unit 402d, a search result information output unit 402e, a traffic jam information acquisition unit 402f, and The current position information acquisition unit 402g is provided. These functions are the route search condition setting unit 102b, the waypoint candidate search unit 202b, the route search unit 202c, the search result information generation unit 202d, the search result information output unit 102e, and the traffic jam information acquisition unit 202f in the first embodiment. And since it is the same as that of the function of the present position information acquisition part 102a, description is abbreviate | omitted.

  Above, description of an example of a structure of the route search apparatus 400 in 2nd Embodiment is finished.

[Processing of Route Searching Device 400 (Stand-Alone Type)]
Next, an example of processing of the route searching apparatus 400 in the second embodiment configured as described above will be described in detail with reference to FIG. Here, FIG. 13 is a flowchart showing an example of processing of the route search apparatus 400 in the second embodiment.

  As shown in FIG. 13, first, the route search condition setting unit 402a causes the user to set a route search condition including at least a departure place and a destination via the input unit 416 (step SC-1). Here, the departure point may be the current position of the user of the route search device 400 based on the current position information acquired by the current position information acquisition unit 402g. The route search condition includes the current position separately from the departure point. Location conditions may be added. In addition, the route search condition setting unit 402a may allow the user to specify a waypoint preference (for example, a POI category searched as a waypoint candidate) as a route search condition.

  The waypoint candidate search unit 402b then searches for a plurality of waypoint candidates from point information (POI information or the like) stored in the POI database 406c (step SC-2). Here, the waypoint candidate search unit 402b includes predetermined points including a departure point, a current position (may be an expected current position after a predetermined time) of a route search condition set by the route search condition setting unit 402a, a destination, and the like. A POI existing within the shape range of the POI database 406c may be searched. As an example of the predetermined shape range, the waypoint candidate search unit 402b may search for a POI located within an ellipse range having two points of a departure point and a destination as a waypoint candidate. In addition, when a POI category or the like is specified as a route search condition, the waypoint candidate search unit 402b may perform a search by narrowing down to a POI corresponding to the specified category or the like. In addition, the route search unit 402b allows the route search unit 402c to spread the search route from the departure point to the destination at the same time before the bidirectional diffusion executed below by the route search unit 402c. A plurality of POIs may be searched from the POI database 406c as a plurality of waypoint candidates based on the search route from the departure place to the destination. That is, when the route search unit 402c spreads the search route from the departure point to the destination, the waypoint candidate search unit 402b performs the spreading process based on the POI point information stored in the POI database 406c. A POI existing on or near the searched route may be acquired as a waypoint candidate.

  Then, the route search unit 402c executes a route search by bidirectional diffusion for a plurality of waypoint candidates searched by the waypoint candidate search unit 402b based on the network data stored in the network database 406a (step SC- 3). Specifically, the route search unit 402c searches for the search route from the starting point of the route search condition set by the route search condition setting unit 402a to a plurality of waypoint candidates, and the plurality of destinations from the destination of the route search condition. The search route to the route point candidate is diffused once each, and the route search by bidirectional diffusion is performed. In addition, the details of the route search by bidirectional diffusion are the same as those in the first embodiment. For example, the route search unit 402c may perform route search using hierarchical network data stored in the network database 406a in order to shorten the processing time. Note that, as described above in Step SC-3, the route search unit 402c may perform a normal route search in which the search route is diffused from the departure point to the destination in addition to the route search by bidirectional diffusion.

  And the search result information generation part 402d produces | generates the search result information containing the path | route from the departure place to the destination via the waypoint candidate searched by the route search part 402c (step SC-4). For example, the search result information generation unit 402d connects the route from the departure point to the waypoint candidate and the route from the destination to the waypoint candidate, which are searched by bidirectional diffusion, from the departure point. A route to the destination via the waypoint candidate may be generated, and search result information indicating the route may be generated. Further, the search result information generation unit 402d may generate search result information including a display screen in which the waypoint candidates are superimposed on the map data stored in the map database 406b. At that time, the search result information generation unit 402d superimposes the starting point, the destination, the route from the starting point to the destination, the route from the starting point to the destination via the waypoint candidate, etc. on the map data. Search result information may be generated. In addition, the search result information generation unit 402d compares the route searched from the departure point to the destination and the route from the departure point to the destination via the waypoint candidate, which is searched by the route search unit 402c. Search result information including may be generated. For example, the search result information generation unit 402d may generate search result information indicating the comparison results (difference, ratio, ratio, etc.) of the time, distance, and fee of both routes. The search result information generation unit 402d sorts these comparison results in descending or ascending order and displays them in a list in the determined display order (for example, POIs are displayed in ascending order of loss time). Result information may be generated. The search result information generation unit 402d is not limited to determining the display order based on the comparison result with the route from the departure point to the destination (not via the route point candidate), but from the departure point to the destination. Without performing the route search, the display order of the route from the departure point to the destination via each waypoint candidate may be determined based on the required time, distance, fee, etc. between the waypoint candidates.

  Then, the search result information output unit 402e outputs the search result information generated by the search result information generation unit 402d to the output unit 414 (step SC-5). Here, the search result information output unit 402e may superimpose the current position information updated by the current position information acquisition unit 402g on the map data or the route according to the search result information, and display it on the output unit 414. Good. In addition, the search result information output unit 402e is configured so that the current position of the current position information updated by the current position information acquisition unit 402g is within a predetermined range of waypoint candidates included in the search result information or a route via the waypoint candidate. When approaching a branch point, it may be output by voice or display that there is a candidate for the waypoint. Here, when one waypoint is selected from a plurality of waypoint candidates via the input unit 416 by the user, the search result information output unit 402e selects the route point selected based on the search result information. Route guidance may be executed according to the route passing through. Note that the route search unit 402c may perform the route search again for the selected waypoint in order to increase the accuracy of the route search.

  The above is an example of processing by the route search apparatus 400 in the second embodiment. In the present embodiment, control may be performed so that the processes in steps SC-1 to SC-5 described above are repeated. For example, each time the current position information is updated by the current position information acquisition unit 402g, the route search condition including the current position information reset by the route search condition setting unit 402a is set. -You may control so that the process of step SC-5 may be repeated. Accordingly, the search result information output by the search result information output unit 402e is updated in real time according to the update of the current position information. In addition, the above-described processing may be repeated to narrow down the waypoint candidates when a waypoint search condition (category designated by the user) is added to the route search condition. Further, when the traffic jam information acquiring unit 402f acquires new traffic jam information or at regular intervals, the processing of step SC-2 to step SC-5 may be repeated.

  Above, description of the process of the route search apparatus 400 in 2nd Embodiment is finished.

[Other embodiments]
Although the embodiments of the present invention have been described so far, the present invention is not limited to the above-described embodiments, but can be applied to various different embodiments within the scope of the technical idea described in the claims. It may be implemented.

  For example, although the case where the route search device 400 performs processing in a stand-alone form has been described as an example, the route search device 400 performs processing in response to a request from the client terminal and returns the processing result to the client terminal You may make it do.

  In addition, among the processes described in the embodiment, all or part of the processes described as being automatically performed can be performed manually, or the processes described as being performed manually can be performed. All or a part can be automatically performed by a known method.

  In addition, unless otherwise specified, the processing procedures, control procedures, specific names, information including registration data for each processing, parameters such as search conditions, screen examples, and database configurations shown in the above documents and drawings Can be changed arbitrarily.

  Moreover, regarding the terminal device 100, the server device 200, and the route search device 400, each illustrated component is functionally conceptual and does not necessarily need to be physically configured as illustrated.

  For example, all or some of the processing functions provided in each device of the terminal device 100, the server device 200, and the route search device 400, particularly the processing functions performed by the control units 102, 202, and 402, are included. It may be realized by a CPU (Central Processing Unit) and a program interpreted and executed by the CPU, or may be realized as hardware by wired logic. The program is recorded on a recording medium to be described later, and is mechanically read by the terminal device 100, the server device 200, and the route search device 400 as necessary. That is, in the storage units 106, 206, and 406 such as a ROM or an HDD, computer programs for performing various processes by giving instructions to the CPU in cooperation as an OS (Operating System) are recorded. This computer program is executed by being loaded into the RAM, and constitutes a control unit in cooperation with the CPU.

  Further, this computer program may be stored in an application program server connected to the terminal device 100, the server device 200, and the route search device 400 via an arbitrary network 300, and the computer program may be stored as necessary. It is also possible to download all or part of it.

  In addition, the program according to the present invention may be stored in a computer-readable recording medium, and may be configured as a program product. Here, the “recording medium” means a memory card, USB memory, SD card, flexible disk, magneto-optical disk, ROM, EPROM, EEPROM, CD-ROM, MO, DVD, and Blu-ray (registered trademark). It includes any “portable physical medium” such as Disc.

  The “program” is a data processing method described in an arbitrary language or description method, and may be in any format such as source code or binary code. The “program” is not necessarily limited to a single configuration, but is distributed in the form of a plurality of modules and libraries, or in cooperation with a separate program represented by an OS (Operating System). Including those that achieve the function. Note that a well-known configuration and procedure can be used for a specific configuration for reading a recording medium, a reading procedure, an installation procedure after reading, and the like in each device described in the embodiment.

  Various databases and the like (guidance data file 106a and network databases 206a and 406a to traffic jam information databases 206d and 406d) stored in the storage units 106, 206, and 406 are fixed to memory devices such as RAM and ROM, hard disks, and the like. A storage device such as a disk device, a flexible disk, and an optical disk, and stores various programs, tables, databases, web page files, and the like used for various processes and website provision.

  The server device 200 may be configured as an information processing device such as a known personal computer or workstation, or may be configured by connecting an arbitrary peripheral device to the information processing device. The server apparatus 200 may be realized by installing software (including programs, data, and the like) that causes the information processing apparatus to implement the method of the present invention.

  Furthermore, the specific form of distribution / integration of the devices is not limited to that shown in the figure, and all or a part of them may be functional or physical in arbitrary units according to various additions or according to functional loads. Can be distributed and integrated. That is, the above-described embodiments may be arbitrarily combined and may be selectively implemented.

  As described above in detail, according to the present invention, a route search device, a route search system, a server device, a terminal device, a route search method, and a program capable of efficiently searching for an appropriate waypoint, In addition, a recording medium can be provided.

DESCRIPTION OF SYMBOLS 100 Terminal apparatus 102 Control part 102a Current position information acquisition part 102b Route search condition setting part 102c Route search condition transmission part 102d Search result information reception part 102e Search result information output part 104 Communication control interface part 106 Storage part 106a Guidance data file 108 In Output control interface unit 112 Position acquisition unit 114 Output unit 116 Input unit 200 Server device 202 Control unit 202a Route search condition reception unit 202b Route location candidate search unit 202c Route search unit 202d Search result information generation unit 202e Search result information transmission unit 202f Congestion Information acquisition unit 204 Communication control interface unit 206 Storage unit 206a Network database 206b Map database 206c POI database 206d Traffic jam information database 30 Network 400 Route search device 402 Control unit 402a Route search condition setting unit 402b Route location candidate search unit 402c Route search unit 402d Search result information generation unit 402e Search result information output unit 402f Congestion information acquisition unit 402g Current position information acquisition unit 404 Communication control Interface unit 406 Storage unit 406a Network database 406b Map database 406c POI database 406d Traffic jam information database 408 Input / output control interface unit 412 Position acquisition unit 414 Output unit 416 Input unit 500 Position transmission device 600 External device

Claims (11)

Each of the search route from the departure point to a plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates in a route search condition including at least a departure point and a destination is diffused once each. Route search means for searching for a route,
Search result information generating means for generating search result information including the route from the departure place to the destination via the waypoint candidate, searched by the route search means;
A route search system comprising: The route search system according to claim 1,
Further comprising a waypoint candidate searching means for searching for the plurality of waypoint candidates from the point information about the point,
The route search means, for the plurality of waypoint candidates searched by the waypoint candidate search means, the search route from the departure point of the route search condition to the plurality of waypoint candidates, and the route search A route search system, characterized in that each of the search routes from the destination in the condition to the plurality of waypoint candidates is diffused once. In the route search system according to claim 2,
When the route search means spreads the search route from the departure point and the search route from the destination by the route search unit, the route point candidate near the search route to be diffused A route search system characterized by searching from the point information. In the route search system according to claim 1 or 2,
The route search means, before spreading the search route from the departure point to the plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates, from the plurality of waypoint candidates. A route search system, characterized in that the search route is diffused based on data defining a detailed traffic network. In the route search system according to any one of claims 1 to 4,
Current position information acquisition means for acquiring current position information indicating the current position of the moving body, and the route search means, the current position information of the current position information acquired by the current position information acquisition means, the current position information A route search system, characterized in that a route search is performed as the starting point of the route search condition. The route search system according to any one of claims 1 to 5,
A traffic information acquisition means for acquiring traffic information indicating the occurrence of traffic jams expected for each point of time,
The route search means calculates an expected arrival time at the destination based on the searched route from the departure point to the waypoint candidate and the route from the destination to the waypoint candidate, and the traffic jam A route search system for correcting the predicted arrival time based on information. The route search system according to any one of claims 1 to 6,
Route search condition setting means for setting the route search condition including at least the departure place and the destination;
A route search system, further comprising: search result output means for outputting the search result information generated by the search result information generation means. Each of the search route from the departure point to a plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates in a route search condition including at least a departure point and a destination is diffused once each. A route search step for searching the route,
A search result information generating step for generating search result information including the route from the starting point to the destination via the waypoint candidate searched by the route searching means;
A route search method, comprising: Computer
Each of the search route from the departure point to a plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates in a route search condition including at least a departure point and a destination is diffused once each. Route search means for searching the route,
Search result information generating means for generating search result information including the route from the departure place to the destination via the waypoint candidate searched by the route search means;
A program characterized by functioning as A program for causing a server device provided with at least a control unit to be communicably connected to a terminal device provided with at least an output unit,
The control unit
Route search condition receiving means for receiving a route search condition transmitted from the terminal device and including at least a departure place and a destination;
The search route from the departure point to a plurality of waypoint candidates according to the route search condition received by the route search condition receiving unit, and the search route from the destination to the plurality of waypoint candidates once each A route search means for searching for a route by diffusing one by one;
Search result information generating means for generating search result information including the route from the departure place to the destination via the waypoint candidate, searched by the route search means;
Search result information transmitting means for transmitting the search result information generated by the search result information generating means to the terminal device;
A program characterized by functioning as A program for causing a terminal device including at least an output unit and a control unit connected to a server device to be communicable,
The control unit
Route search condition transmitting means for transmitting a route search condition including at least a starting point and a destination to the server device;
The search route from the departure point to a plurality of waypoint candidates and the search route from the destination to the plurality of waypoint candidates transmitted from the server device are each diffused once. Search result information receiving means for receiving search result information including the route from the departure point to the destination via the waypoint candidate,
Search result information output means for outputting the search result information received by the search result information receiving means to the output unit;
A program characterized by functioning as

Images