2-opt improves a route by choosing two edges, reconnecting them in another way, and reversing the intervening segment. Keep a change when it reduces distance; repeated trials provide local refinement, not a guarantee of the best possible route. section 7.4
Reversing a route segment
For A→B→C→D, reversing the B→C segment gives A→C→B→D. A depot route visiting C1, C2, and C3 offers another example: reversing C2 and C3 may remove a crossing and shorten the route. section 7.4
Listing 7.24 2-opt local search improvement
def _apply_2opt_improvement(self, state):
improved_state = state.clone()
for vehicle_idx, route in enumerate(improved_state.routes):
if len(route) < 2:
continue #A
improved = True
while improved:
improved = False
for i in range(len(route) - 1):
for j in range(i + 2, len(route)):
current_dist = self._calculate_segment_distance(
➥route, i, j,
➥ vehicle_idx, improved_state) #B
new_route = route[:i+1] +
➥route[i+1:j+1]
➥ [::-1] + route[j+1:] #C
new_dist = self._calculate_segment_distance(
➥new_route, i, j,
➥vehicle_idx, improved_state) #D
if new_dist < current_dist:
improved_state.routes[vehicle_idx] =
➥new_route
route = new_route
improved = True #E
break
if improved:
break
return improved_state
Inspect the Python listing for the route-level 2-opt improvement procedure. section 7.4
