多起点最短路径算法
Algorithm for shortest paths with multiple origins
我有多个起点（蓝色圆圈）和多个目的地（绿色方块），如下图所示：
- 我知道每个起点和终点之间的距离。
- 每个起点只能有一定数量的目的地。
我想找到最有效的起点-终点组合，使总距离最小。
唯一想到的是某种背包问题的变体，但我真的不知道如何进行，因为这里的项目没有常量 "weight"（距离）。
假设您有一个距离矩阵 W，其中 W[i][j] 是起点 i 和目的地 j 之间的距离，您可以将问题表示为二进制整数如果目标 j 分配给起点 i，则 b[i][j] 为 1 的程序，否则为 0。如果我们填满容量
min sum_{i,j} w[i][j]*b[i][j]
subject to
sum_j b[i][j]=capacity[i] for all i (1)
sum_i b[i][j]<=1 for all j(2)
约束 (1) 表示每个起点都已满。约束 (2) 表示没有目的地被分配给超过 1 个起点。
如果有足够的容量容纳所有目的地，则解决
min sum_{i,j} w[i][j]*b[i][j]
subject to
sum_j b[i][j]<=capacity[i] for all i
sum_i b[i][j]=1 for all j
我认为这第二个公式是 Multiple knapsack problem 的一个版本。
所以你可以做的是检查第二个公式是否有可行的解决方案，如果没有，
解决第一个。您可以使用 MIPS 求解器。
我有多个起点（蓝色圆圈）和多个目的地（绿色方块），如下图所示：
- 我知道每个起点和终点之间的距离。
- 每个起点只能有一定数量的目的地。
我想找到最有效的起点-终点组合，使总距离最小。
唯一想到的是某种背包问题的变体，但我真的不知道如何进行，因为这里的项目没有常量 "weight"（距离）。
假设您有一个距离矩阵 W，其中 W[i][j] 是起点 i 和目的地 j 之间的距离，您可以将问题表示为二进制整数如果目标 j 分配给起点 i，则 b[i][j] 为 1 的程序，否则为 0。如果我们填满容量
min sum_{i,j} w[i][j]*b[i][j]
subject to
sum_j b[i][j]=capacity[i] for all i (1)
sum_i b[i][j]<=1 for all j(2)
约束 (1) 表示每个起点都已满。约束 (2) 表示没有目的地被分配给超过 1 个起点。 如果有足够的容量容纳所有目的地，则解决
min sum_{i,j} w[i][j]*b[i][j]
subject to
sum_j b[i][j]<=capacity[i] for all i
sum_i b[i][j]=1 for all j
我认为这第二个公式是 Multiple knapsack problem 的一个版本。
所以你可以做的是检查第二个公式是否有可行的解决方案，如果没有， 解决第一个。您可以使用 MIPS 求解器。