# 推销员行程问题：基于求解器

### 问题表示

• 生成所有可能的行程，意味着经过所有不同停留点对组。

• 计算每次行程的距离。

• 要计算最小值的代价函数是行程中每次旅行的旅行距离之和。

• 决策变量是与每个行程相关联的二元变量，其中每个 1 表示环程中存在的一次行程，每个 0 表示不在环程中的一次行程。

• 为确保环程包括每个经停留点，应加入这样一个线性约束：每个停留点都正好涉及两段行程。这意味着一段行程到达该停留点，一段行程离开该停留点。

### 生成停留点

```load('usborder.mat','x','y','xx','yy'); rng(3,'twister') % Makes a plot with stops in Maine & Florida, and is reproducible nStops = 200; % You can use any number, but the problem size scales as N^2 stopsLon = zeros(nStops,1); % Allocate x-coordinates of nStops stopsLat = stopsLon; % Allocate y-coordinates n = 1; while (n <= nStops) xp = rand*1.5; yp = rand; if inpolygon(xp,yp,x,y) % Test if inside the border stopsLon(n) = xp; stopsLat(n) = yp; n = n+1; end end```

### 计算停留点之间的距离

`idxs = nchoosek(1:nStops,2);`

```dist = hypot(stopsLat(idxs(:,1)) - stopsLat(idxs(:,2)), ... stopsLon(idxs(:,1)) - stopsLon(idxs(:,2))); lendist = length(dist);```

`dist'*x_tsp`

### 创建图和绘制地图

`G = graph(idxs(:,1),idxs(:,2));`

```figure hGraph = plot(G,'XData',stopsLon,'YData',stopsLat,'LineStyle','none','NodeLabel',{}); hold on % Draw the outside border plot(x,y,'r-') hold off```

### 约束

```Aeq = spalloc(nStops,size(idxs,1),nStops*(nStops-1)); % Allocate a sparse matrix for ii = 1:nStops whichIdxs = (idxs == ii); % Find the trips that include stop ii whichIdxs = sparse(sum(whichIdxs,2)); % Include trips where ii is at either end Aeq(ii,:) = whichIdxs'; % Include in the constraint matrix end beq = 2*ones(nStops,1);```

### 二元边界

```intcon = 1:lendist; lb = zeros(lendist,1); ub = ones(lendist,1);```

### 使用 intlinprog 进行优化

```opts = optimoptions('intlinprog','Display','off'); [x_tsp,costopt,exitflag,output] = intlinprog(dist,intcon,[],[],Aeq,beq,lb,ub,opts);```

```x_tsp = logical(round(x_tsp)); Gsol = graph(idxs(x_tsp,1),idxs(x_tsp,2),[],numnodes(G)); % Gsol = graph(idxs(x_tsp,1),idxs(x_tsp,2)); % Also works in most cases```

### 可视化解

```hold on highlight(hGraph,Gsol,'LineStyle','-') title('Solution with Subtours')```

### 子环程约束

```tourIdxs = conncomp(Gsol); numtours = max(tourIdxs); % number of subtours fprintf('# of subtours: %d\n',numtours);```
```# of subtours: 27 ```

```A = spalloc(0,lendist,0); % Allocate a sparse linear inequality constraint matrix b = []; while numtours > 1 % Repeat until there is just one subtour % Add the subtour constraints b = [b;zeros(numtours,1)]; % allocate b A = [A;spalloc(numtours,lendist,nStops)]; % A guess at how many nonzeros to allocate for ii = 1:numtours rowIdx = size(A,1) + 1; % Counter for indexing subTourIdx = find(tourIdxs == ii); % Extract the current subtour % The next lines find all of the variables associated with the % particular subtour, then add an inequality constraint to prohibit % that subtour and all subtours that use those stops. variations = nchoosek(1:length(subTourIdx),2); for jj = 1:length(variations) whichVar = (sum(idxs==subTourIdx(variations(jj,1)),2)) & ... (sum(idxs==subTourIdx(variations(jj,2)),2)); A(rowIdx,whichVar) = 1; end b(rowIdx) = length(subTourIdx) - 1; % One less trip than subtour stops end % Try to optimize again [x_tsp,costopt,exitflag,output] = intlinprog(dist,intcon,A,b,Aeq,beq,lb,ub,opts); x_tsp = logical(round(x_tsp)); Gsol = graph(idxs(x_tsp,1),idxs(x_tsp,2),[],numnodes(G)); % Gsol = graph(idxs(x_tsp,1),idxs(x_tsp,2)); % Also works in most cases % Visualize result hGraph.LineStyle = 'none'; % Remove the previous highlighted path highlight(hGraph,Gsol,'LineStyle','-') drawnow % How many subtours this time? tourIdxs = conncomp(Gsol); numtours = max(tourIdxs); % number of subtours fprintf('# of subtours: %d\n',numtours) end```
```# of subtours: 20 # of subtours: 7 # of subtours: 9 # of subtours: 9 # of subtours: 3 # of subtours: 2 # of subtours: 7 # of subtours: 2 # of subtours: 1 ```
```title('Solution with Subtours Eliminated'); hold off```

### 解质量

`disp(output.absolutegap)`
``` 0 ```