2.3.2 ПунктD1

Построим маршруты в узел 18 (пункт D₃) из узлов 1 (пункт A₁), 2 (пункт A₂), 3 (пункт A₃),4 (пуект A₄₎ .

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

Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 18. Для каждого j-го узла (j = 13, 15), который соединен дугой с узлом 18 (т.е. имеется прямой маршрут), длина U⁰_j кратчайшего маршрута принимается равной расстоянию L_j-18 между этим узлом и узлом 18; для остальных узлов значения U⁰_j принимаются равными бесконечности:

U⁰₈ = L_13-18 = 12;

U⁰₉ = L_15-18 = 22.

Полученные маршруты и значения их длин U⁰_j занесем в таблицу 11.

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

Определим длину L¹_i-j возможного маршрута из i-го узла в узел 18 (пункт D₃), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния L_i-j от i-го узла до j-го узла и длины U⁰_j прямого маршрута из этого узла в узел 18 (пункт D₃):

L¹_i-j = L_i-j + U⁰_j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.

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

U¹_i = min {L¹_i-j}.

Таблица 8 – Маршруты в узел 18 с числом промежуточных узлов не более одного

Из узла 14	j	L14-j	U0j	L114-j	U114
14- 13-18	13	9	12	21	21
14-15-18	15	15	22	37
Из узла 17	j	L17-j	U0j	L117-j	U117
17- 15-18	15	7	22	29	29
Из узла 12	j	L6-j	U0j	L16-j	U16

Продолжение таблицы 8- Маршруты в узел 18 с числом узлов не более одного

12-13-18	13	6	12	18	18
12-15-18	15	2	22	24
Из узла 11	j	L11-j	U0j	L111-j	U111
11-15-18	15	9	22	31	31
Из узла 9	j	L9-j	U0j	L19-j	U19
9-13-18	13	40	12	52	52
Из узла 10	j	L10-j	U0j	L110-j	U110
10-15-18	15	10	22	32	32
Из узла 8	j	L8-j	U0j	L18-j	U18
8-13-18	13	12	12	24	24

Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U¹_j (выделены заливкой) занесем в таблицу 11.

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

Определим длину L²_i-j возможного маршрута из i-го узла в узел 18 (пункт D₃), проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния L_i-j от i-го узла до j-го узла и длины U¹_j маршрута из этого узла в узел 18 (пункт D₃) с числом узлов не более одного:

L²_i-j = L_i-j + U¹_j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.

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

U²_i = min {L²_i-j}.

Таблица 9 – Маршруты в узел 18 с числом промежуточных узлов не более двух

Из узла 1	j	L1-j	U1j	L21-j	U21
1-10-15-18	10	16	32	48	48
1-9-13-18	9	5	52	57
Из узла 2	j	L2-j	U1j	L22-j	U22
2-11-15-18	11	44	31	75
2-10-15-18	10	9	32	41	41
Из узла 3	j	L3-j	U1j	L23-j	U23
3-12-13-18	12	20	18	38	38
3-11-15-18	11	9	31	40
Из узла 4	j	L4-j	U1j	L24-j	U24

Продолжение таблицы 9- Маршруты в узел 18 с числом узлов не более двух

4-12-13-18	12	11	18	29	29
Из узла 7	j	L7-j	U1j	L27-j	U27
7-8-13-18	8	3	24	27	27
Из узла 8	j	L8-j	U1j	L28-j	U28
8-9-13-18	9	9	52	61
8-13-18	13	12	12	24	24
Из узла 9	j	L9-j	U1j	L29-j	U29
9-10-15-18	10	11	32	43
9-13-18	13	40	12	52
9-8-13-18	9	24	33	33	33
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-18	15	10	22	32	32
10-11-15-18	11	4	31	34
10-14-13-18	14	12	21	33
Из узла 15	j	L15-j	U1j	L215-j	U215
15-12-13-18	12	2	18	20	20
Из узла 14	j	L14-j	U1j	L214-j	U214
14-13-18	13	9	12	21	21
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-18	13	6	12	18	18
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-18	15	9	22	31	31

Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U²_j (выделены заливкой) занесем в таблицу 11.

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

Определим длину L³_i-j возможного маршрута из i-го узла в узел 18, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния L_i-j от i-го узла до j-го узла и длины U²_j маршрута из этого узла в узел 18 с числом узлов не более одного:

L³_i-j = L_i-j + U²_j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.

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

U³_i= min {L³_i-j

Таблица 10 – Маршруты в узел 18 с числом промежуточных узлов не более трех

Из узла 1	j	L1-j	U2j	L31-j	U31
1-10-15-18	10	16	32	48
1-9-8-13-18	9	5	33	38	38
Из узла 2	j	L2-j	U2j	L32-j	U32
2-10-15-18	10	9	32	41	41
2-10-14-13-18	10	9	33	42
Из узла 3	j	L2-j	U2j	L32-j	U32
3-12-13-18	12	20	18	38	38
Из узла 4	j	L4-j	U2j	L34-j	U34
4-12-13-18	12	11	18	29	29
Из узла 7	j	L7-j	U1j	L27-j	U27
7-8-13-18	8	3	24	27	27
Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-18	13	12	12	24	24
Из узла 9	j	L9-j	U1j	L29-j	U29
9-8-13-18	9	24	33	33	33
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-12-13-18	15	10	20	30	30
10-15-18	15	10	22	32
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-18	15	9	22	31	31
11-10-14-13-18	10	4	33	37
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-18	13	6	12	18	18
Из узла 15	j	L15-j	U1j	L215-j	U215
15-12-13-18	12	2	18	20	20

Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U³_j (выделены заливкой) занесем в таблицу 11.

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

Определим длину L⁴_i-j возможного маршрута из i-го узла в узел 18, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния L_i-j от i-го узла до j-го узла и длины U³_j маршрута из j-го узла в узел 18 с числом узлов не более трех:

L⁴_i-j = L_i-j + U³_j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.

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

U⁴_i = min {L⁴_i-j}.

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

В таблице 11 для каждого приближения приведены полученные кратчайшие маршруты в узел 18 и их длины.

Таблица 11 – Кратчайшие маршруты в узел 18

J	k=0		k=1		K=2		k=3		k=4
	Маршрут	U0j	Маршрут	U1j	Маршрут	U2j	Маршрут	U3j	Маршрут	U4j
1					1-10-15-18	48	1-9-8-13-18	38	1-9-8-13-18	38
2					2-10-15-18	41	2-10-15-18	41	2-10-15-12-13-18	39
3					3-12-13-18	38	3-12-13-18	38	3-12-13-18	38
4					4-12-13-18	29	4-12-13-18	29	4-12-13-18	29
5
6
7					7-8-13-18	27	7-8-13-18	27	7-8-13-18	27
8			8-13-18	24	8-13-18	24	8-13-18	24	8-13-18	24
9			9-13-18	52	9-8-13-18	33	9-8-13-18	33	9-8-13-18	33
10			10-15-18	32	10-15-18	32	10-15-12-13-18	30	10-15-12-13-18	30
11			11-15-18	31	11-15-18	31	11-15-18	31	11-15-18	31
12			12-13-18	18	12-13-18	18	12-13-18	18	12-13-18	18
13	13-18	12	13-18	12	13-18	12	13-18	12	13-18	12
14			14-13-18	21	14-13-18	21	14-13-18	21	14-13-18	21
15	15-18	22	15-18	22	15-12-13-18	20	15-12-13-18	20	15-12-13-18	20

Искомые кратчайшие маршруты в узел 18 (пункт D₃)

из узла 1 (пункт А₁): 1-9-8-13-18 (А₁-Е₃-Е₂- Е₇-D₃); расстояние перевозки 38;

из узла 2 (пункт А₂): 2-10-15-12-13-18 (A₂-E₄-E₉-E₆- E₇-D₃); расстояние перевозки 39;

из узла 3 (пункт А₃): 3-12-13-18 (A₃-E₆-E₇-D₃); расстояние перевозки 38;

из узла 4 (пункт А₄): 4-12-13-18 (A₄-E₆-E₇-D₃); расстояние перевозки 29.

В таблице 12 приведены расстояния между пунктами отправления и пунктами назначения.

Таблица 12 – Расстояния между пунктами отправления и взаимодействия

		Пункты
Расстояние, км		взаимодействия
		D1	D2	D3	D4
Пункт отправления	A1	96	33	38		37
	A2	75	26	39		30
	A3	36	25	38		34
	A4	20	20	29		35
	A5	80	23	48		120
	A6	140	92	26		54