You could also just use the last place they lived in before prison.

That makes sense along the lines of their second proposal, but doesn't address the concerns of the first. Part of democracy means voting for the folks who govern you, but a prisoner might be left unable to vote in an election for the local state or municipal governments.

You could let them choose between that and where they're locked up. I think that's generally how it's worked for college students, although some states are now trying to keep them from voting in their college towns.