改进遗传算法求解带时间窗的外卖配送车辆路径规划

Solving the Delivery Vehicle Routing Problem with Time Window by Improved Genetic Algorithm

对带时间窗的外卖配送车辆路径规划问题,必须“先取餐再送餐”的准则制约了遗传算法求解时染色体基因的随机性,对此提出了一种改进遗传算法.首先基于配对互换策略设计了染色体基因修复算子,有效消除了不可行解;然后设计了基于种群平均适应度的自适应交叉和变异策略,使得在遗传进化初期个体适应度低于种群平均适应度时会获得较高的交叉变异概率,提高种群多样性,而在进化后期个体适应度高于种群平均适应度时交叉变异概率快速下降,避免破坏优势个体,保证收敛效果.仿真实验表明,与标准遗传算法和标准蚁群算法相比,改进遗传算法的求解结果和遗传进化效率均更优,算法性能在平均值、方差等方面也明显优于另外两种算法,因此算法改进是有效和实用的.

For the delivery vehicle routing problem with time Window,the rule of"fetch food before delivery"restricts the randomness of chromosomal genes when solving by genetic algorithm,for this,an improved genetic algorithm is proposed.At first,the chromosome gene repair operator based on the pairing swap strategy is designed,which effectively eliminates infeasible solutions.Then,an adaptive crossover and mutation probability based on the average fitness of the population is designed,so that when the individual fitness is lower than the average fitness of the population in the early stage of genetic evolution,a higher crossover and mutation probability will be obtained,and the population diversity will be improved.When the individual fitness is higher than the average fitness of the population in the late stage of evolution,the crossover and mutation probability will decrease rapidly to avoid destroying the best individuals,the convergence effect is guaranteed.The simulation results show that,compared with the standard genetic algorithm and the standard ant colony algorithm,the improved genetic algorithm has better solution results and genetic evolution efficiency,and the algorithm performance is also significantly better than the other two algorithms in terms of average value and variance,so the algorithm improvement is effective and practical.