# Multiple agents routing optimisation problem

We are given an array of nodes of the form {{xcoordinate,ycoordinate}, weight, "name"}. This represents nodes on a 2D euclidean coordinate system. Further, we are given a number n which is the number of agents.

We wish to optimise the agent routes and the work distribution between them in the following manner:

For each agent, calculate the area it covers. The area it covers is the area of the smallest possible convex polygon that contains (on its inside, the edges or the corners) all the points that are assigned to that agent. We furthermore calculate the sum of the weights of the nodes that the agent is assigned to.

We take the maximum and the minimum of both the area and the sum of weights, per individual agents. We multiply (areamax - areamin) * (weightsummax - weightsummin). We wish to find the minimal product, for an arbitrary configuration of nodes. Per definition, if the agent is assigned either one or two nodes, the area associated with that is zero (since neither a point, nor a line segment has an area.)

The output of the routine is the following:

1. a printout of how large the biggest and smallest areas are
2. a printout of the difference between the maximal and minimal weight sums
3. a colored map, showing in different (random?) colors the areas of the individual agents, and the particular nodes that are assigned to them
4. a listing of the nodes' names, associated with individual agents, either by numbering or by color coding the list
• This reads rather obviously like homework, so you should show us your work first. – MarcoB Jan 14 at 21:49
• Homework or not, I think the real challenge here is to reduce the problem to several well-optimized Mathematica functions. Otherwise I doubt the solution would be any good from performance or aesthetics viewpoints. – aooiiii Jan 14 at 22:58
• It's not homework. And yes, I was wondering if there are ways for doing it at reasonable speeds in Mathematica. I have coded a solution in FORTRAN (though with very little heuristics,) it spat out a solution for a "10 agents/1000 random coordinates in a square/random weights between 1 and 10" situation in about thirteen minutes. I have left it running for eight more hours afterward, five more solutions (with better score) came, but I think that in such a case, it's difficult to sample the whole solution place in depth. – fischlie Jan 15 at 7:03
• It's very unlikely for a combinatorial search Mathematica program to outperform a compiled binary. This is only possible if you're lucky and Mathematica already has all necessary subroutines built-in, just waiting to be glued together. But who knows? Maybe this is the case! I don't know, though. – aooiiii Jan 15 at 8:28
• It might help to have an explicit example. – Daniel Lichtblau Jan 15 at 16:02