TSP问题及LINGO求解技巧.docx

j j 1 表 145105014910 表 1 4 5 10 5 0 14 9 10 9 23 16 2 7 0 3 10 9 14 5 14 17 17 3 4 3 0 5 9 10 21 8 27 12 5 8 9 9 14 0 7 8 7 20 19 1 0 7 4 5 8 6 12 13 11 18 10 18 17 12 16 19 13 18 12 16 0 8 13 14 8 9 7 5 23 0 18 12 9 11 17 27 23 20 25 21 18 0 16 7 12 5 21 10 8 13 0 23 21 18 n TSP问题及 LINGO 求解技巧 巡回旅行商问题 (Traveling Salesman Problem， TSP)，也称为货郎担问题。最早可以追 溯到 1759年Euler 提出的骑士旅行问题。 1948年，由美国兰德公司推动， TSP成为近代组合优 化领域的一个典型难题。它已经被证明属于 NP难题。 用图论描述 TSP，给出一个图 G (V , E) ，每边 e E 上有非负权值 w(e) ,寻找 G的 Hamilton 圈C，使得 C的总权 W (C) w(e) 最小 . e E(C) 几十年来，出现了很多近似优化算法。如近邻法、贪心算法、最近插入法、最远插入法、 模拟退火算法以及遗传算法。这里我们介绍利用 LINGO 软件进行求解的方法。 问题 1 设有一个售货员从 10个城市中的某一个城市出发，去其它 9个城市推销产品。 10个 城市相互距离如下表。 要求每个城市到达一次仅一次后， 旅行路线，使总路程最短。 10个城市距离表 城市 1 2 3 4 5 6 7 8 9 10 回到原出发城市。 问他应如何选择 6 6 14 10 9 7 0 13 5 25 13 我们采用线性规划的方法求解 设城市之间距离用矩阵 d 来表示， dij 表示城市 i 与城市 j 之间的距离。设 0--1矩阵 X 用 来表示经过的各城市之间的路线。设 x ij x 0 若城市 i不到城市 j 1 若城市 i到城市j , 且i在j前 考虑每个城市后只有一个城市，则： xij 1, i 1,… , n j i 考虑每个城市前只有一个城市，则： i i 1 n n xij 1, j 1,… , n； i j 但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。 为 此 我 们 引 入 额 外 变 量 ui (i 1,… , n） ， 附 加 以 下 充 分 约 束 条 件 ： ui uj nxij n 1, 1 i j n； 该约束的解释： 如 i 与 j 不会构成回路，若构成回路，有： xij 1， xji 1 ，则： ui uj 1， uj ui 1，从而有： 0 2，导致矛盾。 如 i， j 与 k 不会构成回路，若构成回路，有： xij 1， xjk 1， xki 1则： ui uj 1， uj uk 1， uk ui 1从而有： 0 3，导致矛盾。 其它情况以此类推。 于是我们可以得到如下的模型： i i 1 j 1 ni n i , j 1 n n min z dij xij xij 1, j i j s.t. xij 1, j i ui uj nxij xij 0或1, ui为实数 , 1,L , n i 1,L , n n 1, 1 i j n i , j 1,L , n i 1,L , n 前面问题的 Lingo 程序 !TSP quesion; MODEL: SETS: city/1..10/:u; link(city,city):d,x; ENDSETS DATA: d= 0 7