基于多目标模拟退火的带容量限制车辆路径问题

Capacitated Vehicle Routing Problem Based on Multi-Objective Simulated Annealing

车辆路径问题是运筹学中著名的NP问题。带容量限制的车辆路径问题作为最基本的车辆路径问题,其研究对其它类型的车辆路径问题具有重要的借鉴作用。论文首先从物流企业和客户两个不同的角度考察4个优化目标,将带容量限制的车辆路径问题推广到高维多目标领域。然后运用基于Pareto支配接受准则的多目标模拟退火算法在单数组和多数组两种不同的编码方式下进行求解,并通过实验分析对比两种编码方式的优劣。在9个Augerat数据集上的实验结果表明,单数组编码方式在IGD和HV指标下不如多数组编码方式。单数组编码方式得到的Pareto解集具有更好的多样性,而多数组编码方式得到的Pareto解集具有更好的收敛性。

Vehicle routing problem is a well-known NP problem in operations research. As the most basic vehicle routing prob-lem,the research of capacitated vehicle routing problem has important reference for other types of vehicle routing problems. In this paper,four optimization functions are firstly inspected from the view of logistics enterprise and customer,which extends the capaci-tated vehicle routing problem to many-objective field. Then,the multiobjective simulated annealing using Pareto-domination based acceptance criterion is used to solve this problem under single-array encoding and multi-array encoding. The advantages and disad-vantages of these two methods are analyzed with experiment. The experiments on nine Augerat datasets show that the single-array en-coding method is better than the multi-array encoding method with the measure of IGD and HV. The Pareto set obtained by the sin-gle-array encoding method has better diversity and worse convergence than that obtained by the multi-array encoding method.