7

我有一个复杂的问题，我想知道是否存在或适用现有且易于理解的解决方案模型，例如旅行推销员问题。

输入：

  • 包含 N 个时间事件的日历，由开始和结束时间以及地点定义。
  • 每个会议场所的容量（可同时容纳的最大人数）
  • 一组对(Ai,Aj)，表示服务员Ai希望与服务员会面Aj并Aj接受该邀请。

输出：

  • 对于每个助理A，他将参加的所有活动的时间表。主要标准是每个服务员应尽可能多地遇到接受他邀请的服务员，满足空间限制。

到目前为止，我们考虑使用回溯求解（尝试所有可能的解决方案），并使用线性规划（即定义模型并使用单纯形算法求解）

更新：如果在某些情况下Ai已经见过面Aj，他们就不需要再见面了（他们已经见过面了）。

4

3 回答 3

3

Your problem is as hard as minimum maximal matching problem in interval graphs, w.l.o.g Assume capacity of rooms is 2 means they can handle only one meeting in time. You can model your problem with Interval graphs, each interval (for each people) is one node. Also edges are if A_i & A_j has common time and also they want to see each other, set weight of edges to the amount of time they should see each other, . If you find the minimum maximal matching in this graph, you can find the solution for your restricted case. But notice that this graph is n-partite and also each part is interval graph.

P.S: note that if the amount of time that people should be with each other is fixed this will be more easier than weighted one.

于 2012-04-30T09:42:00.250 回答
2

如果您可以访问一个好的 MIP 求解器（cplex/gurobi 通过学术倡议，但 coin OR 和 LP_solve 是开源的，而且也不错），我肯定会尝试 simplex。我看了看将您的问题表述为一个混合整数程序，我的感觉是它会有相当强的松弛，因此分支和切割以及价格对您来说会有很长的路要走。如今，这些求解器提供了非常可扩展的解决方案，尤其是商业解决方案。优点是它们还提供了一个上限，因此您可以了解解决方案的质量，而启发式方法并非如此。

公式：

将 z(i,j)（二进制）定义为一个变量，表示 i 和 j 在 {1,2,...,N} 中的至少一个事件 n 中在一起。定义 z(i,j,n)（二进制）以指示它们在事件 n 中在一起。定义 z(i,n) 表示 i 参加 n。Z(i,j) 和 z(i,j,m) 仅在 i 和 j 应该相遇时才存在。

对于每个 t，M^t 是同时举行的时间事件的子集。因此，如果事件 1 是从 9 到 11，事件 2 是从 10 到 12，事件 3 是从 11 到 13，则 M^1 = {事件 1，事件 2) 和 M^2 = {事件 2，事件 3} . 即没有人可以同时参加 1 和 2，或 2 和 3，但 1 和 3 很好。

Max sum Z(i,j)                      

z(i,j)<= sum_m z(i,j,m)   
(every i,j)(i and j can meet if they are in the same location m at least once)

z(i,j,m)<= z(i,m)   (for every i,j,m) 
(if i and j attend m, then i attends m)

z(i,j,m)<= z(j,m)     (for every i,j,m) 
(if i and j attend m, then j attends m)

sum_i z(i,m) <= C(m)   (for every m) 
(only C(m) persons can visit event m)

sum_(m in M^t) z(i,m) <= 1  (for every t and i)  
(if m and m' are both overlapping time t, then no person can visit them both. )
于 2012-05-15T21:05:39.537 回答
1

正如@SaeedAmiri 所指出的，这看起来是一个复杂的问题。

我的猜测是，您正在考虑的回溯和线性编程选项会随着助手数量的增加（可能是数十个助手的数量级）而爆炸式增长。

如果不需要最优性，也许您应该考虑一种（元）启发式方法，或者使用约束编程来构建初始模型并查看其扩展方式。

为了给你一个更准确的答案，你为什么需要解决这个问题？参加者的典型人数是多少？房间的数量？

于 2012-04-30T10:54:01.397 回答