Traveling Salesman Problem Without Return

9 次查看（过去 30 天）
Jake Smith
Jake Smith 2019-1-17
评论： Walter Roberson 2021-7-24
I've been looking at the traveling salesman problem with the code provided by MATLAB here:
https://www.mathworks.com/help/optim/examples/travelling-salesman-problem.html
While I understand most of the content, I'm wondering if there is a variation that can be implemented that doesn't form a complete loop after the subtours have been removed, but is still optimized for distance.
In other words, what can be changed in the existing code so there is no return to a "start" point after the last point has been reached?
  1 个评论
Walter Roberson
Walter Roberson 2019-1-17
That is a bit tricky in linear programming. You would be trying to program the conditions that:
  • exactly one object has an in-degree of 0
  • all other objects have an in-degree of exactly 1
  • exactly one object has an out-degree of 0
  • all other objects have an out-degree of exactly 1
You can give constraints such as the sum of the in-degree over all nodes is (nodes-1) and you can give constraints such as the in-degree of each node is exactly 1, but ... hmmm...
You can add constraints that the in-degree of each node is either 0 or 1 (>=0 and <=1) , and that the out-degree of each node is either 0 or 1, and you can add constraints that the sum of the in degrees is (nodes-1) and the sum of the out degrees is (nodes-1) .
But at the moment, there would still seem to be the loophole that it could end up creating a tour of all but one of the nodes and leaving that other node isolated. The in-degree of all of the nodes in the tour would be 1, and the out-degree of all of the nodes in the tour would be 1, and the in-degree of the isolated node would be 0, and the out-degree of the isolated node would be 0, and the total in-degree would be (nodes-1) and the total out-degree would be (nodes-1). The equality and inequality constraints would be satisfied. Ah, but if you forced the total degree for each node to be >= 1 and <= 2 then that would eliminate this possibility and by the pigeon-hole principle you would have to get a path instead of a tour.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Iuliu Ardelean
Iuliu Ardelean 2021-7-15
编辑：Iuliu Ardelean 2021-7-16
Hi
If you know your start and end points, and your graph is not directed:
start_idx = 1; % make node 1 start point
end_idx = 2; % make node 2 end point
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
whichIdxs = outedges(G, start_idx);
constr2trips(start_idx) = sum(trips(whichIdxs)) == 1;
whichIdxs = outedges(G, end_idx);
constr2trips(end_idx) = sum(trips(whichIdxs)) == 1;
tsp.Constraints.constr2trips = constr2trips;
  2 个评论
Iuliu Ardelean
Iuliu Ardelean 2021-7-23
编辑：Iuliu Ardelean 2021-7-23
If your graph is directed, some modifications are necessary.
You will need to create a digraph.
Then, for constraints, set inedges and outedges of each point to either 0 or 1, very similar to the not directed graph example above.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息

标签

产品


版本

R2017a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by