Ising solver system

Patent metadata

Field	Value
Publication number	US-11710059-B2
Application number	US-202016816431-A
Country	US
Kind code	B2
Filing date	Mar 12, 2020
Priority date	Mar 14, 2019
Publication date	Jul 25, 2023
Grant date	Jul 25, 2023

Abstract

An ising solver system that searches an optimal route of a vehicle from plural routes passing through plural locations. In the ising solver system, the search of the optimal route uses a Hamiltonian. The Hamiltonian includes an equation representing an interaction between Quadratic Unconstrained Binary Optimization (QUBO) variables depending on a relation between a departure location and an arrival location or capacitated variable of the ising solver. The capacitated variable corresponds to one of the QUOBO variables and includes a variable constraint, and the location-to-location travel step number corresponds to an accumulated movement time of the vehicle.

First claim

The invention claimed is:

1. A route search system comprising:
a plurality of vehicles each of which travels through a plurality of locations; and
a computer programmed to calculate an optimal route for the vehicles by executing an Ising Algorithm using a Hamiltonian, wherein
the Hamiltonian includes a plurality of interaction terms representing an interaction between a plurality of variables of Quadratic Unconstrained Binary Optimization (QUBO),
the interaction depends on a relation between a departure location and an arrival location,
the Hamiltonian includes (a) a concept of a location-to-location travel step number of the Ising Algorithm or (b) a capacitated variable of the Ising Algorithm,
the capacitated variable corresponds to one of the variables of the QUBO and includes a variable constraint,
the location-to-location travel step number corresponds to an accumulated movement time of each vehicle of the plurality of vehicles, and
the computer is programmed to
generate a traveling schedule based on the calculated optimal route, and
present the generated traveling schedule or control traveling of the each vehicle of the plurality of vehicles based on the generated traveling schedule.

2. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm includes a point in time.

3. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm monotonically increases or decreases.

4. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm is associated with an arrival location and is able to change positively or negatively.

5. The route search system according to claim 1 , wherein:
in the Ising Algorithm, the capacitated variable allowed to vary positively or negatively includes a state variable.

6. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm includes a point in time; and
the capacitated variable of the Ising Algorithm includes addition of positive change or negative change of a capacity associated with an arrival location and a state variable.

7. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm monotonically increases or decreases; and
the capacitated variable capable of increasing or decreasing includes a state variable.

8. The route search system according to claim 1 , wherein:
a location that is not reachable is set by introducing the interaction.

9. The route search system according to claim 1 , wherein:
a basic constraint and a parameter are set by introducing the interaction.

10. The route search system according to claim 1 , wherein:
a cost of the Ising Algorithm depends on a time point or the capacitated variable that monotonically increases or decreases.

11. The route search system ising solver system according to claim 1 , wherein:
a schedule time unit in a timetable of the Ising Algorithm has a time point dependency.

12. The route search system according to claim 1 , wherein:
a schedule time unit in a timetable of the Ising Algorithm has a vehicle type dependency.

13. The route search system according to claim 1 , wherein:
the capacitated variable of the Ising Algorithm is different from a cost.

14. The route search system according to claim 1 , wherein:
an arrival allowance to at least one of the plurality of locations is set in accordance with a time point or the capacitated variable that monotonically increases or decreases.

15. The route search system according to claim 1 , wherein:
a range of a time point of the Ising Algorithm or a range of a capacity that monotonically increases or decreases differs for each of the plurality of vehicles.

16. The route search system according to claim 1 , wherein:
the plurality of vehicles includes a first vehicle and a second vehicle; and
when, in the Ising Algorithm, a time point of the first vehicle or the capacitated variable that is used for the first vehicle and monotonically increases or decreases is in an identical range to a range of the second vehicle, the second vehicle does not visit a location that the first vehicle visits.

17. The route search system according to claim 1 , wherein:
in the Ising Algorithm, arrival allowance or arrival rejection of a specific vehicle to the plurality of locations is set.

18. The route search system according to claim 1 , wherein:
the interaction includes an interaction that generates a tendency for equally assigning a variable associated with each of the plurality of locations to each vehicle.

19. The route search system according to claim 1 , wherein the capacitated variable is at least a loading capacity of the each vehicle.

20. The route search system according to claim 19 , wherein the loading capacity is set according to a type of the each vehicle.

21. The route search system according to claim 1 , wherein
the computer includes:
an input configured to receive input data including at least one of:
(i) cost data indicating a cost caused by the each vehicle of the plurality of vehicles traveling through the plurality of locations,
(ii) traveling time data indicating a time of traveling of the each vehicle of the plurality of vehicles,
(iii) package data indicating size or weight of a package,
(iv) vehicle data indicating at least one of a capacity, a weight, or a vehicle type of the each vehicle of the plurality of vehicles,
(v) limit data indicating at least one of a time limit for delivery, a capacity limit, or a weight limit of the each vehicle of the plurality of vehicles, or
(vi) driver data indicating a work time of a driver for the each vehicle of the plurality of vehicles;

a processor programmed to execute the Ising Algorithm by inputting the input data into the Ising Algorithm; and
an output configured to output the calculated optimal route.

22. The route search system according to claim 1 , wherein
the computer includes a display screen configured to display the generated traveling schedule.

23. The route search system according to claim 1 , wherein
the plurality of variables of the QUBO depend on at least:
(1) a variable representing the locations which the each vehicle travels through; and
(2-i) a variable representing an accumulated movement step number of the each vehicle, or
(2-ii) a variable representing an accumulated loading amount of the each vehicle of the plurality of vehicles, and
the plurality of interaction terms of the Hamiltonian include:
a first interaction term between two first variables of the plurality of variables of the QUBO, each of the two first variables representing the departure location or the arrival location, respectively; and
a second interaction term between two second variables of the plurality of variables of the QUBO, each of the second variables corresponding to a total of the location-to-location travel step number or a third interaction term between two third variables of the plurality of variables of the QUBO, each of the third variables corresponding to a loading amount change due to the traveling between one of the locations and another of the locations.

Assignees

• Denso Corp
• Toyota Tsusho Corp

Inventors

• Irie Hirotaka
• Miki Akira
• Terabe Masayoshi
• Awashima Toru
• Takahashi Shunsuke
• Goragot Wongpaisarnsin
• Dungjade Shiowattana

Classifications

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G08G1/096844

  where the complete route is dynamically recomputed based on new data · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title