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

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

作　　者：梁学恒 杨家其[1] 向子权 LIANG Xueheng;YANG Jiaqi;XIANG Ziquan(School of Transportation and Logistics Engineering,Wuhan University of Technology,Wuhan 430063,China)

机构地区：[1]武汉理工大学交通与物流工程学院,武汉430063

出　　处：《武汉理工大学学报（交通科学与工程版）》2024年第1期19-24,共6页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：中央高校基本科研业务费专项资金(215202003)。

摘　　要：在标准头脑风暴算法(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.

关 键 词：车辆路径优化 头脑风暴算法 两阶段 单边软时间窗 

分 类 号：U491.112[交通运输工程—交通运输规划与管理]