Реферат: Планирование поставок торговой фирме с использованием имитации и генетического алгоритма

, ,

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

Оптимизационная процедура

Пусть заданы допустимые диапазоны варьирования точек заказов D_Pi - для критических и D_Pri - для предкритических уровней заказов.

Необходимо найти такую комбинацию значений критических и предкритических уровней, чтобы значение критерия W было минимальным:

; ,

Таким образом мы имеем комбинаторную задачу большой размерности, даже для небольшого числа товаров N. Для ее решения предлагается использовать простейший генетический алгоритм (ПГА) [7, 8]. Применение ПГА для решения подобных оптимизационных задач на языке РДО дано в [9], поэтому здесь мы рассмотрим только особенности реализации данного алгоритма.

Для использования ПГА необходимо кодирование значений точек заказов в двоичную форму. Способ кодирования представлен на рис. 2. Особь представляет собой битовую строку-хромосому длиной 350 бит. Гены в этой строке имеют длину по 7 бит и представляют собой закодированные значения точек заказов. Выбор длины гена равной 7 бит обусловлен тем, что гены в РДО представляются в виде целочисленных параметров типа ресурсов Особи. Целое число в РДО представляется в виде двух байтов. Из них один бит - знаковый. Из оставшихся пятнадцати бит четырнадцать используются для представления точек заказов.

Кодирование
Воспроизведение

Скрещивание

Мутация
Рис. 2. Работа ПГА

Таким образом в одном параметре типа ресурсов Особи закодированы два гена - две точки заказов: критический и предкритический уровни для товара одного наименования. Для представления точек заказов в случае двадцати пяти наименований товаров используются 25 подобных параметров ресурса.

Так как семью битами может быть представлено число от 0 до 127, необходим пересчет диапазонов критических - D_Pi и предкритических уровней - D_Pri в диапазон D от 0 до 127. Этот пересчет осуществляется по формулам:

, ,

где i - номер товара, G_2i-1 и G_2i - представления в виде десятичных чисел закодированных в семи битах значений точек заказов.

Имея эти формулы для любой особи возможен обратный пересчет из генов особи в критические и предкритические уровни запасов для каждого наименования товаров.

Оптимизируемой величиной является функция пригодности (ФП), рассчитываемая для особей. Используемая нами реализация ПГА из [9], находит особь с максимальной ФП, поэтому необходимо выбрать такую ФП, которая растет с уменьшением значения критерия W. Ее вид определен в результате моделирования работы фирмы с типовыми значениями годовых затрат на хранение единицы товара, неустойках за задержку отгрузки клиентам единицы товара каждого наименования на один день, объемов упаковки, отнесенных к единице товара, объема грузовика, стоимости поездки одного грузовика и организационных затрат на поставку товаров. При этом было выяснено, что в суммарных потерях всегда присутствует такая составляющая, как потери от хранения. Изменение этой составляющей для различных комбинаций точек заказов невелико из-за невысоких значений годовых затрат на хранение. Поэтому в качестве ФП была выбрана показательная функция, которая быстро растет с ростом показателя степени:

, (*)

где H - функция пригодности, W_max - максимально возможное значение потерь, которое выбрано на основании результатов моделирования с превышением максимальной полученной величины суммарных потерь на два порядка. Если для какой-либо особи значение суммарных потерь превысит W_max , у этой особи будет очень малое значение функции пригодности.

Основными параметрами генетического алгоритма являются: количество особей в поколении, число поколений, вероятность скрещивания, вероятность мутации. Значения этих параметров были взяты из результатов исследований [9].

Исходная популяция генерируется случайным образом, при этом создаются особи со значениями генов от 0 до 127. Число генерируемых особей равно размеру поколения.

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

Результатом решения оптимизационной задачи является лучшая особь по всем поколениям. Значения точек заказов, которые будут использоваться в торговой фирме при принятии решений о заявках на поставки в процессе работы на квартале осуществляются путем расшифровки лучшей особи. Далее определяем планы поставок, взяв значения критических и предкритических уровней из лучшей особи, как заказанные поставки в течение периода моделирования - квартала.

Результаты работы системы планирования поставок

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

Рис. 3. Интервалы между приходами заказов