Why did you jump straight to MILP for ordering the lines of segments? It seems like it would be more obvious to first try ordering the routes by id for each segment. That would guarantee that routes are always ordered the same way relatively to each other and would eliminate the problem in the before/after image with much less effort.