INFORMATION PROCESSING APPARATUS, ROUTE GENERATION METHOD, AND NON-TRANSITORY COMPUTER-READABLE STORAGE MEDIUM

An information processing apparatus includes a processor. The processor configured to generate a plurality of routes satisfying a first condition among a plurality of conditions included in a vehicle routing problem The processor, when a total cost for each route satisfying a second condition among the plurality of conditions is calculated from the plurality of routes, performs narrowing-down on the plurality of routes based on the total cost and a value that is set for the route, the value indicating whether or not the route satisfies the second condition and being set to a real number which is equal to or greater than 0 and equal to or smaller than 1 by linear relaxation. The processor calculates a route satisfying the first condition and the second condition based on information on the plurality of routes narrowed down.