Problema del viajante de Comercio TSP (XIV). Método Programación Lineal Entera (PLE).

El algoritmo formula el TSP como un problema de optimización matemática donde las variables de decisión son enteras (generalmente binarias). Busca minimizar la distancia total del recorrido sujeto a restricciones que aseguran que cada ciudad se visite exactamente una vez y que el tour sea continuo.

Características:

  . Exactitud: Garantiza encontrar la solución óptima global, si existe y si el algoritmo se ejecuta hasta su finalización.
  . Formulación matemática: Utiliza variables binarias para representar las decisiones de viaje entre ciudades.
  . Función objetivo: Minimiza la suma de las distancias entre las ciudades visitadas consecutivamente.
  . Complejidad: Es un problema NP-duro, lo que significa que el tiempo de ejecución puede crecer exponencialmente con el tamaño del problema.
  . Métodos de resolución: Suele utilizar técnicas como ramificación y acotación (branch and bound) o planos de corte (cutting planes).
  . Escalabilidad: Eficiente para instancias pequeñas a medianas, pero puede volverse computacionalmente intensivo para problemas grandes.
  . Flexibilidad: Permite incorporar fácilmente restricciones adicionales al problema base.
  . Precisión: No se ve afectado por errores de redondeo como algunos métodos heurísticos.
  . Uso de software especializado: A menudo se implementa utilizando solucionadores de programación lineal entera como CPLEX, Gurobi o CBC.



Código Java (TSP_IntegerProgramming):

package tsp_programacionlinealentera;

import java.util.ArrayList;

public class TSP_ProgramacionLinealEntera {

    public static void main(String[] args) {
        double[][] distanceMatrix = {
            {0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
            {8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
            {823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
            {8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
            {1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
            {8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
            {5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
            {5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
            {7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
            {8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 9509, 7830, 5276, 7174, 8535, 2604},
            {7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 9509, 0, 1847, 8948, 9498, 9456, 4716},
            {2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 7830, 1847, 0, 1620, 6634, 7744, 9744},
            {4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 5276, 8948, 1620, 0, 2261, 3892, 7722},
            {510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 7174, 9498, 6634, 2261, 0, 6734, 6447},
            {7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 8535, 9456, 7744, 3892, 6734, 0, 2382},
            {6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 2604, 4716, 9744, 7722, 6447, 2382, 0}
        };
        TSPIP tsp = new TSPIP(distanceMatrix);
        ArrayList<Integer> bestRoute = tsp.solve();
        double bestDistance = tsp.calculateTotalDistance(bestRoute);

        System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
        System.out.println("Distancia mínima aproximada: " + bestDistance);
    }
}


Código Java (TSPIP.java):

package tsp_programacionlinealentera;

import java.util.ArrayList;

public class TSPIP {

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

    public TSPIP(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
    }

    public ArrayList<Integer> solve() {
        ArrayList<Integer> currentRoute = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            currentRoute.add(i);
        }

        double currentDistance = calculateTotalDistance(currentRoute);
        boolean improved = true;

        while (improved) {
            improved = false;
            for (int i = 1; i < numCities - 1; i++) {
                for (int j = i + 1; j < numCities; j++) {
                    ArrayList<Integer> newRoute = new ArrayList<>(currentRoute);
                    reverse(newRoute, i, j);
                    double newDistance = calculateTotalDistance(newRoute);

                    if (newDistance < currentDistance) {
                        currentRoute = newRoute;
                        currentDistance = newDistance;
                        improved = true;
                    }
                }
            }
        }

        return currentRoute;
    }

    private void reverse(ArrayList<Integer> route, int start, int end) {
        while (start < end) {
            int temp = route.get(start);
            route.set(start, route.get(end));
            route.set(end, temp);
            start++;
            end--;
        }
    }

    public double calculateTotalDistance(ArrayList<Integer> route) {
        double totalDistance = 0.0;
        for (int i = 0; i < route.size() - 1; i++) {
            totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
        }
        totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start
        return totalDistance;
    }
}


Resultado:

run:
Ruta óptima aproximada encontrada: [0, 4, 3, 10, 7, 8, 11, 2, 14, 5, 12, 1, 9, 15, 6, 13]
Distancia mínima aproximada: 30268.0
BUILD SUCCESSFUL (total time: 0 seconds)