关键词:
多仓库多车程车辆路径规划问题
带时间窗约束的取货送货问题
混合局部搜索
空间剪枝
摘要:
本文针对最后一公里配送问题中的一种变种问题进行了深入研究。最后一公里配送问题的研究在近几年得到了大量的关注,不仅仅是因为互联网的快速发展催生了大量的电商包裹配送需求,还因为移动互联网的普及让Online-to-Offline(O2O)这一类包裹配送需求也急剧上升。对于电商包裹来说,该类包裹最大的特点为每个包裹的体积重量差距很大,且城市中每个网点每天的配送需求非常巨大。而O2O包裹一般包括鲜花,蛋糕的配送等,这一类包裹通常在同一城市中进行同城配送,即要求服务提供者提供运力,在同城的起点和终点之间进行往返配送,并且这类包裹的客户通常会要求在指定时间内完成配送,即这类包裹拥有时间窗约束。这两类包裹的特点对运力提供者提出了非常大的挑战,包括运力的规划和协调。本文为了解决上述的问题与挑战提出了一类种问题变体,该变体对电商包裹以及020包裹进行调度配送,本文提出的这个问题是由配送即服务(Delivery-as-a-Service)这一概念所驱动的,该概念目标在于建立统一的基础设施,使用同一车队来为不同种类的商品货物提供标准配送服务。我们把这一问题建模成多仓库多车程的车辆路径规划问题(Multi-Depot Multi-Trip Vehicle Routing Problem,MD-MT-VRP)与带有时间窗约束的成对取货送货问题(Paired Pickup and Delivery Problem with Time Window,PPDPTW)的混合模型。为 了解决这个MD-MT-VRP与PPDPTW的混合问题,我们建立了这一问题的混合整数规划(Mixed-Integer Programming,MIP)模型,来求得这一问题在小规模实例下的最优解。而在大规模问题实例下,我们提出了一种混合领域搜索策略来有效地结合了自适应大领域搜索(Adaptive Larger Neighborhood Search,ALNS)和禁忌搜索(Tabu Search)算法。我们根据该问题的特性,加入了大量的新设计的算子来提高算法搜索的多样性,寻找并利用了该问题的辅助信息来证明了多个搜索上、下界,从而提出两阶段剪枝策略来极大地加速了提出算法的局部搜索过程。我们在多个数据集上进行大量的数值实验,包括小规模以及接近现实情况规模的数据集,对算法的表现和行为进行了分析,实验结果表明我们的混合方法能够达到近似最优的表现,并且与ALNS和禁忌搜索算法相比表现出了明显的优越性。我们还在其他相似问题的数据集上进行了大量实验,来考察本文提出算法的泛化性能。