我正在研究旅行商问题，无法解决如何解决问题 . 问题包括十个 Worker ，十个工作场所，他们应该被驱赶，一辆车一个接一个地开车 . 每公里的费用为1.5美元 . 此外，所有节点（ Worker 和工作场所）都位于10 * 10矩阵中，矩阵中每个块之间的距离为1 km .
应该使用AMPL解决问题 .
我已经计算了excel中每个坐标之间的距离，并将复制粘贴到AMPL中的dat.file .
This is my mod.file so far (without the constrains):
param D > 0;
param D > 0;
set A = 1..W cross 1..D;
var x{A}; # 1 if the route goes from person p to work d,
# 0 otherwise
param cost;
param distance;
minimize Total_Cost:
sum {(w,d) in A} cost * x[w,d];
1 回答
好的，所以你的路线看起来像：start-worker 1-job 1-worker 2-job 2-worker 3-job-3 -...- job 10-end（给予或采取开始和结束点，取决于你如何制定问题 .
在这种情况下，路线的“ Worker n工作”部分是预先确定的 . 您不需要在路径优化中包含“worker n-job n”成本，因为路由的那些部分没有选择（当然，您确实需要记住它们来计算总成本） .
所以你在这里有一个基本的TSP，有10个“目的地”（每个目的地代表一个 Worker 及其分配的工作），但是具有不对称的成本矩阵（因为从工作i到 Worker j的旅行成本与成本不同）从工作j到 Worker 的旅行i） .
如果您已经有基本TSP的实现，那么应该很容易适应 . 如果没有，那么您需要编写一个并对非对称成本矩阵进行小的更改 . 我在AMPL中看到了两种不同的方法 .
2 -D带有地形消除的决策矩阵
决策变量x {1..10,1..10}定义为：如果路径从作业i转到作业j，则x [i，j] = 1，否则为0 . 约束要求此矩阵的每一行和每列只有一个1 .
采用这种方法的挑战性部分是防止小区（即产生的“路线”实际上是两个或更多个单独的循环而不是一个大循环） . 听起来你现在的尝试就是在这个阶段 .
对于子层问题的一种解决方案是迭代方法：
编写一个包含除了地下防护之外的所有要求的实现 .
解决此实现 .
检查生成的解决方案以获得小计 .
如果未找到子量，则返回解决方案并结束 .
如果确实找到了子列，请添加一个可以阻止该特定子量的约束 . （识别参数中涉及的弧，并设置一个约束，暗示它们不能全部被选中 . ）然后转到＃2 .
对于小练习，您可以手动进行小区消除 . 对于更大的练习，或者如果您的讲师在this thread中没有提供实施示例的话 .
3 -D具有时间维度的决策矩阵
在这种方法下，你设置一个决策变量x {1..10,1..10,1..10}，其中x [i，j，t] = 1，如果路线从工作i到 Worker j的时间t，否则为0 . 然后你的约束要求路由往返于每个作业/工作者组合一次，如果它在时间t转到工作者i那么它必须在时间t 1从作业i开始（除了第一个/最后一个问题），它是在时间t完成一件事，并且时间10处的 endpoints 与时间1处的起点匹配（假设您想要电路） .
这可以防止小轮，因为它会强制在时间1的某个点开始的路线，在时间10返回到该点，并且不会多次访问任何其他点 - 这意味着它必须完全通过所有这些 .