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

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

Страница 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

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

Расчёт годовой производственной программы
Определение нормативов пробега (L1 и L2) между ТО – 1 и ТО – 2 Норматив пробега определяют с помощью коэффициентов по формуле: L1= L1Н∙K1∙K3, (2.1) где L1н – величина пробега между ТО – 1; K1 – коэффициент учитывающий вли ...

Расчет годового объема работ СТО
Годовой объем работ СТО по ТО и ТР, чел-ч (4) где Lг – среднегодовой пробег одного легкового автомобиля в зоне обслуживания СТО, км. Таблица 4. Расчет годового объема работ СТО по ТО и ТР Класс грузового автомобиля Число автомо ...

Кинематика кривошипно-шатунного механизма
Рис. 1 Sx – текущее перемещение поршня (точка А – ось поршневого пальца); φ – угол поворота кривошипа (ОВ), отсчитываемый по оси цилиндра (А`О) в направлении вращения коленчатого вала по часовой стрелке (точка О обозначает ось ко ...