JP7698535B2 - Route search device, route search method, and computer program - Google Patents

Description

The present invention relates to a route search device, a route search method, and a computer program.

Navigation devices that provide route guidance from a departure point to a destination are known. Such navigation devices are often installed in vehicles and used to provide guidance on the vehicle's travel route, so there is a demand to avoid searching for routes that include dead ends or cul-de-sacs where the vehicle may have to make a U-turn.

In this regard, for example, Patent Document 1 discloses that when a navigation device has first information indicating a dead end within or beyond a specified section, the specified section is excluded from the selection settings for a driving route, so that routes that cannot be used as a driving route are not searched for. For example, Patent Document 2 discloses that when a navigation device has set a guide route that makes a U-turn at the end of a dead end, a U-turn guidance image is displayed. For example, Patent Document 3 discloses that when a car navigation device determines that a road is a dead end, it provides guidance regarding the dead end road.

JP 2000-18958 A JP 2010-243187 A JP 2006-220562 A

In recent years, the popularity of internet shopping has led to an increase in the demand for logistics services, and the number of people (hereinafter referred to as "delivery personnel") engaged in the task of delivering goods and other packages to designated destinations is on the rise. From the perspective of improving work efficiency, delivery personnel have a predefined area of responsibility, and deliver packages to residential homes within that area. Compared to normal main roads, areas with many residential homes tend to have more cul-de-sacs and dead ends where vehicles have to make U-turns, and there is a lot of traffic of people, bicycles, and the like. For this reason, there is a particular need for route search devices (navigation devices) used in delivery services to suppress guidance of routes that include cul-de-sacs and dead ends.

In this regard, the navigation device described in Patent Document 1 uses the first information to determine whether a route is a dead end, so in places where there is no first information, routes that include dead ends or cul-de-sacs are guided. In particular, in residential areas where there are many private homes, the development of information tends to be delayed compared to office areas, but in delivery work, it is even more important in terms of demand and safety to suppress guidance of such routes (routes that include dead ends or cul-de-sacs) in such residential areas. In addition, the navigation devices described in Patent Documents 2 and 3 only present information on U-turns and cul-de-sac roads, and do not take into consideration the suppression of guidance of routes that include dead ends or cul-de-sacs. As mentioned above, such issues are not limited to route search devices used in delivery work, but are also common to route search devices for general users.

Therefore, there was a demand for a route search device that could suppress guidance on routes that included dead ends and cul-de-sacs.

The present invention has been made to solve at least part of the above-mentioned problems, and can be realized in the following form: A route search device comprising: a route information storage unit that stores road network data including node information and link information connecting the nodes; and a route search unit that searches for a route from a departure point to a destination via one or more intermediate points, wherein when a link in which only one of the nodes located at both ends is connected to another link is considered to be an end link, even if the intermediate point is set on the end link, the route search unit searches for the route from the road network data after excluding the end link from the search target, and outputs the searched route. In addition, the present invention can be realized in the following form.

(1) According to one aspect of the present invention, a route search device is provided. The route search device includes a route information storage unit that stores road network data including node information and link information connecting the nodes, and a route search unit that searches for a route from a starting point to a destination. The route search unit searches for the route from the road network data after excluding terminal links, which are links in which only one of the nodes located at both ends of a link is connected to another link, from the search targets, and outputs the searched route.

A "dead end" refers to a road where only one of the two ends of the road is connected to another road. With this configuration, the route search unit searches for a route after excluding terminal links (i.e., links that are dead ends) from the road network data, which are links where only one of the nodes located at both ends is connected to another link. This makes it possible to provide a route search device that can suppress guidance of routes that include dead ends. Also, with this configuration, the determination of whether a link is a terminal link (a link that is a dead end) is made using the connection relationships of the links in the road network data used for route search. Therefore, compared to when special information is required separately, guidance of routes that include dead ends can be suppressed without being affected by whether information is available or not.

(2) In the route search device of the above embodiment, the route search unit may search for the route from the road network data by excluding from the search target a specific link in which, among the nodes located at both ends of a link, one is connected only to the terminal link, in addition to the terminal link.
A "cul-de-sac" means a group of roads that are in a bag shape and cannot be passed through. According to this configuration, the route search unit searches for a route from the road network data, excluding from the search target, in addition to the terminal links, specific links (i.e., links for entering a cul-de-sac) in which one of the nodes located at both ends of the link is connected only to the terminal link. Therefore, a route search device capable of suppressing guidance of a route including a cul-de-sac can be provided. Also, according to this configuration, the determination of whether or not a link is a specific link (a link for entering a cul-de-sac) is performed using the connection relationship of the links in the road network data used for route search. Therefore, compared to the case where special information is separately required, guidance of a route including a cul-de-sac can be suppressed without being affected by the availability of information.

(3) In the route search device of the above embodiment, the route search unit searches for a route from the departure point to the destination via a predetermined intermediate point, and when a node that is not connected to other links among the nodes located at both ends of the terminal link is set as an end node, if the link length from the end node to the intermediate point is equal to or greater than a predetermined threshold, the route may be searched for without excluding the terminal link from the search target.
In cases where the road length is long even if the link is a dead end, there is a demand for guidance of a route that includes the dead end. In this regard, according to the present configuration, when a node that is not connected to other links among the nodes located at both ends of a terminal link is set as an end node, if the link length from the end node to a via point is equal to or greater than a predetermined threshold, the route search unit does not exclude the terminal link (link that corresponds to a dead end) from the search target. Therefore, in cases where the road length is long even if the link is a dead end, the route search unit can guide a route that includes the dead end.

(4) In the route search device of the above aspect, when the terminal link is a link facing either the starting point or the destination, the route search unit may search for the route without excluding the terminal link from the search target.
Even if it is a dead end, if it faces either the departure point or the destination, there is a demand for guidance of a route including the dead end. In this regard, according to the present configuration, if an end link is a link facing either the departure point or the destination, the route search unit does not exclude the end link (link corresponding to a dead end) from the search target. Therefore, even if it is a dead end, if it faces either the departure point or the destination, the route search unit can guide the user to a route including the dead end.

(5) In the route search device of the above embodiment, when the searched route includes a route that makes a U-turn around a certain link, the route search unit may exclude the links that make up the U-turn route from the search, re-search for the route, and output the re-searched route.
In residential areas with many private homes, compared to normal main streets, there are many narrow roads where vehicles make U-turns, and there is a lot of traffic of people, bicycles, etc. In this regard, according to the present configuration, when the searched route includes a route that makes a U-turn at a certain link, the route search unit excludes the links that make up the U-turn route from the search targets, and then re-searches for the route and outputs the re-searched route. As a result, according to the route search device of the present configuration, guidance of routes that include U-turn routes is further suppressed, thereby improving ease of travel on the guided route and improving safety.

(6) In the route search device of the above embodiment, the route search unit may obtain information on one or more delivery destinations where a user of the route search device will stop for the delivery of a package, and search for the route from the departure point to the destination, passing through the one or more delivery destinations as intermediate points.
In recent years, the demand for logistics services has increased due to the spread of internet shopping, and the number of people (delivery personnel) engaged in the task of delivering packages such as goods to designated delivery destinations is increasing. In this regard, according to the present configuration, the route search unit obtains information on one or more delivery destinations where the user (delivery personnel) of the route search device stops to deliver the package, and searches for a route from the departure point to the destination via one or more delivery destinations as intermediate points, so that a route search device specialized for delivery services can be provided.

(7) In the route search device of the above embodiment, the route search unit may acquire location information of a parking space that is located near a road and where a vehicle can be safely parked, along the searched route, and may output the acquired location information of the parking space in addition to the searched route.
In residential areas where many private homes exist, there are fewer parking spaces than in areas near normal main streets. In this regard, according to the present configuration, the route search unit acquires location information of parking spaces (parking spaces where the vehicle can be safely parked) along the searched route, and outputs the location information of the parking spaces along with the searched route. This prevents users (delivery people) from parking their vehicles on unsafe roadsides in residential areas where there are few parking spaces, thereby improving convenience and safety for users.

The present invention can be realized in various forms, such as a route search device, a navigation device, a navigation system, a computer program for implementing the functions of these devices and systems, a server device for distributing the computer program, a non-transitory storage medium on which the computer program is stored, etc.

1 is a diagram showing a schematic configuration of a navigation system according to an embodiment of the present invention; FIG. 4 is a diagram showing an example of delivery plan information. 13 is a flowchart showing an example of a processing procedure of a route search process. FIG. 13 is a diagram illustrating a specific example of rule a1. FIG. 13 is a diagram illustrating a specific example of rule a2. FIG. 13 is a diagram illustrating a specific example of rule a3. FIG. 13 is a diagram illustrating specific examples of rules a4 and a5. FIG. 11 is a diagram illustrating a specific example of an excluded route. FIG. 13 is a diagram showing an example of a guide screen displayed on a client; FIG. 13 is a diagram showing a schematic configuration of a navigation system according to a second embodiment. 13 is a flowchart showing an example of a processing procedure of a route search process according to a second embodiment; FIG. 13 is a diagram showing a schematic configuration of a navigation system according to a third embodiment. FIG. 13 is a diagram showing a schematic configuration of a navigation system according to a fourth embodiment.

A. First embodiment:
1 is a diagram showing a schematic configuration of a navigation system 1 according to an embodiment of the present invention. The navigation system 1 is a system whose users are people (hereinafter also referred to as "delivery persons") who are engaged in logistics operations, particularly the operation of delivering packages such as merchandise to designated delivery destinations. The navigation system 1 illustrated here is used to output to the users (delivery persons) guidance information including route guidance to the delivery destination of the package to be delivered (hereinafter also referred to as "package to be delivered") and information regarding the delivery destination, thereby facilitating delivery operations.

The navigation system 1 of this embodiment can suppress guidance of routes that include dead ends or cul-de-sacs by using a route search process described below. Here, a "dead end" refers to a road where only one of the two ends of the road is connected to another road. Also, a "cul-de-sac" refers to a group of roads that are in a bag shape and cannot be passed through.

The navigation system 1 includes a server 10 and a client 30. The server 10 is connected to the Internet INT by wired communication. The client 30 is connected to the Internet INT by wireless communication via a communication carrier BS. The communication carrier BS includes a transmitting/receiving antenna, a wireless base station, and a switching center. In other words, the server 10 and the client 30 can communicate with each other via the Internet INT.

The server 10 uses delivery plan information 341 (details will be described later) acquired from the client 30 to search for a route (hereinafter also referred to as a "delivery route") in which the delivery addresses of packages to be delivered are set as intermediate destinations. The server 10 corresponds to a "route search device." The server 10 includes a CPU 110, a communication unit 120, a ROM/RAM 130, and a storage unit 140, and each unit is interconnected by a bus (not shown).

The CPU 110 controls each part of the server 10 by expanding the computer program stored in the ROM 130 into the RAM 130 and executing it. The CPU 110 also functions as a route search unit 111. The route search unit 111 is a processing unit that searches for a route from a departure point to a destination using the route information DB 142. In this embodiment, the route search unit 111 calculates the delivery route described above. The communication unit 120 controls communication with other devices such as the client 30 via a communication interface (not shown).

The storage unit 140 is composed of a hard disk, a flash memory, a memory card, etc. A map information database 141, a route information database 142, and a guidance information database 143 are pre-stored in the storage unit 140. In the following explanation, the database is also simply referred to as "DB".

Map information DB141 is a database that stores data representing map images. The data representing map images includes information necessary for map display, such as topography, buildings, and road shapes. Route information DB142 is a database that stores road network data. Road network data includes node information on "nodes" that represent the positions of intersections and landmarks such as stations, and link information on "links" that represent roads connecting nodes. Node information includes node position information, node type, node name, other node information, etc. Link information includes link cost for each mode of travel (average travel time on the road represented by the link), link type, link name, link status, other link information, etc. Route information DB142 corresponds to a "route information storage unit."

The guidance information DB 143 is a database that stores information about parking spaces. Here, a "parking space" refers to a location that is located near a road and where a vehicle can be safely parked. The parking space in this embodiment is not limited to a so-called parking lot. Information about the parking space may include the location information of the parking space, as well as the type of parking space (whether it is a parking lot or not), the size of the parking space, the time period during which the parking space is available, and the like. The guidance information DB 143 may be stored in a server other than the server 10. In that case, the server 10 may connect to the other server as necessary in the process described below to obtain information about the parking space.

The client 30 can be configured as any device, such as a smartphone as shown in the figure, a personal computer, an in-vehicle device, a wearable device, etc. The client 30 includes a CPU 310, a communication unit 320, a ROM/RAM 330, a storage unit 340, an input/output unit 350, and a current position acquisition unit 360, and each unit is interconnected by a bus (not shown).

The CPU 310 controls each part of the client 30 by expanding the computer program stored in the ROM 330 into the RAM 330 and executing it, and also functions as a guidance unit 311. The guidance unit 311 transmits delivery plan information 341 to the server 10 and acquires delivery route information 342 from the server 10. The guidance unit 311 uses the acquired delivery route information 342 to output the delivery route (path) from the input/output unit 350, thereby providing the user of the client 30 with guidance on the delivery route.

The communication unit 320 controls communication between other devices, such as the server 10, via a communication interface (not shown).

The storage unit 340 is composed of a hard disk, a flash memory, a memory card, etc. The storage unit 340 stores delivery plan information 341 in advance. The storage unit 340 also stores delivery route information 342 acquired from the server 10 through a process described below.

Figure 2 is a diagram showing an example of delivery plan information 341. Delivery plan information 341 stores information on parcels to be delivered that day by the user of client 30 (hereinafter also referred to as "parcel information"). As shown in the figure, each piece of parcel information includes, for example, the delivery address, the latitude and longitude of the delivery destination, whether or not there is a delivery box at the delivery destination, nameplate information, remarks information, a specified delivery time for the parcel, whether or not the delivery box can be used, and drop-off information. Drop-off information may include whether or not drop-off is possible, a specified drop-off location, and specified conditions for drop-off (date, time, weather, etc.). Note that parcel information may also include other information not shown.

Returning to FIG. 1, the explanation will be continued. The input/output unit 350 is a variety of interfaces used for inputting and outputting information between the client 30 and the user. For example, the input/output unit 350 may be a touch panel as an input unit, a touch panel as a display unit (output unit), or a liquid crystal panel. The current position acquisition unit 360 receives radio waves transmitted from artificial satellites constituting the Global Positioning System (GPS) or Quasi-Zenith Satellite System (QZSS), and acquires current position information (latitude and longitude) indicating the current position of the client 30. Here, since the client 30 is carried by the user, the current position acquired by the current position acquisition unit 360 can be regarded as the current position of the user.

Figure 3 is a flowchart showing an example of the processing procedure of the route search process. The route search process is a process executed by the server 10 in order to search for a delivery route. The route search process is started in response to a processing request from the client 30. The processing request from the client 30 includes the delivery plan information 341 described in Figure 2. In step S100, the route search unit 111 acquires the delivery plan information 341 included in the processing request from the client 30.

In step S102, the route search unit 111 refers to the delivery plan information 341 acquired in step S100 and performs a route search in which each delivery address of package information 1 to n (n is any natural number) is set as a stopover point. The departure point at this time may be the current position acquired by the current position acquisition unit 360, or may be a predetermined location (e.g., the user's home, a delivery business office, etc.). The arrival point can be a predetermined location (e.g., the user's home, a delivery business office, etc.). The route search can be performed using the well-known Dijkstra's algorithm or the well-known A-star search algorithm, using the route information DB 142.

In step S102, the route search unit 111 excludes terminal links and specific links from the search in accordance with the following rules a1 to a5. Specifically, the links in the route information DB 142 that correspond to terminal links and specific links are excluded from the search by performing processing such as assigning a maximum cost, correcting the link cost so that they are not selected, or assigning a specific flag (hereinafter referred to as "exclusion processing"). Here, an "terminal link" is a link that corresponds to a dead end (a road where only one of both ends of the road is connected to another road). Also, a "specific link" is a link that leads to a dead end (a group of roads that form a bag and cannot be passed through).

(a1) The route searching unit 111 excludes a link in which only one of the nodes located at both ends of the link is connected to another link as a "terminal link" from the search.
(a2) The route searching unit 111 excludes a link in which one of the nodes located at both ends of the link is connected only to a terminal link of rule a1 as a "specific link" from the search.
(a3) Even if a link corresponds to a terminal link under rule a1, if the link length from a node (end node) that is not connected to any other link among the nodes located on both ends of the terminal link to an intermediate point is equal to or longer than a predetermined threshold, the route search unit 111 does not exclude the terminal link from the search.
(a4) Even if a link corresponds to an end link under rule a1, if the end link faces either the departure point or the destination, the route searching unit 111 does not exclude the end link from the search target.
(a5) When all links correspond to the terminal links of rule a1 or the specific links of rule a2, the route searching unit 111 does not exclude the terminal links and the specific links from the search targets.

Figure 4 is a diagram for explaining a specific example of rule a1. Figure 4 (A) shows an example of a search route RT before the exclusion process. Figure 4 (B) shows an example of a search route RTa after the exclusion process. Note that the nodes with diagonal hatching in Figure 4 mean nodes (end nodes) that are not connected to other links. This point is the same in the figures after Figure 4. As shown in Figure 4 (A), assume that the waypoint WP is set on the link EL. In the link EL, only one of the nodes N2 and N3 located at both ends of the link EL (node N2) is connected to other links. In such a case, the route search unit 111 excludes the link EL from the search target by performing an exclusion process on the link EL, assuming that the link EL corresponds to an end link in accordance with rule a1. As a result, a route RTa that does not include the link EL is calculated as shown in Figure 4 (B). The route RTa is a route that does not include a U-turn on the link EL (see the route RT before the exclusion process). In addition, as shown in FIG. 4(B), the route search unit 111 may move the symbol display position of the waypoint WP to a position on the route RTa that is closest to the original position of the waypoint WP (waypoint WPa).

Figure 5 is a diagram for explaining a specific example of rule a2. Figure 5 (A) shows an example of a search route RT before the exclusion process. Figure 5 (B) shows an example of a search route RTa after the exclusion process. As shown in Figure 5 (A), it is assumed that a waypoint WP is set on a link L1, and the link L1 is connected to a link EL1 and a link EL2 via a node N3. In the link EL1, only one of the nodes N3 and N5 located at both ends of the link EL1 (node N3) is connected to another link. Similarly, in the link EL2, only one of the nodes N3 and N6 located at both ends of the link EL2 (node N3) is connected to another link. Therefore, in accordance with rule a1, the route search unit 111 excludes the links EL1 and EL2 from the search target by performing an exclusion process on the links EL1 and EL2, respectively, assuming that the links EL1 and EL2 correspond to terminal links. In addition, one of the nodes N2 and N3 located at both ends of link L1 (node N3) is connected only to the terminal links (EL1 and EL2) of rule a1. Therefore, in accordance with rule a2, the route search unit 111 determines that link L1 corresponds to a specific link and performs an exclusion process on link L1, thereby excluding link L1 from the search target. As a result, as shown in FIG. 5(B), a route RTa that does not include links L1, EL1, and EL2 is calculated. This is a route that does not include a U-turn on link L1 (see route RT before the exclusion process). Note that the route search unit 111 may move the symbol display position of the waypoint WP (waypoint WPa), as in FIG. 4.

Figure 6 is a diagram for explaining a specific example of rule a3. Figure 6 (A) is a diagram for explaining a specific example of rule a3. The link connection relationship and the intermediate points in Figure 6 (A) are the same as those in Figure 5. On the other hand, in Figure 6 (A), the link length of link EL1 is longer than that in the example of Figure 5. As described in Figure 5, link EL1 corresponds to a terminal link. Of the nodes N3 and N5 located at both ends of link EL1, the node N5 that is not connected to other links is called the "end node". In link EL1, the link length A1 from the end node N5 to the intermediate point WP is equal to or greater than a predetermined threshold value X1. Therefore, in accordance with rule a3, the route search unit 111 does not perform an exclusion process on link EL1 and does not exclude it from the search target (i.e., treats link EL1 as a link that does not fall under rule a1). The threshold value X1 can be set arbitrarily, and may be registered or changed by the user of the client 30. Furthermore, link L1 is not subject to exclusion processing and is not excluded from the search because one of the nodes N2 and N3 located at both ends of link L1 is not a link (specific link) in which the other is connected only to the terminal link of rule a1.

6B is a diagram for explaining rules that may be executed in addition to rule a3. In addition to the above-mentioned rules a1 to a5, the route search unit 111 may determine links not to be searched in accordance with the following rule a31.
(a31) Even if a link corresponds to a specific link of rule a2, if the link length from a node (entrance node) other than the node connected to the terminal link among the nodes located at both ends of the specific link to the intermediate point is equal to or longer than a predetermined threshold, the route search unit 111 does not exclude the specific link from the search.

The link connection relationship and the intermediate points in FIG. 6(B) are the same as those in FIG. 5. On the other hand, in FIG. 6(B), the link length of the link L1 is longer than that in the example in FIG. 5. As described in FIG. 5, the link L1 corresponds to a specific link, and the links EL1 and EL2 correspond to terminal links. Of the nodes N2 and N3 located at both ends of the link L1, the node N2 different from the node N3 connected to the terminal links EL1 and EL2 is called an "entrance node". The link length B1 of the link L1 from the entrance node N2 to the intermediate point WP is equal to or greater than a predetermined threshold Y1. Therefore, in accordance with the rule a31, the route search unit 111 does not perform an exclusion process on the link L1 and does not exclude it from the search target (i.e., the link L1 is treated as a link that does not correspond to the rule a2). The threshold Y1 can be set arbitrarily, and may be registered or changed by the user of the client 30. The threshold Y1 may be the same value as the threshold X1 in FIG. 6(A).

The route searching unit 111 may determine which links are not to be searched in accordance with the following rules b3 and b31, instead of the above-mentioned rules a3 and a31.
(b3) Even if a link corresponds to an end link of rule a1, if the link length of the end link (i.e., the link length stored in the route information DB 142) is equal to or greater than a predetermined threshold, the route search unit 111 does not exclude the end link from the search.
(b31) Even if a link corresponds to a specific link of rule a2, if the link length of the specific link (i.e., the link length stored in the route information DB 142) is equal to or greater than a predetermined threshold, the route search unit 111 does not exclude the specific link from the search.

The route searching unit 111 may determine which links are not to be searched in accordance with the following rules c3 and c31, instead of the above-mentioned rules a3 and a31.
(c3) Even if a link corresponds to a terminal link of rule a1, if the end node of the terminal link is not included within a specified area from a specified position, the route searching unit 111 does not exclude the terminal link from the search target.
(c31) Even if a link corresponds to a specific link of rule a2, if the entrance node of the specific link is not included within a specified area from a specified position, the route searching unit 111 does not exclude the specific link from the search target.
The predetermined position of rules c3 and c31 can be determined arbitrarily, and can be, for example, the position of the route point WP, the node N3 closest to the route point WP, etc. The predetermined area of rules c3 and c31 means an arbitrary range defined with the predetermined position as the center, and can be, for example, a criterion such as within the frame of a virtual circle having a predetermined radius centered on the predetermined position.

Figure 7 is a diagram for explaining specific examples of rules a4 and a5. Figure 7 (A) shows a specific example of rule a4. The link connection relationship in Figure 7 (A) is the same as in Figure 4, but in Figure 7 (A), destination G is set on link EL. Link EL corresponds to a terminal link as explained in Figure 4. Link EL is a link facing either the departure point or the destination (destination G in the illustrated example). Therefore, in accordance with rule a4, the route search unit 111 does not perform an exclusion process on link EL and does not exclude it from the search target (i.e., link EL1 is treated as a link that does not fall under rule a1). As a result, in the example of Figure 7 (A), a route RT to destination G on link EL is calculated.

Figure 7 (B) shows a specific example of rule a5. The link connection relationship and the intermediate points in Figure 7 (B) are the same as those in Figure 5, but in Figure 7 (B), in addition to nodes N5 and N6, nodes N1 and N4 also correspond to end nodes. Also, in Figure 7 (B), the destination G is set on link EL3. Link EL3 is a terminal link in which only one (node N2) of nodes N1 and N2 located at both ends of link EL3 is connected to another link. Similarly, link EL4 is a terminal link in which only one (node N2) of nodes N2 and N4 located at both ends of link EL4 is connected to another link. Therefore, in accordance with rule a5, the route search unit 111 does not perform an exclusion process on terminal links EL1, EL2, EL3, EL4 and specific link L1, and does not exclude them from the search (i.e., links EL1, EL2, EL3, EL4 are treated as links that do not fall under rule a1, and link L1 is treated as a link that does not fall under rule a2). As a result, a route RT including a U-turn on link L1 is calculated, as shown in FIG. 7(B).

The route search unit 111 does not apply rules a1 to a5 to links that are not terminal links in terms of the link connections but are impassable due to road closures or restrictions, etc.

In step S104 of FIG. 3, the route search unit 111 determines whether the route obtained in step S102 includes an excluded route. Here, the "excluded route" can be arbitrarily defined; for example, a U-turn route can be the excluded route. In this case, the route search unit 111 analyzes the route (link sequence) obtained in step S102, and can determine that a U-turn route is included if a round trip on the same link is included (specifically, if forward travel on a certain link A and reverse travel on link A are included). If an excluded route is included (step S104: YES), the route search unit 111 transitions the process to step S106. On the other hand, if an excluded route is not included (step S104: NO), the route search unit 111 transitions the process to step S108.

Figure 8 is a diagram explaining a specific example of a route to be excluded. Assume that the route RT shown in Figure 8 is calculated as a result of the route search in step S102. In this case, the route search unit 111 determines that the route RT includes a U-turn route. Note that in step S104, the route search unit 111 may determine the route to be excluded by taking into account the link width (road width). For example, if the link width is greater than a predetermined value, the route search unit 111 may determine that the route is a main road on which a U-turn is possible, and determine that the route to be excluded is not included (step S104: NO). This predetermined value serving as a criterion can be determined arbitrarily.

In step S106, the route search unit 111 performs an exclusion process on the links that make up the route to be excluded, thereby excluding the links that make up the route to be excluded from the search. After that, the route search unit 111 performs a route search again, and transitions the process to step S108.

In step S108, the route search unit 111 generates delivery route information and transmits it to the client 30 to output it. Specifically, the route search unit 111 searches the guidance information DB 143 to obtain information on parking spaces along the route (delivery route) searched in step S102 or step S104 (location information of the parking space, type of parking space, size of the parking space, time period during which the parking space is available, etc.). The route search unit 111 then transmits the route searched in step S102 or step S104 and the obtained information on the parking space as "delivery route information" to the client 30. Note that the description "step S102 or step S104" means that if a re-search is performed in step S104, the search result in step S104 is used, and if a re-search is not performed in step S104, the search result in step S102 is used.

Figure 9 is a diagram showing an example of a guidance screen W1 displayed on the client 30. After obtaining delivery route information from the server 10, the guidance unit 311 of the client 30 outputs a screen W1 for providing guidance on the delivery route to the input/output unit 350. As shown in Figure 9, the screen W1 includes a map view V1, a delivery destination list view V2, and a guidance view V3.

The map view V1 displays a map. The map displays a current location symbol PL, a delivery route RT, a delivery destination symbol S1 plotted at the first delivery destination position, a delivery destination symbol S2 plotted at the second delivery destination position, and symbols PS1 to PS3 representing the positions of parking spaces along the delivery route RT. Here, as shown in the map view V1 of FIG. 9, the first delivery destination S1 is set on the terminal link. However, as a result of the route search process described in FIG. 3 suppressing the calculation of routes including dead ends and cul-de-sacs, the delivery route RT is a route that does not include the terminal link facing the delivery destination S1. Here, when the user taps on any of the parking spaces PS1 to PS3, the guidance unit 311 may display detailed information of the tapped parking space (for example, the type of parking space, the size of the parking space, the time period during which the parking space is available, etc.) in any manner, such as a balloon or a separate window. The parking space PS3 is located slightly away from the delivery route RT. In this way, the route search unit 111 may add information about parking spaces around the delivery route RT to the delivery route information in addition to information about parking spaces along the delivery route RT (Figure 3: step S108).

In the delivery destination list view V2, package information on packages to be delivered (delivery destination address, delivery destination latitude and longitude, presence or absence of a delivery box at the delivery destination, nameplate information, remarks information, delivery time designation, availability of a delivery box, drop-off information, etc.) is displayed in list form. In the guidance view V3, the first stopover point, in other words, the estimated time of arrival at the first delivery destination S1 and the distance from the current position PL to the first delivery destination S1 are displayed. Note that the screen W1 shown in FIG. 9 is merely an example, and various modifications can be made. For example, the delivery destination list view V2 and the guidance view V3 may be omitted. In this case, for example, when the user taps on the delivery destinations S1 and S2, package information on packages to be delivered to the tapped delivery destination may be displayed in any manner, such as a balloon or a separate window. For example, the estimated time of arrival at the first delivery destination S1 and the distance from the current position PL to the first delivery destination S1 may be output by voice together with or instead of the screen display.

As described above, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 searches for a route from the road network data stored in the route information DB 142, excluding terminal links (i.e., links that are dead ends), which are links in which only one of the nodes located at both ends of the link is connected to another link (step S102: rule a1). Therefore, it is possible to provide a route search device (server 10) that can suppress guidance of routes that include dead ends. Also, according to the navigation system 1 of the first embodiment, the determination of whether a link is a terminal link (a link that is a dead end) is performed using the connection relationship of the links in the route information DB 142 used for route search (rule a1). Therefore, compared to the case where special information is required separately, guidance of routes that include dead ends can be suppressed without being affected by the availability of information (FIG. 4).

According to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 searches for a route from the road network data stored in the route information DB 142, excluding from the search target, in addition to the terminal links, specific links (i.e., links for entering a dead end) in which one of the nodes located at both ends of the link is connected only to the terminal link (step S102: rule a2). Therefore, it is possible to provide a route search device (server 10) that can suppress guidance of routes that include dead ends. According to the navigation system 1 of the first embodiment, the determination of whether a link is a specific link (a link for entering a dead end) is performed using the connection relationship of the links in the route information DB 142 used for route search (rule a2). Therefore, compared to the case where special information is required separately, guidance of routes that include dead ends can be suppressed without being affected by the availability of information (FIG. 5).

In cases where the road length is long even if the link is a dead end, there is a demand for guidance on a route that includes the dead end. In this regard, according to the navigation system 1 of the first embodiment, when a node that is not connected to any other link among the nodes located at both ends of a terminal link is set as an end node, if the link length from the end node to the intermediate point is equal to or greater than a predetermined threshold, the route search unit 111 of the server 10 does not exclude the terminal link (link that is a dead end) from the search (step S102: rule a3). For this reason, when the road length is long even if the link is a dead end, the route search unit 111 can provide guidance on a route that includes the dead end (FIG. 6(A)).

Even if it is a dead end, if it faces either the departure point or the destination, there is a demand for guidance on a route that includes the dead end. In this regard, according to the navigation system 1 of the first embodiment, if an end link is a link that faces either the departure point or the destination, the route search unit 111 of the server 10 does not exclude the end link (a link that is a dead end) from the search (step S102: rule a4). Therefore, even if it is a dead end, if it faces either the departure point or the destination, the route search unit 111 can provide guidance on a route that includes the dead end (FIG. 7(A)).

Compared to normal main streets, residential areas with many private homes have many narrow roads where vehicles make U-turns, and there is a lot of traffic of people and bicycles. In this regard, according to the navigation system 1 of the first embodiment, when a searched route includes a route that makes a U-turn at a certain link, the route search unit 111 of the server 10 excludes the links that make up the U-turn route from the search targets, re-searches for the route, and outputs the re-searched route (steps S104, S106, FIG. 8). As a result, according to the route search device (server 10), guidance of routes that include U-turn routes is further suppressed, thereby improving ease of travel on the guided route and improving safety.

In recent years, the popularity of internet shopping has led to an increase in the demand for logistics services, and an increase in the number of people (delivery personnel) engaged in the task of delivering packages such as merchandise to designated destinations. In this regard, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 acquires information on one or more delivery destinations where a user of the route search device (server 10) will stop to deliver a package (step S100), and searches for a route from the departure point to the destination via one or more delivery destinations as intermediate points (step S102). This makes it possible to provide a route search device specialized for delivery services.

Furthermore, there are fewer parking spaces near residential areas where many private homes exist compared to areas near normal main streets. In this regard, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 acquires position information of parking spaces (parking spaces where a vehicle can be safely parked) along the searched route (step S108), and outputs the position information of the parking spaces together with the searched route (FIG. 9). This makes it possible to prevent users from parking their vehicles on unsafe roadsides in residential areas where there are few parking spaces, thereby improving convenience and safety for users.

B. Second embodiment:
10 is a diagram showing a schematic configuration of a navigation system 1A of the second embodiment. The navigation system 1A of the second embodiment includes a server 10A instead of the server 10 in the configuration described in the first embodiment. In the second embodiment, the process content of the route search process executed by the server 10A is different from that of the first embodiment.

Figure 11 is a flowchart showing an example of the processing procedure of the route search process of the second embodiment. The CPU 110A of the server 10A has a route search unit 111A instead of the route search unit 111. The route search unit 111A executes the route search process shown in Figure 11. The route search process of Figure 11 is the same as the route search process of Figure 3, except that steps S104 and S106 (Figure 3: re-search when an excluded route is included) are not executed.

In this way, the configuration of the navigation system 1A can be modified in various ways, and re-searching when an excluded route is included may be omitted. With such a navigation system 1A of the second embodiment, it is possible to achieve the same effects as the first embodiment described above. Furthermore, with the navigation system 1A of the second embodiment, it is possible to reduce the processing load on the server 10A and shorten the time from when a processing request is made by the client 30 to when the server 10 responds (step S108 in FIG. 11: sending the delivery route).

C. Third embodiment:
12 is a diagram showing a schematic configuration of a navigation system 1B of the third embodiment. The navigation system 1B of the third embodiment includes a server 10B instead of the server 10 in the configuration described in the first embodiment, and does not include a client 30. The server 10B of the third embodiment executes processing without cooperating with the client 30.

In addition to the map information DB 141, route information DB 142, and guidance information DB 143, the storage unit 140B of the server 10B also stores delivery plan information 144 in advance. The content of the delivery plan information 144 is the same as the delivery plan information 341 described in FIG. 2. Furthermore, the storage unit 140B stores delivery route information 145 as a result of the route search process (FIG. 3). The CPU 110B of the server 10B has a route search unit 111B instead of the route search unit 111. In step S100 of the route search process (FIG. 3), the route search unit 111B acquires the delivery plan information 144 from the storage unit 140B. Furthermore, in step S108 of the route search process (FIG. 3), the route search unit 111B stores the generated delivery route information in the delivery route information 145.

In this way, the configuration of the navigation system 1B can be modified in various ways, and the server 10B may output the generated delivery route information to the memory unit 140B of the server 10B. The server 10B may also acquire delivery plan information 144 from other devices or servers connected via the network. Similarly, the server 10B may output the delivery route information generated in the route search process (Figure 3) to other devices or servers connected via the network. The navigation system 1B of this third embodiment can also achieve the same effects as the first embodiment described above.

D. Fourth embodiment:
13 is a diagram showing a schematic configuration of a navigation system 1C of the fourth embodiment. The navigation system 1C of the fourth embodiment includes a client 30C instead of the client 30 in the configuration described in the first embodiment, and does not include the server 10. The client 30C of the fourth embodiment executes processing without cooperating with the server 10. In this embodiment, the client 30C corresponds to a "route search device."

In addition to delivery plan information 341 and delivery route information 342, the memory unit 340C of the client 30C also prestores a map information DB 343, a route information DB 344, and a guidance information DB 345. The map information DB 343 is similar to the map information DB 141 described in FIG. 1. The route information DB 344 is similar to the route information DB 142 described in FIG. 1. The guidance information DB 345 is similar to the guidance information DB 143 described in FIG. 1. The CPU 310C of the client 30C further has a route search unit 312 in addition to the guidance unit 311. The route search unit 312 is a functional unit that performs the same processing as the route search unit 111 described in FIG. 1 and FIG. 3.

In this way, the configuration of the navigation system 1C can be modified in various ways, and the client 30C can be configured as a route search device. The map information DB 343, route information DB 344, and guidance information DB 345 can be stored in an external data server, and the route search unit 312 can connect to the data server each time in the process of FIG. 3 to obtain the necessary data. In addition, in order to execute the route search process (particularly step S102 in FIG. 3) in the client 30C, which has a lower processing power than the server 10 (FIG. 1), restrictions can be imposed on the search speed and search distance range in the route search process. The navigation system 1C of this fourth embodiment can also achieve the same effects as the first embodiment described above.

E. Variations:
In the above embodiment, a part of the configuration realized by hardware may be replaced by software, and conversely, a part of the configuration realized by software may be replaced by hardware. In addition, the following modifications are also possible.

Variation 1:
In the above embodiment, an example of the configuration of the navigation system, the server, and the client is shown. However, the configuration of each device can adopt any aspect. For example, at least a part of each DB of the server and the client may be stored in a device other than the server and the client (including an external server connected via the Internet).

In the above embodiment, the navigation system is a system that provides delivery route guidance, in other words, a system used in delivery operations. However, the navigation system is not limited to delivery operations, and can be configured as a system for general users that provides normal route guidance.

Variation 2:
In the above embodiment, the route search process (FIGS. 3 and 11) has been described by way of an example of a processing procedure. However, these processing procedures can be modified in various ways, and the processing contents in each step may be added, omitted, or changed, and the execution order of each step may be changed.

For example, in step S102, rules a1 to a5 are illustrated for excluding terminal links and specific links from search targets. However, any combination of one or more of these rules a1 to a5 may be used. For example, only rule a1 may be executed, or a combination of rules a1 and a3 may be executed.

For example, in step S108, the delivery route information includes the route searched for in step S102 or step S104 and parking space information. However, the parking space information may be omitted. In addition, the delivery route information may include other information.

Variation 3:
The present invention is not limited to the above-mentioned embodiments, examples, and modifications, and can be realized in various configurations without departing from the spirit of the present invention. For example, the technical features in the embodiments, examples, and modifications corresponding to the technical features in each aspect described in the Summary of the Invention column can be appropriately replaced or combined to solve some or all of the above-mentioned problems or to achieve some or all of the above-mentioned effects. Furthermore, if a technical feature is not described as essential in this specification, it can be appropriately deleted.

1, 1A to 1C... Navigation system 10, 10A, 10B... Server 30, 30C... Client 110, 110A, 110B... CPU
111, 111A, 111B...route search unit 120...communication unit 130...ROM/RAM
140, 140B... Storage section 141... Map information DB
142...Route information DB
143...Guidance information DB
144: Delivery plan information 145: Delivery route information 310, 310C: CPU
311: Guidance section 312: Route search section 320: Communication section 330: ROM/RAM
340, 340C... Storage unit 341... Delivery plan information 342... Delivery route information 343... Map information DB
344...Route information DB
345...Guidance information DB
350...Input/output section 360...Current position acquisition section

Claims (8)

A route search device, comprising:
a route information storage unit that stores road network data including information on nodes and information on links connecting the nodes;
a route search unit that searches for a route from a departure point to a destination via one or more intermediate points ;
Equipped with
The route search unit is
When a link is defined as a terminal link, only one of the nodes at both ends of the link is connected to another link.
Even if the intermediate point is set on the terminal link, the route is searched for from the road network data while excluding the terminal link from the search target;
A route search device that outputs the searched route. The route search device according to claim 1,
The route search unit searches for the route from the road network data by excluding from the search target a specific link in which one of the nodes located at both ends of the link is connected only to the terminal link, in addition to the terminal link. 3. A route search device according to claim 1, further comprising:
A route search device, wherein when the terminal link is a link facing either the departure point or the destination, the route search unit searches for the route without excluding the terminal link from the search target. A route search device according to any one of claims 1 to 3 ,
The route search unit, when the intermediate point is set on the terminal link, moves a symbol display position of the intermediate point displayed on a guidance screen of the searched route to a position on the searched route that is closest to the position of the intermediate point . A route search device according to any one of claims 1 to 4 ,
The route search unit is
Acquire information on one or more delivery destinations where a user of the route search device stops for delivery of a package;
A route search device that searches for the route from the departure point to the destination via the one or more delivery destinations as the intermediate points. 6. A route search device according to claim 5 ,
The route search unit is
acquiring location information of parking spaces located near roads and where the vehicle can be safely parked, the location information being along the searched route;
A route search device that outputs the acquired position information of the parking space in addition to the searched route. A route search method, comprising:
Executing a step of searching for a route from a departure point to a destination via one or more intermediate points using road network data including information on nodes and information on links connecting the nodes;
In the searching step,
When a link is defined as a terminal link, only one of the nodes at both ends of the link is connected to another link.
Even if the intermediate point is set on the terminal link, the route is searched for from the road network data while excluding the terminal link from the search target;
and outputting the searched route. A computer program comprising:
A computer program for executing a step of searching for a route from a departure point to a destination via one or more intermediate points by using road network data including node information and link information connecting the nodes, the computer program comprising:
In the searching step,
When a link is defined as a terminal link, only one of the nodes at both ends of the link is connected to another link.
Even if the intermediate point is set on the terminal link, the route is searched for from the road network data while excluding the terminal link from the search target;
A computer program that outputs the searched route.

Images