[go: up one dir, main page]

WO2024084628A1 - 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム - Google Patents

運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム Download PDF

Info

Publication number
WO2024084628A1
WO2024084628A1 PCT/JP2022/038949 JP2022038949W WO2024084628A1 WO 2024084628 A1 WO2024084628 A1 WO 2024084628A1 JP 2022038949 W JP2022038949 W JP 2022038949W WO 2024084628 A1 WO2024084628 A1 WO 2024084628A1
Authority
WO
WIPO (PCT)
Prior art keywords
qubo
constraint
coefficient
term
unit
Prior art date
Application number
PCT/JP2022/038949
Other languages
English (en)
French (fr)
Inventor
兼三 牧野
浩章 村上
敏裕 和田
健詞 上田
健人 内藤
Original Assignee
三菱電機株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 三菱電機株式会社 filed Critical 三菱電機株式会社
Priority to PCT/JP2022/038949 priority Critical patent/WO2024084628A1/ja
Publication of WO2024084628A1 publication Critical patent/WO2024084628A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G08—SIGNALLING
    • G08G—TRAFFIC CONTROL SYSTEMS
    • G08G1/00—Traffic control systems for road vehicles
    • G08G1/123—Traffic control systems for road vehicles indicating the position of vehicles, e.g. scheduled vehicles; Managing passenger vehicles circulating according to a fixed timetable, e.g. buses, trains, trams

Definitions

  • This disclosure relates to an operation planning device, an operation planning method, an operation planning program, and an operation management system.
  • Patent Document 1 proposes a system that estimates an optimal route for multiple moving bodies while avoiding collisions between the moving bodies.
  • time-series route candidates are generated for the shortest route and detour route (i.e., a route other than the shortest route to the destination), route allocation evaluation values of the time-series route candidates are calculated, travel distance evaluation values of the time-series route candidates are calculated, and route collision evaluation values of combinations of the time-series route candidates are calculated.
  • the time-series routes of the multiple moving bodies are estimated as optimal candidates.
  • JP 2020-46384 A (e.g., Abstract, Claim 1, Figure 1)
  • each mobile body selects the optimal route from among the shortest route and detour route candidates has the following problems.
  • any mobile body can head to that destination.
  • that mobile body can head to any destination.
  • the mobile body may be dispatched to a destination far from the starting point, and the overall travel cost of the multiple mobile bodies may not be minimized.
  • the present disclosure has been made to solve the problems described above, and aims to optimize the combination of operation candidates for multiple moving bodies so as to minimize the overall movement cost of the multiple moving bodies.
  • the operation planning device includes an operation candidate enumeration unit that, when given a departure point of each of a plurality of moving bodies and a plurality of requests indicating a destination, outputs operation candidate data indicating a route starting from the departure point and ending at the destination and a plurality of operation candidates that are travel schedules for the route, for a combination indicating which destination each of the plurality of moving bodies is heading for; an objective term setting unit that sets the travel cost required for the movement of each of the plurality of operation candidates to the QUBO coefficient of the objective term of the QUBO problem, which is a binary optimization problem without quadratic constraints; and a combination of operation candidates among the plurality of operation candidates that do not satisfy constraint conditions.
  • the system is characterized by comprising a constraint term setting unit that sets a constraint term that is a penalty term for the constraint term and sets a QUBO coefficient for the constraint term; a combining unit that generates a combined QUBO coefficient by weighting and combining the QUBO coefficient of the objective term and the QUBO coefficient of the constraint term; an annealing unit that performs an annealing process to calculate the QUBO problem represented by the combined QUBO coefficient one or more times using a simulated annealing method of quantum computing or classical computing to obtain one or more solutions; and a constraint verification unit that extracts feasible solutions that satisfy the constraint conditions from the one or more solutions obtained by the annealing process and selects an optimal solution from the feasible solutions.
  • the operation management system is characterized by comprising the operation planning device, a control unit that generates control information for operating the multiple mobile bodies using the optimal solution selected by the operation planning device as an operation plan, and a transmission unit that transmits the control information to the multiple mobile bodies.
  • FIG. 1 is a block diagram showing a configuration of an operation planning device according to a first embodiment.
  • 2 is a block diagram showing a configuration of a constraint term setting unit in FIG. 1 .
  • FIG. 13 is a diagram showing an example of matching between departure points of multiple mobile objects and destinations of multiple requests.
  • 4 is a flowchart showing an operation of the operation planning device according to the first embodiment.
  • FIG. 1 is a diagram showing an example of a map indicating an area in which a plurality of moving objects can move.
  • FIG. 1 is a diagram showing an example of candidate operations enumerated by a candidate operation enumeration unit in FIG. 1 .
  • FIG. 10 is a diagram showing another example of the candidate operations enumerated by the candidate operation enumeration unit of FIG. 1 .
  • FIG. 2 shows an example of operation candidate data enumerated by the operation candidate enumeration unit of FIG. 1 .
  • 10 shows another example of operation candidate data enumerated by the operation candidate enumeration unit of FIG. 1 .
  • 3A to 3D are diagrams illustrating a method of intersection determination performed by the intersection determination unit in FIG. 2.
  • 1 is a diagram illustrating an example of a hardware configuration of an operation planning device according to a first embodiment.
  • 4 is a diagram illustrating another example of a hardware configuration of the operation planning device according to the first embodiment.
  • FIG. FIG. 11 is a block diagram showing the configuration of a traffic management system according to a second embodiment.
  • FIG. 1 is a block diagram showing the configuration of an operation planning device 10 according to the first embodiment.
  • the operation planning device 10 is a device capable of implementing an operation planning method according to the first embodiment.
  • the operation planning device 10 is, for example, a computer that is an information processing device that executes an operation planning program according to the first embodiment.
  • FIG. 2 is a block diagram showing the configuration of the constraint term setting unit 13 in FIG. 1.
  • FIG. 3 is a diagram showing an example of matching between starting points A 1 to A 4 of multiple moving bodies c 1 to c 4 and destinations B 1 to B 4 of multiple requests r 1 to r 4 .
  • the operation planning device 10 has an operation candidate enumeration unit 11, an objective term setting unit 12, a constraint term setting unit 13, a combination unit 14, an annealing unit 15, and a constraint verification unit 16.
  • the operation planning device 10 may have a storage unit 17 as a storage device.
  • the storage unit 17 may be a storage device of an external device (e.g., a server on a network) that can communicate with the operation planning device 10.
  • the multiple moving bodies are, for example, vehicles that run along a passage.
  • the vehicles are, for example, autonomous vehicles or autonomous robots.
  • the vehicles may be driven by a person.
  • the passages are, for example, indoor passages, outdoor passages or roads, and passages within facilities such as theme parks, parks, factories, warehouses, etc.
  • the passages may be of a width such that two moving bodies cannot pass each other (or the moving body behind cannot overtake the moving body in front).
  • the operation planning device 10 has an operation candidate enumeration unit 11 that, when given starting points A1 to A4 (denoted as starting point information D0 in FIG. 1) of each of multiple moving bodies c1 to c4 and multiple requests r1 to r4 (denoted as D1 in FIG. 1) indicating destinations B1 to B4 , outputs multiple operation candidates (denoted as operation candidate data D2 in FIG. 1) including combination information indicating which of the multiple destinations B1 to B4 each of the multiple moving bodies c1 to c4 is heading for, and an objective term setting unit 12 that sets the travel cost required for the movement of each of the multiple operation candidates to a QUBO coefficient Q (o) (denoted as D3 in FIG.
  • the operation planning device 10 has a constraint term setting unit 13 that sets a constraint term, which is a penalty term, for a combination of operation candidates among a plurality of operation candidates that does not satisfy a constraint condition (i.e., a constraint condition of the optimization problem to be solved), and sets a QUBO coefficient Q ( k) of the constraint term (denoted as D4 in FIG. 1), and a combination unit 14 that generates a combined QUBO coefficient Q(l) (denoted as D5 in FIG.
  • a constraint term which is a penalty term
  • the operation planning device 10 has an annealing unit 15 that performs an annealing process to calculate the QUBO problem represented by the combined QUBO coefficient Q (l) one or more times by a simulated annealing method of quantum computing or classical computing (e.g., quantum annealing or simulated annealing) to obtain one or more solutions (denoted as D6 in FIG. 1), and a constraint verification unit 16 that extracts one or more feasible solutions that satisfy the constraint conditions from the one or more solutions obtained by the annealing process and selects an optimal solution (denoted as D7 in FIG. 1) from the one or more feasible solutions.
  • a simulated annealing method of quantum computing or classical computing e.g., quantum annealing or simulated annealing
  • the operation candidate enumeration unit 11 acquires, for example, from the storage unit 17, a map showing the range in which the moving body can move, information showing the travel cost required for travel between each point on the map, and information showing at which point the moving body can wait (i.e., information showing the position where the moving body can stop and wait).
  • the operation candidate enumeration unit 11 also receives as input departure point information D0 showing departure points A1 to A4 of the multiple moving bodies c1 to c4 and destination information D1 showing destinations B1 to B4 of the multiple requests r1 to r4 . As shown in FIG.
  • the operation candidate enumeration unit 11 performs an operation candidate enumeration process to enumerate operation candidates for all combinations of which moving body among the multiple moving bodies c1 to c4 heads to which destination (i.e., which of the destinations B1 to B4 ).
  • the operation candidate enumeration unit 11 outputs the enumerated operation candidates as operation candidate data D2. That is, the operation candidate enumeration unit 11 outputs operation candidate data including departure times and arrival times of the moving bodies passing through predetermined points on a plurality of routes having starting points A1 to A4 of the moving bodies c1 to c4 as starting points and having multiple destinations B1 to B4 as end points.
  • a specific example of the operation candidate enumeration process will be described later with reference to Figs. 5 to 11.
  • a specific example of the operation candidate data D2 will be described later with reference to Fig. 12.
  • the objective term setting unit 12 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, performs an objective term setting process to set the movement cost of each operation candidate to a coefficient of a QUBO problem, which is a quadratic unconstrained binary optimization problem, and outputs the coefficient Q (o) (D3 in FIG. 1) of the QUBO problem of the objective term.
  • the coefficient of the QUBO problem is also called a "QUBO coefficient".
  • the QUBO coefficient can be expressed as a matrix (or, in a broader sense, a vector).
  • the movement cost is determined based on, for example, one or a combination of two or more of the following: the movement distance of the moving object, the movement time of the moving object, the cost required for the movement, and the arrival waiting time required for the moving object to arrive at the destination from the generation of a request.
  • the details of the objective term setting process will be described later.
  • the constraint term setting unit 13 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, performs a constraint term setting process to set the QUBO coefficient Q (k) of the constraint term set as a penalty term in the QUBO problem for a combination of operation candidates that does not satisfy the constraint conditions (Constraints), and outputs the QUBO coefficient Q (k) (D4 in FIG. 1) which is the coefficient of the QUBO problem of the constraint term. Details of the constraint term setting process will be described later.
  • the QUBO coefficient Q (k) of the constraint term is expressed as a matrix consisting of a plurality of QUBO coefficients according to the number of conditions of the constraint conditions.
  • the constraint term setting unit 13 has an intersection determination unit 130, a first constraint term setting unit 131, a second constraint term setting unit 132, and a third constraint term setting unit 133.
  • the intersection determination unit 130 receives as input the operation candidate data D2 output from the operation candidate enumeration unit 11, performs an intersection determination process for a combination of two operation candidates to determine whether or not a collision will occur when two moving bodies move according to the operation candidate of the combination, and outputs the intersection determination result. Details of the intersection determination process of the intersection determination unit 130 will be described later with reference to Figures 12 (A) to (D).
  • collision means that the operations (timetables) on which two moving bodies are moving cross each other, that is, the occurrence of a situation in which the two moving bodies may collide on the same passage.
  • collision includes not only two moving bodies actually colliding with each other, but also two moving bodies passing each other on the same passage and one moving body overtaking the other moving body.
  • the first constraint term setting unit 131 selects a pair of two operation candidates that will cause a collision based on the result of the intersection determination output from the intersection determination unit 130, it performs a first constraint term setting process to set a first constraint term of the QUBO problem so that a collision cost is added, and outputs a QUBO coefficient Q (1) of the first constraint term.
  • the details of the first constraint term setting process will be described later.
  • the second constraint term setting unit 132 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, performs a second constraint term setting process to set a second constraint term of the QUBO problem using a constraint that the number of operation candidates selected by one moving body is 0 or 1 as a penalty term, and outputs a QUBO coefficient Q (2) of the second constraint term.
  • the details of the second constraint term setting process will be described later.
  • the third constraint term setting unit 133 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, performs a third constraint term setting process to set a third constraint term of the QUBO problem with a penalty term being a constraint that the number of moving objects heading toward the destination of one request is one or less, and outputs a QUBO coefficient Q (3) of the third constraint term.
  • the details of the third constraint term setting process will be described later.
  • the constraint term setting unit 13 outputs the QUBO coefficient Q (1) of the first constraint term, the QUBO coefficient Q (2) of the second constraint term, and the QUBO coefficient Q (3) of the third constraint term as the QUBO coefficients Q (k) of the constraint terms.
  • the combining unit 14 performs a combining process of combining (for example, linearly combining) the QUBO coefficient Q (o) of the objective term set by the objective term setting unit 12 and the QUBO coefficient Q (k) of the constraint term set by the constraint term setting unit 13 using one or more combining coefficients.
  • the combining unit 14 outputs a combined QUBO coefficient Q (l) (D5 in FIG. 1) which is the combined QUBO coefficient. The details of the combining process will be described later.
  • the annealing unit 15 receives the combined QUBO coefficient Q (l) as an input, performs an annealing process to calculate the QUBO problem represented by the combined QUBO coefficient Q (l) one or more times by the simulated annealing method of quantum computing or classical computing, and outputs one or more sample solutions (D6 in FIG. 1).
  • the simulated annealing method used may be either the simulated annealing method by quantum computing or the simulated annealing method by classical computing.
  • the solution is a sequence of values of the decision variables in the QUBO problem, and corresponds to a combination of operation candidates.
  • the annealing unit 15 since the simulated annealing method obtains a solution of one sample per calculation, if the number of calculations is N (N is an integer equal to or greater than 1), the annealing unit 15 outputs solutions of N samples, which is the same number as the number of calculations. In addition, since the annealing unit 15 may use a probabilistic approximation solution method, the solution output from the annealing unit 15 does not need to be a globally optimal solution of the problem setting.
  • the constraint verification unit 16 performs a constraint verification process to extract solutions (hereinafter referred to as "feasible solutions”) that satisfy the constraint conditions from the one or more sample solutions output from the annealing unit 15 by removing solutions that do not satisfy the constraint conditions, and to select an optimal solution (D7 in FIG. 1) from among the feasible solutions. Details of the constraint verification process will be described later.
  • Fig. 4 is a flowchart showing the operation of the operation planning device 10.
  • the operation candidate enumeration unit 11 executes an operation candidate enumeration process to enumerate operation candidates based on the departure points and destinations of each of the multiple mobile bodies (step ST1).
  • the objective term setting unit 12 executes an objective term setting process for setting the travel cost of each of the listed operation candidates to the QUBO coefficient Q (o) of the objective term (step ST2).
  • the constraint term setting unit 13 executes a constraint term setting process for setting the constraint condition to the QUBO coefficient Q (k) of the constraint term (step ST3).
  • the combining unit 14 executes a process of combining the QUBO coefficient Q (o) of the objective term with all the QUBO coefficients Q (k) of the constraint terms to output a combined QUBO coefficient Q (l) (step ST4).
  • the annealing unit 15 executes an annealing process in which the QUBO problem represented by the combined QUBO coefficient Q (l) is calculated one or more times by the simulated annealing method (step ST5).
  • the constraint verification unit 16 extracts feasible solutions that satisfy the constraint conditions from one or more solutions calculated by the annealing unit 15, and executes a constraint verification process to select an optimal solution from among the feasible solutions (step ST6).
  • FIG. 5 is a diagram showing an example of a map showing the ranges in which multiple moving bodies c 1 and c 2 can move.
  • the operation candidate enumeration unit 11 can obtain a map (i.e., map data) showing the range within which a mobile object can move, and information showing the travel cost required to move between each point on the map.
  • the map can be represented using a graph of graph theory (hereinafter simply referred to as a "graph").
  • points (i.e., positions) on the map are represented by the vertices of the graph (vertices numbered 0 to 8 in FIG. 5), and paths between each point through which a mobile object can pass are represented by the edges of the graph.
  • Information required to calculate the travel cost, such as the distance of the path is set as an attribute of the edges of the graph.
  • Information on whether or not a mobile object can wait on the map is set as an attribute of the vertices of the graph.
  • the operation candidate enumeration unit 11 receives the departure points (i.e., departure point information) of multiple moving objects and the destination points (i.e., destination information) of multiple requests as input, and searches for a route that starts from the departure point (e.g., A1 to A4 ) of the moving object and ends at the destination point (e.g., B1 to B4 ) of the request for each combination of moving object c (e.g., c1 to c4 ) and request r (e.g., r1 to r4 ) as shown in FIG. 3, using Dijkstra's algorithm or the like (this process is also called "route search step").
  • this process is also called "route search step"
  • the operation candidate enumeration unit 11 If the operation candidate enumeration unit 11 does not find a route, it checks the route for the next combination of moving object c and request r. If a route is found, the operation candidate enumeration unit 11 calculates a schedule for moving along the route, and adds information consisting of the operation route and the movement schedule to the operation candidates (this process is also called "operation candidate enumeration step"). Then, the operation candidate enumeration unit 11 repeats the route search step and the operation candidate enumeration step for other routes, other requests, and other moving bodies in the same manner, and enumerates operation candidates.
  • FIG. 3 shows an example of a combination in which four mobile entities c 1 to c 4 correspond to four requests r 1 to r 4 , but the number of mobile entities and the number of requests are not limited to four.
  • the operation of the operation candidate enumeration unit 11 will be explained using a specific example of an operation planning problem.
  • a graph representing a map a graph having nine vertices from vertex 0 to vertex 8, with the distance of each edge being "1", as shown in Figure 5, will be used.
  • vertex 4 is a point where a mobile object can wait to avoid a collision.
  • the mobile bodies c1 and c2 move on each edge at a speed of "1", and the travel time on each edge is "1".
  • the maximum waiting time allowed for each mobile body is set as "1”
  • the waiting time per waiting is set as "1".
  • route search step in addition to searching for the shortest route from the starting point of the mobile body to the destination of the request, other possible detour routes may also be searched for.
  • the operation candidate enumeration unit 11 may search for routes in ascending order of travel cost for each combination of the departure point of each of the multiple mobile bodies and the multiple destinations for which there are requests, and enumerate the operation candidates by limiting them to routes for which the difference between the travel cost and the minimum travel cost is equal to or less than a predetermined upper limit.
  • the operation candidate enumeration unit 11 may omit the operation candidate enumeration step for that combination of the mobile object and the request.
  • the operation candidate enumeration unit 11 calculates the departure time and arrival time of each point on the route from the map information and the information of the moving object, and compiles one operation candidate in a format that summarizes the departure time and arrival time of each point as shown in Figure 10 (i.e., creates operation candidate data).
  • This operation candidate is denoted as M1,1,1 .
  • the first subscript is the number of the mobile unit
  • the second subscript is the number of the destination
  • the third subscript is a number indicating the number of the mobile unit represented by the first subscript among multiple operation candidates toward the destination of the request indicated by the second subscript.
  • the operation candidate enumeration unit 11 may refer to the attributes set at the vertices of the graph to check possible waiting points on the route, and enumerate operation candidates that wait at the possible waiting points on the route.
  • the operation candidate enumeration unit 11 may enumerate operation candidates that wait at the possible waiting points as multiple operation candidates.
  • vertex 4 on path p111 is a vertex where waiting is possible.
  • This operation candidate is denoted as M1,1,2 .
  • the operation candidate data of operation candidate M1,1,2 is shown in the M1,1,2 column in FIG. 10.
  • the operation candidate enumeration unit 11 repeats the route search step and operation candidate enumeration step for other routes in the same way, and enumerates operation candidates. Then, for other requests and other moving bodies, it repeats the route search step and operation candidate enumeration step in the same way, and enumerates all operation candidates.
  • the operation candidate enumeration unit 11 may not enumerate all possible operation candidates for each combination of the departure point of the moving body and the destination of the request, but may enumerate a limited number of operation candidates in ascending order of travel cost so that the number of combinations is within a predetermined upper limit.
  • Route p121 [1,2,5] does not have a vertex on the route where waiting is possible, so the only operation candidate that passes through this route is operation candidate M1,2,1 (shown in the M1,2,1 column in FIG. 10).
  • Route p122 [1,4,5] has a vertex 4 on the route where waiting is possible, so there are two operation candidates that pass through route p122 : operation candidate M1,2,2 with zero waiting times, and operation candidate M1,2,3 with one waiting time (shown in the M1,2,2 column and M1,2,3 column in FIG. 10, respectively).
  • the objective term setting unit 12 receives as input the operation candidate data D2 output from the operation candidate enumeration unit 11, calculates the movement cost of each operation candidate, and sets the QUBO coefficient Q (o) of the objective term of the QUBO problem.
  • the decision variables xc ,r,m and xc ',r',m ' are variables that take on the binary values of 0 or 1.
  • the decision variables xc ,r,m are 1 when the mth operation candidate is selected from among multiple operation candidates heading from the departure point of the mobile body c to the destination of the corresponding request r, and are 0 otherwise.
  • the decision variables xc ',r',m ' are 1 when the m'th operation candidate is selected from among multiple operation candidates heading from the departure point of the mobile body c' to the destination of the corresponding request r, and are 0 otherwise.
  • the index function i(c,r,m) is a function that returns the numbers (hereinafter referred to as "index") of the decision variables xc ,r,m when all decision variables are assigned numbers starting from 1.
  • the index function i(c',r',m') is a function that returns the indexes that are the numbers of the decision variables xc ',r',m' when all decision variables are assigned numbers starting from 1.
  • the QUBO coefficient Q (o) of the objective term can be expressed as a real matrix.
  • the QUBO coefficient Q (o) of the objective term may also be expressed as an array as a vector that generalizes a matrix.
  • the objective setting unit 12 determines a physical quantity related to the movement cost according to the purpose of optimization.
  • the physical quantity may be, for example, the movement distance of a moving object, the movement time of a moving object, the cost required for the moving object to move, the waiting time required from the occurrence of a request until the moving object arrives at the destination, or a combination of two or more of these.
  • the objective term setting unit 12 sets the movement cost to the QUBO coefficient Q(o ) of the objective term using the physical quantity ⁇ c ,r,m related to the movement cost and the weight function f as shown in formula (2).
  • the weight function f is selected from any one of a linear function, a step function, a normalized linear function, a quadratic function, and a downward convex function.
  • the operation candidate enumeration unit 11 sets the distance value between points in advance as the attribute of the edge of the graph representing the map, and the objective term setting unit 12 adds up the distance values of the edges along the route indicated by the operation candidates.
  • the objective setting unit 12 can calculate the time difference (i.e., the time difference) between the arrival time at the destination and the departure time from the departure point indicated by each operation candidate.
  • the operation candidate enumeration unit 11 sets the cost between points in advance as an attribute of the edge of the graph representing the map, and the objective term setting unit 12 adds up the cost of traveling along the edge along the route indicated by the operation candidate.
  • the objective setting unit 12 can calculate the difference in time between the arrival time at the destination indicated by the operation candidate and the time when the request was generated.
  • the function form of the weighting function f may be selected from among a step function, a normalized linear function, a quadratic function, and a downward convex function, depending on the user's requirements.
  • An example of a user request is minimizing the total travel time of moving objects, and if the weights of the travel times ⁇ (travel costs per hour) are equal, the objective term setting unit 12 can select a linear function such as that shown in equation (3) as the weight function f.
  • the objective term setting unit 12 may select a normalized linear function as shown in formula (5) as the weighting function f.
  • the objective term setting unit 12 can select a quadratic function or a higher-order downward convex function as the weighting function f.
  • the objective term setting unit 12 may select, as the weighting function f, a downward convex function in which ⁇ is a minimum at the specified time ⁇ 0.
  • the objective term setting unit 12 sets the QUBO coefficient Q (o) of the objective term.
  • the constraint term setting unit 13 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, and sets a constraint term that is a penalty term in the QUBO problem for a combination of operation candidates that does not satisfy the constraint conditions using the penalty function method, and sets the QUBO coefficient Q (k) of the constraint term.
  • the constraint term setting unit 13 sets the QUBO coefficient Q(k) of the constraint term so that a penalty is added when a combination of operation candidates that does not satisfy the constraint conditions is selected for the first to third constraint conditions, which are the following three constraint conditions.
  • the first constraint condition is "Do not select a combination of operation candidates in which moving objects collide with each other.”
  • the QUBO coefficient Q (1) of the first constraint term corresponding to this first constraint condition is set by the first constraint term setting process of the first constraint term setting unit 131, which is performed based on the intersection determination result of the intersection determination process of the intersection determination unit 130.
  • the second constraint condition is "the number of operation candidates selected by one moving body is 0 or 1."
  • the QUBO coefficient Q (2) of the second constraint term corresponding to this second constraint condition is set by the second constraint term setting process of the second constraint term setting unit 132.
  • the third constraint condition is "the number of moving objects heading toward the destination of one request is one or less.”
  • the QUBO coefficient Q (3) of the third constraint term corresponding to this third constraint condition is set by the third constraint term setting process of the third constraint term setting unit 133.
  • the constraint term setting unit 13 performs an intersection determination process in the intersection determination unit 130, a first constraint term setting process in the first constraint term setting unit 131, a second constraint term setting process in the second constraint term setting unit 132, and a third constraint term setting process in the third constraint term setting unit 133, and outputs the QUBO coefficient Q (1) of the first constraint term, the QUBO coefficient Q (2) of the second constraint term, and the QUBO coefficient Q (3) of the third constraint term together as the QUBO coefficient Q (k) of the constraint term.
  • the intersection determination unit 130 receives the operation candidate data D2 output from the operation candidate enumeration unit 11 as an input, and determines whether or not two moving bodies collide when moving on each of two different operation candidates (i.e., whether or not a situation that may cause a collision occurs) for each of two different operation candidates.
  • the two operation candidates to be subjected to the intersection determination are denoted as M c,r,m and M c',r',m' .
  • the intersection determination unit 130 first extracts graph edges common to the two routes (hereinafter referred to as "common edges") and performs intersection determination for each common edge to determine whether the two routes indicated by the two target operation candidates Mc,r,m and Mc ',r',m' share the same section.
  • side e is the same section.
  • Point u and point v are the first point and the second point at both ends of the same section, respectively.
  • Tu1 is the time when the first moving body c arrives at or departs from point u (vertex) u
  • Tu2 is the time when the second moving body c' arrives at or departs from point u.
  • Tv1 is the time when the first moving body c arrives at or departs from point v
  • Tv2 is the time when the second moving body c' arrives at or departs from point v.
  • the intersection determination unit 130 determines that there is a "collision" between the first moving body c and the second moving body c' (i.e., there is an "intersection” or there is a "possibility of collision"), and sets the intersection determination result Xe ( Mc,r,m ,Mc' ,r',m' ) of the common edge e to 1 or a non-zero value.
  • Figure 12(A) is a diagram of when two opposing moving bodies c, c' collide from the front (i.e., a head-on collision)
  • Figure 12(B) is a diagram of when the faster moving body c' collides with the slower moving body c from behind (i.e., a rear-end collision).
  • the first time difference (Tu1-Tu2) and the second time difference (Tv1-Tv2) have opposite signs, and the diagrams representing the two operations intersect. Also, if there is a collision at the vertex at the end of a common side, at least one of the first time difference (Tu1-Tu2) and the second time difference (Tv1-Tv2) is 0, and in that case too, the diagrams representing the two operations intersect.
  • the intersection determination unit 130 calculates the intersection determination result X( Mc,r,m,Mc',r',m') of the two operation candidates Mc,r,m and Mc ',r',m' by adding up the intersection determination results on the shared sides as shown in formula (7).
  • the intersection determination unit 130 may set the intersection determination result X( Mc,r,m ,Mc' ,r',m' ) to 1 or a nonzero value if Xe (Mc ,r , m, Mc',r',m' ) is nonzero on at least one common side e, and may set it to 0 otherwise.
  • E(M c,r,m , M c',r',m' ) represents a set of edges common to two routes indicated by two candidate operations M c,r,m and M c',r',m' .
  • the first constraint term setting unit 131 receives the intersection determination result of the intersection determination unit 130 as an input, and sets the QUBO coefficient Q (1) of the first constraint term so that the first constraint term has the form of equation (8) using the result as a collision cost.
  • each element takes a binary value of 0 or 1, corresponding to the decision variable x.
  • the first constraint term setting unit 131 may omit the intersection determination process of the intersection determination unit 130 and set the QUBO coefficient Q (1) of the first constraint term as shown in the following formula (9).
  • the first constraint term setting unit 131 may set the QUBO coefficient Q (1) of the first constraint term as shown in the following equation (10).
  • the second constraint term setting unit 132 introduces a slack variable s c , which is an auxiliary decision variable, for each moving body c, and sets the QUBO coefficient Q (2) of the second constraint term so that the second constraint term takes the form of equation (11).
  • the slack variable s c is a binary variable that is 1 if the number of operation candidates selected by the mobile unit c is 1, and is 0 if the number of operation candidates is 0. Note that when the number of mobile units is greater than the number of requests, there is a mobile unit for which the number of operation candidates selected by the mobile unit is 0.
  • the third constraint condition is that "the number of moving objects heading toward the destination of one request is one or less.”
  • the third constraint term setting unit 133 introduces a slack variable sr , which is an auxiliary decision variable, for each request r, and sets the QUBO coefficient Q (3) of the third constraint term so that the third constraint term takes the form of equation (13).
  • s r is a binary variable that is 1 if there is a mobile towards request r and 0 otherwise.
  • the constraint term setting unit 13 combines the QUBO coefficient Q (1) of the first constraint term set by the first constraint term setting unit 131, the QUBO coefficient Q (2) of the second constraint term set by the second constraint term setting unit 132, and the QUBO coefficient Q (3) of the third constraint term set by the third constraint term setting unit 133 to obtain the QUBO coefficient Q (k) of the constraint term.
  • the combining unit 14 receives as input the QUBO coefficient Q (o) of the objective term output from the objective term setting unit 12 and the QUBO coefficient Q (k) of the constraint term output from the constraint term setting unit 13, and weights and combines the QUBO coefficient Q (o) of the objective term and the QUBO coefficient Q (k) of the constraint term.
  • the combining unit 14 linearly combines the QUBO coefficient Q( o ) of the objective term and the QUBO coefficient Q (k) of the constraint term using the combination coefficient ⁇ o of the objective term and one or more combination coefficients ⁇ k of the constraint term.
  • Q (o) is the QUBO coefficient of the objective term output from the objective term setting unit 12.
  • Q (k) is the QUBO coefficient of the constraint term output from the constraint term setting unit 13, and respectively, Q (1) is the QUBO coefficient of the first constraint term output from the first constraint term setting unit 131, Q (2) is the QUBO coefficient of the second constraint term output from the second constraint term setting unit 132, and Q (3) is the QUBO coefficient of the third constraint term output from the third constraint term setting unit 133.
  • ⁇ o is the coupling coefficient of the objective term.
  • ⁇ k is the coupling coefficient of the constraint term
  • ⁇ 1 is the coupling coefficient of the first constraint term
  • ⁇ 2 is the coupling coefficient of the second constraint term
  • ⁇ 3 is the coupling coefficient of the third constraint term. All coupling coefficients are real numbers.
  • the combining unit 14 sets the combining coefficient ⁇ o of the objective terms so that the range of the combined QUBO coefficient Q (l) falls within the allowable input range of the annealing unit 15.
  • the combining unit 14 sets the coupling coefficient ⁇ k of the constraint term as follows: To obtain a solution that satisfies the constraint conditions in the annealing process of the annealing unit 15, the magnitude relationship between the coupling coefficient ⁇ o of the objective term and the coupling coefficient ⁇ k of the constraint term is important, and an optimal coupling coefficient exists to obtain a globally optimal solution with a small number of annealing calculations.
  • the combining unit 14 may set the coupling coefficient ⁇ o of the objective term and the coupling coefficient ⁇ k of the constraint term within the range of the following formula (16) so that the evaluation value of the constraint term for a solution that does not satisfy the constraints is sufficiently larger than the evaluation value of the objective term.
  • the combination unit 14 may set the combination coefficient ⁇ o of the objective term and the combination coefficient ⁇ k of the constraint term within the range of the following formula (17) by allowing a certain degree of probability that the annealing unit 15 will output a solution that does not satisfy the constraints.
  • the combining unit 14 sets the combining coefficient ⁇ o of the objective term and the combining coefficient ⁇ k of the constraint term, linearly combines the QUBO coefficient Q (o) of the objective term and the QUBO coefficient Q (k) of the constraint term, and generates a combined QUBO coefficient Q (l) which is a linearly combined QUBO coefficient.
  • the annealing unit 15 inputs the combined QUBO coefficient Q (l) linearly combined by the combining unit 14, calculates the QUBO problem represented by the combined QUBO coefficient Q (l) once or more by the simulated annealing method of quantum calculation or classical calculation, and obtains one or more sample solutions.
  • a quantum annealing machine or a gate-type quantum computer that executes a quantum approximate optimization algorithm (QAOA) may be used.
  • a CPU Central Processing Unit
  • a GPU Graphics Processing Unit
  • an FPGA Field Programmable Gate Array
  • other computers dedicated to simulated annealing that execute simulated annealing may be used.
  • the annealing unit 15 may also transform the QUBO problem to match the physical structure of the hardware being used, and perform simulated annealing calculations for quantum or classical computation.
  • the constraint verification unit 16 receives one or more sample solutions output from the annealing unit 15 as input, removes infeasible solutions that do not satisfy the constraint conditions, and extracts feasible solutions that satisfy the constraint conditions (feasible solutions that satisfy all of the multiple constraint conditions when there are multiple constraint conditions).
  • the constraint verification unit 16 calculates an evaluation value of the first constraint term expressed by formula (8), an evaluation value of the second constraint term expressed by formula (11), and an evaluation value of the third constraint term expressed by formula (13) for each input sample solution, and may remove the solution as an infeasible solution if at least one evaluation value is nonzero, and may determine that the solution is feasible if all evaluation values of the first to third constraint terms are 0.
  • the constraint verification unit 16 selects, from the extracted feasible solutions, the solution with the smallest evaluation value of the QUBO problem represented by the linearly combined combined QUBO coefficient Q (l) or the QUBO coefficient Q (o) of the objective term, as the optimal solution.
  • the constraint verification unit 16 may verify whether one or more sample solutions output from the annealing unit 15 satisfy the constraint conditions in ascending order of the evaluation value of the QUBO problem represented by the linearly combined combined QUBO coefficient Q (l) , and select the first feasible solution found as the optimal solution.
  • the constraint verification unit 16 may execute the annealing process of the annealing unit 15 again, and repeat the constraint verification process until a feasible solution is found. In addition, if a feasible solution is not found even after multiple repetitions, the constraint verification unit 16 may output that there is no solution.
  • the operation planning device 10 when departure points and destinations of multiple moving bodies are given on a map, the operation planning device 10 according to the first embodiment lists operation candidates for each moving body, including matching which moving body is headed for which destination, in the operation candidate enumeration unit 11. This makes it possible to optimize the combination of operation candidates for all moving bodies, including which moving body is headed for which destination.
  • the operation candidate enumeration unit 11 can enumerate operation candidates that wait at possible waiting points on a route that starts at the departure point of the mobile body and ends at the destination, thereby listing operation candidates that avoid collisions between mobile bodies at possible waiting points without using a detour route. This can also list operations that save the time and fuel costs required for the mobile bodies to travel on the detour route.
  • the operation candidate enumeration unit 11 can manage operation candidates for mobile bodies moving at different speeds in the same format by outputting operation candidate data D2 that summarizes the departure time and arrival time of the mobile body for each point on the route that starts from the departure point of the mobile body and ends at the destination. This makes it possible to calculate the optimal combination of operation candidates even when multiple mobile bodies move at different speeds.
  • the objective term setting unit 12 also determines the physical quantities related to the travel cost, and selects the function that determines the value of the travel cost from among a linear function, a step function, a normalized linear function, a quadratic function, and a downward convex function. This makes it possible to minimize the travel distance, travel time, and request waiting time of the mobile body as a whole, depending on the optimization objective. Also, depending on the user's request, it is possible to optimize the combination of operation candidates that reflects the relationship between the physical quantities related to the travel cost and the travel cost, such as specifying the arrival time of the mobile body and minimizing the variation in waiting time.
  • the constraint term setting unit 13 checks whether the route of the first moving body and the route of the second moving body share the same section (i.e., the same side) for a combination of an operation candidate of a certain moving body (first moving body) and an operation candidate of another moving body (second moving body) (i.e., a combination of any two operation candidates) from the operation candidate data D2 output from the operation candidate enumeration unit 11.
  • the constraint term setting unit 13 calculates, for two points (i.e., vertices indicated by u and v) at both ends of the same section, a first time difference (Tu1-Tu2) which is the time difference between the arrival or departure time Tu1 of the first moving body at point u and the arrival or departure time Tu2 of the second moving body at point u, and a second time difference (Tv1-Tv2) which is the time difference between the arrival or departure time Tv1 of the first moving body at point v and the arrival or departure time Tv2 of the second moving body at point v.
  • a first time difference Tu1-Tu2 which is the time difference between the arrival or departure time Tu1 of the first moving body at point u and the arrival or departure time Tu2 of the second moving body at point u
  • Tv1-Tv2 second time difference
  • the constraint term setting unit 13 has an intersection determination unit 130 that determines that a collision has occurred if the first time difference (Tu1-Tu2) and the second time difference (Tv1-Tv2) have different signs, or if at least one of the first time difference and the second time difference is 0.
  • This makes it possible to determine a collision from the operation candidate data D2 and calculate the collision cost of a combination of two operation candidates that will cause a collision between moving bodies.
  • the collision cost can be calculated in the same manner for a combination of two operation candidates of moving bodies with different speeds.
  • the QUBO problem can be formulated with fewer decision variables, reducing the calculation memory and calculation time of the annealing unit 15.
  • the constraint term setting unit 13 sets the constraint that the number of operation candidates selected by one mobile body is 0 or 1 as a penalty term to the QUBO coefficient of the second constraint term of the QUBO problem, so that the annealing unit 15 can calculate a solution that satisfies the second constraint that the number of operation candidates selected by one mobile body is 0 or 1, and obtain a combination of operation candidates that satisfies the second constraint. This makes it possible to prevent multiple requests from being concentrated on one mobile body.
  • the constraint term setting unit 13 sets the constraint that the number of moving objects heading towards one destination is one or less as a penalty term in the QUBO coefficient of the third constraint term of the QUBO problem, so that the annealing unit 15 can calculate a solution that satisfies the third constraint that the number of moving objects heading towards one destination is one or less, and obtain a combination of operation candidates that satisfies the third constraint. This makes it possible to prevent multiple moving objects from concentrating at the destination of one request.
  • the operation candidate enumeration unit 11 may search for routes in ascending order of travel cost for one combination of the departure point and destination of the moving body, and enumerate operation candidates whose difference between the travel cost of the route and the minimum travel cost is equal to or less than a predetermined upper limit. In this way, when there are many possible operations of the moving body, the enumeration of operation candidates is terminated within the allowable upper limit of travel cost, thereby shortening the calculation time of the operation candidate enumeration unit 11, limiting the size of the search area of the annealing unit 15, and reducing the required calculation time and calculation memory. As a result, the overall calculation time of the operation planning device 10 can be shortened.
  • the operation candidate enumeration unit 11 may enumerate operation candidates in ascending order of travel cost for one combination of the departure point and destination of the moving body within a range of a predetermined upper limit number. In this way, when there are many possible operations of the moving body, the enumeration of the operation candidates can be terminated within the allowable upper limit number, thereby shortening the calculation time of the operation candidate enumeration unit 11, limiting the size of the search area of the annealing unit 15, and reducing the required calculation time and calculation memory. As a result, the overall calculation time of the operation planning device 10 can be shortened.
  • FIG. 13 and FIG. 14 are diagrams showing an example of a hardware configuration of the operation planning device 10.
  • the operation planning device 10 is, for example, a computer.
  • the operation planning device 10 is a device capable of implementing the operation planning method according to the first embodiment.
  • the operation planning device 10 has a processor 101 and a memory 102 which is a volatile storage device.
  • the operation planning device 10 may have a non-volatile storage device such as a hard disk drive (HDD) or a solid state drive (SSD), and a communication device which communicates with an external device.
  • the memory 102 is, for example, a semiconductor memory such as a RAM (Random Access Memory).
  • the operation candidate enumeration unit 11, the objective term setting unit 12, the constraint term setting unit 13, the combining unit 14, the annealing unit 15, and the constraint verification unit 16 are configured by a processor which executes an operation planning program which is a software program installed from a recording medium or via a communication line and stored in the memory 102.
  • Each function of the operation planning device 10 may be realized by a processing circuit 103.
  • the processing circuit 103 may be dedicated hardware, or may be a processor 201 that executes an operation planning program stored in the memory 102.
  • the processor 101 may be any of a processing device, an arithmetic device, a microprocessor, a microcomputer, and a DSP (Digital Signal Processor).
  • the processing circuit is dedicated hardware, the processing circuit is, for example, an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array).
  • ASIC Application Specific Integrated Circuit
  • FPGA Field Programmable Gate Array
  • the operation planning device 10 may be partially realized by dedicated hardware and other parts by software or firmware. In this way, the processing circuit can realize each of the above-mentioned functions by hardware, software, firmware, or any combination of these.
  • Fig. 15 is a block diagram showing a configuration of an operation management system 20 according to embodiment 2.
  • the operation management system 20 includes an operation planning device 10, a control unit 30, and a transmission unit 40 (or a communication unit that transmits and receives).
  • the operation planning device 10 is any of the devices described in the first embodiment.
  • the control unit 30 acquires the optimal solution selected by the constraint verification unit 16 of the operation planning device 10.
  • the control unit 30 then generates control information for operating multiple moving bodies using the optimal solution as an operation plan.
  • the transmission unit 40 is a device that transmits the control information to the multiple moving bodies.
  • the multiple moving bodies share the control information.
  • the control unit 30 may transmit the control information as data to a server (not shown) via the transmission unit 40. Based on the control information stored in the server, the control unit 30 can create an operation plan that optimizes the combination of operation candidates for all of the moving bodies while avoiding collisions between the moving bodies.

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Navigation (AREA)

Abstract

運行計画装置（１０）は、移動体がどの目的地に向かうかを示す組み合わせ情報を含む運行候補を出力する運行候補列挙部（１１）と、運行候補の各々の移動に要する移動コストの合計である合計移動コストを計算し、ＱＵＢＯ問題の目的項のＱＵＢＯ係数（Ｑ（ｏ））を設定する目的項設定部（１２）と、制約項のＱＵＢＯ係数（Ｑ（ｋ））を設定する制約項設定部（１３）と、目的項のＱＵＢＯ係数（Ｑ（ｏ））と制約項のＱＵＢＯ係数（Ｑ（ｋ））とを重み付けして結合することで、結合ＱＵＢＯ係数（Ｑ（ｌ））を生成する結合部（１４）と、結合ＱＵＢＯ係数（Ｑ（ｌ））が表すＱＵＢＯ問題を焼きなまし法により１つ以上の解を得るアニーリング部（１５）と、１つ以上の解から制約条件を満たす実行可能解を取り出し、実行可能解の中から最適解を選択する制約検証部（１６）とを備える。

Description

運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム
　本開示は、運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システムに関する。
　移動体（例えば、自律走行車、自律走行ロボット、など）に作業を実行させる要請（以下「リクエスト」という）を受け取った場合に、移動体をリクエストのある目的地（以下「リクエストの目的地」ともいう）へ移動させる配車を行うシステムが知られている。しかし、複数の移動体がそれぞれの目的地に向けて同時に移動する場合には、移動体が他の移動体とすれ違う又は移動体が他の移動体を追い越す状況が発生し、移動体同士の衝突の可能性が生じる。
　特許文献１は、移動体同士の衝突を回避しつつ、複数の移動体の全体にとって最適な移動体の経路を推定するシステムを提案している。このシステムでは、複数の移動体の各々について、それぞれの目的地までの最短経路及び迂回経路（すなわち、目的地までの最短経路以外の経路）の時系列経路候補を生成し、前記時系列経路候補の経路割当評価値を計算し、前記時系列経路候補の移動距離評価値を計算し、前記時系列経路候補の組み合わせの経路衝突評価値を計算し、複数の移動体の時系列経路候補について、経路割当評価値と移動距離評価値と経路衝突評価値との合計値を比較することで、複数の移動体の時系列経路を最適候補として推定する。
特開２０２０－４６３８４号公報（例えば、要約書、請求項１、図１）
　しかしながら、各々の移動体が最短経路及び迂回経路を経路の候補として、候補の中で最適な経路を選ぶ方法には以下のような問題点がある。リクエストの目的地が複数あり、１つのリクエストに対応できる移動体が複数ある場合に、どの移動体がその目的地へ向かってもよい。同様に、１つの移動体が対応できる同種類のリクエストが複数あれば、その移動体がどの目的地へ向かってもよい。このようなときに、移動体の初期配置によっては、各移動体が予め定められた目的地に向かうと、出発地から遠い目的地へ移動体が配車され、複数の移動体の全体の移動コストが最小にならない。
　そこで、本開示は、上記のような問題点を解決するためになされたものであり、複数の移動体の全体の移動コストを最小にするように複数の移動体の運行候補の組み合わせを最適化することを目的としている。
　本開示に係る運行計画装置は、複数の移動体の各々の出発地と、目的地を示す複数のリクエストとが与えられたときに、前記複数の移動体の各々が、どの目的地に向かうかを示す組み合わせについて、前記出発地を始点とし前記目的地を終点とする経路と前記経路の移動スケジュールである複数の運行候補を示す運行候補データを出力する運行候補列挙部と、前記複数の運行候補の各々の移動に要する移動コストを、二次制約無し二値最適化問題であるＱＵＢＯ問題の目的項のＱＵＢＯ係数に設定する目的項設定部と、前記複数の運行候補のうちの制約条件を満たさない運行候補の組み合わせに対してペナルティ項である制約項を設け、前記制約項のＱＵＢＯ係数を設定する制約項設定部と、前記目的項のＱＵＢＯ係数と前記制約項のＱＵＢＯ係数とを重み付けして結合することで、結合ＱＵＢＯ係数を生成する結合部と、前記結合ＱＵＢＯ係数が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算するアニーリング処理を行い、１つ以上の解を得るアニーリング部と、前記アニーリング処理で得られた前記１つ以上の解から、前記制約条件を満たす実行可能解を取り出し、前記実行可能解の中から最適解を選択する制約検証部とを備えることを特徴とする。
　本開示に係る運行管理システムは、前記運行計画装置と、前記運行計画装置で選択された前記最適解を運行計画として前記複数の移動体を運行させるための制御情報を生成する制御部と、前記制御情報を前記複数の移動体に送信する送信部とを備えることを特徴とする。
　本開示によれば、複数の移動体の全体の移動コストを最小にするように複数の移動体の運行候補の組み合わせを最適化することができる。
実施の形態１に係る運行計画装置の構成を示すブロック図である。 図１の制約項設定部の構成を示すブロック図である。 複数の移動体の出発地と複数のリクエストの目的地とのマッチングの例を示す図である。 実施の形態１に係る運行計画装置の動作を示すフローチャートである。 複数の移動体が移動できる範囲を表す地図の例を示す図である。 図１の運行候補列挙部によって探索された経路候補の例を示す図である。 図１の運行候補列挙部によって探索された経路候補の他の例を示す図である。 図１の運行候補列挙部によって列挙された運行候補の例を示す図である。 図１の運行候補列挙部によって列挙された運行候補の他の例を示す図である。 図１の運行候補列挙部によって列挙された運行候補データの例を示す。 図１の運行候補列挙部によって列挙された運行候補データの他の例を示す。 （Ａ）から（Ｄ）は、図２の交差判定部によって行われる交差判定の方法を示す図である。 実施の形態１に係る運行計画装置のハードウェア構成の例を示す図である。 実施の形態１に係る運行計画装置のハードウェア構成の他の例を示す図である。 実施の形態２に係る運行管理システムの構成を示すブロック図である。
　以下に、実施の形態に係る運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システムを、図面を参照しながら説明する。以下の実施の形態は、例にすぎず、実施の形態を適宜組み合わせること及び各実施の形態を適宜変更することが可能である。
《１》実施の形態１
《１－１》構成
　図１は、実施の形態１に係る運行計画装置１０の構成を示すブロック図である。運行計画装置１０は、実施の形態１に係る運行計画方法を実施することができる装置である。運行計画装置１０は、例えば、実施の形態１に係る運行計画プログラムを実行する情報処理装置であるコンピュータである。図２は、図１の制約項設定部１３の構成を示すブロック図である。図３は、複数の移動体ｃ１～ｃ４の出発地Ａ１～Ａ４と複数のリクエストｒ１～ｒ４の目的地Ｂ１～Ｂ４とのマッチングの例を示す図である。
　まず、図１、図２及び図３を参照して、実施の形態１に係る運行計画装置１０について説明する。図１に示されるように、運行計画装置１０は、運行候補列挙部１１、目的項設定部１２、制約項設定部１３、結合部１４、アニーリング部１５、及び制約検証部１６を有している。運行計画装置１０は、記憶装置としての記憶部１７を有してもよい。ただし、記憶部１７は、運行計画装置１０と通信可能な外部装置（例えば、ネットワーク上のサーバ）の記憶装置であってもよい。複数の移動体は、例えば、通路を走行する車両である。車両は、例えば、自律走行車又は自律走行ロボットなどである。車両は、人が運転操作するものであってもよい。通路は、例えば、屋内の通路、屋外の通路又は道路、及びテーマパーク、公園、工場、倉庫などのような施設内の通路である。通路は、２台の移動体がすれ違うことができない（又は後ろの移動体が前の移動体を追い越すことができない）幅のものであってもよい。
　運行計画装置１０は、複数の移動体ｃ１～ｃ４の各々の出発地Ａ１～Ａ４（図１では出発地情報Ｄ０と表記する）と、目的地Ｂ１～Ｂ４を示す複数のリクエストｒ１～ｒ４（図１ではＤ１と表記する）とが与えられたときに、複数の移動体ｃ１～ｃ４の各々が、複数の目的地Ｂ１～Ｂ４のうちのどの目的地に向かうかを示す組み合わせ情報を含む複数の運行候補（図１では運行候補データＤ２と表記する）を出力する運行候補列挙部１１と、複数の運行候補の各々の移動に要する移動コストを、二次制約無し二値最適化（ＱＵＢＯ）問題の目的項のＱＵＢＯ係数Ｑ（ｏ）（図１ではＤ３と表記する）に設定する目的項設定部１２とを有している。また、運行計画装置１０は、複数の運行候補のうちの制約条件（すなわち、解きたい最適化問題の制約条件）を満たさない運行候補の組み合わせに対してペナルティ項である制約項を設け、制約項のＱＵＢＯ係数Ｑ（ｋ）（図１ではＤ４と表記する）を設定する制約項設定部１３と、目的項のＱＵＢＯ係数Ｑ（ｏ）と制約項のＱＵＢＯ係数Ｑ（ｋ）とを重み付けして結合することで、結合ＱＵＢＯ係数Ｑ（ｌ）（図１ではＤ５と表記する）を生成する結合部１４とを有している。さらに、運行計画装置１０は、結合ＱＵＢＯ係数Ｑ（ｌ）が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法（例えば、量子アニーリング又はシミュレーテッド・アニーリング）により１回以上計算するアニーリング処理を行い、１つ以上の解（図１ではＤ６と表記する）を得るアニーリング部１５と、アニーリング処理で得られた１つ以上の解から、制約条件を満たす１つ以上の実行可能解を取り出し、１つ以上の実行可能解の中から最適解（図１ではＤ７と表記する）を選択する制約検証部１６とを有している。
　運行候補列挙部１１は、移動体が移動できる範囲を示す地図と、その地図上の各地点間の移動に要する移動コストを示す情報と、移動体がどの地点で待機可能かを示す情報（すなわち、停車して待機することができる位置を示す情報）とを、例えば、記憶部１７から取得する。また、運行候補列挙部１１は、複数の移動体ｃ１～ｃ４の出発地Ａ１～Ａ４を示す出発地情報Ｄ０と、複数のリクエストｒ１～ｒ４の目的地Ｂ１～Ｂ４を示す目的地情報Ｄ１とを入力として受け取る。運行候補列挙部１１は、図３に示されるように、複数の移動体ｃ１～ｃ４のうちのどの移動体が、どの目的地に（すなわち、目的地Ｂ１～Ｂ４のいずれに）向かうかの組み合わせのすべてについて、運行候補を列挙する運行候補列挙処理を行う。運行候補列挙部１１は、列挙した運行候補を運行候補データＤ２として出力する。つまり、運行候補列挙部１１は、複数の移動体ｃ１～ｃ４の各々の出発地Ａ１～Ａ４を始点とし複数の目的地Ｂ１～Ｂ４を終点とする複数の経路上の予め決められた地点について、当該地点を通る前記移動体の出発時刻と到着時刻を含む運行候補データを出力する。運行候補列挙処理の具体例は、図５～図１１を参照して後述される。また、運行候補データＤ２の具体例は、図１２を参照して後述される。
　目的項設定部１２は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、各運行候補の移動コストを二次制約無し二値最適化（Ｑｕａｄｒａｔｉｃ　Ｕｎｃｏｎｓｔｒａｉｎｅｄ　Ｂｉｎａｒｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ）問題であるＱＵＢＯ問題の係数に設定する目的項設定処理を行い、目的項のＱＵＢＯ問題の係数Ｑ（ｏ）（図１におけるＤ３）を出力する。ＱＵＢＯ問題の係数は、「ＱＵＢＯ係数」ともいう。ＱＵＢＯ係数は、行列（広義にはベクトル）で表すことができる。移動コストは、例えば、移動体の移動距離、移動体の移動時間、移動に要する費用、及びリクエストの発生から移動体が目的地へ到着するまでに要する到着待ち時間、のうちの１つ又は２つ以上の組み合わせに基づいて決められる。目的項設定処理の詳細は後述される。
　制約項設定部１３は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、制約条件（Ｃｏｎｓｔｒａｉｎｔｓ）を満たさない運行候補の組み合わせに対して、ＱＵＢＯ問題においてペナルティ項として設けられた制約項のＱＵＢＯ係数Ｑ（ｋ）を設定する制約項設定処理を行い、制約項のＱＵＢＯ問題の係数であるＱＵＢＯ係数Ｑ（ｋ）（図１におけるＤ４）を出力する。制約項設定処理の詳細は後述される。なお、制約項のＱＵＢＯ係数Ｑ（ｋ）は、制約条件の条件数に応じて、複数のＱＵＢＯ係数からなる行列で表される。
　図２に示されるように、制約項設定部１３は、交差判定部１３０、第１の制約項設定部１３１、第２の制約項設定部１３２、及び第３の制約項設定部１３３を有している。
　交差判定部１３０は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、２つの運行候補の組み合わせについて、その組み合わせの運行候補に従って２台の移動体が移動すると衝突するか否かを判定する交差判定処理を行い、交差判定結果を出力する。交差判定部１３０の交差判定処理の詳細は、図１２（Ａ）から（Ｄ）を参照して後述される。なお、本出願において、「衝突」は、２台の移動体が移動する運行（ダイヤ）が交差すること、すなわち、２台の移動体が同じ通路で衝突する可能性がある状況が発生することを意味する。つまり、本出願において、「衝突」は、２台の移動体が実際に衝突することだけでなく、２台の移動体が同じ通路ですれ違うこと及び一方の移動体が他方の移動体を追い越すことを含む。
　第１の制約項設定部１３１は、交差判定部１３０から出力された交差判定の結果に基づいて、衝突が生じる２つの運行候補の組を選択すると、衝突コストが付加されるようにＱＵＢＯ問題の第１の制約項を設定する第１の制約項設定処理を行い、第１の制約項のＱＵＢＯ係数Ｑ（１）を出力する。第１の制約項設定処理の詳細は後述される。
　第２の制約項設定部１３２は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、１つの移動体が選択する運行候補の数を０又は１とする制約をペナルティ項として、ＱＵＢＯ問題の第２の制約項を設定する第２の制約項設定処理を行い、第２の制約項のＱＵＢＯ係数Ｑ（２）を出力する。第２の制約項設定処理の詳細は後述される。
　第３の制約項設定部１３３は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、１つのリクエストの目的地に向かう移動体の数は、１台以下とする制約をペナルティ項として、ＱＵＢＯ問題の第３の制約項を設定する第３の制約項設定処理を行い、第３の制約項のＱＵＢＯ係数Ｑ（３）を出力する。第３の制約項設定処理の詳細は後述される。
　制約項設定部１３は、第１の制約項のＱＵＢＯ係数Ｑ（１）と、第２の制約項のＱＵＢＯ係数Ｑ（２）と、第３の制約項のＱＵＢＯ係数Ｑ（３）とを、制約項のＱＵＢＯ係数Ｑ（ｋ）として出力する。
　結合部１４は、目的項設定部１２によって設定された目的項のＱＵＢＯ係数Ｑ（ｏ）と、制約項設定部１３によって設定された制約項のＱＵＢＯ係数Ｑ（ｋ）とを、１つ又は複数の結合係数を用いて結合（例えば、線形結合）する結合処理を行う。結合部１４は、結合されたＱＵＢＯ係数である結合ＱＵＢＯ係数Ｑ（ｌ）（図１におけるＤ５）を出力する。結合処理の詳細は後述される。
　アニーリング部１５は、結合ＱＵＢＯ係数Ｑ（ｌ）を入力として受け取り、その結合ＱＵＢＯ係数Ｑ（ｌ）が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算するアニーリング処理を行い、１サンプル以上の解（図１におけるＤ６）を出力する。使用する焼きなまし法は、量子計算による焼きなまし法又は古典計算による焼きなまし法のいずれであってもよい。ここで、解は、ＱＵＢＯ問題における決定変数（Ｄｅｃｉｓｉｏｎ　Ｖａｒｉａｂｌｅ）の値の数列であり、運行候補の組み合わせに対応している。なお、焼きなまし法は、１回の計算あたり、１サンプルの解を得るため、アニーリング部１５は、計算回数がＮ回（Ｎは１以上の整数）であれば、計算回数と同数であるＮサンプルの解を出力する。また、アニーリング部１５は、確率的な近似解法を用いてもよいため、アニーリング部１５から出力された解は、問題設定の大域的最適解である必要はない。
　制約検証部１６は、アニーリング部１５から出力された１サンプル以上の解から制約条件を満たさない解を取り除くことで、前記１サンプル以上の解のうちの制約条件を満たす解（以下「実行可能解」という）を取り出し、その実行可能解の中から最適解（図１におけるＤ７）を選択する制約検証処理を行う。制約検証処理の詳細は後述される。
《１－２》動作
《１－２－１》運行計画装置１０の動作
　次に、図４を参照して、運行計画装置１０の動作について説明する。図４は、運行計画装置１０の動作を示すフローチャートである。
　図４に示されるように、まず、運行候補列挙部１１は、複数の移動体の各々の出発地と複数の目的地とから運行候補を列挙する運行候補列挙処理を実行する（ステップＳＴ１）。
　次に、目的項設定部１２は、列挙された各運行候補の移動コストを目的項のＱＵＢＯ係数Ｑ（ｏ）に設定する目的項設定処理を実行する（ステップＳＴ２）。
　次に、制約項設定部１３は、制約条件を制約項のＱＵＢＯ係数Ｑ（ｋ）に設定する制約項設定処理を実行する（ステップＳＴ３）。
　次に、結合部１４は、目的項のＱＵＢＯ係数Ｑ（ｏ）と制約項のすべてのＱＵＢＯ係数Ｑ（ｋ）とを結合して、結合ＱＵＢＯ係数Ｑ（ｌ）を出力する処理を実行する（ステップＳＴ４）。
　次に、アニーリング部１５は、結合ＱＵＢＯ係数Ｑ（l）が表すＱＵＢＯ問題を焼きなまし法により、１回以上計算するアニーリング処理を実行する（ステップＳＴ５）。
　次に、制約検証部１６は、アニーリング部１５が計算した１つ以上の解のうち、制約条件を満たす実行可能解を取り出し、その実行可能解の中から最適解を選択する制約検証処理を実行する（ステップＳＴ６）。
《１－２－２》運行候補列挙部１１の動作
　次に、図３、図５～図１１を参照して、運行候補列挙部１１の運行候補列挙処理（図４におけるステップＳＴ１）の具体例について説明する。図５は、複数の移動体ｃ１、ｃ２が移動できる範囲を表す地図の例を示す図である。
　運行候補列挙部１１は、移動体が移動できる範囲を表す地図（すなわち、地図データ）と、その地図上の各地点間の移動に要する移動コストを示す情報とを取得可能である。図５に示されるように、地図は、グラフ理論のグラフ（以下単に「グラフ」という）を用いて表現することができる。図５では、地図上の地点（すなわち、位置）をグラフの頂点（図５では、０～８が付されたｖｅｒｔｅｘ）で表し、また、移動体が通行可能な各地点間の通路をグラフの辺（ｅｄｇｅ）で表している。通路の距離など、移動コストの算出に必要な情報は、グラフの辺の属性として設定される。また、地図上で移動体が待機可能か否かの情報は、グラフの頂点の属性として設定される。
　運行候補列挙部１１は、複数の移動体の出発地（すなわち、出発地情報）と複数のリクエストの目的地（すなわち、目的地情報）とを入力として受け取り、図３に示されるように、移動体ｃ（例えば、ｃ１～ｃ４）とリクエストｒ（例えば、ｒ１～ｒ４）との組み合わせの各々について、移動体の出発地（例えば、Ａ１～Ａ４）を始点とし、リクエストの目的地（例えば、Ｂ１～Ｂ４）を終点とする経路を、ダイクストラ法（Ｄｉｊｋｓｔｒａ′ｓ　ａｌｇｏｒｉｔｈｍ）などを用いて探索する（この処理は「経路探索ステップ」ともいう）。運行候補列挙部１１は、もし経路が見つからなければ、移動体ｃとリクエストｒの次の組み合わせについて、経路を調べる。もし経路が見つかれば、運行候補列挙部１１は、その経路を移動するスケジュールを計算し、その運行経路と移動スケジュールとからなる情報を運行候補に追加する（この処理は「運行候補列挙ステップ」ともいう）。そして、運行候補列挙部１１は、その他の経路、その他のリクエスト、その他の移動体についても同様に、経路探索ステップ、運行候補列挙ステップを繰り返し、運行候補を列挙する。
　図３は、４つの移動体ｃ１～ｃ４が４つのリクエストｒ１～ｒ４に対応する組み合わせの例を示すが、移動体の数とリクエストの数は、４に限定されない。
　運行計画問題の具体例を用いて、運行候補列挙部１１の動作を説明する。地図を表すグラフの例として、図５に示されるように、頂点０から頂点８までの９つの頂点を持ち、各辺の距離が「１」であるグラフを例とする。ここで、頂点４は、衝突を避けるために移動体が待機可能な地点である。
　運行計画問題の例として、次の問題を考える。時刻Ｔ＝０の初期配置において、２台の移動体ｃ１、ｃ２がそれぞれ頂点１、頂点３にあり、それらの頂点を各移動体の出発地とする。また、２つのリクエストｒ１、ｒ２がそれぞれ頂点７、頂点５を示し、それらの頂点を目的地とする。このような複数の出発地（頂点１、頂点３）と複数の目的地（頂点７、頂点５）が与えられたとき、移動体が出発地から目的地まで移動するのに要する移動時間を移動コストとし、移動体同士の衝突を避けながら、全体の移動コストが最小である最適な運行候補の組み合わせを求める。なお、移動体ｃ１、ｃ２は、各辺を速度「１」で移動し、各辺の移動時間が「１」であるとする。また、各移動体が許容される最大の待機時間を「１」とし、待機１回あたりの待機時間を「１」とする。
　経路探索ステップでは、運行候補列挙部１１が、まず、複数の移動体の出発地と複数のリクエストの目的地を入力として受け取り、移動体ｃとリクエストｒの組み合わせの各々について、移動体の出発地を始点としリクエストの目的地を終点とする経路を、ダイクストラ法などを用いて探索する。以降、移動体が移動する経路を経路上の始点から終点の頂点番号を用いて数列で表す。例えば、頂点１、頂点４、頂点７を通る経路ｐ１１１は、ｐ１１１＝［１，４，７］と表記する。
　移動体ｃ１がリクエストｒ１の目的地へ向けて、頂点１から頂点７へ移動する最短経路は、ｐ１１１＝［１，４，７］の経路である（図６）。一方、移動体ｃ１がリクエストｒ２の目的地へ向けて、頂点１から頂点５へ移動する最短経路は、ｐ１２１＝［１，２，５］、ｐ１２２＝［１，４，５］の２通りある（図７）。
　また、移動体ｃ２がリクエストｒ１の目的地へ向けて、頂点３から頂点７へ移動する最短経路は、ｐ２１１＝［３，４，７］、ｐ２１２＝［３，６，７］の２通りある（図７）。一方、移動体ｃ２がリクエストｒ２の目的地へ向けて、頂点３から頂点５へ移動する最短経路は、ｐ２２１＝［３，４，５］の１通りである（図６）。
　また、経路探索ステップでは、移動体の出発地からリクエストの目的地までの最短経路だけではなく、その他に取りうる迂回経路を探索してもよい。
　また、経路探索ステップでは、運行候補列挙部１１が、複数の移動体の各々の出発地とリクエストのある複数の目的地との組み合わせの各々について、移動コストが小さい経路順に経路を探索し、その移動コストと移動コストの最小値との差が予め定められた上限値以下の経路に限定して、運行候補を列挙してもよい。
　また、経路探索ステップでは、運行候補列挙部１１は、移動体とリクエストの１つの組み合わせについて、出発地から目的地に至る経路が存在しない場合に、その移動体とリクエストの組み合わせについての運行候補列挙ステップを省略してもよい。
　次に、運行候補列挙ステップでは、運行候補列挙部１１が、地図情報と移動体の情報から、経路上の各地点の出発時刻と到着時刻を計算し、図１０に示されるように各地点の出発時刻と到着時刻をまとめた形式で１つの運行候補をまとめる（すなわち、運行候補データを作成する）。
　例として、移動体ｃ１がリクエストｒ１によって指定される目的地へ向かう経路ｐ１１１＝［１，４，７］を移動する運行候補Ｍ１，１，１を説明する。移動体ｃ１が経路ｐ１１１を移動する様子は、頂点４で待機しない場合、図８のダイヤグラムに示されるようなものである。すわなち、時刻Ｔ＝０に頂点１を出発し、時刻Ｔ＝１に頂点４に到着する。また、同時刻に頂点４を出発し、時刻Ｔ＝２に頂点７に到着する。この運行候補をＭ１，１，１と表記する。ここで、１番目の下付き添え字は、移動体の番号、２番目の下付き添え字は、目的地の番号、３番目の下付き添え字は、１番目の下付き添え字が表す移動体が、２番目の下付き添え字が示すリクエストの目的地へ向かう複数の運行候補の中で何番目の候補であるかを示す番号である。
　また、運行候補列挙ステップでは、運行候補列挙部１１がグラフの頂点に設定された属性を参照して経路上の待機可能な地点を調べ、その経路上の待機可能な地点で待機する運行候補を列挙してもよい。つまり、運行候補列挙部１１は、複数の移動体ｃ１～ｃ４の出発地Ａ１～Ａ４を始点とし複数の目的地Ｂ１～Ｂ４を終点とする複数経路上に待機可能な地点がある場合、複数の運行候補として、待機可能な地点で待機する運行候補を列挙してもよい。
　例えば、経路ｐ１１１＝［１，４，７］は、経路ｐ１１１上の頂点４が待機可能な頂点である。頂点４で時間「１」だけ待機する場合、移動体ｃ１の運動の様子は、図９のダイヤグラムに示されるようなものである。すなわち、時刻Ｔ＝０で頂点１を出発し、時刻Ｔ＝１に頂点４に到着する。頂点４では、時間「１」だけ待機した後、時刻Ｔ＝２に頂点４を出発し、時刻Ｔ＝３に頂点７に到着する。この運行候補をＭ１，１，２と表記する。運行候補Ｍ１，１，２の運行候補データを図１０のＭ１，１，２欄に示す。
　もし経路上に待機可能な頂点が複数ある場合は、待機可能な各頂点の待機時間の合計が許容される最大待機時間以内であるように、待機可能な各頂点の待機時間の組み合わせを列挙し、各待機時間の組み合わせについて移動スケジュールを計算し、運行候補を列挙すればよい。
　運行候補列挙部１１は、その他の経路についても同様に経路探索ステップ、運行候補列挙ステップを繰り返し、運行候補を列挙する。そして、その他のリクエスト、その他の移動体についても、同様に、経路探索ステップ、運行候補列挙ステップを繰り返し、すべての運行候補を列挙する。
　また、運行候補列挙部１１は、移動体の出発地とリクエストの目的地の各組み合わせについて、すべての取り得る運行候補を列挙するのではなく、予め定められた上限個数以内の範囲の組み合わせの数であるように、移動コストが小さい順に運行候補の数を限定して列挙してもよい。
　移動体ｃ１がリクエストｒ２の目的地に向かう運行候補の具体例を示す。経路ｐ１２１＝［１，２，５］は、経路上に待機可能な頂点がないため、その経路を通る運行候補は、運行候補Ｍ１，２，１だけである（図１０のＭ１，２，１欄に示される）。経路ｐ１２２＝［１，４，５］は、経路上に待機可能な頂点４があるため、経路ｐ１２２を通る運行候補は、待機回数が０回の運行候補Ｍ１，２，２と、待機回数が１回の運行候補Ｍ１，２，３の２通りある（それぞれ図１０のＭ１，２，２欄とＭ１，２，３欄に示される）。
　以上のように、移動体ｃ１のすべての運行候補（例えば、Ｍ１，１，１、Ｍ１，１，２、Ｍ１，２，１、Ｍ１，２，２、Ｍ１，２，３）を列挙する。次に、移動体ｃ２についても同様に、図１１に示されるように、経路ｐ２１１の運行候補Ｍ２，１，１、Ｍ２，１，２、経路ｐ２１２の運行候補Ｍ２，１，３、経路ｐ２２１の運行候補Ｍ２，２，１、Ｍ２，２，２を列挙する。そして、列挙した運行候補を運行候補データの形式にまとめて出力する。
《１－２－３》目的項設定部１２の動作
　次に、目的項設定部１２の目的項設定処理の具体例について説明する。目的項設定部１２は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、各運行候補の移動コストを計算し、ＱＵＢＯ問題の目的項のＱＵＢＯ係数Ｑ（ｏ）を設定する。
　ＱＵＢＯ問題の目的項は、式（１）のように表される。式（１）において、決定変数ｘｃ，ｒ，ｍとｘｃ´，ｒ´，ｍ´は、０又は１の二値を取る変数である。決定変数ｘｃ，ｒ，ｍは、移動体ｃの出発地から対応するリクエストｒの目的地に向かう複数の運行候補の中から、ｍ番目の運行候補を選択する場合には１、それ以外の場合には０である。決定変数ｘｃ´，ｒ´，ｍ´は、移動体ｃ´の出発地から対応するリクエストｒ´の目的地に向かう複数の運行候補の中から、ｍ´番目の運行候補を選択する場合には１、それ以外の場合には０である。
Figure JPOXMLDOC01-appb-M000001
　ここで、インデックス関数ｉ（ｃ，ｒ，ｍ）は、すべての決定変数に対して１から順に番号を割り当てたときの、決定変数ｘｃ，ｒ，ｍの番号（以降「インデックス」と呼ぶ）を返す関数である。インデックス関数ｉ（ｃ´，ｒ´，ｍ´）は、すべての決定変数に対して１から順に番号を割り当てたときの、決定変数ｘｃ´，ｒ´，ｍ´の番号であるインデックスを返す関数である。目的項のＱＵＢＯ係数Ｑ（ｏ）は、実数行列で表現することができる。また、目的項のＱＵＢＯ係数Ｑ（ｏ）は、行列を一般化したベクトルとして配列で表現されてもよい。
　まず、目的項設定部１２は、最適化の目的に応じて移動コストに関する物理量を決める。物理量として、例えば、移動体の移動距離、移動体の移動時間、又は移動体の移動に要する費用、リクエストの発生から移動体が目的地へ到着するまでに要する待ち時間、又は、これらのうちの２つ以上の組み合わせなどがある。
　次に、目的項設定部１２は、各運行候補Ｍｃ，ｒ，ｍについて、式（２）に示されるように、移動コストに関する物理量τｃ，ｒ，ｍと重み関数ｆを用いて、移動コストを、目的項のＱＵＢＯ係数Ｑ（ｏ）に設定する。ここで、重み関数ｆは、線形関数、ステップ関数、正規化線形関数、二次関数、下凸関数のいずれか、から選択される。
Figure JPOXMLDOC01-appb-M000002
　移動コストに関する物理量の例として、移動体の移動距離の合計を最小化する場合は、運行候補列挙部１１が地図を表すグラフの辺の属性に予め地点間の距離値を設定しておき、目的項設定部１２が、運行候補が示す経路上に沿って辺の距離値を積算すればよい。
　また、移動コストに関する物理量の他の例として、移動体の移動時間の合計を最小化する場合は、目的項設定部１２は、各運行候補が示す目的地の到着時刻と出発地の出発時刻の差の時間（すなわち、時刻差）を算出すればよい。
　また、移動コストに関する物理量の他の例として、移動に要する費用の合計を最小化する場合は、運行候補列挙部１１が、地図を表すグラフの辺の属性に予め地点間の費用を設定しておき、目的項設定部１２が、運行候補が示す経路上に沿って辺を移動する際の費用を積算すればよい。
　また、移動コストに関する物理量の他の例として、リクエストの発生から移動体が目的地へ到着するまでに要する待ち時間の合計を最小化する場合は、目的項設定部１２は、運行候補が示す目的地の到着時刻とリクエストの発生時刻の差の時間を算出すればよい。
　重み関数ｆの関数形は、ユーザの要求に応じて、ステップ関数、正規化線形関数、二次関数、下凸関数のいずれか、から選択してもよい。
　ユーザの要求の例として、移動体の移動時間の合計の最小化であり、移動時間τの重み（時間あたりの移動コスト）が等しい場合、目的項設定部１２は、重み関数ｆとして式（３）に示されるような線形関数を選択すればよい。
Figure JPOXMLDOC01-appb-M000003
　その際、目的項設定部１２は、線形関数の１次係数をａ＝１に設定し、切片ｂを以下のように設定してもよい。
Figure JPOXMLDOC01-appb-M000004
　また、ユーザの要求の他の例として、リクエストの発生から移動体が目的地へ到着するまでに要する待ち時間τが予め定められた時間ｔ未満であれば許容され、時間ｔ以上であれば一律の費用が発生するような場合、目的項設定部１２は、重み関数ｆとして式（４）に示されるようなステップ関数を選択すればよい。その際、目的項設定部１２は、ステップ関数の閾値をτ０＝ｔ、ステップ幅をｂ＝１と設定してもよい。
Figure JPOXMLDOC01-appb-M000005
　また、ユーザの要求の他の例として、リクエストの発生から移動体が目的地へ到着するまでに要する待ち時間τが予め定められた時間τ０未満であれば許容され、時間τ０以上であれば時間τ０を超過した時間について時間当たりの費用が発生するような場合、目的項設定部１２は、重み関数ｆとして式（５）に示されるような正規化線形関数を選択すればよい。その際、正規化線形関数の閾値をτ０＝τ、超過時間当たりの移動コストをａ＝１と設定してもよい。
Figure JPOXMLDOC01-appb-M000006
　また、ユーザの要求の他の例として、リクエストの発生から移動体が目的地へ到着するまでに要する待ち時間τのばらつきを最小化したい場合、目的項設定部１２は、重み関数ｆとして二次関数又はより高次の下凸関数を選択すればよい。待ち時間τが大きいほど、非線形に移動コストが大きくなるため、ばらつきを減少させる効果がある。
　また、ユーザの要求の他の例として、移動体が目的地へ指定の時間に到着することを目的とする場合、目的項設定部１２は、重み関数ｆとしてτが指定の時間τ０で最小である下凸関数を選択すればよい。下凸関数の例として、式（６）の関数形を選び、指定時刻からのずれに対する移動コストをａ＝１としてもよい。
Figure JPOXMLDOC01-appb-M000007
　以上の方法を用いて、目的項設定部１２は、目的項のＱＵＢＯ係数Ｑ（ｏ）を設定する。
《１－２－４》制約項設定部１３の動作
　次に、制約項設定部１３の制約項設定処理の具体例について説明する。制約項設定部１３は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、ペナルティ関数法を用いて、制約条件を満たさない運行候補の組み合わせに対してＱＵＢＯ問題においてペナルティ項である制約項を設け、その制約項のＱＵＢＯ係数Ｑ（ｋ）を設定する。制約項設定部１３は、具体的には、次の３つの制約条件である第１～第３の制約条件について、制約条件を満たさない運行候補の組み合わせが選択されるとペナルティが付加されるように制約項のＱＵＢＯ係数Ｑ（ｋ）を設定する。
　第１の制約条件は、「移動体同士が衝突する運行候補の組み合わせを選択しない。」である。この第１の制約条件に対応する第１の制約項のＱＵＢＯ係数Ｑ（１）は、交差判定部１３０の交差判定処理の交差判定結果に基づいて行われる、第１の制約項設定部１３１の第１の制約項設定処理で設定される。
　第２の制約条件は、「１台の移動体が選択する運行候補の数は、０又は１である。」である。この第２の制約条件に対応する第２の制約項のＱＵＢＯ係数Ｑ（２）は、第２の制約項設定部１３２の第２の制約項設定処理で設定される。
　第３の制約条件は、「１つのリクエストの目的地に向かう移動体の数は、１台以下である。」である。この第３の制約条件に対応する第３の制約項のＱＵＢＯ係数Ｑ（３）は、第３の制約項設定部１３３の第３の制約項設定処理で設定される。
　そして、制約項設定部１３は、交差判定部１３０の交差判定処理及び第１の制約項設定部１３１の第１の制約項設定処理と、第２の制約項設定部１３２の第２の制約項設定処理と、第３の制約項設定部１３３の第３の制約項設定処理と、を行い、第１の制約項のＱＵＢＯ係数Ｑ（１）と、第２の制約項のＱＵＢＯ係数Ｑ（２）と、第３の制約項のＱＵＢＯ係数Ｑ（３）とをまとめて、制約項のＱＵＢＯ係数Ｑ（ｋ）として出力する。
　まず、交差判定部１３０の交差判定処理と第１の制約項設定部１３１の第１の制約項設定処理について、図１０及び図１１を参照して説明する。交差判定部１３０は、運行候補列挙部１１から出力された運行候補データＤ２を入力として受け取り、異なる２つの運行候補の組み合わせについて、２台の移動体がその運行候補でそれぞれ移動する際に衝突するか否か（すなわち、衝突の可能性のある状況が発生するか否か）を判定する。なお、交差判定対象の２つの運行候補をＭｃ，ｒ，ｍ、Ｍｃ´，ｒ´，ｍ´と表記する。
　交差判定部１３０は、まず、対象とする２つの運行候補Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´が示す２つの経路が同一区間を共有するかどうかを調べるために、２つの経路に共通するグラフの辺（以下「共通する辺」と呼ぶ）を抽出し、共通する各辺について交差判定を行う。
　次に、交差判定部１３０は、共通する辺ｅ＝｛ｕ，ｖ｝について、第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）を計算する。ここで、辺ｅは同一区間である。地点ｕ、地点ｖは、それぞれ同一区間の両端の第１の地点、第２の地点である。Ｔｕ１は、第１の移動体ｃが地点（頂点）ｕに到着又は地点ｕから出発する時刻であり、Ｔｕ２は、第２の移動体ｃ´が地点ｕに到着又は地点ｕから出発する時刻である。また、Ｔｖ１は、第１の移動体ｃが地点ｖに到着又は地点ｖから出発する時刻であり、Ｔｖ２は、第２の移動体ｃ´が地点ｖに到着又は地点ｖから出発する時刻である。交差判定部１３０は、もし第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）の２つの時刻差が異符号である場合、又は、少なくとも一方の時刻差が０である場合に、第１の移動体ｃと第２の移動体ｃ´との「衝突あり」（すなわち、「交差あり」又は「衝突の可能性あり」）として、共通する辺ｅの交差判定結果Ｘｅ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）を１又は非零の値とする。それ以外の場合は、第１の移動体ｃと第２の移動体ｃ´との「衝突なし」（すなわち、「交差なし」又は「衝突の可能性なし」）として、交差判定結果Ｘｅ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）を０とする。
　共通する辺ｅ＝｛ｕ，ｖ｝について、図１２（Ａ）～（Ｄ）に示すダイヤグラムを用いて、第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）の符号関係と、２台の移動体が衝突する場合と衝突しない場合の関係を説明する。図１２（Ａ）は、対向する２台の移動体ｃ、ｃ´が前方から衝突（すなわち、正面衝突）する場合のダイヤグラムであり、図１２（Ｂ）は、速度の速い移動体ｃ´が速度の遅い移動体ｃに後方から衝突（すなわち、追突）する場合のダイヤグラムである。いずれの場合も第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）とは、互いに異符号であり、２つの運行を表すダイヤグラムは、交差する。また、共通する辺の端の頂点で衝突する場合は、第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）の少なくとも一方の時刻差が０であり、その場合も２つの運行を表すダイヤグラムは交差する。
　そして、交差判定部１３０は、共有する辺上の交差判定結果を、式（７）のように加算して、２つの運行候補Ｍｃ，ｒ，ｍとＭｃ´，ｒ´，ｍ´の交差判定結果Ｘ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）を計算する。あるいは、交差判定部１３０は、少なくとも１つの共通する辺ｅでＸｅ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）が非零であれば、交差判定結果Ｘ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）を１又は非零の値とし、それ以外の場合は０としてもよい。
Figure JPOXMLDOC01-appb-M000008
　ここで、Ｅ（Ｍｃ，ｒ，ｍ，Ｍｃ´，ｒ´，ｍ´）は、２つの運行候補Ｍｃ，ｒ，ｍとＭｃ´，ｒ´，ｍ´が示す２つの経路に共通する辺の集合を表す。
　続いて、第１の制約項設定部１３１の第１の制約項設定処理について説明する。第１の制約項設定部１３１は、交差判定部１３０の交差判定結果を入力として受け取り、その値を衝突コストとして、第１の制約項が式（８）の形になるように、第１の制約項のＱＵＢＯ係数Ｑ（１）を設定する。
Figure JPOXMLDOC01-appb-M000009
Figure JPOXMLDOC01-appb-M000010
 は、決定変数ｘに対応して、各要素が０か１の二値の値をとる列ベクトルである。
　第１の制約項設定部１３１は、式（８）に示されるように、２つの運行候補の組み合わせのうち、移動体が同一の場合（ｃ＝ｃ´の場合）又はリクエストが同一の場合（ｒ＝ｒ´の場合）は、交差判定部１３０の交差判定処理を省略して、第１の制約項のＱＵＢＯ係数Ｑ（１）を、以下の式（９）のように設定してもよい。
Figure JPOXMLDOC01-appb-M000011
　あるいは、第１の制約項設定部１３１は、第１の制約項のＱＵＢＯ係数Ｑ（１）を、以下の式（１０）のように設定してもよい。
Figure JPOXMLDOC01-appb-M000012
　次に、第２の制約項設定部１３２の第２の制約項設定処理の具体例を説明する。第２の制約条件は、「１つの移動体が選択する運行候補の数は、０又は１である。」である。第２の制約項設定部１３２は、各移動体ｃについて補助的な決定変数であるスラック変数ｓｃを導入し、第２の制約項が式（１１）の形になるよう、第２の制約項のＱＵＢＯ係数Ｑ（２）を設定する。
Figure JPOXMLDOC01-appb-M000013
　ここで、スラック変数ｓｃは、移動体ｃが選択する運行候補の数が１個であれば１であり、運行候補の数が０個であれば０である二値変数である。なお、移動体の数がリクエストの数より多い場合、移動体が選択する運行候補の数が０である移動体が生じる。
　式（１１）として示される第２の制約項は、移動体の数Ｎｃがリクエストの数Ｎｒ以下の場合は、すべての移動体がリクエストに対応するものとして、スラック変数ｓｃを以下の式（１２）のように設定してもよい。すなわち、すべてのｃに対してｓｃ＝１と固定してもよい。
Figure JPOXMLDOC01-appb-M000014
　次に、第３の制約項設定部１３３の第３の制約項設定処理の具体例を説明する。第３の制約条件は、「１つのリクエストの目的地に向かう移動体の数は、１台以下とする」である。第３の制約項設定部１３３は、各リクエストｒについて補助的な決定変数であるスラック変数ｓｒを導入し、第３の制約項が式（１３）の形になるよう、第３の制約項のＱＵＢＯ係数Ｑ（３）を設定する。
Figure JPOXMLDOC01-appb-M000015
　ここで、ｓｒは、リクエストｒへ向かう移動体があれば１であり、それ以外では、０である二値変数である。
　式（１３）として示される第３の制約項は、移動体の数Ｎｃがリクエストの数Ｎｒ以上の場合、すべてのリクエストｒが対応されるものとして、スラック変数ｓｒを以下の式（１４）のように設定してもよい。すなわち、すべてのリクエストｒに対してｓｒ＝１と固定してもよい。
Figure JPOXMLDOC01-appb-M000016
　以上の方法を用いて、制約項設定部１３は、第１の制約項設定部１３１が設定した第１の制約項のＱＵＢＯ係数Ｑ（１）と、第２の制約項設定部１３２が設定した第２の制約項のＱＵＢＯ係数Ｑ（２）と、第３の制約項設定部１３３が設定した第３の制約項のＱＵＢＯ係数Ｑ（３）とをまとめて、制約項のＱＵＢＯ係数Ｑ（ｋ）とする。
《１－２－５》結合部１４の動作
　次に、結合部１４の結合処理の具体例を説明する。結合部１４は、目的項設定部１２から出力された目的項のＱＵＢＯ係数Ｑ（ｏ）と、制約項設定部１３から出力された制約項のＱＵＢＯ係数Ｑ（ｋ）を入力として受け取り、目的項のＱＵＢＯ係数Ｑ（ｏ）と制約項のＱＵＢＯ係数Ｑ（ｋ）とを重み付けして結合する。例えば、結合部１４は、式（１５）に示されるように、目的項の結合係数λｏと制約項の１つ以上の結合係数λｋを用いて、目的項のＱＵＢＯ係数Ｑ（ｏ）と制約項のＱＵＢＯ係数Ｑ（ｋ）との線形結合を行う。
Figure JPOXMLDOC01-appb-M000017
　ここで、Ｑ（ｏ）は、目的項設定部１２から出力された目的項のＱＵＢＯ係数である。また、Ｑ（ｋ）は、制約項設定部１３から出力された制約項のＱＵＢＯ係数であり、それぞれ、Ｑ（１）は、第１の制約項設定部１３１から出力された第１の制約項のＱＵＢＯ係数、Ｑ（２）は、第２の制約項設定部１３２から出力された第２の制約項のＱＵＢＯ係数、Ｑ（３）は、第３の制約項設定部１３３から出力された第３の制約項のＱＵＢＯ係数である。また、λｏは、目的項の結合係数である。また、λｋは、制約項の結合係数であり、λ１は、第１の制約項の結合係数、λ２は、第２の制約項の結合係数、λ３は、第３の制約項の結合係数である。結合係数は、いずれも実数である。
　結合部１４は、結合ＱＵＢＯ係数Ｑ（ｌ）の範囲がアニーリング部１５の許容入力範囲に収まるように、目的項の結合係数λｏを設定する。目的項の結合係数λｏは、目的項設定部１２の重み関数に依存するが、例えば、λｏ＝１としてもよい。
　また、結合部１４は、制約項の結合係数λｋを次のように設定する。アニーリング部１５のアニーリング処理で制約条件を満たす解を得るには、目的項の結合係数λｏと制約項の結合係数λｋの大小関係が重要であり、少ないアニーリング計算回数で大域的最適解を得るためには、最適な結合係数が存在する。結合部１４は、制約を満たさない解に対して制約項の評価値が目的項の評価値より十分大きくなるように設定するために、目的項の結合係数λｏと制約項の結合係数λｋを、以下の式（１６）の範囲で設定してもよい。
Figure JPOXMLDOC01-appb-M000018
　あるいは、アニーリング処理で大域的最適解が出力される確率的を上げるために、アニーリング部１５が制約を満たさない解を出力する確率をある程度許容して、結合部１４は、目的項の結合係数λｏと制約項の結合係数λｋを、以下の式（１７）の範囲で設定してもよい。
Figure JPOXMLDOC01-appb-M000019
　以上の方法を用いて、結合部１４は、目的項の結合係数λｏと制約項の結合係数λｋを設定し、目的項のＱＵＢＯ係数Ｑ（ｏ）と制約項のＱＵＢＯ係数Ｑ（ｋ）とを線形結合し、線形結合されたＱＵＢＯ係数である結合ＱＵＢＯ係数Ｑ（ｌ）を生成する。
《１－２－６》アニーリング部１５の動作
　次に、アニーリング部１５のアニーリング処理の具体例を説明する。アニーリング部１５は、結合部１４によって線形結合された結合ＱＵＢＯ係数Ｑ（ｌ）を入力して、その結合ＱＵＢＯ係数Ｑ（ｌ）が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算し、１サンプル以上の解を得る。量子計算には、量子アニーリングマシン又は、量子近似最適化アルゴリズム（ＱＡＯＡ）を実行するゲート型量子コンピュータを用いてもよい。また、古典計算の焼きなまし法のために、シミュレーテッド・アニーリングを実行するＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）、その他シミュレーテッド・アニーリング専用計算機を用いてもよい。
　また、アニーリング部１５は、使用するハードウェアの物理的な構造に合わせてＱＵＢＯ問題を変形し、量子計算又は古典計算の焼きなまし法の計算を実行してもよい。
《１－２－７》制約検証部１６の動作
　次に、制約検証部１６の制約検証処理の具体例を説明する。まず、制約検証部１６は、アニーリング部１５から出力された１サンプル以上の解を入力として受け取り、制約条件を満たさない実行不可能解を取り除き、制約条件を満たす実行可能解（複数の制約条件がある場合には、複数の制約条件のすべてを満たす実行可能解）を取り出す。ここで、制約検証部１６は、入力した各サンプルの解についてそれぞれ、式（８）で表される第１の制約項の評価値と、式（１１）で表される第２の制約項の評価値と、式（１３）で表される第３の制約項の評価値と、を計算し、少なくとも１つの評価値が非零であれば実行不可能な解として取り除き、第１から第３の制約項のすべての評価値が０であれば実行可能解と判定してもよい。
　制約検証部１６は、取り出した実行可能解の中から、線形結合された結合ＱＵＢＯ係数Ｑ（ｌ）又は目的項のＱＵＢＯ係数Ｑ（ｏ）が表すＱＵＢＯ問題の評価値が最小である解を最適解として選択する。
　また、制約検証処理の他の方法として、制約検証部１６は、アニーリング部１５から出力された１サンプル以上の解を、線形結合された結合ＱＵＢＯ係数Ｑ（ｌ）が表すＱＵＢＯ問題の評価値が小さい順に制約条件を満たすかどうか検証し、最初に見つかった実行可能解を最適解として選択してもよい。
　また、制約検証部１６は、入力した複数のサンプルの解のうち、実行可能解が見つからなかった場合に、アニーリング部１５のアニーリング処理を再度実行し、実行可能解が、見つかるまで制約検証処理を繰り返してもよい。また、制約検証部１６は、複数回繰り返しても実行可能解が見つからなかった場合は、解なしと出力してもよい。
《１－３》効果
　以上に説明したように、実施の形態１に係る運行計画装置１０は、地図上に複数の移動体の出発地と複数の目的地が与えられたときに、運行候補列挙部１１で、どの移動体がどの目的地に向かうかのマッチングを含めて、各移動体の運行候補を列挙する。それにより、どの移動体がどの目的地へ向かうかも含めて、移動体全体の運行候補の組み合わせを最適化することができる。
　また、運行候補列挙部１１は、移動体の出発地を始点とし目的地を終点とする経路について、その経路上の待機可能な地点で待機する運行候補を列挙することで、移動体が迂回経路を使わずに、待機可能な地点で移動体同士の衝突を回避する運行候補を挙げることができる。それにより、移動体の迂回経路の移動に要する時間及び燃料などの費用を節約する運行も候補に挙げられる。
　また、運行候補列挙部１１は、移動体の出発地を始点とし目的地を終点とする経路について、その経路上の地点ごとに移動体の出発時刻と到着時刻をまとめた運行候補データＤ２を出力することで、異なる速度で移動する移動体の運行候補を同一形式で管理することができる。それにより、複数の移動体が異なる速度で移動する場合でも、最適な運行候補の組み合わせを計算できる。
　また、目的項設定部１２は、移動コストに関する物理量を決め、移動コストの値を決定する関数を線形関数、ステップ関数、正規化線形関数、二次関数、及び下凸関数のいずれかから選択する。それにより、最適化の目的に応じて、移動体の移動距離、移動時間、リクエストの待ち時間などを、移動体全体で最小化することができる。また、ユーザの要求に応じて、移動体の到着時刻の指定、待ち時間のばらつきの最小化など、移動コストに関する物理量と移動コストの関係を反映した運行候補の組み合わせを最適化ができる。
　また、制約項設定部１３は、運行候補列挙部１１から出力された運行候補データＤ２から、ある移動体（第１の移動体）の運行候補と他のある移動体（第２の移動体）の運行候補との組み合わせ（すなわち、任意の２つの運行候補の組み合わせ）について、第１の移動体の経路と第２の移動体の経路が同じ区間（すなわち、同じ辺）を共有するかを調べる。制約項設定部１３は、共有する場合に、前記同じ区間の両端の２地点（すなわち、ｕ，ｖで示される頂点）について、第１の移動体の地点ｕの到着又は出発の時刻Ｔｕ１と第２の移動体の地点ｕの到着又は出発の時刻Ｔｕ２の時刻差である第１の時刻差（Ｔｕ１－Ｔｕ２）と、第１の移動体の地点ｖの到着又は時刻Ｔｖ１と第２の移動体の地点ｖの到着又は出発の時刻Ｔｖ２の時刻差である第２の時刻差（Ｔｖ１－Ｔｖ２）とを計算する。制約項設定部１３は、第１の時刻差（Ｔｕ１－Ｔｕ２）と第２の時刻差（Ｔｖ１－Ｔｖ２）と異なる符号を持つ、又は、第１の時刻差と前記第２の時刻差の少なくとも一方が０であれば、「衝突あり」と判定する交差判定部１３０を有する。それにより、運行候補データＤ２から衝突を判定し、移動体の衝突が発生する２つの運行候補の組み合わせの衝突コストを計算することができる。また、速度の異なる移動体の２つの運行候補の組み合わせについても同じ方法で衝突コストを計算できる。さらに、ＱＵＢＯ問題を少ない決定変数で定式化でき、アニーリング部１５の計算メモリと計算時間を削減できる。
　また、制約項設定部１３は、１台の移動体が選択する運行候補の数が０又は１とする制約をペナルティ項として、ＱＵＢＯ問題の第２の制約項のＱＵＢＯ係数に設定することで、アニーリング部１５は、１台の移動体が選択する運行候補の数は、０又は１とする第２の制約を満たす解を計算することができ、第２の制約を満たす運行候補の組み合わせを得ることができる。それにより、１台の移動体に複数のリクエストが集中することを防ぐことができる。
　また、制約項設定部１３は、１つの目的地に向かう移動体の数は、１台以下とする制約をペナルティ項として、ＱＵＢＯ問題の第３の制約項のＱＵＢＯ係数に設定することで、アニーリング部１５は、１つの目的地に向かう移動体の数は、１台以下とするとする第３の制約を満たす解を計算することができ、第３の制約を満たす運行候補の組み合わせを得ることができる。それにより、１つのリクエストの目的地に複数の移動体が集中することを防ぐことができる。
《１－４》変形例１
　運行候補列挙部１１は、移動体の出発地と目的地の１つの組み合わせについて、移動コストが小さい経路順に経路を探索し、その経路の移動コストと移動コストの最小値との差が予め定められた上限値以下の運行候補の候補を列挙することとしてもよい。それにより、移動体の取り得る運行が多数存在する場合に、許容する上限値の移動コスト以内で運行候補の列挙を打ち切ることで、運行候補列挙部１１の計算時間を短くでき、アニーリング部１５の探索領域の大きさを制限でき、必要な計算時間及び計算メモリを削減できる。その結果、運行計画装置１０の全体の計算時間を短くすることができる。
《１－５》変形例２
　運行候補列挙部１１は、移動体の出発地と目的地の１つの組み合わせについて、予め定められた上限個数以内の範囲で、移動コストが小さい順に運行候補を列挙すること、としてもよい。それにより、移動体の取り得る運行が多数存在する場合に、許容する上限個数以内で運行候補の列挙を打ち切ることで、運行候補列挙部１１の計算時間を短くでき、アニーリング部１５の探索領域の大きさを制限でき、必要な計算時間及び計算メモリを削減できる。その結果、運行計画装置１０の全体の計算時間を短くすることができる。
《１－６》ハードウェア構成
　図１３及び図１４は、運行計画装置１０のハードウェア構成の例を示す図である。運行計画装置１０は、例えば、コンピュータである。運行計画装置１０は、実施の形態１に係る運行計画方法を実施することができる装置である。運行計画装置１０は、プロセッサ１０１と、揮発性の記憶装置であるメモリ１０２とを有している。運行計画装置１０は、ハードディスクドライブ（ＨＤＤ）又はソリッドステートドライブ（ＳＳＤ）などの不揮発性の記憶装置と、外部の装置との通信を行う通信装置とを有してもよい。メモリ１０２は、例えば、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）などの半導体メモリである。運行候補列挙部１１、目的項設定部１２、制約項設定部１３、結合部１４、アニーリング部１５、及び制約検証部１６は、記録媒体から又は通信回線を介してインストールされメモリ１０２に記憶されたソフトウェアプログラムである運行計画プログラムを実行するプロセッサにより構成される。
　運行計画装置１０の各機能は、処理回路１０３により実現されてもよい。処理回路１０３は、専用のハードウェアであってもよく、又はメモリ１０２に格納される運行計画プログラムを実行するプロセッサ２０１であってもよい。プロセッサ１０１は、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、及びＤＳＰ（Ｄｉｇｉｔａｌ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｏｒ）のいずれであってもよい。
　処理回路が専用のハードウェアである場合、処理回路は、例えば、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ　Ｓｐｅｃｉｆｉｃ　Ｉｎｔｅｇｒａｔｅｄ　Ｃｉｒｃｕｉｔ）又はＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）などである。
　なお、運行計画装置１０は、一部を専用のハードウェアで実現し、他の一部をソフトウェア又はファームウェアで実現するようにしてもよい。このように、処理回路は、ハードウェア、ソフトウェア、ファームウェア、又はこれらのうちのいずれかの組み合わせによって、上述の各機能を実現することができる。
《２》実施の形態２
　図１５は、実施の形態２に係る運行管理システム２０の構成を示すブロック図である。図１５に示されるように、運行管理システム２０は、運行計画装置１０、制御部３０、及び送信部４０（又は送受信を行う通信部）を有している。
　運行計画装置１０は、実施の形態１において説明したいずれかの装置である。制御部３０は、運行計画装置１０の制約検証部１６で選択された最適解を取得する。そして、制御部３０は、最適解を運行計画として複数の移動体を運行させるための制御情報を生成する。送信部４０は、制御情報を複数の移動体に送信する装置である。複数の移動体は、制御情報を共有する。
　それにより、１つのリクエストの目的地に複数の移動体が集中することを防ぐことができる。
　なお、制御部３０は、送信部４０を介して制御情報をデータとしてサーバ（図示せず）に送信してもよい。制御部３０は、サーバに蓄積された制御情報に基づいて、移動体の衝突を避けながら移動体全体の運行候補の組み合わせが最適化された運行計画を立てることができる。
　１０　運行計画装置、　１１　運行候補列挙部、　１２　目的項設定部、　１３　制約項設定部、　１４　結合部、　１５　アニーリング部、　１６　制約検証部、　１７　記憶部、　１３０　交差判定部、　１３１　第１の制約項設定部、　１３２　第２の制約項設定部、　１３３　第３の制約項設定部、　２０　運行管理システム、　３０　制御部、　４０　送信部、　ｃ、ｃ´、ｃ１～ｃ４　移動体、　Ａ１～Ａ４　出発地、　Ｂ１～Ｂ４　目的地、　ｒ１～ｒ４　リクエスト、　Ｑ（ｏ）　目的項のＱＵＢＯ係数、　Ｑ（ｋ）　制約項のＱＵＢＯ係数、　Ｑ（１）　第１の制約項のＱＵＢＯ係数、　Ｑ（２）　第２の制約項のＱＵＢＯ係数、　Ｑ（３）　第３の制約項のＱＵＢＯ係数、　Ｑ（ｌ）　結合ＱＵＢＯ係数。

Claims (15)

  1. 　複数の移動体の各々の出発地と、目的地を示す複数のリクエストとが与えられたときに、前記複数の移動体の各々が、どの目的地に向かうかを示す組み合わせについて、前記出発地を始点とし前記目的地を終点とする経路と前記経路の移動スケジュールである複数の運行候補を示す運行候補データを出力する運行候補列挙部と、
    　前記複数の運行候補の各々の移動に要する移動コストを、二次制約無し二値最適化問題であるＱＵＢＯ問題の目的項のＱＵＢＯ係数に設定する目的項設定部と、
    　前記複数の運行候補のうちの制約条件を満たさない運行候補の組み合わせに対してペナルティ項である制約項を設け、前記制約項のＱＵＢＯ係数を設定する制約項設定部と、
    　前記目的項のＱＵＢＯ係数と前記制約項のＱＵＢＯ係数とを重み付けして結合することで、結合ＱＵＢＯ係数を生成する結合部と、
    　前記結合ＱＵＢＯ係数が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算するアニーリング処理を行い、１つ以上の解を得るアニーリング部と、
    　前記アニーリング処理で得られた前記１つ以上の解から、前記制約条件を満たす実行可能解を取り出し、前記実行可能解の中から最適解を選択する制約検証部と、
    　を備えることを特徴とする運行計画装置。
  2. 　前記運行候補列挙部は、
    　前記移動体が移動できる範囲を含む地図と、前記地図上の各地点間の移動に要する前記移動コストを示す情報と、前記移動体が待機可能な地点を示す情報とを記憶部から取得し、
    　前記地図と、前記移動コストを示す情報と、前記待機可能な地点を示す情報とを用いて、前記複数の移動体の各々の出発地と、目的地を示す複数のリクエストとの間の組み合わせについて、前記出発地を始点とし前記目的地を終点とする経路と前記経路の移動スケジュールである前記運行候補を示す前記運行候補データを生成する
    　ことを特徴とする請求項１に記載の運行計画装置。
  3. 　前記移動コストは、前記移動体の移動距離、前記移動体の移動時間、前記移動体の移動に要する費用、及び前記リクエストの発生から前記移動体が前記目的地へ到着するまでに要する到着待ち時間のうちの１つ又は２つ以上の組み合わせに基づいて決められる
    　ことを特徴とする請求項１又は２に記載の運行計画装置。
  4. 　前記運行候補列挙部は、前記複数の移動体の各々の前記出発地を始点とし前記複数の目的地を終点とする複数経路上に待機可能な地点がある場合、前記複数の運行候補として、前記待機可能な地点で待機する運行候補を列挙する
    　ことを特徴とする請求項１から３のいずれか１項に記載の運行計画装置。
  5. 　前記運行候補列挙部は、前記複数の移動体の各々の前記出発地を始点とし前記複数の目的地を終点とする複数の経路上の予め決められた地点について、当該地点を通る前記移動体の出発時刻と到着時刻を含む運行候補を列挙する
    　ことを特徴とする請求項１から４のいずれか１項に記載の運行計画装置。
  6. 　前記運行候補列挙部は、前記複数の移動体の各々の出発地と複数の目的地との組み合わせの各々について、前記移動コストが小さい経路順に経路を探索し、探索された前記経路の前記移動コストと前記移動コストの最小値との差が予め定められた上限値以下の運行候補を列挙する
    　ことを特徴とする請求項１から５のいずれか１項に記載の運行計画装置。
  7. 　前記運行候補列挙部は、前記移動体の出発地と目的地の各組み合わせについて、予め定められた上限個数以内の範囲で前記移動コストの小さい順に運行候補を列挙する
    　ことを特徴とする請求項１から５のいずれか１項に記載の運行計画装置。
  8. 　前記目的項設定部は、前記移動コストに関する物理量を決め、前記移動コストの値を決定する関数を線形関数、ステップ関数、正規化線形関数、二次関数、及び下凸関数から選択する
    　ことを特徴とする請求項１から７のいずれか１項に記載の運行計画装置。
  9. 　前記制約項設定部は、
    　前記運行候補データから、第１の移動体の運行候補と第２の移動体の運行候補との組み合わせについて、前記第１の移動体の経路と前記第２の移動体の経路が同じ区間を共有するか調べ、
    　共有する場合に、前記同じ区間の両端の第１の地点及び第２の地点について、前記第１の移動体の前記第１の地点の到着又は出発の時刻と前記第２の移動体の前記第１の地点の到着又は出発の時刻との時刻差である第１の時刻差と、前記第１の移動体の前記第２の地点の到着又は出発の時刻と前記第２の移動体の前記第２の地点の到着又は出発の時刻との時刻差である第２の時刻差とを計算し、
    　前記第１の時刻差と前記第２の時刻差とが異なる符号を持つ、又は前記第１の時刻差と前記第２の時刻差の少なくとも一方が０であれば、前記第１の移動体と前記第２の移動体との衝突が生じると判定する
    　ことを特徴とする請求項５に記載の運行計画装置。
  10. 　前記制約項設定部は、前記衝突が生じる２つの運行候補の組み合わせについての衝突コストが付加されるように前記制約項のＱＵＢＯ係数を設定する
    　ことを特徴とする請求項９に記載の運行計画装置。
  11. 　前記制約項設定部は、１台の移動体が選択する運行候補の数が０又は１とする制約をペナルティ項として、前記制約項のＱＵＢＯ係数に設定する
    　ことを特徴とする請求項１から１０のいずれか１項に記載の運行計画装置。
  12. 　前記制約項設定部は、１つの目的地に向かう移動体の数は、１台以下とする制約をペナルティ項として、前記制約項のＱＵＢＯ係数に設定する
    　ことを特徴とする請求項１から１１のいずれか１項に記載の運行計画装置。
  13. 　運行計画装置によって実施される運行計画方法であって、
    　複数の移動体の各々の出発地と、目的地を示す複数のリクエストとが与えられたときに、前記複数の移動体の各々が、どの目的地に向かうかを示す組み合わせについて、前記出発地を始点とし前記目的地を終点とする経路と前記経路の移動スケジュールである複数の運行候補を示す運行候補データを出力するステップと、
    　前記複数の運行候補の各々の移動に要する移動コストを、二次制約無し二値最適化問題であるＱＵＢＯ問題の目的項のＱＵＢＯ係数に設定するステップと、
    　前記複数の運行候補のうちの制約条件を満たさない運行候補の組み合わせに対してペナルティ項である制約項を設け、前記制約項のＱＵＢＯ係数を設定するステップと、
    　前記目的項のＱＵＢＯ係数と前記制約項のＱＵＢＯ係数とを重み付けして結合することで、結合ＱＵＢＯ係数を生成するステップと、
    　前記結合ＱＵＢＯ係数が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算するアニーリング処理を行い、１つ以上の解を得るステップと、
    　前記アニーリング処理で得られた前記１つ以上の解から、前記制約条件を満たす実行可能解を取り出し、前記実行可能解の中から最適解を選択するステップと
    　を有することを特徴とする運行計画方法。
  14. 　複数の移動体の各々の出発地と、目的地を示す複数のリクエストとが与えられたときに、前記複数の移動体の各々が、どの目的地に向かうかを示す組み合わせについて、前記出発地を始点とし前記目的地を終点とする経路と前記経路の移動スケジュールである複数の運行候補を示す運行候補データを出力するステップと、
    　前記複数の運行候補の各々の移動に要する移動コストを、二次制約無し二値最適化問題であるＱＵＢＯ問題の目的項のＱＵＢＯ係数に設定するステップと、
    　前記複数の運行候補のうちの制約条件を満たさない運行候補の組み合わせに対してペナルティ項である制約項を設け、前記制約項のＱＵＢＯ係数を設定するステップと、
    　前記目的項のＱＵＢＯ係数と前記制約項のＱＵＢＯ係数とを重み付けして結合することで、結合ＱＵＢＯ係数を生成するステップと、
    　前記結合ＱＵＢＯ係数が表すＱＵＢＯ問題を量子計算又は古典計算の焼きなまし法により１回以上計算するアニーリング処理を行い、１つ以上の解を得るステップと、
    　前記アニーリング処理で得られた前記１つ以上の解から、前記制約条件を満たす実行可能解を取り出し、前記実行可能解の中から最適解を選択するステップと
    　をコンピュータに実行させることを特徴とする運行計画プログラム。
  15. 　請求項１から１２のいずれか１項に記載の運行計画装置と、
    　前記運行計画装置で選択された前記最適解を運行計画として前記複数の移動体を運行させるための制御情報を生成する制御部と、
    　前記制御情報を前記複数の移動体に送信する送信部と、
    　を備えることを特徴とする運行管理システム。
PCT/JP2022/038949 2022-10-19 2022-10-19 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム WO2024084628A1 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/JP2022/038949 WO2024084628A1 (ja) 2022-10-19 2022-10-19 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2022/038949 WO2024084628A1 (ja) 2022-10-19 2022-10-19 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム

Publications (1)

Publication Number Publication Date
WO2024084628A1 true WO2024084628A1 (ja) 2024-04-25

Family

ID=90737174

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2022/038949 WO2024084628A1 (ja) 2022-10-19 2022-10-19 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム

Country Status (1)

Country Link
WO (1) WO2024084628A1 (ja)

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007078489A (ja) * 2005-09-13 2007-03-29 Aisin Aw Co Ltd ナビゲーション装置
WO2009104244A1 (ja) * 2008-02-19 2009-08-27 パイオニア株式会社 走行計画装置、ナビゲーション装置、走行計画方法、走行計画プログラムおよび記録媒体
WO2022024244A1 (ja) * 2020-07-29 2022-02-03 日本電気株式会社 経路案内装置、経路案内方法、および記録媒体
JP2022032552A (ja) * 2020-08-12 2022-02-25 富士通株式会社 評価関数生成プログラム、評価関数生成方法及び情報処理装置
JP2022141131A (ja) * 2021-03-15 2022-09-29 オムロン株式会社 点検支援システム、点検支援装置、端末装置、点検支援方法、及びプログラム

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2007078489A (ja) * 2005-09-13 2007-03-29 Aisin Aw Co Ltd ナビゲーション装置
WO2009104244A1 (ja) * 2008-02-19 2009-08-27 パイオニア株式会社 走行計画装置、ナビゲーション装置、走行計画方法、走行計画プログラムおよび記録媒体
WO2022024244A1 (ja) * 2020-07-29 2022-02-03 日本電気株式会社 経路案内装置、経路案内方法、および記録媒体
JP2022032552A (ja) * 2020-08-12 2022-02-25 富士通株式会社 評価関数生成プログラム、評価関数生成方法及び情報処理装置
JP2022141131A (ja) * 2021-03-15 2022-09-29 オムロン株式会社 点検支援システム、点検支援装置、端末装置、点検支援方法、及びプログラム

Similar Documents

Publication Publication Date Title
US11702105B2 (en) Technology to generalize safe driving experiences for automated vehicle behavior prediction
CN113850363A (zh) 将驾驶规范应用于自动车辆行为预测的技术
Nishi et al. Merging in congested freeway traffic using multipolicy decision making and passive actor-critic learning
JP6578331B2 (ja) 自律走行車のコマンド遅延を決定するための方法
CN110389584A (zh) 用于评估自动驾驶车辆的轨迹候选项的方法
JP2019138903A (ja) 加速カーブの投影に用いられるシステム及び方法
Ghodsi et al. Generating and characterizing scenarios for safety testing of autonomous vehicles
US10809080B2 (en) System and method for determining routing by learned selective optimization
CN110462703A (zh) 基于碰撞后分析的自动驾驶车辆的车辆动作优化
US20230038673A1 (en) Sequential pedestrian trajectory prediction using step attention for collision avoidance
US20180252540A1 (en) Method and system for providing route guidance using navigation system
Guney et al. Scheduling‐based optimization for motion coordination of autonomous vehicles at multilane intersections
KR20230024392A (ko) 주행 의사 결정 방법 및 장치 및 칩
CN113767393A (zh) 使用具有显示生命周期的矢量图数据可视化自主交通工具过程
Oh et al. Hcnaf: Hyper-conditioned neural autoregressive flow and its application for probabilistic occupancy map forecasting
Maiti et al. Ad-hoc platoon formation and dissolution strategies for multi-lane highways
Garlick et al. Real-time optimal trajectory planning for autonomous vehicles and lap time simulation using machine learning
Li et al. Basics and Applications of AI in ADAS and Autonomous Vehicles
WO2024084628A1 (ja) 運行計画装置、運行計画方法、運行計画プログラム、及び運行管理システム
US20140297243A1 (en) Traffic simulation method, program, and system
Wang et al. Multi-agent reinforcement learning guided by signal temporal logic specifications
JP7563037B2 (ja) 集配計画最適化装置、集配計画最適化方法およびプログラム
Mortazavi Azad et al. Smart control of traffic lights based on traffic density in the multi-intersection network by using Q learning
Masuda et al. Optimization of delivery plan by quantum computing
CN114973656B (zh) 交通交互性能的评估方法、装置、设备、介质和产品

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 22962737

Country of ref document: EP

Kind code of ref document: A1