An information processing apparatus for generating routes constituting a subset that is subjected to optimization in a vehicle routing problem, the subset being part of an entire set that contains all possible routes in the vehicle routing problem, comprising: a route generating unit configured to generate a plurality of routes, as the subset, for delivering packages in a vehicle routing problem; an arithmetic unit configured to obtain a first optimum solution of the vehicle routing problem with respect to the plurality of routes, the first optimum solution being obtained for an integer programming problem of the vehicle routing problem, the integer programming problem being a problem in which a variable indicative of a choice of a given route in the vehicle routing problem is a binary variable having a value of 0 or 1; a solution evaluating unit configured to determine whether a difference between an objective function value of the first optimum solution and an objective function value of a second optimum solution is greater than or equal to a first threshold value, the second optimum solution being obtained for a linear relaxation problem of the vehicle routing problem with respect to the plurality of routes, the linear relaxation problem being a problem in which the variable indicative of a choice of a given route in the vehicle routing problem is a real number value greater than or equal to zero; and a route removing unit configured to remove, when the difference is greater than or equal to the first threshold value, from among the plurality of routes, one or more routes for which the variable indicative of a choice of a corresponding route is less than or equal to a second threshold value in the second optimum solution, wherein the route generating unit generates one or more new routes for delivering packages other than packages that are to be delivered by one or more routes which are left remaining among the plurality of routes. a route generating unit configured to generate a plurality of routes, as the subset, for delivering packages in a vehicle routing problem; an arithmetic unit configured to obtain a first optimum solution of the vehicle routing problem with respect to the plurality of routes, the first optimum solution being obtained for an integer programming problem of the vehicle routing problem, the integer programming problem being a problem in which a variable indicative of a choice of a given route in the vehicle routing problem is a binary variable having a value of 0 or 1; a solution evaluating unit configured to determine whether a difference between an objective function value of the first optimum solution and an objective function value of a second optimum solution is greater than or equal to a first threshold value, the second optimum solution being obtained for a linear relaxation problem of the vehicle routing problem with respect to the plurality of routes, the linear relaxation problem being a problem in which the variable indicative of a choice of a given route in the vehicle routing problem is a real number value greater than or equal to zero; and a route removing unit configured to remove, when the difference is greater than or equal to the first threshold value, from among the plurality of routes, one or more routes for which the variable indicative of a choice of a corresponding route is less than or equal to a second threshold value in the second optimum solution, wherein the route generating unit generates one or more new routes for delivering packages other than packages that are to be delivered by one or more routes which are left remaining among the plurality of routes.