融合多策略蜣螂优化算法的外卖订单配送路径优化  

Dung Beetle Optimization Algorithm Integrating Multiple Strategies for Take-out Order Distribution Route Optimization

作　　者：杨俞沣 夏小云 陈泽丰 廖伟志 李积武 YANG Yufeng;XIA Xiaoyun;CHEN Zefeng;LIAO Weizhi;LI Jiwu(School of Computer Science and Technology,Zhejiang Normal University,Jinhua 321004,China;School of Information Science and Engineering,Jiaxing University,Jiaxing 314001,China;School of Artificial Intelligence,Sun Yat-sen University,Zhuhai 519082,China)

机构地区：[1]浙江师范大学计算机科学与技术学院,浙江金华321004 [2]嘉兴大学信息科学与工程学院,浙江嘉兴314001 [3]中山大学人工智能学院,广东珠海519082

出　　处：《计算机与现代化》2024年第9期25-32,共8页Computer and Modernization

基　　金：国家自然科学基金资助项目(62206313,61703183);浙江省自然科学基金资助项目(LGG19F030010);浙江省普通本科高校“十四五”教学改革项目(jg20220434);浙江省重点研发攻关计划项目(2023C04008);嘉兴大学“勤慎青年学者”培养计划项目(嘉院人字[2023]12号)。

摘　　要：随着外卖行业的发展,外卖平台要在大量候选订单中选择并规划出高效的配送路线。为了满足外卖平台和顾客的需求,建立以配送成本最小和顾客时间满意度最大为目标的优化模型。采用蜣螂优化算法进行求解,针对蜣螂优化算法易陷入局部最优和求解质量低等问题,通过引入模拟多项式变异策略、模拟退火概率突跳算子和单纯形法局部搜索策略,提出一种融合多策略的增强蜣螂优化算法(Improved Dung Beetle Optimizer,IDBO)。测试算例的求解结果与其它算法相比,IDBO算法的最优解、均值、标准差、成本和满意度更好。仿真实验表明,3种改进策略均能提高算法的寻优能力,可有效求解模型。With the development of takeaway industry,takeaway platforms have to select and plan efficient delivery routes among a large number of candidate orders.In order to satisfy the needs of both takeaway platforms and customers,an optimization model is established with the objectives of minimizing the delivery cost and maximizing the customer’s time satisfaction.The dung beetle optimization algorithm is used for solving the problem.Aiming at the problems that dung beetle optimization algorithm is prone to local optimization and low solving quality,a multi-strategy enhanced dung beetle optimization algorithm,named IDBO(Improved Dung Beetle Optimizer)is proposed by introducing simulated polynomial mutation strategy,simulated annealing probability jump operator and simplex local search strategy.The solution results obtained on randomly generated test cases show that the IDBO algorithm achieves better optimal solution,mean,standard deviation,cost and satisfaction compared to other algorithms.The simulation results show that the three improvement strategies can improve the optimization ability of the algorithm and solve the model effectively.

关 键 词：外卖配送 路径规划 蜣螂优化算法 单纯形法 时间窗 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]