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

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

随着外卖行业的发展,外卖平台要在大量候选订单中选择并规划出高效的配送路线。为了满足外卖平台和顾客的需求,建立以配送成本最小和顾客时间满意度最大为目标的优化模型。采用蜣螂优化算法进行求解,针对蜣螂优化算法易陷入局部最优和求解质量低等问题,通过引入模拟多项式变异策略、模拟退火概率突跳算子和单纯形法局部搜索策略,提出一种融合多策略的增强蜣螂优化算法(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 optimiza‐tion 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 algo‐rithm 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.