Логистическое планирование доставки товаров

где l(z_k) и θ(z_k) – протяженность и продолжительность маршрута z_k соответственно, λ – весовой коэффициент. Протяженность l(z_k) маршрута z_k складывается из длин путей u~i_m,i_m+1(τ)∈U~(τ), соединяющих следующие друг за другом вершины i_m, i_m+1∈p_k, m=1...(g_k–1). На рисунке 2.1 u~i_m,i_m+1 (τ)=(i,1,2,3,4,5,j). Путь u~i_m,i_m+1 (τ) является функцией дискретного времени τ, поскольку с течением суток оптимальный маршрут, соединяющий вершины i_m,i_m+1, может существенно меняться, τ=τ(t_im–1), где t_im–1– время отъезда из вершины i_m–1. Подробней алгоритм построения множества U~(τ) описан ниже. Длительность θ(z_k) маршрута z_k определяется следующим образом. Пусть время отъезда из текущей вершины i_m рассчитывается по формуле

             ,        (2.3)

где – момент прибытия в вершину i_m из вершины i_m–1; – время отправления со склада автомобиля k; – интервал времени, необходимый для разгрузки заказа клиента i_m∈p_k, k=1...α. Величина складывается из времени отъезда из предыдущей вершины t_im–1 и времени на преодоление расстояния l(u~i_m,i_m+1(τ)), τ=τ(t_im–1) со средней скоростью w(u~i_m,i_m+1(τ)), τ возвращает номер суточного интервала, соответствующий текущему значению t_im–1.

                 (2.4)

Время разгрузки заказа определяется по формуле

                    (2.5)

где – среднее количество времени для разгрузки 1 ед. продукции. Тогда время маршрута отдельно взятого автомобиля θ(z_k) равно величине , определяющей время возвращения автомобиля k на склад – вершина минус время старта .

    (2.6)

 

 

 

 

 

 

 

 

3. МЕТОД РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА В УСЛОВИЯ ГОРОДСКОЙ ДОРОЖНОЙ СЕТИ

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

1. Упрощение исходного  графа городской дорожной сети

Для решения ЗМТ, в указанной постановке, строим новый граф G~=<Pl,U~(τ)>, Pl⊂D, τ=1...T на основании исходного G, где Pl – множество всех клиентов, U~(τ) – множество путей, соединяющих клиентов оптимальным для суточного интервала образом. Для построения множеств дуг U~(τ), τ=1...T применяем алгоритм Дейкстры, который специально модифицируем для этих целей [8]. В модифицированной форме алгоритм учитывает: протяженность l(u_i,j), u_i,j∈U, i,j∈P_l исходных дуг, среднюю скорость движения w(u_i,j,t) в текущем интервале, запрещенные на момент τ повороты, дороги с односторонним движением, а также проводит штрафование за совершение поворотов большой крутизны. Алгоритм работает за линейное время. Применяя алгоритм n_l (n_l–1)T раз, строим упрощенный граф для каждого τ. В итоге совокупность множеств U~(τ), τ=1...T образует полностью допустимое, оптимально сокращенное пространство поиска, учитывающее специфику ГДС, где в каждый момент времени точно известно, каким маршрутом следует двигаться из одной целевой вершины в другую. Готовый граф G~ можно хранить в отдельной базе данных и проводить пересчет только при изменении списка постоянных клиентов – появлении новых или удалении пассивных на протяжении определенного срока клиентов. Поиск маршрутов. Решение задачи маршрутизации транспортных единиц для обслуживания клиентов реализовано в виде ГА.

2. Архитектура генетического  алгоритма 

Генетический алгоритм представляет собой методику случайного поиска [9, 10]. Метод кодирования решений подбирается под конкретный тип исследуемой задачи и должен обеспечивать адекватное представление любой точки пространства решений. В качестве альтернативного решения рассмотрим последовательность обслуживаемых клиентов, в которой выполняется доставка продукции. Например, первая альтернатива в популяции решений вида:

 

 

 

  ,              (3.1)

…………………………………

           

 

 

говорит о  том, что, если в первый автомобиль можно загрузить только трёх первых клиентов, не нарушая условие (2.1), то его маршрут будет следующим:

0–1–2–5–0; если все оставшиеся клиенты помещаются в следующий автомобиль, его маршрут будет: 0–11–7–4–6–0, где ноль является складом готовой продукции. Для запуска поискового процесса необходимо создать стартовую популяцию решений хромосом. В нашем случае применена смешанная схема инициализации. Часть популяции создана при помощи широко известного метода Ближайшего Соседа (Nearest Neighbour) [11]. При создании оставшихся особей используется генератор случайных чисел, выдающий допустимые последовательности на конечном множестве клиентов P. Подобная схема позволяет существенно улучшить поиск при выраженной кластеризованности клиентов.

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

• Цикл оценки альтернатив, где m – размер популяции.
• Цикл перебора доступного транспорта.
• Установка времени начала выполнения доставки для привязки к конкретному временному интервалу τ.
• Цикл загрузки заказов клиентов j в текущий автомобиль в порядке, определяемом текущей хромосомой.
• Проверка наличия места в автомобиле k для загрузки заказа клиента j.
• Загрузка очередного заказа.

Рисунок 3.1 – Функциональная схема алгоритма оценки

При погрузке заказа корректируется свободное место в автомобиле на соответствующую заказу величину. При этом увеличиваются счетчики пройденного пути и затраченного на дорогу и разгрузку заказа времени на величины соответствующих характеристик дуг u~(τ), соединяющих соседних в решении клиентов (3–4). Также учитываем и дуги, соединяющие первого и последнего клиента со складом. Корректировка текущего времени t по окончании разгрузки приводит к смене τ, если текущее время вышло за границы интервала. Что позволяет выбрать оптимальный маршрут движения к следующему клиенту. Потенциальное количество заказов, которое можно загрузить, зависит от их объема, следовательно, количество вершин в одном автомобиле может варьироваться в широких пределах. Поэтому предложена система представления решений, кодирующая не транспортные единицы со списками обслуживаемых клиентов, а простую их последовательность. Это в сочетании с описанным алгоритмом оценки позволяет эффективно использовать выделенную память, максимально упростив при этом структуру кодируемых решений (3.1), и исключить отдельный блок контроля допустимости получаемых во время эволюции альтернатив. Недопустимые с точки зрения перегруза транспорта решения просто исключаются. С каждой оценкой на альтернативную последовательность клиентов накладываются в строго фиксированном для всей эволюции порядке емкости доступных автомобилей, то есть выполняется строго последовательная динамическая загрузка транспорта клиентами. Поэтому с течением эволюционного процесса лучшими решениями будут те альтернативы, где сравнительно близкие клиенты будут группироваться в соответствии с емкостями автомобилей и в последовательности, обеспечивающей минимум целевой функции (2.2). Сочетание в данном ГА системы представления решений и оценочной процедуры обладает ключевыми для задачи свойствами: в эволюционном процессе происходит параллельный поиск оптимального разбиения вершин по маршрутам и оптимального порядка объезда клиентов внутри каждого подмножества. Здесь использована стратегия отбора родителей по принципу колеса рулетки и стратегия элитизма. Таким образом, исключается потеря хороших решений при применении генетических операторов. При помощи генетических операторов производится создание новых, ранее не присутствовавших в популяции особей. Сканирование поискового пространства осуществляется операторами скрещивания (кроссинговера), мутации, инверсии. Применен частично – соответствующий оператор скрещивания. Выбор продиктован таким условием задачи, что любой клиент может быть обслужен только однажды и одним автомобилем: pk∩ps=q, k≠s,k,s=1...α. То есть потомок должен иметь тот же генный состав, что и исходные особи. Модификации проявляются лишь в порядке следования вершин. Существенно улучшить качество решений позволяет применение жадных мутаций – стратегий локального поиска, модифицирующих исходное решение на основе анализа целевой функции или ее некоторых параметров. Описание методов локального поиска и различных генетических операторов широко представлено в литературе и сети Интернет, например, в [9, 10].

Условия останова поиска:

• алгоритм выполнил заданное количество итераций AbsN;
• на протяжении LocN итераций лучшее решение не изменяется.

3.  Сравнительные результаты и эффективность подхода

Пробные расчеты  на статических тестовых задачах, опубликованных в научной литературе и доступных в сети Интернет, показывают хорошие результаты, сопоставимые с лучшими достижениями, опубликованными в литературе [12]. По многим задачам отклонения достигают меньше 2 %. Стандартных задач на динамических графах не найдено. Следует отметить, что качество решений, в том числе их стабильность, существенным образом зависят от отведенного на поиск времени. Например, для задачи с 200 клиентами при LocN = 200 среднее время поиска составляет 40 с, а разброс результатов может достигать 5...7 % от лучшего найденного алгоритмом решения. При LocN = 2000 среднее время поиска уже равно 7 мин., и разброс составляет 2...3 %. Предложенный выше подход подразумевает такую стратегию поиска, что найденные на динамическом графе маршруты обеспечивают лучшие результаты при их использовании в реальных условиях, по с сравнению с маршрутами, найденными на статическом графе. Предложена следующая методика оценки эффективности поиска на динамическом графе. Пусть P1– решение задачи, найденное на статическом графе, P2 – на динамическом. Качество решения определенное по весам статического графа обозначим через L(P), где P – некоторое решение. Оценка решения P на динамическом графе – H(P). За оценку снизу примем L(P1), поскольку решение найдено в легких дорожных условиях. Очевидно, худшей оценкой является H(P1), т. к. решение P1 не учитывает особенностей динамического графа. Через Δ1=H(P1–L(P1) обозначим погрешность моделирования. Тогда эффективность метода решения определим формулой в предположении, что L(P1)≤H(P2)≤H(P1). Чем ближе Δ2 к единице, тем больше эффект от моделирования на динамическом графе. Расчеты показали, что Δ2≈0,6, т. е. моделирование на динамическом графе позволяет сократить примерно на 60 % ошибку моделирования Δ1, которая составляет 30 % по отношению к H(P1). Причем параметр существенно зависит от степени и структуры загрузки графа, количества и разброса клиентов.

4. ВЫБОР ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ И ПОСТРОЕНИЕ БАЗЫ ДАННЫХ

1. Обоснование выбора используемого программного средства

При разработке приложения были использованы такие технологии: Java, СУБД MySql, а так же GoogleMaps API.

1. Java

Java–технологии имеют много особенностей, отличающие их от других технологий разработки программного обеспечения:

• переносимость (программы, написанные на языке Java, после однократной трансляции в байт-код могут быть исполнены на любой платформе, для которой реализована виртуальная Java-машина; наиболее эффективно возможности реального компьютера может использовать только программа, написанная с использованием «родного» машинного кода);
• безопасность (функционирование программы полностью определяется (и ограничивается) виртуальной Java-машиной; отсутствуют указатели и другие механизмы для непосредственной работы с физической памятью и прочим аппаратным обеспечением компьютера; дополнительные ограничения снижают возможность написания эффективно работающих Java-программ);
• надежность (в языке Java отсутствуют механизмы, потенциально приводящие к ошибкам: арифметика указателей, неявное преобразование типов с потерей точности и т.п.; присутствует строгий контроль типов, обязательный контроль исключительных ситуаций; многие логические ошибки обнаруживаются на этапе компиляции; наличие дополнительных проверок снижает эффективность выполнения Java-программ);
• сборщик мусора (освобождение памяти при работе программы осуществляется автоматически с помощью «сборщика мусора», поэтому программировать с использованием динамически распределяемой памяти проще и надежнее; при интенсивной работе с динамически распределяемой памятью возможны ошибки из-за того, что «сборщик мусора» не успел освободить неиспользуемые области памяти);
• стандартные библиотеки (многие задачи, встречающиеся при разработке программного обеспечения, уже решены в рамках стандартных библиотек; использование объектно-ориентированного подхода позволяет легко использовать готовые объекты в своих программах; для запуска приложения необходима установка JRE, содержащего полный набор библиотек, даже если все они не используются в приложении; отсутствие библиотеки необходимой версии может воспрепятствовать запуску приложения);

2. MySql

Основные преимущества MySQL:

• многопоточность, поддержка нескольких одновременных запросов;
• оптимизация связей с присоединением многих данных за один проход;
• записи фиксированной и переменной длины;
• ODBC драйвер;
• гибкая система привилегий и паролей;
• гибкая поддержка форматов чисел, строк переменной длины и меток времени;
• интерфейс с языками C и Perl, PHP;
• быстрая работа, масштабируемость;
• совместимость с ANSI SQL;
• бесплатна в большинстве случаев;
• хорошая поддержка со стороны провайдеров услуг хостинга;
• быстрая поддержка транзакций через механизм InnoDB.

3.   GoogleMaps Api

Существует множество  способов встраивать в собственные  приложения маршруты, сформированные приложением Карты Google. С помощью API матрицы расстояний пользователи найдут кратчайшие по протяженности и времени в пути автомобильные маршруты до конечной точки. С помощью функций просмотра улиц в API Google Карт пользователи смогут изучить место, в которое они направляются.

2. Создание базы данных

В ходе разработки была создана  база данных включающая в себя 3 таблицы (рисунок 4.1):

• таблица base, в которой хранятся данные о депо и машинах, обеспечивающих доставку;
• таблица client, в которой хранятся данные о клиентах и заказах
• таблица rout, в которой хранятся данные расстояния и время от клиента до остальных клиентов.

 

Рисунок 4.1 – Структура базы данных.

Часть данных в таблицы  поступает из формы, в которую  пользователь вводит данные о депо и добавляет клиентов. Такие показатели как расстояние и время мы получаем из GoogleMaps API.

Так же в таблице route есть такие поля как interval и foul – это, на мой взгляд, и есть самая большая сложность всей программы. Задание этих параметров требует консультации специалиста, но в связи с тем что информационные технологии очень быстро развиваются и проникают практически во все сферы нашей деятельности, стоит ожидать, что очень скоро значение этих полей можно будет взять из того же GoogleMaps API.

На рисунке 4.2 представлен  пример добавления в базу данных депо и клиента.

Рисунок 4.2 – пример добавления в БД депо и  клиента

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. ТЕСТОВЫЙ ЗАПУСК ПРИЛОЖЕНИЯ

1. Руководство пользователя

При запуске разработанного программного продукта появляется главная  форма (рисунок 5.1)

Рисунок 5.1 – Форма ввода данных

На этой форме  пользователю необходимо ввести адрес  депо, количество машин в депо, а  также грузоподъемность машин и нажать кнопку «Добавить депо» (предполагается, что все машины имеют одинаковую грузоподъемность). На рисунке 5.2 показан пример задания параметров депо.

Рисунок 5.2 – Пример задания параметров депо

После пользователю нужно ввести адрес каждого клиента, а так же объем заказа каждого из товаров и нажать кнопку «Добавить клиента» (рисунок 5.3).

Рисунок 5.3 – Пример задания параметров клиента