python - 用于将特定规模的志愿者团体与要求特定数量的志愿者的志愿者站点进行最佳匹配的算法？

Question

我有不同规模(从 5 人到 250 人)的志愿者组，需要与请求不同数量的志愿者(从 3 人到 400 人)的志愿者网站配对。我需要将志愿者组与志愿者站点配对，在需要时拆分志愿者组，并在必要时将多个志愿者组与一个志愿者站点配对。但是，我想尽量减少任何 split 。是否有一种算法可以将它们最佳配对？这是否属于具有维基百科页面的已知类型的计算机科学问题会有所帮助？任何建议表示赞赏 !

Answer 1

这个问题可以解释为运输问题的变体。考虑具有源节点(志愿者组，用 i 表示)和目标节点(志愿者站点，用 j 表示)的二分图。假设志愿者总数等于或大于站点的总需求。然后目标是最小化从 i → j 中使用的链接数。

此问题可以表述为混合整数规划模型，并使用现成的 MIP 求解器求解。该模型看起来像:

项目x^up_i,j 表示x_i,j.

让我们生成一些随机数据:

----     18 PARAMETER size  volunteers in group

group1   47,    group2  212,    group3  140,    group4   79,    group5   76,    group6   60,    group7   91
group8  215,    group9   21,    group10 128,    group11 250,    group12 147


----     18 PARAMETER request  needed by site

site1 397,    site2 306,    site3  55,    site4 257,    site5  66


----     18 PARAMETER numvolunteer         =         1466  total volunteers
            PARAMETER numrequest           =         1081  total requests

将这些数据输入我们的模型时，我们得到以下结果:

----     44 VARIABLE y.L  link used

              site1       site2       site3       site4       site5

group2                        1
group3                                                1
group4                                                            1
group5                                    1
group8                        1
group10                                               1
group11           1
group12           1


----     44 VARIABLE x.L  flow

              site1       site2       site3       site4       site5

group2                       91
group3                                              140
group4                                                           66
group5                                   55
group8                      215
group10                                             117
group11         250
group12         147