JP7613253B2 - Route search program, route search device, and route search method - Google Patents

Description

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

Technology is known for generating a movement plan for moving a convoy of vehicles from multiple starting points to multiple destinations. A convoy is an example of a vehicle group formed by one or more vehicles. The vehicles may be moving objects such as trucks and cars.

As a method for generating a travel plan, for example, the first method is known, which optimizes traffic volume and avoids congestion by solving a combinatorial optimization problem.

In the first method, for example, it is assumed that if all vehicle convoys are set to travel the shortest route from their respective starting points to their destinations, the vehicle convoys may concentrate on each shortest route, causing congestion and delaying the arrival time of the vehicle convoy at its destination by the amount of the reduction in travel speed caused by the congestion.

For example, the first method finds multiple routes for each combination of departure points and destinations of a motorcade, and from among the multiple combinations, finds a combination whose route does not overlap with motorcades having other combinations of departure points and destinations. The first method distributes traffic by dispersing the routes of vehicles heading from multiple departure points to multiple destinations, and finds the route that can arrive at the destination the fastest, thereby smoothing out delay times.

A second method for generating travel plans is known, which optimizes traffic flow by dispersing traffic volume to avoid congestion.

In the second method, for example, a computer extracts a graph based on map data that includes the names of points (place names) included in the map data and the distances between the points. Examples of points include intersections, highway interchanges, and other locations that affect route decisions, such as locations where routes branch off or merge.

The computer then determines multiple candidate routes for each motorcade based on the information on the departure point and destination of the motorcade and the extracted graph. The multiple candidate routes may include, for example, a route with the shortest travel distance, a route with the shortest travel time, a route that prioritizes either expressways or general roads, etc. From the determined candidate routes, the computer then determines an optimal route that combines routes from the departure point to the destination of each motorcade that avoids traveling on the same roads as much as possible.

US Patent Publication No. 2020/0082711 JP 2010-44528 A US Patent Publication No. 2010/0057346

The first method disperses traffic by limiting the number of vehicles (or convoys) passing through each route, so it is difficult to set detailed routes, such as by individually setting priorities for convoys that should be prioritized and then setting routes according to the priorities.

In addition, it is not anticipated that traffic volume will be distributed over time, such as by setting the same route for multiple convoys by staggering the times at which the convoys pass. For example, it is difficult to set a convoy with a lower priority after a convoy with a higher priority on the same route.

In the second method, when creating a schedule for avoiding congestion for individual convoys (or vehicles), the computer's processing can become cumbersome. For example, the computer calculates the route each convoy will take from the departure point to the destination and the time (e.g., the passing time) for each point, and creates a schedule that does not overlap with the routes of other convoys.

As such, with the first and second methods, it is difficult to set a route that provides the shortest travel time for all vehicle convoys, in other words, an appropriate route. Furthermore, setting an appropriate route for all vehicle convoys requires a large amount of calculations, which increases the processing load on the computer and increases the processing time for setting the route (route search).

In one aspect, the present invention aims to reduce the processing time required to search for optimal routes for each of multiple vehicle groups.

In one aspect, the route search program may cause a computer to execute the following processes. The process may include a process of executing a route search process for assigning any one of a plurality of routes that share at least one point to each of a plurality of vehicle groups. The process may also include a process of specifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups that are allowed to pass each of a plurality of points included in the plurality of routes for each first time interval. Furthermore, the process may include a process of specifying a second combination of each of the two or more vehicle groups and each of a plurality of second routes distinguished for each second time interval shorter than the first time interval in accordance with the priority when two or more vehicle groups pass the same point in the first combination in the first time interval in the route search process.

In one aspect, the present invention can reduce processing time when searching for optimal routes for each of multiple vehicle groups.

FIG. 2 is a block diagram illustrating an example of a functional configuration of a system according to an embodiment. FIG. 2 is a diagram for explaining an example of a vehicle convoy and intervals between the vehicle convoys. FIG. 1 is a diagram for explaining an example of traffic congestion. FIG. 2 is a block diagram illustrating an example of a functional configuration of a server according to an embodiment. FIG. 11 is a diagram for explaining an example of a graph extraction process. FIG. 11 is a diagram illustrating an example of start point and end point information. FIG. 4 is a diagram illustrating an example of route candidate information. FIG. 4 is a diagram illustrating an example of route information. 11 is a flowchart illustrating an example of an operation of a server according to an embodiment. 10 is a flowchart illustrating an example of the operation of the time information setting process shown in FIG. 9 . 10 is a flowchart illustrating an example of the operation of the combination optimization process shown in FIG. 9 . 10 is a flowchart illustrating an example of the operation of the route overlap determination process shown in FIG. 9 . 10 is a flowchart illustrating an example of the operation of the duplicated recovery process illustrated in FIG. 9 . FIG. 11 is a diagram illustrating an example of a time information setting process according to the first application example. FIG. 13 is a diagram illustrating an example of an optimal solution determination in the first application example. FIG. 13 is a diagram illustrating an example of a combination optimization process in the first application example. 13A and 13B are diagrams illustrating graphs and route examples of a second application example. FIG. 13 is a diagram showing an example of a route for each vehicle convoy in a second application example. FIG. 13 is a diagram showing an example of passing times for each vehicle train in the second application example. FIG. 13 is a diagram showing example route candidates in a second application example. FIG. 13 is a diagram showing example route candidates in a second application example. FIG. 13 is a diagram illustrating an example of a combinatorial optimization process in the second application example. FIG. 13 is a diagram showing an example of route candidates (details) in the second application example. FIG. 13 is a diagram illustrating an example of a route overlap determination process according to the second application example. FIG. 13 is a diagram illustrating an example of a partial route determination process in the second application example. FIG. 13 is a diagram illustrating an example of a duplicated recovery process according to the second application example. FIG. 13 is a diagram showing an example of combinatorial optimization reprocessing of the second application example. FIG. 13 is a diagram showing an example of confirmed route information in the second application example; FIG. 13 is a diagram illustrating an example of a plurality of paths in a third application example. FIG. 13 is a diagram showing an example of multiple departure points and multiple destinations in the third application example. FIG. 2 is a block diagram showing an example of a hardware (HW) configuration of a computer that realizes the functions of a server.

The following describes an embodiment of the present invention with reference to the drawings. However, the embodiment described below is merely an example, and is not intended to exclude the application of various modifications or techniques not specifically described below. For example, this embodiment can be modified in various ways without departing from the spirit of the invention. In the drawings used in the following description, parts with the same reference numerals represent the same or similar parts unless otherwise specified.

[1] One embodiment [1-1] Description of a system according to one embodiment (Example of system configuration)
Fig. 1 is a block diagram showing an example of a functional configuration of a system 1 according to an embodiment. As shown in Fig. 1, the system 1 may exemplarily include a server 2, a map data provider 3, and a route information provider 4. In the following description, for convenience, the system 1 according to an embodiment is assumed to be in a case where a vehicle (vehicle train) that is the subject of a route search can preferentially use a route and there are a small number of vehicles that are not the subject of the route search, but is not limited to this.

The server 2 is a device or system that generates a travel plan for moving multiple vehicle convoys from multiple departure points to multiple destinations. For example, the server 2 is an example of a route search device that executes a route search process that assigns each of multiple vehicle convoys to one of multiple routes that share at least one point. The server 2 may generate, for example, route information for each vehicle convoy as the travel plan. The route information may include, for example, the routes that the vehicle convoy will pass through and the time of each route (for example, the passing time; as an example, one or both of the arrival time and the departure time).

The map data provider 3 is a device or system that provides a service for providing map data to the server 2, and may be, for example, any of various known map information providing services. The map data provider 3 may transmit map data to the server 2 via, for example, an API (Application Programming Interface). The API accepts a map data acquisition request from the server 2, and transmits (responses to) map data covering the departure point and destination, or the area, to the server 2 based on information indicating the departure point and destination, or information indicating the area, included in the acquisition request.

The route information destination 4 is a device or system to which the route information (movement plan) generated by the server 2 is provided. Examples of the route information destination 4 include at least one of a management device that manages the movement of a convoy (a plurality of vehicles), at least one of the plurality of vehicles, and a terminal device owned by the driver of at least one of the plurality of vehicles.

The management device may be, for example, a computer such as a PC (Personal Computer) used by an operator who manages the movement of multiple vehicles. When the route information destination 4 is a vehicle, the route information may be provided (transmitted) from the server 2 to a communication device such as a navigation system installed in the vehicle. The terminal device owned by the driver may be, for example, various computers such as a PC, a smartphone, a mobile phone, etc.

The server 2 and the map data provider 3, and the server 2 and the route information provider 4 may be connected to each other via various networks so that they can communicate with each other. The network may be, for example, one or both of the Internet and a mobile network such as a cellular network. The network may also include an intranet such as a LAN (Local Area Network).

(About the motorcade)
Next, a vehicle convoy that is a premise for processing in the system 1 according to an embodiment will be described. For example, in one embodiment, a route for moving all of the vehicle convoys from multiple starting points to multiple destinations is calculated for each vehicle convoy. The system 1 according to an embodiment may be applied to the creation of various movement plans in various organizations, such as a company or a government agency.

Figure 2 is a diagram for explaining an example of a convoy and the distance between vehicles in the convoy. As illustrated in Figure 2, the convoy is an example of a vehicle group, and may be formed by multiple (a predetermined number) vehicles, for example, about 10 vehicles. It can be said that the multiple vehicles forming the convoy belong to a group that has a common starting point and destination. The convoy travels (moves) in a line with multiple vehicles keeping a certain distance between them. In one embodiment, the number of vehicles that are the subject of a route search may range from a few vehicles to tens of thousands of vehicles, or even more.

The inter-vehicle distance may be determined for each organization, for example. In one embodiment, the inter-vehicle distance is 200 m. The length of the convoy is the number of vehicles in the convoy multiplied by the inter-vehicle distance, which is Xm (X is a real number or integer between 1 and tens of thousands). In the example of FIG. 2, the length may be, for example, 10 vehicles x 200 m = 2000 m (2 km).

In addition, when more than 10 vehicles, for example 20 vehicles, belong to a group that shares a common starting point and destination, the group may be divided into multiple groups (vehicle convoys), for example two, so that each group contains a predetermined number of vehicles.

As shown in FIG. 2, sufficient spacing may be ensured between convoys to avoid congestion caused by convoys of, for example, 2 km each. The spacing between convoys may be determined, for example, by each organization. As an example, the spacing between convoys may be expressed by the time difference when the vehicle at the head of each convoy passes a certain point. In the example of FIG. 2, the spacing between convoys may be Y minutes (Y is a real number ranging from 0 to several hundred), for example, about 10 minutes.

As shown in FIG. 3, when vehicle convoys starting from multiple starting points A and B each travel to a common destination C, congestion may occur when the vehicle convoys join together. The possibility of congestion and the degree of congestion increase, for example, as each vehicle convoy approaches its destination.

For example, as described above, with the first and second methods, it is difficult to set a route that provides the shortest travel time for all vehicle convoys, in other words, an appropriate route. Furthermore, when setting an appropriate route for all vehicle convoys, the amount of calculation required is large, which increases the processing load on the computer and increases the processing time for setting the route (route search).

Therefore, system 1 according to one embodiment creates a schedule that takes into account the travel time for each vehicle convoy. For example, based on the conditions of the vehicle convoys and the intervals between the vehicle convoys, system 1 determines a schedule for each vehicle convoy that allows all vehicles to complete their travel in the shortest time by setting up a detour when the shortest route for each vehicle convoy has a high traffic volume, or by delaying the travel time and traveling along the shortest route, etc.

As an example, system 1 may obtain route information for each vehicle convoy from the route candidates by creating route candidates for each vehicle convoy with time information added to each vertex of the route, measuring the congestion level at each vertex, and performing optimization taking into account the passing time of each vehicle convoy. Each vertex may be, for example, a passing point or branching point of the vehicle convoy on the route. As a result, system 1 according to one embodiment can reduce the processing time when searching for optimal routes for each of multiple vehicle convoys.

[1-2] Example of Functional Configuration of Server Fig. 4 is a block diagram showing an example of the functional configuration of the server 2 according to an embodiment. As shown in Fig. 4, the server 2 may exemplarily include a memory unit 21, a map data acquisition unit 22, a graph extraction unit 23, a start point and end point setting unit 24, a route candidate calculation unit 25, a condition setting unit 26, a combination optimization unit 27, and an output unit 28. The map data acquisition unit 22, the graph extraction unit 23, the start point and end point setting unit 24, the route candidate calculation unit 25, the condition setting unit 26, the combination optimization unit 27, and the output unit 28 are examples of the control unit 20.

The memory unit 21 is an example of a storage area, and stores various data used by the server 2. As shown in FIG. 4, the memory unit 21 may be capable of storing, for example, map data 21a, graph information 21b, start point/end point information 21c, route candidate information 21d, condition information 21e, and route information 21f. Hereinafter, for convenience, each of the information 21a to 21f is represented in table format, but this is not limited to this, and at least one of the information 21a to 21f may be stored in the memory unit 21 in various formats such as DB (database) format or array format.

The map data acquisition unit 22 acquires map data from the map data provider 3, and stores the acquired map data as map data 21a in the memory unit 21. For example, the map data acquisition unit 22 may transmit an acquisition request including information indicating the departure point and destination, or information indicating the region (area), to the API of the map data provider 3, and receive (acquire) map data from the API.

The graph extraction unit 23 performs a graph extraction process to extract graph information from the map data 21a acquired by the map data acquisition unit 22, and stores the extracted graph information in the memory unit 21 as graph information 21b.

Figure 5 is a diagram for explaining an example of the graph extraction process. As shown in Figure 5, in the graph extraction process, the graph extraction unit 23 acquires the distance between points (vertices) and connection information from the map data 21a. A "point" is, for example, a location that affects route determination, such as an intersection or an interchange on a highway, and an example of a location related to a branching or merging of routes.

For example, the graph extraction unit 23 extracts a graph from the map data 21a. The graph may include, for example, location names and distance information between locations. In the example of FIG. 5, the graph extraction unit 23 may assign the numbers "1" to "11" as names to the vertices to be extracted, such as intersections, included in the map data 21a, and create a graph in which the intersections in the map data 21a are vertices and the roads are edges. Note that distance information in units of meters or kilometers, for example, may be set for the "edges." The graph extraction unit 23 may then convert the vertices and edges of the graph into graph information 21b. In other words, the graph extraction unit 23 performs a graph information generation process to generate graph information 21b based on the map data 21a, as exemplified in FIG. 5.

As shown in FIG. 5, graph information 21b may illustratively include items such as "Vertex A" and "Vertex B" as multiple vertices, as well as an "Edge" item. "Vertex A" and "Vertex B" are examples of point connection information. For example, "Vertex A" and "Vertex B" may each be set to a pair of vertices that form an edge (line segment) included in the graph, for example, identification information of two intersections (e.g., names "1" to "11"). "Edge" is an example of a distance between points. For example, the distance between the two intersections of "Vertex A" and "Vertex B" may be set to "Edge".

The start point and end point setting unit 24 may set the departure point (start point) and destination point (end point) of the vehicle convoy for each vehicle convoy in the start point and end point information 21c and store it in the memory unit 21.

Figure 6 is a diagram showing an example of start point/end point information 21c. As shown in Figure 6, start point/end point information 21c may, for example, include the items "convoy No.", "start point," and "destination." "Convoy No." is an example of identification information for the convoy. "Start point" and "destination" are information indicating the start point and destination of the convoy, respectively, and may be, for example, position information such as the latitude and longitude of the point (vertex), or identification information such as a name.

For example, the start point/end point setting unit 24 may generate the start point/end point information 21c based on information input by an operator of the server 2 via an input device or received via a network. Alternatively, the start point/end point setting unit 24 may acquire the start point/end point information 21c itself from an input device or a network. The map data acquisition unit 22 may acquire map data 21a corresponding to the departure point and destination from the map data provider 3 based on the start point/end point information 21c, for example.

The route candidate calculation unit 25 generates route candidates for each vehicle train, with the passing time assigned to each vertex of the route, and stores them in the memory unit 21 as route candidate information 21d.

For example, the route candidate calculation unit 25 may use various route search methods, such as the Dijkstra algorithm, based on the graph information 21b and the start point and end point information 21c to find multiple route candidates from the departure point to the destination for each vehicle convoy.

The route candidate calculation unit 25 may also calculate the time at which the motorcade (e.g., the lead vehicle in the motorcade) passes each point based on the distance between the points included in the route candidate and the travel speed of the motorcade (vehicles) between the points, and associate the calculated time information with the route candidate. The travel speed is, for example, the travel speed of the motorcade (vehicles) according to the road type between the points, and may be obtained by various known methods.

Furthermore, the route candidate calculation unit 25 may generate route candidates in which the times (departure times) of the departure points in the route candidates are shifted from each other, thereby obtaining multiple route candidates for one vehicle convoy that have a common route from the departure point to the destination but differ in time. The amount by which the route candidates are shifted (the shift time) may be the same as the interval (time interval) between vehicle convoys, for example. Note that the amount by which the route candidates are shifted may change depending on changes to the constraint conditions made by the condition setting unit 26, which will be described later.

For example, when a departure time and/or an arrival time are set for at least one of the departure point, intermediate point, and destination of each vehicle convoy, the route candidate calculation unit 25 may set time information for the route according to the set time. For example, the departure time and/or the arrival time may be specified in the start point/end point information 21c, or the route candidate calculation unit 25 may obtain them from an input device, a network, etc.

FIG. 7 is a diagram showing an example of route candidate information 21d. As shown in FIG. 7, route candidate information 21d includes a plurality of point information items that correspond, for each of a plurality of routes (route candidates), information indicating points included in each route and the time at which the motorcade departs from, passes through, or arrives at the point. As shown in FIG. 7, route candidate information 21d may, for example, include the items "motorcycle No.", "route candidate No.", "point", "time", "departure FLG", and "destination FLG".

"Vehicle convoy No." is an example of identification information for a vehicle convoy, and "route candidate No." is an example of identification information for a route candidate. "Point" is information indicating a vertex through which the vehicle convoy passes on the route candidate, and may be, for example, identification information for the point. "Time" is the time at which the vehicle convoy passes the "point." "Departure FLG" and "Destination FLG" may be flag (FLAG) information that is set to valid (e.g., "1") when the "point" is the departure point and the destination, respectively, and is set to invalid (e.g., "0") when the "point" is neither the departure point nor the destination.

As illustrated in FIG. 7, the route candidate calculation unit 25 may generate two route candidates, route candidates No. 1 and 2, for the vehicle convoy No. 1. Route candidate No. 1 is a route candidate in which the times "8:00", "10:00", "15:00", and "17:00" are associated with the route from point a (start point), point 1, point 2, and point b (destination). Route candidate No. 2 is a route candidate in which the times "9:00", "11:00", "16:00", and "18:00", which are shifted from the time of route candidate No. 1 (for example, delayed by one hour), are associated with the route common to route candidate No. 1.

In addition, since the starting point and destination points can be determined for each vehicle convoy based on the start point and end point information 21c, the "start point FLG" and "destination FLG" may be omitted from the route candidate information 21d. Alternatively, information indicating the order in which each point is passed may be set in the route candidate information 21d instead of the "start point FLG" and "destination FLG".

In addition, for a motorcade in which one or both of a departure time and a destination time are specified, the route candidate calculation unit 25 may limit the route candidates generated for the motorcade to route candidates that match one or both of the specified departure time and destination time.

The condition setting unit 26 may set condition information 21e for optimizing the combination of routes between vehicle convoys based on the route candidate information 21d, and store the condition information in the memory unit 21. The condition information 21e may include, for example, an objective and constraint conditions. The "objective" may be, for example, an objective function to be achieved in combinatorial optimization, and examples thereof include "minimizing the total travel time" and "maximizing the total number of incoming vehicles." The "constraint conditions" are conditions that act as constraints in combinatorial optimization, and examples thereof include "only one route can be assigned to one vehicle," "the number of vehicles that can pass one vertex (at the same time)," and "the order of arrival of the vehicle convoy at the destination."

For example, the condition setting unit 26 may generate the condition information 21e based on information input by an operator of the server 2 via an input device or received via a network. Alternatively, the condition setting unit 26 may acquire the condition information 21e itself from an input device, a network, or the like. The condition information 21e may be different for each organization requesting a route search, and may also be different for each route search purpose within the organization.

Based on the route candidate information 21d and the condition information 21e, the combination optimization unit 27 stores in the memory unit 21 as route information 21f an optimal route combination in which all vehicle trains subject to the route search satisfy the constraint conditions included in the condition information 21e and can achieve the objective.

FIG. 8 is a diagram showing an example of route information 21f. As shown in FIG. 8, route information 21f may include, by way of example, the items "Convoy No.", "Location," and "Time." "Convoy No.", "Location," and "Time" are similar to the items "Convoy No.", "Location," and "Time" included in route candidate information 21d, respectively. Route information 21f is an example of a schedule that associates, for each convoy, the locations through which the convoy passes and the times at which the convoy passes each location.

As an example, the combination optimization unit 27 may find a combination of routes that ensures that all convoys heading from the departure point to the destination are not in the same place (point) at the same time and that the travel time of all convoys is the shortest. For example, the combination optimization unit 27 can create a schedule that satisfies the condition information 21e, based on the route that each convoy takes from the departure point to the destination and the time at each point on the route, so that each convoy (vehicle) does not overlap with other convoys on the route. In other words, the combination optimization unit 27 can create a schedule that enables each convoy (vehicle) to avoid congestion.

When the condition information 21e includes multiple objectives, the combination optimization unit 27 may optimize the route combination by setting priorities between the objectives using a method such as multi-objective optimization calculation.

The output unit 28 outputs the route information 21f. For example, the output unit 28 may transmit the route information 21f to the route information destination 4.

[1-3] Description of the Combination Optimization Unit Next, a description will be given of the details of the combination optimization unit 27. As described above, the route candidate information 21d generated by the route candidate calculation unit 25 according to one embodiment includes, for each vehicle convoy, a plurality of route candidates that are time-shifted from one another as route candidates along which the vehicle convoy travels on the same road.

For this reason, when the combination optimization unit 27 finds a combination optimum solution, the scale of combination calculations increases exponentially as the number of route candidates increases. For example, consider a case where there are two convoys (or vehicles) and the number of route candidates is increased. If there are two route candidates for each convoy, the number of combinations of route candidates is 2^2 = 4. If there are three route candidates, the number of combinations is 3^2 = 9, and if there are four route candidates, the number of combinations is 4^2 = 16.

In addition, the route information 21f shown in FIG. 8 shows an example in which one vehicle convoy passes each point per hour. However, if, for example, six vehicle convoys (or vehicles) pass each point per hour, the number of combinations of route candidates described above will be the number of combinations of route candidates every 10 minutes. In this case, even if the number of route candidates is two, the number of combinations per hour will be 6^2=36.

In view of this, the combination optimization unit 27 according to one embodiment reduces the number of combinations (number of route candidates) when the number of combinations increases exponentially by increasing the number of route candidates. Below, an example of a method for reducing the number of combinations (number of route candidates) by the combination optimization unit 27 is described.

For example, in one embodiment, the combination optimization unit 27 performs the combination optimization process using the condition information 21e with the modified constraint condition. As an example, the condition setting unit 26 generates or acquires condition information 21e in which the constraint condition "one or less vehicle convoys can pass through one vertex at the same time (10 minutes)" is changed to "a predetermined number or less vehicle convoys can pass through one vertex at the same time (1 hour)," and stores the condition information in the memory unit 21. This makes it possible to specify the number of vehicle convoys that pass through the same vertex at the same time.

The predetermined number is an example of the allowable number of convoys that are permitted to pass through each of the multiple points included in the multiple route candidates for each time interval of a reference time, such as one hour, and may be calculated, for example, based on the interval between convoys and a reference time, such as one hour. As an example, the predetermined number may be calculated by "reference time (e.g., one hour)" / "interval between convoys (e.g., 10 minutes)." The predetermined number may be referred to as the "allowable number of vertices convoys."

For example, if there are two convoys and the interval between the convoys is 10 minutes, six route candidates will be generated per hour for each vehicle. In this case, when route candidates are generated based on condition information 21e that states as a constraint that "a vertex can be passed by up to a 'predetermined number' of convoys at the same time (in one hour)," the number of route candidates can be reduced to one per hour by setting the predetermined number to six. In this case, the condition setting unit 26 may change (increase) the predetermined time (time interval) that is treated as the same time from 10 minutes to a reference time such as one hour.

The reference time (e.g., 1 hour) is an example of a first time interval. An interval between vehicles that is less than the reference time (e.g., 10 minutes) is an example of a second time interval that is shorter than the first time interval.

The above-mentioned constraint conditions may be generated (changed) by the condition setting unit 26, or may be specified as changed conditions by an operator of the server 2, etc. The route candidate calculation unit 25 may generate route candidates based on the constraint conditions in which the predetermined time as the interval (time interval) between vehicle trains has been changed to the reference time by the condition setting unit 26, etc., as described above.

When a combination of route candidates is calculated under the constraint that "a specified number or less of vehicle convoys" pass each vertex, the specified maximum number of vehicle convoys will exist at the same time at each vertex. Therefore, the combination optimization unit 27 sets detailed times (detailed duration) for the route candidates after the combination optimization process. For example, if the interval between vehicle convoys is 10 minutes and the route candidate calculation unit 25 finds one route candidate per hour, six vehicle convoys will pass the same vertex at the same time. In this case, the combination optimization unit 27 reassigns times to each of the six vehicle convoys at 10-minute intervals after the combination optimization process.

The combination optimization unit 27 determines whether the route of the vehicle convoy to which detailed times have been assigned overlaps with that of other vehicle convoys. If the combination optimization unit 27 detects an overlap, it recalculates the route of the overlapping vehicle convoy and updates the route information 21f.

As another example, if a route allows one convoy (vehicle) per minute, the condition setting unit 26 sets the number of convoys (vehicles) that can pass through the route in one hour to 60 or less. In this case, the combination optimization unit 27 adjusts the combination (route information 21f) optimized by 60 convoys/hour based on priority and arrival time. For example, when 60 convoys are assigned within one hour, the combination optimization unit 27 creates multiple route candidates by assigning times from 0 to 59 minutes to all route candidates for the corresponding 60 convoys according to priority, and optimizes the combination of the created route candidates.

As described above, the server 2 according to one embodiment identifies a first combination based on the priority set for each of the multiple vehicle convoys, the time at which the vehicle convoy passes each of the multiple points included in the multiple routes, and the allowable number of vehicle convoys at vertices. The first combination is a combination of each of the multiple vehicle convoys with each of the multiple first route candidates (see FIG. 7) that are distinguished by reference time, and may be, for example, route information 21f identified based on condition information 21e that multiple vehicle convoys can pass a single vertex at the same time.

In addition, in one embodiment, the server 2 identifies a second combination according to priority when, in the first combination, two or more vehicle convoys pass the same point during the first time interval (in other words, when the predetermined number is two or more). The second combination is a combination of each of the two or more vehicle convoys and each of a plurality of second routes distinguished for each second time interval, and may be, for example, route information 21f identified (updated) based on route candidates for which a detailed time (detailed period) is set by the combination optimization unit 27.

[1-4] Operational Example Hereinafter, an operational example of the above-mentioned system 1 (server 2) will be described with reference to a flowchart. Fig. 9 is a flowchart for explaining an operational example of the server 2 according to one embodiment. Figs. 10 to 13 are flowcharts for explaining operational examples of the time information setting process, combination optimization process, route overlap determination process, and overlap recovery process shown in Fig. 9, respectively.

(Example of operation of server 2)
As illustrated in FIG. 9, the graph extraction unit 23 of the server 2 acquires graph information 21b based on the map data 21a acquired by the map data acquisition unit 22 from the map data provider 3 (step S1), and stores the graph information 21b in the memory unit 21.

Based on the graph information 21b and the start and end point information 21c acquired by the start and end point setting unit 24, the route candidate calculation unit 25 calculates route candidate information 21d including multiple route candidates for each vehicle train (step S2) and stores it in the memory unit 21.

The route candidate calculation unit 25 determines whether route candidates for the entire vehicle train have been calculated based on the start point/end point information 21c, etc. (step S3), and if route candidates for the entire vehicle train have not been calculated (NO in step S3), the process proceeds to step S2.

When route candidates for the entire vehicle train have been calculated (YES in step S3), the route candidate calculation unit 25 performs a time information setting process (step S4). For example, the route candidate calculation unit 25 may calculate the time at which the vehicle train passes each vertex for each route candidate based on the distance between the vertices and the travel speed obtained from the graph information 21b, and store the calculated time in the route candidate information 21d in association with the route candidate.

The combination optimization unit 27 performs a combination optimization process based on the route candidate information 21d and the condition information 21e acquired by the condition setting unit 26 (step S5). The combination of route candidates optimized by the combination optimization process is stored in the memory unit 21 as route information 21f. In the combination optimization process of step S5, a process of identifying a first combination is performed.

The combination optimization unit 27 determines whether there are multiple vehicle convoys passing the same vertex at the same time in the route information 21f (step S6). Note that "the same time" in step S6 may mean a predetermined time (time segment) such as one hour. The predetermined time may be the same as or different from the interval (time interval) between vehicle convoys. If there are no multiple vehicle convoys passing the same vertex at the same time (NO in step S6), the process proceeds to step S10.

If there are multiple vehicle convoys passing the same vertex at the same time (YES in step S6), the combination optimization unit 27 reassigns times to the route candidates of the vehicle convoys passing the same vertex at the same time (step S7). For example, the combination optimization unit 27 may associate detailed time information (detailed information) with each of the route candidates of multiple vehicle convoys passing the same vertex at the same time, with the time shifted by "predetermined time/number of overlapping vehicle convoys". For example, if there are six vehicle convoys passing the same vertex at the same time (e.g. per hour), the combination optimization unit 27 may associate time information with the passing time of each of the six vehicle convoys at the corresponding point, shifted by 10 minutes. The route candidates of the vehicle convoys to which detailed time information is associated may be selected in an order according to the priority, such as the arrival order of the vehicle convoys set as a constraint condition.

The combination optimization unit 27 performs route overlap determination processing (step S8) and overlap recovery processing (step S9).

The output unit 28 outputs the route information 21f to the route information destination 4 (step S10), and the process ends.

(Time information setting process)
Next, an example of the operation of the time information setting process in step S4 in Fig. 9 will be described with reference to Fig. 10. As illustrated in Fig. 10, the time information setting process may include a process of setting time information for route candidates (steps S12 and S13), and a process of generating, for each set route candidate, one or more route candidates in which the time information is changed but the route is common (steps S14 and S15).

For example, the route candidate calculation unit 25 obtains route candidates for which time information has not been set (not assigned) from the route candidate information 21d (step S11).

The route candidate calculation unit 25 calculates the travel time of the vehicle convoy between vertices included in the acquired route candidate based on the distance between vertices and the travel speed obtained from the graph information 21b (step S12). The route candidate calculation unit 25 then adds the travel time between each vertex to the departure time or subtracts it from the arrival time to calculate the time at which the vehicle convoy passes each vertex of the route candidate, and sets the calculated time information in the route candidate information 21d in association with the route candidate (step S13).

The route candidate calculation unit 25 also adds a time corresponding to the interval between the vehicle convoys to the time information (step S14). The time corresponding to the interval between the vehicle convoys may be, for example, a time such as Y minutes as shown in FIG. 2. This time may be, for example, the travel time between the first vehicles in the convoy. Note that the time corresponding to the interval between the vehicle convoys may be a predetermined time (time segment) such as one hour, for example, if the constraint condition is changed to "a vertex can be passed by up to a 'predetermined number' of vehicle convoys at the same time."

Then, the route candidate calculation unit 25 generates one or more route candidates with the added time information set (step S15), and the process ends. As a result, for one route candidate for one vehicle convoy, multiple route candidates are generated that share a common road (route) that the vehicle convoy travels, but have different passing times (shifted by a time corresponding to the distance between the vehicle convoys).

(Combinatorial optimization processing)
Next, an example of the operation of the combination optimization process in step S5 in Fig. 9 will be described with reference to Fig. 11. As illustrated in Fig. 11, the combination optimization unit 27 calculates a combination of route candidates based on the route candidates in the route candidate information 21d and the number of vehicle convoys (step S21). The combination is a combination in which one route candidate is selected for each vehicle convoy.

The combination optimization unit 27 selects one combination, counts the number of vehicle convoys at each vertex in the combination (step S22), and calculates the travel time of all vehicle convoys (step S23).

The combination optimization unit 27 acquires the condition information 21e (step S24) and determines whether the number of vehicle convoys at each vertex in the combination and the travel time of all vehicle convoys satisfy the constraints in the condition information 21e (step S25).

For example, let us assume that the constraints are that a certain number of vehicles or less pass through each vertex at the same time, that the movement must be completed in the shortest time possible, and that vehicles with higher priority arrive first.

If the condition is not satisfied (NO in step S25), the process proceeds to step S29. On the other hand, if the condition is satisfied (YES in step S25), the combination optimization unit 27 compares the number of vehicle trains at each vertex and the travel time of all vehicle trains with the previous optimal solution (step S26) and determines whether the current solution is the optimal solution (step S27). The determination of whether the current solution is the optimal solution may be made, for example, from the perspective of the degree to which the objective of the condition information 21e is achieved, or other methods may be used. The optimal solution may be stored, for example, in a storage area such as the memory unit 21.

In the judgment of one or both of steps S25 and S27, for example, if there are multiple constraint conditions or objectives, the judgment may be made by comprehensively evaluating the multiple constraint conditions or objectives using a multi-objective optimization calculation. At this time, weights (priorities) may be assigned to the evaluation results of the multiple constraint conditions or objectives, such as whether the vehicle convoy is moving in the shortest possible way or whether a vehicle convoy with a higher priority has arrived first.

If the current solution is not the optimal solution (NO in step S27), the process proceeds to step S29. On the other hand, if the current solution is an optimization solution (YES in step S27), the combination optimization unit 27 updates the optimal solution (step S28) and determines whether the processing of all combinations calculated in step S21 has been completed (step S29).

If processing of all combinations has not been completed (NO in step S29), the process proceeds to step S22. If processing of all combinations has been completed (YES in step S29), the combination optimization unit 27 stores the combination of route candidates that is the optimal solution in the route information 21f (step S30), and the process ends.

As a result, the combination optimization unit 27 can determine, as an optimal solution, a combination of route candidates in which a predetermined number of vehicles or less pass through each vertex at the same time, the movement is completed in the shortest time, and the vehicle with the highest priority arrives first.

Note that FIG. 11 illustrates an example of a method for calculating an optimal solution by exhaustively searching combinations of route candidates, but this is not limiting. The optimal solution may be calculated with simpler logic using various methods, such as a method for solving optimization problems using a quantum computer.

(Route overlap determination process)
Next, an example of the operation of the route overlap determination process in step S8 in Fig. 9 will be described with reference to Fig. 12. As shown in Fig. 12, the combination optimization unit 27 sets counters for all vertices included in the route information 21f (step S31). These counters count the number of vehicle trains passing through each point for each point and time.

The combination optimization unit 27 obtains the route (route candidates) of each vehicle convoy from the route information 21f (step S32) and updates the counters corresponding to the vertices used in the route (passed by the vehicle convoy) (step S33).

The combination optimization unit 27 determines whether or not processing has been performed for all the routes of the convoy (step S34), and if processing has not been performed for all the routes of the convoy (NO in step S34), the process proceeds to step S32.

When the processing has been performed for all the vehicle convoy routes (YES in step S34), the combination optimization unit 27 judges whether or not all of the counter values are equal to or less than "1" (step S35). When all of the counter values are equal to or less than "1" (YES in step S35), in other words, when multiple vehicle convoys do not pass the same vertex at the same time, the combination optimization unit 27 sets OK (e.g., "1") as the judgment result (step S36), and the processing ends.

If the counter value includes a value greater than "1" (NO in step S35), in other words, if multiple vehicle convoys pass the same vertex at the same time (if the vehicle convoys overlap), the combination optimization unit 27 sets the judgment result to NG (e.g., "0") (step S37), and the process ends.

(Duplicate recovery process)
Next, an example of the operation of the overlap recovery process in step S9 in Fig. 9 will be described with reference to Fig. 13. As illustrated in Fig. 13, the combination optimization unit 27 acquires a determination result of the route overlap determination process (step S41), and determines whether or not the determination result is NG (step S42).

If the judgment result is not NG (OK) (NO in step S42), the process ends. In other words, since there is no overlapping route, the server 2 outputs the route information 21f to the route information destination 4 (see step S10 in FIG. 9).

If the result of the determination is NG (YES in step S42), the combination optimization unit 27 selects one of the route candidates of the overlapping vehicle convoys (step S43), and determines whether the priority of the selected vehicle convoy is higher than the other overlapping vehicle convoys (step S44). An example of the priority is the arrival order of the vehicle convoys.

If the priority of the selected vehicle convoy is higher than other overlapping vehicle convoys (YES in step S44), the combination optimization unit 27 confirms the selected route candidate to the route information 21f (step S45), and the process proceeds to step S49.

If the priority of the selected vehicle convoy is not higher than other overlapping vehicle convoys (NO in step S44), the combination optimization unit 27 determines whether the selected route candidate is the same as the confirmed route (step S46).

If the selected route candidate is the same as the confirmed route (YES in step S46), the combination optimization unit 27 discards the selected route information (step S47) and the process proceeds to step S49.

If the selected route candidate is not the same as the confirmed route (NO in step S46), the combination optimization unit 27 stores the selected route candidate in new route candidate information 21d (step S48) and determines whether all overlapping route candidates have been processed (step S49).

If all overlapping route candidates have not been processed (NO in step S49), processing proceeds to step S43.

When all overlapping route candidates have been processed (YES in step S49), the combination optimization unit 27 confirms to the route information 21f the route candidate of the vehicle convoy that has a higher priority than the overlapping vehicle convoy confirmed in step S45 among the vehicle convoys that do not have overlapping route candidates (step S50).

In addition, the combination optimization unit 27 stores route candidates for vehicle convoys that have a lower priority than the undetermined vehicle convoys among those with no overlapping route candidates in the new route candidate information 21d described above (step S51).

Furthermore, the combination optimization unit 27 fixes all the confirmed routes of the convoy as one route candidate and stores it in the new route candidate information 21d described above (step S52).

Then, the combination optimization unit 27 executes the combination optimization process illustrated in FIG. 11 using the new route candidate information 21d generated in steps S48, S51, and S52 (step S53), and the process ends. In the combination optimization process of step S53, a process of identifying a second combination is performed, and the route information 21f obtained in the combination optimization process of step S5 in FIG. 9 may be updated.

In this way, when convoys passing through the same point during the second time interval overlap, the combination optimization unit 27 determines the routes of some of the convoys in steps S45 and S50. For example, the combination optimization unit 27 determines the route of a first convoy that has a higher priority among the overlapping convoys, and the route of a second convoy that has a higher priority than the first convoy among the multiple convoys, as routes that satisfy the priority among the multiple second routes.

The combination optimization unit 27 also determines the routes of the vehicle convoys whose routes have not been determined among the multiple vehicle convoys based on priority order (steps S51 to S53) from among the multiple second routes, excluding the determined routes (step S47).

[1-5] Application Examples Next, application examples of the system 1 according to one embodiment will be described.

[1-5-1] First Application Example Hereinafter, the first application example will be described with reference to Fig. 14 to Fig. 16. In the first application example, the server 2 is assumed to comply with the following "purpose" and "movement conditions". The movement conditions may be obtained from at least one of the graph information 21b, the start point/end point information 21c, and the condition information 21e (constraint conditions).
Objective: Create a schedule that will get all vehicles to their destinations as quickly as possible, subject to travel conditions.
Travel conditions - Travel speed: 80 km/h on expressway, 30 km/h on general road
Number of vehicles in the train: 2
- Priority of convoys: Convoy 1 > Convoy 2
・Interval between trains: 1 hour ・Graph information Number of vertices: 4 (start point, point 1, point 2, destination)
Distance between vertices: Starting point to point 1: 60 km (public road), point 1 to point 2: 240 km (expressway), point 2 to destination: 60 km (public road)
・Start time from destination: 8:00

The route candidate calculation unit 25 generates route candidate information 21d based on the graph (graph information 21b) indicated by symbol A in FIG. 14. Note that, although one "route candidate 1" is illustrated in the example of FIG. 14, multiple route candidates may be generated for each vehicle convoy.

In the time information setting process, the route candidate calculation unit 25 calculates the travel time between vertices (see symbol B), and calculates the passing time of each vertex (see symbol C) based on the departure time from the departure point in the start point and end point information 21c, and associates it with the route candidate information 21d (see symbol D). In addition, the route candidate calculation unit 25 creates multiple route candidates with staggered departure times for each vehicle convoy (see symbols E and F).

As shown in the example of FIG. 15, the combinatorial optimization unit 27 solves a combinatorial optimization problem using multiple route candidates (see symbol A) for each vehicle convoy, to find a combination that does not include multiple vehicle convoys at the same time and in the same place. In the example of FIG. 15, for the sake of simplicity, it is assumed that two vehicle convoys, vehicle convoy 1 and vehicle convoy 2, use the same route candidate.

As shown by symbol B in FIG. 15, the combination optimization unit 27 checks whether the required time and constraint conditions are satisfied for each combination of routes that each vehicle convoy can take. In the example of symbol B, combinations 1 and 4 have two vehicle convoys at the same vertex at the same time, so the constraint conditions are judged as NG (constraint judgment).

Both combinations 2 and 3 pass the constraint judgment (are optimal solutions). In this case, the same effect can be obtained regardless of which combination is selected, but the priority of the convoys is convoy 1 > convoy 2. Therefore, the combination optimization unit 27 judges combination 2, in which convoy 1 arrives first, to be the optimal solution. In this way, by specifying the priority of arrival at the destination for each convoy, for example the order of arrival or arrival time, it is possible to create a schedule that takes priority into consideration.

Figure 16 is a diagram showing an example of the combination optimization process of the first application example. As illustrated in Figure 16, the combination optimization unit 27 finds combinations (see symbol B) from route candidates for each vehicle convoy (see symbol A), counts the number of vehicle convoys at each vertex from each combination, and calculates the travel time (see symbol C). The combination optimization unit 27 then checks whether the count and calculation result in symbol C meets constraints such as the number of vehicle convoys allowed at each vertex (see symbol D) (see symbol E), and compares the check result with the past optimal value (see symbol F). If the calculation result is a more optimal value than the past optimal value (unconditionally in the case of the first combination), the combination optimization unit 27 stores the calculation result in the memory unit 21 or the like as the optimal value (see symbol G), and repeats the processes of symbols E to G the number of combinations.

As shown in the first application example above, the server 2 according to one embodiment creates route candidate information 21d with time information added to each vertex (passing point, branching point), measures the congestion level (e.g., the number of vehicle convoys) at each vertex, and optimizes the route taking into account the passing time of each vehicle convoy. This makes it possible to set a schedule from the departure point to the destination for each vehicle convoy, taking into account the congestion level.

In addition, by setting priorities for each vehicle convoy, the server 2 can determine which vehicle convoy should be given priority at each vertex when routes overlap, allowing the vehicle convoys to arrive at the destination in the order of priority.

Furthermore, when one or both of the departure time and the arrival time of each vehicle train are specified in the start point/end point information 21c, the server 2 can search for route candidates that have a schedule close to one or both of the departure time and the arrival time. This makes it possible to search for route candidates that satisfy one or both of the preset departure time and the arrival time.

As described above, according to one embodiment, server 2 can calculate the route, departure time, arrival time, etc. for all vehicle convoys to arrive from the departure point to the destination in the shortest time, and generate an optimized schedule for each vehicle convoy individually.

[1-5-2] Second Application Example Next, a second application example will be described with reference to Figures 17 to 28. In the second application example, the server 2 is assumed to comply with the following "purpose" and "movement conditions".
Objective: Create a schedule that will get all vehicles to their destinations as quickly as possible, subject to travel conditions.
Travel conditions - Travel speed: 80 km/h on expressway, 30 km/h on general road
Number of vehicles in the train: 7
- Convoy priority: Convoy 1 > Convoy 2 > Convoy 3 > Convoy 4 > Convoy 5 > Convoy 6 > Convoy 7
・Interval between trains: 20 minutes ・Graph information Number of vertices: 8 (start point (10, 20), intermediate points (11, 12, 21, 22), destination (13, 23))
Distance between vertices: 10-11: 60km (general road), 11-12: 240km (expressway), 12-13: 60km (general road), 20-21: 60km (general road), 21-22: 240km (expressway), 22-23: 60km (general road), 11-22: 240km (expressway), 21-12: 240km (expressway)
・Start time from destination: 8:00
・Start point and destination of each convoy Convoy 1, Convoy 2: Start point 10, Destination 13
Convoy 4, Convoy 6, Convoy 7: Origin 20, Destination 23
Convoy 3: Origin 10, Destination 23
Convoy 5: Origin 20, Destination 13

Figure 17 is a diagram showing a graph and a route example of the second application example. As shown in Figure 17, the server 2 calculates which vehicle convoy 1 to vehicle convoy 7 should take which route and when they move from the starting point 10 or 20 to the destination 13 or 23. Note that in Figure 17, the diagram of one vehicle (truck) represents one vehicle convoy, the white vehicles are trucks whose starting point is vertex 10, and the black vehicles are trucks whose starting point is vertex 20.

Based on the graph in FIG. 17 (graph information 21b), the route candidate calculation unit 25 generates route candidate information 21d according to the above travel conditions, as illustrated in FIG. 18.

In the time information setting process, the route candidate calculation unit 25 calculates the travel time between vertices for each vehicle train, as illustrated in FIG. 19, calculates the passing time of each vertex based on the departure time from the departure point in the start point and end point information 21c, and associates the calculated time with the route candidate information 21d.

The route candidate calculation unit 25 also creates multiple route candidates with different departure times for each vehicle convoy, as illustrated in FIG. 20. Symbol A shows an example in which route candidates are created every 20 minutes, in accordance with the interval (20 minutes) between vehicle convoys in the travel conditions.

However, in the example of symbol A, the number of route candidates increases as the interval between vehicle convoys becomes shorter, and the number of combinations increases exponentially as the number of route candidates increases, resulting in an increase in the scale of calculations. Therefore, as illustrated in symbol B, the route candidate calculation unit 25 creates route candidates by consolidating multiple route candidates into one route candidate for each reference time (e.g., one hour) based on the travel conditions modified to consolidate the interval between vehicle convoys into a reference time. This generates route candidate information 21d in one-hour units as illustrated in FIG. 21.

As illustrated in FIG. 22, the combination optimization unit 27 determines a solution that has the shortest total travel time and satisfies the priority of the vehicle convoy among the combinations of the route candidates in the route candidate information 21d that satisfy the constraint conditions as the optimal solution. The constraint condition is "the number of vehicle convoys passing through the same vertex (point and time) is "3" or less." In the example of FIG. 22, the combinations 2 and 3 that satisfy the constraint conditions ("Constraint check" is "OK") among the combinations 1 to 12 of the route candidates in the route candidate information 21d are combinations 2 and 3. Both combinations 2 and 3 have a total travel time of "50" that satisfies the constraint conditions, which is the shortest time. As illustrated in FIG. 21, in combination 2, the priority of vehicle convoys 1 to 7 is respected, but in combination 3, vehicle convoy 6 arrives at the destination after vehicle convoy 7. Therefore, the combination optimization unit 27 determines combination 2, in which the priority of the vehicle convoy is respected, as the optimal solution. The combination of the optimal solution may be stored in the route information 21f.

The combination optimization unit 27 extracts a route for each vehicle convoy found by the combination optimization (see reference A in FIG. 23). In the optimal solution, there are multiple vehicle convoys that pass the same vertex at the same time (see reference A in FIG. 22 and FIG. 23). The route candidate calculation unit 25 creates route candidates assuming that there are three vehicle convoys that can pass the vertex within one hour, so the combination optimization unit 27 sets detailed times to route candidates with 20 minutes between each time based on the travel conditions. For example, as illustrated by reference B in FIG. 23, the combination optimization unit 27 adds detailed time information by adding 20 minutes to the route candidates based on the priority order. In the example of reference B in FIG. 23, 20 minutes are added from reference A to the shaded time portion changed to "route candidate 1'". In the example of reference B in FIG. 23, the combination optimization unit 27 shifts the time based on the departure time, but this is not limited to this, and the time may be shifted based on other vertices (locations and times).

In the route overlap determination process, the combination optimization unit 27 determines whether the route candidates indicated by symbol B in FIG. 23 overlap for each vertex (location and time), as illustrated in FIG. 24. In the example of FIG. 24, the vertices in the "overlap confirmation" row where the number of vehicle convoys is "2" or more (vertex 12: time "15:20", vertex 13: time "17:20", vertex 22: time "15:40", vertex 23: time "17:40") are determined to overlap. Vertex 12 (time "15:20") and vertex 13 (time "17:20"), with the number of vehicle convoys surrounded by solid line circles, are routes where vehicle convoys 2 and 5 overlap, and vertex 22 (time "15:40") and vertex 23 (time "17:40"), with the number of vehicle convoys surrounded by dashed line circles, are routes where vehicle convoys 3 and 6 overlap.

In the overlap recovery process, the combination optimization unit 27 determines routes for the convoy of vehicles that do not overlap, as illustrated in FIG. 25.

For example, in the example of FIG. 24, the combination optimization unit 27 determines the routes of the non-overlapping convoys 1 and 4 (see symbol A in FIG. 25). Furthermore, for the overlapping convoys 2 and 5, and for the overlapping convoys 3 and 6, the combination optimization unit 27 determines the routes of the high-priority convoys 2 and 3, respectively (see symbol A in FIG. 25). Furthermore, among the overlapping convoys 5 and 6 whose routes are undetermined, the combination optimization unit 27 sets the convoys with a priority level equal to or lower than the high-priority convoy 5 as undetermined (see symbol B in FIG. 25). Although convoy 7 does not overlap, convoys 5 and 6, which have higher priorities than convoy 7, are undetermined, so the combination optimization unit 27 also sets convoy 7 as undetermined.

As illustrated in FIG. 26, the combination optimization unit 27 creates new route candidates for the overlapping vehicle convoys (vehicle convoys whose routes are undetermined) shown by symbol B in FIG. 25. For example, the combination optimization unit 27 fixes the determined routes for vehicle convoys 1 to 4 whose routes are determined, and generates multiple route candidates for vehicle convoys 5 to 7 whose routes are undetermined, shifting each route by the interval between the vehicle convoys (20 minutes). At this time, when generating route candidates for vehicle convoys 5 to 7, the combination optimization unit 27 excludes routes that overlap with the already determined routes for vehicle convoys 1 to 4 from the candidates to be generated. In the example of FIG. 26, route candidates 1 and 2 for vehicle convoy 5, route candidates 1 and 3 for vehicle convoy 6, and route candidate 1 for vehicle convoy 7 are excluded from the candidates to be generated.

As shown in FIG. 27, the combination optimization unit 27 generates all combinations (1 x 2 x 2 x 3 = 12 combinations) of vehicle trains 1 to 4 (collectively, 1 combination), vehicle train 5 (2 combinations), vehicle train 6 (2 combinations), and vehicle train 7 (3 combinations), and performs combination optimization processing (reprocessing).

In the example of FIG. 27, combination 3 and combination 4 satisfy the constraint condition (all vertices (locations and times) are one or less convoy). The combination optimization unit 27 determines combination 3, which respects the priority of the convoys, as the optimal solution, and stores the routes of each convoy of combination 3 in the route information 21f, as exemplified by reference character A in FIG. 28. This results in the acquisition of movement models of convoys 1 to 7, as exemplified by reference character B in FIG. 28. Note that, as can be seen from the example of FIG. 28, the priority between convoys with different destinations (e.g., convoys 2 and 4) does not need to be taken into consideration. In other words, it is sufficient that a schedule based on priority is generated between convoys with a common destination.

As shown in the above second application example, the server 2 according to one embodiment can generate route information 21f using a method similar to that of the first application example. In addition, at that time, the server 2 can reduce the number of combinations that are the subject of the combinatorial optimization process.

For example, in the second application example, when generating route combinations every 20 minutes from the beginning, the number of combinations is 7 to the fourth power = 2401. On the other hand, according to the method of one embodiment, when determining route combinations for each hour, the number of combinations is 7 to the second power = 49, and when recalculating the overlapping parts (combination optimization processing after overlap recovery processing), the number of combinations is 2 x 2 x 3 = 12. In this way, according to the method of one embodiment, a schedule can be obtained with a total of 61 combinations in the second application example, and the number of combinations can be significantly reduced (for example, reduced to about 1/40) compared to when generating route combinations every 20 minutes from the beginning. Therefore, the processing load on the server 2 can be reduced and the processing time can be shortened, in other words, the schedule generation can be accelerated.

In this way, when the number of combinations increases as a constraint condition, the server 2 according to one embodiment sets the difference time for shifting the departure time to a unit time greater than the interval between vehicle convoys, and further increases the number of vehicle convoys that can pass the vertex within that unit time. This reduces the number of route candidates and the number of combinations, thereby reducing the calculation time.

As described above, according to the server 2 of one embodiment, even if the number of combinations increases as a constraint condition, the number of candidate routes generated for each time can be reduced by allowing multiple vehicle convoys to exist at one vertex at the same time (limiting the number of vehicle convoys to multiple).

After calculating the optimal solution for the combination of route candidates, the server 2 generates route candidates by adding detailed times for multiple vehicle convoys that exist at one vertex at the same time, thereby deriving the optimal combination of detailed route candidates for each vehicle convoy. This makes it possible to adjust the schedule of each vehicle convoy individually.

Furthermore, when priority is given to vehicle convoys, the server 2 can select a combination of detailed route candidates based on the priority, such that the vehicle convoy with the highest priority arrives first.

[1-5-3] Third Application Example Next, a third application example will be described with reference to Fig. 29 and Fig. 30. In the third application example, another usage form of the system 1 according to an embodiment will be described. Note that the third application example may be implemented in appropriate combination with the first application example or the second application example.

(Example of setting priorities for multiple routes)
As shown by symbol A in Figure 29, it is assumed that there are two routes from the departure point to the destination: a shortest route (departure point, point 1, point 2, destination) that takes the shortest time, and a detour route (departure point, point 3, point 4, destination) that takes longer than the shortest route.

The server 2 uses the above-mentioned method to calculate the combination that will result in the shortest travel time for all vehicle convoys, but for detours, it can calculate an efficient route for each vehicle convoy by taking into account the required travel time and determining whether or not to use the detour.

As an example, as shown by symbol B, the server 2 may generate route candidate 1-1, which is the shortest route with a departure time of "8:00", route candidate 1-2, which is the shortest route with the departure time delayed to "9:00", and route candidate 2, which is a detour with a departure time of "8:00". For example, the server 2 may set values for the priority of the route candidates in the order of shortest route 1-1 > shortest route 1-2 > detour 2. In this way, the detour is assigned to the vehicle convoy only if route candidates 1-1 and 1-2 are both used by another vehicle convoy that precedes it (e.g. has a higher priority).

Therefore, for example, when route candidate 1-1 is assigned to the motorcade with the first priority, it may be possible to bring forward the arrival time of the motorcade with the second priority compared to when route candidate 2, which has an earlier departure time, is assigned to the motorcade with the second priority. In the example of FIG. 29, by assigning route candidate 1-2 to the motorcade with the second priority, it is possible to set the arrival time of the motorcade with the second priority to "18:00", one hour earlier than the arrival time of the detour route, which is "19:00".

(When part of a route is shared between multiple departure points and multiple destinations)
As illustrated in FIG. 30 , when there are multiple departure points and/or destinations, such as departure points 1 and 2, and destinations 1 and 2, part of the route, for example intermediate points (points 3 and 4), may be shared between different routes.

In this case, server 2 can avoid congestion on the route passing through shared points 3 and 4 by limiting the number of vehicles in the convoy at each vertex.

[1-6] Hardware Configuration Example The device that realizes the server 2 according to an embodiment may be a virtual server (VM; Virtual Machine) or a physical server. The functions of the server 2 may be realized by one computer or by two or more computers. Furthermore, at least a part of the functions of the server 2 may be realized using HW (Hardware) resources and NW (Network) resources provided by a cloud environment.

FIG. 31 is a block diagram showing an example of a hardware (HW) configuration of a computer 10 that realizes the functions of a server 2 according to one embodiment. When multiple computers are used as HW resources that realize the functions of the server 2, each computer may have the HW configuration shown in FIG. 31.

As shown in FIG. 31, the computer 10 may, as a HW configuration, illustratively include a processor 10a, a memory 10b, a storage unit 10c, an IF (Interface) unit 10d, an I/O (Input/Output) unit 10e, and a reading unit 10f.

Processor 10a is an example of a processing unit that performs various controls and calculations. Processor 10a may be connected to each block in computer 10 via bus 10i so that they can communicate with each other. Processor 10a may be a multiprocessor including multiple processors, a multicore processor having multiple processor cores, or a configuration having multiple multicore processors.

The processor 10a may be, for example, an integrated circuit (IC) such as a CPU, MPU, GPU, APU, DSP, ASIC, or FPGA. Note that a combination of two or more of these integrated circuits may be used as the processor 10a. CPU is an abbreviation for Central Processing Unit, and MPU is an abbreviation for Micro Processing Unit. GPU is an abbreviation for Graphics Processing Unit, and APU is an abbreviation for Accelerated Processing Unit. DSP is an abbreviation for Digital Signal Processor, ASIC is an abbreviation for Application Specific IC, and FPGA is an abbreviation for Field-Programmable Gate Array.

Memory 10b is an example of HW that stores various data, programs, and other information. Examples of memory 10b include one or both of a volatile memory such as a dynamic random access memory (DRAM) and a non-volatile memory such as a persistent memory (PM).

The storage unit 10c is an example of HW that stores various data, programs, and other information. Examples of the storage unit 10c include various storage devices such as magnetic disk devices such as HDDs (Hard Disk Drives), semiconductor drive devices such as SSDs (Solid State Drives), and non-volatile memories. Examples of non-volatile memories include flash memories, SCMs (Storage Class Memory), and ROMs (Read Only Memory).

In addition, the information 21a to 21f stored in the memory unit 21 shown in FIG. 4 may be stored in a storage area of either or both of the memory 10b and the storage unit 10c.

The storage unit 10c may also store a program 10g (route search program) that realizes all or part of the various functions of the computer 10. For example, the processor 10a of the server 2 can realize the functions of the server 2 illustrated in FIG. 4 by expanding the program 10g stored in the storage unit 10c into the memory 10b and executing it.

The IF unit 10d is an example of a communication IF that controls the connection and communication between one or both of the networks. For example, the IF unit 10d may include an adapter that complies with a LAN such as Ethernet (registered trademark) or optical communication such as FC (Fibre Channel). The adapter may support one or both of wireless and wired communication methods. For example, the server 2 may be connected to the map data provider 3, the route information provider 4, and an operator's operation terminal (not shown) via the IF unit 10d so that they can communicate with each other. Also, for example, the program 10g may be downloaded from the network to the computer 10 via the communication IF and stored in the memory unit 10c.

The I/O unit 10e may include one or both of an input device and an output device. Examples of input devices include a keyboard, a mouse, a touch panel, etc. Examples of output devices include a monitor, a projector, a printer, etc.

The reading unit 10f is an example of a reader that reads data and program information recorded on the recording medium 10h. The reading unit 10f may include a connection terminal or device to which the recording medium 10h can be connected or inserted. Examples of the reading unit 10f include an adapter that complies with USB (Universal Serial Bus) or the like, a drive device that accesses a recording disk, and a card reader that accesses a flash memory such as an SD card. The recording medium 10h may store a program 10g, and the reading unit 10f may read the program 10g from the recording medium 10h and store it in the memory unit 10c.

Examples of the recording medium 10h include non-transitory computer-readable recording media such as magnetic/optical disks and flash memories. Examples of magnetic/optical disks include flexible disks, CDs (Compact Discs), DVDs (Digital Versatile Discs), Blu-ray Discs, and HVDs (Holographic Versatile Discs). Examples of flash memories include semiconductor memories such as USB memories and SD cards.

The HW configuration of the computer 10 described above is an example. Therefore, the HW in the computer 10 may be increased or decreased (for example, adding or deleting any block), divided, integrated in any combination, or buses may be added or deleted as appropriate. For example, in the server 2, at least one of the I/O unit 10e and the reading unit 10f may be omitted.

Note that each of the map data provider 3 computer, the route information recipient 4 computer, and the operator's operation terminal may be realized with a HW configuration similar to that of the computer 10 described above.

[2] Others The technology according to the embodiment described above can be modified and changed as follows.

For example, the map data acquisition unit 22, graph extraction unit 23, start point/end point setting unit 24, route candidate calculation unit 25, condition setting unit 26, combination optimization unit 27, and output unit 28 provided in the server 2 shown in FIG. 4 may be combined in any combination, or may be separated.

The server 2 shown in FIG. 4 may also be configured such that multiple devices cooperate with each other via a network to realize each processing function. For example, each of the multiple functional blocks shown in FIG. 4 may be distributed and arranged on servers such as a web server, an application server, and a database server. In this case, the web server, the application server, and the database server may cooperate with each other via a network to realize each processing function of the server 2.

In one embodiment, the vehicle is described as being a truck, but this is not limited thereto, and the vehicle may be, for example, a passenger car, a two-wheeled vehicle (motorcycle), or a bicycle.

[3] Supplementary Notes The following supplementary notes are further disclosed with respect to the above-described embodiment.

(Appendix 1)
A route search process is performed to assign one of a plurality of routes sharing at least one point to each of a plurality of vehicle groups;
In the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
In the first combination, when two or more vehicle groups pass through the same point during the first time interval, a second combination is identified between each of the two or more vehicle groups and each of a plurality of second routes that are distinguished by a second time interval shorter than the first time interval, according to the priority order.
A route search program that causes a computer to execute processing.

(Appendix 2)
The permitted number is calculated based on the first time interval and the second time interval;
The process of identifying the second combination is executed when the allowable number is equal to or greater than 2.
2. The route search program according to claim 1.

(Appendix 3)
The process of identifying the second combination includes:
A route search program as described in Appendix 1 or Appendix 2, which includes a process of, when vehicle groups passing through the same point during the second time interval overlap, determining the route of a first vehicle group having the higher priority among the overlapping vehicle groups and the route of a second vehicle group having a higher priority than the first vehicle group among the multiple vehicle groups as routes among the multiple second routes that satisfy the priority, respectively.

(Appendix 4)
The process of identifying the second combination includes:
A route search program as described in Appendix 3, which includes a process of determining a route of a vehicle group of the plurality of vehicle groups whose route has not been determined based on the priority from among the routes of the plurality of second routes excluding the determined route.

(Appendix 5)
Each of the process of identifying the first combination and the process of identifying the second combination includes one or both of a departure time and an arrival time of at least one of the plurality of vehicle groups.
The route search program according to any one of claims 1 to 4.

(Appendix 6)
Each of the plurality of first routes and the plurality of second routes includes a plurality of point information in which information indicating a point included in the first route or the second route is associated with a time when a vehicle group departs from, passes through, or arrives at the point.
A route search program according to any one of claims 1 to 5.

(Appendix 7)
a control unit that executes a route search process for assigning any one of a plurality of routes that share at least one point to each of a plurality of vehicle groups;
The control unit, in the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
A route search device that, when two or more vehicle groups pass through the same point during the first time interval in the first combination, identifies a second combination of each of the two or more vehicle groups and each of a plurality of second routes distinguished by second time intervals shorter than the first time interval, according to the priority order.

(Appendix 8)
The permitted number is calculated based on the first time interval and the second time interval;
the control unit executes a process of identifying the second combination when the allowable number is 2 or more.
8. The route search device according to claim 7.

(Appendix 9)
In the process of identifying the second combination, when vehicle groups passing through the same point during the second time interval overlap, the control unit determines a route of a first vehicle group having a higher priority among the overlapping vehicle groups and a route of a second vehicle group having a higher priority than the first vehicle group among the plurality of vehicle groups as routes that satisfy the priority among the plurality of second routes, respectively.
9. The route search device according to claim 7 or 8.

(Appendix 10)
The control unit, in the process of identifying the second combination, determines a route of a vehicle group of the plurality of vehicle groups whose route has not been determined from among the plurality of second routes excluding the determined route, based on the priority order.
10. The route search device according to claim 9.

(Appendix 11)
Each of the process of identifying the first combination and the process of identifying the second combination includes one or both of a departure time and an arrival time of at least one of the plurality of vehicle groups.
The route search device according to any one of Supplementary Note 7 to Supplementary Note 10.

(Appendix 12)
Each of the plurality of first routes and the plurality of second routes includes a plurality of point information in which information indicating a point included in the first route or the second route is associated with a time when a vehicle group departs from, passes through, or arrives at the point.
The route search device according to any one of claims 7 to 11.

(Appendix 13)
A route search process is performed to assign one of a plurality of routes sharing at least one point to each of a plurality of vehicle groups;
In the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
In the first combination, when two or more vehicle groups pass through the same point during the first time interval, a second combination is identified between each of the two or more vehicle groups and each of a plurality of second routes that are distinguished by a second time interval shorter than the first time interval, according to the priority order.
A route search method in which processing is performed by a computer.

(Appendix 14)
The permitted number is calculated based on the first time interval and the second time interval;
The process of identifying the second combination is executed when the allowable number is equal to or greater than 2.
14. The route search method according to claim 13.

(Appendix 15)
The process of identifying the second combination includes:
A route search method as described in Appendix 13 or Appendix 14, which includes a process of, when vehicle groups passing through the same point during the second time interval overlap, determining the route of a first vehicle group having the higher priority among the overlapping vehicle groups and the route of a second vehicle group having a higher priority than the first vehicle group among the multiple vehicle groups as routes among the multiple second routes that satisfy the priority, respectively.

(Appendix 16)
The process of identifying the second combination includes:
A route search method as described in Appendix 15, which includes a process of determining a route of a vehicle group of the plurality of vehicle groups whose route has not been determined based on the priority from among the routes of the plurality of second routes excluding the determined route.

(Appendix 17)
Each of the process of identifying the first combination and the process of identifying the second combination includes one or both of a departure time and an arrival time of at least one of the plurality of vehicle groups.
The route search method according to any one of Supplementary Note 13 to Supplementary Note 16.

(Appendix 18)
Each of the plurality of first routes and the plurality of second routes includes a plurality of point information in which information indicating a point included in the first route or the second route is associated with a time when a vehicle group departs from, passes through, or arrives at the point.
The route search method according to any one of Supplementary Note 13 to Supplementary Note 17.

REFERENCE SIGNS LIST 1 System 2 Server 20 Control unit 21 Memory unit 21a Map data 21b Graph information 21c Start point/end point information 21d Route candidate information 21e Condition information 21f Route information 22 Map data acquisition unit 23 Graph extraction unit 24 Start point/end point setting unit 25 Route candidate calculation unit 26 Condition setting unit 27 Combination optimization unit 28 Output unit 3 Map data provider 4 Route information provider

Claims (8)

A route search process is performed to assign one of a plurality of routes sharing at least one point to each of a plurality of vehicle groups;
In the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
In the first combination, when two or more vehicle groups pass through the same point during the first time interval, a second combination is identified between each of the two or more vehicle groups and each of a plurality of second routes that are distinguished by a second time interval shorter than the first time interval, according to the priority order.
A route search program that causes a computer to execute processing. The permitted number is calculated based on the first time interval and the second time interval;
The process of identifying the second combination is executed when the allowable number is equal to or greater than 2.
The route search program according to claim 1 . The process of identifying the second combination includes:
3. The route search program according to claim 1 or claim 2, further comprising a process for, when vehicle groups passing through the same point during the second time interval overlap, determining the route of a first vehicle group having the higher priority among the overlapping vehicle groups and the route of a second vehicle group having a higher priority than the first vehicle group among the plurality of vehicle groups as routes among the plurality of second routes that satisfy the priority, respectively. The process of identifying the second combination includes:
The route search program according to claim 3, further comprising a process of determining, from among the plurality of second routes excluding the determined route, a route of a vehicle group among the plurality of vehicle groups whose route has not been determined based on the priority. Each of the process of identifying the first combination and the process of identifying the second combination includes one or both of a departure time and an arrival time of at least one of the plurality of vehicle groups.
The route search program according to any one of claims 1 to 4. Each of the plurality of first routes and the plurality of second routes includes a plurality of point information in which information indicating a point included in the first route or the second route is associated with a time when a vehicle group departs from, passes through, or arrives at the point.
The route search program according to any one of claims 1 to 5. a control unit that executes a route search process for assigning any one of a plurality of routes that share at least one point to each of a plurality of vehicle groups;
The control unit, in the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
A route search device that, when two or more vehicle groups pass through the same point during the first time interval in the first combination, identifies a second combination of each of the two or more vehicle groups and each of a plurality of second routes distinguished by second time intervals shorter than the first time interval, according to the priority order. A route search process is performed to assign one of a plurality of routes sharing at least one point to each of a plurality of vehicle groups;
In the route search process,
identifying a first combination of each of the plurality of vehicle groups and each of a plurality of first routes distinguished for each first time interval based on a priority set for each of the plurality of vehicle groups, a time when the vehicle group passes each of a plurality of points included in the plurality of routes, and an allowable number of vehicle groups permitted to pass each of a plurality of points included in the plurality of routes for each first time interval;
In the first combination, when two or more vehicle groups pass through the same point during the first time interval, a second combination is identified between each of the two or more vehicle groups and each of a plurality of second routes that are distinguished by a second time interval shorter than the first time interval, according to the priority order.
A route search method in which processing is performed by a computer.

Images