带有回程取货约束的车辆路径问题(Vehicle Routing Problem with Backhauls,VRPB)和二维装箱问题(two-dimensional Bin Packing Problem,2L-BPP)是两个经典的组合优化问题,在融合两者的基础上,本文提出了一种新的组合最优化问题,即2L-VR...
详细信息
带有回程取货约束的车辆路径问题(Vehicle Routing Problem with Backhauls,VRPB)和二维装箱问题(two-dimensional Bin Packing Problem,2L-BPP)是两个经典的组合优化问题,在融合两者的基础上,本文提出了一种新的组合最优化问题,即2L-VRPB.在该问题中,车队的最优路径规划和货物的最优装载设计需要同时进行考虑,该问题的优化目标是在满足所有客户的送货和取货需求的前提下,为车队中的车辆制定尽可能最优的行驶路线和货物装载方案,使得车队的总的服务成本最低.该问题在实际生活中有着广泛的应用场景,例如在设备维修和零售行业的货物运输中可经常遇到此类情形,但是文献中关于此类问题的研究论文仍然较少.为了求解2L-VRPB问题,我们提出了一种具有自适应性机制的混合模因算法(HMA),该算法采用改进的模因算法(IMA)来规划最优路径,并通过增强的组合装箱算法(MultiPack)来设计货物的最优装载方案.在实验环节,通过在VRPB问题的Goetschalckx &Jacobs-Blecha测试算例和2L-VRPB问题的Gendreau测试算例上设计对比实验,我们验证了混合模因算法在求解VRPB和2L-VRPB问题时的鲁棒性和有效性.
模因算法(Memetic Algorithm,简称MA)是一种融合了群体全局搜索和个体生命周期学习(局部搜索)的启发式搜索框架。在MA解决复杂优化问题的过程中,全局搜索和局部搜索的计算资源分配很大程度上影响了算法的性能。为了得到全局搜索和局部搜索的权衡依据,概率模因算法框架(Probability Memetic Framework,简称PMF)被提出。PMF把全局搜索和局部搜索分离,作为独立的优化行为,并且把MA建模为对全局搜索和局部搜索的选择决策过程。PMF通过搜索过程中计算得到的局部搜索强度理论上界,控制每个个体的局部搜索强度,平衡全局搜索和局部搜索的计算资源消耗。根据Feng等学者的研究[1],当使用PMF解决组合优化问题的时候,恰当的个体间距离度量(相似度度量)选择对局部搜索强度的估计起着极为关键的作用。然而,就目前最新的研究进展,几乎没有相应的工作研究关于PMF在解决组合优化问题中个体相似度度量选择的理论,我们的工作尝试改进这一方面的不足。在本文中,我们对PMF在解决组合优化问题时个体间距离度量的选择进行了初步地分析和研究,并且在经典组合优化问题:限量弧路径问题(Capacitated Arc Routing Problem,简称CARP)和有时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,简称VRPTW)上进行了实验研究。我们首先分析在组合优化问题中十分常用的4个距离度量被用来度量CARP候选解之间的相似度的可行性。接下来,我们提出一个基于邻近候选解度量和适应度距离相关性度量的距离度量适合度评价策略,用于量化一个候选个体相似度度量被用在PMF中解决组合优化问题时估计局部搜索强度的适合程度。最后,我们在egl的24个CARP benchmark上进行的实验研究表明:只有在使用编辑距离时,PMF找到了4个目前最优的解;对比改进Jaccard距离,当在PMF中使用编辑距离时得到了9个更优的解。我们在Solomon的VRPTW benchmark上的实验研究表明:对比MA,使用编辑距离作为距离度量的PMF在24个VRPTW benchmark中找到了10个更优的解;对比改进Jaccard距离,当在PMF中使用编辑距离时得到了12个更优的解。实验研究结果强调了在使用PMF解决组合优化问题时,恰当的距离度量选择对PMF的重要影响,同时在一定程度上验证了我们提出的距离度量适合度评价策略在CARP和VRPTW上是有效的。
暂无评论