两阶段BSO-SA算法求解带单边软时间窗的多车型VRP问题

Two-stage BSO-SA Algorithm for Fleet Size and Mixed Vehicle Routing Problem with Unilateral Soft Time Window

在标准头脑风暴算法(BSO)的基础上,提出了一种新的两阶段头脑风暴退火算法(BSO-SA).根据多车型问题,设计了基于贪婪算法的编解码形式.使用K-medoids聚类代替BSO算法中的Kmeans聚类,以提高算法聚类性能.同时,采用了四种局部搜索算子,提高新解的产生效率.两阶段求解思路,解决了BSO算法容易陷入局部最优值和SA算法收敛较慢的问题.使用三个不同规模的算例用于验证,并与模拟退火、遗传算法、头脑风暴算法进行对比,结果验证了该算法的有效性.

Based on the standard brainstorming algorithm (BSO), a new two-stage brainstorming annealing algorithm (BSO-SA) was proposed. According to the multi-vehicle problem, a coding and decoding form based on greedy algorithm was designed. Kmeans clustering in BSO algorithm was replaced by Kmedoids clustering to improve the clustering performance of the algorithm. Meanwhile, four local search operators were adopted to improve the efficiency of generating new solutions. The idea of two-stage solution solves the problems that BSO algorithm is easy to fall into local optimum and SA algorithm converges slowly. Three numerical examples with different scales are used for verification, and compared with simulated annealing, genetic algorithm and brainstorming algorithm. The results show that the algorithm is effective.