INFORMATION PROCESSING DEVICE, COMPUTER-READABLE RECORDING MEDIUM STORING INFORMATION PROCESSING PROGRAM, AND INFORMATION PROCESSING METHOD

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.