CODEWITHSUNDEEP
optimizationnearest-neighbormulti-agent
Alijy
Alijy

Reputation: 165

Algorithm for Minimising Sum of Distance of agents to visiting targets

I'm working on implementing a model in Python. As part of this model, I have a set of agents (e.g. humans) that need to visit a set of targets (e.g. places). Each agent has its own initial location (i.e. starting point) and I can calculate the distance from each agent to each target.

What I need at this point is to allocate a first job to each agent in a way that the sum of all travel distances for agents from their starting location to their first job is minimum.

I considered greedy algorithm, but I found examples that proves order of allocation can lead to non-optimal solutions. I also looked into nearest neighbour algorithm in TSP, but all I could find was for one agent (or salesman) not multiple.

Could someone point me to any (non-exhaustive search) algorithm/approach that could be used for this purpose please? Thanks

Upvotes: 0

Views: 164

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16772

If the number of agents = number of targets, we end up with a standard assignment problem. This can be solved in different ways:

  • as an LP (linear programming problem). Technically a MIP but variables are automatically integer-valued, so an LP solver suffices.
  • as a network problem
  • or using specialized algorithms.

If, say, the number of locations > number of agents, we still can use an LP/MIP:

 min sum((i,j), d(i,j)*x(i,j))
 sum(j, x(i,j)) = 1  for all agents i  (each agent should be assigned to exactly one location)
 sum(i, x(i,j)) <= 1  for all locations j (each location should be assigned to at most one agent)
 x(i,j) in {0,1}

For the network approach, we would need to add some dummy nodes.

All these methods are quite fast (this is an easy model). To give you an indication: I solved a random example with 500 agents and 1000 locations as an LP and it took 0.3 seconds.

Upvotes: 1

Related Questions