云南省图书馆机构用户，欢迎您！
针对O2O订单取送货点成对出现且先取货后送货的情况，同时考虑多车型、多行程、顾客时间窗等实际配送约束，以配送总成本最小化为目标构建O2O订单配送路径优化模型.为求解该模型，提出结合邻域搜索的模拟退火算法(ISA-NS)，设计独特的编码方式满足订单优先级、成对和多车型约束，采用贪心策略构造初始解，并引入3种邻域搜索算子扩展算法的搜索范围.求解小规模与大规模基准案例，ISA-NS算法的解接近于现存最优解，这验证了该算法的有效性及收敛性.最后，以天津“货拉拉”平台的O2O订单为例优化配送路径，验证模型和算法的可行性.
图1 同城货运平台下O2O订单配送流程 目前，国内O2O订单配送模式主要应用于外卖行业，逐步扩展到零售物流配送、生鲜配送等方面.在外卖配送领域，吴腾宇等[3]研究O2O平台下外卖服务的配送问题，针对不同适用情况设计TAIB算法与IGNORE算法进行求解.余海燕等[4]提出了贪婪策略、最小差值策略以解决基于众包平台的外卖实时配送订单分配及路径优化问题.戴韬等[5]统一考虑了众包模式下的订单选择及订单执行路径问题，提出改进的遗传算法和贪心算法解决双层模型.在零售物流配送方面，李文莉等[6]在突发疫情环境下考虑订单释放时间的车辆路径优化问题，提出了改进的迭代局部搜索求解算法.赵泉午等[7]研究生鲜企业店铺选址及末端需求点分配问题，设计混合拉格朗日松弛算法求解.肖可等[8]考虑了配送中心的订单分批优化问题，设计了基于复合相似度的订单分批启发式种子算法.王征等[9]针对同城即时配送问题，提出基于多预测场景的动态在线调度方案.上述关于O2O订单配送的研究应用场景丰富，但大多只考虑了同车型的订单配送问题，鲜有考虑同城货运企业中多车型车辆配送订单以及违反订单送达时间窗影响客户满意度的实际情况，缺乏对于多车型车辆配送、送达时间窗两种实际约束的订单配送问题探讨. 求解订单配送问题的算法主要分为两大类，一类为精确算法，可求得问题最优解但耗时较长；另一类为启发式算法，以合理的求解时间求得较优解[10].对于精确算法，李昆鹏等[11]采用分支切割算法求解以最小化配送总里程为目标的电商末端配送路径问题.李建斌等[12]提出改进的K-means算法求解订单车辆匹配的多目标决策问题.张源凯等[13]结合C-W节约算法和邻域搜索技术优化网上超市的订单配送路径.上述文献采用精确算法求解订单车辆匹配或者订单路径优化问题，均只适用于小规模案例.而在面对高峰期的O2O订单时，所涉及的成对取送货点、取送顺序、服务时间等变量可达上百个，精确算法难以计算，多采用启发式算法进行求解.对于启发式算法，Wang等[14]研究电子商务包裹及O2O包裹的配送路径优化问题，有效地结合邻域搜索和禁忌搜索算法构成混合邻域搜索求解算法.Soman等[15]考虑了订单服务时间、截止时间以及多车型车辆路径问题，采用离散搜索算法求解混合整数模型.Li等[16]提出了自适应大邻域搜索算法解决考虑订单时间窗、产品和服务相匹配的车辆路径问题.Sethanan等[17]研究饮料分配系统流程，设计混合差分进化算法求解多车型车辆路径和多行程车辆路径的结合问题.Veenstra等[18]研究带有取送货顺序的取送货旅行商问题，设计邻域搜索算法进行求解.Cattaruzza等[19]、Wang等[20]分别设计混合遗传算法、池元启发式算法求解带时间窗MTVRP.Wang等[21]针对外卖配送问题存在的MTVRP和PDPTW特征，开发了迭代局部搜索和自适应大邻域搜索两种启发式方法求解.Kafle等[22]利用众包资源构建城市包裹中继和交付系统，利用模拟退火算法求解车辆运输包裹路线.上述文献多采用邻域搜索算子扩大算法的搜索范围，获得较高质量的最优解.因此，针对要求算法求解速度较高、且较为复杂的O2O订单配送问题，本文采用简单、高效的模拟退火算法与邻域搜索算子相结合，从而避免陷入局部最优解，在保证算法求解速度的同时提高算法的整体搜索能力.
