Таблица 2.1.2. – расчет потребного количества автосредств.
Схема | tp, сут. | np ,рейсов. | Псп , т. | Nавто, Единиц. |
Александрия – Херсон | 0,29 | |||
Калиновка - Херсон | 0,51 | |||
Харьков - Феодосия | 0,66 | |||
Геническ - Феодосия | 0,19 |
2.2. Построение исходной системы (сети) доставки груза по сухопутному участку
Поставщики и потребители (порты) в сетевой транспортной задаче рассматриваются как источник и сток, соответственно. Необходимо построить исходную транспортную сеть с 6-8 промежуточными узлами с указанием расстояний.
Получили 4 схемы:
1) источник – Александрия, сток – Херсон;
2) источник – Калиновка, сток – Херсон;
3) источник – Харьков, сток – Феодосия;
4) источник – Геническ, сток – Феодосия.
Представим каждую схему более подробно с указанием промежуточных населённых пунктов.
Рис.2.2.1. Исходная сеть при построении рационального маршрута движения автотранспортных средств по маршруту «Александрия - Херсон»
Рис.2.2.2. Исходная сеть при построении рационального маршрута движения автотранспортных средств по маршруту «Калиновка - Херсон»
Рис.2.2.3. Исходная сеть при построении рационального маршрута движения автотранспортных средств по маршруту «Харьков- Феодосия»
Рис.2.2.4. Исходная сеть при построении рационального маршрута движения автотранспортных средств по маршруту «Геническ - Феодосия»
2.3. Нахождение оптимального маршрута
Задачу поиска наикротчайшего пути произведем с помощью алгоритма предложенного в методическом указании.
Для этого составим матрицу расстояний (таблица 2.3.1).
Таблица 2.3.1. – матрица расстояний для маршрута Александрия – Херсон.
Исходный пункт | Пункты назначения | |||||||
Определяем потенциалы для каждого узла сети:
Ui = min {Ui + dij},
где dij – расстояние между связанными узлами i и j;
Ui – кратчайшее расстояние между узлами.
U1 = 0
U2 = min {U1 + d12} = 0 + 109= 109 (км);
U3 = min {U2 + d23} = 109 + 69 = 178 (км);
U4 = min {U2 + d24} = 109 + 103 = 212 (км);
U5 = min {U3 + d35} = 178 + 96 = 274 (км);
U6 = min { U3 + d36 ;U4 + d46} = {178+181;212+45}={359;257} = 257 (км);
U7 = min { U5 + d57;U6 + d67} = {274+101;257+27} ={375;284}= 284 (км);
U8 = min { U5 + d58 ;U7 + d78} = min {274+74; 284+36} = min {348;320} = 320 (км);
Маршрут: 1 – 2 – 4 – 6 – 7 – 8
Минимальное расстояние: 320км.
Таким же образом находим маршруты по остальным поставщикам и результаты заносим в таблицы.
Таблица 2.3.2. – матрица расстояний для маршрута Калиновка -Херсон.
Исходный пункт | Пункты назначения | ||||||||
U1 = 0
U2 = min{U1 + d12} = 0 + 92 = 92 (км);
U3 = min{U1 + d13 } = 0+71=71 (км);
U4 = min{U2 + d24} = 92+88=180 (км);
U5 = min{ U2 + d25;U3 + d35} ={92+105; 71+113}={197;184} = 184 (км);
U6 =min{U4 + d46 }=180+166=346 (км);
U7 = min{ U4 + d46;U5 + d57 }={180+107; 184+101}={287;285} =285 (км);
U8 =min{U7 + d78; U6 + d68}= min{285+110; 346+119}= min{395;465 }= 395 (км);
U9 =min{U6 + d69; U8 + d89}=min{346+231; 395+160}= min{577;555}=555 (км).
Маршрут: 1 – 3 – 5 – 7 – 8 – 9
Минимальное расстояние: 555 км.
3. Харьков – Феодосия.
Таблица 2.3.3. – матрица расстояний для маршрута Харьков – Феодосия.
Исходный пункт | Пункты назначения | |||||||
U1 = 0
U2 = min{U1 + d12} = 0 + 122 = 122 (км);
U3 = min{U1 + d13; U2 + d23 } = {0+202;122+208}={202;330}=202(км);
U4 = min{U2 + d24} = 122+158=280 (км);
U5 = min{U3 + d35; U4 + d45} = {202+147; 280+185}={349;465} = 349 (км);
U6 =min{ U5 + d56; U4 + d46}= min{349+40; 280+168}= min{389; 448}=389 (км);
U7 = min{ U6 + d67;U5 + d57 }= min{389+65; 349+71 }= min{454; 420}=420 (км);
U8 =min{U7 + d78}= 420+293=713 (км).
Маршрут: 1 – 3 – 5 – 7 – 8
Минимальное расстояние: 713 км.
3. Геническ – Феодосия.
Таблица 2.3.4. – матрица расстояний для маршрута Геническ – Феодосия.
Исходный пункт | Пункты назначения | |||||||
U1 = 0
U2 = min{U1 + d12} = 0 + 75= 75 (км);
U3 = min {U2 + d23} = 75 + 95 = 170 (км);
U4 = min {U2 + d24; U3 + d34} = {75+25;170+95}={100;265} = 100 (км);
U5 = min {U3 + d35; U4 + d45} = {170+89;100+90}={259;190} = 190 (км);
U6 = min {U4 + d46} = 100+44 = 144 (км);
U7 = min { U5 + d57;U6 + d67} = {190+36;144+53}={236;197} = 197 (км);
U8 = min { U5 + d58 ;U7 + d78} = min {190+25; 197+12} = min {215;209} = 209 (км);
Маршрут: 1– 2 – 4 – 6 – 7 – 8
2.4. Выводы
В результате применения математических методов удалось рассчитать оптимальные и кратчайшие маршруты доставки нашего груза от выбранных поставщиков в порты отправления:
1. Александрия – Кривой Рог – Баштанка – Калиновка– Посад покровское –Херсон – 320 км.
2. Калиновка – Немиров – Чичельник – Кривое Озеро–Вознесенск–Херсон – 555 км.
3.Харьков– Новомосковск – Васильевка – Мелитополь– Феодосия -713 км.
4. Геническ –Джанкой– Азовское –Советский– Владиславовка –Феодосия - 209 км.