Abstract:

There are higher requirements for the timeliness of vegetable transportation and distribution. In order to solve the problems of long transportation time, high total transportation cost and short preservation time of vegetables during transportation, considering the constraints such as vehicle load and time window, this study proposed a genetic simulated annealing algorithm (GA-SA) for multi-objective vegetable distribution path optimization with time windows. That was, the simulated annealing algorithm (SA) adaptive (Metropolis) acceptance criterion was introduced into the operation process of genetic algorithm (GA). The basic idea was: First, the original population was selected, crossed and mutated by genetic algorithm to form a new generation of path population. At this time, by introducing metropolis acceptance criterion, and then, after modifying the sub situation of the new generation path population and selecting cross mutation, a new target path population was obtained. The improved algorithm retained the excellent individual, and the convergence speed, jumped out of the local optimal solution found based on genetic algorithm, and then found the global optimal solution. Then, the multi-objective of returning all vehicles to the distribution center after distribution was the least time-consuming, the lowest cost and the least use of vehicles was achieved, and the optimal path of vegetable transportation was obtained. Taking Baoding city in Hebei province as the distribution center and some towns under the jurisdiction of Baoding city as the distribution points, the experiment of vegetable transportation path optimization was designed. The experiments of genetic algorithm, simulated annealing algorithm and genetic simulated annealing algorithm were carried out, respectively. The comparative analysis was carried out from the aspects of convergence speed, total distance, total time, vehicles and total cost. The experimental results showed that, compared with the genetic algorithm and simulated annealing algorithm, GA-SA could effectively accelerate its convergence speed. The total cost of the optimized distribution route reduced by about 23.7% and 4% respectively, the total distance reduced by 22.6% and 3% respectively, the time consumption reduced by 26.2 and 2.6 hours respectively, and 2 and 1 vehicles were used less respectively. This study could also provide reference for the research of cold fresh food and other transportation path optimization.

Key words: genetic algorithm, Metropolis guidelines, vehicle routing problem, vegetable transportation, simulated annealing algorithm, time consuming, cost, path optimization