根据可能的最低行进距离将一组分成两部分
Split a group in two based on lowest possible travel distance
我正试图将 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 组，则为 0。第 1 组的旅行者 i 的距离为 d，第 2 组的距离为 d'
然后你可以使用像gurobi/pulp这样的整数求解器来计算python。
还有其他可能的公式，具体取决于您如何定义 "balanced"。我猜总旅行时间的平方会给你想要的那种分裂。你可以解决这个问题，看看你是否喜欢你得到的解决方案。但是您可能还有其他平衡的公式。一个例子可能是，“一个旅行者应该旅行的最大数量少于一些 'D_high'。在这种情况下，您将添加一个约束，例如 x_i d_i + (1-x_i)d'_i<= D_high
对于大多数现代求解器来说，这是一个相对较小的问题，您应该会在几分钟内得到答案。
编辑：刚刚意识到 pulp/gurobi 是线性求解器。如果将平方用作非线性整数的 objective，则不能再使用 gurobi/pulp。您有两个选择：
坚持非线性公式并使用 cvxpy（开源凸优化，据我所知也支持整数变量）
寻求线性公式，其中您的 objective 只是距离之和而不是平方和。并施加一个线性约束，就像我之前提到的 x_i d_i + (1-x_i)d'_i<= D_high，以对某种公平性施加限制
我正试图将 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 组，则为 0。第 1 组的旅行者 i 的距离为 d，第 2 组的距离为 d'
然后你可以使用像gurobi/pulp这样的整数求解器来计算python。
还有其他可能的公式，具体取决于您如何定义 "balanced"。我猜总旅行时间的平方会给你想要的那种分裂。你可以解决这个问题，看看你是否喜欢你得到的解决方案。但是您可能还有其他平衡的公式。一个例子可能是，“一个旅行者应该旅行的最大数量少于一些 'D_high'。在这种情况下，您将添加一个约束，例如 x_i d_i + (1-x_i)d'_i<= D_high
对于大多数现代求解器来说，这是一个相对较小的问题，您应该会在几分钟内得到答案。
编辑：刚刚意识到 pulp/gurobi 是线性求解器。如果将平方用作非线性整数的 objective，则不能再使用 gurobi/pulp。您有两个选择：
坚持非线性公式并使用 cvxpy（开源凸优化，据我所知也支持整数变量）
寻求线性公式，其中您的 objective 只是距离之和而不是平方和。并施加一个线性约束，就像我之前提到的 x_i d_i + (1-x_i)d'_i<= D_high，以对某种公平性施加限制