随着科学技术高速发展,人类的生活节奏也越来越快,社会也随之催生一批适应快节奏的新生类行业,比如:外卖行业。随着外卖行业进入常轨运行阶段,如何保证用户满意度的前提下,提高外卖平台的收益则成为了平台首要目标。外卖订单的动态分配问题本质上是一个车辆路径问题,设计合理的车辆路径问题的解决方案可以有效的提高平台的收益率、优化平台配送效率。本文对订单动态分配问题进行分析与总结,建立多车辆的带时间窗和取送顺序约束的动态路径优化问题的数学模型,并设计相关算法进行求解。本文的研究内容主要包括以下几个方面:(1)首先对大连市外卖的时空分布情况做描述性分析,调研分析大连市的外卖空间分布具有商圈化的特点;其时间分布具有双高峰的特点。然后对现有订单分配模式进行比较分析,总结其特点,得出在现阶段的外卖行业背景下,派单模式更适合外卖平台取得更高收益的结论。其次对订单分配问题的特征进行比较分析,说明静态订单分配问题具有全局透明性;而动态订单分配问题则仅具有局部透明性、变化强等特点。最后比较外卖行业的订单分配问题与电商行业的订单分配问题的相同点与不同点,突出其具有小批量、时效高等特点;再通过与拼车行业的订单分配问题的特征比较,突出其具有路途短、载容量大等特点。(2)考虑实际订单分配问题的基础上,对[0,T]时段内的外卖订单分配问题进行建模。首先对该问题进行数学描述、定义数学变量,然后建立在保证用户满意度的前提下,以平台收益最大化为目标、以骑士的载容量、订单的起始位置的时间约束和终止位置的时间约束、订单取送的顺序为主要约束条件的多车辆的带时间窗和取送顺序约束的动态车辆路径模型。(3)随后针对该问题提出考虑并单情况下的两种启发式算法,贪心算法和混合遗传算法。贪心算法的思想是将[0,T]时段分解成若干个[k,k+1]小时段,然后对[k,k+1]时段内产生的订单,仅分配使得平台获得最高收益的订单,迭代分配,直至不满足分配条件为止。贪心算法的过程:首先合并相似的订单;然后计算订单池中的订单与骑士匹配后的收益矩阵,优先分配高优先级的订单;其次再分配收益率高的订单,直至无法分配为止。混合遗传算法的思想在于:将[0,T]时段分解成若干个[k,k+1]小时段,对于[k,k+1]时段内产生的订单,遗传算法每次分配给每个骑士指定数量的订单,邻域搜索再决定这些订单插入骑士现有的派送列表的顺序,依次循环迭代,直至迭代结束。混合遗传算法的过程:首先利用遗传算法初始化种群,通过交叉、变异、选择算子选择适应度高的下一代个体,然后在下一代个体进行邻域搜索确定待分配订单插入骑士现有的订单列表中的顺序,继续执行遗传算法的迭代过程,直至迭代结束。(4)结合大连市罗斯福商圈2016年6月份的外卖配送数据,做两部分实验内容。第一部分实验是以2016年6月某天(订单数量最多和最少各一天)订单数据为实验对象得出的实验结果和从一个月的角度考虑统计意义上得到的收益效果以及从算法运行时间的角度来考虑两种算法的优劣,综合考虑得出贪心算法优于混合遗传算法的结论。第二部分实验是利用贪心算法对骑士数量、时间间隔、预计订单服务时间的变化对平台的收益影响做了实验分析,并找到罗斯福商圈的最佳预计订单服务时间和骑士数量以及时间间隔。