动态需求下考虑订单聚类的外卖配送路径优化

外卖配送路径优化包括骑手间订单分配和骑手配送路径规划两部分。针对其中订单动态产生和骑手位置不断变化的问题，基于预优化后动态调整的思想建立以最小化超时订单比例、单均配送时间和单均行驶距离为目标的两阶段优化模型。在预优化阶段，设计改进变邻域搜索算法获得初始配送方案；在动态调整阶段，采用周期性优化策略，将不断变换的骑手位置转化为虚拟配送中心车辆问题进行求解；在每一阶段采用不同的聚类方法对订单进行聚类，优化初始解的质量以更快求解。结果验证了本文策略和算法在求解动态外卖配送路径问题时的有效性和可行性。研究成果不仅深化拓展了PDVRP(pickup and delivery vehicle routing problem with time window)相关理论研究，也为外卖平台提供一种科学的优化方案。

Takeout Distribution Routes Optimization Considering Order Clustering under Dynamic Demand

Takeout distribution optimization includes order allocation and route planning. Aiming at dynamic order and rider position change, with the goal of minimizing the overtime order proportion, average delivery time and average travel distance,a two-stage mathematical model is established based on the idea of pre-optimization and dynamic adjustment. In the pre-optimization stage, an improved variable neighborhood search algorithm is designed to obtain the initial distribution scheme. In the dynamic adjustment stage, a periodic optimization strategy is adopted to transform the problem into a virtual distribution center vehicle problem for solution. In each stage,different clustering methods are used to optimize the initial solution quality for faster solution. The effectiveness and feasibility of the proposed strategy and algorithm to solve the dynamic takeout distribution routing problem are verified and comparatively analzed. The research results not only deepen and expand PDVRP related theoretical research, but also provide a scientific takeout distribution optimization scheme for the takeout distribution platform.