供应链中车辆路径问题的改进模拟退火算法

Improved simulated annealing algorithm for vehicle routing problem in supply chain

车辆路径的优化是供应链优化中的重要环节。设计了一种改进的模拟退火算法用于求解有客户需求、车辆最大载重量和最大行驶距离三个约束条件的车辆路径问题。主要改进在于:编码方案采用客户编号的顺序编码,并设计专门的解码方法能够把三种约束全都纳入考虑,再综合运用三种邻域生成算子提高局部搜索能力,采用基本的线性降温方式控制降温过程。运用此算法针对同一算例,采用三种不同的降温系数进行了仿真实验,得到了更好的配送方案。实验结果表明该算法不仅求解速度快,而且寻优能力也有显著增强。

The optimization of vehicle route is an important link in supply chain optimization. An improved simulated annealing algorithm is designed to solve the vehicle routing problem with following three constraints:customer demand, maximum load and maximum distance of vehicles. Main improvement includes:using the order of the customer code in encoding scheme, designing a special decoding method which can take all three constraints into account, comprehensively applying three kinds of operators in neighborhood generation to improve local search ability, adopting basic linear cooling method to control the cooling process. Three simulation experiments are conducted for the same calculation example. Each of them has a different cooling coefficient, and a better delivery scheme is achieved in each experiment. Experimental results show that the proposed algorithm is not only fast, but also has a conspicuous increase in search ability.