mathematical-optimization - 具有最大日长和特定节点开始/结束日的旅行推销员问题

Question

旅行商问题 (TSP) 表述如下：

• 给定一个有向图 G = (V, E)，其中 V = {1, ..., n} 是一组节点，E <= V x V 是一组弧。
• 让每个弧 e = (i,j) 被分配一个数字 c[i,j]，它是弧 e 的长度。
• 问题是找到一条通过 G 的每个节点恰好一次的最小长度闭合路径。

对问题的一些额外限制/修改：

• “推销员”每天在同一个节点（比如节点 1）开始和结束。
• 推销员每天最多可以工作 10 小时。
• 一旦业务员到达一个节点，他们必须执行一些工作，每个节点的工作量将在 1-4 小时之间变化。在开始/结束节点（节点 1）不需要做任何工作。
• 推销员可以多次穿越同一个节点，但任何重复的节点访问都不需要任何额外的工作（即推销员只是在前往下一个节点的途中穿越节点）。根据节点的地理位置，推销员很可能会多次穿越一个节点。

谁能指出我现有的解决这个问题的方法？最好在 MiniZinc 中（我最近完成了 coursera 课程），但也可以解释 python 解决方案。

标签： mathematical-optimizationminizinc

Answer 1

AMPL 中的 TSP

这是我使用的版本，它是用 AMPL（另一种数学语言）编写的，您可以轻松地将其转换为 minizinc，并添加附加约束