liveBook · Manning

Local search

As explained in Applied Reinforcement Learning

Local search is an optimization technique that iteratively improves a candidate solution by examining nearby solutions.

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

How Applied Reinforcement Learning covers it

How deep it goes
Describes 2-opt segment reversal and repeated distance comparisons, without detailing broader local-search variants.
Examples
Demonstrates reversing C2 and C3 in a depot route to remove a crossing and potentially reduce distance.
What you can do after
Apply 2-opt to refine vehicle routes by retaining segment reversals that reduce distance.
How it connects
Combines with Monte Carlo tree search and applies to the traveling salesman and vehicle routing problems.

Also explained in

Compare how 4 books explain local search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.