parallel_cross_exchange.py

import numpy as np
from numba import njit, parallel

@njit(parallel=True)
def cross_exchange(route1, route2, dist):
    best_savings = -np.inf
    for offset11 in prange(len(route1) - 3):
        i1, i2 = route1[offset11], route1[offset11 + 1]
        dii = dist[i1, i2]
        
        for offset21 in range(len(route2) - 3):
            j1, j2 = route2[offset21], route2[offset21 + 1]
            djj = dist[j1, j2]
            
            dijji = dist[i1, j2] + dist[j1, i2]
            
            for offset12 in range(offset11 + 2, len(route1) - 1):
                k1, k2 = route1[offset12], route1[offset12 + 1]
                dkk = dist[k1, k2]
                  
                for offset22 in range(offset21 + 2, len(route2) - 1):
                    l1, l2 = route2[offset22], route2[offset22 + 1]
                    dll = dist[l1, l2]
                    
                    dkllk = dist[k1, l2] + dist[l1, k2]
                    
                    best_savings = max(best_savings, (
                        (dijji + dkllk) -
                        (dii + djj + dkk + dll)
                    ))
    
    return best_savings

n      = 1000
pts    = np.random.uniform(0, 1, (n, 2))
dist   = squareform(pdist(pts))

route1 = np.random.permutation(np.arange(n // 2))
route2 = np.random.permutation(np.arange(n // 2, n))

t = time()
_ = cross_exchange(route1, route2, dist)
time() - t