基于多目标VRP的离散型萤火虫算法研究

Multi-objective vehicle routing problem based on discrete glowworm swarm optimization algorithm

以车辆路径问题为准,对萤火虫算法进行研究。建立了以最小化车辆数量和行驶路程为目标的多目标规划数学模型,提出一种结合变邻域搜索算法的离散型萤火虫算法。该离散型萤火虫算法的特色之处在于:重新定义了个体的生成方式和距离移动方式;采用变邻域搜索技术以增强算法的邻域搜索能力;在搜索过程中采用随机个体替代种群中的重复个体以维持种群的多样性;采取精英策略记录迭代过程中的最优解。通过不同规模的Solomon算例进行仿真实验,结果表明所提算法无论是在车辆数量还是行驶路程的求解质量都取得了很好的效果。

In this paper,the multi-objective mathematical model is established in order to minimize the number of vehicles and driving distance in vehicle routing problem,and a discrete glowworm swarm optimization algorithm（ DGSO） combined with variable neighborhood search is proposed. The characteristic of DGSO algorithm is that individual generation and movement mode are redefined; variable neighborhood search technique is adopted to balance the global search ability and local development ability of the algorithm; random individuals take place of repeated individuals in order to maintain the diversity of the population in the search process; the elite strategy records the optimal solution in the iterative process. Simulation results for different scale Solomon cases show that DGSO algorithm both in the number of vehicles and driving distance have achieved good results.