智能优化算法应用：TSP的数学描述

TSP的描述十分简单，即寻找一条最短的遍历N个城市的路径，其数学描述如下：

设有N个城市的集合C=｛c1，c2，…，cN｝，每两个城市之间的距离为d（ci，cj）∈R+，其中，ci，cj∈C（1≤i，j≤N），求使目标函数

达到最小的城市序列｛c∏（1），c∏（2），…，c∏（N）｝，其中，∏（1），∏（2），…，∏（N）是l，2，…，N的全排列。

遗传算法充分利用适应度函数的信息而完全不依靠其他补充知识。正是基于遗传算法的这一特点，对于各种TSP只需找到它们各自的目标函数，以此作为适应度评估的基础，就可以将解决问题的遗传方案统一起来。对于现实问题，由于限制条件的增加，TSP可衍生出许多相关的问题，通常有以下几种。

1.有时间约束的TSP

要求在一定时间内访问每个城市，就会产生有时间约束的TSP。由一个旅行商访问N个城市，要求访问每个城市一次且仅一次，尽可能在一定时间范围内访问，否则将产生等待或延迟损失，求成本最小的旅行路线。下面推导该问题的目标函数。

以1，2，…，N表示N个城市，以cij表示旅行商从城市i到城市j的运输成本，若i=j可以将cij赋为0；tij表示旅行商从城市i到城市j所花费的时间；si表示旅行商到达城市i的时刻，要求尽可能落在时间范围［Ai，Di］内；xij为0-1决策变量，取值为1表示旅行路线中包括路段（i，j），取值为0表示旅行路线中不包括路段（i，j）。tij和si有以下关系

不妨设城市1为旅行商问题的出发点和返回点，则该问题的目标函数为(www.xing528.com)

式（2.24）右端由三部分组成：第一部分表示不考虑时间约束的旅行费用（或距离，在简单TSP中距离和费用是成正比的）；第二部分表示旅行商到达城市i的时刻早于Ai，则在该城市等待，等待单位时间处以惩罚值α；第三部分表示若旅行商到达城市i的时刻晚于Di，则推迟访问，推迟单位时间处以惩罚值β。

如果旅行商必须在给定的时间范围内访问各个城市，超过时间范围，所得到的旅行商路线为不可行解，则该问题的目标函数如下

其中，除了γ外，各变量的含义同式（2.24）。由于如果不满足给定的时间约束，就为不可行解，所以这里的γ应为一趋于正无穷的参数。需要指出的是，由于遗传算法的初始群体是随机选取的。这样，在初始群体中会出现部分不可行解，这里允许不可行解的存在，但它们的适应度将很低，随着代数的增加，不可行解将逐步被淘汰。

2.多重TSP

多重TSP是指由m（1≤m≤M）个旅行商共同访问N个城市，M为最大允许的旅行商数，旅行商从同一个指定的城市（中心城市）出发，分别旅行一条路线，使得其余每个城市有且仅有一个旅行商作一次访问，最后回到原来的出发城市，要求总的旅行路程最短。首先这个问题在编码上就不同于一般的TSP，但可以通过增加虚拟城市的方法转换成直接对城市进行编码。不妨设由中心城市1，需旅行商到其余编号为2，3，…，N的N-1个城市，设派M个旅行商来完成这样的访问。通过设置M-1个虚拟城市（实际上代表同一个出发的中心城市）且编号分别为N+1，N+2，…，N+M-1来解决在编码上存在的问题。需要指出的是，在计算距离的时候按实际意义计算，如N+l和N+2到城市k的距离是一样的，因为N+I和N+2是同一个出发城市，只是标号不同。这样就可以将多重TSP转化为求解N+M-1个城市的普通TSP。例如，6个城市，由两个旅行商进行访问，数字是城市编号，城市7是虚拟城市，串码为l—2—3—6—7—4—5表示了两条子路径：a=1—2—3—6—l，b=1—4—5—l，这样就可以很容易地确定出目标函数。

3.时间约束性多重TSP

时间约束性多重TSP基本上可以看成是上述两种情况的组合，其解决方法可以先将多重问题转化为普通约束性TSP，再按已经讨论过的方法确定目标函数，从而确定适应度函数。至此，可以将三种衍生的TSP转化为普通的TSP，用遗传算法进行有效的求解。