背景描述
电商的蓬勃发展使得目前很大一部分的物流包裹均来源于线上电商订单。在中国，该比例超过了60%。这些包裹在配送的最后环节，是由快递员将包裹从网点送到消费者手中。另一方面，随着互联网逐渐向线下渗透，涌现出了越来越多的同城包裹配送需求，如外卖订单或鲜花蛋糕等等同城订单。这两类包裹的配送是目前中国最后一公里配送中最典型的场景。通过大数据对中国物流最后一公里提供智能的配送方案，通过全局优化来提升效率及降低成本。国内外学者针对此问题做了大量的研究。
O2O配送
金辉阐释了生鲜电商配送环节存在的问题与搭建O2O环境下生鲜配送模式必要性的基础上,针对O2O不同的主导方提出了三种不同的配送模式,并从生鲜品价值实现度与企业资源占有度两个方面建立了生鲜品配送模式的判定矩阵,以期不断完善企业现有的生鲜品配送体系,使其与生鲜O2O发展相适应[1]。赵泉午等研究了O2O转型背景下大型零售企业城市配送网络优化面临的中转中心选址及末端需求点分配问题,构建了考虑配送中心到末端需求点近似配送距离的中转中心选址及末端需求点分配联合优化模型,设计了集成遗传算法和禁忌搜索算法的混合算法求解模型[2]。邓娜结合对O2O外卖订单配送任务分配环节现有分配模式的分析,提出了一种基于聚类分析和TSP路径规划的订单集指派模式,为优化外卖配送提供了理论参考[3]Tsai, TM对一些流行的O2O服务场景进行了客户旅程分析，定义了O2O商务服务模型，提出了O2O商务系统框架。基于此框架，实现了“一键式购物墙”服务，对邻近商务服务的最佳实践进行了实验[4]。
VRP（车辆路径问题）问题
宋伟刚针对非满载的VRP问题具有组间无序、组内有序的特性,采用一种有效的改进交叉算子,最大程度的保留了父代的优良特性并增强了算法的寻优能力,避免了早熟现象的发生[5]。卫田提出了精度、时间、解决问题个数相结合的三维算法比较方法。首次,将精度作为算法比较的一个重要方面,得到了算法比较三维模型,同时,给出了可行的算法选择流程,并开发了算法选择软件[6]。孙中悦构建了车辆路径问题的仿真优化模型。针对车辆路径问题的复杂性,利用离散事件仿真方法对物流配送过程进行建模,并采用面向对象的技术实现。为了求解VRP问题,将仿真技术与优化算法(选择遗传算法作为优化算法)有机融合,建立了仿真优化模型,并此模型上增加了智能决策模块,解决VRP随机问题、处理约束条件、辅助优化算法寻优[7]。
CVRP（最大容量约束的车辆路径问题）问题
姜昌华对CVRP问题,提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小,从而提高搜索效率并降低计算时间[8]。王超，金淳等提出三维装载与CVRP联合多目标优化问题(3LCVRPMO)模型,该模型在三维装载约束下的CVRP问题(3LCVRP)的基础上,考虑了配送车辆数目及路径总距离两个目标函数.在权衡装箱和路径优化两个优化过程的基础上,构建了多阶段/两层混合算法架构(MSOTLH)及其算法,并对路径优化偏好的3LCVRPMO问题进行求解[9]。于雷建立了符合实际情况的数学模型，在CVRP及VRPSDP下均以降低燃油消耗为优化目标，将内燃机燃油消耗因素与CVRP（VRPSDP）问题建立连接，使得CVRP及VRPSDP模型可以定量的表达内燃机燃油消耗[10]。
Lysgarrd, J提出了一种新的求解有容量车辆路径问题的分枝割算法。该算法使用了不同的割平面，包括容量、框架容量、广义容量、加强梳状、多阶、部分多阶、扩展的低阶不等式和经典的Gomory混合整数割。特别地，Lysgarrd, J首次将Augerat的三个实例（B-n50-k8、B-n66-k9和B-n78-k10）求解为最优性[11]。
VRPTW（带时间窗的车辆路径问题）问题
张涛，王珊珊等提出车辆可重复利用的VRPTW问题,建立多目标整数规划模型;基于蚁群系统(ACS),按优先访问服务开始时间较早、服务时间较短和关窗时间较早的原则,设计启发式因子和蚂蚁状态转移规则，根据客户服务结束时间较早优先原则构造初始解[12]。金淳，张雨等提出一种改进的分布式多agent蚁群算法,该算法在传统蚁群算法的基础上,为提高算法精度,改进了状态转移规则,结合了邻域搜索算法;为提高算法速度,将算法设计为分布式结构,利用多分布式agent系统实现了分布式求解VRPTW问题[13]。唐勇，刘峰涛为了克服现有遗传算法不能有效求解时间窗车辆路径问题的缺陷,提出了一种由遗传算法结合模拟退火算法的混合算法求解该问题，利用了模拟退火算法具有较强的局部搜索能力的特性,有效地克服了传统遗传算法的“早熟收敛”问题[14]。黄樟灿提出了一种基于模拟退火算法(SA)和大规模邻域搜索(LNS)的混合算法,并采用PFIH算法构造较高质量的初始解,同时给出了一种调整客户时间窗的回归迭代策略,从而计算出每辆车的最佳出发时间,并证明这种策略可使每辆车的等待时间均为零[15]。Baldacci, R综述了电容式VRP（CVRP）和带时间窗VRP（VRPTW）这两种VRP最重要变体的数学公式、松弛方法和最新的精确计算方法[16]。
VRPPD（先取货后配送的车辆路径问题）问题
朱玲玲，程学云等通过改进的Sweep算法获取初始解,设计了候选解结构、适应度函数、4种邻域操作以及邻域操作需满足的车辆容量约束和时间窗约束方程,采用主动禁忌算法自适应地修改禁忌长度以增强算法的全局寻优能力[17]。祁文祥提出VRPPDTW的数学模型表达式,将租车费用、运输费用、时间惩罚费用之和作为目标函数，然后提出一种两阶段启发式算法对模型进行求解。第一阶段,采用改进的Clarke-Wright算法针对模型的特点构建初始解;第二阶段,构造四种带禁忌规则的邻域搜索机制,并采用多种优化机制避免搜索过程陷入局部最优,得到最终优化结果[18]。付在峰改进了人工蜂群算法的搜索方式和选择方式，通过benchmark函数验证了改进后算法的可行性，并介绍了Unpaired VRPPD问题的概念和数学模型,并结合该问题的特点,设计了初始解构造方法和局部搜索方法等,提出了以人工蜂群算法为主体的优化算法[19]。Nagy, G没有采用VRPPD文献中常见的假设，即只有在所有交货完成后才能提货。也避免了插入的概念，并提出了一种以集成方式处理取货和送货的方法。该方法找到了相应的VRP问题的解，并对该解进行了修正，使其对VRPPD是可行的[20]。P.D提出了一个统一的启发式算法，能够解决五种不同的车辆路径问题：带时间窗的车辆路径问题（VRPTW），带容量的车辆路径问题（CVRP），多车辆段的车辆路径问题（MDVRP），站点相关的车辆路径问题（SDVRP）和开放的车辆路径问题（OVRP）。所有的问题变量都转化为一个丰富的取货和送货模型，并使用Ropke和Pisinger提出的自适应大邻域搜索（ALNS）框架（一种针对带时间窗的取货和送货问题的自适应大邻域搜索启发式算法）求解[21]。
总结
首先，此题是典型的VRP（Vehicle Routing Problem）问题，需要对实际问题进行建模，搞清楚目标函数及约束条件。要求快递员总体配送时间最短配送路径最短，即为目标函数。对于约束条件，VRP中常见的约束无外乎最大容量约束（CVRP）、时间窗口约束（VRPTW）、先取货后配送约束（VRPPD），该题目全包含了[22]。题目中描述所有电商单的配送需要到网点取货后才能配送，所有的O2O单要到店铺取货后才能配送，这是先取货后配送约束；题目中要求O2O订单的取送货时间要满足要求的最早取货时间和最晚配送时间，这是时间窗口约束；题目中要求快递员任意时刻携带的包裹量不能超过140件，这是最大容量约束。至此，该问题就建模完成，然后可以调用求解工具或者自己采用贪婪的方式去求解问题[23]。
但是，之前人们所提出的方法解决小规模问题效率非常高，超过限制性能就会出现问题，比如求解时间会成倍增加。目前上百个点的求解基本是不成问题的，速度很快，但最大规模也仅限于几百个点，像最后一公里中上万点的规模是相当大的，一般的工具难以承受的住[24]。我们只能转而求次优解，将问题规模缩小，分治求解，比如配送点按区域划分给各小件员，一个大问题可以一下子缩小为若干个小问题，各个部分的可行解很快就可以出来。时间窗口约束较弹性，可以不满足，转而相应的增加惩罚时间，甚至可以将时间窗口约束去掉，增大花费，也是有效的解[25]。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
