Abstract: Based on the delivery route planning of chain convenience stores under soft time windows, a multichromosome genetic algorithm with time windows for such scenarios is proposed to solve the problem of single distribution center with multiple types of vehicles under dense semisoft time windows, and its feasible solution of preventing falling into local optimal solution is discussed. For the abovementioned delivery route planning problem, the proposed multichromosome genetic algorithm solves the optimal route under the goal of reducing vehicle transportation cost and penalty cost, and proposes an optimization plan for vehicle and route selection for the chain convenience store's route planning case. Finally, the algorithm is compared with the traditional genetic algorithm. The experimental results show that this algorithm significantly reduces the total delivery cost in comparison to the traditional genetic algorithm under the dense semisoft time window, thus verifying the effectiveness of the algorithm.

Key words: soft time window, vehicle routing optimization, genetic algorithm, heterogeneous fleet, multiple chromosomes