基于修正遗传算法的含服务费的车辆路径问题

Vehicle Rounting Problem with Service Cost Based on Modified Genetic Algorithm

在一般的带时间窗的集配货一体化问题研究的基础上增加了对装卸货产生的服务费的研究。通过推理计算求出包括服务费在内的各部分费用在总费用中所占权重,建立含服务费的带时间窗的集配货一体化车辆路径问题(VRPPDTW)模型。在求解时基于遗传算法并对算子做出修正,通过动态自适应技术修正交叉算子和引入2-opt操作修正变异算子,通过修正确保种群的多样性和稳定性并提高算法的求解效率。最后,通过数值例子对文章的模型和计算策略进行验证。结果显示:执行修正遗传算法(MGA)的最优成本为246.136;执行自适应规则确定交叉概率遗传算法(AGA)的最优成本为275.944 3;执行标准遗传算法(SGA)的最优成本为304.188 6;经过多次反复执行验证,使用修正遗传算法较其余两种算法更适合求解此模型。

Considering the vehicle loading and unloading cargo will bring cost in the process of delivery it increases the research of the service cost based on the traditional pick-up and delivery vehicle routing problem with time window.By calculating the each part of the cost to get the weight of the cost at the same time the model of VRPPDTW including the service cost is established.Then making modify to the operators based on genetic algorithm.Using dynamic adaptive technique to modify the crossover Through the above.In addition,introducing the 2-opt operator to modify the mutation operator.Through the above operators on one hand to ensure the diversity and the stability of the population on the other hand to improve the efficiency of the algorithm.At last,a numerical example is given to verify the model and the calculation method.The results showed that the optimal cost of executing the modified genetic algorithm（MGA） is 246.136.The optimal cost of executing the adaptive genetic algorithm（AGA） is 275.944 3.The optimal cost of executing the standard genetic algorithm（SGA） is 304.188 6.The optimal solution changes little after executing repeatedly.It can be concluded that using the modified genetic algorithm is more suitable than another two for solving this model.