近年来,外卖O2O行业凭借着互联网经济的高速发展和国家政策的鼓励支持,获得了突飞猛进的发展。随着居民人均可支配收入的增长以及用户用餐习惯的改变,外卖成为了人们日常饮食中非常重要的一部分。但是目前在市场需求日益旺盛的环境下,外卖的现实配送能力与顾客对配送服务提出的高要求和高期望之间已经出现了矛盾。随着平台补贴大战的结束,用户的主要关注点从价格逐渐转为时间和食物品质。配送时效成为衡量需求是否满足的重要指标之一。如果哪个外卖平台能在持续提升用户体验的同时,提升配送服务质量,降低配送成本,将会在未来的竞争中处于优势地位。外卖订单分配问题作为外卖调度流程中的关键环节之一,对于提高外卖配送效率、降低配送成本起着重要的作用。同时,外卖订单分配问题也是当下热门研究领域。本文主要针对外卖订单分配问题进行优化研究,主要研究工作如下:(1)外卖订单分配问题是一个非常复杂的问题。不仅受到确定性因素的影响,也会受到很多不确定性因素的影响。出餐时间作为一个不确定性因素,对订单分配的准确性和合理性有很大的影响。是影响外卖配送时效性与服务质量的一个关键因素。当配送员到达商家处时,若外卖还未制作完成,需要等待一段时间。这时就会造成运力的浪费,还会影响到其他订单的配送。尤其是在高峰期时会影响整体运力分配。若商家早已出餐而配送员迟迟未到,等食物送达客户时口感可能已经发生改变,这时会导致顾客满意度下降。因此本文在进行订单分配时充分考虑出餐时间这个因素。由于出餐时间具有随机性,无法确定,不能直接计算出来。因此本文从多个维度分析了影响出餐时间的因素,构建预测模型对其进行预测,从而为后续决策提供依据。(2)现实场景中,大多数平台在进行订单分配时只考虑单笔订单的属性,对多个订单之间的关联性的关注则较少。而单个订单的分配模式,单位时间内送单量低,整个配送过程距离增长,导致配送效率较低,配送成本增高。针对这个问题,本文在对订单进行分配时,首先根据空间相似性和时间相似性对相似订单进行合并,形成一个配送任务包,然后分配给同一个配送员配送。订单合并的分配方式相比单笔订单分配的方式,可以有效提高整体配送效率,使资源得到合理利用。从而增加单位时间送单量,降低配送成本。(3)外卖订单分配问题具有很强的复杂性,具有动态性、时间窗约束、取送货顺序约束以及商家客户严格配对等特征。针对该问题,本文结合外卖实际业务流程,以配送成本最小化为优化目标,将实际问题转化为具有时间窗约束与取送货配对有序的优化模型。由于实际场景中可能会存在商家和客户之间的多对多现象,本文通过设立虚拟点的方式,将多对多问题转化为一对一问题。使原本就很复杂的问题得到简化,方便后续求解。(4)外卖订单分配问题的复杂性,也增大了问题求解难度。在对现有文献研究以及实际调查的基础上,本文设计了一个两阶段求解算法。针对订单分配问题的动态性,引入滚动时域机制。将整个配送时域划分为若干个等长的时间窗口,实现动态求解。在此基础上,首先利用X-means算法将相似订单进行合并,然后再使用遗传算法实现订单与配送员的最优匹配。最后设计了算例,对本文所构建的模型和算法进行了验证。实验结果证明本论文提出的求解外卖订单分配问题的数学模型和两阶段算法是有效的。本文在对外卖订单分配问题的研究中,构建出具有时间窗约束、各点配对有序的优化模型。针对本文所研究问题的特征,设计了X-means算法和遗传算法的两阶段算法进行求解。本文的研究对于外卖O2O行业的订单分配问题研究具有一定的借鉴和参考价值。能够为外卖平台的运营决策提供一定的辅助作用。