Information processing device, computer-readable recording medium storing information processing program, and information processing method

Patent metadata

Field	Value
Publication number	US-12235115-B2
Application number	US-202318152793-A
Country	US
Kind code	B2
Filing date	Jan 11, 2023
Priority date	Apr 28, 2022
Publication date	Feb 25, 2025
Grant date	Feb 25, 2025

Abstract

An information processing device of: generating first routes satisfying a first condition; calculating a first index of each node based on a cost of each edge; generating a second route arriving at each node from a starting point and satisfying a second condition; generating a third route satisfying the second condition by adding the edge to the second route; calculating a second index being a difference between a total value of the first index and the cost of the second and third routes; updating the second route when the second index of the third route is smaller than the second index of the second route; excluding the edge having not contributed to the updating more than a predetermined number of times; and outputting a route with the smallest second index, the first index representing a degree of reduction of the cost in a linearly relaxed problem of the routing problem.

First claim

What is claimed is:

1. An information processing device comprising:
a memory; and
a processor coupled to the memory, the processor being configured to perform processing including:
generating a plurality of first routes that satisfies a first condition out of a plurality of conditions included in a vehicle routing problem;
calculating a first index of each of nodes on a basis of a cost of each edge between each of the nodes of the first route;
generating, as an optimum route, a second route that arrives at each of the nodes from a starting point and satisfies a second condition out of the plurality of conditions by combining the edge;
generating a third route that satisfies the second condition by adding the edge to the second route;
calculating, for each route of the second rote and the third route, a second index that is a difference between a total value of the first index and the cost of the each route;
updating the optimum route when the second index of the third route is smaller than the second index of the second route that arrives at a same node as the third route;
excluding the edge that has not contributed to the updating of the optimum route equal to or more than a predetermined number of times from a target to be added to each route; and
outputting a route with the smallest second index as a route candidate by repeating the adding of the edge to the optimum route, the calculating of the second index, and the updating of the optimum route until the route returns to the starting point, wherein
the first index includes an index that represents a degree of reduction of the cost in a linearly relaxed problem of the vehicle routing problem.

2. The information processing device according to claim 1 , wherein
the updating the optimum route includes updating the optimum route to the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third route, and
the outputting the route candidate includes selecting, as the route candidate, the route with the smallest second index out of the optimum route that returns to the starting point.

3. The information processing device according to claim 1 , wherein
the updating the optimum route includes updating the optimum route to the third route with the smallest second index out of the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third route, and
the outputting the route candidate includes outputting the optimum route that returns to the starting point as the route candidate.

4. A non-transitory computer-readable storage medium storing an information processing program for causing a computer to perform processing comprising:
generating a plurality of first routes that satisfies a first condition out of a plurality of conditions included in a vehicle routing problem;
calculating a first index of each of nodes on a basis of a cost of each edge between each of the nodes of the first route;
generating, as an optimum route, a second route that arrives at each of the nodes from a starting point and satisfies a second condition out of the plurality of conditions by combining the edge;
generating a third route that satisfies the second condition by adding the edge to the second route;
calculating, for each route of the second rote and the third route, a second index that is a difference between a total value of the first index and the cost of the each route;
updating the optimum route when the second index of the third route is smaller than the second index of the second route that arrives at a same node as the third route;
excluding the edge that has not contributed to the updating of the optimum route equal to or more than a predetermined number of times from a target to be added to each route; and
outputting a route with the smallest second index as a route candidate by repeating the adding of the edge to the optimum route, the calculating of the second index, and the updating of the optimum route until the route returns to the starting point, wherein
the first index includes an index that represents a degree of reduction of the cost in a linearly relaxed problem of the vehicle routing problem.

5. The non-transitory computer-readable storage medium according to claim 4 , wherein
the updating the optimum route includes updating the optimum route to the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third route, and
the outputting the route candidate includes selecting, as the route candidate, the route with the smallest second index out of the optimum route that returns to the starting point.

6. The non-transitory computer-readable storage medium according to claim 4 , wherein
the updating the optimum route includes updating the optimum route to the third route with the smallest second index out of the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third route, and
the outputting the route candidate includes outputting the optimum route that returns to the starting point as the route candidate.

7. An information processing method implemented by a computer, the information processing method comprising:
generating a plurality of first routes that satisfies a first condition out of a plurality of conditions included in a vehicle routing problem;
calculating a first index of each of nodes on a basis of a cost of each edge between each of the nodes of the first route;
generating, as an optimum route, a second route that arrives at each of the nodes from a starting point and satisfies a second condition out of the plurality of conditions by combining the edge;
generating a third route that satisfies the second condition by adding the edge to the second route;
calculating, for each route of the second rote and the third route, a second index that is a difference between a total value of the first index and the cost of the each route;
updating the optimum route when the second index of the third route is smaller than the second index of the second route that arrives at a same node as the third route;
excluding the edge that has not contributed to the updating of the optimum route equal to or more than a predetermined number of times from a target to be added to each route; and
outputting a route with the smallest second index as a route candidate by repeating the adding of the edge to the optimum route, the calculating of the second index, and the updating of the optimum route until the route returns to the starting point, wherein
the first index includes an index that represents a degree of reduction of the cost in a linearly relaxed problem of the vehicle routing problem.

8. The information processing method according to claim 7 , wherein
the updating the optimum route includes updating the optimum route to the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third route, and
the outputting the route candidate includes selecting, as the route candidate, the route with the smallest second index out of the optimum route that returns to the starting point.

9. The information processing method according to claim 7 , wherein
the updating the optimum route includes updating the optimum route to the third route with the smallest second index out of the third route when the second index of the third route is smaller than the second index of the second route that arrives at the same node as the third rou

Assignees

• Fujitsu Ltd

Inventors

• Ito Yuto

Classifications

• G01C21/343

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title

• G01C21/3415 Primary

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G06Q10/047 Primary

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

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title