Finished 2nd, 10988 points.
I used simulated annealing as well, but instead of working directly on arrows, I worked on a set of cycles (starting with an empty set).
For example, let say that I have a set of cycles like this:
For the evaluation I simulate the robots, and when one enters a cycle, it follows it, (while putting arrows if it was not already done by a previous robot).
The way to go through the cycle depends only on the first robot entering it.
So after a simulation I might have something like this:
For the simulated annealing, in order to go from one state to another I add another small cycle to it this set of cycles.
If an edge is present twice, it is removed (so it’s more a ‘xor’ with another cycle, than an addition).
If we add this small cycle to the previous state:
We’ve got this:
Which might give something like that after a simulation:
The small cycles I used were these ones (and the rotations):
Sometimes adding a small cycle like this can split/merge cycles, sometimes it can reverse a part of a cycle, etc.
One other thing is that the cycles are not necessary on free cells only, they can partially be over void cells, or fixed arrows cells, so it can work (kind of) on test cases without big open area too.
The good thing with this approach, is that it creates a “smooth” search space : it can go from one good state to another without going too low with the evaluation function, and for simulated annealing this is often critical, and I think it has some good scores on tests with big open area.
The bad thing is that it requires some hacks to handle the robots before they enter the cycles, or when you want them to do a 180, and because of that it behave badly on some cases (I almost always miss the 354 points solution of the test #13 by more than 150 points, I should have brute-forced this kind of test cases 
).
I score around 8500 which is not great but still better than my 4500ish score in the contest.