# US 2021/0239481 A1 · Information processing apparatus, recording medium, information processing method, and information processing system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0239481 A1
- Document ID: US20210239481A1
- Status: Published application
- Kind: A1
- Application number: 17/121,808
- Filed: 2020-12-15
- Published: 2021-08-05
- Earliest claimed: 2020-02-05
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Satoshi HANDA; Matthieu Parizy; Hidetoshi MATSUOKA
- Web page: https://patentgrep.com/patent/US20210239481A1

## CPC

- G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles}
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G01C 21/3492: {employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G08G 1/096827: {where the route is computed onboard}
- G08G 1/096844: {where the complete route is dynamically recomputed based on new data}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

A combinatorial optimization problem for acquiring a plurality of routes to be used by a traveling entity to visit a plurality of spot nodes and having a depot node as a starting point and end point of each of the routes is solved by a computer. The computer acquires a maximum number of spot nodes to be allocated to one route, determines the number of state variables to be used for formulating the combinatorial optimization problem based on the maximum number, generates, for the determined number of state variables, information on an objective function; and outputs the generated information on the objective function to a searching apparatus searching a ground state indicated by a set of the state variables included in the objective function.

## Claims

### Claim 1

An information processing apparatus comprising:
a memory, and
a processor coupled to the memory, and configure to:
acquire, for a combinatorial optimization problem for acquiring a plurality of routes to be used by a traveling entity to visit a plurality of spot nodes and having a depot node as a starting point and end point of each of the routes, a maximum number of spot nodes to be allocated to one route,
determine the number of state variables to be used for formulating the combinatorial optimization problem based on the maximum number,
generate, for the determined number of state variables, information on an objective function including a constraint term indicating that, after the traveling entity travels from the spot node to the depot node in each of the routes, traveling of the traveling entity to each of the plurality of spot nodes within the route is limited; and
output the generated information on the objective function to a searching apparatus searching a ground state indicated by a set of the state variables included in the objective function.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1, wherein in the determine,
allocate a first maximum number of spot nodes equal to the acquired maximum number to a first route of the plurality of routes and allocating an m-th (where m is an integer equal to or higher than 2) maximum number of spot nodes equal to or lower than an (m−1)th maximum number of spot nodes allocated to the (m−1)th route and higher than 0 to the m-th route of the plurality of routes, and
determine the number of the state variables based on the plurality of maximum numbers of spot nodes allocated to the plurality of routes.

### Claim 3 (depends on 2)

The information processing apparatus according to claim 2, wherein
in the acquire, acquire, as the maximum number, a maximum cumulative number of spot nodes having a cumulative demand amount not exceeding a capacity for demand amounts in the traveling entity, wherein the cumulative demand amount is acquired by accumulating, in increasing order, a plurality of demand amounts corresponding to the plurality of spot nodes, and
in the allocate, handle an integer part of a quotient, acquired by dividing the maximum cumulative number of spot nodes having a cumulative demand amount not exceeding the m times of the capacity by m, as the m-th maximum number of spot nodes to be allocated to the m-th route.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3, wherein
in the allocate, when the (m−1) times of the capacity is equal to or higher than a total of the plurality of demand amounts, handle an integer part of a quotient, acquired by dividing a second number acquired by subtracting a first number of the m-th and subsequent remaining routes from a total number of the plurality of spot nodes by (m−1), as the (m−1)th maximum number of spot nodes to be allocated to the (m−1)th route.

### Claim 5 (depends on 2)

The information processing apparatus according to claim 2, wherein in the allocate,
acquire a plurality of patterns each being a pattern of the numbers of a plurality of possible spot nodes for the plurality of routes where a total of the plurality of spot nodes belonging to the pattern is equal to the total number of the plurality of spot nodes,
extract a maximum value of the number of spot nodes corresponding to each of the routes from the plurality of patterns, and
handle the maximum value extracted for each of the routes as the maximum number of spot nodes to be allocated to the route.

### Claim 6 (depends on 2)

The information processing apparatus according to claim 2, wherein
a total of the plurality of maximum numbers of spot nodes is larger than a total number of the plurality of spot nodes.

### Claim 7 (depends on 1)

The information processing apparatus according to claim 1, wherein
the processor is further configured to add a state variable corresponding to a dummy depot node such that a number of the state variables is equal to a square of the total of the plurality of maximum numbers of spot nodes to be allocated to the plurality of routes based on the maximum number.

### Claim 8 (depends on 7)

The information processing apparatus according to claim 7, wherein in the output,
output identification information indicating a set of the four state variables having values to be changed for one state transition to the searching apparatus.

### Claim 9 (depends on 7)

The information processing apparatus according to claim 7, wherein the processor is further configured to set the constraint term to 0, when costs between the two spot nodes and between the spot node and the depot node satisfy triangle inequality.

### Claim 10

A non-transitory computer-readable recording medium having stored a program causing a computer to perform a process comprising:
acquiring, for a combinatorial optimization problem for acquiring a plurality of routes to be used by a traveling entity to visit a plurality of spot nodes and having a depot node as a starting point and end point of each of the routes, a maximum number of spot nodes to be allocated to one route,
determining the number of state variables to be used for formulating the combinatorial optimization problem based on the maximum number,
generating, for the determined number of state variables, information on an objective function including a constraint term indicating that, after the traveling entity travels from the spot node to the depot node in each of the routes, traveling of the traveling entity to each of the plurality of spot nodes within the route is limited; and
outputting the generated information on the objective function to a searching apparatus searching a ground state indicated by a set of the state variables included in the objective function.

### Claim 11

An information processing system comprising: an information processing apparatus and a searching apparatus, wherein
the information processing apparatus including:
a memory and a processor coupled to the memory and configured to:
acquire, for a combinatorial optimization problem for acquiring a plurality of routes to be used by a traveling entity to visit a plurality of spot nodes and having a depot node as a starting point and end point of each of the routes, a maximum number of spot nodes to be allocated to one route,
determine the number of state variables to be used for formulating the combinatorial optimization problem based on the maximum number,
generate, for the determined number of state variables, information on an objective function including a constraint term indicating that, after the traveling entity travels from the spot node to the depot node in each of the routes, traveling of the traveling entity to each of the plurality of spot nodes within the route is limited; and
output the generated information on the objective function,
and
the searching apparatus is configured to search a ground state indicated by a set of the state variables included in the objective function received from the information processing apparatus.