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

Abstract: 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.

Key words: take-out delivery, path planning, dung beetle optimization algorithm, simplex method, time window