A modified genetic algorithm for solving routing problems with weight constraints and multiple vehicles is developed. The fundamental difference between the developed genetic algorithm and existing modifications is the use of a diploid set of chromosomes in individuals of the evolving population. Such a modification makes the dependence of an individual’s phenotype on genotype less deterministic and, as a result, helps to preserve the diversity of the population’s gene pool and the variability of phenotype traits during the algorithm’s execution. The result of such a modification is a maintenance of sufficiently high variability of traits (genes) in the population gene pool during evolution, while possibly having a small effect on the phenotype of individuals. A modification of the genetic mutation operator is proposed. In contrast to the classical method, individuals subjected to the mutation operator are not randomly selected, but in accordance with their mutational resistance, which corresponds to the value of the fitness function of the individual. As such, “weaker” individuals mutate, while the genome of “strong” individuals remains unchanged. In this case, the probability of losing the extremum of the function achieved during evolution due to the action of the mutation operator decreases, and the transition to a new extremum is carried out in the case of accumulation of a sufficient proportion of the “best” traits in the population. Such a modification of the operator allows searching for optimal values, excluding the loss of the acquired ones during the search for better solutions.