【組合優化】旅行商問題Traveling Salesman Problem(TSP)-限制定義

樸素限制

最樸素的限制為：每個節點有且僅有兩條邊。

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個消除子回路限制。

最終得到的結果如下圖所示：

解的最優性說明見下節。