论文部分内容阅读
着色旅行商问题（CTSP）是旅行商问题（TSP）和多旅行商问题（MTSP）的泛化,它通过引入颜色来表现个体城市对多重旅行商访问允许性的差异,适用于建模与求解现实中的多机差别化访问/执行多任务的优化调度问题。李俊的团队基于完全图先后提出了三种CTSP模型,即:星型CTSP（R-CTSP）、连环CTSP（S-CTSP）和通用CTSP。为了进一步泛化通用CTSP来建模基于复杂网络的实际工程问题,本文拟采用超图代替完全图重新描述通用CTSP,提出三种超图定义的广义CTSP（GCTSP）,并针对这些模型的特点和难点,分别设计了三种高效的求解算法。主要的研究内容与工作列举如下:1)利用超图定义了城市划分及划分上的代价函数的概念,首次提出了一种超图定义下的GCTSP并讨论了它的一些基本性质,得出了GCTSP在特定条件下可转化为R-CTSP、S-CTSP及MTSP的结论。随后,在GCTSP的基础上,分别考虑了调度系统中可能出现的“木桶效应”现象和访问次序的优先约束,建模了双目标CTSP（BCTSP）和带优先约束的CTSP（PCTSP）。此外,还讨论了BCTSP的NP难性,并统计了PCTSP上划分的数目。2)鉴于大规模TSP案例求解的核心在于构建低密度城市网,提出了一种基于Delaunay三角剖分的变邻域搜索（DVNS）来求解大规模GCTSP案例。该算法可利用分治法快速创建低密度Delaunay三角网。特别地,研究了一种新型贪婪多插入算子（GMI）以Delaunay边作为候选插入对象来扰动当前解,并采用2-Opt和3-Opt依次优化DVNS的局部搜索过程。此外,设计了21个带规则颜色和随机颜色的城市集来比较DVNS和其它6种算法的性能。PC上执行的仿真结果显示DVNS能在120秒内得到规模33000+、旅行商数多达240的GCTSP案例的满意解,它在解的搜索能力和收敛速度方面均优于这6种对比算法。3)提出了一种基于种群的双目标VNS（BVNS）求解BCTSP,该算法包含四个主算子,即:基于概率的插入变异,基于种群的多插入算子,保色交换和2-opt。其中,第一种算子用于构建不同的解邻域,而后三种策略用于执行局部搜索。多插入操作延用Delaunay三角剖分来确定插入的候选对象,保色交换则通过减少不同旅行商之间不必要的交叉路径来提高BVNS的全局搜索能力。此外,设计了25个BCTSP案例来测试BVNS的性能。特别地,在其中5个小规模数据集上,还对比了BVNS与精确算法ε-constraint所得Pareto前沿之间的差距。仿真结果显示,BVNS对求解小规模或大规模BCTSP案例均是有效的,且其所得解的超体积、反转世代距离等指标均远优于4种对比算法。4)考虑到PCTSP是非对称的,而Delaunay三角剖分不能处理非对称模型,提出了一种部分优化元启发式VNS（PVNS）来求解PCTSP。PVNS由四个主要部分组成,即:保约束多插入算子、保约束的交换变异子、保约束2-exchange和保路径3-exchange。其中保约束多插入算子利用POPMUSIC法来确定候选边。基于仿真实验分析了这四种算子对PVNS全局搜索能力的重要影响。此外,对比了PVNS、LKH3和其它5算法在34个测试案例上的结果,得出了PVNS在大多数案例上的解均优于后六种算法的结论。特别地,考虑到自动调参软件的效果通常远优于手动调参,这里还利用irace软件包调试了PVNS及对比算法的所有参数。本文以超图作为描述工具,共建立了三种GCTSP,提出了三种高效的VNS求解算法,并应用于建模和求解任务对执行个体的访问允许性十分复杂的实际问题——电商仓库自主导航小车（AGV）任务调度。上述工作进一步丰富了CTSP的理论体系、拓宽了CTSP在实际工程应用中的前景。