TSP笔记


TSP即旅行商问题,其可以被描述为从一点A出发,经过所有点返回A点,求每个节点(最好)被访问一次的最短路径。

怎样求解TSP


TSP问题属于NP问题的一种,对于少量节点可以使用穷举法,对于大量节点的TSP问题其时间复杂度是O(n!),非常恐怖,一般使用数学规划软件求解。本文将使用Lingo实现TSP求解。

具体描述


在一个由n个顶点构成的网络中,要求找出一个包括所有顶点的具有最小损耗(如最短距离或最小时间代价)的环路。一个环路也就是一个回路,因此可以将任何一个点作为起点和终点。

求解过程


确定变量

  1. 首先建立0-1决策变量代表起点为终点为的路径是否在路线中。

  2. 代表经过起点为终点为的路径所花费的代价。

确定约束

  1. 由于每个节点只能被访问一次,那么对于节点被当作起点的次数只有1次,仅有有一个。同理节点被当作终点的次数只有1次,仅有有一个

  2. 为了防止出现子回环,如果那么

确定目标函数

  • 以总的行驶代价最小为目标

写出求解模型(数学)

minZ=\sum_{i=1}^{n}\sum_{j=1}^{n}C_{ij}X_{ij}\\
\sum_{i=1}^{n}X_{ij}=1\quad j=1,2,..,n\\
\sum_{j=1}^{n}X_{ji}=1\quad i=1,2,..,n\\
X_{ij}+X_{ji}<=1\quad i=1,2,...,n;j=1,2,..,n;i不等于j

写出求解模型(lingo)

model:
title:100个节点的TSP问题求解
	sets:
		city/1..100/:u;
		link(city,city):dist,x;
	endsets

	data:
		dist = @ole('D:\Documents\教材\物流系统工程\excelTSP(Heuristic).xls','data_dist');
	enddata

	min = @sum(link: dist*x ); ! Object Function
    n = @size(city);
	@for(city(j): @sum(city(i):x(i,j)) = 1);
    @for(city(i): @sum(city(j):x(j,i)) = 1);
    @for(link(i,j)|i#NE#j: x(i,j)+x(j,i)<=1);
	@for(link:@bin(x));
end

本文章使用limfx的vscode插件快速发布