不确定旅行商问题的鲁棒模型与算法

摘要：

考虑到不确定参数在旅行商问题(TSP)中广泛存在,在Bertsimas鲁棒离散优化理论的框架下,建立了不确定旅行商问题的鲁棒优化模型,并按转换规则将鲁棒模型转换为鲁棒对等模型.给出了一种求解旅行商问题的基于Prufer数编码的单亲遗传算法,与求解该类问题的传统遗传算法相比,该算法缩减了染色体长度,避免了传统交叉和变异操作破坏染色体可行解的缺陷.通过算例验证,表明该算法有较高的求解效率,所建立的鲁棒模型在不确定环境下能得到较好的鲁棒解.

关键词：不确定旅行商问题、鲁棒优化、遗传算法、Prufer编码、鲁棒解

所属期刊栏目：34

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61364026,61164003;甘肃省科技计划项目1308RJYA030

在线出版日期：2014-08-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：2090-2092,2098