search

N-Wouda / Euro-NeurIPS-2022

OptiML's contribution to the EURO meets NeurIPS 2022 vehicle routing competition.
Other
16 stars 2 forks source link

Do not require at least two iterations in LS #153

Closed N-Wouda closed 2 years ago

N-Wouda commented 2 years ago

Currently, LocalSearch::search requires at least two iterations. This ensures we also test against empty routes in the second iteration. However, this is only useful in very very rare cases. As such, we are better off just stopping the first moment there's no improvement.

N-Wouda commented 2 years ago

I did one 30s run to collect some data on this. In that 30s I collected 13,081 calls to LocalSearch::search. Of these, 1,014 did not find an improving move in the first iteration. Only five of these then went on to find an improving move in the second iteration, where the empty routes are tested. So 1K out of 13K iterations were wasted.

I ran a benchmark with static to be sure. This PR finds a slightly better average cost (164222), and runs around ~2K more iterations than current baseline.