, i=1,2,…17, j=1,2,…17, i≠16, j≠16, i≠j.

В качестве наименьшего времени следования по маршруту из i-го узла в узел 16 принимается минимальное из возможных значение:

.

Полученные маршруты из каждого узла в узел 16 и значения времён следования по ним занесем в таблицу 5.12 (приложение).

Приближение k=4

Определим время следования по возможному маршруту из i-го узла в узел 16, проходящему через j-й узел, с числом промежуточных узлов не более четырех как сумму времени следования от i-го узла до j-го узла и времени следования по маршруту из j-го узла в узел 16 с числом узлов не более трех:

, i=1,2,…17, j=1,2,…17, i≠16, j≠16, i≠j.

В качестве наименьшего времени следования по маршруту из i-го узла в узел 16 принимается минимальное из возможных значение:

.

Результаты расчетов показывают, что на

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

В таблице 5.12 (приложение) для каждого приближения приведены полученные маршруты в узел 16 и значения времени следования по ним.

Искомые маршруты с минимальными значениями времён следования в узел 16 (пункт D2):

Из узла 1 (пункт A1): 1-8-12-16 (A1-E3-E7-D2); время перевозки 24;

Из узла 2 (пункт A2): 2-10-13-12-16 (A2-E5-Е8-E7-D2); время перевозки 21;

Из узла 3 (пункт A3): 3-10-13-12-16 (A3-E5-Е8-E7-D2); время перевозки 28;

Из узла 4 (пункт A4): 4-13-12-16 (A4-E8-Е7-D2); время перевозки 18;

Из узла 5 (пункт A5): 5-16 (A5-D2); время перевозки 126;

5.3.6 Пункт D1

Построим маршруты в узел 15 (пункт D1) из узлов 1 (пункт А1), 2 (пункт А2), 3 (пункт А3), 4 (пункт А4), 5 (пункт А5).

Приближение k = 0.

Определим наименьшее время следования (без посещения промежуточных узлов) по маршрутам в узел 15. Для каждого j-го узла (j=1, 2, 3, 4, 11, 14), который соединен дугой с узлом 15 (т.е. имеется прямой маршрут), наименьшее время следования по маршруту принимается равным времени следования между этим узлом и узлом 15; для остальных узлов значения принимаются равными бесконечности:

;

;

;

;

;

;

;

Полученные маршруты и значения времени следования по ним занесем в таблицу 5.17 (приложение).