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

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

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

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

Мероприятия по обеспечению безопасности дорожного движения
Эффективность и надежность эксплуатации подвижного состава во многом зависит от безопасной работы автотранспорта. В настоящее время этому вопросу уделяется особое внимание. Наше государство выделяет огромные средства, которые направлены н ...

Финансовый анализ проекта
Таблица 3.8 Расчет выручки и дохода от продажи продукции Наименование показателей Обозначение Значение показателей по итогам года 2012 2013 Цена единицы услуги (с НДС), тыс. руб. р 0,9 0,957 Объем реал ...

Определение ординат для разбивки переводной кривой стрелочного перевода
Начало координат для разбивки переводной кривой расположено на рабочей грани рамного рельса против корня остряка, точка (рис. 3.2). Координаты точек в конце переводной кривой определяются по формулам: где - начальное значение орди ...