Dibuja el mapa y se detiene

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

Formulación problemática

Formular el problema del vendedor ambulante para la programación lineal de enteros de la siguiente manera:

Calcular distancias entre puntos

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 variables y problema

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;

Restricciones de igualdad

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;

Resuelva el problema inicial

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]

Visualice la solución

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.

Restricciones subtour

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

Calidad de la solución

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.