Feature: Moveable depots #6328 #7051
Gave this 5 minutes of testing, initial impressions are that all worked as expected. Vehicle orders are preserved for up to 1 month, then invalidated if the depot isn't rebuilt by then. The search radius for 'preserve depot' seems to be about 8 tiles or so. In use, it's pretty neat.
FWIW, adf88 considered there was more to do on the original patch #6328 (comment)
However it might be useful as is.
I rebased this branch and updated it to use Kdtree here: https://github.com/nielsmh/OpenTTD/tree/movable-depots
Update: Got an ok on IRC.