I notice you are using FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC
. If this name does what it suggests, then it's probably a greedy strategy that chooses between distance 1
, 1
and so on.
The clue is that you're using a strategy that does not guarantee optimal solutions. The structure also suggests that a certain random seed is used; there is an iteration above five until the largest node number is reached, an iteration under five until the lowest number is reached and in the end, five is left.