关键词:
车辆路径问题
产品分类
取送货
混合互补元启发式算法
双种群模因算法
摘要:
物流行业作为现代国民经济新兴支柱,其运输调度问题得到了广泛关注。VRP作为物流运输中车辆调度分配的核心问题,已成为近年来的研究热点。作为经典VRP的一种特例,带产品分类和取送货约束的车辆路径问题(VRP with constraints including Product Classification,Pickup-Delivery Simultaneously,and Time Window,PC-VRPSPDTW)有效融合了多种实际约束,因而更具有挑战性和实用价值。在该问题中,车辆的路径规划不仅制约着车辆的运输距离,还会影响汽车尾气的排放量、顾客的等待时长,从而影响顾客对服务的满意度。如何灵活规划车辆的运输路线、设计高效智能的优化算法,成为多约束条件下满足顾客对不同种类的产品需求的关键。因此,本论文研究了不同优化目标下带产品分类和取送货约束的车辆路径问题。论文的主要研究工作内容和创新点如下:1.在不考虑绿色运输的情况下,以车辆成本、车辆行驶距离、超载部分和时间惩罚为目标,提出了一种混合互补元启发式算法(Tabu Search-Artificial Immune Algorithm,TS-AIA)。该方法在顾客需求已知的情况下,用数学表达式对决策变量、约束条件、目标进行描述,从而实现问题建模。为了解决带产品分类和取送货约束的车辆路径问题,首先通过考虑顾客的时间要求和车辆的容量限制,设计了一种基于顾客最早时间窗和车辆剩余容量(the Earliest Time and Residual Capacity,ETRC)的初始化算法,得到了高质量初始解。其次,混合互补元启发式算法能够融合全局搜索算法和局部搜索策略的优势,实现对解的广度挖掘和深度挖掘。算法的实施过程可以分为两个阶段:第一阶段,使用禁忌搜索算法对种群中的最优解优化,辅以变邻域搜索策略减少车辆数目,降低车辆成本;第二阶段,使用人工免疫算法对解种群进行优化,并设计了一种基于顾客关系表的交叉策略,通过总结顾客间的亲疏程度将关联性强的顾客传递至子代,保证优秀基因的传递。此外,大邻域搜索的运用能够有效提高搜索能力。实验结果表明,针对初始解和适应度的优化,所提算法能够获得较多的最优解,证明了算法的有效性。2.在考虑绿色运输的情况下,以车辆成本、车辆行驶距离、燃油消耗和时间惩罚为目标,提出了一种双种群模因算法(Bi-Population Memetic Algorithm,BPMA)。该算法以适应度为标准将种群划分为优质子种群和劣质子种群,并根据不同子种群的特点采取不同的交叉和变异概率,选择不同的优化策略。其中,双种群协同选择策略融合了精英选择、扰动选择和锦标赛选择,在保留优秀个体的同时确保了物种多样性。基于顾客-位置表的交叉策略考虑了种群中顾客间的关联性和每个顾客的独特性,延续了关联性较强的基因对。针对不同的子种群,多点双种群动态变异策略采取不同策略,在种群进化后期提升了变异概率。基于三种局部搜索策略前期的表现,自导向局部搜索决定搜索策略的选择,从而实现了多种搜索策略的集成应用。实验结果表明,所提算法对适应度和子目标的优化具有良好的效果,得到了有效范围内较优的解决方案。