基于ALNS算法的城市商品配送车辆路径问题研究

发布时间：2021-10-30 03:36

　　随着现代经济飞速发展,尤其是电子商务平台的快速崛起,城市商品配送成为社会物流活动不可或缺的一部分,人们对物流配送服务的要求也在日益提高。车辆路径规划问题作为物流配送行业的重要问题,自提出以来就吸引了运筹优化等领域工作者的广泛研究。在商品配送领域,客户对于交付的及时性要求日趋严格,带时间窗的车辆路径问题越来越受到重视,而对该问题的研究由于其复杂性目前还没有突出进展。本文基于此开展研究,研究内容主要有以下几个方面。结合实际背景将城市商品配送问题抽象为多目标带有时间窗约束的车辆路径问题（VRPTW）,建立相应的数学模型。本文模型基于电商企业考察了总行驶距离和未服务客户点数量这两个目标,基于车队承运商考察了司机收入均衡程度和司机作业时间均衡程度这两个目标。选择设计ALNS算法对问题进行求解,对算法引入随机性,改进了算子设计和选择策略部分。利用Solomon公共算例集考察了本文ALNS算法的求解性能和效率。在某公司的实际大件派工项目背景下,将公司的业务数据和相关的要求与论文模型进行匹配,将多目标优化问题转化为求解目标矩阵和理想值矩阵最短欧式距离的问题,并且利用ALNS算法进行求解。对比ALNS算... 

【文章来源】：南京大学江苏省 211工程院校 985工程院校 教育部直属院校

【文章页数】：78 页

【学位级别】：硕士

【部分图文】：

常见VRP及其拓展问题

南京大学硕士学位论文第二章车辆路径问题类型及求解方法—16—图2-2LNS算法解决VRP问题示例2.5ALNS算法介绍自适应大规模邻域搜索算法(ALNS)是大规模邻域搜索算法的一种扩展，由Ropke和Pisinger[23]提出。ALNS算法不同于LNS算法的地方主要在于ALNS在搜索过程中采用多种移除和插入的算子，在每一轮算法迭代中只会选择一个移除和插入算子，算子的每一轮的选择概率与其历史表现相对应，并且随之发生变化，而LNS只采用一个移除算子和一个插入算子。ALNS算法的流程如算法2-3所示。算法2-3：AdaptiveLargeNeighborSearchInput:probleminstanceIcreateinitialsolution=s∈()whilestoppingcriterianotmetdofori=1,…,selectr∈R,d∈Daccordingtoprobabilitiesp,=(())ifaccept(,,)=,if(,)<()=endifendifendforendwhilereturn自适应大规模邻域搜索方法通过使用启发式方法探索复杂的邻域，使用较大的邻域可以在每次迭代中找到更好的候选解，从而遵循更有希望的搜索路径。

南京大学硕士学位论文第二章车辆路径问题类型及求解方法—17—图2-3ALNS算法解决VRP问题示例相对于其他算法，ALNS的优势包括：(1)对优化模型要求宽松ALNS算法类似GA算法，对优化模型的目标没有可微可导等要求，同时优化目标的设置基本不影响算法本身的求解效率。(2)ALNS算法的框架容易拓展ALNS算法可以提供类似模块化的组合方案，根据求解的问题对算子进行自定义和组合。ALNS算法在提出时即被用来解决VRPPDPTW问题，对于其他类型的VRP问题此算法同样拥有良好的求解能力。(3)能实现不同的搜索策略在ALNS算法中，可以根据具体的优化问题，设计相应类型的算子，利用不同算子的邻域操作可以实现不同的搜索策略。(4)拥有更大的解空间ALNS算法相比于普通的本地搜索、邻域搜索算法，可以探索更大的邻域空间，因而有可能获得更优的解。(5)对算子的自适应选择通过给定算子的自适应选择机制，在ALNS算法中可以对算子的表现进行记录打分，进而可以通过反馈机制决定下一次迭代时算子的选择概率，表现更好的算子更容易被选择进行邻域操作。自然，相同问题的不同实例，甚至不同的解决方案都由不同的移除和插入算子构成，其成功程度也各不相同，通常很难预测哪种启发式的构造是最有利的。


本文编号：3465971