求助：规划求解解决路线问题

garylu3000

各位好！

应用的“规划求解”出错了，提示“规划求解遇到目标或约束单元格的错误值”。

在附件的B1:C2定义了四个单元格，名称定义分别为：B1 - node1  C1- node2 B2- node3  C2- node4
现在需要在这四个单元格中定义一条路线，使每个单元格走且只能走一次，而且两次移动的单元格必须是相邻的。

从1开始，最后回到1。

如现在应该有两种方案：1-2-3-4 或者 1-3-4-2


文件中应用了规划求解方法

设置了目标单元格：L8 =4


变量单元格：H4:K7

约束：

L4:L7 =1
H8:K8 =1

H4 /I5 /J6 /K7 =0（这四条路线不能用）

H4:K7 为二进制(0/1取值)

S4:S7=1 （移动必须为相邻单元格）

但是设置好的规划求解方案却无法执行，提示“规划求解遇到目标或约束单元格的错误值”。

恳请各位高人帮忙解决！谢谢！

灰袍法师

很常见的新手错误

规划求解不可使用任何不连续的函数，包括所有逻辑判断，引用，绝对值函数都不能用的

只能用加减乘除乘方开方三角函数对数，其他一概不能用。

论坛搜索 tsp 即可

garylu3000

灰刨法师果然高人！

不知道可否给些更多资料让我学习学习，不胜感激之至！

谢谢！

garylu3000

法师高人，我将判断相邻的函数约束进行修改为：
(终点X-起点X)^2 + (终点Y-起点Y)^2 = 1

but it still doesn't work, Could you pls help me with it?

Many Thanks.

twoleavs

不知是否这样？参见附件： path(复件).rar (7.32 KB, 下载次数: 13)

2011-5-19 14:14 上传

点击文件名下载附件

灰袍法师

五楼做的也不对

如果一定要相邻，那么根本不需要些约束条件，把不相邻的距离写成9999即可

这样就可以保证 任何一条走了不相邻路径的解，必定不是最小值

又或者增加 约束所有从本地点出发的路径长度，要求不能大于9999，这样也可以保证不走相邻路径，而且速度会比上面无约束的求解方案更快

楼主的模型没有处理子回路问题，也就是如果求出的解是 1-2 2-1 3-4 4-3，那么也是合符楼主模型的限制，但是却不合要求

你搜索 tsp，就可以找到这个
http://club.excelhome.net/thread-372982-1-1.html

[ 本帖最后由 灰袍法师 于 2011-5-19 17:10 编辑 ]

fdd

用LINGO解：
model:
        sets:
                dt/1..4/:u;
                links(dt,dt)/1,2 1,3 2,1 2,4 3,1 3,4 4,2 4,3/:x;
        endsets
        n=@size(dt);
        @for(links:@bin(x));
        @for(dt(i)|i#gt#1:@sum(links(j,i):x(j,i))=1);
        @for(dt(i)|i#eq#1:@sum(links(j,i):x(j,i))=0);
        @for(dt(i)|i#eq#1:@sum(links(i,j):x(i,j))=1);
        @for(dt(i):@for(dt(j)|j#gt#1 #and# @in(links,i,j):u(i)-u(j)+n*x(i,j)<=n-1););
        @for(dt(i):u(i)<=n-1);
end

yanglegeyang

灰袍法师 发表于 2011-5-19 17:01
五楼做的也不对

如果一定要相邻，那么根本不需要些约束条件，把不相邻的距离写成9999即可

您好，我是个小白，这边要解决就5个供应商一个工厂的tsp问题，从工厂出发经过5个供应商后返回供应商，该怎么进行解决，还有如果其中增加了取货重量问题就是循环取货问题该怎么进行解决（用规划求解）

世界客都

yanglegeyang 发表于 2024-2-28 20:26
您好，我是个小白，这边要解决就5个供应商一个工厂的tsp问题，从工厂出发经过5个供应商后返回供应商，该 ...

灰袍法师16年就没登录了，你这个旅行商问题可以发帖求助，大家看到后自然会帮助你。