Problema del Viajante de Comercio TSP (V.3). Método Optimization N-Opt.

El algoritmo TSP Optimization (N-opt) es una técnica heurística generalizada utilizada para mejorar la solución del Problema del Viajante de Comercio (TSP). Este enfoque permite seleccionar y modificar un número arbitrario de aristas (N) en la ruta actual, donde N representa el número de segmentos que se consideran para ser reordenados. Al igual que con las variantes más simples, como el 2-opt o el 3-opt, el N-opt busca encontrar una ruta más corta, pero con una mayor flexibilidad y un espacio de búsqueda más amplio, lo que potencialmente conduce a mejores soluciones. Sin embargo, al aumentar N, también se incrementa la complejidad computacional, y como en las otras variantes, no garantiza encontrar el óptimo global.



Código Java 1 (TSP_Optimization.java):

package tsp_optimization;

import java.util.ArrayList;
import java.util.List;

public class TSP_Optimization {

    public static void main(String[] args) {

        double[][] distances = {
            {0, 1190, 1255, 7549, 7009, 4245, 7539, 314, 993, 5236, 3676, 2508, 8987, 5886, 1835},
            {1190, 0, 7723, 3900, 7082, 8972, 8360, 5127, 6002, 8613, 5598, 7216, 7303, 1013, 2294},
            {1255, 7723, 0, 7843, 6636, 9905, 3190, 5337, 8012, 6704, 9300, 6966, 328, 2112, 1028},
            {7549, 3900, 7843, 0, 2657, 5301, 9294, 1987, 8633, 6415, 2611, 8728, 3895, 7705, 7429},
            {7009, 7082, 6636, 2657, 0, 8304, 2569, 9744, 7886, 9015, 8502, 4337, 5159, 32, 8341},
            {4245, 8972, 9905, 5301, 8304, 0, 9945, 4113, 3297, 8881, 9562, 9211, 4182, 7529, 4457},
            {7539, 8360, 3190, 9294, 2569, 9945, 0, 1714, 2308, 7467, 1861, 7895, 7867, 240, 2956},
            {314, 5127, 5337, 1987, 9744, 4113, 1714, 0, 7642, 2461, 9780, 9201, 640, 9583, 8358},
            {993, 6002, 8012, 8633, 7886, 3297, 2308, 7642, 0, 8584, 6593, 3903, 3533, 5105, 5461},
            {5236, 8613, 6704, 6415, 9015, 8881, 7467, 2461, 8584, 0, 94, 9758, 2375, 5656, 3203},
            {3676, 5598, 9300, 2611, 8502, 9562, 1861, 9780, 6593, 94, 0, 6284, 3894, 948, 633},
            {2508, 7216, 6966, 8728, 4337, 9211, 7895, 9201, 3903, 9758, 6284, 0, 4675, 4214, 9524},
            {8987, 7303, 328, 3895, 5159, 4182, 7867, 640, 3533, 2375, 3894, 4675, 0, 7004, 3146},
            {5886, 1013, 2112, 7705, 32, 7529, 240, 9583, 5105, 5656, 948, 4214, 7004, 0, 1020},
            {1835, 2294, 1028, 7429, 8341, 4457, 2956, 8358, 5461, 3203, 633, 9524, 3146, 1020, 0}
        };

        int n = distances.length;
        List<String> cityNames = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char letter = (char) ('A' + i);
            cityNames.add(String.valueOf(letter));
        }

        int N = 4; // Puedes cambiar el valor de N según lo necesites
        TSPNOpt tspN = new TSPNOpt(distances, N);
        bestRoute = tspN.findBestRoute(100);
        bestDistance = tspN.calculateTotalDistance(bestRoute);

        System.out.println("Matriz de distancias :");
        for (double[] distance : distances) {
            for (int j = 0; j < distance.length; j++) {
                System.out.printf("%7d", Math.round(distance[j]));
            }
            System.out.println();
        }
        System.out.println();

        System.out.println("> Mejor ruta encontrada:");
        bestRoute.forEach(city -> {
            System.out.print(cityNames.get(city) + " ");
        });
        System.out.println(cityNames.get(bestRoute.get(0)));
        System.out.println("> La distancia total recorrida es: " + bestDistance);

    }

}


Código Java 2 (TSPNOpt.java):

package tsp_optimization;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TSPNOpt {

    private final double[][] distances;
    private final int numCities;
    private final int N;

    public TSPNOpt(double[][] distances, int N) {
        this.distances = distances;
        this.numCities = distances.length;
        this.N = N;
    }

    public List<Integer> findBestRoute(int numRuns) {
        List<Integer> bestRoute = null;
        double bestDistance = Double.MAX_VALUE;

        for (int run = 0; run < numRuns; run++) {
            List<Integer> route = generateRandomRoute();
            route = optimizeRoute(route);

            double distance = calculateTotalDistance(route);
            if (distance < bestDistance) {
                bestDistance = distance;
                bestRoute = new ArrayList<>(route);
            }
        }

        return bestRoute;
    }

    private List<Integer> generateRandomRoute() {
        List<Integer> route = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            route.add(i);
        }
        Collections.shuffle(route);
        return route;
    }

    private List<Integer> optimizeRoute(List<Integer> route) {
        boolean improved = true;
        while (improved) {
            improved = false;
            for (int i = 0; i < numCities - N + 1; i++) {
                for (int j = i + 1; j < numCities - N + 2; j++) {
                    List<Integer> newRoute = nOptSwap(route, i, j);
                    if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
                        route = newRoute;
                        improved = true;
                    }
                }
            }
        }
        return route;
    }

    private List<Integer> nOptSwap(List<Integer> route, int i, int j) {
        List<Integer> newRoute = new ArrayList<>(route.subList(0, i));
        List<Integer> subRoute = new ArrayList<>(route.subList(i, j + 1));
        Collections.reverse(subRoute);
        newRoute.addAll(subRoute);
        newRoute.addAll(route.subList(j + 1, route.size()));
        return newRoute;
    }

    public double calculateTotalDistance(List<Integer> route) {
        double totalDistance = 0;
        for (int i = 0; i < route.size(); i++) {
            totalDistance += distances[route.get(i)][route.get((i + 1) % route.size())];
        }
        return totalDistance;
    }
}


Resultado:

run:
Matriz de distancias:
      0   1190   1255   7549   7009   4245   7539    314    993   5236   3676   2508   8987   5886   1835
   1190      0   7723   3900   7082   8972   8360   5127   6002   8613   5598   7216   7303   1013   2294
   1255   7723      0   7843   6636   9905   3190   5337   8012   6704   9300   6966    328   2112   1028
   7549   3900   7843      0   2657   5301   9294   1987   8633   6415   2611   8728   3895   7705   7429
   7009   7082   6636   2657      0   8304   2569   9744   7886   9015   8502   4337   5159     32   8341
   4245   8972   9905   5301   8304      0   9945   4113   3297   8881   9562   9211   4182   7529   4457
   7539   8360   3190   9294   2569   9945      0   1714   2308   7467   1861   7895   7867    240   2956
    314   5127   5337   1987   9744   4113   1714      0   7642   2461   9780   9201    640   9583   8358
    993   6002   8012   8633   7886   3297   2308   7642      0   8584   6593   3903   3533   5105   5461
   5236   8613   6704   6415   9015   8881   7467   2461   8584      0     94   9758   2375   5656   3203
   3676   5598   9300   2611   8502   9562   1861   9780   6593     94      0   6284   3894    948    633
   2508   7216   6966   8728   4337   9211   7895   9201   3903   9758   6284      0   4675   4214   9524
   8987   7303    328   3895   5159   4182   7867    640   3533   2375   3894   4675      0   7004   3146
   5886   1013   2112   7705     32   7529    240   9583   5105   5656    948   4214   7004      0   1020
   1835   2294   1028   7429   8341   4457   2956   8358   5461   3203    633   9524   3146   1020      0

> Mejor ruta encontrada:
F D E N G K J H M C O B A L I F
> La distancia total recorrida es: 27834.0
BUILD SUCCESSFUL (total time: 0 seconds)