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)
sábado, 10 de agosto de 2024
Problema del Viajante de Comercio TSP (V.2). Método Optimization 3-Opt.
Suscribirse a:
Entradas (Atom)