JP7685980B2 - Route search support device, route search support method, and route search support system - Google Patents

Description

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

When solving shortest path problems using graph theory, complex constraints are often set. In such cases, candidate path patterns are created, and a solution algorithm for the set covering problem or set problem is applied to the created patterns to determine whether each path should be adopted or not, thereby solving the optimization problem.

For example, Patent Document 1 discloses an operation planning program that uses the set covering problem to create a route plan. The program uses an index indicating the likelihood of satisfying subadditivity for a set whose elements are users for whom an operation plan including carpooling is to be created, determines whether a combination of elements in descending order and within a certain number satisfies subadditivity, and adds combinations of elements that satisfy subadditivity to a subset that is the target of carpooling. The program divides the set into subsets while allowing overlapping elements as a set covering problem, and generates an operation plan using the divided subsets.

JP 2017-191504 A

However, because the number of route patterns increases exponentially with the number of stopovers on the route, when there are a large number of stopovers, the process of processing the optimization problem exceeds the processing power of the computer or the performance of the algorithm, increasing the possibility that a solution cannot be obtained.

The present invention was made in consideration of such problems, and aims to provide a route search support device, a route search support method, and a route search support system that can efficiently support searching for an appropriate route that passes through intermediate points to be passed, even when there are multiple intermediate points.

One of the present inventions for solving the above problem is an apparatus for supporting creation of a route for each of a plurality of moving bodies to travel via one or a plurality of via points, the route search support apparatus comprising: a processing device that executes a unit node creation process for creating unit nodes indicating via points that the moving body can pass through in the course of moving from a departure point to a destination; a real node setting process for setting, as a real node, one unit node or a combination of two or more adjacent unit nodes that satisfy a first condition among the unit nodes; a dummy node setting process for searching, among the unit nodes constituting the real node, one unit node or a combination of two or more adjacent unit nodes that satisfy a second condition, and setting the searched unit node as a dummy node; an optimal route creation process for calculating a value indicating whether or not to use a via point indicated by the unit node when optimizing a value of an objective function including a predetermined evaluation function related to a movement route of the moving body, with the number of times a via point indicated by a unit node other than the dummy node among the unit nodes constituting the real node as a constraint condition; and a result output process for outputting information indicating whether or not the moving body passed through each via point based on the calculated value.

Another aspect of the present invention for solving the above problem is a route search support system that supports creation of a route for each of a plurality of moving bodies to travel via one or a plurality of via points, the system comprising: a unit node creation process that creates unit nodes indicating via points that the moving body can travel via in the course of traveling from a departure point to a destination; a real node setting process that sets, as a real node, one unit node or a combination of two or more unit nodes adjacent to each other that satisfies a first condition among the unit nodes; a dummy node setting process that searches, among the unit nodes constituting the real node, for one unit node or a combination of two or more unit nodes adjacent to each other that satisfies a second condition, and sets the searched unit node to a dummy node; and an optimal route creation process that calculates a value indicating whether or not to use a via point indicated by the unit node when optimizing a value of an objective function including a predetermined evaluation function related to a moving route of the moving body, using as a constraint the number of times a via point indicated by a unit node other than the dummy node among the unit nodes constituting the real node.
The route creation support system is configured to include a route creation support device having a processing device that executes a result output process that outputs information indicating whether or not the mobile body will pass through each intermediate destination based on the calculated value, and an information processing device having a processing device that executes an input process that accepts input of intermediate destinations that the mobile body can pass through from a user, and a display process that displays the information output by the result output process on a screen.

According to the present invention, it is possible to assist in efficiently searching for an appropriate route that passes through via-points to be passed through, even when there are a large number of via-points.
Configurations and effects other than those described above will become apparent from the following description of the embodiments.

1 is a diagram illustrating an example of a configuration of a route search support system according to an embodiment of the present invention. FIG. 2 is a diagram illustrating an example of functions included in the route search assistance device. FIG. 2 is a diagram illustrating an example of hardware included in the route search assistance device. FIG. 11 is a flow diagram illustrating an outline of a route search support process. FIG. 11 is a flow diagram illustrating details of a route candidate generation process. FIG. 13 illustrates an example of a setting screen. FIG. 10 is a diagram illustrating an example of a search for a real node. FIG. 13 is a diagram illustrating an example of the configuration of a directed graph to be created. FIG. 11 is a diagram illustrating an example of a method for setting a dummy node. FIG. 4 is a diagram illustrating an example of a database stored in a graph analysis unit. 1 is a timing chart for obtaining the ground state of a spin system. 1 is a flowchart showing a solution algorithm for an Ising model.

The following describes an embodiment of the present invention with reference to the drawings.

<Route search support system>
1 is a diagram showing an example of the configuration of a route search support system 1 according to this embodiment. As shown in the figure, the route search support system 1 includes a route search support device 100 and one or more information processing devices of user terminals 200.

Communication between the route search assistance device 100 and each user terminal 200 is possible via a wired or wireless communication network 10 such as the Internet, a local area network (LAN), a wide area network (WAN), or a dedicated line.

The route search support device 100 supports the calculation of the optimal route (intermediate points through which each moving body should pass) to be adopted by each of multiple moving bodies when each of the moving bodies travels from a departure point to a destination via one or more intermediate points.

In this embodiment, the route search support device 100 creates a proposed delivery plan for relief supplies in the event of a widespread disaster spanning multiple cities. That is, bases where relief supplies are collected (supply collection bases) are located in various locations in each city, and vehicles that deliver the relief supplies are deployed at these supply collection bases. Each vehicle loads relief supplies at the supply collection base, departs from the supply collection base as a departure point, stops at each evacuation shelter while supplying the relief supplies, and arrives at a specified destination. The route search support device 100 then determines a vehicle route that ensures that the amount of relief supplies supplied is as fair as possible between the cities. Note that there is a constraint that only one vehicle can visit each evacuation shelter.

Specifically, first, the user terminal 200 requests the route search support device 100 to create a delivery plan for relief supplies. The route search support device 100 then creates a graph with nodes representing supply collection points, evacuation shelters, and destinations, and performs a graph search to create route candidates for each vehicle. The route search support device 100 then incorporates the created route candidates into an optimization model including a predetermined objective function to solve an optimization problem for the fair distribution of relief supplies, and identifies the optimal route for each vehicle. The user terminal 200 displays information about the route created by the route search support device 100. Note that the user of the user terminal 200 is, for example, a country, a local government, or a business entity that manages disaster response.

In this embodiment, the optimization model for calculating the optimal route is, for example, the model disclosed in International Publication No. WO 2016/157333.

The applicant has developed quantum computing technology and has attempted to solve various problems, for example, exhaustive search problems (including the concept of combinatorial optimization problems) based on big data. Expectations are generally high for quantum computers to solve such exhaustive search problems. Quantum computers consist of basic elements called quantum bits, which simultaneously realize "0" and "1". As a result, all solution candidates can be calculated simultaneously using the initial value, and there is the potential to realize an exhaustive search. However, quantum computers must maintain quantum coherence throughout the entire calculation time.

One method that has been gaining attention is adiabatic quantum computing (Reference: E. Farhi, et al., "A quantum adiabatic evolution al gorithm applied to random instances of an NP-complete problem," Science 292, 472 (2001).). This method transforms the problem so that the ground state of a certain physical system is the solution, and attempts to obtain a solution by finding the ground state.

Let H^p be the Hamiltonian of the physical system for which the problem is set. However, at the start of the calculation, the Hamiltonian is not H^p, but a different Hamiltonian H^0, whose ground state is clear and easy to prepare, is used. Next, a sufficient amount of time is taken to transition the Hamiltonian from H^0 to H^p. If a sufficient amount of time is taken, the system will remain in the ground state, and the ground state of Hamiltonian H^p will be obtained. This is the principle of adiabatic quantum computing. If the calculation time is τ, the Hamiltonian becomes equation (1),
[Formula 1]

A solution is obtained by time evolution based on the Schrödinger equation of equation (2).

[Formula 2]

Adiabatic quantum computing can be applied to problems that require exhaustive search, and a solution is reached in a one-way process. However, if the computation process needs to follow the Schrödinger equation in equation (2), quantum coherence must be maintained, just like in a quantum computer.

However, while a quantum computer repeats gate operations between one or two quantum bits, adiabatic quantum computing involves simultaneous interactions across the entire quantum bit system, and the concept of coherence is different.

For example, consider a gate operation on a certain quantum bit. At this time, if there is an interaction between that quantum bit and other quantum bits, it will cause decoherence, but in adiabatic quantum computing, all quantum bits interact simultaneously, so decoherence does not occur in this example. Reflecting this difference, adiabatic quantum computing is thought to be more robust against decoherence than quantum computers.

As described above, adiabatic quantum computing is effective for difficult problems that require an exhaustive search. Spin is treated as a variable in the calculation, and the problem to be solved is set in terms of spin-spin interactions and local fields acting on each spin.

At time t = 0, an external magnetic field is applied to orient all spins in one direction, and the external magnetic field is gradually reduced so that it becomes zero at time t = τ.

The orientation of each spin evolves over time according to the effective magnetic field determined by the combined effect of the external magnetic field at each site and the spin-spin interactions at time t.

In this case, the spin direction is not perfectly aligned with the effective magnetic field, but is quantum mechanically corrected so that the system remains nearly in the ground state.

In addition, a term that maintains each spin in its original orientation during time evolution (relaxation term) is added to the effective magnetic field, improving the convergence of the solution.
Based on the above, the functions of the route search assistance device 100 will be described next.

<Route search support device>
2 is a diagram showing an example of functions of the route search support device 100. The route search support device 100 includes an input data storage unit 110, a graph analysis unit 120, an optimal route creation processing unit 130, a result output processing unit 140, and an output data storage unit 150.

The input data storage unit 110 stores data input via the user terminal 200.

The graph analysis unit 120 creates a graph showing candidate routes for each vehicle. This graph is a directed graph in which the departure point, destination, and intermediate destination are each nodes, and the routes connecting these points are each links.

The graph analysis unit 120 specifically includes a unit node creation unit 121, a real node setting unit 122, a dummy node setting unit 123, a link connection unit 124, a graph search unit 125, and a coefficient storage unit 126.

The unit node creation unit 121 creates unit nodes, which are nodes that indicate intermediate stops that a vehicle can take on its journey from the departure point to the destination.

The real node setting unit 122 contracts a part of the unit nodes. In other words, the real node setting unit 122 sets one or a combination of two or more adjacent unit nodes that satisfy the first condition as a real node.

A unit node that satisfies the first condition is, for example, a unit node related to an evacuation shelter through which vehicles are likely to need to pass.

Furthermore, a combination of two or more adjacent unit nodes that satisfies the first condition is one in which an evaluation value indicating the strength of the bond between the unit nodes is equal to or greater than a predetermined value. In this embodiment, this is defined as a short vehicle travel time or short distance between the unit nodes being equal to or greater than a predetermined value, but it may also be based on an evaluation value from another perspective (for example, an evaluation value indicating low congestion of the route).

The real node setting unit 122 also creates real nodes that satisfy certain constraints that are commonly applied to each vehicle (e.g., the specification of a portion of a route that cannot be traveled by vehicles).

Next, the dummy node setting unit 123 contracts the unit nodes in the real node. That is, the dummy node setting unit 123 searches for one or two or more adjacent unit nodes that satisfy the second condition among the unit nodes that make up the real node, and sets the searched unit nodes as dummy nodes.

In this embodiment, the second condition is that if a unit node in the set real node contains one or two or more adjacent unit nodes that need to be passed through when a vehicle travels from a departure point to a destination point via a unit node other than the set real node (i.e., when a different travel route is adopted), the unit node is designated as a dummy node.

The second condition may be such that, among the unit nodes constituting the real node set above, a unit node whose evaluation value indicating the strength of the bond with other unit nodes is equal to or less than a predetermined value (for example, the travel time from another unit node is equal to or more than a predetermined time or the distance is equal to or more than a predetermined distance) is set as a dummy node. The second condition described here is an example, and the second condition may be a condition for specifying, among the unit nodes constituting the real node, a unit node that particularly requires a vehicle to pass through on each travel route. Note that these second conditions may be applied in combination.

The link connection unit 124 creates a directed graph showing the routes that the vehicle can travel based on the nodes set by the real node setting unit 122 and the dummy node setting unit 123.

The graph search unit 125 searches for a route (route candidates) for the vehicle to travel from the departure point to the destination via intermediate points based on the directed graph created by the link connection unit 124.

The coefficient storage unit 126 stores various data such as the route of each candidate route calculated during processing in the graph search unit 125 (a list of supply points, transit evacuation shelters, and destination), the distance of each candidate route, and the amount of relief supplies supplied to each city by vehicles traveling along each candidate route. These data include information such as coefficients of the optimization model created by the optimal route creation processing unit 130.

Next, the optimal route creation processing unit 130 creates an optimization model based on the data stored in the coefficient storage unit 126, and finds the optimal solution for the travel route of each vehicle that will ensure a fair supply of relief supplies in each city.

The optimization model includes an objective function including an evaluation function related to the vehicle's travel route, with the constraint being the number of times the route is visited at a route indicated by a unit node other than a dummy node among the unit nodes that make up the real node. The optimization model may also include different constraints in the objective function depending on the vehicle.

In addition, in this embodiment, the evaluation function is a leveling function that indicates the sufficiency rate of relief supplies between cities (the ratio of the actual supply of relief supplies to the demand for them), but it is also possible to adopt other evaluation functions, such as a function that reduces travel distances.

In addition, in this embodiment, the objective function includes a constraint on the number of vehicles to be deployed at each departure point, but is not limited to this.

In this embodiment, an Ising model is adopted as the optimization model. Specifically, the Ising model is an Ising model in which the spin is the use or non-use of the route indicated by the unit node, and the sensitivity between variables in the constraint function is set as the strength of interaction between the spins, for an objective function including a constraint function that is minimized when a constraint condition related to the number of times the route is passed through the route indicated by the unit nodes other than the dummy node among the unit nodes constituting the real node is satisfied, and an evaluation function related to the vehicle's travel route as a term. The Ising model will be described in detail later.

The optimization model is not limited to the Ising model, and any model that can appropriately solve the combinatorial optimization problem in accordance with the pathfinding support method of the present invention can be applied. An overview of the Ising model is disclosed in the above-mentioned international publication, and details of its specific configuration, operation, etc. will be omitted as appropriate (the same applies below).

Next, the result output processing unit 140 displays the calculation results by the optimal route creation processing unit 130 on the screen of the user terminal 200. The output data storage unit 150 stores the calculation results by the optimal route creation processing unit 130.

Here, Fig. 3 is a diagram showing an example of hardware included in the route search support device 100. The route search support device 100 includes a processing device 101 such as a central processing unit (CPU), a digital signal processor (DSP), a graphics processing unit (GPU), or a field-programmable gate array (FPGA), a memory 102 such as a random access memory (RAM) or a read only memory (ROM), a storage device 103 such as a hard disk drive (HDD) or a solid state drive (SSD), a communication device 104 including a network interface card (NIC), a wireless communication module, a universal serial interface (USB) module, or a serial communication module, an input device 105 such as a keyboard, a mouse, or a touch panel, and an output device 106 such as a liquid crystal monitor or a liquid crystal display (LCD). The user terminal 200 also includes similar hardware.

The route search support device 100 may be implemented not only by hardware implemented with an electronic circuit (such as a digital circuit) in the annealing method, but also by a superconducting circuit. The route search support device 100 may also include hardware that realizes an Ising model using a method other than the annealing method. This method is, for example, a laser network method (optical parametric oscillation) or a quantum neural network. In addition, although some of the concepts are different as described above, the present invention can also be realized using a quantum gate method in which the calculations performed in the Ising model are replaced with gates such as a Hadamard gate, a rotation gate, or a controlled NOT gate.

Each of the functions realized by the route search support device 100 described above is realized by the processing device 101 reading and executing each program stored in the memory 102 or the storage device 103. In addition, each program can be recorded on a recording medium and distributed, for example. Note that the route search support device 100 may be realized, in whole or in part, using virtual information processing resources provided using virtualization technology, process space separation technology, or the like, such as a virtual server provided by a cloud system. In addition, all or in part of the functions provided by the route search support device 100 may be realized, for example, by a service provided by a cloud system via an API (Application Programming Interface) or the like.

In addition, the adiabatic quantum computing in the Ising model is also called quantum annealing, and is an extension of the concept of classical annealing to quantum mechanics. In other words, adiabatic quantum computing can be interpreted as being capable of classical operation, with quantum mechanical effects added to improve performance in terms of speed and accuracy rate of solutions. Therefore, in this embodiment, the processing device 101 of the route search support device 100 itself is classical, and a parameter determined by quantum mechanics is introduced into the calculation process to realize a calculation method and device that are classical but include quantum mechanical effects, and perform calculations according to the Ising model. However, it is of course possible to adopt a form in which the processing device 101 is configured by a quantum computer.
Next, the processes performed by the route search assistance system 1 will be described.

<Route search support processing>
4 is a flow diagram for explaining an outline of a route search support process for searching an optimal route for transporting relief supplies by each vehicle. The route search support process is started, for example, when a route search instruction is input to the route search support device 100 from the user terminal 200.

First, the route search support device 100 executes a route candidate creation process s10 to create candidates (route candidates) for the transportation route of relief supplies. Then, the route search support device 100 executes an optimal route creation process s20 to create an Ising model based on the route candidates created in the route candidate creation process s10 and calculate the optimal transportation route for relief supplies. After that, the route search support device 100 outputs information about the optimal travel route created in the optimal route creation process s20 and displays it on the screen of the user terminal 200 (s30).

For example, the route search support device 100 displays each travel route on a map (for real nodes and dummy nodes, it displays intermediate stops for each unit node that constitutes them), as well as the amount of relief supplies transported along each travel route and the total amount of relief supplies supplied to each city, etc.
The route candidate generation process s10 and the optimum route generation process s20 will be described in detail below.

<Route candidate creation process>
FIG. 5 is a flow diagram illustrating the details of the route candidate generation process s10.
First, the graph analysis unit 120 stores the locations to be set as unit nodes from among possible collection locations, arrival locations, and evacuation shelters (s101).

Figure 6 is a diagram showing an example of a setting screen displayed on the user terminal 200 during processing of s101. This setting screen 500 includes a location operation screen 510, a location-to-location operation screen 520, a transport equipment operation screen 530, and an advanced screen 540.

The location operation screen 510 displays a list of locations (potential starting points, evacuation shelters, and arrival points) such as collection points for relief materials and public facilities in each city, and accepts the user's selection of locations to be used as unit nodes.

The point-to-point operation screen 520 displays a list of routes connecting points and the distances of those routes, and accepts the user's selection of available routes (links that can connect unit nodes).

The setting screen 500 may display a specified map screen, and accept the selection of a location corresponding to the location operation screen 510 and the selection of a route corresponding to the location-to-location operation screen 520 from the displayed map screen.

The transport equipment operation screen 530 displays a list of vehicles and the amount of relief supplies they transport, and accepts the user's selection of an available vehicle.

The advanced screen 540 accepts settings from the user regarding the optimization model, real nodes, and dummy nodes. Specifically, the advanced screen 540 includes a variable scale factor setting unit 541 that accepts the setting of the upper limit of the number of variables that can be used in the optimization model created in the optimal path creation process s20 or the upper limit of the ratio to the default value (variable scale factor) to adjust the complexity of the optimization problem, a dummy node number setting unit 542 that accepts the setting of the upper limit number of dummy nodes that can be set, and a maximum real node setting unit 543 that accepts the setting of the maximum real node length that is the upper limit of the length of a real node that can be contracted.

By adjusting the upper limit number of dummy nodes, it is possible to adjust the ease of passing through shelters related to the dummy nodes in route search, so for example, by reducing the upper limit number of dummy nodes, it is possible to improve the route search speed. Also, by adjusting the maximum length of real nodes, it is possible to adjust the route search speed. Also, by adjusting the variable scale factor, it is possible to prevent the number of variables of the objective function in the optimal route creation process s20 from exceeding the number of variables indicated by the variable scale factor.

Next, as shown in FIG. 5, the graph analysis unit 120 acquires mandatory constraint conditions that are commonly applied to each vehicle for the points indicated by each unit node set in s101 (s102). For example, the graph analysis unit 120 acquires information from a specified database regarding the time periods at each evacuation shelter during which the supply of relief supplies is not possible, or the routes between the supply collection point and the evacuation shelter, between the evacuation shelters, or between the evacuation shelter and the destination that are not passable by vehicles (for example, routes that are not passable by vehicles due to a disaster).

Then, the graph analysis unit 120 creates a virtual directed graph that shows a travel route that satisfies the above constraints and also satisfies a predetermined evaluation criterion (s103). The graph analysis unit 120 sets each unit node on this directed graph as a real node.

Specifically, the graph analysis unit 120 sets an evaluation criterion for the shortness of the distance of the route between points (an evaluation criterion formula in which the shorter the distance, the higher the evaluation value). Then, after setting the destination and the arrival point, the graph analysis unit 120 uses an algorithm such as Dijkstra's algorithm to search for a vehicle route from the departure point to the destination that will maximize the evaluation value related to the above evaluation criterion while adhering to the constraints set in s102. Note that the graph analysis unit 120 stores in advance information required for creating the evaluation criterion (for example, information between bases).

Then, the graph analysis unit 120 contracts the real nodes that are adjacent to each other and have strong mutual connections (real nodes that satisfy the first condition) from among the real nodes set above into a single real node (s104).

Specifically, when an evaluation value indicating the strength of the connection between adjacent real nodes is equal to or greater than a predetermined value, the graph analysis unit 120 contracts those real nodes. For example, when the distance between adjacent real nodes is shorter than a predetermined distance, the graph analysis unit 120 contracts and stores those real nodes. Note that this predetermined distance may be stored in advance in the route search support device 100, or may be a statistical value (e.g., an average value) of distances used up to now.

Figure 7 is a diagram for explaining an example of searching for a real node. As shown in the figure, when a vehicle searches for a movement route from a node 700, which is a departure point, to a node (not shown) which is a destination point, the next possible movement route from the first unit node 701, which is a real node, is a route to the second unit node 702 and a route to the fourth unit node 704. However, since the distance from the first unit node 701 to the second unit node 702 is shorter than the distance from the first unit node 701 to the fourth unit node 704, the graph analysis unit 120 determines the route from the first unit node 701 to the second unit node 702 as the shortest route, and determines the second unit node 702 as a real node. In addition, the graph analysis unit 120 determines the third unit node 703, which is the next adjacent node of the second unit node 702, as a real node. Then, if the distance between the first unit node 701 and the second unit node 702, and the distance between the second unit node 702 and the third unit node 703 are each equal to or less than a predetermined distance, the graph analysis unit 120 contracts the first unit node 701, the second unit node 702, and the third unit node 703 into one real node 705.

8 is a diagram showing an example of the configuration of a directed graph to be created. In the directed graph shown in the figure, a first moving route 831 is calculated for a moving route from a unit node 811 related to the first departure point to a unit node 821 related to the first arrival point, the first moving route 831 passing through a first unit node 801 (real node) related to the first shelter and a fourth unit node 804 (real node) related to the fourth shelter in this order. In addition, a second moving route 832 is calculated for another moving route from the unit node 811 related to the first departure point to a unit node 821 related to the first arrival point, the fourth unit node 804 (real node) related to the fourth shelter, the second unit node 802 (real node) related to the second shelter, the third unit node 803 (real node) related to the third shelter, the sixth unit node (real node) related to the sixth shelter, and the fifth unit node (real node) related to the fifth shelter in this order. On the other hand, for the movement route from the unit node 812 related to the second departure point to the unit node 822 related to the second arrival point, a third movement route 833 is calculated that passes through the third unit node 803 (real node) related to the third shelter, the sixth unit node 806 (real node) related to the sixth shelter, and the seventh unit node 807 (real node) related to the seventh shelter in this order. Furthermore, for the movement route from the unit node 812 related to the second departure point to the unit node 821 related to the first arrival point, a fourth movement route 834 is calculated that passes through the third unit node 803 (real node) related to the third shelter, the sixth unit node 806 (real node) related to the sixth shelter, and the fifth unit node 805 (real node) related to the fifth shelter in this order.

If the distance between the first unit node 801 (real node) related to the first shelter and the fourth unit node 804 (real node) related to the fourth shelter is equal to or less than a predetermined distance, the graph analysis unit 120 contracts these real nodes and sets them as the first contracted real node 841. If the distance between the third unit node 803 (real node) related to the third shelter and the sixth unit node 806 (real node) related to the sixth shelter is equal to or less than a predetermined distance, and the distance between the sixth unit node 806 (real node) related to the sixth shelter and the seventh unit node 807 (real node) related to the seventh shelter is equal to or less than a predetermined distance, the graph analysis unit 120 contracts these three real nodes and sets them as the second contracted real node 842.

If the total length of the unit nodes that make up the contracted real node exceeds the maximum real node length set in s101, the graph analysis unit 120 divides the contracted real node into two or more contracted real nodes so that the length of the unit nodes that make up each contracted real node does not exceed the maximum real node length.

Next, as shown in FIG. 5, the graph analysis unit 120 sets, as dummy nodes, unit nodes that satisfy the second condition among the unit nodes that constitute each real node on each movement route (s105, s106). Specifically, the graph analysis unit 120 identifies unit nodes that are important as stopovers on other movement routes among the unit nodes in each real node on each movement route, and sets the identified unit nodes as dummy nodes (s105). Then, the graph analysis unit 120 contracts multiple dummy nodes that are adjacent to each other among the set dummy nodes and sets them as one dummy node (s106).

For example, the graph analysis unit 120 selects a real node of a certain movement route, and among the unit nodes of the selected real node, searches for unit nodes related to shelters that need to be passed through on other movement routes (movement routes that pass through shelters indicated by unit nodes other than the unit nodes in the real node), and sets these as dummy nodes. Also, for example, the graph analysis unit 120 may set unit nodes in a real node whose preset importance is higher than a specified value as dummy nodes.

Also, for example, the graph analysis unit 120 sets, as dummy nodes, unit nodes within a real node whose evaluation value indicating the strength of the bond with other unit nodes is equal to or less than a predetermined value (for example, whose distance from other unit nodes is equal to or greater than a predetermined distance).

Next, the graph analysis unit 120 reduces, among the dummy nodes set as described above, multiple adjacent dummy nodes into one dummy node. At this time, the graph analysis unit 120 may reduce, into one dummy node, a combination of dummy nodes whose evaluation value indicating the strength of their mutual bonds is equal to or greater than a predetermined value (for example, a combination of real nodes whose adjacent real nodes are separated by a predetermined distance or less).

If the number of dummy nodes is equal to or greater than the upper limit of dummy nodes set in step s101, the graph analysis unit 120 will not set any more dummy nodes.

9 is a diagram for explaining an example of a method for setting dummy nodes by the graph analysis unit 120 (showing a situation following FIG. 8). For example, a first contracted real node 841 set on a first movement path 831 includes a first unit node 801 and a fourth unit node 804. Here, on a second movement path 832, which is another movement path,
It is necessary to go through the fourth unit node 804. Therefore, the graph analysis unit 120 sets the fourth unit node 804 in the first contracted real node 841 as a dummy node.

In addition, the second contracted real node 842 set in the third movement path 833 includes the third unit node 803, the sixth unit node 806, and the seventh unit node 807. Here, in the second movement path 832, which is another movement path, it is necessary to pass through the third unit node 803 and the sixth unit node 806. Therefore, the graph analysis unit 120 sets the third unit node 803 and the sixth unit node 806 in the second contracted real node 842 as dummy nodes. Furthermore, the graph analysis unit 120 contracts these mutually adjacent third unit node 803 and sixth unit node 806 into one dummy node.

Furthermore, for the third movement path 833, another movement path, the fourth movement path 834, needs to go through the sixth unit node 806. Therefore, the graph analysis unit 120 sets the sixth unit node 806 in the second contracted real node 842 as a dummy node. In this way, a dummy node may be set simultaneously (overlappingly) in relation to multiple movement paths (here, the second movement path 832 and the fourth movement path 834).

As described above, the graph analysis unit 120 creates real nodes and dummy nodes that have different contraction perspectives (s104-s106).

Next, as shown in FIG. 5, the graph analysis unit 120 creates links that connect the nodes based on the real nodes and dummy nodes identified above, thereby creating a graph consisting of nodes and links (s107).

For example, the graph analysis unit 120 sets one real node by representing the unit node (however, a real node that is not set as a dummy node) that is closest to the departure point in the contracted real node. The graph analysis unit 120 also sets one dummy node by representing the unit node that is closest to the departure point in the dummy node. The graph analysis unit 120 creates a graph consisting of nodes and links based on the node related to the departure point, the node related to the destination point, the set nodes, and real nodes (not contracted) and dummy nodes other than the set nodes.

At this time, the graph analysis unit 120 calculates the distance between each of the created links by obtaining the distance between each of the unit nodes (starting point, each evacuation shelter, and the arrival point) set in s101 from a specified database.

Then, based on the directed graph created in s107, the graph analysis unit 120 searches for and identifies all travel routes (route candidates) from each departure point to each arrival point via evacuation shelters (s108). The graph analysis unit 120 then stores in a database various data calculated and identified for all travel routes. This completes the route candidate creation process s10.

Figure 10 is a diagram showing an example of a database stored in the graph analysis unit 120. This database has data items for multiple travel routes 1001 (route candidates).

The data item of the travel route 1001 has data subitems of a supply point 1002 as a starting point, one or more shelters 1003 via which relief supplies are to be supplied, travel distance 1004, and the amount of relief supplies to be supplied for each city 1005 (note that information on the city to which each shelter belongs can be obtained from a specified database.) Note that in each data subitem, 1 is set if the supply point or shelter is used or passed through, and 0 is set if it is not used or passed through.

<Optimal Route Creation Process>
Next, the optimum route creation process s20 will be described.
First, the optimal route creation processing unit 130 creates an Ising model based on the database created in the route candidate creation process s10, in order to find the optimal travel route (stopover) for each vehicle when leveling out the supply of relief materials in each city.

(About the Ising model)
Here, a classical algorithm by which the route search support device 100 obtains a ground state as a solution of the Ising model, and a configuration of the Ising model for realizing this will be described.

The route search support device 100 is configured such that N variables sj ^z (j=1, 2, . . . , N) are −1≦sj
An Ising model having a range of ^z ≦1 and a local field gj and an interaction between variables Jij (i, j=1, 2, . . . , N) is set.

Specifically, the route search support device 100 divides time into m parts and performs discrete calculations from t=t. (t.=0) to tm (tm=τ), and when determining the variable ^Sjz (tk) at each time tk, the value of the variable ^Sjz (tk-1) (i=1, 2, .., N) at the previous time tk-1 and the relaxation term coefficient 9pina or 9pinb are used to obtain ^Bjz (tk)={ΣiJijSiz ⁽ tk-1)+gj+sgn( ^sjz (tk-1))·9pina}·tk/τ or ^Bjz (tk)={ ^ΣiJiJSjz (tk-1)+gj+9pinb. ^Sjz (tk-1))·tk/τ is obtained, a function f is defined so that the value range of the above-mentioned variable ^Sjz (tk) is -1≦ ^sjz (tk)≦1, and ^Sjz (tk)=f( ^Bjz (tk),tk) is set. As the time step progresses from t=t0 to t=tm, the above-mentioned variable ^Sjz approaches -1 or 1, and finally, if ^sjz <0, ^Sjzd =-1, and if ^Sjz >0, ^Sjzd =1 are set to determine the solution.

The coefficient gpinb is, for example, a value between 50% and 200% of the average value of |Jij|. In addition, for the local field gj in the problem setting, a correction term δgj' can be added to gj' only for a certain site j', and the magnitude of gj' can be increased only for that site j'. In addition, the correction term δgj' is, for example, a value between 10% and 100% of the average value of |Jij|.

Next, we will explain the basic principles of annealing realized by the route search support device 100, starting from a quantum mechanical description and moving to a classical form.

The problem of searching for the ground state of the Ising spin Hamiltonian given by equation (3) includes a classification of problems called NP-hard, and is known to be a useful problem (reference: F. Barahona, "On the computational complexity of Isingspin glass models," J. Phys. A: Math. Gen. 15, 3241 (1982)).

[Formula 3]

Jij and gj are the problem setting parameters, and σ^ ^Z is the z component of the Pauli spin matrix, which has an eigenvalue of ±1. i and j represent the spin site. An Ising spin is a variable that can only take on a value of ±1, and in equation (3), the eigenvalue of σ^ ^z is ±1, making it an Ising spin system.

The Ising spin in equation (3) does not have to be a literal spin; it can be anything physically as long as the Hamiltonian is described by equation (3).

For example, it is possible to associate the use or non-use of each base point for each vehicle (described later) with ±1, to associate the high and low of a logic circuit with ±1, to associate the vertical and horizontal polarization of light with ±1, and to associate the phase of 0, π with ±1.

In the method exemplified here, similar to adiabatic quantum computing, a computational system is prepared in the ground state of the Hamiltonian given by equation (4) at time t = 0.

[Formula 4]

γ is a proportionality constant determined by the magnitude of the external field applied uniformly to all sites j, and σ^j ^x is the x component of the Pauli spin matrix. If the calculation system is the spin itself, the external field means a magnetic field.

Equation (4) corresponds to the application of a transverse magnetic field, and the ground state is when all spins point in the x direction (γ>0). The Hamiltonian in the problem formulation was defined as an Ising spin system with only the z component, but equation (4) includes the x component of spin. Therefore, the spin in the calculation process is not Ising but vectorial (Bloch vector). At t=0, we start with the Hamiltonian in equation (4), but as time t progresses, the Hamiltonian is gradually changed, and finally the Hamiltonian described by equation (3) is obtained, with the ground state being the solution.

[Formula 5]

Here, σ^ represents the three components of the Pauli spin matrix as a vector. The ground state is when the spin is oriented in the magnetic field direction, and can be written as <σ^> = B/|B|, with <·> being the quantum mechanical expectation value. In an adiabatic process, the ground state is always maintained, so the spin direction always follows the direction of the magnetic field.

The above discussion can be extended to multi-spin systems. At t=0, the Hamiltonian is given by equation (4). This means that a magnetic field ^BjX = γ is applied uniformly to all spins. At t>0, the x component of the magnetic field gradually weakens to ^BjX = γ(1-t/τ). As for the z component, the effective magnetic field is given by equation (6) due to the interaction between spins.

[Formula 6]

Since the spin direction can be defined by <σ^ ^z >/<σ^ ^x >, if the spin direction follows the effective magnetic field, the spin direction is determined by equation (7).

[Formula 7]

Although equation (7) is a quantum mechanical description, it takes the expectation value and is therefore a relational equation relating to classical quantities, unlike equations (1) to (6).

In classical systems, there is no nonlocal correlation (quantum stitching) in quantum mechanics, so the spin direction should be completely determined by the local field at each site, and equation (7) determines the behavior of the classical spin system. In quantum systems, equation (7) is transformed due to the existence of nonlocal correlation, but this will be discussed later. Here, we will describe the classical system defined by equation (7) to explain the basic form of the invention.

Figure 11 shows a timing chart for obtaining the ground state of the spin system. Since the description in this figure is related to classical quantities, the spin of site j is expressed by sj rather than σ^j. Accordingly, the effective magnetic field Bj in this figure is a classical quantity. At t = 0, a rightward effective magnetic field Bj is applied to all sites, and all spins Sj are initialized to the right.

As time t passes, the magnetic field in the z-axis direction and the spin-spin interaction are gradually added, and finally the spins are in the +z or -z direction, and the z component of the spin Sj becomes sj ^z = +1 or -1. Ideally, time t is continuous, but in the actual calculation process, it can be made discrete to improve convenience. The discrete case is described below.

The spin shown here is a vectorial spin because it includes not only the z component but also the x component. Its vectorial behavior can also be understood from Figure 11. The y component has not appeared so far, but this is because the external field direction is taken to be on the xz plane, so there is no y component of the external field, and therefore <σ^ ^Y > = 0.

The spin of the computational system is assumed to be a three-dimensional vector of magnitude 1 (called a Bloch vector, which can describe the state as a point on a sphere), but the axis selection in the example shown in Figure 11 requires that only two dimensions be considered (the state can be described as a point on a circle).

Furthermore, since γ is constant, Bj ^x (t)>0 (γ>0) or Bj ^x (t)<0 (γ<0) holds. In this case, the two-dimensional spin vector can be described using only a semicircle, and if Sj ^z is specified as [-1, 1], the two-dimensional spin vector is determined by the single variable Sj ^z . Therefore, although the spin is a two-dimensional vector in this example, it can also be expressed as a one-dimensional continuous variable with a range of [-1, 1].

In the timing chart of Figure 11, the effective magnetic field is calculated for each site at time t = tk, and the spin direction at t = tk is calculated using this value according to equation (8).

[Formula 8]

Equation (8) is equation (7) rewritten in terms of classical quantities, so there is no symbol <>. Next, the effective magnetic field at t = tk + l is calculated using the value of the spin at t = tk. The effective magnetic field at each time can be written specifically as equations (9) and (10).

[Formula 9]

[Formula 10]

Thereafter, the spin and the effective magnetic field are alternately determined according to the procedure diagrammatically shown in the timing chart of FIG.

In the classical system, the magnitude of the spin vector is 1. In this case, each component of the spin vector is described as ^Sjz (tk) = sin θ and Sjx(tk) = cos θ, using the parameter θ defined as tan θ = ^Bjz (tk)/ ^Bjx (tk) ^.

Rewriting this, Sj ^z (tk)=sin(arctan(Bj ^z (tk)/Bj ^x (tk))), and Sj ^x (tk)=cos(arctan(Bj ^z (tk)/Bj ^x (tk))).

As is clear from equation (9), the only variable of ^Bjx (tk) is tk, and τ and γ are constants. Therefore, ^Sjz (tk)=sin(arctan( ^Bjz (tk)/ ^Bjx (tk))) and Sjx(tk)=cos(arctan( ^Bjz (tk)/ ^Bjx (tk))) can also be generalized as functions with ^Bjz (tk) and tk as variables, such as ^Sjz (tk)=f1( ^Bjz (tk),tk) and ^Sjx (tk)=f2( ^Bjz (tk),tk).

Since the spin is described as a two-dimensional vector, two components Sj ^z (tk) and sj ^x (tk) appear, but if Bj ^z (tk) is determined based on equation (10), Sj ^x (tK) is not necessary.

This corresponds to the fact that the spin state can be described only by Sj ^z (tk) whose range is [-1, 1]. The final solution Sj ^zd must be Sj ^zd = -1 or 1. If Sj ^z (τ) > 0, then Sj ^zd = 1, and if Sj ^z (τ) < 0, then Sj ^zd = -1.

FIG. 12 shows a flow chart summarizing the solution algorithm in the Ising model described above. Here, tm=τ. Each step s1 to s9 in the flow chart corresponds to a process at a certain time in the timing chart of FIG. 11 from time t=0 to t=τ. That is, steps s2, s4, and s6 in the flow chart correspond to the above equations (9) and (10) at t=t1, tk+l, and tm, respectively. The final solution is determined in step s8 by setting ^Sjzd =-1 if ^sjz <0, and ^Sjzd =1 if ^Sjz >0 (s9).

So far, we have shown how to solve the Ising model, which is a specific problem, when it is expressed by equation (3). Next, we will explain, using a specific example, how the Ising model is expressed by equation (3) including the local field gj and the interaction between variables Jij (i, j = 1, 2, ..., N).

For example, the Ising model sets the spins of whether each vehicle uses each passing point, and the sensitivity between variables in the constraint function as the strength of the interaction between the spins, for an objective function that includes as terms an evaluation function for the vehicle's route and a constraint function that is minimized when certain constraint conditions are satisfied.

In this case, the local field gj is assumed to be set as the degree of influence that the variables in, for example, the evaluation value of the evaluation function and the constraint function that is minimized when a certain constraint is satisfied have on the objective function.

Through the above considerations, we specifically set the variable interactions Jij and local fields gj (between each term of the objective function described above), and identify the route for each vehicle through a search for the ground state of the Ising model represented by equation (3), i.e., a search for the ground state that minimizes the objective function described above.

The only calculation performed by the Ising model and the annealing method is to "minimize the objective function." Therefore, if there are constraints that must be satisfied when minimizing the objective function, they must be added to the objective function in some way.

for example,
[Formula 11]

If we convert this constraint into a function that is minimized when the constraint is satisfied, we get the following formula:

[Formula 12]

Since the squared part is always a positive value, this formula will only reach its minimum value when the squared part is 0. The only time the squared part is 0 is when ΣXi-A=0, so if you solve the optimization problem that minimizes this function, you will automatically obtain a solution that satisfies ΣXi=A.

For example, in the annealing method mentioned above, the items you want to use as constraints must also be included in the objective function, so the objective function and constraints are treated with the same importance.

For example, suppose we have the following optimization problem:

[Formula 13]

If we change this to a formulation for annealing, we get the following:

[Formula 14]

Here, P and Q are constants that determine which term is given priority for minimization. For example, if you want to minimize all three terms equally (i.e., solve the problem without biasing the strength of the constraints), you can set values to balance the terms, such as making P and Q equal.

On the other hand, if the problem is posed such that "the constraint in the third term is not as important as the constraint in the third term," then the desired solution can be obtained by making the value of P, which is the coefficient of the term that is important, greater than the value of Q.

In this way, the annealing method allows constraint conditions to be prioritized, and constraint conditions that are not given much importance can be set to be "satisfied as much as possible." Note that various settings related to the Ising model are appropriately made in accordance with existing general concepts according to the various conditions and information of this embodiment.

Based on the above, we will explain the Ising model created by the route search support device 100 of this embodiment.

First, the optimization problem that the route search support device 100 should solve in the optimal route creation process s20 is a problem of optimizing the travel route (stopover) of each vehicle to level out the sufficiency rate _Yc of relief materials in city c. This optimization problem is generally expressed using the following objective function formula (15) and constraint conditions formulas (16) and (17) (Takahashi Yoshiho, Masaki Akiko, Aratani Taro, Mashima Takahiro, and Kono Kazuo, "Effectiveness of Pseudo Quantum Computers for Delivery Planning in Disasters,"
(2022 Autumn Conference of the Operations Research Society of Japan, 1-E-7).

[Formula 15]

[Formula 16]

[Formula 17]

Here, the fulfillment rate ^Yc in formula (15) is expressed by the following formula (18).

[Formula 18]

In the above equations, N _city is the number of municipalities, M is the set of municipalities, W ^c _supplied is the amount of relief materials already supplied in city c, W ^c _demand is the demand (required amount) of relief materials in city c, W ^c _j is the supply of relief materials in city c along route candidate j from the departure point to the destination point, x _j is a binary value indicating route candidate j (specifically, a binary value indicating adoption (1) or non-adoption (0)), D j is the travel distance between bases along route candidate j, J is a set of route candidates, P _kj is supply depot k (starting point) along route candidate j, N ^k _truck is the number of vehicles at supply depot k, K is a set of vehicles, A _ij is shelter i that can be passed through along route candidate j, V is a set of shelters, α ₁ is a weighting value indicating the degree of importance placed on the ratio of the supply amount to the demand amount of relief materials (the degree to which the demand for relief materials should be met), and α ₂ is a weighting value indicating the degree of importance placed on shortening the travel distance of vehicles.

Note that N _city , M, W ^c _supplied , W ^c _demand , _J , ^{N k} _truck , _K , V, α ₁ , and α ₂ may be stored in advance by the route search support device 100, or values may be input from a _user .
Retrieve from the database created in 0.
Here, when the above optimization problem is converted into an Ising model, it becomes as shown in the following formula (19).

[Formula 19]

The first term on the right-hand side of equation (19) represents the bias in the ratio of the supply to the demand for relief supplies (sufficiency rate) between cities. When the Hamiltonian H is in the ground state (when the objective function is at its minimum), the value of this term is minimized, i.e., the bias is minimized.

The second term on the right-hand side of equation (19) represents the total shortage of relief supplies at evacuation centers. The value of this term is minimized when the Hamiltonian H is in the ground state.

The third term on the right-hand side of equation (19) represents the distance traveled by all vehicles. The value of this term is minimized when the Hamiltonian H is in the ground state.

The fourth term on the right-hand side of equation (19) is a constraint function that indicates the constraint on the number of vehicles to be deployed at the departure point (material collection point).

The fifth term on the right side of formula (19) is a constraint function indicating a restriction on the number of vehicles passing through each shelter i (only once in this embodiment). For this shelter i, shelters related to dummy nodes among unit nodes constituting the real node are not included, and only shelters indicated by unit nodes other than dummy nodes among unit nodes constituting the real node are included. In other words, each vehicle can pass through only shelters related to dummy nodes without any restrictions.

In equation (19), x _j which is a binary value indicating whether or not a path candidate j is used corresponds to a spin in the Ising model.

The optimal route creation processing unit 130 solves the above Ising model to identify the travel route of each vehicle (determines whether or not the route candidate j is used).
calculates the amount of relief supplies to be provided to each evacuation center and each city via each travel route.

As described above, the route search support device 100 of this embodiment sets (contracts) one or a combination of two or more adjacent unit nodes that satisfy a first condition among unit nodes that indicate intermediate stops that a vehicle can pass through while traveling from a departure point to a destination as a real node, searches for one or two or more adjacent real nodes that satisfy a second condition among the real nodes, sets (contracts) the searched real node as a dummy node, calculates a value indicating whether or not the intermediate stops indicated by the unit nodes are used when optimizing the value of the objective function including an evaluation function (smoothing function) related to the vehicle's travel route, and outputs information indicating whether or not each intermediate stop is used.

That is, the route search support device 100 of the present embodiment uses the objective function as follows:
Based on the first condition and the second condition, a contracted real node and a contracted dummy node in the real node are set. Then, the route search support device 100 calculates whether or not the vehicle will pass through each route point by using an objective function in which the number of times the vehicle passes through the route point indicated by the unit node other than the dummy node is set as a constraint condition.

In this way, the route search support device 100 of this embodiment narrows down the candidate intermediate points to be input to the objective variable for finding the optimal route for the vehicle in advance using real nodes that are contracted unit nodes, while setting constraints on the number of intermediate points that the moving object will pass only for unit nodes other than dummy nodes, thereby supporting efficient search for an appropriate route that passes through intermediate points that should be passed through even when the vehicle has multiple intermediate points.

Here, in this embodiment, the route search support device 100 sets, as a real node, a combination of unit nodes for which an evaluation value indicating the strength of the connection between the unit nodes is equal to or greater than a predetermined value with respect to the first condition.

This makes it possible to extract combinations of intermediate locations that a moving object is likely to need to pass through.

In addition, in this embodiment, the route search support device 100 sets, as a real node, a combination of unit nodes in which the travel time or distance between the unit nodes is equal to or greater than a predetermined value, in relation to the first condition.

This makes it possible to extract combinations of stopovers that can shorten a moving object's travel time.

Furthermore, in relation to the second condition, the route search support device 100 of this embodiment searches for a unit node that needs to be passed through in order to pass through a unit node other than the unit node that constitutes the real node from the unit node in the real node, and sets the searched unit node as a dummy node.

This allows the system to explicitly set intermediate points that the vehicle will likely need to pass through when searching for each travel route as nodes that can be passed through, enabling route searches to be performed that optimize each travel route.

In addition, in accordance with the second condition, the route search support device 100 of this embodiment searches for unit nodes in the real node whose evaluation value indicating the strength of the bond with other unit nodes is equal to or less than a predetermined value (e.g., a unit node that is far from other unit nodes), and sets the searched unit node as a dummy node.

This allows the system to explicitly set intermediate points that the vehicle will likely need to pass through when searching for each travel route as nodes that can be passed through, enabling route searches to be performed that optimize each travel route.

In addition, the route search support device 100 of this embodiment accepts a setting from the user on the setting screen 500 for an upper limit of connections between unit nodes in a real node that is a combination of two or more unit nodes (maximum real node length), and sets a combination of unit nodes in the real node that does not exceed the upper limit.

This increases the number of constituent nodes of a real node, prevents optimal route candidates from being overly limited, and allows the optimal route for a vehicle to be calculated more reliably.

In addition, the route search support device 100 of this embodiment accepts the setting of an upper limit on the number of dummy nodes from the user via the setting screen 500, and sets the dummy nodes so that the upper limit is not exceeded.

This prevents excessively complicated routes from being searched for, and allows the optimal route for the moving object to be calculated more reliably.

In addition, the route search support device 100 of this embodiment creates real nodes that satisfy constraint conditions that are commonly applied to each vehicle (e.g., the interruption of routes between certain intermediate points, the time periods during which an intermediate point can be entered), and sets further constraint conditions that differ depending on the vehicle (e.g., constraints on the number of vehicles at each departure point) in the objective function.

In this way, the constraint conditions that are common to all vehicles and have a high load are incorporated into the route candidate creation process s10 (processing related to real nodes), which has a relatively small processing load as the number of variables increases, while the constraint conditions that have different strengths depending on the moving body are incorporated into the optimal route creation process s20 (processing of objective functions), which has a large processing load as the number of variables increases. By allocating the constraint conditions in this way, the overall processing can be performed quickly.

In addition, the route search support device 100 of this embodiment calculates whether the vehicle will pass each intermediate point using an Ising model in which the spin is the use or non-use of the intermediate point indicated by the unit node and the sensitivity between variables in the constraint function is set as the strength of interaction between the spins, for a constraint function that is minimized when the constraint condition regarding the number of times the intermediate point indicated by the unit node other than the dummy node among the unit nodes constituting the real node is satisfied, and an objective function that includes an evaluation function regarding the vehicle's travel route as a term.

This allows for fast search for optimal routes with complex travel routes and intermediate stops.

In addition, the route search support device 100 of this embodiment accepts the designation of nodes that are candidates for unit nodes from the user via the setting screen 500.

This allows users to narrow down the routes used in route searches and perform route searches as needed.

In addition, the route search support device 100 of this embodiment accepts the setting of an upper limit on the number of variables in the objective function from the user via the setting screen 500, and sets the variables in the objective function so that the upper limit is not exceeded.

This allows users to perform route searches while balancing route search accuracy and route search processing speed.

The route search support system 1 of this embodiment also includes a user terminal 200 that accepts input of intermediate stops that the vehicle can take from the user and displays the results output by the optimization model on the screen.

This allows users to search for routes at any time and check the results.

The present invention is not limited to the above-described embodiment, and may be modified without departing from the spirit and scope of the present invention.
The present invention can be implemented using any components. The above-described embodiments and modifications are merely examples, and the present invention is not limited to these contents as long as the features of the invention are not impaired. In addition, although various embodiments and modifications have been described above, the present invention is not limited to these contents. Other aspects conceivable within the scope of the technical idea of the present invention are also included in the scope of the present invention.

For example, some of the hardware provided in each device of this embodiment may be provided in another device.

Furthermore, each program of each device may be provided in another device, a program may consist of multiple programs, or multiple programs may be integrated into a single program.

In addition, in this embodiment, the delivery of relief supplies by vehicle has been described as a target for solving the optimization problem, but the present invention can be applied to other general route search problems. For example, as an optimization problem in marine _{transportation} , an optimization model (Shinnosuke Wanaka, Kazuo _Hiekata ,
Yuji Horii, Evaluation of the Effect of GHG Emission Reduction in International Maritime Transport Using a Network Optimization Model, Journal of the Japan Society of Naval Architects and Ocean Engineers, 2020, Vol. 31, p. 205-212, https://doi.org/10.2534/jjasnaoe.31.205) can be applied. By applying the present invention to this optimization model, it is possible to process optimization problems that include more than 100 times the number of ports.

1 Route search support system, 100 Route search support device, 120 Graph analysis unit, 130
Optimal route creation processing unit, 140 Result output processing unit

Claims (13)

An apparatus for assisting in the creation of a route for each of a plurality of moving objects passing through one or a plurality of intermediate points, comprising:
a unit node creation process for creating unit nodes indicating route points that the moving body can take while moving from a departure point to a destination point;
a real node setting process for setting one unit node or a combination of two or more adjacent unit nodes that satisfy a first condition as a real node among the unit nodes;
a dummy node setting process for searching for one unit node or a combination of two or more adjacent unit nodes that satisfy a second condition among the unit nodes constituting the real node, and setting the searched unit node as a dummy node;
an optimal route creation process for calculating a value indicating whether or not a route indicated by a unit node other than the dummy node among unit nodes constituting the real node is used when optimizing a value of an objective function including a predetermined evaluation function related to a moving route of a moving object, with the number of times of passing through a route indicated by the unit node being a constraint condition;
and a processing device that executes a result output process of outputting information indicating whether the moving object has passed through each of the route points based on the calculated value.
Route search assistance device. the processing device, in the real node setting process, sets, as the real node, a unit node having an evaluation value indicating a strength of a bond between unit nodes of the combination that satisfies the first condition and that is equal to or greater than a predetermined value.
The route search support device according to claim 1 . In the real node setting process, the processing device sets, as a real node, a unit node in which a travel time or a distance between unit nodes of the combination satisfies the first condition and is equal to or greater than a predetermined value.
The route search support device according to claim 2 . In the dummy node setting process, the processing device searches for one or two or more adjacent unit nodes that need to be passed through in order to pass through a unit node other than the unit node constituting the real node from the unit node constituting the real node in relation to the second condition, and sets the searched unit node as a dummy node.
The route search support device according to claim 1 . In the dummy node setting process, the processing device searches for a unit node in the real node having an evaluation value indicating a strength of a connection with other unit nodes that is equal to or less than a predetermined value with respect to the second condition, and sets the searched unit node as a dummy node.
The route search support device according to claim 1 . The processing device includes:
Executing a setting process for accepting from a user a setting of an upper limit of the number of connections between unit nodes in a real node formed by a combination of two or more unit nodes;
In the real node setting process, a combination of two or more adjacent unit nodes is set as a real node so as not to exceed the upper limit.
The route search support device according to claim 1 . The processing device includes:
Executing a setting process to receive a setting of an upper limit of the number of the dummy nodes from a user;
In the dummy node setting process, a dummy node is set so as not to exceed the upper limit.
The route search support device according to claim 1 . The processing device includes:
In the real node setting process, a real node is created that satisfies a predetermined constraint condition that is commonly applied to each of the mobile objects;
In the optimal route creation process, different constraint conditions are set in the objective function depending on the moving body.
The route search support device according to claim 1 . The processing device includes:
In the optimal path creation process, an Ising model is calculated for a constraint condition function that is minimized when a constraint condition related to the number of times a route through a route indicated by a unit node other than the dummy node among unit nodes constituting the real node is satisfied, and an objective function including an evaluation function related to a moving path of a moving body as a term, in which the presence or absence of use of the route indicated by the unit node is set as a spin, and a sensitivity between variables in the constraint condition function is set to a strength of interaction between the spins;
In the result output process, information indicating whether or not the moving object passed through each of the route points is output to an output device based on a result of the calculation.
The route search support device according to claim 1 . The route search support device according to claim 1, wherein the processing device executes a setting process to accept, from a user, a designation of a node that is a candidate for the unit node. The processing device includes:
Executing a setting process to receive from a user an upper limit setting of the number of variables of the objective function;
In the optimal route generation, variables of the objective function are set so as not to exceed the upper limit.
The route search support device according to claim 1 . A method for supporting creation of a route in which each of a plurality of moving objects moves via one or more waypoints, comprising:
An information processing device,
a unit node creation process for creating unit nodes indicating route points that the moving body can take while moving from a departure point to a destination point;
a real node setting process for setting one unit node or a combination of two or more adjacent unit nodes that satisfy a first condition as a real node among the unit nodes;
a dummy node setting process for searching for one unit node or a combination of two or more adjacent unit nodes that satisfy a second condition among the unit nodes constituting the real node, and setting the searched unit node as a dummy node;
an optimal route creation unit process for calculating a value indicating whether or not a route point indicated by a unit node other than the dummy node among unit nodes constituting the real node is used when optimizing a value of an objective function including a predetermined evaluation function related to a moving route of a moving object, with the number of times of passing through the route point indicated by the unit node being a constraint condition;
and executing a result output process of outputting information indicating whether the moving object has passed through each of the route points based on the calculated value.
A method for assisting with route finding. A route search support system that supports creation of a route for each of a plurality of moving objects to travel via one or a plurality of intermediate points,
a unit node creation process for creating unit nodes indicating route points that the moving body can take while moving from a departure point to a destination point;
a real node setting process for setting one unit node or a combination of two or more adjacent unit nodes that satisfy a first condition as a real node among the unit nodes;
a dummy node setting process for searching for one unit node or a combination of two or more adjacent unit nodes that satisfy a second condition among the unit nodes constituting the real node, and setting the searched unit node as a dummy node;
an optimal route creation process for calculating a value indicating whether or not a route indicated by a unit node other than the dummy node among unit nodes constituting the real node is used when optimizing a value of an objective function including a predetermined evaluation function related to a moving route of a moving object, with the number of times of passing through a route indicated by the unit node being a constraint condition;
a route creation assistance device including a processing device that executes a result output process of outputting information indicating whether or not the moving object has passed through each of the route points based on the calculated value; and
An input process of receiving an input of a route through which the mobile object can pass from a user;
and a display process for displaying the information output in the result output process on a screen.

Images