多目标MIN-MAX度最小树问题及其求解

来源：上海理工大学学报杂志2019年第3期北京时间：

作者：魏欣

单位：上海理工大学 管理学院, 上海 200093,上海理工大学 管理学院, 上海 200093

摘要：在多目标最小生成树问题和MIN-MAX度最小树问题的基础上，探讨使生成树最大顶点度数以及总权重都尽可能小的另类多目标MIN-MAX度最小生成树问题。分析了这一特殊的顶点度约束与Hamilton路的关联性质，在此基础上设计了先Hamilton路再MIN-MAX度最小树的独特求解方案。根据初始条件不同，当网络图不存在Hamilton路时，引入改进的蚁群优化算法，将转移概率由基本的指数形式改进为线性形式，在不影响求解质量的前提下，提高计算效率。针对以上策略，设计了相应的求解方案，并在计算机上用Delphi编程实现。大量数值算例验证表明，算法能快速有效地求解多目标情形下的MIN-MAX度最小生成树问题。

关键词：多目标;MIN-MAX度;生成树;Hamilton路

基金资助：国家自然科学基金资助项目（71401106）；教育部人文社科规划基金资助项目（16YJA630037）；上海市软科学研究重点项目（18692110500）