求解多目标VRPTW的离散萤火虫膜算法研究

发布时间：2020-07-26 20:33

【摘要】：车辆路径问题(Vehicle Routing Problem,VRP)是城市交通改善和物流配送管理等实际应用中常见的问题。本文主要求解多目标的带时间窗车辆路径问题(Vehicle Routing Problem with Time Window,VRPTW),同时最小化车辆配送数量和车辆行驶距离这两个目标。通过返回一个非支配解的集合而非单一的解,给决策者提供更强大的决策支持。多目标VRPTW是典型的NP-Hard组合优化问题,现有的启发式优化算法难以获得问题的全局最优解。智能优化算法具有杰出的全局搜索能力,越来越多的被用以求解多目标VRPTW。本文围绕求解多目标VRPTW的离散萤火虫膜优化算法进行了深入研究,主要做了以下方面的工作:(1)本文首先针对多目标VRPTW这一具有重要现实意义的NP-Hard问题,利用萤火虫算法本身多目标寻优的特性,提出一种基于时间窗划分的改进离散型萤火虫算法(MDGSO-TWD)。在算法中,首先根据时间窗对客户点进行分类,并由此设计了萤火虫个体的生成方式。为了更加真实有效地反映萤火虫算法的进化机制,本文重新定义和设计了萤火虫算法的运动规则。在搜索过程中,使用随机个体来替代种群中的重复个体以维持种群的多样性。同时,为了加快搜索速度,弥补算法局部搜索能力的不足,提出了一种基于时间窗分类的模因邻域搜索技术和自适应萤火虫飞行步长的概念来增强算法的局部搜索能力,并在搜索过程中采用精英策略记录全局最优解以防止算法退化。由于多目标问题的不可评估性,引入Pareto支配的概念来评估萤火虫个体的优劣,并对生成Pareto非支配解集的方式进行了重新设计。最后,通过仿真实验和对比实验,验证了所提算法的可行性和有效性。(2)在改进离散型萤火虫算法的基础上,提出了一个度为3的组织P系统。通过分析膜计算模型的三个要素:对象、反应规则和膜结构,建立了基于膜计算的萤火虫膜优化算法(PDVA)。该算法不仅保留了常规膜计算系统的基本特征,还吸收了萤火虫算法的研究成果。在该系统中,以萤火虫编码作为进化对象,采用离散型萤火虫进化机制和变邻域进化机制作为子算法对对象进行进化。使用细胞通讯规则对系统内的对象进行信息传递与共享。为了扩大解空间的搜索区域,提高算法求解精度,在算法之中改进了变邻域进化机制。最后,通过仿真实验和对比实验,验证了所提算法的有效性和高效性。
【学位授予单位】：武汉轻工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18;U491
【图文】：

牛物计算樟型

示意图,时间窗,示意图,客户

本文根据客户的服务时间窗，将客户分为不同的类，这有助于减群初始化和邻域搜索算法。首先，将客户分到不同的类，然后将分类结果用于种始化和邻域搜索，我们可以对不同类别的客户采取不同的操作，在种群初始化阶段为客户类别之间是互斥的，因此我们只需要选取不同类别的客户组成新的路径，邻域搜索阶段，因为同一类别的客户拥有相似的服务时间窗口，因此我们只需要一类别的客户采取邻域操作，相比于盲目搜索，这将有效的缩短算法搜索时间。服务时间窗口对客户进行分类是 MDGSO-TWD 算法的基础。客户分类的详细步骤如算法 3.1 所示。首先，计算仓库的开放时间窗口，并将为 K 个子类，如图 3.2 所示。第二，假如客户 c 的服务时间窗为[ec, lc]，对于某客户类别 j，如果[ec, lc] [e0+j*T/K, e0+(j+1)*T/K] ≠ ，那么客户 c 就被划分户类别 j 中。重复这个过程直到所有的客户都被分类。在图 3.2 中，K 为车辆数估计值。e0是仓库的最早开放时间，0l 是仓库的最晚开放时间，00T = l e。

示意图,客户,时间窗,示意图

for i=1 to K, T = ldepot- edepot3: for ( c ∈C) do4: C ←C/{c}5: for ( j=1; j≤K; j++) do6: if ([ec,lc] Timewindow(class(j)) ≠ ) then7: class(j)←class(j) {c}8: end if9: end for10: end for11: return class(i), for i=1 to K面举例说明这个过程。例如，如图 3.3 所示，假设划分的某两个时间段为[10,30]，而客户 i 和 j 的服务时间窗口分别为[15,25]和[21,28]，则将客户 i 归并到[10,20]和[20,30]的时间窗集合内，将客户 j 归并到时间段为[20,30]的时间窗

【相似文献】