Development of a genetic method for solution of routing problems with several transport

• Date: 2023
• Main Authors: Федорченко, Є. М., Олійник, А. О., Степаненко, О. О., Зайко, Т. А., Шило, С. І., Нестеров, Г. Д.
• Format: Article
• Language: Ukrainian
• Published: Інститут проблем реєстрації інформації НАН України 2023
• Subjects: metaheuristic algorithms; genetic algorithm; optimization; tabu search algorithm; vehicle routing problem
• Online Access: http://drsp.ipri.kiev.ua/article/view/300589
• Journal Title: Data Recording, Storage & Processing

A modified genetic method has been developed to solve routing problems with weighted constraints and multiple transportation means. The fundamental difference of this developed genetic method from existing modifications lies in the use of a diploid set of chromosomes in the population of evolving indivi-duals. This modification makes the dependence of an individual's phenotype on its genotype less deterministic and, as a result, promotes the preservation of population genetic diversity and phenotypic variability throughout the execution of the method. The result of such modification is the maintenance of a sufficiently high variability of traits (genes) in the population (gene pool of the population) during evolution, which, at the same time, may have a minor impact on the individual's phenotype. A modification of the genetic mutation operator has been proposed. Unlike the classical method, individuals subjected to the mutation operator are selected not randomly, but according to their mutation resistance, corresponding to the value of the individual's fitness function. Thus, «weaker» individuals mutate, while the genome of «strong» individuals remains unchanged. In this case, the likelihood of losing the achieved extremum of the function during the action of the mutation operator decreases, and the transition to a new extremum occurs in case of accumulation of sufficient specific weight of «better» traits in the population. This modification of the operator allows for the search of values approximating the optimal ones, excluding the loss of acquired advantages during the search for better solutions. Tabl.: 1. Fig.: 3. Refs: 36 titles.