如何找到最佳的团队阵容（游泳）

Question

我目前有一个相当简单的算法，尝试在给定一些限制的情况下构建最佳的团队阵容：

1. 需要游泳运动员来填补的赛事清单有限

• 活动一：50免费
• 活动2：100免费
• ...

2. 在每个项目中，一支队伍最多可以派出 N (

   MaxSwimmersPerTeam

   ) 名游泳运动员。
3. 单个游泳运动员可以参加多个项目，但受到M（

   MaxEntriesPerSwimmer

   ）的限制。
4. 我有一份游泳运动员参加的每项赛事的最佳时间清单。 （注：并不是每个游泳运动员都会游过所有可能的项目，它是一个大小接近 M 的子集）。

team_1_best_times = [
    {"time_id": 1, "swimmer_id": 1, "event_id": 1, "time": 22.00, "rating": 900.00},
    {"time_id": 2, "swimmer_id": 1, "event_id": 2, "time": 44.00, "rating": 800.00},
    {"time_id": 3, "swimmer_id": 2, "event_id": 1, "time": 22.10, "rating": 890.00},
    {"time_id": 4, "swimmer_id": 2, "event_id": 2, "time": 46.00, "rating": 750.00},
]

rating

键（越高越好）使我能够比较不同事件的时间。

最佳阵容将是在所有选定时间中平均评分最高且满足

N

和

M

的阵容

我当前的方法是迭代按

rating

排序的所有时间并填充队列，直到

N

和

M

满足。 例如，给定

N=1

和

M=1

我的算法将：

1. 将评分为 900 的

   Time1

   （Swimmer1） 放入

   Event1

2. 跳过

   Time3

   (Event1-Swimmer2)，评级为

   890

   - 因为我们已经在

   1

   中拥有 Event1 = N 其他游泳者

   (Swimmer1)

   ，因此已达到

   MaxSwimmersPerTeam

   。
3. 跳过

   Time2

   (Event2-Swimmer1)，评级为

   800

   - 因为

   Swimmer1

   已被放入

   1

   = M 其他事件 (Event1)，因此 (

   MaxEntriesPerSwimmer

   ) 已被放入达到了。
4. 将具有

   Time4

   评级的 750

   (Swimmer2)

   放入

   Event2

   。

现在该队伍阵容Event1-Swimmer1 (

900

) 和 Event2-Swimmer2 (

750

) 的平均评分为：

(900+750)/2 = 825

。

这是最简单的例子，显示了我的方法的不足之处。聪明的教练可以做的就是将

Swimmer1

放入

Event2

(

800

) 并将

Swimmer2

放入

Event1

(

890

) 达到更高的平均评分：

(890+800)/2 = 845

。

我尝试稍微研究一下这个问题，找到了像

python-constraint 

、

gekko

、

pyomo

这样的库，但我仍然不知道如何使用他们的工具来解释问题。

Answer 1

游泳者分配与日程优化或集合覆盖算法有关。启发式方法通常可以通过简单的排序和选择方法接近最优解。优化方法通常速度较慢，但可以找到更优化的解决方案。下面是一个简单的混合整数线性规划 (MINLP)，它解决了

gekko

中游泳者分配问题的简化版本。

from gekko import GEKKO

# Initialize the model
model = GEKKO(remote=False)

# Example mock data (replace with actual data)
swimmers = ['Swimmer1', 'Swimmer2', 'Swimmer3', 'Swimmer4', 'Swimmer5']
events = ['100Y Free', '200Y IM', '200Y Free']
# for each swimmer-event combination
rating = {('Swimmer1', '100Y Free'): 800,
         ('Swimmer1', '200Y IM'):    805,
         ('Swimmer1', '200Y Free'):  750,
         ('Swimmer2', '100Y Free'):  600,
         ('Swimmer2', '200Y IM'):    650,
         ('Swimmer2', '200Y Free'):  620,
         ('Swimmer3', '100Y Free'):  815,
         ('Swimmer3', '200Y IM'):    675,
         ('Swimmer3', '200Y Free'):  300,
         ('Swimmer4', '100Y Free'):  705,
         ('Swimmer4', '200Y IM'):    820,
         ('Swimmer4', '200Y Free'):  802,
         ('Swimmer5', '100Y Free'):  713,
         ('Swimmer5', '200Y IM'):    715,
         ('Swimmer5', '200Y Free'):  350,
         }

# Variables
assignments = {}
for swimmer in swimmers:
    for event in events:
        assignments[(swimmer, event)] = model.Var(lb=0, ub=1, integer=True)

# Objective Function: Maximize rating for each event
for event in events:
    total_rating = sum([rating[(swimmer,event)]*assignments[(swimmer, event)] for swimmer in swimmers])
    model.Maximize(total_rating)

# Constraint: min 1 event, max 3 events per swimmer
for swimmer in swimmers:
    model.Equation(model.sum([assignments[(swimmer, event)] for event in events]) <= 3)
    model.Equation(model.sum([assignments[(swimmer, event)] for event in events]) >= 1)

# Constraint: 3 swimmers per individual event
for event in events:
    model.Equation(model.sum([assignments[(swimmer, event)] for swimmer in swimmers]) == 3)

# Constraint 4 for each relay
# Add constraints for relay events

# Solve the model
model.options.SOLVER = 1
model.solve(disp=True)

# Output the assignments
for swimmer in swimmers:
    for event in events:
        if assignments[(swimmer, event)].value[0] >= 0.1:
            print(f"{swimmer} participates in {event}")

解决办法是：

Swimmer1 participates in 100Y Free
Swimmer1 participates in 200Y IM
Swimmer1 participates in 200Y Free
Swimmer2 participates in 200Y Free
Swimmer3 participates in 100Y Free
Swimmer4 participates in 200Y IM
Swimmer4 participates in 200Y Free
Swimmer5 participates in 100Y Free
Swimmer5 participates in 200Y IM

我建议首先考虑启发式方法，将其作为更灵活/可配置的解决方案。与更优化的解决方案相比，启发式方法需要更少的计算资源来获得快速解决方案。如果您确实想使用 MILP，启发式方法是一种用良好的初始猜测来初始化求解器的方法。