Правило отсечения множества

Задачи маршрутизации

J — множество клиентов

K — множество грузовиков

Q_k — грузоподъемность грузовика k Î K

 

Задача коммивояжера (TSP)

Дана матрица (c_ij) попарных расстояний между городами, 1 £ i, j £ n.

Найти контур минимальной длины, то есть цикл, проходящий через каждую вершину ровно один раз и имеющий минимальный вес.

Теорема 1. Задача коммивояжера является NP-трудной даже в случае, когда (с_ij) — евклидовы расстояния на плоскости, то есть матрица симметрична и удовлетворяет неравенству треугольника

с_ij £ с_ik + с_kj, 1 £ i, j, k £ n.

Составление расписаний на одном станке

Дано n деталей и один станок, с_ij — длительность переналадки станка для обработки j -й детали после i- й детали, p_j – длительность обработки j -й детали.

Найти последовательностьобработки деталей, имеющую минимальную суммарную длительность.

	in		in –1		…		i 1

	детали		станок

Раскрой рулонного материала с рисунком

Дано бесконечный рулон с рисунком в 1м и размеры n кусков

0 £ s_j £ 1 — начало куска j, 0 £ f_j £ 1 — конец куска j. Начало рулона и конец раскроя — f ₀.

Найти последовательностьотрезания кусков с минимальной длиной использованного материала

Задача коммивояжера для (n + 1)-го города.

Математическая модель задачи коммивояжера

Пусть - полный ориентированный граф, где - множество вершин – городов, - множество ребер (участков дорог). Каждому ребру сопоставлено число - расстояние (или стоимость) между парой городов.

Введем переменные

 

 

Найти маршрут наименьшей стоимости

при выполнении следующих условий

(только одно ребро должно выходить из каждой вершины)

(только одно ребро должно входить в каждую вершину)

, (запрещены замкнутые маршруты)

 

Задача коммивояжера в Интернет

· TSPBIB Home Page https://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html

· The Hamiltonian Page: Hamiltonian cycle and path problems, their generalizations and variations

https://www.ing.unlp.edu.ar/cetad/mos/Hamilton.html

 

· Fractal Instances of the Traveling Salesman Problem

https://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html

 

· DIMACS: The Traveling Salesman Problem

https://www.research.att.com/~dsj/chtsp/

Метод ветвей и границ

В основе метода лежит принцип «разделяй и властвуй».

Пусть D — множество допустимых решений задачи

min { f (x) | x Î D },

и для любого подмножества d Í D вычисляют:

LB (d)[1] — нижнюю оценку для минимума f (x), x Î d,

UB (d) — верхнюю оценку для минимума f (x), x Î d,

т. е.

LB (d) £ min { f (x) | x Î d } £ UB (d), для любого d Í D.

Пусть x ⁰ — текущий рекорд и сначала f (x ⁰) = UB (D). Вычисляем LB (D) и, если LB (D) = UB (D), то STOP, x⁰ — оптимальное решение задачи.

В противном случае разбиваем[2] D на подмножества

D = d ₁ È …. È d_k. Для каждого подмножества вычисляем UB (d_i), LB (d_i), i = 1,…, k.

Если f (x⁰) > UB (d_i), то меняем рекорд.

Если LB (d_i) ³ f (x⁰), то отсекаем d_i, иначе дробим d_i на подмножества. Так как D — конечное множество, то процесс конечен, и дает точное решение задачи.

Описание метода В&Г (один шаг)

На каждом шаге имеется

- рекорд x⁰;

- просмотренная часть P Ì D, для которой f (x) ³ f (x⁰), x Î P;

- разбиение множества D \ P на подмножества .

Шаг алгоритма

1. Выбрать элемент разбиения, например,

2. Вычислить Если то сменить рекорд x⁰.

3. Вычислить

3.1. Если то добавить к P и перейти к следующему шагу.

3.2. Если то в множестве удалось найти наилучший элемент : добавить к P; если то положить .

3.3. Если но элемент найти не удалось, то разбиваем на подмножества и переходим к следующему шагу, имея новое разбиение для D \ P.

Метод В&Г для задачи коммивояжера

D

d 5

d 6

d 4

d 2

d 3

d 1

{1,5,3}

{1,5,4}

{1,5}

Разбиение множества D представляется в виде бинарного дерева.

Каждой вершине дерева соответствует частичный тур и список запретов.

Например, вершине d ₆ соответствует

частичный тур 1,5 и запреты {4,3}

на выход из города 5.

 

Правило отсечения множества

Пусть проверяется множество . Оно отсекается в одном из двух последовательно проверяемых случаев:

А) если ;

Б) если и найден такой элемент , что .

 

В случае Б) происходит смена рекорда

 

Примитивная нижняя оценка для вершины дерева,

например, d ₆:

( наименьшие элементы в -ой строке и -м столбце соответственно)

Верхняя оценка — алгоритм «Иди в ближайший».
Выбор переменной для ветвления

Основная идея — угадать оптимальное решение на подмножестве и ветвиться по дугам этого тура.

Введем обозначения:

- простой путь из вершины в вершину ;

- длина контура , пусть =1;

- подмножества допустимых решений, где

- частичный маршрут (последовательность посещения первых городов),

- совокупность запретов на переходы из последнего города частичного маршрута .

Если , то и пара задает одноэлементное множество.

Если , то определяем функцию ветвления, которая разбивает множество контуров на два подмножества:

1) контуры, в которых коммивояжер из конечного пункта частичного маршрута переезжает в некоторый город

2) контуры, в которых переход из конечного пункта частичного маршрута в некоторый город запрещен