樸素限制
最樸素的限制為:每個節點有且僅有兩條邊。
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;
這樣得到的結果大機率如下圖所示,會有許多子回路。
子回路的個數通過如下進行計算:
tspsol = solve(tsp,'options',options)
tspsol.trips = logical(round(tspsol.trips))
Gsol = graph(idxs(tspsol.trips,1),idxs(tspsol.trips,2),[],numnodes(G));
tourIdxs = conncomp(Gsol)
numtours = max(tourIdxs); % Number of subtours
fprintf('# of subtours: %d\n',numtours);
如何消除子回路成為定義限制的關鍵問題。
額外的限制稱為子回路消除限制。
子回路消除限制
由于無法在問題求解的一開始就找到子回路,子回路隻能在通過上述樸素限制求解的基礎上進行。
基本的思路是,找到上述基本解中的子回路,通過增加限制消除子回路。
如何消除子回路?舉一個例子。如果一個子回路是5個節點組成的,這個子回路就有5條互聯的邊,增加的一個不等式限制為:這五個節點之間的邊不能多于5.
推廣得到:任意小于nSteps的集合若包含N個節點,則這N個節點包含的邊不能多于N。
在疊代的過程中遇到一個子回路則添加上述的一個限制,直到最終隻剩下1個子回路。代碼如下所示。
figure
hGraph = plot(G,'XData',stopsLon,'YData',stopsLat,'LineStyle','none','NodeLabel',{});
hold on
% Draw the outside border
plot(x,y,'r-')
hold on
% 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',options);
tspsol.trips = logical(round(tspsol.trips));
Gsol = graph(idxs(tspsol.trips,1),idxs(tspsol.trips,2),[],numnodes(G));
% Gsol = graph(idxs(tspsol.trips,1),idxs(tspsol.trips,2)); % Also works in most cases
% 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)
fprintf('# total trip length: %f\n',fval)
end
title('Solution with Subtours Eliminated');
疊代過程如下圖所示:
最終的限制如下所示。其中包含了41個消除子回路限制。
最終得到的結果如下圖所示:
解的最優性說明見下節。