Определение оптимального замкнутого маршрута

Рисунок 2.2 – Схема возможных маршрутов коммивояжера

Постановка задачи. Имеется п пунктов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Задана матрица lij транспортных расстояний между этими пунктами (время перевозки или поездки из пункта i в пункт j). Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным.

Решение. Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j - номера пунктов выезда и въезда, lij – расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что lij в общем случае может быть не равно расстоянию в обратном направлении lij ≠ lji.

Таблица 2.1 - Расстояния между пунктами

Из пункта i	В пункт j
	1	2	3	4	5	6
1	l11	l12	l13	l14	l15	l16
2	l21	l22	l23	l24	l25	l26
3	l31	l32	l33	l34	l35	l36
4	l41	l42	l43	l44	l45	l46
5	l51	l52	l53	l54	l55	l56
6	l61	l62	l63	l64	l65	l66

Построим математическую модель задачи, введя булевы переменные:

xij={

Популярные материалы:

Расчёт ведомости затрат труда на выполнение основных работ в «окно»
Фактические затраты, чел.∙мин, на выполнение какой-либо работы определяются из выражения Q = αaV, (2.20) где α – коэффициент, учитывающий потери рабочего времени на пропуск поездов, переходы в рабочей зоне и кратковремен ...

Охрана труда при проведении работ
Подготовить и одеть необходимые для работы средства индивидуальной защиты. Застегнуть манжеты рукавов специальной одежды. Осмотреть и подготовить свое рабочее место, убрать все лишние предметы, не загромождая при этом проходов. Проверит ...

Прирост парка легковых автомобилей
В связи с тем, что увеличивается число легковых автомобилей возрастает спрос и на услуги, предоставляемые автосервисными предприятиями. Началом автомобилизации Украины можно считать 70-е годы XX столетия. В этот период в Украине насчитыв ...