A technique for solving combinatorial problems, such as vehicle routing for multiple vehicles integrates evolutionary algorithms and reinforcement learning. A genetic algorithm maintains a set of solutions for the problem and improves the solutions using mutation (modify a solution) and crossover (combine two solutions). The best solution is selected from the improved set of solutions. A system that integrates evolutionary algorithms, such as a genetic algorithm, and reinforcement learning comprises two components. A first component is a beam search technique for generating solutions using a reinforcement learning model. A second component augments a genetic algorithm using learning-based solutions that are generated by the reinforcement learning model. The learning-based solutions improve the diversity of the set which, in turn, improves the quality of the solutions computed by the genetic algorithm.