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

Если f (x) обозначает стоимость  решения x, то f (x_t+1) в метаэвристиках не обязательно меньше f (x_t) [15]. Это является ключевым отличием метаэвристик от классических эвристик, применяемых для решения ЗМТ. В каждом случае такая возможность требует наличия дополнительного механизма защиты от возможного зацикливания процесса поиска.

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

2.  Генетический алгоритм

Генетический  алгоритм (genetic algorithm) – методика решения некоторых задач путём имитации процессов, наблюдаемых в ходе эволюции естественной природы. Впервые парадигма генетического алгоритма была предложена в [58], но понадобилось ещё почти десять лет, чтобы на неё обратили внимание в широких научных и исследовательских кругах. В чистом виде генетический алгоритм _ это общая методика решения задач, для реализации которой требуется относительно небольшое количество информации о предметной области. Как следствие этот подход может быть использован для достаточно большого числа плохо структурированных задач, где специализированные методы не показывают удачных результатов [19].

В своей работе генетический алгоритм пытается развивать популяцию битовых строк (bitstrings) или “хромосом”, где каждая хромосома кодирует некоторое решение задачи в некоторой её конкретной постановке. Такая эволюция реализуется путём применения нескольких операторов, имитирующих феномены живой природы (воспроизведение, видоизменение и. т. д.). Ниже приводится общее описание генетического алгоритма, а затем будет описано, как применить подобную стратегию к ЗМТ.

1.   Основной вид генетического алгоритма

Опишем основную схему  работы генетического алгоритма. Он начинает выполнение с некоторой начальной популяции хромосом X¹ = , полученной при помощи датчика случайных чисел. На каждой итерации             t = 1, . . ., T выполняются k раз шаги с 1 по 3, приведённые ниже (k 6 N/2), затем выполняется шаг 4.

1. Выбираем две родительские хромосомы из X^t
2. Порождаем два потомка на основе двух родительских хромосом при помощи оператора скрещивания (crossover operator).
3. Выполняем операцию мутации для каждого потомка (с малой вероятностью).
4. Создаём X^t+1 из X^t путём удаления 2k наихудших решений в X^t и замены их 2k новых потомков.

В приведённом алгоритме параметр T – количество поколений, и k – количество выборок в поколении. Наилучшее решение, полученное за T поколений, является окончательным результатом работы алгоритма. На шаге 1 выбор родительских хромосом вероятностно склоняется к выбору наилучших вариантов. На шаге 2 потомок генерируется скрещиванием путем сочетания битовых строк, найденных у родителей. Каждый потомок может быть затем немного модифицирован на шаге 3 путём изменения значения битов в битовой строке с малой вероятностью для каждой битовой позиции. Ожидается, что первоначальное случайно построенное множество будет улучшено в ходе описанного процесса. Такого вывода придерживаются некоторые теоретические исследования [18, 16].

2.   Применение генетического алгоритма для задач упорядочивания

Классический подход генетического  алгоритма, представленный ранее, не подходит для задач упорядочивания (sequencing problems), к которым относятся ЗК и ЗМТ. Прежде всего, для таких задач битовое представление решения не является естественным. Например, его можно заменить представлением путём использования цепочек чисел, где каждое число обозначает некоторую вершину. Положение каждого числа в строке представляет положение вершины в маршруте, предполагая, что последняя вершина замкнута с первой. Далее, должны быть разработаны новые специальные операторы скрещивания и мутации для получения потомков, которые учитывали бы порядок элементов.

Прямое применение классического  алгоритма приводит и к другим подобным проблемам. Известны предложения  специализированных вариантов операторов скрещивания и мутации для получения цепочек потомков на основе родительских решений [22]. Одно из них – предложение оператора “упорядоченное скрещивание” [21]. Сначала случайно выбираются две вершины для вырезания, и подстрока, находящаяся между ними, приписывается потомку. Оставшиеся позиции заполняются вершинами, начиная со второй выбранной, в таком порядке, как они встречаются во втором родительском решении, соблюдая циклическую замкнутость маршрута и отслеживая повторения. Второй потомок может быть получен тем же способом при помощи обмена роли родительских решений. В этом алгоритме потомок обычно наследует относительный порядок вершин от родительских строк. Другие операторы стараются сохранять порядок вершин или порядок дуг родительских решений [17, 30].

3. Применение алгоритма для решения ЗМТ

Литература по разработке алгоритмов для решения ЗМТ на основе генетического алгоритма  довольно скудна в отличие от его  применения для решения ЗК или  от более сложных вариантов ЗМТ, где учитываются временные окна или есть ограничения предшествования [14, 24, 23, 28, 27, 29, 22]. Отставание по сравнению с ЗК объясняется тем, что ЗК_ это хорошо изученная каноническая комбинаторная задача, хорошо подходящая для исследования пробного применения новых идей вообще и генетического алгоритма в частности, а сложные ограничения тяжело обрабатывать общими алгоритмами. Генетический алгоритм хорошо подошёл для случаев со сложными ограничениями, т. к. он требует относительно небольшое количество информации о природе самой задачи. В настоящий момент можно говорить, что генетический алгоритм имеет хороший потенциал для создания быстрых методов поиска решений ЗМТ в сочетании с обработкой сложных видов ограничений. Это подтверждают существующие предложенные методы применения генетического алгоритма для решения ЗМТ в окнах времени. Выполнена работа в области решения ЗМТ с ограничениями по грузоподъёмности, где уделялось особое внимание влиянию различных параметров на качество получаемых результатов.  

В ЗМТ решение содержит несколько маршрутов (в отличии от ЗК), поэтому представления цепочек для генетического алгоритма расширено и депо включается в них многократно. Каждое включение депо служит разделителем между двумя соседними маршрутами.

Применяемый классический оператор скрещивания, называемый PMX оператор мутации RAR, были адаптированы для использования в новых условиях [17]. На каждой итерации они применяются до тех пор, пока не будет получено требуемое количество решений, удовлетворяющих ограничениям, а остальные потомки отбрасываются. Автор применял специальный оператор локального спуска (local descent operator), основанный на четырёх различных типов изменения порядка выполняемых шагов, и вызывал его только для наилучших решений в текущей популяции. В работе показано, что применение оператора локального спуска даёт заметное улучшение производительности алгоритма. В целом, наилучшие решения, получаемые при помощи генетического алгоритма, моделируемого отжига и поиска с исключениями, сравнимы по качеству. Генетический алгоритм требует несколько больше процессорного времени для работы, чем два других подхода. Пока не приведено сравнительных результатов качества работы генетического алгоритма относительно алгоритма на основе муравьиных колоний и нейронных сетей.

Интересный вариант генетического  алгоритма приведён в [25, 26]. Он может быть использован в задачах с ограничениями на окна времени. Интересная особенность этого алгоритма в том, что в нём используется классический подход с разрезанием общего маршрута, полученным после решения ЗК на общем множестве вершин, что позволяет использовать традиционную схему представления решения без разделителей в виде многократного включения депо. Для разделения на маршруты каждого экипажа применяется процедура заметания, начиная работу с первой вершины, находящейся на первом месте в генетической цепочке. Переход к следующему маршруту происходит, когда превышается ограничение на длину маршрута или грузоподъёмности. Таким образом генетическая цепочка может быть всегда преобразована в допустимое решение ЗМТ.

Реализация алгоритма, предложенная в [26], использует оператор скрещивания OX и оператор мутации, который основан на обмене местами двух случайно выбранных вершин. Для повышения качества работы этот оператор в дальнейшем был заменён на использование алгоритма 2-опт, запускаемый для каждой вершины с вероятностью 0, 15.

В [13] предложена схема кодирования, основанная на случайных ключах.

В такой схеме каждый элемент задачи связывается со случайно сгенерированным ключом. Преобразование таких ключей в решение задачи можно выполнить при помощи операции сортировки. Непосредственно в ЗМТ каждая вершина–клиент связывается со случайным целым числом, обозначающим транспортное средство, которое будет обслуживать эту вершину, плюс число с плавающей точкой в интервале (0, 1). При сортировке этих чисел можно получить последовательности вершин для каждого маршрута. Подобное применение случайных чисел для решения ЗМТ приводится скорее для иллюстрации такой возможности, но оно не исследовалось достаточно детально.

3.  Задача построения планов доставки для розничной клиентской сети

Специфика ЗМТ на любом графе состоит в том, что на суммарный пройденный всем используемым транспортом путь, на время выполнения всех заказов влияют как качество разбиения множества клиентов по маршрутам, так и качество найденных циклов объезда клиентов транспортными единицами. Эта специфика особенно важна при моделировании сетей с большими колебаниями пропускной способности, что характерно для современных городов. В данной работе учитывается указанная специфика ЗМТ. Предлагаемая методика решения задачи маршрутизации состоит из нескольких этапов: преобразование исходного графа городской транспортной сети (ГДС) к графу определенного вида применением специально модифицированного алгоритма Дейкстры; построение маршрутов при помощи разработанной метаэвристики, реализованной на основе генетического алгоритма (ГА). В составе ГА предлагается комплекс мер, позволяющий эффективно находить схемы движения транспорта, минимизирующие стоимость доставки. Выбор метода обоснован тем, что задача маршрутизации является NP сложной, т. е. размер пространства поиска имеет экспоненциальную зависимость от количества переменных. В предложенном расширении она имеет большое и сложное пространство решений даже при сравнительно небольшом количестве клиентов. Существует ряд источников, где на тестах показана эффективность применения на графовых задачах метаэвристик, особенно ГА. С ростом размерности задачи качество получаемых в ГА решений, по сравнению с другими методами, растет.

В качестве модели ГДС использован динамический граф, который имитирует изменения пропускной способности улиц, существование участков с односторонним движением, постоянно и периодически запрещенные повороты, увеличение времени преодоления маршрута при использовании поворотов большой крутизны, связанное с необходимостью тормозить и снова набирать скорость. В условиях динамического графа целевым критерием принят баланс протяженности и продолжительности искомых маршрутов. Представим городскую дорожную сеть в виде ориентированного связанного графа G=<D,U>, где D={1,2...n_D} – множество вершин графа мощностью n D, U – множество дуг, соединяющих вершины. Узлами графа считаются как различные точки реализации продукции, например магазины, столовые, больницы или детские сады, так и простые перекрестки автомобильных дорог. Выделим целевое подмножество вершин P_l={1,2...n_l}, P_l⊂D, которое составляют только обслуживаемые клиенты. На рисунке 3.1 множество вершин D – все вершины графа, P_l – черные вершины, u_i,j ∈U, i,j∈D – дуги между любыми соседними вершинами, причем u_i,j≠u_j,i . В левом верхнем углу обозначен склад готовой продукции. Предприятие выпускает продукцию циклически. Поэтому все множество клиентов P_l, при поступлении заявок, разносится по циклам производства. Тогда нашей задачей является планирование доставки для клиентов некоторого цикла производства. В качестве подмножества клиентов некоторого производственного цикла примем P, P⊂P_l. Тогда n – количество клиентов, соответствующее некоторому циклу, которое необходимо обслужить.

Рисунок 2.1. – Граф G – модель городской дорожной сети

Пропускная способность  улиц является функцией времени и почти циклически изменяется каждые сутки. Поэтому весь суточный диапазон условно разобьем на T отрезков, внутри которых показатель постоянен. Тогда каждая дуга u_i,j∈U графа G, соединяющая вершины i,j∈D и представляющая собой некоторую часть улицы, обладает протяженностью l(u_i,j), км, и средней скоростью w(u_i,j ,τ), τ=1...T, км/ч, в момент времени τ, где τ – дискретное время, определяющее номер суточного интервала. Номер интервала τ определяется как функция времени τ=τ(t), где t – текущее модельное время. В распоряжении транспортного цеха находится q автомобилей. Каждый автомобиль характеризуется грузоподъемностью – K, кг(м3). Заказ i-го клиента имеет вид: d_i=(d_iv), i∈P, v∈S, где d_iv – объем d товара v, который должен быть доставлен клиенту i, S – множество производимой на заводе продукции. Множество клиентов P требуется разбить по автомобилям так, чтобы суммарный объем заказов подмножества клиентов, назначенных конкретному автомобилю для перевозки, не превышал грузоподъемности этого автомобиля. Обозначим через y∈Y разбиение множества P на непересекающиеся подмножества p₁∪...∪p_k∪...∪p_α так, что p_k∩p_s=q, где α – общее количество рейсов, Y – множество всех допустимых разбиений множества P. Например, на рисунке 2.1, p₁={h,f,j,i}, p₂={e}. Тогда загрузка автомобилей для перевозки товаров назначенным заказчикам определяется неравенством

                                                      (2.1)

 Для каждого используемого автомобиля необходимо вычислить оптимальный маршрут объезда вершин назначенного подмножества p_k разбиения y. Обозначим перестановкой z_k=(i₁...i_m...i_gk–1,i_gk) альтернативный порядок объезда автомобилем k вершин i_m∈p_k, m=1...g_k из множества всех возможных перестановок Z_k. Здесь i₁– отправная вершина, обозначающая начало маршрута, т. е. склад готовой продукции; g_k–1=|p_k| – количество целевых вершин на маршруте. На рис. 2.1 z₁=(i₁,h,i,j,f,i₆). Завершение объезда происходит в исходной вершине, т. е. i_gk=i₁. Маршруты должны охватывать вершины множеств p_k в порядке, обеспечивающем минимальную суммарную стоимость доставки. Основными факторами, определяющими ее стоимость, являются продолжительность и протяженность маршрутов. Поэтому в качестве целевого критерия рассматривается их линейная комбинация по всем транспортным единицам, что ведет к оптимальному использованию транспортных ресурсов и, следовательно, к оптимизации затрат. Целевая функция имеет вид:

,                 (2.2)