0
$\begingroup$

Can I improve on a Monte-Carlo search for the problem, described?

enter image description here

So I have a graph/network consisting of segments a1, a2, ..., b1, b2, ..., and c1, c2, ...

For all the underlying segments there is some weighting e.g. a1 = 2, b3 = 0, c3 = 4

In addition I have a matrix of the distances from each segment to all other segments in the network e.g.

|from/to | a1  | a2  | a3  | b1  | b2  | b3  | c1  | c2  | c3  |
|--------|-----|-----|-----|-----|-----|-----|-----|-----|-----|
|   a1   |  0  | 4   | 6   | 84  | 82  | 80  | 150 | 148 | 146 |
|   a2   | ... | 0   | ... | ... | ... | ... | ... | ... | ... |
|   a3   | ... | ... | 0   | ... | ... | ... | ... | ... | ... |
|   b1   | ... | ... | ... | 0   | ... | ... | ... | ... | ... |
|   b2   | ... | ... | ... | ... | 0   | ... | ... | ... | ... |
|   b3   | ... | ... | ... | ... | ... | 0   | ... | ... | ... |
|   c1   | ... | ... | ... | ... | ... | ... | 0   | ... | ... |
|   c2   | ... | ... | ... | ... | ... | ... | ... | 0   | ... |
|   c3   | ... | ... | ... | ... | ... | ... | ... | ... | 0   |
| ...    | ... | ... | ... | ... | ... | ... | ... | ... | ... |

I want to place n agents (in the image n = 3) such as to cover as much of the segments by weighting as possible, within a distance of 50. And be able to optimise for any parameter combination e.g. any n and any distance.

So far I have tried:

  • a greedy approach: placing an agent where most segments are covered (local optimum), then placing the next agent to cover most segments etc up to n.
  • a monte-carlo approach: selecting n random segments and evaluating, repeating many times and choosing the best solution.

In reality this network, and the number of agents n may be much larger and more complex.

I'm wondering what other approaches might work, better than a monte-carlo?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.