# 推销员行程问题：基于问题

### 问题表示

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

• 计算每次行程的距离。

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

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

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

### 生成停留点

```load('usborder.mat','x','y','xx','yy'); rng(3,'twister') % Makes 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) % tTest 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'*trips`

### 创建图和绘制地图

`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```

### 创建变量和问题

```tsp = optimproblem; trips = optimvar('trips',lendist,1,'Type','integer','LowerBound',0,'UpperBound',1);```

`tsp.Objective = dist'*trips;`

### 约束

```constr2trips = optimconstr(nStops,1); for stop = 1:nStops whichIdxs = outedges(G,stop); % Identify trips associated with the stop constr2trips(stop) = sum(trips(whichIdxs)) == 2; end tsp.Constraints.constr2trips = constr2trips;```

### 求解初始问题

```opts = optimoptions('intlinprog','Display','off'); tspsol = solve(tsp,'options',opts)```
```tspsol = struct with fields: trips: [19900×1 double] ```

### 可视化解

```tspsol.trips = logical(round(tspsol.trips)); Gsol = graph(idxs(tspsol.trips,1),idxs(tspsol.trips,2));```

```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 ```

```% Index of added constraints for subtours k = 1; while numtours > 1 % Repeat until there is just one subtour % Add the subtour constraints for ii = 1:numtours inSubTour = (tourIdxs == ii); % Edges in current subtour a = all(inSubTour(idxs),2); % Complete graph indices with both ends in subtour constrname = "subtourconstr" + num2str(k); tsp.Constraints.(constrname) = sum(trips(a)) <= (nnz(inSubTour) - 1); k = k + 1; end % Try to optimize again [tspsol,fval,exitflag,output] = solve(tsp,'options',opts); tspsol.trips = logical(round(tspsol.trips)); Gsol = graph(idxs(tspsol.trips,1),idxs(tspsol.trips,2)); % Plot new solution 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 ```