旅行推销员问题:基于求解器

打开生活的脚本

这个例子展示了如何使用二进制整数规划来解决经典的旅行商问题。这个问题涉及到通过一组站点(城市)找到最短的封闭路线(路径)。在这种情况下，有200个站点，但你可以很容易地改变nStops变量以获得不同的问题大小。您将解决初始问题，并看到解决方案具有子故事。这意味着找到的最佳解决方案不会通过所有点给出一个连续路径，而是有几个断开连接的环。然后，您将使用迭代过程来确定子资源，添加约束，并重新运行优化，直到消除子流程。

关于基于问题的方法，请参见旅行推销员问题:基于问题．

问题公式化

用公式表示整数线性规划的旅行商问题:

生成所有可能的行程，意味着所有不同的站点对。
计算每次旅行的距离。
要最小化的代价函数是旅途中每次行程的行程距离之和。
决策变量是二元的，并且与每个行程相关联，其中每个1表示在行程中存在的行程，每个0表示不在行程中。
为确保行程包含每一站，应包含每一站正好包含两趟行程的线性约束。这意味着一次到达，一次离开。

生成停止

在一个粗糙的多边形代表美国大陆内产生随机止损

负载(“usborder.mat”，“x”，“y”，“xx”，“yy”）;rng (3“旋风”）%在缅因州和佛罗里达州做一个站点，并可复制nStops = 200;你可以使用任何数字，但问题的规模是N^2stopsLon = 0 (nStops, 1);%分配nStops的x坐标stopsLat = stopsLon;%分配坐标n = 1;而(n <= nStops) xp = rand*1.5;yp =兰德;如果inpolygon (xp, yp, x, y)%测试是否在边界内stopsLon (n) = xp;stopsLat (n) = yp;n = n + 1;结束结束

计算点之间的距离

因为有200个站点，有19,900次行程，这意味着19,900个二进制变量(# variables = 200 choose 2)。

生成所有行程，意味着所有对的停止。

idx = nchoosek (1: nStops, 2);

假设地球是平的，用勾股定理计算所有的旅行距离。

drawtext (dixs (:，1) - dixs (:，2))， color0000ff;．．.stopsLon (idx(: 1))——stopsLon (idx (:, 2)));lendist =长度(经销);

根据这个定义经销向量，旅行的长度是

dist'* x_tsp

在哪里x_tsp是二进制解向量。这是你试图最小化的旅行距离。

创建图形和绘制地图

用图来表示这个问题。创建一个图形，其中站点是节点，行程是边。

图G = (idx (: 1), idx (:, 2));

使用图形图显示停止。绘制没有图边的节点。

图hGraph = plot(G，“XData”stopsLon,“YData”stopsLat,“线型”，“没有”，“NodeLabel”, {});持有在绘制外部边界情节(x, y,的r -)举行从

约束

创建线性约束，使每个站点有两个相关的行程，因为必须有到每个站点的行程和离开每个站点的行程。

Aeq = spalloc (nStops、长度(idx) nStops * (nStops-1));%分配一个稀疏矩阵为ii = 1:nStops where dxs == ii;找到包含stop ii的行程whichIdxs =稀疏(sum (whichIdxs, 2));%包括ii在任何一端的行程Aeq (ii):) = whichIdxs ';%包含在约束矩阵中结束说真的= 2 * 1 (nStops 1);

二进制界限

所有决策变量都是二进制的。现在,设置intcon变量的个数，每个变量的下界为0，上界为1。

intcon = 1: lendist;1磅= 0 (lendist);乌兰巴托= 1 (lendist, 1);

优化使用intlinprog

这个问题已经准备好了。若要抑制迭代输出，请关闭默认显示。

选择= optimoptions (“intlinprog”，“显示”，“关闭”）;[x_tsp, costopt exitflag、输出]= intlinprog(经销、intcon [], [], Aeq,说真的,磅,乌兰巴托,选择);

用解决方案行程作为边创建一个新图。为此，在某些值不是精确整数的情况下，将解四舍五入，并将结果值转换为逻辑．

x_tsp =逻辑(圆(x_tsp));Gsol =图(idx (x_tsp, 1), idx (x_tsp, 2), [], numnodes (G));% Gsol = graph(idxs(x_tsp,1)，idxs(x_tsp,2));%在大多数情况下也有效

可视化解决方案

持有在突出(hGraph Gsol,“线型”，“- - -”)标题(“解决方案与Subtours”）

从地图上可以看到，该解决方案有几个子游览。到目前为止指定的约束并不能阻止这些子行程的发生。为了防止发生任何可能的子循环，您将需要大量的不等式约束。

Subtour约束

因为您不能添加所有的子游览约束，所以采用迭代的方法。检测当前解决方案中的子循环，然后添加不等约束以防止发生那些特定的子循环。通过这样做，您可以在几个迭代中找到合适的行程。

消除带有不等式约束的子行程。举个例子，如果你在一个子游览中有五个点，那么你有五条线连接这些点来创建子游览。通过实现一个不等式约束来消除这个子过程，即这5个点之间必须小于或等于4条线。

更重要的是，找出这五个点之间的所有直线，并限制解中出现的直线不超过四条。这是一个正确的约束，因为如果一个解中存在5条或更多的直线，那么这个解就会有一个子环(一个带有 $n$ 节点和 $n$ 边总是包含一个循环)。

通过识别中连接的组件来检测子行程Gsol，用当前解决方案中的边构建的图。Conncomp.返回一个向量，其中包含每条边所属的子游程的编号．

tourIdxs = conncomp (Gsol);numtours = max (tourIdxs);%分游次数流('# of subtours: %d\n', numtours);

小圈子数量:27个

包括线性不等式约束来消除子环，并反复调用求解器，直到只剩下一个子环。

lendist = spalloc (0, 0);%分配一个稀疏线性不等式约束矩阵b = [];而numtours > 1重复，直到只有一个子游览%添加子游览约束b = [b;零（numtours，1）];%分配bA = [; spalloc (numtours、lendist nStops)];猜测要分配多少个非零为ii = 1:numtours rowIdx = size(A,1) + 1;用于索引的%计数器subTourIdx = find(touridx == ii);%提取当前子游览的所有变量%特殊子tour，然后添加一个不等式约束来禁止%该子游览和所有使用这些站点的子游览。变化= nchoosek(1:长度(subTourIdx), 2);为var = (sum(idxs==subTourIdx(variables (jj,1))，2)) &．．.(和(idx = = subTourIdx(变化(jj, 2)), 2));(rowIdx whichVar) = 1;结束b(rowIdx) = length(subTourIdx) - 1; / /指定长度比分游站点少一次行程结束再次尝试优化[x_tsp, costopt exitflag、输出]= intlinprog(经销、intcon A、b Aeq,说真的,磅,乌兰巴托,选择);x_tsp =逻辑(圆(x_tsp));Gsol =图(idx (x_tsp, 1), idx (x_tsp, 2), [], numnodes (G));% Gsol = graph(idxs(x_tsp,1)，idxs(x_tsp,2));%在大多数情况下也有效%可视化的结果hGraph。线型=“没有”；%删除前面突出显示的路径突出(hGraph Gsol,“线型”，“- - -”) drawnow这次有多少次短途旅行?tourIdxs = conncomp (Gsol);numtours = max (tourIdxs);%分游次数流('# of subtours: %d\n'numtours)结束

分游数量:20

7个

9个

9个

二

7个

二

#分游:1

标题(“取消子行程的解决方案”）;持有从

解决方案质量

这个解代表了一个可行的旅行，因为它是一个单闭环。但是这是一种低成本的旅行吗?找出答案的一种方法是检查输出结构。

disp (output.absolutegap)

绝对间隙的小意味着解是最优的或有一个接近最优的总长度。