agents与访问目标距离最小的算法

Question

我正在用Python实现一个模型。作为这个模型的一部分，我有一组需要访问一组目标(例如地方)的代理(例如人类)。每个代理都有自己的初始位置(即起点)，我可以计算每个代理到每个目标的距离。

在这一点上，我需要的是为每个代理分配第一个任务，其方式是代理从其起始位置到其第一个工作的所有旅行距离之和最小。

我考虑了贪婪算法，但我找到了一些例子，证明了分配顺序可以导致非最优解。我还研究了TSP中最近的邻居算法，但我只能找到一个代理(或销售员)而不是多个代理。

请有人向我指出任何(非详尽无遗的搜索)算法/方法可用于此目的吗？谢谢

Answer 1

如果代理数=目标数，我们将得到一个标准的分配问题。可以通过不同的方式解决这一问题：

• 是线性规划问题。从技术上讲是一个MIP，但是变量是自动整数值的，所以LP求解器就足够了。
• 作为一个网络问题
• 或者使用专门的算法。

。

如果，比如说，位置的数量>代理的数量，我们仍然可以使用LP/MIP：

 min sum((i,j), d(i,j)*x(i,j))
 sum(j, x(i,j)) = 1  for all agents i  (each agent should be assigned to exactly one location)
 sum(i, x(i,j)) <= 1  for all locations j (each location should be assigned to at most one agent)
 x(i,j) in {0,1} 

对于网络方法，我们需要添加一些虚拟节点。

所有这些方法都相当快(这是一个简单的模型)。给你一个提示:我解决了一个随机的例子，500个代理和1000个位置作为一个LP，它花了0.3秒。