秦媛媛

（江苏财经职业技术学院，江苏 淮安 223003）

一、引言

人们在日常生活当中经常会遇到关于组合优化方面的问题，该类问题主要任务是要在组合问题所有的可行解集合里面找到最优的解，一般可以表示成：令集合Ω={s1，s2，…，sn}，该集合Ω是为一切状态组合而成的问题解的集合，C(si)是状态si是所照应的目标函数的解，要求寻找最优解s，使得对于所有的si∈Ω，有C(s)=minC(si)。常见的组合优化问题包括：旅行商问题（TravelingSalesman Problem-TSP）、生产调度问题（Production Scheduling Problem，如Flow-Shop，Job-Shop）、0-1 背包问题（KnapsackProblem）、装箱问题（Bin Packing Problem）、图着色问题（Graph ColoringProblem）、聚类问题（ClusteringProblem）和最大团问题等。该类问题的表达很简单，同时表现出鲜明的工程行业相关特性，然而想获得最优解相对较难，根本的原因在于使用传统的解决这类问题的算法需要很长的运算时间和很大的存储容量，对计算机性能的要求很高，这就是常见的一个词“组合爆炸”的由来。组合优化问题的复杂性和应用广泛引起研究人员的对其理论和算法的研究热情，各种启发式算法纷纷展现。本文从应用十分广泛的旅行商问题出发，研究应用一种启发式算法来解决此类问题。

二、研究现状

旅行商问题为比较典型的组合优化的应用案例，它通常被这样描述为：旅行推销员经常会面临这样一种问题，就是在给出既定的许多城市（坐标点已定）和这些城市之间的相对距离条件后，从中求解出推销员走过每个城市一次然后还能回到起点城市的最短的回路，还可以找到推销员行走过路程的最短路径。旅行商问题还能衍生用至像车辆调度优化问题、运输路线规划、物流和计算机应用网络等领域里，应用方向相当广泛。……