随着O2O外卖行业的发展越来越成熟,各大外卖平台开始从补贴战和流量争夺的萌芽阶段,向提高外卖配送效率的成熟阶段转变,核心目标为提高顾客满意度。外卖配送这一环节直接面向顾客,能直观反映顾客的体验。然而,顾客对外卖配送服务质量尤其是时效性的高要求、高期望与外卖的配送能力之间存在矛盾。在订餐高峰时段尤为明显,随着大量订单不断涌入,商家订单处理能力较弱,导致餐品不能按时送达严重降低了顾客用餐体验。因为骑手必须先去商家处取餐才能前往相应的顾客处送餐,商家因兼顾处理堂食订单而难以保证外卖订单的按时出餐,如果商家出餐时间未知,骑手抵达商家处的时间过早,外卖餐品尚未做完并打包,则骑手需等待较长时间,以至于影响其他订单的配送;如果到达时间过晚则有可能导致该订单配送延误,并且影响餐品的食用口感,降低顾客体验。由此可见,商家的出餐时间对外卖骑手的配送路径优化有着至关重要的作用。本文在考虑商家出餐时间的基础上,分别研究了外卖抢单和派单两种经典模式下的骑手配送路径优化问题。在抢单模式下,构建了基于距离成本和时间成本的多目标优化模型,考虑到不同的骑手选择配送策略的偏好,采用遗传算法获得Pareto解集,从而实现为不同选择的骑手制定了相应的配送路线。考虑到骑手在外卖配送过程中随时可能产生新的订单,设计了考虑新订单加入的混合启发式算法,对每份新订单加入后的成本增量进行分析,探究骑手最优的抢单选择以及抢单后的路径安排。在派单模式下,骑手们的外卖订单由平台统一分配,考虑多位顾客向同一商家下单或者一位顾客向多位商家下单的情况出现,通过设置虚拟点简化了问题,以便于求解。构建了基于距离成本和时间成本的多目标优化模型,模型中考虑取送货顺序约束、骑手载货量上限约束以及顾客时间窗约束等,将多目标优化问题通过加权法转化为单目标问题,使骑手配送距离成本与时间成本总成本之和最低,设计了遗传算法进行求解。对于派单模式下新订单的插入,提出结合新订单的配送路径重规划算法。数值试验结果表明,本文提出的算法对于抢单模式和派单模式下的骑手配送路径规划具有一定的指导意义。