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

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

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

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

.

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

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

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

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

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

.

Полученные маршруты с наименьшим временем следования из каждого узла в узел 17 и значения их длин занесем в таблицу 8.

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

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

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

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

.

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

В таблице 5.8 (приложение) для каждого приближения приведены полученные значения минимальных времён следования в узел 17.

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

Из узла 1 (пункт A1): 1-8-12-13-17 (A1-E3-E7-E8-D3); время перевозки 34;

Из узла 2 (пункт A2): 2-10-11-17 (A2-E5-E6-D3); время перевозки 15;

Из узла 3 (пункт A3): 3-10-11-17 (A3-E5-E6 -D3); время перевозки 22;

Из узла 4 (пункт A4): 4-13-17 (A4-E8-D3); время перевозки 20;