The AI just moves it to the "center-most" large or huge city it can find I know it does take size in count it won't move it to a town.

For instance when I took out Seleukeia it moved to Alexandreia even if the most logical choice would've been Damaskos (the AS still had territories in the far east).