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

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

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

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

Составление рациональных транспортных схем и возможных вариантов закрепления флота
Движение судов при перевозках грузов должно быть организованно так, чтобы производительность работы флота судоходного предприятия была наибольшей, а себестоимость перевозок наименьшей, что достигается минимальными балластными пробегами. ...

Анализ технологической операции
025 Операция. Шлифовальная. После проведения всех основных восстановительных операций необходимо произвести механическую обработку для доведения до номинального размера. Так как припуск на механическую обработку невелик (0,13мм), то сразу ...

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