近年来,随着移动互联网技术的发展以及人们生活节奏的加快,O2O外卖市场愈发繁荣,2020年中国在线外卖市场规模达6646.2亿元。在O2O外卖服务中,顾客可以在外卖平台实时下单,因此订单的产生具有实时性。平台需要根据实时订单信息完成从商家处取餐和到顾客处送餐的任务,这种线上点餐、线下配送的服务模式被越来越多的人接受和选择,线下配送服务也已成为各大外卖平台降本增效、提高客户满意度的重要环节,如美团和饿了么两大外卖平台先后自建专业配送团队负责外卖订单的线下配送任务。另一方面,由于外卖订单的实时性,骑手在配送过程中需要不断调整取送路线,造成了配送难度的增大,进而导致目前外卖配送环节仍存在配送路线重复、配送超时严重、配送成本较高等问题,而目前现有的车辆路径优化研究往往建立在需求信息完全已知的离线状态下,因此无法直接应用于外卖配送路径优化问题。基于以上背景,本文对考虑订单动态产生的O2O外卖实时取送货问题进行研究,主要工作如下:（1）通过对国内外相关文献进行梳理,分析取送货问题和实时车辆调度问题与传统VRP问题在模型建立和算法求解方面的异同,明确本文要建立一个动态模型,并借鉴滚动时域和再优化策略设计动态的在线算法。此外,通过对外卖配送服务过程的分析,为后续算法参数的设置提供依据。（2）以规范化程度更高的专业配送模式为研究对象,考虑外卖订单实时到达的特性,以整个时间轴上任意时刻的订单、骑手状态为示例,结合静态取送货问题的数学模型,建立考虑实时订单信息的外卖配送车辆在线路径优化模型。（3）基于禁忌搜索算法和贪婪算法,借鉴滚动时域和再优化策略,设计了TS-Ropt在线算法来求解实时取送货问题模型。首先,借鉴滚动时域和再优化策略将在线动态问题转化为一系列离线静态问题,然后设计了双重嵌套禁忌搜索算法来求解静态外卖取送货问题,其中,针对取送货问题需满足先取后送访问顺序和取送节点成对匹配的要求,本文分别采用交换点对算法和内部互换算法来实现路径之间和路径内部的邻域搜索。（4）基于Python实现算法,并分别设计静态和动态算例来验证算法的求解效果。首先基于Solomon经典数据,创建了包含三种节点分布类别（R、C、RC）和两种订单规模（25、50）的六组静态测试算例来分析双重禁忌搜索算法的求解质量和速度;之后,以E外卖平台的真实订单数据设计动态测试算例,通过将TS-Ropt算法与贪婪在线算法的计算结果进行比较,验证了模型和算法的可行性和有效性。实验结果表明,本模型和算法能有效解决外卖订单的实时配送问题,与贪婪算法相比可降低约17.3%的配送成本。本文共有图17幅,表14个,参考文献61篇。