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

Информация » Стратегия управления доставкой груза на транспорте » Определение оптимального замкнутого маршрута

Страница 1

Рисунок 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={

Страницы: 1 2 3 4

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

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

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

Определение потребности в технологическом оборудовании
Определили потребности СТО в технологическом оборудовании, оргоснастки, перечень и количество которого установили на основе выполняемых станцией видов работ с учетом соблюдения сертификационных требований. Таблица 18. Технологическое обо ...