混合乌鸦算法求解带软时间窗的车辆路径问题  

Hybrid crow algorithm for solving vehicle routing problemwith soft time windows

作　　者：闫龙 石小娟 唐源 YAN Long;SHI Xiao-juan;TANG Yuan(School of Management Science and Engineering,Shandong Technology and Business University,Yantai 264005,China)

机构地区：[1]山东工商学院管理科学与工程学院,山东烟台264005

出　　处：《计算机工程与设计》2023年第12期3656-3661,共6页Computer Engineering and Design

基　　金：教育部协同育人基金项目(202101398034);教育部人文社会科学研究规划基金项目(21YJCZH077);山东省研究生导师指导能力提升计划基金项目(SDYY18176)。

摘　　要：为求解带软时间窗的车辆路径问题,提出一种混合乌鸦搜索算法(hybrid crow search algorithm, HCSA)。设计最小惩罚成本与最小距离成本两种种群初始化规则,根据乌鸦在搜寻食物时的确定性搜索与随机性搜索两种智能搜索行为,将固定感知概率改进为可自适应调整的动态参数,引入自适应大规模邻域搜索策略,设计多种确定性与随机性邻域搜索算子。与已有文献算例结果及Solomon测试数据库进行对比,其结果表明,HCSA的优化质量优于其它文献算法,可有效求解带软时间窗的车辆路径问题。To solve the vehicle routing problem with soft time windows(VRPSTW),a hybrid crow search algorithm(HCSA)was proposed.The design on the two population initialization rules of the minimum penalty cost and the minimum distance cost was carried out.In line with the two kinds of intelligent search behaviors of crows when searching for food,such as the deterministic search and random search,the fixed perception probability was improved into a dynamic parameter that could be adjusted adaptively.The adaptive large neighborhood search(ALNS)strategy was introduced to design a variety of deterministic and random neighborhood search operators.Through the contrast with the results of the existing literature instances and that of Solomon benchmark set,it indicates that the optimization quality of HCSA is better than that of other literature algorithms in accor-dance with the results,which is able to effectively solve the vehicle routing problem with soft time windows.

关 键 词：软时间窗 车辆路径问题 惩罚成本 乌鸦搜索算法 种群初始化 感知概率 自适应大规模邻域搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]