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)
jueves, 15 de agosto de 2024
Problema del viajante de Comercio TSP (XIV). Método Programación Lineal Entera (PLE).
Problema del viajante de Comercio TSP (XIII). Método Aproximación de Christofides.
El Algoritmo de Aproximación de Christofides es un método para resolver el Problema del Viajante de Comercio (TSP).
Características:
Garantía de aproximación: Proporciona una solución que es, como máximo, 3/2 veces el óptimo para instancias que cumplen la desigualdad triangular.
Complejidad: Tiene una complejidad temporal de O(n^3), donde n es el número de ciudades.
Pasos principales:
1.Construye un árbol de expansión mínima (MST)
2.Encuentra vértices de grado impar en el MST
3.Crea un emparejamiento perfecto de mínimo peso para estos vértices
4.Combina el MST y el emparejamiento para formar un circuito euleriano
5.Convierte el circuito euleriano en un tour hamiltoniano
Aplicabilidad: Es especialmente útil para instancias del TSP que cumplen la desigualdad triangular.
Eficiencia: Ofrece un buen equilibrio entre calidad de la solución y tiempo de ejecución.
Limitaciones: No garantiza el óptimo global y su rendimiento puede degradarse en instancias que no cumplen la desigualdad triangular.
Código Java (TSP_Christofides.java):
package tsp_christofides;
import java.util.ArrayList;
public class TSP_Christofides {
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}
};
TSPCh tsp = new TSPCh(distanceMatrix);
ArrayList<Integer> bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
// Verificar la desigualdad triangular
if (!tsp.checkTriangleInequality()) {
System.out.println("ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.");
System.out.println("El resultado puede no ser óptimo o estar alejado del óptimo esperado.\n");
}
System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
System.out.println("Distancia mínima aproximada: " + bestDistance);
}
}
Código Java (TSPCh.java):
package tsp_christofides;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;
public class TSPCh {
private final double[][] distanceMatrix;
private final int numCities;
public TSPCh(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
public ArrayList<Integer> solve() {
ArrayList<int[]> mstEdges = generateMST();
ArrayList<Integer> oddDegreeNodes = findOddDegreeNodes(mstEdges);
ArrayList<int[]> perfectMatching = generatePerfectMatching(oddDegreeNodes);
ArrayList<int[]> eulerianCircuit = combineMSTAndMatching(mstEdges, perfectMatching);
return findHamiltonianCircuit(eulerianCircuit);
}
private ArrayList<int[]> generateMST() {
boolean[] inMST = new boolean[numCities];
double[] key = new double[numCities];
int[] parent = new int[numCities];
Arrays.fill(key, Double.MAX_VALUE);
key[0] = 0;
parent[0] = -1;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingDouble(o -> key[o[0]]));
pq.add(new int[]{0, -1});
ArrayList<int[]> mstEdges = new ArrayList<>();
while (!pq.isEmpty()) {
int u = pq.poll()[0];
inMST[u] = true;
for (int v = 0; v < numCities; v++) {
if (!inMST[v] && distanceMatrix[u][v] < key[v]) {
key[v] = distanceMatrix[u][v];
pq.add(new int[]{v, u});
parent[v] = u;
}
}
}
for (int i = 1; i < numCities; i++) {
mstEdges.add(new int[]{i, parent[i]});
}
return mstEdges;
}
private ArrayList<Integer> findOddDegreeNodes(ArrayList<int[]> mstEdges) {
int[] degree = new int[numCities];
for (int[] edge : mstEdges) {
degree[edge[0]]++;
degree[edge[1]]++;
}
ArrayList<Integer> oddDegreeNodes = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
if (degree[i] % 2 != 0) {
oddDegreeNodes.add(i);
}
}
return oddDegreeNodes;
}
private ArrayList<int[]> generatePerfectMatching(ArrayList<Integer> oddDegreeNodes) {
ArrayList<int[]> perfectMatching = new ArrayList<>();
boolean[] matched = new boolean[numCities];
for (int i = 0; i < oddDegreeNodes.size(); i++) {
if (matched[oddDegreeNodes.get(i)]) {
continue;
}
int minJ = -1;
double minDistance = Double.MAX_VALUE;
for (int j = i + 1; j < oddDegreeNodes.size(); j++) {
if (!matched[oddDegreeNodes.get(j)] && distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)] < minDistance) {
minDistance = distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)];
minJ = j;
}
}
matched[oddDegreeNodes.get(i)] = true;
matched[oddDegreeNodes.get(minJ)] = true;
perfectMatching.add(new int[]{oddDegreeNodes.get(i), oddDegreeNodes.get(minJ)});
}
return perfectMatching;
}
private ArrayList<int[]> combineMSTAndMatching(ArrayList<int[]> mstEdges, ArrayList<int[]> perfectMatching) {
ArrayList<int[]> combinedGraph = new ArrayList<>(mstEdges);
combinedGraph.addAll(perfectMatching);
return combinedGraph;
}
private ArrayList<Integer> findHamiltonianCircuit(ArrayList<int[]> eulerianCircuit) {
LinkedHashSet<Integer> visited = new LinkedHashSet<>();
Stack<Integer> stack = new Stack<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : eulerianCircuit) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
}
stack.push(0);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
if (graph.containsKey(node)) {
for (int neighbor : graph.get(node)) {
stack.push(neighbor);
}
}
}
}
return new ArrayList<>(visited);
}
public double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
int city1 = route.get(i);
int city2 = route.get(i + 1);
totalDistance += distanceMatrix[city1][city2];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start city
return totalDistance;
}
public boolean checkTriangleInequality() {
for (int i = 0; i < numCities; i++) {
for (int j = 0; j < numCities; j++) {
for (int k = 0; k < numCities; k++) {
if (distanceMatrix[i][j] > distanceMatrix[i][k] + distanceMatrix[k][j]) {
return false;
}
}
}
}
return true;
}
}
Resultado:
run:
ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.
El resultado puede no ser óptimo o estar alejado del óptimo esperado.
Ruta óptima aproximada encontrada: [0, 13, 8, 11, 12, 5, 14, 6, 1, 3, 4, 2, 7, 15, 9, 10]
Distancia mínima aproximada: 43089.0
BUILD SUCCESSFUL (total time: 0 seconds)
Problema del viajante de Comercio TSP (XII). Método de Recocido Simulado (Simulated Annealing).
El Algoritmo de Recocido Simulado (Simulated Annealing) es una técnica metaheurística inspirada en el proceso de enfriamiento de metales, donde se trata de encontrar una solución cercana al óptimo global para problemas de optimización, como el Problema del Viajero (TSP). El algoritmo funciona de la siguiente manera:
Inicialización: Comienza con una solución inicial (ruta en el caso del TSP) y una temperatura inicial alta.
Vecindario: En cada iteración, se genera una nueva solución en el vecindario de la solución actual, por ejemplo, intercambiando dos ciudades en la ruta.
Aceptación de Soluciones: La nueva solución se acepta automáticamente si es mejor que la solución actual. Si es peor, se acepta con una probabilidad que disminuye a medida que la temperatura baja, permitiendo así escapar de óptimos locales.
Enfriamiento: La temperatura se reduce gradualmente según una política de enfriamiento, hasta que se alcanza un umbral mínimo, momento en el que se detiene la búsqueda.
Criterio de Terminación: El algoritmo termina cuando la temperatura es muy baja o después de un número fijo de iteraciones sin mejora significativa.
Código Java (TSP_RecocidoSimulado.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
public class TSP_RecocidoSimulado {
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, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 5176, 967, 3706, 6509, 7380, 1942, 0, 6631, 1397},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 6631, 0, 2345},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 1397, 2345, 0}
};
// Parametros de entrada:
double TemperaturaInicial = 10000;
double TasaEnfriamiento = 0.9999;
int NumeroIteraciones = 1000000;
TSPRS tsp = new TSPRS(distanceMatrix, TemperaturaInicial, TasaEnfriamiento, NumeroIteraciones);
// Generar una solución inicial (ruta aleatoria)
ArrayList<Integer> initialRoute = new ArrayList<>();
for (int i = 0; i < distanceMatrix.length; i++) {
initialRoute.add(i);
}
Collections.shuffle(initialRoute);
// Resolver el TSP usando Recocido Simulado
ArrayList<Integer> bestRoute = tsp.solve(initialRoute);
double bestDistance = tsp.calculateTotalDistance(bestRoute);
// Imprimir los resultados
System.out.println("Ruta óptima encontrada: " + bestRoute);
System.out.println("Distancia mínima: " + bestDistance);
}
}
Código Java (TSPRS.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class TSPRS {
private final double[][] distanceMatrix;
private final double initialTemperature;
private final double coolingRate;
private final int maxIterations;
private final Random random;
public TSPRS(double[][] distanceMatrix, double initialTemperature, double coolingRate, int maxIterations) {
this.distanceMatrix = distanceMatrix;
this.initialTemperature = initialTemperature;
this.coolingRate = coolingRate;
this.maxIterations = maxIterations;
this.random = new Random();
}
public ArrayList<Integer> solve(ArrayList<Integer> initialRoute) {
ArrayList<Integer> currentRoute = new ArrayList<>(initialRoute);
ArrayList<Integer> bestRoute = new ArrayList<>(initialRoute);
double bestDistance = calculateTotalDistance(bestRoute);
double temperature = initialTemperature;
int iteration = 0;
while (temperature > 1 && iteration < maxIterations) {
ArrayList<Integer> newRoute = generateNeighbor(new ArrayList<>(currentRoute));
double currentDistance = calculateTotalDistance(currentRoute);
double newDistance = calculateTotalDistance(newRoute);
if (acceptanceProbability(currentDistance, newDistance, temperature) > random.nextDouble()) {
currentRoute = new ArrayList<>(newRoute);
}
if (calculateTotalDistance(currentRoute) < bestDistance) {
bestRoute = new ArrayList<>(currentRoute);
bestDistance = calculateTotalDistance(bestRoute);
}
temperature *= coolingRate;
iteration++;
}
return bestRoute;
}
private ArrayList<Integer> generateNeighbor(ArrayList<Integer> route) {
int pos1 = random.nextInt(route.size());
int pos2 = random.nextInt(route.size());
Collections.swap(route, pos1, pos2);
return route;
}
private double acceptanceProbability(double currentDistance, double newDistance, double temperature) {
if (newDistance < currentDistance) {
return 1.0;
}
return Math.exp((currentDistance - newDistance) / temperature);
}
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)]; // Regreso a la ciudad de inicio
return totalDistance;
}
}
Resultado:
run:
Ruta óptima encontrada: [7, 8, 11, 2, 5, 14, 6, 1, 12, 3, 4, 0, 13, 15, 9, 10]
Distancia mínima: 23620.0
BUILD SUCCESSFUL (total time: 0 seconds)