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)
Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.
Archivo del blog
-
►
2012
(38)
- ► septiembre (3)
-
►
2020
(12)
- ► septiembre (1)
-
▼
2024
(29)
-
▼
agosto
(17)
- Problema del Viajante de Comercio TSP (V.1). Métod...
- Problema del Viajante de Comercio TSP (V.2). Métod...
- Problema del Viajante de Comercio TSP (V.3). Métod...
- Problema del viajante de Comercio TSP (IV.2). Méto...
- Problema del Viajante de Comercio TSP (V.3.1). Aná...
- Matriz de conectividad circular.
- Problema del viajante de Comercio TSP (VI). Método...
- Problema del viajante de Comercio TSP (VII). Métod...
- Problema del viajante de Comercio TSP (VIII). Méto...
- Problema del viajante de Comercio TSP (IX). Método...
- Problema del viajante de Comercio TSP (X). Método ...
- Problema del viajante de Comercio TSP (XI). Método...
- Problema del viajante de Comercio TSP (XII). Métod...
- Problema del viajante de Comercio TSP (XIII). Méto...
- Problema del viajante de Comercio TSP (XIV). Métod...
- Problema del viajante de Comercio TSP (XV). Método...
- Juegos VII. La Mansión Misteriosa: Un juego de tex...
-
▼
agosto
(17)
jueves, 15 de agosto de 2024
Problema del viajante de Comercio TSP (XIV). Método Programación Lineal Entera (PLE).
Suscribirse a:
Enviar comentarios (Atom)
Con la tecnología de Blogger.
No hay comentarios:
Publicar un comentario