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

El 3-opt es una técnica heurística avanzada que extiende el método 2-opt para optimizar rutas en el Problema del Viajante de Comercio (TSP). Este enfoque mejora una ruta existente al considerar múltiples formas de reordenar tres segmentos de la ruta, ofreciendo mayor flexibilidad y capacidad para explorar soluciones mejores que con el 2-opt, aunque tampoco garantiza encontrar el óptimo global.


*Ejemplo visual de funcionamiento:

Imagina una ruta inicial que conecta las ciudades en el orden A -> B -> C -> D -> E -> F -> A. El algoritmo 3-opt selecciona tres aristas en la ruta, por ejemplo, A-B, C-D, y E-F, y evalúa diferentes maneras de reconectar estos segmentos. Entre las posibles reordenaciones, el 3-opt podría, por ejemplo, intercambiar e invertir segmentos para formar la ruta A -> C -> B -> E -> D -> F -> A. Si esta nueva ruta resulta ser más corta que la original, se adopta como la nueva ruta y el proceso continúa iterativamente para seguir mejorando la solución.



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));
        }

        TSP3Opt tsp3 = new TSP3Opt(distances);
        List<Integer> bestRoute = tsp3.findBestRoute(1000);
        double bestDistance = tsp3.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 (TSP3Opt.java):

package tsp_optimization;

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

public class TSP3Opt {

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

    public TSP3Opt(double[][] distances) {
        this.distances = distances;
        this.numCities = distances.length;
    }

    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 - 2; i++) {
                for (int j = i + 1; j < numCities - 1; j++) {
                    for (int k = j + 1; k < numCities; k++) {
                        List<Integer> newRoute = threeOptSwap(route, i, j, k);
                        if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
                            route = newRoute;
                            improved = true;
                        }
                    }
                }
            }
        }

        return route;
    }

    private List<Integer> threeOptSwap(List<Integer> route, int i, int j, int k) {
        List<Integer> newRoute = new ArrayList<>();

        // Caso 1: No invertir ninguna subruta
        newRoute.addAll(route.subList(0, i));
        newRoute.addAll(route.subList(i, j));
        newRoute.addAll(route.subList(j, k));
        newRoute.addAll(route.subList(k, numCities));
        if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
            return newRoute;
        }

        // Caso 2: Invertir subruta entre i y j
        newRoute.clear();
        List<Integer> reversed1 = new ArrayList<>(route.subList(i, j));
        Collections.reverse(reversed1);
        newRoute.addAll(route.subList(0, i));
        newRoute.addAll(reversed1);
        newRoute.addAll(route.subList(j, k));
        newRoute.addAll(route.subList(k, numCities));
        if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
            return newRoute;
        }

        // Caso 3: Invertir subruta entre j y k
        newRoute.clear();
        List<Integer> reversed2 = new ArrayList<>(route.subList(j, k));
        Collections.reverse(reversed2);
        newRoute.addAll(route.subList(0, i));
        newRoute.addAll(route.subList(i, j));
        newRoute.addAll(reversed2);
        newRoute.addAll(route.subList(k, numCities));
        if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
            return newRoute;
        }

        // Caso 4: Invertir ambas subrutas
        newRoute.clear();
        List<Integer> reversed3 = new ArrayList<>(route.subList(i, j));
        List<Integer> reversed4 = new ArrayList<>(route.subList(j, k));
        Collections.reverse(reversed3);
        Collections.reverse(reversed4);
        newRoute.addAll(route.subList(0, i));
        newRoute.addAll(reversed3);
        newRoute.addAll(reversed4);
        newRoute.addAll(route.subList(k, numCities));
        if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
            return newRoute;
        }

        // Retornar la ruta original si ninguna de las permutaciones es mejor
        return route;
    }

    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:
I L A B O C M H J K G N E D F I
> La distancia total recorrida es: 27834.0
BUILD SUCCESSFUL (total time: 0 seconds)