РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОЙ ТРАНСПОРТИРОВКИ ТОВАРА Ибрагимов Нурлан

ЦЕЛЬ И АКТУАЛЬНОСТЬ ПРОЕКТА Цель: кратчайшего пути максимальная прибыль Минимальное время Актуальность: Любой предприниматель хочет получить максимальную прибыль с ограниченными ресурсами и при минимальных затратах. Поэтому, эта проблема побудила меня оптимизировать маршрут доставки молока в разных частях города Алматы с ограниченными ресурсами.

МОЛОКО ПИТАТЕЛЬНАЯ ЖИДКОСТЬ, ВЫРАБАТЫВАЕМАЯ МОЛОЧНЫМИ ЖЕЛЕЗАМИ САМОК МЛЕКОПИТАЮЩИХ.

УСЛОВИЯ ЗАДАЧИ. ПАРАМЕТРЫ. Найти оптимальный путь доставки молока в магазины. Старт : Жандосова, 82 Общее количество молока – 150 л Общее время пути : не более 120 минут Общее количество магазинов : 13 Машины : 2 В расчет берутся : Расстояния между магазинами S ij ; Средние скорости на участках дорог между магазинами V ij ; Влияние уклонов дороги на скорость передвижения α ij ; Время простоя автомобилей во время разгрузки товара у магазина p i ; Неравенство расстояний при движении от А до Б и от Б до А : S ij S ji ; Односторонность движения S ij =-1 ( учитывается алгоритмом ).

СПИСОК МАГАЗИНОВ п / п НазваниеКоличество молока, л Время стоянки, мин 1 Адал E 55 3 Фуделла 55 4 Торнадо Magnum Санжар 55 7 Моника 55 8 Арба 55 9 Helios Хороший A-Store (ADK) Алуа Тан 157 ВСЕГО :

РАСПОЛОЖЕНИЕ МАГАЗИНОВ выбранные магазины отклоненные магазины исходный пункт группы магазинов

МАГАЗИНЫ ГРУППЫ 1. МАТРИЦА РАССТОЯНИЙ. Магазины Жандосова, 82 Адал 2-E Фуделла Торнадо Magnum Санжар Моника Жандосова, 82 3,6 км 3,4 км 4 км 4,6 км 5,1 км 5,6 км 4,9 км Адал 3,5 км 1,7 км 2,2 км 1,8 км 3,6 км 2,8 км 1,6 км 2-E4,3 км 1,6 км 1,9 км 1,5 км 1,9 км 2,5 км 1,4 км Фуделла 4,1 км 3,2 км 2,9 км 1,2 км 1,8 км 2,3 км 2,8 км Торнадо 5,5 км 2,9 км 4,3 км 1,6 км 1,5 км 2,1 км 2,6 км Magnum5,8 км 2,2 км 3,4 км 2,3 км 1,9 км 733 м 2,2 км Санжар 5,9 км 3,7 км 3,5 км 2,4 км 2 км 2,3 км 2,3 км Моника 5,2 км 2,9 км 2,7 км 2,9 км 2,6 км 2,9 км 1,6 км

МАГАЗИНЫ ГРУППЫ 2. МАТРИЦА РАССТОЯНИЙ. Магазины Жандосова, 82 Арба Helios Хороший A-Store (ADK) Алуа Тан Жандосова, 82 2,8 км 3,4 км 2,8 км 2,3 км 736 м 794 м Арба 2,9 км 831 м 1,2 км 2,5 км 3,4 км 3,1 км Helios4,1 км 1,5 км 2,4 км 3,8 км 4,7 км 4,3 км Хороший 3,4 км 2,6 км 3,4 км 1,5 км 3 км 3,7 км A-Store (ADK)1,9 км 2,4 км 2,3 км 2,6 км 3,1 км 2,7 км Алуа 677 м 3,2 км 3,7 км 3,4 км 2,5 км 997 м Тан 715 м 3,2 км 4 км 3,5 км 2,6 км 945 м

ПАРАМЕТРЫ ( ПРИМЕР ) Средние скорости движения между магазинами группы 1. Средние уклоны дороги между магазинами группы 1 ( в процентах ).

МЕТОД РЕШЕНИЯ

Поиск в глубину – это рекурсивный алгоритм обхода вершин графа. Данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность дальнейшего продвижения означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения ( один из которых исследован полностью ), ранее посещенный узел ( вершину ). Отсутствие последнего свидетельствует об одной из двух возможных ситуаций : либо все вершины графа уже просмотрены, либо просмотрены все те, что доступны из вершины, взятой в качестве начальной, но не все ( несвязные и ориентированные графы допускают последний вариант ).

//граф var a = [ ]; // количество вершин var n = 5; // время для обхода всех вершин var t = tbackup = 120; //счетчик ……………………….. ………….. for (var i = 0; i < n; i++) isVisited[i] = false; //проверка графа for (var i = 0; i < n; i++) { for (var j = 0; j < n; j++) { console.log(a[i][j] + " "); } console.log(""); } // запись в массив посещений начальная точка isVisited[start] = true; counter = 0; // запуск алгоритма dfs(start, 1); АЛГОРИТМ ПОИСКА Для расчетов был создан скрипт для работы в интернет - браузере на языке JavaScript. Основные использованные переменные : A – граф ; N – количество вершин графа ; T – время, за которое нужно обойти все вершины ; START – вершина с которой начать движение ; Глобальные переменные : isVisited – массив вершин, по которым мы уже прошли ; visitedWays – временный массив в который записываются шаги ; если шаг оказался успешным, т. е. все магазины были посещены за заданное время, он сохраняется для дальнейшего анализа.

НАЙДЕННОЕ РЕШЕНИЕ Группа 1. Затраченное время : 34 минут. 1 Жандосова, 82 – 0 км 2 Адал – 8 км 3 2-E – 13 км 4 Торнадо – 20 км 5 Фуделла – 27 км 6 Magnum – 35 км 7 Санжар – 41 км 8 Моника – 49 км Всего путей найдено : 5040 Группа 2. Затраченное время : 29 минут. 1 Жандосова, 82 – 0 км 2 Арба – 8 км 3 Helios – 13 км 4 Хороший – 20 км 5 A-Store (ADK) – 27 км 6 Алуа – 35 км 7 Тан – 41 км Всего путей найдено : 720

РЕШЕНИЕ ( ГРУППА 1) 1 - Адал E 4 - Фуделла 3 - Торнадо 5 - Magnum 6 - Санжар 7 - Моника

РЕШЕНИЕ ( ГРУППА 2 ) 1 - Арба 2 - Helios 4 - A-Store 3 - Хороший 5 - Алуа 6 - Тан

СПАСИБО ЗА ВНИМАНИЕ !