2 Определение расстояний перевозки

2.1 Пункты отправления – пункты назначения (первый вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом отправления единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 1).

Таблица 1 – Расстояния между пунктами

отправления и назначения

		Пункты
Расстояние, км		назначения
		В1	В2
Пункты отправления	А1	24	60
	А2	14	30
	А3	56	17
	A4	98	68
	A5	140	119
	A6	182	170

2.2 Пункты взаимодействия – пункты назначения (второй вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом взаимодействия единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 2).

Таблица 2 – Расстояния между пунктами

взаимодействия и назначения

		Пункты
Расстояние, км		назначения
		В1	В2
Пункты взаимодействия	D1	84	51
	D2	126	102
	D3	186	153
	D4	210	204

2.3 Пункты отправления – пункты взаимодействия (первый вид транспорта)

Из матрицы расстояний видно, что прямых маршрутов между пунктами A_k (k = 1...4) отправления и пунктами D_i (i = 3...4) взаимодействия нет. Между пунктами A_k (k = 1...6) отправления и пунктами D_i (i = 1...2) взаимодействия есть, пока его учитывать не будем. Необходимо построить кратчайшие маршруты, пролегающие через промежуточные пункты E_s (s = 1...9), и определить длины этих маршрутов.

Сформируем матрицу расстояний между пунктами A_k отправления, промежуточными пунктами E_s, пунктами D_i взаимодействия; введем сквозную нумерацию узлов (таблица 3).

2.3.1 Пункт d4

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

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

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

U⁰₉ = L_12-19 = 33;

U⁰₁₀ = L_14-19 = 9.

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

Таблица 3 – Матрица расстояний между пунктами отправления,

взаимодействия и промежуточными пунктами

Пункты			А1		А2		А3		A4		A5		A6		E1		E2		E3		E4		E5		E6		E7		E8		E9		D1		D2		D3		D4
	Узлы	1		2		3		4		5		6		7		8		9		10		11		12		13		14		15		16		17		18		19
А1	1																	5		16												96		33
А2	2																			9		44										75		26
А3	3																					9		20								36		25
A4	4																							11								20		20
A5	5																															80		23		48		120
A6	6																															140		92		26		54
E1	7															3
E2	8													3				9								12
E3	9	5														9				11						40
E4	10	16		9														11				4						12		10
E5	11			44		9														4										9
E6	12					20		11																		6				2								33
E7	13															12		40						6				9								12
E8	14																			12						9				15								9
E9	15																			10		9		2				15
D1	16	96		75		36		20		80		140
D2	17	33		26		25		20		23		92																		7
D3	18									48		26														12				22
D4	19									120		54												33				9

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

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

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

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

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

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

Из узла 13	j	L13-j	U0j	L113-j	U113
13-14-19	14	9	9	18	18
13-12-19	12	6	33	39
Из узла 15	j	L15-j	U0j	L115-j	U115
15-14-19	14	15	9	24	24
15-12-19	12	2	33	35
Из узла 10	j	L10-j	U0j	L110-j	U110
10-14-12	14	12	9	21	21
Из узла 3	j	L3-j	U0j	L13-j	U13
3-12-19	12	20	33	53	53
Из узла 4	j	L4-j	U0j	L14-j	U14
4-12-19	12	11	33	44	44

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

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

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

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

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

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

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

Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-14-19	13	12	18	30	30
8-13-12-19	13	12	39	51
Из узла 9	j	L9-j	U1j	L29-j	U29
9-13-12-19	13	40	39	79
9-13-14-19	13	40	18	58	58
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-12-19	15	10	35	45
10-15-14-19	15	10	24	34	34
10-14-19	14		21	21	21
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-14-19	15	9	24	33
11-10-14-19	10	4	21	25	25
Из узла 12	j	L12-j	U1j	L212-j	U212
12-19	12			33
12-15-14-19	15	2	24	26
12-13-14-19	13	6	18	24	24
Из узла 1	j	L1-j	U1j	L21-j	U21
1-10-14-19	10	16	21	37	37
Из узла 2	j	L2-j	U1j	L22-j	U22
2-10-14-19	10	9	21	30	30

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

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

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

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

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

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

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

Из узла 1	j	L1-j	U2j	L31-j	U31
1- 10-14-19	10	16	21	37	37
1-9-13-14-19	9	5	58	63
1-10-15-14-19	10	16	34	50
Из узла 2	j	L2-j	U2j	L32-j	U32
2- 10-14-19	10	9	21	30	30
2-10-15-14-19	10	9	34	43
2-11-10-14-19	11	44	25	69
Из узла 3	j	L3-j	U2j	L33-j	U33
3-12-19	12	20	33	53
3-11-10-14-19	11	9	25	34	34
Из узла 4	j	L4-j	U2j	L34-j	U34
4-12-19	12	11	33	44
4-12-15-14-19	12	11	26	37
4-12-13-14-19	12	11	24	35	35
Из узла 8	j	L8-j	U1j	L28-j	U28
8-13-14-19	13	12	18	30	30
8-13-12-19	13	12	39	51
Из узла 9	j	L9-j	U1j	L29-j	U29
9-13-12-19	13	40	39	79
9-13-14-19	13	40	18	58	58
Из узла 10	j	L10-j	U1j	L210-j	U210
10-15-14-19	15	10	24	34
10-14-19	14		21	21	21
Из узла 11	j	L11-j	U1j	L211-j	U211
11-15-14-19	15	9	24	33
11-10-14-19	10	4	21	25	25
Из узла 12	j	L12-j	U1j	L212-j	U212
12-13-14-19	13	6	18	24	24

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

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

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

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

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

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

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

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

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

	k=0			k=1			K=2			k=3			k=4
	Маршрут	U0j	Маршрут		U1j	Маршрут		U2j	Маршрут		U3j	Маршрут		U4j
1						1-10-14-19		37	1-10-14-19		37	1-10-14-19		37
2						2-10-14-19		30	2-10-14-19		30	2-10-14-19		30
3			3-12-19		53	3-12-19		53	3-11-10-14-19		34	3-11-10-14-19		34
4			4-12-19		44	4-12-19		44	4-12-13-14-19		35	4-12-13-14-19		35
5
6
7
8						8-13-14-19		30	8-13-14-19		30	8-13-14-19		30
9						9-13-14-19		58	9-13-14-19		58	9-13-14-19		58
10			10-14-19		21	10-14-19		21	10-14-19		21	10-14-19		21
11						11-10-14-19		25	11-10-14-19		25	11-10-14-19		25
12	12-19	33	12-19		33	12-13-14-19		24	12-13-14-19		24	12-13-14-19		24
13			13-14-19		18	13-14-19		18	13-14-19		18	13-14-19		18
14	14-19	9	14-19		9	14-19		9	14-19		9	14-19		9
15			15-14-19		24	15-14-19		24	15-14-19		24	15-14-19		24
16
17
18

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

из узла 1 (пункт А₁): 1-10-14-19 (А₁-Е₄-Е₈-D₄); расстояние перевозки 37;

из узла 2 (пункт А₂): 2-10-14-19 (A₂-E₄-E₈-D₄); расстояние перевозки 30;

из узла 3 (пункт А₃): 3-11-10-14-19 (A₃-E₅-E₄-E₈-D₄); расстояние перевозки34;

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