Local search improves a routing solution by testing nearby alternatives. In 2-opt, two route edges are reconnected by reversing the segment between them; keep the change when it shortens the route. This refinement runs after each Monte Carlo tree search simulation and again on the final best solution. section 7.4
Reversing a route segment
For Depot → C1 → C2 → C3 → Depot, reversing C2 and C3 gives Depot → C1 → C3 → C2 → Depot, which can reduce distance by removing a crossing. 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
See the 2-opt implementation that tests reversed route segments. section 7.4



