JP7799369B2 - Information processing device, information processing method, and program - Google Patents

Description

The present invention relates to an information processing device, an information processing method, and a program.

In transportation systems, logistics systems, and other such systems, the problem of what route would be most efficient when traveling between multiple locations has long been considered. This type of problem is known as the traveling route search problem or the traveling salesman problem, and various methods for searching for the optimal route have been proposed as a solution to this problem.

For example, Patent Document 1 describes a vehicle dispatch scheduling method for determining an optimal vehicle dispatch plan for traveling between multiple locations. In this vehicle dispatch scheduling method, an optimal vehicle dispatch plan is selected based on an approximate solution that minimizes a predetermined evaluation function for the multiple locations and satisfies various constraints.

Japanese Patent Application Laid-Open No. 2003-26335

However, many solutions to the circular route search problem search for routes under the assumption that travel is always required between points. As a result, for example, if multiple points are located within the same building, the calculation may assume that travel is required between those points, resulting in the generation of a route that makes an unnecessary loop around the roads surrounding the block containing the building. Furthermore, if multiple points are densely packed around a single road, the generation of a circular route that repeatedly arrives at each of the many points on that road is problematic.

The present invention was made in consideration of these circumstances, and aims to provide an information processing device, information processing method, and program that can generate a route that reduces travel between points on related premises.

An information processing device according to one aspect of the present invention includes an acquisition unit that acquires site-related information related to a site; a setting unit that sets at least two points among a plurality of points that correspond to the site-related information as aggregation targets associated with the site-related information; an aggregation unit that aggregates the at least two points set as aggregation targets into a predetermined representative point; and a search unit that searches for a route that travels between the predetermined representative point and points among the plurality of points that have not been aggregated into the predetermined representative point.

According to the present invention, at least two locations among a plurality of locations that correspond to the same site-related information are set as aggregation targets and aggregated into a representative point. A route is then searched for that travels between the representative point of the aggregated locations and the locations among the plurality of locations that have not been aggregated into the representative point. This reduces travel between locations associated with the same site-related information, making it possible to generate an appropriate travel route.

1 is a diagram illustrating an example of a device configuration of a navigation system 1 according to an embodiment. 1 is a diagram illustrating an example of the hardware configuration of a route search device 10 and a terminal 20. [0020] FIG. FIG. 2 is a diagram illustrating an example of a functional block configuration of a route search device 10. 1 is a diagram for explaining map information 100a and site-related information 100b. FIG. FIG. 2 is a diagram illustrating an example of a functional block configuration of a terminal 20. 4 is an operation sequence showing an example of processing executed by the navigation system 1 according to the present embodiment. FIG. 10 is a diagram illustrating an example of a delivery application screen. FIG. 10 is an operational flow diagram illustrating an example of a route search process executed by the route search device 10. FIG. 10 is a diagram showing an example of a tour route screen.

Embodiments of the present invention will be described with reference to the accompanying drawings. Note that in each drawing, components with the same reference numerals have the same or similar configurations.

<System Configuration>
1 is a diagram showing an example of the device configuration of a navigation system 1 according to an embodiment. The navigation system 1 generates a route for traveling around a plurality of points, such as delivery destinations of a package, and displays the route on a map screen. The navigation system 1 also provides guidance for traveling along the route.

The navigation system 1 includes a route search device 10 and a terminal 20. The route search device 10 is managed by, for example, a designated administrator, performs route searches based on requests from the terminal 20, and transmits the route search results to the terminal 20. The route search device 10 may be configured as one or more physical servers, a virtual server running on a hypervisor, or a cloud server. The terminal 20 is operated by a user such as a package deliverer, and can be any device with communication capabilities, such as a smartphone, tablet, mobile phone, personal computer (PC), laptop, personal digital assistant (PDA), or home game console. The terminal 20 displays an input screen for entering information indicating points to be visited, a guidance screen displaying the route received from the route search device 10 and text indicating guided points on the route, etc.

Note that the navigation system 1 may be implemented as a standalone system on a single device. In other words, both the functions of the route search device 10 and the functions of the terminal 20 may be implemented on a single device. In this embodiment, the route search device 10 may be referred to as a navigation device or a computer, or a device having the functions of both the route search device 10 and the terminal 20 may be referred to as a navigation device or a computer.

<Hardware configuration>
FIG. 2 is a diagram illustrating an example of the hardware configuration of the route search device 10 and the terminal 20. The route search device 10 and the terminal 20 are configured with a communication controller 30-1, a CPU 30-2, a random access memory (RAM) 30-3 used as working memory, a read-only memory (ROM) 30-4 for storing boot programs and the like, a storage device 30-5 such as a flash memory or a hard disk drive (HDD), a drive device 30-6, and an input/output interface (I/F) 30-7, all interconnected by an internal bus or a dedicated communication line. The communication controller 30-1 communicates with other information processing devices. The storage device 30-5 stores a program 30-5a executed by the CPU 30-2. This program 30-5a is loaded into the RAM 30-3 by a direct memory access (DMA) controller (not shown) or the like and executed by the CPU 30-2. The input/output I/F 30-7 includes an input device that accepts input to the route search device 10 and the terminal 20, and an output device that executes predetermined output. The input device may be any input device, such as a keyboard, touch panel, touchpad, mouse, or microphone. The output device may be any output device, such as a display or speaker. Note that the route search device 10 does not necessarily have to include the input/output I/F 30-7.

<Function block configuration>
(Travel route search device 10)
FIG. 3 is a diagram showing an example of the functional block configuration of the circular route search device 10. The circular route search device 10 includes a storage unit 100, a receiving unit 101, an acquiring unit 102, aggregating unit 104, a searching unit 105, and a transmitting unit 106. The storage unit 100 can be realized using a storage unit 30-5 provided in the circular route search device 10. The receiving unit 101, the acquiring unit 102, the aggregating unit 104, the searching unit 105, and the transmitting unit 106 can be realized by the CPU 30-2 of the circular route search device 10 executing a program 30-5a stored in the storage unit 30-5. The program 30-5a can be stored in a storage medium. The storage medium storing the program 30-5a may be a non-transitory computer-readable medium. The non-transitory storage medium is not particularly limited, but may be, for example, a storage medium such as a USB memory or a CD-ROM.

The memory unit 100 stores map information 100a and site-related information 100b. The map information 100a and site-related information 100b will be explained with reference to Figure 4.

Map information 100a includes data on nodes and road links (hereinafter simply referred to as "links"). Here, a node is a term that refers to an intersection or a junction on a road. Nodes N1, N2, N3, N4, and N5 are shown as examples in Figure 4. Node-related data may include node coordinates, traffic regulations, and the like. A link is a term that refers to a road connecting two nodes. As an example, Figure 4 shows links L12, L13, L14, and L15 corresponding to roads R12, R13, R14, and R15, respectively. Link-related data may include information indicating the link's direction (e.g., information indicating the passable direction of the corresponding road), information identifying the nodes that serve as the link's endpoints, and information about the road corresponding to the link (e.g., type of road (national highway, prefectural road, etc.), number of lanes, other attribute information, traffic regulations, etc.). Links and nodes may also be assigned a "cost." The costs set for links and nodes may be set lower, for example, the higher the priority of links and nodes that should be searched for during route search. For example, a link corresponding to a wide national highway may be set to a lower cost than a link corresponding to a narrow alley. The costs set for links may also be updated as appropriate based on congestion information. For example, the cost of a link corresponding to a congested road may be set to a higher cost than the cost of a link corresponding to a non-congested road.

Site-related information 100b is information related to sites such as buildings and land, and may include, for example, names, polygon data, representative points, access points, and access links where the access points are located. The name may be the name of the site, such as a building or land, or a unique ID. In the example of Figure 4, site-related information for a site named "H1" and site-related information for a site named "H2" are shown. Polygon data is data used to define the area of the site and may be expressed, for example, as a set of coordinates (e.g., latitude and longitude) indicating the vertices of the divisions that define the site. In the example of Figure 4, the sets of coordinates indicating vertices P1a, P1b, P1c, P1d, P1e, P1f, P1g, and P1h are set as polygon data corresponding to site H1, and the sets of coordinates indicating vertices P2a, P2b, P2c, and P2d are set as polygon data corresponding to site H2.

The representative point is the coordinates of a point that represents the location of the site. In the example of Figure 4, point C1 is set as the representative point of site H1, and point C2 is set as the representative point of site H2. The representative point may be the center or center of gravity of the site (for example, the center or center of gravity of the coordinates of each vertex included in the polygon data), or may be set arbitrarily.

An access point is a point for accessing a site, and an access link is a link on which the access point is located. Access points are also referred to as, for example, D2D information (Door-to-Door information). Specifically, an access point is a point located on a specific access link near the site, indicating that it is possible to enter and exit the site from the road corresponding to the access link. Access points and access links may be set arbitrarily, taking into account the traffic environment around the site. In the example of FIG. 4, link L14 is set as the access link to site H1, and point G1, located at a specific position on link L14, is set as the access point for site H1. Similarly, link L14 is also set as the access link to site H2, and point G2, located at a specific position on link L14, is set as the access point for site H2. In other words, sites H1 and H2 are associated with a common access link (link L14).

Note that there may be cases where roads adjacent to a site are difficult to access or travel on. In such cases, the access link may be set to a link corresponding to a road that is not adjacent to the site, and the access point may be located on that access link. For example, in the example of Figure 4, the access link for sites H1 and H2 may be set not to link L14 of road R14 adjacent to sites H1 and H2, but to links L13 and L15 (in the case of the access link for site H2, link L12 may also be included) that connect to link L14 (via a node), and the access point may be located on that access link.

The receiving unit 101 receives various types of information from other information processing devices, such as the terminal 20. For example, the receiving unit 101 may receive a request for a route from the terminal 20. The request for a route includes information indicating each of multiple locations, such as the delivery destination of the package. This information may be, for example, the address of the location or the coordinates of the location. The address may be information obtained based on input by the operator to the terminal 20. The coordinates may be input by the delivery person or the like specifying an arbitrary location on a map displayed on the terminal 20, for example.

The acquisition unit 102 acquires site-related information related to a site that includes a point to be patrolled. For example, the acquisition unit 102 may acquire polygon data for defining the area of the site as the site-related information. In the example shown in FIG. 4, the acquisition unit 102 may acquire, as the site-related information, the coordinates of vertices P1a to P1h, which are polygon data for defining the area of site H1, and the coordinates of vertices P2a to P2d, which are polygon data for defining the area of site H2. Furthermore, for example, the acquisition unit 102 may acquire, as the site-related information, access links, which are links where access points for accessing the site are located. In the example shown in FIG. 4, the acquisition unit 102 may acquire, as the site-related information, access link L14 associated with sites H1 and H2.

The setting unit 103 sets at least two locations among the multiple locations that correspond to the site-related information as aggregation targets associated with the site-related information. Specifically, the setting unit 103 determines whether each of the multiple locations corresponds to any of the acquired site-related information, and associates each location with the site-related information. Each location associated with the site-related information is set as a target for aggregation (aggregation target) by the aggregation unit 104, which will be described later.

For example, if the site-related information includes polygon data, the setting unit 103 sets, for each polygon data, at least two points included in the area defined by the polygon data as aggregation targets. Specifically, the setting unit 103 determines whether the coordinates of each point are included in the area indicated by the polygon data, and if the coordinates of each point are included in the area indicated by the polygon data, determines that the point is included in the site indicated by the polygon data. The setting unit 103 then sets at least two points included in the polygon data as aggregation targets associated with the polygon data. In the example shown in FIG. 4, for example, the setting unit 103 sets points T1a, T1b, T1c, T1d, and T1e included in the area (site H1) defined by polygon data P1a to P1h of site H1 as aggregation targets associated with polygon data P1a to P1h of site H1. Similarly, the setting unit 103 sets, for example, points T2a, T2b, and T2c included in the area (site H2) defined by the polygon data P2a to P2d of site H2 as aggregation targets associated with the polygon data P2a to P2d of site H2. Note that if multiple polygon data associated with each of the multiple areas satisfy a predetermined condition, the multiple polygon data may be merged into a single polygon data. This allows multiple points included in each of the multiple areas to be set as aggregation targets. Here, the predetermined condition may be specified, for example, by the area or shape of the multiple areas associated with each of the multiple polygon data. For example, the predetermined condition may include the sum of the areas of the multiple areas being within a predetermined threshold.

Furthermore, for example, if the site-related information includes access links (links that include access points set for the site), the setting unit 103 sets at least two points associated with each access link as aggregation targets for each access link. Specifically, the setting unit 103 determines whether the coordinates of each point are included in the area indicated by the polygon data, and if the coordinates of each point are included in the area indicated by the polygon data, determines that the point is included in the site indicated by the polygon data. The setting unit 103 then sets each point as an aggregation target associated with the access link associated with the site indicated by the polygon data. In the example shown in FIG. 4, it is assumed that link L14 is associated as an access link with each of site H1 and site H2. In this case, the setting unit 103 sets, for example, points T1a, T1b, T1c, T1d, and T1e included in site H1, and points T2a, T2b, and T2c included in site H2, as aggregation targets associated with the access link (link L14).

When at least two locations are associated with the site-related information as aggregation targets, the aggregation unit 104 aggregates the at least two aggregation target locations into a predetermined representative point. The representative point may be determined, for example, based on the aggregation target locations. More specifically, the representative point may be determined, for example, as a weighted average of each aggregation target location. Note that the weighted average of each location is the sum of values obtained by multiplying each coordinate by a predetermined weight. In particular, when all weights are equal, the weighted average is also referred to as the center of gravity. In the example shown in FIG. 4, the aggregation unit 104 may determine, for example, the weighted average (e.g., center of gravity) of locations T1a, T1b, T1c, T1d, and T1e included in site H1 as the aggregation target location, as the representative point for these locations T1a, T1b, T1c, T1d, and T1e. Similarly, the aggregation unit 104 may determine, for example, the weighted average (e.g., the center of gravity) of points T2a, T2b, and T2c, which are included in site H2 and are to be aggregated, as the representative point of these points T2a, T2b, and T2c.

Furthermore, for example, when aggregation targets are set for each polygon data serving as site-related information, the aggregation unit 104 may determine a predetermined point for the site indicated by the polygon data as the representative point of the aggregation target points. In the example shown in FIG. 4, the aggregation unit 104 may, for example, determine a representative point C1 and access point G1, etc., previously set for site H1, as representative points for points T1a, T1b, T1c, T1d, and T1e, which are aggregation targets included in site H1. Similarly, a representative point C2 and access point G2, etc., previously set for site H2, may be determined as representative points for points T2a, T2b, and T2c, which are aggregation targets included in site H2.

Furthermore, for example, when aggregation targets are set for each access link as site-related information, the aggregation unit 104 may determine one of the access points located on the access link as the representative point of the aggregation target points. In the example shown in FIG. 4, it is assumed that points T1a, T1b, T1c, T1d, and T1e included in site H1 and points T2a, T2b, and T2c included in site H2 are set as aggregation targets associated with the access link (link L14). In this case, the aggregation unit 104 may determine, for example, access point G1 of site H1 or access point G2 of site H2 as the representative point.

The search unit 105 determines a tour route in response to a tour route request. When determining a tour route, for example, the search unit 105 calculates the cost of each candidate route based on the costs set for the links and nodes included in the map information 100a, and then compares the costs to determine at least one tour route. In particular, the search unit 105 may exclude from the tour target any of the multiple locations included in the tour route request that have been aggregated into a predetermined representative point by the aggregation unit 104, and instead include the predetermined representative point in the tour target. This reduces unnecessary travel to visit each location individually, for example, and enables the generation of an appropriate tour route, even when the tour target includes multiple locations close to each other. Alternatively, the search unit 105 may not exclude from the tour target any of the multiple locations included in the tour route request that have been aggregated into a predetermined representative point by the aggregation unit 104, and may include the predetermined representative point and the aggregated location in the tour target. In particular, the search unit 105 may include in the generated travel route a route from a representative point to a point aggregated at the representative point, or a route from a point aggregated at the representative point to the representative point.

The transmitting unit 106 transmits various types of information to other information processing devices such as the terminal 20. For example, the transmitting unit 106 may transmit map information extracted from the storage unit 100 to the terminal 20. The transmitting unit 106 may also transmit data on the travel route determined by the search unit 105 to the terminal 20.

(Terminal 20)
FIG. 5 is a diagram showing an example of the functional block configuration of the terminal 20. The terminal 20 includes a storage unit 200, a reception unit 201, a transmission unit 202, a reception unit 203, and a display control unit 204. The storage unit 200 can be realized using a storage unit 30-5 provided in the terminal 20. The reception unit 201, the transmission unit 202, the reception unit 203, and the display control unit 204 can be realized by the CPU 30-2 of the terminal 20 executing a program 30-5a stored in the storage unit 30-5. The program 30-5a can be stored in a storage medium. The storage medium storing the program may be a computer-readable non-transitory storage medium. The non-transitory storage medium is not particularly limited, and may be, for example, a storage medium such as a USB memory or a CD-ROM. The program 30-5a may be a delivery application, a route guidance application, or the like that can be installed in the terminal 20.

The memory unit 200 stores various types of information. For example, the memory unit 200 may store map information acquired from the route search device 10, etc., in a cache 200a for storing such map information.

The reception unit 201 accepts various operations by the user. For example, the reception unit 201 may accept input of various information related to the package to be registered in the delivery application (such as the package delivery destination, delivery status, time designation, whether or not drop-off delivery is available, whether or not a delivery box can be used, etc.). The reception unit 201 also accepts input of various points for route search.

The transmission unit 202 transmits various information to other information processing devices such as the route search device 10. For example, the transmission unit 202 transmits a request for a route to the route search device 10. The request for a route includes, for example, information indicating each location to be patrolled. The information indicating each location may be the address of each location or the coordinates of each location. The address of each location can be input, for example, by the operator specifying text. The coordinates of each location can be input, for example, by the operator specifying an arbitrary position on a map displayed on the terminal 20. In this case, the terminal 20 references a predetermined table (which may be stored in the storage unit 200 of the terminal 20 or may be accessible by accessing the route search device 10, etc.) that associates positions on the map with coordinates, and obtains the coordinates corresponding to the specified location.

The receiving unit 203 receives various types of information from other information processing devices, such as the circular route search device 10. For example, the receiving unit 203 acquires predetermined map information from the circular route search device 10. The receiving unit 203 also acquires, for example, data on the circular route searched by the circular route search device 10 from the circular route search device 10.

The display control unit 204 has the function of displaying various screens on the terminal 20. For example, the display control unit 204 displays a screen on the terminal 20 for inputting, viewing, etc. various information related to package delivery. The display control unit 204 also displays a map on the terminal 20 based on map information acquired from the route search device 10. The display control unit 204 also displays on the terminal 20 a route (routes) that travels around the delivery destinations of multiple packages, superimposed on the map, based on route data acquired from the route search device 10.

<Operation processing>
The processing executed by the navigation system 1 according to this embodiment will be described with reference to Fig. 6. Fig. 6 is an operation sequence showing an example of the processing executed by the navigation system 1 according to this embodiment. Fig. 6 is a diagram showing an example of a screen displayed on the terminal 20 in the processing executed by the navigation system 1 according to this embodiment.

In the terminal 20 according to this embodiment, for example, a delivery application and a route guidance application work together to provide support for a delivery person or the like in delivering multiple packages. The delivery application is, for example, an application implemented in the terminal 20, and manages various information related to the delivery of each package. The route guidance application is, for example, an application implemented in the terminal 20, and provides display and guidance of routes for visiting each of the delivery destinations of multiple packages.

(S10) First, the terminal 20 displays a delivery application screen, for example, as shown in FIG. 7. This figure shows the delivery application screen g1. As shown in this figure, the delivery application screen g1 includes various information related to the delivery of the package. The various information related to the delivery of the package includes, for example, the delivery destination of the package, delivery status, time designation, whether or not drop-off delivery is available, and whether or not a delivery box can be used.

(S11) Next, the terminal 20 accepts input of information indicating the package delivery destination on, for example, the delivery application screen g1. For example, the deliverer selects the package delivery destination field on the delivery application screen g1 and then text-enters the address to which the package will be delivered via the input device of the terminal 20. At this time, for example, the terminal 20 may obtain predicted address candidates based on the input address and display them in the package delivery destination field, etc. Furthermore, if the deliverer selects an address candidate regardless of whether or not they are in the middle of entering the address, the terminal 20 may accept the selected address candidate as the package delivery destination. In obtaining predicted address candidates, the terminal 20 may, for example, extract addresses, etc. that closely match the text entered so far in the package delivery destination field from a predetermined address database (which may be stored in the memory unit 200 of the terminal 20 or may be accessible by accessing the route search device 10, etc.), and then obtain these as predicted address candidates. Step S11 is performed for each of the multiple packages to be delivered. In step S11, the terminal 20 may, for example, display a predetermined map and accept input of the coordinates of the package delivery destination by accepting an operation to specify a location on the map. In this case, the terminal 20 references a predetermined table (which may be stored in the storage unit 200 of the terminal 20 or may be accessible by accessing the route search device 10, etc.) that associates locations on the map with coordinates, and obtains the coordinates corresponding to the specified location. In step S11, the terminal 20 may also receive information indicating the package delivery destination from, for example, an external information processing device, rather than accepting input of information indicating the package delivery destination from the deliverer.

(S12) Next, when the deliverer selects the object g1a (navigation button) containing the text "Navigation" on the delivery application screen g1, the terminal 20 accepts the selection of the object g1a.

(S13) When the terminal 20 accepts the selection of the navigation button (S12), it sends a request for a route to the route search device 10. The request for a route includes, for example, the location information acquired by the terminal 20 and information indicating each of the multiple delivery destinations entered in step S11 (address, coordinates, etc.). Note that the terminal 20 may acquire location information using a GPS function at least when accepting the selection of the navigation button, or may acquire location information periodically.

(S14) Next, when the circular route search device 10 receives a circular route request from the terminal 20, it executes a circular route search process based on the request.

Now, with reference to Figure 8, the circular route search process performed by the circular route search device 10 will be described. Figure 8 is an operational flow diagram showing an example of the circular route search process performed by the circular route search device 10.

(S20) First, the acquisition unit 102 acquires the coordinates of each delivery destination included in the request for the route. If the address of the delivery destination is included in the request for the route, the acquisition unit 102 acquires the coordinates associated with the address of each delivery destination, for example, by referencing a predetermined database that associates coordinates with addresses. Furthermore, if the request for the route includes coordinates of the delivery destination, the acquisition unit 102 acquires those coordinates. Furthermore, the acquisition unit 102 acquires map information of an area including the address of each delivery destination included in the request for the route by extracting it from map information 100a stored in the memory unit 100.

(S21) Next, the setting unit 103 acquires mesh data corresponding to the map information acquired in step S20 from the storage unit 100, etc. Here, a mesh is a rectangular section arranged in a mesh pattern to divide the map information. The dimensions of the mesh are not particularly limited, but may be, for example, 10 m, 25 m, 50 m, 100 m, 200 m, 500 m, etc., and may be set arbitrarily.

(S22) Next, the setting unit 103 determines which mesh each delivery destination is included in, and associates each delivery destination with the mesh that includes that delivery destination. As will be described later, the setting unit 103 may set each delivery destination as a candidate for aggregation, provided that it is associated with the same mesh. Note that steps S21 and S22 do not necessarily have to be performed.

(S23) Next, the acquisition unit 102 acquires at least one piece of site-related information from the storage unit 100. The acquisition unit 102 may acquire, for example, polygon data as the site-related information. Alternatively, the acquisition unit 102 may acquire, for example, an access link in which an access point for accessing the site is located as the site-related information.

(S24) Next, the setting unit 103 sets at least two delivery destinations corresponding to any of the site-related information as aggregation targets associated with the site-related information. Note that when the above-mentioned steps S21 and S22 are executed, the setting unit 103 sets the at least two delivery destinations as aggregation targets associated with the site-related information, on the condition that they are associated with the same mesh as a result of step S22.

Specifically, the setting unit 103 determines whether each delivery destination corresponds to any site-related information, and then associates each delivery destination with the site-related information that it determines to correspond. Then, if at least two delivery destinations correspond to the site-related information, the setting unit 103 sets those at least two delivery destinations as aggregation targets. For example, if the site-related information includes polygon data, the setting unit 103 sets, for each polygon data, at least two points included in the area defined by the polygon data as aggregation targets. Alternatively, for example, if the site-related information includes access links (links that include access points for accessing the site), the setting unit 103 sets, for each access link, at least two delivery destinations associated with the access links as aggregation targets.

(S25) Next, the aggregation unit 104 aggregates at least two delivery destinations set as aggregation targets in step S24 into a predetermined representative point. For example, the aggregation unit 104 may determine the representative point based on each delivery destination to be aggregated. The representative point may be, for example, a weighted average of the coordinates of each delivery destination to be aggregated. Furthermore, for example, if an aggregation target is set for each polygon data as site-related information, the aggregation unit 104 may determine a point that is predetermined for the site indicated by the polygon data as the representative point of the delivery destination to be aggregated. Furthermore, for example, if an aggregation target is set for each access link as site-related information, the aggregation unit 104 may determine one of the access points located on the access link as the representative point of the delivery destination to be aggregated.

(S26) Next, the search unit 105 searches for at least one circular route. Specifically, the search unit 105 searches for a route that travels between the representative point aggregated by the aggregation unit 104 and the multiple delivery destinations that have not been aggregated. In other words, in the process of searching for a circular route, of the multiple delivery destinations included in the circular route request, the delivery destinations aggregated by the aggregation unit 104 are excluded from the route, and instead the representative point at which these delivery destinations are aggregated is included in the route. Note that in determining the circular route, for example, the search unit 105 may calculate the cost of each candidate route based on the costs set for the links and nodes included in the map information 100a, and then determine at least one circular route by comparing the costs.

(S15) Refer again to FIG. 6. The circular route search device 10 transmits data indicating at least one determined circular route to the terminal 20. At this time, the circular route search device 10 may also transmit map information for overlaying the circular route to the terminal 20.

(S16) When the terminal 20 receives data indicating the circular route from the circular route search device 10, it launches a route guidance application and displays a circular route screen on the terminal 20. Figure 9 is a diagram showing an example of a circular route screen. The figure shows circular route screen g2. The circular route screen g2 shows delivery destinations T1a, T1b, T1c, T1d, and T1e included in site H1 and delivery destinations T2a, T2b, and T2c included in site H2. The delivery destinations T1a, T1b, T1c, T1d, and T1e included in site H1 are aggregated at representative point G1 corresponding to site H1. The delivery destinations T2a, T2b, and T2c included in site H2 are aggregated at representative point G2 corresponding to site H2. In the figure, a portion of the circular route R1 is indicated by a dotted line. As shown in the diagram, the route R1 passes through representative point G1 corresponding to site H1 and representative point G2 corresponding to site H2 in sequence. This aggregates multiple delivery destinations, reducing the need to repeatedly travel around blocks that include sites H1 and H2 to visit these destinations individually, and allows for the generation of an appropriate route.

[Modification]
In the above-described embodiment, the site-related information includes polygon data for defining the site area and access links, which are links where access points for accessing the site are located, and aggregation of multiple points is performed based on this site-related information. However, the site-related information is not limited to polygon data and access links, and may also be an address for identifying the site. Here, the address for identifying the site may be only the portion of a general address excluding the room number, etc., as long as it is information necessary and sufficient to identify the site, such as land or building.

The acquisition unit 102 may acquire an address for identifying the site as the site-related information. When the acquisition unit 102 acquires an address indicating a location (such as a delivery destination entered by a delivery person, etc.) from the terminal 20, it may acquire an address for identifying the site that is included in the address as the site-related information. Alternatively, when the acquisition unit 102 acquires coordinates of a location from the terminal 20, it may refer to a specified database to acquire an address associated with the coordinates, and then acquire an address for identifying the site that is included in the address as the site-related information. The database is not particularly limited as long as it associates addresses with coordinates, and may be a known geocoding database, etc.

The setting unit 103 determines which of the premises indicated by the addresses for identifying the premises each of the multiple locations is included in. For example, the setting unit 103 may determine which premises each location is included in by comparing the address of each location acquired from the terminal 20 with the address for identifying the premises acquired as premises-related information. Then, the setting unit 103 may set at least two locations included in the same premises as aggregation targets associated with the address.

The above-described embodiments are intended to facilitate understanding of the present invention and are not intended to limit the scope of the present invention. The present invention may be modified or improved without departing from its spirit, and equivalents are also included within the scope of the present invention. In other words, designs modified appropriately by a person skilled in the art from each embodiment are also encompassed within the scope of the present invention as long as they incorporate the characteristics of the present invention. For example, the functional units, steps, and other elements of each embodiment, as well as their arrangement and order, are not limited to those illustrated and can be modified as appropriate. Furthermore, each embodiment is merely an example, and it goes without saying that partial substitution or combination of the configurations shown in different embodiments is possible, and these are also encompassed within the scope of the present invention as long as they incorporate the characteristics of the present invention.

1...Navigation system, 10...Travel route search device, 20...Terminal, 30-1...Communication controller, 30-2...CPU, 30-3...RAM, 30-4...ROM, 30-5...Storage device, 30-5a...Program, 30-6...Drive device, 30-7...Input/output I/F, 100...Storage unit, 100a...Map information, 100b...Site-related information, 101...Receiving unit, 102...Acquisition unit, 103...Setting unit, 104...Aggregation unit, 105...Search unit, 106...Transmitting unit, 200...Storage unit, 200a...Cache, 201...Receiving unit, 202...Transmitting unit, 203...Receiving unit, 204...Display control unit

Claims (11)

an acquisition unit that acquires site-related information related to the site;
a setting unit that sets at least two locations corresponding to the site-related information among a plurality of locations as aggregation targets associated with the site-related information;
an aggregation unit that aggregates the at least two points set as aggregation targets into a predetermined representative point;
a search unit that calculates the cost of each of a plurality of routes that travel between the predetermined representative point and the plurality of points that are not aggregated at the predetermined representative point based on costs set for links and nodes that constitute the routes, and determines at least one of the plurality of routes as a search result based on the cost of each of the plurality of routes;
An information processing device comprising: the site-related information includes polygon data for defining the area of the site;
The information processing apparatus according to claim 1 , wherein the setting unit sets at least two of the plurality of points that are included in an area defined by the polygon data as the aggregation targets associated with the polygon data. The information processing device according to claim 2, wherein the aggregation unit determines the predetermined representative point based on a point predetermined for the site. the site-related information includes an access link, which is a link where an access point for accessing the site is located;
The information processing device according to claim 1 , wherein the setting unit sets at least two locations associated with the access link among the plurality of locations as the aggregation targets associated with the access link. The information processing device according to claim 4, wherein the aggregation unit determines the predetermined representative point to be one of the access points located on the access link. The site-related information includes an address for identifying the site,
The information processing device according to claim 1 , wherein the setting unit sets at least two of the plurality of points included in the premises indicated by the address as the aggregation targets associated with the address. The information processing device of claim 6, wherein the aggregation unit determines the predetermined representative point based on the at least two points. The information processing device according to claim 7, wherein the aggregation unit determines the predetermined representative point as a weighted average of the coordinates of the at least two points. The information processing device described in any one of claims 1 to 8, wherein the setting unit sets at least two points among the plurality of points that correspond to the site-related information as the aggregation targets, on the condition that the at least two points are included in the same mesh. The computer
obtaining site-related information related to the site;
setting at least two locations corresponding to the site-related information among the plurality of locations as aggregation targets associated with the site-related information;
aggregating the at least two points set as aggregation targets into a predetermined representative point;
a step of calculating the cost of each of a plurality of routes that travel between the predetermined representative point and the plurality of points that are not aggregated at the predetermined representative point based on costs set for links and nodes that constitute the routes, and determining at least one of the plurality of routes as a search result based on the cost of each of the plurality of routes;
An information processing method that performs the above.
Information processing methods. Computer,
an acquisition unit that acquires site-related information related to the site;
a setting unit that sets at least two locations corresponding to the site-related information among a plurality of locations as aggregation targets associated with the site-related information;
an aggregation unit that aggregates the at least two points set as aggregation targets into a predetermined representative point;
a search unit that calculates the cost of each of a plurality of routes that travel between the predetermined representative point and the plurality of points that are not aggregated at the predetermined representative point based on costs set for links and nodes that constitute the routes, and determines at least one of the plurality of routes as a search result based on the cost of each of the plurality of routes;
A program that functions as a