CODEWITHSUNDEEP
algorithmknapsack-problem
tamir
tamir

Reputation: 3297

Algorithm for shortest paths with multiple origins

I have multiple origins (blue circles) and multiple destinations (green squares) as in the image below: enter image description here

I want to find the most efficient combination of origins-destinations so that the total distances is at the minimum.

The only thing that comes to mind is some kind of Knapsack Problem variation, but I don't really know how to proceed because there is no constant "weight" (distance) for the items here.

Upvotes: 0

Views: 169

Answers (1)

Juan Carlos Ramirez
Juan Carlos Ramirez

Reputation: 2129

Assuming you have a matrix W of distances where W[i][j] is the distance between origin i and destination j, you can formulate your problem as a binary integer program where b[i][j] is 1 if destination j is assigned to origin i, and 0 otherwise. If we fill to capacity

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)

Constraint (1) says that every origin is filled to capacity. constraint (2) says that no destination is assigned to more than 1 origin. If there is enough capacity to accomodate all destinations then solve

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

I think this second formulation is a version of the Multiple knapsack problem.

So what you can do is check if this second formulation has a feasible solution, if not, solve the first one. You can use a MIPS solver.

Upvotes: 3

Related Questions