How to avoid Thread.sleep in Unit tests?

If you are testing [Unit Test] for the method methodToBeTested, you should simply mock routingservice.
You shouldn't be testing any methods that methodToBeTested calls.

However, it sounds like you want to test the RoutingService (you said "The problem is that RoutingService changes the state of objectToRoute and this is exactly what I want to check").

To test RoutingService methods, you should write separate unit tests for those methods.

I suggest awaitility for synchronizing asynchronous tests. For example, assume you have an result object that get set after some thread operations and you want to test it. You write statement like this:

 await()
.atMost(100, TimeUnit.SECONDS)
.untilAsserted(() -> assertNotNull(resultObject.getResult()));

It waits maximum 100 seconds, or until the assertion is satisfied. For instance, if getResult() returns something that is not null in between 0-100 seconds, the execution continues unlike Thread.sleep which holds the execution for given time no matter result is there or not.