# US 2025/0085118 A1 · Computer-readable recording medium storing information processing program, information processing method, and information processing device

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

- Number: US 2025/0085118 A1
- Document ID: US20250085118A1
- Status: Published application
- Kind: A1
- Application number: 18/768,104
- Filed: 2024-07-10
- Published: 2025-03-13
- Earliest claimed: 2023-09-12
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Keiji KIMURA
- Web page: https://patentgrep.com/patent/US20250085118A1

## CPC

- G01C 21/34: Route searching; Route guidance
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 10/0631: Resource planning, allocation, distributing or scheduling for enterprises or organisations
- 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

## Abstract

A non-transitory computer-readable recording medium storing an information processing program for causing a computer to execute processing including: generating routes in a case where a plurality of mobile bodies that have started from a specific node passes through a plurality of nodes and returns to the specific node, which satisfy a plurality of newly set conditions related to the routes, from a set of the plurality of routes that indicates order in which the plurality of mobile bodies visit the nodes, by applying a column generation method to the set of the plurality of routes; generating a route selection problem by using the generated routes; solving the generated route selection problem; and outputting a solution result of the route selection problem.

## Claims

### Claim 1

A non-transitory computer-readable recording medium storing an information processing program for causing a computer to execute processing comprising:
generating routes in a case where a plurality of mobile bodies that have started from a specific node passes through a plurality of nodes and returns to the specific node, which satisfy a plurality of newly set conditions related to the routes, from a set of the plurality of routes that indicates order in which the plurality of mobile bodies visit the nodes, by applying a column generation method to the set of the plurality of routes;
generating a route selection problem by using the generated routes;
solving the generated route selection problem; and
outputting a solution result of the route selection problem.

### Claim 2 (depends on 1)

The non-transitory computer-readable recording medium according to claim 1, wherein
the plurality of newly set conditions includes a route constraint that indicates a constraint condition for each route, which does not depend on another route, and
in the processing of generating the routes, routes that satisfy the route constraint and minimize a value of an objective function related to the routes are generated.

### Claim 3 (depends on 2)

The non-transitory computer-readable recording medium according to claim 2, wherein
the plurality of newly set conditions includes a mobile body number constraint related to the number of mobile bodies that pass through a route, and
in the processing of generating the routes, routes that minimize the value of the objective function within a range that satisfies the mobile body number constraint are generated.

### Claim 4 (depends on 3)

The non-transitory computer-readable recording medium according to claim 3, wherein the plurality of newly set conditions includes a definition related to a cost of the route, and in the processing of generating the routes, routes that minimize the value of the objective function are generated by using a cost of the route calculated based on the definition.

### Claim 5 (depends on 4)

The non-transitory computer-readable recording medium according to claim 4, wherein
the plurality of newly set conditions includes a definition of a travel time of the route, and
in the processing of generating the routes, the routes are generated by further using a cost of the route based on the travel time, the mobile body number constraint based on the travel time, and a route constraint based on the travel time.

### Claim 6

An information processing method implemented by a computer, the information processing method comprising:
generating routes in a case where a plurality of mobile bodies that have started from a specific node passes through a plurality of nodes and returns to the specific node, which satisfy a plurality of newly set conditions related to the routes, from a set of the plurality of routes that indicates order in which the plurality of mobile bodies visit the nodes, by applying a column generation method to the set of the plurality of routes;
generating a route selection problem by using the generated routes;
solving the generated route selection problem; and
outputting a solution result of the route selection problem.

### Claim 7

An information processing apparatus comprising:
a memory; and
a processor coupled to the memory, the processor being configured to perform processing comprising:
generating routes in a case where a plurality of mobile bodies that have started from a specific node passes through a plurality of nodes and returns to the specific node, which satisfy a plurality of newly set conditions related to the routes, from a set of the plurality of routes that indicates order in which the plurality of mobile bodies visit the nodes, by applying a column generation method to the set of the plurality of routes;
generating a route selection problem by using the generated routes;
solving the generated route selection problem; and
outputting a solution result of the route selection problem.
