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

Description

This invention relates to a pathfinding device, a pathfinding method, and a computer program.

Navigation systems that provide route guidance from a starting point to a destination are well-known. Since such navigation systems are often installed in vehicles and used to guide the vehicle's journey, there is a need to avoid searching for routes that include dead ends or cul-de-sacs where the vehicle would have to make a U-turn.

In this regard, for example, Patent Document 1 discloses that in a navigation device, if there is first information indicating a dead end within or beyond a predetermined section, the predetermined section is excluded from the selection of the driving route, thereby preventing the search for routes that cannot be used as a driving route. For example, Patent Document 2 discloses that in a navigation device, when a guidance route that involves a U-turn at the end of a dead end is set, a U-turn guidance image is displayed. For example, Patent Document 3 discloses that in a car navigation device, when it is determined that a road is a dead end, guidance regarding that dead end road is provided.

Japanese Patent Publication No. 2000-18958 Japanese Patent Publication No. 2010-243187 Japanese Patent Publication No. 2006-220562

Incidentally, in recent years, the demand for logistics services has increased due to the spread of internet shopping, and the number of people engaged in the work of delivering goods and other packages to designated delivery destinations (hereinafter also referred to as "delivery personnel") has increased. From the perspective of operational efficiency, delivery personnel are assigned predetermined service areas and deliver packages to individual homes within their assigned area. Here, areas with many individual homes are characterized by a higher number of dead ends and cul-de-sacs where vehicles have to make U-turns, and by a higher volume of pedestrian and bicycle traffic, compared to typical main roads. Therefore, route search devices (navigation devices) used in delivery services are particularly required to suppress guidance on routes that include dead ends and cul-de-sacs.

In this regard, the navigation device described in Patent Document 1 uses first information to determine if a route is a dead end. Therefore, in areas where first information is unavailable, it has the problem of guiding users along routes that include dead ends or cul-de-sacs. In particular, residential areas with many private homes tend to have less readily available information compared to office districts. In delivery services, however, suppressing guidance to such routes (routes including dead ends or cul-de-sacs) in residential areas is even more important from both a demand and safety perspective. Furthermore, the navigation devices described in Patent Documents 2 and 3 only provide information on U-turns and dead-end roads, and do not consider suppressing guidance to routes including dead ends or cul-de-sacs. It should be noted that, as mentioned above, this problem is not limited to route search devices used in delivery services, but is also common to route search devices for general users.

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

The present invention has been made to solve at least some of the above-mentioned problems and can be realized in the following forms: A route search device comprising: a route information storage unit that stores road network data including node information and link information connecting nodes; and a route search unit that searches for a route from a starting point to a destination via one or more waypoints, wherein the route search unit searches for a route from the road network data, excluding terminal links, which are links where only one of the nodes located at both ends of the link is connected to another link, and outputs the searched route, wherein, when the node located at both ends of the terminal link that is not connected to another link is set as the endpoint node, and the nearest waypoint to the endpoint node is set as the reference waypoint, if the link length from the endpoint node to the reference waypoint is greater than or equal to a predetermined threshold, the terminal link is not excluded from the search.

(1) According to one embodiment of the present invention, a route search device is provided. This route search device comprises 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 a route from the road network data, excluding terminal links (links where only one of the nodes at both ends of the link is connected to another link), and outputs the searched route.

A "dead end" refers to a road where only one of its ends connects to another road. In this configuration, the route search unit excludes terminal links (i.e., dead ends)—links where only one of the nodes at either end of the link connects to another link—from the road network data before searching for a route. Therefore, a route search device capable of suppressing guidance for routes including dead ends can be provided. Furthermore, in this configuration, the determination of whether a link is a terminal link (a dead end) is made using the link connection relationships in the road network data used for route search. Therefore, compared to cases requiring separate special information, guidance for routes including dead ends can be suppressed regardless of the availability of such information.

(2) In the above-described path search device, the path search unit may search for the path by excluding from the road network data any specific links in which one of the nodes located at both ends of the link is connected only to the end link, in addition to the terminal links.
A "dead end" refers to a group of roads that are shaped like a bag and cannot be passed through. With this configuration, the route search unit searches for a route from the road network data, excluding not only terminal links but also specific links where one of the nodes at both ends of the link is connected only to the terminal link (i.e., links leading to dead ends). Therefore, it is possible to provide a route search device that can suppress the guidance of routes that include dead ends. Furthermore, with this configuration, the determination of whether or not a link is a specific link (a link leading to a dead end) is made using the link connection relationships in the road network data used for route search. Therefore, compared to cases where special information is required separately, it is possible to suppress the guidance of routes that include dead ends without being affected by the availability of information.

(3) In the above-described pathfinding device, the pathfinding unit searches for a path from the starting point to the destination via predetermined intermediate points, and when the node located at both ends of the terminal link that is not connected to other links is designated as the terminal node, if the link length from the terminal node to the intermediate point is greater than or equal to a predetermined threshold, the pathfinding unit may search for the path without excluding the terminal link from the search.
Even if a road is a dead end, if the road length is long, there is a request to be guided along a route that includes the dead end. In this regard, with this configuration, the route search unit, when it sets a node located at both ends of a terminal link that is not connected to other links as the endpoint node, will not exclude the terminal link (the dead end link) from the search if the link length from the endpoint node to the intermediate point is greater than or equal to a predetermined threshold. Therefore, even if a road is a dead end, if the road length is long, the route search unit can guide along a route that includes the dead end.

(4) In the above-described pathfinding device, if the terminal link is a link facing either the departure point or the destination, the pathfinding unit may search for the path without excluding the terminal link from the search.
There is a demand for route guidance that includes a dead end, even if it faces either the starting point or the destination. In this regard, with this configuration, the route search unit does not exclude terminal links (links that are dead ends) from the search if the terminal link faces either the starting point or the destination. Therefore, the route search unit can guide users along a route that includes a dead end, even if it faces either the starting point or the destination.

(5) In the above-described path search device, if the path search unit finds a route that involves making a U-turn at a certain link, it may exclude the link constituting the U-turn route from the search target, re-search for the path, and output the re-searched path.
Residential areas, with their many private homes, often have narrow roads where vehicles need to make U-turns, and also experience heavy traffic from pedestrians and cyclists, compared to typical main roads. In this regard, according to this configuration, if the route search unit finds a route that includes a U-turn at a certain link, it excludes the link constituting the U-turn route from the search, re-searches for the route, and outputs the re-searched route. As a result, this route search device further suppresses the guidance of routes that include U-turn routes, thereby improving the ease of driving on the guided route and enhancing safety.

(6) In the above-described configuration of the route search device, the route search unit may acquire information on one or more delivery destinations that the user of the route search device will stop at 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 stops.
In recent years, the spread of internet shopping has increased the demand for logistics services, and the number of people (delivery personnel) engaged in the work of delivering goods and other packages to designated delivery destinations has increased. In this regard, according to this configuration, the route search unit acquires information on one or more delivery destinations that the user of the route search device (delivery person) will stop at for the delivery of the package, and searches for a route from the starting point to the destination, passing through one or more delivery destinations as intermediate stops, thereby providing a route search device specifically for delivery services.

(7) In the above-described path search device, the path search unit may acquire location information of parking spaces located near a road where it is possible to safely park a vehicle, and may output the acquired location information of the parking spaces along the searched path.
In residential areas with many private homes, there are fewer parking spaces compared to areas near typical main roads. In this configuration, the route search unit acquires location information of parking spaces (parking spaces where vehicles can be safely parked) along the searched route and outputs the location information of these parking spaces along with the searched route. Therefore, in residential areas with few parking spaces, it is possible to prevent users (delivery personnel) from parking their vehicles on unsafe roadsides, thereby improving both user convenience and safety.

Furthermore, the present invention can be realized in various forms, for example, as a route search device, a navigation device, a navigation system, a computer program for realizing the functions of these devices and systems, a server device for distributing the computer program, and a non-temporary storage medium storing the computer program.

This figure shows a schematic configuration of a navigation system as one embodiment of the present invention. This figure shows an example of delivery plan information. This flowchart shows an example of the processing steps for route finding. This is a diagram illustrating a specific example of rule a1. This diagram illustrates a specific example of rule a2. This is a diagram illustrating a specific example of rule a3. This diagram illustrates specific examples of rules a4 and a5. This diagram illustrates specific examples of routes that should be excluded. This figure shows an example of a guidance screen displayed to the client. This figure shows the schematic configuration of the navigation system according to the second embodiment. This flowchart shows an example of the processing procedure for the pathfinding process in the second embodiment. This figure shows the schematic configuration of the navigation system according to the third embodiment. This figure shows the schematic configuration of the navigation system according to the fourth embodiment.

A. First embodiment:
Figure 1 shows a schematic configuration of a navigation system 1 as one embodiment of the present invention. The navigation system 1 is a system whose users are persons engaged in logistics operations, particularly the operation of delivering goods and other packages to designated delivery destinations (hereinafter also referred to as "delivery personnel"). The navigation system 1 exemplified here outputs guidance information to the user (delivery personnel), including route guidance to the delivery destination of the package to be delivered (hereinafter also referred to as "package to be delivered") and information about the delivery destination, and is used to facilitate delivery operations.

The navigation system 1 of this embodiment can suppress guidance on routes including dead ends and cul-de-sacs through the route search process described later. Here, "dead end" refers to a road where only one of its ends connects to another road. "Cul-de-sac" refers to a group of roads that are shaped like a bag and cannot be passed through.

Navigation system 1 comprises a server 10 and a client 30. Server 10 is connected to the Internet (INT) via wired communication. Client 30 is connected to the Internet (INT) via wireless communication through a communication carrier BS. The communication carrier BS includes transmitting and receiving antennas, wireless base stations, and switching stations. In other words, server 10 and client 30 can communicate with each other via the Internet (INT).

Server 10 uses the delivery plan information 341 (details described later) obtained from client 30 to search for a route (hereinafter also referred to as the "delivery route") where the delivery addresses of the packages to be delivered are set as intermediate points. Server 10 corresponds to a "route search device." Server 10 comprises 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 various parts of the server 10 by loading computer programs stored in the ROM 130 into the RAM 130 and executing them. 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 the origin to the 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 consists of a hard disk, flash memory, memory card, etc. The storage unit 140 pre-stores a map information database 141, a route information database 142, and a guidance information database 143. In the following explanation, the database will also be simply referred to as "DB".

The map information database (DB141) is a database that stores data representing map images. This data includes information necessary for map display, such as terrain, buildings, and road shapes. The route information database (DB142) is a database that stores road network data. This road network data includes node information, which represents the locations of landmarks such as intersections and stations, and link information, which represents the roads connecting these nodes. Node information includes node location information, node type, node name, and other node information. Link information includes link cost for each mode of transport (average travel time for the road represented by the link), link type, link name, link status, and other link information. The route information database (DB142) corresponds to the "route information storage unit."

The guidance information DB 143 is a database that stores information about parking spaces. Here, "parking space" refers to a location near a road where vehicles can be safely parked. In this embodiment, parking spaces are not limited to so-called parking lots. Information about parking spaces may include not only the location of the parking space, but also the type of parking space (whether it is a parking lot or not, etc.), the size of the parking space, and the time period during which the parking space is available. Note that the guidance information DB 143 may be stored on a server other than server 10. In that case, server 10 may connect to the other server as needed during the processing described later and obtain the information about parking spaces.

The client 30 can be configured as any device, such as a smartphone (as shown in the diagram), a personal computer, an in-vehicle device, or a wearable device. The client 30 comprises a CPU 310, a communication unit 320, a ROM/RAM 330, a storage unit 340, an input/output unit 350, and a current location acquisition unit 360. These units are interconnected by a bus (not shown).

The CPU 310 controls various parts of the client 30 by loading 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 obtains delivery route information 342 from the server 10. Using the obtained delivery route information 342, the guidance unit 311 outputs the delivery route (path) from the input/output unit 350, thereby guiding the user of the client 30 along the delivery route.

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

The storage unit 340 consists of a hard disk, flash memory, memory card, etc. Delivery plan information 341 is pre-stored in the storage unit 340. Furthermore, delivery route information 342, obtained from the server 10 through a process described later, is also stored in the storage unit 340.

Figure 2 shows an example of delivery plan information 341. The delivery plan information 341 stores information about packages to be delivered on that day by the client 30's users (hereinafter also referred to as "package information"). As shown in the figure, each package information includes, for example, the delivery address, delivery address latitude and longitude, presence or absence of a delivery box at the delivery address, nameplate information, remarks information, specified delivery time, whether or not a delivery box is available, and information on unattended delivery. Unattended delivery information may include whether or not unattended delivery is possible, the specified location for unattended delivery, and the specified conditions for unattended delivery (date and time, weather, etc.). Note that package information may also include other information not shown in the figure.

Returning to Figure 1, let's continue the explanation. 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 can employ a touch panel as an input unit, a touch panel as a display unit (output unit), an LCD panel, etc. The current location acquisition unit 360 receives radio waves transmitted from satellites constituting the GPS (Global Positioning System) or QZSS (Quasi-Zenith Satellite System) and acquires current location information (latitude and longitude) representing the current location of the client 30. Since the client 30 is carried by the user, the current location acquired by the current location acquisition unit 360 can be considered equivalent to the user's current location.

Figure 3 is a flowchart illustrating an example of the processing procedure for route search. Route search is a process executed on the server 10 to search for a delivery route. The route search is initiated by a processing request from the client 30. The client 30's processing request 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 client 30's processing request.

In step S102, the route search unit 111 refers to the delivery plan information 341 obtained in step S100 and performs a route search, setting each delivery address of package information 1 to n (where n is an arbitrary natural number) as an intermediate point. The departure point at this time may be the current location obtained by the current location acquisition unit 360, or a predetermined location (e.g., the user's home or the delivery service office). The destination can also be a predetermined location (e.g., the user's home or the delivery service office). The route search can be performed using the route information DB 142 and employing the well-known Dijkstra's algorithm or the well-known Aester search algorithm.

In step S102, the route search unit 111 excludes terminal links and specific links from the search target in accordance with the following rules a1 to a5. Specifically, it excludes links in the route information DB 142 that correspond to terminal links and specific links by performing processes such as assigning a maximum cost, correcting the link cost to exclude them from selection, or assigning a predetermined flag (hereinafter also referred to as "exclusion processing"). Here, a "terminal link" is a link that corresponds to a dead end (a road where only one of the ends connects to another road). A "specific link" is a link that leads to a dead end (a group of roads that form a cul-de-sac and cannot be passed through).

(a1) The route search unit 111 excludes links from the search if only one of the nodes located at both ends of the link is connected to another link, as these are considered "end links".
(a2) The route search unit 111 excludes links from the search if one of the nodes located at both ends of the link is connected only to the terminal link of rule a1, as a "specific link".
(a3) Even if a link is a terminal link of rule a1, the route search unit 111 will not exclude the terminal link from the search if the link length from the node located at both ends of the terminal link that is not connected to other links (end node) to the intermediate point is equal to or greater than a predetermined threshold.
(a4) The route search unit 111 does not exclude a link from the search if that link is a terminal link of rule a1, but that link faces either the origin or the destination.
(a5) If all links fall under the terminal links of rule a1 or the specific links of rule a2, the route search unit 111 will not exclude those terminal links and specific links from the search.

Figure 4 illustrates a specific example of rule a1. Figure 4(A) shows an example of the search route RT before exclusion processing. Figure 4(B) shows an example of the search route RTa after exclusion processing. Note that in Figure 4, nodes with hatched lines represent nodes that are not connected to other links (endpoint nodes). This is the same for Figures 4 and subsequent figures. As shown in Figure 4(A), we assume that the waypoint WP is set on link EL. Link EL has only one of the nodes N2 and N3 located at both ends of link EL (node N2) connected to other links. In such a case, the route search unit 111, in accordance with rule a1, considers link EL to be an end link and excludes link EL from the search by performing exclusion processing on link EL. As a result, as shown in Figure 4(B), route RTa that does not include link EL is calculated. Route RTa is a route that does not include U-turns on link EL (see route RT before exclusion processing). Furthermore, as shown in Figure 4(B), the route search unit 111 may move the symbol display position of the waypoint WP to the position closest to the original waypoint WP on the route RTa (waypoint WPa).

Figure 5 illustrates a specific example of rule a2. Figure 5(A) shows an example of the search route RT before exclusion processing. Figure 5(B) shows an example of the search route RTa after exclusion processing. As shown in Figure 5(A), it is assumed that the waypoint WP is set on link L1, and that link L1 is connected to links EL1 and EL2 via node N3. Link EL1 has only one of the nodes N3 and N5 located at both ends of link EL1 (node N3) connected to another link. Similarly, link EL2 has only one of the nodes N3 and N6 located at both ends of link EL2 (node N3) connected to another link. Therefore, the route search unit 111, in accordance with rule a1, considers links EL1 and EL2 to be terminal links and excludes links EL1 and EL2 from the search by performing exclusion processing on links EL1 and EL2, respectively. Furthermore, in link L1, one of the nodes N2 and N3 located at both ends of link L1 (node N3) is connected only to the terminal links (EL1, EL2) of rule a1. Therefore, according to rule a2, the route search unit 111 considers link L1 to be a specific link and excludes it from the search. As a result, as shown in Figure 5(B), a route RTa is calculated that does not include links L1, EL1, and EL2. This route does not include a U-turn on link L1 (see route RT before exclusion). Note that, as in Figure 4, the route search unit 111 may also move the symbol display position of the waypoint WP (waypoint WPa).

Figure 6 illustrates a specific example of rule a3. Figure 6(A) shows a specific example of rule a3. The link connections and intermediate points in Figure 6(A) are the same as in Figure 5. On the other hand, in Figure 6(A), the link length of link EL1 is longer than in the example in Figure 5. Link EL1 corresponds to a terminal link, as explained in Figure 5. Of the nodes N3 and N5 located at both ends of link EL1, node N5, which is not connected to other links, is called the "endpoint node". The link length A1 from the endpoint node N5 to the intermediate point WP of link EL1 is greater than or equal to a predetermined threshold X1. For this reason, the route search unit 111 does not exclude link EL1 in accordance with rule a3 and does not exclude it from the search (i.e., it treats link EL1 as a link that does not fall under rule a1). The threshold X1 can be set arbitrarily, and it may be possible to register or change it by the user of client 30. Furthermore, since link L1 does not fall under the category of a link (specific link) where one of the nodes N2 and N3 located at both ends of link L1 is connected only to the terminal link of rule a1, it is not excluded and is not excluded from the search.

Figure 6(B) illustrates rules that may be executed in addition to rule a3. In addition to the rules a1 to a5 described above, the route search unit 111 may also determine links to be excluded from the search in accordance with the following rule a31.
(a31) Even if a link falls under the specific link of rule a2, the route search unit 111 will not exclude the specific link from the search if the link length from a node at both ends of the specific link that is different from the node connected to the terminal link (the entry node) to the intermediate destination is greater than or equal to a predetermined threshold.

The link connections and intermediate points in Figure 6(B) are the same as in Figure 5. However, in Figure 6(B), the link length of link L1 is longer than in the example in Figure 5. As explained in Figure 5, link L1 corresponds to a specific link, and links EL1 and EL2 correspond to terminal links. Of the nodes N2 and N3 located at both ends of link L1, node N2, which is different from node N3 connected to terminal links EL1 and EL2, is called the "entrance node." The link length B1 from the entrance node N2 to the intermediate point WP of link L1 is greater than or equal to a predetermined threshold Y1. Therefore, the route search unit 111 does not exclude link L1 according to rule a31 and does not exclude it from the search (i.e., it treats link L1 as a link that does not fall under rule a2). The threshold Y1 can be set arbitrarily, and may be registered or changed by the user of client 30. The threshold Y1 may be the same value as the threshold X1 in Figure 6(A).

The route search unit 111 may, instead of following rules a3 and a31, determine which links are excluded from the search in accordance with the following rules b3 and b31.
(b3) Even if a link is a terminal link of rule a1, the route search unit 111 will not exclude the terminal link from the search if the link length of the terminal link (i.e., the link length stored in the route information DB 142) is equal to or greater than a predetermined threshold.
(b31) The route search unit 111 does not exclude a link from the search if the link length of that specific link (i.e., the link length stored in the route information DB 142) is equal to or greater than a predetermined threshold, even if the link falls under the specific link of rule a2.

The route search unit 111 may, instead of following rules a3 and a31, determine which links are excluded from the search in accordance with the following rules c3 and c31.
(c3) The route search unit 111 does not exclude a link from the search even if it is a terminal link of rule a1, if the endpoint node of the terminal link is not included within a predetermined area from a predetermined position.
(c31) The route search unit 111 does not exclude a link from the search if, even if it is a link that falls under the specific link of rule a2, the entry node of the specific link is not included within the predetermined area from the predetermined position.
The predetermined locations in rules c3 and c31 can be arbitrarily determined, for example, the location of a transit point WP or the nearest node N3 from a transit point WP can be used. The predetermined areas in rules c3 and c31 mean any range demarcated with the predetermined location as the center, for example, a criterion such as the area within a virtual circle with a predetermined radius centered on the predetermined location can be used.

Figure 7 illustrates specific examples of rules a4 and a5. Figure 7(A) shows a specific example of rule a4. The link connections in Figure 7(A) are 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 origin or the destination (in this example, destination G). Therefore, the route search unit 111 does not exclude link EL in accordance with rule a4 and does not exclude it from the search (i.e., it treats link EL1 as a link that does not fall under rule a1). As a result, in the example of Figure 7(A), the route RT to destination G on link EL is calculated.

Figure 7(B) shows a specific example of rule a5. The link connections and intermediate points in Figure 7(B) are the same as in Figure 5, but in Figure 7(B), in addition to nodes N5 and N6, nodes N1 and N4 also correspond to endpoint nodes. Also, in Figure 7(B), destination G is set on link EL3. Link EL3 is an end link in which only one of the nodes N1 and N2 located at both ends of link EL3 (node N2) is connected to another link. Similarly, link EL4 is an end link in which only one of the nodes N2 and N4 located at both ends of link EL4 (node N2) is connected to another link. For this reason, the route search unit 111 does not exclude end links EL1, EL2, EL3, EL4 and specific link L1 in accordance with rule a5, and does not exclude them from the search (i.e., links EL1, EL2, EL3, and 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, as shown in Figure 7(B), the route RT, including the U-turn on link L1, is calculated.

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

In step S104 of Figure 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 excluded. In this case, the route search unit 111 analyzes the route (link sequence) obtained in step S102 and determines that a U-turn route is included if it includes a round trip of the same link (specifically, if it includes forward movement of a certain link A and reverse movement of link A). If an excluded route is included (step S104: YES), the route search unit 111 proceeds to step S106. On the other hand, if an excluded route is not included (step S104: NO), the route search unit 111 proceeds to step S108.

Figure 8 illustrates 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 a U-turn route is included in route RT. Note that in step S104, the route search unit 111 may also consider the link width (road width) when determining whether a route should be excluded. For example, if the link width is greater than a predetermined value, the route search unit 111 may determine that it is a main road where a U-turn is possible and that no route to be excluded is included (step S104: NO). This predetermined value can be arbitrarily determined.

In step S106, the route search unit 111 excludes links constituting the excluded route by performing an exclusion process, thereby excluding those links from the search. Subsequently, the route search unit 111 performs another route search and transitions the process to step S108.

In step S108, the route search unit 111 generates delivery route information and outputs it to the client 30. Specifically, the route search unit 111 searches the guidance information DB 143 and obtains 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.). Then, the route search unit 111 transmits the route searched in step S102 or step S104 and the obtained parking space information to the client 30 as "delivery route information." The notation "step S102 or step S104" means that if a re-search is performed in step S104, the search result of step S104 is used; if a re-search is not performed in step S104, the search result of step S102 is used.

Figure 9 shows an example of the 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 screen W1 for guiding the delivery route to the input/output unit 350. As shown in Figure 9, screen W1 includes a map view V1, a delivery destination list view V2, and a guidance view V3.

Map view V1 displays a map. The map displays the current location symbol PL, the delivery route RT, the delivery destination symbol S1 plotted at the first delivery destination location, the delivery destination symbol S2 plotted at the second delivery destination location, and symbols PS1 to PS3 representing the locations of parking spaces along the delivery route RT. Here, as shown in map view V1 of Figure 9, the first delivery destination S1 is set on a terminal link. However, as a result of the route search process described in Figure 3 suppressing the calculation of routes including dead ends and cul-de-sacs, the delivery route RT is defined as a route that does not include the terminal link that delivery destination S1 faces. Here, when the user taps one of the parking spaces PS1 to PS3, the guidance unit 311 may display detailed information about 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 can be used, etc.) in a callout or in a separate window or any other manner. Note that parking space PS3 is located at a location slightly away from the delivery route RT. Thus, the route search unit 111 may add information about parking spaces surrounding the delivery route RT, in addition to information about parking spaces along the delivery route RT, to the delivery route information (Figure 3: Step S108).

The delivery destination list view V2 displays package information for deliverables (delivery address, delivery latitude and longitude, presence or absence of a delivery box at the delivery location, nameplate information, remarks, specified delivery time, availability of delivery boxes, unattended delivery information, etc.) in list format. The guidance view V3 displays the estimated arrival time at the first intermediate stop, in other words, the first delivery destination S1, and the distance from the current location PL to the first delivery destination S1. Note that screen W1 shown in Figure 9 is merely an example, and various changes can be made. For example, the delivery destination list view V2 and guidance view V3 may be omitted. In this case, for example, when the user taps delivery destinations S1 and S2, package information for deliverables at the tapped destination may be displayed in a callout, a separate window, or any other desired manner. For example, the estimated arrival time at the first delivery destination S1 and the distance from the current location PL to the first delivery destination S1 may be output via voice, or alternatively, along with 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) where only one of the nodes at both ends of the link is connected to another link (step S102: rule a1). Therefore, a route search device (server 10) capable of suppressing guidance for routes including dead ends can be provided. Furthermore, according to the navigation system 1 of the first embodiment, the determination of whether or not a link is a terminal link (a link that is a dead end) is made using the link connection relationships in the route information DB 142 used for route search (rule a1). Therefore, compared to cases where special information is required separately, guidance for routes including dead ends can be suppressed without being affected by the availability of information (Figure 4).

Furthermore, 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 not only terminal links but also specific links where one of the nodes at both ends of the link is connected only to the terminal link (i.e., links leading to dead ends) (step S102: rule a2). Therefore, a route search device (server 10) capable of suppressing guidance for routes including dead ends can be provided. Also, according to the navigation system 1 of the first embodiment, the determination of whether or not a link is a specific link (a link leading to a dead end) is made using the link connection relationships in the route information DB 142 used for route search (rule a2). Therefore, compared to cases where special information is required separately, guidance for routes including dead ends can be suppressed without being affected by the availability of information (Figure 5).

Even if a road is a dead end, if the road length is long, there is a request to be guided along a route that includes the dead end. In this regard, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10, when considering nodes located at both ends of a terminal link that are not connected to other links as the endpoint node, will not exclude the terminal link (the dead end link) from the search if the link length from the endpoint node to the intermediate point exceeds a predetermined threshold (Step S102: Rule a3). Therefore, the route search unit 111 can guide along a route that includes a dead end if the road length is long (Figure 6(A)).

There is a demand for guidance that includes a dead end, even if it faces either the starting point or the destination. In this regard, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 does not exclude a terminal link (a dead end link) from the search if the terminal link faces either the starting point or the destination (Step S102: Rule a4). Therefore, the route search unit 111 can guide users along a route that includes a dead end, even if it faces either the starting point or the destination (Figure 7(A)).

Residential areas, with their many private homes, often have narrow roads where vehicles need to make U-turns, and also experience heavy pedestrian and bicycle traffic, compared to typical main roads. In this regard, according to the navigation system 1 of the first embodiment, if the route search unit 111 of the server 10 includes a route requiring a U-turn at a certain link, it excludes the link constituting the U-turn route from the search, re-searches for the route, and outputs the re-searched route (steps S104, S106, Figure 8). As a result, the route search device (server 10) further suppresses guidance of routes including U-turn routes, thereby improving the ease of driving on the guided route and enhancing safety.

In recent years, the widespread adoption of online shopping has led to increased demand for logistics services, resulting in a rise in the number of people (delivery personnel) engaged in delivering goods and other packages 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 that the user of the route search device (server 10) will visit for package delivery (step S100), and searches for a route from the starting point to the destination, passing through one or more delivery destinations as intermediate stops (step S102). Therefore, a route search device specifically designed for delivery services can be provided.

Furthermore, residential areas with many private homes tend to have fewer parking spaces compared to areas near typical main roads. In this regard, according to the navigation system 1 of the first embodiment, the route search unit 111 of the server 10 acquires location information of parking spaces (parking spaces where vehicles can be safely parked) along the searched route (step S108), and outputs the location information of these parking spaces along with the searched route (Figure 9). Therefore, in residential areas with limited parking, this system can prevent users from parking their vehicles on unsafe roadsides, thereby improving both user convenience and safety.

B. Second Embodiment:
Figure 10 shows a schematic configuration of the navigation system 1A of the second embodiment. The navigation system 1A of the second embodiment includes a server 10A instead of server 10 in the configuration described in the first embodiment. In the second embodiment, the processing content of the route search process executed by server 10A differs from that of the first embodiment.

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

Thus, the configuration of the navigation system 1A can be modified in various ways, and re-searching when excluded routes are included may be omitted. This second embodiment of the navigation system 1A can achieve the same effects as the first embodiment described above. Furthermore, the second embodiment of the navigation system 1A can reduce the processing load on the server 10A and shorten the time from when a processing request is made from the client 30 to when the server 10 responds (step S108 in Figure 11: transmission of delivery route).

C. Third Embodiment:
Figure 12 shows a schematic configuration of the navigation system 1B of the third embodiment. The navigation system 1B of the third embodiment has a server 10B instead of server 10 in the configuration described in the first embodiment, and does not have a client 30. The server 10B of the third embodiment performs processing without cooperating with the client 30.

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

Thus, 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 its storage unit 140B. Furthermore, the server 10B may 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. This third embodiment of the navigation system 1B can achieve the same effects as the first embodiment described above.

D. Fourth Embodiment:
Figure 13 shows a schematic configuration of the navigation system 1C of the fourth embodiment. The navigation system 1C of the fourth embodiment has a client 30C instead of client 30 in the configuration described in the first embodiment, and does not have a server 10. The client 30C of the fourth embodiment performs processing without cooperating with the server 10. In this embodiment, the client 30C corresponds to the "route search device".

The storage unit 340C of client 30C pre-stores delivery plan information 341, delivery route information 342, as well as map information DB 343, route information DB 344, and guidance information DB 345. Map information DB 343 is the same as map information DB 141 described in Figure 1. Route information DB 344 is the same as route information DB 142 described in Figure 1. Guidance information DB 345 is the same as guidance information DB 143 described in Figure 1. The CPU 310C of client 30C has a guidance unit 311 and a route search unit 312. The route search unit 312 is a functional unit that performs the same processing as the route search unit 111 described in Figures 1 and 3.

Thus, the configuration of the navigation system 1C can be modified in various ways, and the client 30C may be configured as a route search device. The map information DB 343, route information DB 344, and guidance information DB 345 may be stored on an external data server, and the route search unit 312 may connect to the data server each time during the processing shown in Figure 3 to obtain the necessary data. Furthermore, to enable the route search process (especially step S102 in Figure 3) to be executed on the client 30C, which has inferior processing power compared to the server 10 (Figure 1), constraints may be placed on the search speed and search distance range during the route search process. This fourth embodiment of the navigation system 1C can achieve the same effects as the first embodiment described above.

E. Variations:
In the above embodiment, some of the configuration implemented by hardware may be replaced with software, and conversely, some of the configuration implemented by software may be replaced with hardware. Other modifications are also possible, as follows.

Variation 1:
The above embodiment shows an example of the configuration of a navigation system, server, and client. However, the configuration of each device can be arbitrarily chosen. For example, at least a portion of the databases of the server and client may be stored on other devices (including external servers connected via the Internet).

In the above embodiment, the navigation system was defined as a system that guides users along delivery routes, in other words, a system used in delivery operations. However, the navigation system can be constructed not only for delivery operations but also as a system for general users that provides regular route guidance.

Variation 2:
In the above embodiment, the pathfinding process (Figures 3 and 11) was described with an example of the processing procedure. However, these processing procedures can be modified in various ways, and the processing content in each step may be added, omitted, or changed, and the execution order of each step may also be changed.

For example, in step S102, rules a1 to a5 were provided as examples for excluding terminal links and specific links from the search, respectively. However, one or more of these rules a1 to a5 may be adopted in any combination. For example, rule a1 may be executed alone, or rule a1 and rule a3 may be executed in combination.

For example, in step S108, the delivery route information is assumed to include the route explored in step S102 or step S104 and information about parking spaces. However, the information about parking spaces may be omitted. Furthermore, the delivery route information may include other information.

Variation 3:
The present invention is not limited to the embodiments, examples, and modifications described above, and can be realized in various configurations without departing from its spirit. For example, the technical features in the embodiments, examples, and modifications corresponding to the technical features in each form described in the summary of the invention can be replaced or combined as appropriate in order 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 deleted as appropriate.

1, 1A-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... Memory Unit 141... Map Information Database
142... Route information DB
143... Information Database
144...Delivery plan information 145...Delivery route information 310, 310C...CPU
311... Guidance unit 312... Route search unit 320... Communication unit 330... ROM/RAM
340, 340C... Memory Unit 341... Delivery Plan Information 342... Delivery Route Information 343... Map Information DB
344... Route information database
345... Information Database
350...Input/output section 360...Current position acquisition section

Claims (10)

A pathfinding device,
A route information storage unit that stores road network data including node information and link information connecting nodes,
A route search unit that searches for a route from the starting point to the destination via one or more intermediate points ,
Equipped with,
The aforementioned path search unit,
From the aforementioned road network data, terminal links, which are links where only one of the nodes located at both ends of the link is connected to another link, are excluded from the search, and the aforementioned route is then searched.
This outputs the aforementioned searched path.
A route search device that, when a node located at both ends of the terminal link that is not connected to another link is designated as the terminal node, and the nearest intermediate point to the terminal node is designated as the reference intermediate point, if the link length from the terminal node to the reference intermediate point is greater than or equal to a predetermined threshold, the terminal link is not excluded from the search . A pathfinding device according to claim 1,
The route search unit searches for a route from the road network data, excluding specific links from the search, in addition to the terminal links, where one of the nodes located at both ends of the link is connected only to the terminal link. A pathfinding device according to claim 2 ,
The route search unit is a route search device that searches for the route without excluding the terminal link from the search if the terminal link is a link facing either the departure point or the destination. A pathfinding device according to claim 2 or claim 3,
The route search unit is a route search device that, even if a link is a specific link, searches for the route without excluding the specific link from the search if the link length from the entry node, which is a node different from the node connected to the terminal link among the nodes located at both ends of the specific link, to the reference transit point is greater than or equal to a predetermined threshold. A pathfinding device according to any one of claims 1 to 3,
The route search unit is a route search device that searches for the route without excluding a terminal link from the search if the link length of the terminal link is greater than or equal to a predetermined threshold, even if the terminal link is a terminal link. A pathfinding device according to claim 2 or claim 3,
The route search unit is a route search device that searches for the route without excluding a specific link from the search if the link length of the specific link is greater than or equal to a predetermined threshold, even if the link falls under the category of a specific link. A pathfinding device according to any one of claims 1 to 3,
The route search unit is a route search device that searches for the route without excluding a terminal link from the search if the endpoint node is not included within a predetermined area from a predetermined position, even if the link is a terminal link. A pathfinding device according to claim 2 or claim 3,
The route search unit is a route search device that, even if a link corresponds to the specified link, searches for the route without excluding the specified link from the search if the entry node, which is a node located at both ends of the specified link and is different from the node connected to the terminal link, is not included within a predetermined area from a predetermined position. A pathfinding method, wherein the information processing device is
Using road network data that includes node information and link information connecting nodes, the process of searching for a route from a starting point to a destination via one or more intermediate points is performed.
In the aforementioned search process,
From the aforementioned road network data, terminal links, which are links where only one of the nodes located at both ends of the link is connected to another link, are excluded from the search, and the aforementioned route is then searched.
Output the searched path ,
A route search method in which, among the nodes located at both ends of the terminal link, the node not connected to any other link is designated as the terminal node, and the nearest intermediate point to the terminal node is designated as the reference intermediate point, and if the link length from the terminal node to the reference intermediate point is greater than or equal to a predetermined threshold, the terminal link is not excluded from the search . A computer program, for use in an information processing device.
A computer program that performs the step of searching for a route from a starting point to a destination via one or more intermediate points , using road network data that includes node information and link information connecting nodes,
In the aforementioned search step,
From the aforementioned road network data, terminal links, which are links where only one of the nodes located at both ends of the link is connected to another link, are excluded from the search, and the aforementioned route is then searched.
Output the searched path ,
A computer program that, when a node located at both ends of the terminal link that is not connected to any other link is designated as the terminal node, and the nearest intermediate point to the terminal node is designated as the reference intermediate point, if the link length from the terminal node to the reference intermediate point is greater than or equal to a predetermined threshold, the terminal link is not excluded from the search .