时间戳

首页 > 解决方案 > 根据可能的最短行驶距离将一组分成两部分

python - 根据可能的最短行驶距离将一组分成两部分

问题描述

我试图将一组 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（熊猫）。

标签： pythonpandasmathmathematical-optimization

解决方案

您可以像这样对数学问题进行建模。

http://mathb.in/31885?key=216f0d8271c8a65ecbce2faff12735042a4b7684

其中，如果旅行者 i 被分配到第 1 组，则 x_i 为 1；如果被分配到第 2 组，则 x_i 为 0。第 1 组的旅行者 i 的距离为 d，第 2 组的距离为 d'

然后你可以使用像 gurobi/pulp 这样的整数求解器在 python 中进行计算。

根据您如何定义“平衡”，还有其他可能的公式。我猜总旅行时间的平方会给你你想要的那种分裂。你可以解决这个问题，看看你是否喜欢你得到的解决方案。但是您可能还有其他平衡的配方。一个例子可能是，“一个旅行者应该旅行的最大值小于某个 'D_high'。在这种情况下，您将添加一个约束，例如 x_i d_i + (1-x_i)d'_i<= D_high

对于大多数现代求解器来说，这是一个相对较小的问题，您应该在几分钟内得到答案。

编辑：刚刚意识到纸浆/古罗比是线性求解器。如果您使用平方作为非线性整数的目标，则不能再使用 gurobi/pulp。你有两个选择：

  1. 坚持使用非线性公式并使用 cvxpy （据我所知，开源凸优化，也支持整数变量）

  2. 寻求线性公式，其中您的目标只是距离的总和而不是平方和。并像我之前提到的那样施加线性约束 x_i d_i + (1-x_i)d'_i<= D_high，以对某种公平性施加限制

推荐阅读