我正在尝试将 80 人分成两部分。每个小组都必须前往一个地点。我正在尝试将团队分开，以便人们尽可能少地旅行。我对最少的总旅行时间感兴趣，但我也希望它是平衡的，这样我们就不会有少数人旅行很远，即使这意味着其他人的距离会更短。
我的数据看起来像这样:
-------------------------------------------------------------
| Person | Distance 1 | Distance 2 |
|---------------------|------------------|------------------|
| Person 1 | 0:56:52 | 1:23:50 |
|---------------------|------------------|------------------|
| Person 2 | 0:42:55 | 0:22:45 |
|---------------------|------------------|------------------|
| Person 3 | 1:32:35 | 2:23:02 |
-------------------------------------------------------------
我想添加另一列，其中包含“A”或“B”，具体取决于他们应该被放置在哪个组中。需要将人员平均分配到两组中，以便最小化正方形旅行时间。我知道某种数学优化可能是可行的方法，我只是不确定如何去做。我正在使用 python( Pandas )。
最佳答案
您可以像这样对数学问题建模。
http://mathb.in/31885?key=216f0d8271c8a65ecbce2faff12735042a4b7684
如果旅行者 i 被分配到第 1 组，则 x_i 为 1；如果分配给第 2 组，则 x_i 为 0。旅行者 i 与第 1 组的距离为 d，对于第 2 组的距离为 d'
然后你可以使用像 gurobi/pulp 这样的整数求解器在 python 中进行计算。
还有其他可能的表述，具体取决于您如何定义“平衡”。我猜总旅行时间的平方会给你想要的那种 split 。你可以解决这个问题，看看你是否喜欢你得到的解决方案。但是您可能还有其他平衡的公式。一个例子可能是，“一个旅行者应该旅行的最大值小于某个‘D_high’。在这种情况下，您将添加一个约束，例如 x_i d_i + (1-x_i)d'_i<= D_high
对于大多数现代求解器来说，这是一个相对较小的问题，您应该会在几分钟内得到答案。
编辑:刚刚意识到 pulp/gurobi 是线性求解器。如果您使用正方形作为非线性整数的目标，您将无法再使用 gurobi/pulp。您有两个选择:
坚持非线性公式并使用 cvxpy(开源凸优化，据我所知也支持整数变量)
采用线性公式，您的目标只是距离总和，而不是平方和。并施加一个线性约束，就像我之前提到的 x_i d_i + (1-x_i)d'_i<= D_high，对某种公平性施加限制
关于python - 根据可能的最低行进距离将一组分成两部分，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54961789/