Esta página es para la versión anterior. La página correspondiente en inglés ha sido eliminada en la versión actual.
Este ejemplo muestra cómo utilizar la programación de enteros binarios para resolver el problema clásico del vendedor ambulante. Este problema implica encontrar el recorrido cerrado más corto (ruta) a través de un conjunto de paradas (ciudades). En este caso hay 200 paradas, pero puede cambiar fácilmente la variable para obtener un tamaño de problema diferente.nStops
Resolverás el problema inicial y verás que la solución tiene subtours. Esto significa que la solución óptima encontrada no da una ruta continua a través de todos los puntos, pero en su lugar tiene varios bucles desconectados. A continuación, utilizará un proceso iterativo para determinar los subrecorridos, agregar restricciones y volver a ejecutar la optimización hasta que se eliminen los subrecorridos.
Para conocer el enfoque basado en el solucionador de este problema, consulte.Problema del vendedor viajante: basado en Solver
Genere paradas aleatorias dentro de una representación poligonal bruta de los Estados Unidos continentales.
figure; load('usborder.mat','x','y','xx','yy'); rng(3,'twister') % makes a plot with stops in Maine & Florida, and is reproducible nStops = 200; % you can use any number, but the problem size scales as N^2 stopsLon = zeros(nStops,1); % allocate x-coordinates of nStops stopsLat = stopsLon; % allocate y-coordinates n = 1; while (n <= nStops) xp = rand*1.5; yp = rand; if inpolygon(xp,yp,x,y) % test if inside the border stopsLon(n) = xp; stopsLat(n) = yp; n = n+1; end end plot(x,y,'Color','red'); % draw the outside border hold on % Add the stops to the map plot(stopsLon,stopsLat,'*b') hold off
Formular el problema del vendedor ambulante para la programación lineal de enteros de la siguiente manera:
Genere todos los viajes posibles, lo que significa que todos los pares de paradas diferentes.
Calcule la distancia para cada viaje.
La función de coste para minimizar es la suma de las distancias de viaje para cada viaje en el recorrido.
Las variables de decisión son binarias, y asociadas con cada viaje, donde cada 1 representa un viaje que existe en el Tour, y cada 0 representa un viaje que no está en el Tour.
Para asegurarse de que el tour incluye cada parada, incluya la restricción lineal que cada parada está en exactamente dos viajes. Esto significa una llegada y una salida de la parada.
Debido a que hay 200 paradas, hay 19.900 viajes, que significa 19.900 variables binarias (# variables = 200 elegir 2).
Generar todos los viajes, lo que significa todos los pares de paradas.
idxs = nchoosek(1:nStops,2);
Calcular todas las distancias de viaje, suponiendo que la tierra es plana con el fin de utilizar la regla de Pitágoras.
dist = hypot(stopsLat(idxs(:,1)) - stopsLat(idxs(:,2)), ... stopsLon(idxs(:,1)) - stopsLon(idxs(:,2))); lendist = length(dist);
Con esta definición del vector, la duración de un recorrido esdist
dist'*trips
donde está el vector binario que representa los viajes que toma la solución.trips
Esta es la distancia de un recorrido que intenta minimizar.
Crear un problema y variables binarias.
tsp = optimproblem; trips = optimvar('trips',lendist,1,'Type','integer','LowerBound',0,'UpperBound',1);
Incluya la función objetiva en el problema.
tsp.Objective = dist'*trips;
El problema tiene dos tipos de restricciones de igualdad. La primera impone que debe haber 200 viajes en total. El segundo impone que cada parada debe tener dos viajes adjuntos a él (debe haber un viaje a cada parada y un viaje saliendo de cada parada).
Especifique el primer tipo de restricción de igualdad, que debe tener viajes e incluirlo en el problema.nStops
constrips = sum(trips) == nStops; tsp.Constraints.constrips = constrips;
Para especificar el segundo tipo de restricción de igualdad, que debe haber dos viajes adjuntos a cada parada, encontrar los viajes para cada parada y sumar el número de viajes para esa parada. Mira los viajes que empiezan y terminan en esa parada.
constr2trips = optimconstr(nStops,1); for stops = 1:nStops whichIdxs = (idxs == stops); whichIdxs = any(whichIdxs,2); % start or end at stops constr2trips(stops) = sum(trips(whichIdxs)) == 2; end tsp.Constraints.constr2trips = constr2trips;
El problema está listo para ser resuelto. Para suprimir la salida iterativa, desactive la visualización predeterminada.
opts = optimoptions('intlinprog','Display','off'); tspsol = solve(tsp,'options',opts)
tspsol = struct with fields:
trips: [19900×1 double]
hold on segments = find(tspsol.trips); % Get indices of lines on optimal path lh = zeros(nStops,1); % Use to store handles to lines on plot lh = updateSalesmanPlot(lh,tspsol.trips,idxs,stopsLon,stopsLat); title('Solution with Subtours');
Como se puede ver en el mapa, la solución tiene varios subtours. Las restricciones especificadas hasta ahora no impiden que estos subcamino ocurran. Con el fin de evitar cualquier posible subtour de suceder, se necesitaría un número increíblemente grande de restricciones de desigualdad.
Dado que no puede agregar todas las restricciones de subrecorrido, tome un enfoque iterativo. Detecte los subrecorridos en la solución actual y, a continuación, agregue restricciones de desigualdad para evitar que esos subcamino particulares ocurran. Al hacer esto, encontrará un recorrido adecuado en unas cuantas iteraciones.
Elimine subrecorridos con restricciones de desigualdad. Un ejemplo de cómo funciona esto es si tienes cinco puntos en un subtour, entonces tienes cinco líneas conectando esos puntos para crear el subtour. Eliminar este subtour implementando una restricción de desigualdad para decir que debe haber menos o igual a cuatro líneas entre estos cinco puntos.
Aún más, encuentre todas las líneas entre estos cinco puntos, y restrinja la solución para no tener más de cuatro de estas líneas presentes. Esta es una restricción correcta porque si existían cinco o más líneas en una solución, la solución tendría un subtour (un gráfico con
La función analiza la solución y devuelve una matriz de vectores de celdas.detectSubtours
Cada vector en la matriz de celdas contiene las paradas involucradas en ese subrecorrido en particular.
tours = detectSubtours(tspsol.trips,idxs); numtours = length(tours); % number of subtours fprintf('# of subtours: %d\n',numtours);
# of subtours: 27
Incluya las restricciones de desigualdad lineales para eliminar subrecorridos, y llame repetidamente al solucionador, hasta que solo quede un subrecorrido.
% Index of added constraints for subtours k = 1; while numtours > 1 % repeat until there is just one subtour % Add the subtour constraints for ii = 1:numtours subTourIdx = tours{ii}; % Extract the current subtour % The next lines find all of the variables associated with the % particular subtour, then add an inequality constraint to prohibit % that subtour and all subtours that use those stops. variations = nchoosek(1:length(subTourIdx),2); a = false(length(idxs),1); for jj = 1:length(variations) whichVar = (sum(idxs==subTourIdx(variations(jj,1)),2)) & ... (sum(idxs==subTourIdx(variations(jj,2)),2)); a = a | whichVar; end tsp.Constraints.(sprintf('subtourconstr%i',k)) = sum(trips(a)) <= length(subTourIdx)-1; k = k + 1; end % Try to optimize again [tspsol,fval,exitflag,output] = solve(tsp,'options',opts); % Visualize result lh = updateSalesmanPlot(lh,tspsol.trips,idxs,stopsLon,stopsLat); % How many subtours this time? tours = detectSubtours(tspsol.trips,idxs); numtours = length(tours); % number of subtours fprintf('# of subtours: %d\n',numtours); end
# of subtours: 20
# of subtours: 7
# of subtours: 9
# of subtours: 9
# of subtours: 3
# of subtours: 2
# of subtours: 7
# of subtours: 2
# of subtours: 1
title('Solution with Subtours Eliminated'); hold off
La solución representa un recorrido factible, ya que es un único bucle cerrado. Pero, ¿es un tour de costo mínimo? Una forma de averiguarlo es examinando la estructura de salida.
disp(output.absolutegap)
0
La pequeñez de la brecha absoluta implica que la solución es o bien óptima o tiene una longitud total que está cerca de óptima.