最大值最小化着色旅行商问题的研究及应用

摘要

着色旅行商问题(Colored Traveling Salesman Problem，CTSP)是一种泛化的多旅行商问题，其通过引入颜色来区分城市对旅行商多样的访问允许性，解决了多旅行商问题难以描述城市可访问性差别的难题。但目前对其研究局限于以总旅行路径最短为优化目标，完全未考虑商人个体路程或花费的平衡，从而容易导致负载的分布不均，出现“短板效应”。故本文提出一种以最小化最大个体路径为目标的着色旅行商问题-最大值最小化着色旅行商问题(Min-Max CTSP:MM-CTSP)，其有望弥补上述“短板”，达到尽量均衡个体间任务或负载的效果。本文主要研究了其数学建模、启发式求解方法及相关应用。具体的内容与成果如下:
　　首先，建立了MM-CTSP的0-1非线性整数规划模型，并证明了问题的NP难性，同时采用LINGO非线性求解器对问题进行了精确求解。结果表明，LINGO只能求解很少规模的问题。
　　其次，针对适中和较大规模的问题，设计了本问题的遗传算法(GA)、差分进化算法(DE)、萤火虫算法(FA)、人工蜂群算法(ABC)和种群增量学习(PBIL)算法。接着，分别结合贪婪算法、爬山算法、模拟退火算法、插入搜索算法(IN)和2-opt对这五种基本求解算法进行了改进研究，提高了算法求解的收敛速度和局部搜索能力。
　　然后，设计了广泛的实验对提出的算法进行了全面的性能比较。分别在固定函数评价次数和固定运行时间下，从解质量、时耗和收敛速度三个方面依次对五种基本求解算法、五种局部搜索算法，以及带局部操作的基本求解算法进行了性能比较。结果表明，五种基本求解算法中，FA的性能最好;五种局部搜索算法中，2-opt优化的效果最好;带局部操作的算法中，在适中规模问题时，GA+IN的性能最好，GA+2-opt和FA+IN性能相当，仅次于GA+IN;在较大规模问题时，FA+IN、GA+IN和GA+2-opt的解质量都不错，FA+IN可取得解质量和时耗的较好平衡，而GA+IN和GA+2-opt的时耗较大。
　　最后，将MM-CTSP应用到双横梁水切割拼花的路径规划中，并与总路径最短化进行了效果对比，实验结果表明，MM-CTSP可以有效地最小化最大工作时间，弥补“短板”，提高作业系统的运行效率。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．3 论文研究内容及组织结构

第二章 最大值最小化CTSP的定义、建模与精确求解

2．1 CTSP的定义

2．2 最大值最小化CTSP建模与精确求解

2．2．1 最大值最小化CTSP的0-1整数规划模型

2．2．2 最大值最小化CTSP的LINGO求解

2．3 本章小结

第三章 最大值最小化CTSP的算法设计

3．1 遗传算法的设计

3．1．1 GA的编码设计

3．1．2 GA的变异和交叉操作

3．1．3 GA的选择算子设计

3．1．4 GA的适应度函数设计

3．1．5 最大值最小化CTSP的GA求解步骤

3．2 差分进化算法的设计

3．2．1 DE的编码设计

3．2．2 DE的种群初始化

3．2．3 DE的变异操作

3．2．4 DE的交叉操作

3．2．5 DE的选择操作

3．2．6 最大值最小化CTSP的DE求解步骤

3．3 人工蜂群算法的设计

3．3．1 ABC的引领蜂搜索策略

3．3．2 ABC的跟随蜂搜索策略

3．3．3 ABC的侦查蜂行为机制

3．3．4 最大值最小化CTSP的ABC求解步骤

3．4 种群增量学习算法的设计

3．4．1 PBIL算法的编码设计

3．4．2 PBIL算法种群初始化

3．4．3 PBIL算法概率模型的更新机制

3．4．4 最大值最小化CTSP的PBIL算法求解步骤

3．5 萤火虫算法的设计

3．5．1 FA的编码和亮度设计

3．5．2 FA的吸引力和移动策略

3．5．3 最大值最小化CTSP的FA求解步骤

3．6 算法检验

3．7 本章小结

第四章 最大值最小化CTSP算法的改进

4．1 基本启发式算法的缺点和改进方案

4．1．1 缺点

4．1．2 改进方案

4．2 算法的贪婪初始化

4．2．1 贪婪算法的设计

4．2．2 贪婪初始化流程

4．2．3 效果检验

4．3 基于爬山操作的算法改进

4．3．1 爬山算法设计

4．3．2 爬山算法求解流程

4．3．3 效果检验

4．4 基于模拟退火的算法改进

4．4．1 模拟退火算法的设计

4．4．2 模拟退火算法求解流程

4．4．3 效果检验

4．5 基于插入操作的算法改进

4．5．1 插入算法的设计

4．5．2 插入算法求解流程

4．5．3 效果检验

4．6 基于2-opt的算法改进

4．6．1 2-opt算法设计

4．6．2 2-opt的求解流程

4．6．3 效果检验

4．7 本章小结

第五章 求解算法比较研究

5．1 实验设计

5．2 相同函数评价次数下的对比实验

5．2．1 五种基本求解算法的比较

5．2．2 五种局部算法的比较

5．2．3 带相同局部操作的五种求解算法比较

5．2．4 带不同局部操作的五种求解算法比较

5．3 相同运行时间下的对比实验

5．3．1 五种基本求解算法的比较

5．3．2 同一求解算法带不同局部操作的比较

5．4 本章小结

第六章 最大值最小化CTSP在多横梁水切割中的应用

6．1 双横梁水切割机床及研究议题简介

6．2 水切割拼花介绍

6．3 拼花切割路径规划的CTSP建模与求解

6．3．1 切割路径规划的CTSP建模

6．3．2 总路径最短化与最大路径最小化效果对比

6．4 本章小结

第七章 总结与展望

7．1 总结

致谢

参考文献

附录

攻读硕士学位期间的研究成果