liveBook · Manning

2-opt

As explained in Applied Reinforcement Learning

2-opt is a routing improvement heuristic that replaces two route edges by reconnecting the resulting segments in the opposite order.

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

How Applied Reinforcement Learning covers it

How deep it goes
Explains edge reconnection and segment reversal, then shows repeated route-level improvement logic in code.
Examples
Uses a four-customer route and a depot route with three customers to illustrate reversing a segment.
What you can do after
Apply 2-opt to test route segment reversals and retain changes that reduce total distance.
How it connects
Connects local search with the traveling salesman problem, vehicle routing, and Monte Carlo tree 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.