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

El algoritmo TSP Optimization (2-opt) es una técnica heurística utilizada para mejorar la solución del Problema del Viajante de Comercio, cuyo objetivo es encontrar la ruta más corta que visita un conjunto de ciudades exactamente una vez y regresa al punto de partida. El 2-opt es una de las maneras más simples y efectivas de optimizar una ruta existente, aunque no garantiza el óptimo global.


*Ejemplo visual de funcionamiento:

Imagina una ruta inicial que conecta las ciudades en el orden A -> B -> C -> D -> E -> A. El algoritmo 2-opt selecciona dos aristas, digamos A-B y D-E, y las intercambia invirtiendo el segmento entre ellas, resultando en la ruta A -> D -> C -> B -> E -> A. Si esta nueva ruta es más corta, se adopta como la nueva ruta y el proceso continúa.



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;
        // Pone nombre a los nodos siguiendo la secuencia del abcedario
        List<String> cityNames = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char letter = (char) ('A' + i);
            cityNames.add(String.valueOf(letter));
        }

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

package tsp_optimization;

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

public class TSP2Opt {

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

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

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