近年来,大型网上超市成为电子商务发展的新趋势,并逐渐成为主流的商品零售方式之一。大型网上超市主要销售使用频率最高的日常快消品,其销售商品种类达百万种。由于单个仓库的存储容量有限,大型网上超市通常需在同城区内建造多个仓库来解决自营商品的库存问题。一地多仓的库存结构导致大型网上超市每天需对上万订单进行仓库分配,也增加了订单配送的难度。由于很难在短时间内得到较优的订单分配方案和物流配送方案,大型网上超市通常只是得到一种可行的方案,使得物流配送成本居高不下(如国内某大型网上超市平均每个订单中物流成本占运营成本的58%[1])。本文研究的一地多仓库存结构下的订单分配和物流配送问题,它指的是大型网上超市在自建的二级配送网络(仓库→配送站→顾客)环境下,如何将接收的订单分配至恰当的一个或多个仓库,并获得从仓库到配送站之间物流配送成本最小的行车路线。从时间轴来看,订单分配先于物流配送工作,订单分配的结果将影响后续配送路线的安排。从求解目标的角度来看,订单分配和物流配送的目标具有一致性,二者的目标都是物流配送成本最小化。因此,在一地多仓的情况下,如何对订单分配问题和物流配送问题进行联合优化,即如何在分配订单时就能考虑订单的物流配送问题,已经成为大型网上超市亟待解决的难题。大型网上超市一地多仓的订单分配与物流配送问题可以归属为定位-运输路线安排问题(Location-Routing Problem,LRP)[2]。相对于一般的LRP,本文的问题具有以下特点:(1)多个仓库既不是平行仓,也不是分仓;(2)配送站的需求可拆分,每个车辆可以访问多个仓库,每个配送站可以被访问多次;(3)物流配送属于开放式车辆路径问题(Open Vehicle Routing Problem,OVRP)。基于对该问题的分析,本文建立了以物流配送总成本最小为目标,以行车时间限制、车载容量等为约束条件的模型。配送总成本等价于从仓库配送到配送站的派车成本和路径成本之和。LRP属于NP-hard难题,自20世纪70年代开始,已有大批学者针对LRP提出了各种启发式算法。但是,由于大型网上超市的订单数量庞大,单个订单中商品品项多(是普通网购平均数的8~10倍[3]),大部分订单将根据商品存储仓库不同而被分解成多个包裹送达顾客。这使大型网上超市的订单分配和物流配送问题的求解难度更加突出,使用现有的算法很难进行求解。因此,本文基于缩减问题求解空间的思想,针对一地多仓的订单分配与物流配送问题提出了求解方法。首先,在分析订单和仓库特点的基础上,采用人工智能状态空间搜索理论,剔除较差的订单分配方案,根据订单拆单数以及仓库与配送站之间的路径成本生成初始订单分配方案,同时生成备选的订单分配方案集合。其次,考虑配送时间和车载容量,利用改进的节约算法[4]生成较优的初始配送方案。最后,以最小化总的配送成本为目标,基于初始的订单分配方案和配送方案,利用改进的邻域搜索算法,从备选方案中生成最优订单分配方案和配送方案。另外,基于某大型网上超市自建二级配送网络下一地多仓的实例验证了该算法的有效性。本文针对大型网上超市实际中所存在的一地多仓的订单分配与物流配送问题,运用人工智能状态空间搜索理论和邻域搜索技术,提出了可以快速生成较优的订单分配方案和物流配送方案的算法。本文提出的改进广度优先搜索算法通过剔除较差的订单分配方案,大大缩减了问题的求解空间,通过改进节约算法中路径合并的规则,有利于较快地生成较优的物流配送方案。本文提出的算法可以帮助大型网上超市提高订单履行作业的科学性与实用性。同时,该算法对于求解OLRP(Open Location Routing Problem)和需求可分割的LRP有一定启发,有助于丰富LRP的理论成果。由于该问题的复杂性,本文对问题作了一些简化和假设,为了提高普遍性和实用性,将进一步研究的内容包括:(1)考虑仓库中商品的库存,进一步研究订单在多个仓库的有效分配;(2)对于当前所存在的从仓库→配送站→顾客的二级物流配送网络,进一步研究从配送站到顾客的物流配送对配送总成本的影响。