Планування постачань торговій фірмі з використанням імітації і генетичного алгоритму

В.В. Ємельянов П.А. Захаров

Планування постачань товарів на склад торгової фірми є однією з основних завдань організації матеріальних та інформаційних потоків у розгалуженій мережі постачальників товарів і замовників [1]. Переслідувана мета - забезпечення необхідного рівня обслуговування безлічі замовників, а також отримання максимальної віддачі коштів від вкладеного капіталу. Рішення поставленої задачі ускладнюється стохастичним характером процесу в системі (зміна попиту, недопоставки товарів на склад і т.п.). У випадку багато-номенклатурних запасу на складі завдання планування поставок перетворюється на багатопараметричної оптимізаційних задач великої розмірності. Складність процесів в розглянутій системі робить проблематичним отримання її математичного опису, адекватного реальності. Це призводить до необхідності використання імітаційного моделювання (ІМ). Розмірність оптимізаційної завдання планування вимагає застосування ефективних методів пошуку рішень.

Для побудови подібних систем бажано мати єдині засоби для розробки імітаційних моделей і реалізації пошукових процедур. В якості такого засобу може бути використаний мова РДО, що дозволяє створювати інтелектуальні системи моделювання і управління [2, 3], а також гібридні системи, що містять у своєму складі імітаційні моделі, моделі дослідження операцій, експертні системи та інші типи моделей та систем [4, 5].

Склад системи планування

Система планування поставок включає в себе (рис.1):

ІМ, призначену для генерації варіантів планів та оцінки їх ефективності;

Блок оптимізації, що забезпечує вибір оптимальних значень керуючих змінних, що передаються в ІМ для складання ефективних планів поставок.

Вимоги до планів поставок

Торгова фірма займається продажем гомеопатичних товарів. На складі фірми зберігаються товари N найменувань, для кожного з яких визначені специфічні умови і терміни зберігання. Товари на склад постачаються одним виробником, для цього він використовує власні транспортні засоби.

Фірма має чотири каналу реалізації товарів (чотири типи клієнтів): великі оптовики, магазини, дилери (по регіонах), представництва фірми. Канали розрізняються споживаними обсягами товарів, їх номенклатури, а також частотою звернень на торговельну фірму з приводу отримання товарів.

Зазвичай замовлення від клієнта містить товари декількох найменувань, але незалежність попиту на різні товари дозволяє розглядати це замовлення як кілька замовлень, що розрізняються найменуваннями товарів.

Дана фірма діє за принципом системи управління запасом з постійним обсягом поставок від виробника по кожному найменуванню товару [1]. Це означає, що після того, як фірма відвантажить всі замовлені товари (які можуть бути відвантажені) клієнтам на даний день, проводиться аналіз поточного стану складу. Перевіряється запас товару даного найменування. Якщо він знизився до певного рівня, що зветься критичним (або точкою замовлення), то робиться заявка виробнику на постачання заданого обсягу товару даного найменування.

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

В результаті рішення завдання планування необхідно отримувати квартальні, місячні і потижневий плани поставок, які мінімізують сумарні втрати від зберігання, неможливості відвантаження товарів клієнтам із-за відсутності товарів на складі і від оплати поставок (організаційні та транспортні витрати).

Імітаційна модель торговельної фірми

ІМ використовується для варіанта складання плану при заданих значеннях точок замовлення і розрахунку для отриманого варіанту величини втрат (W). Об'єктом моделювання є робота торгової фірми з управління поставками, запасами і обслуговуванням замовлень клієнтів. Вихідними даними для системи планування служать статистичні дані про обсяги попиту, про заявки і постачання, що зберігаються в інформаційній базі фірми.

Елементи торгової фірми, необхідні для вирішення задачі планування представляються у РДО-метод як ресурси [3, 6]. Ресурси, що володіють ідентичними властивостями, описуються однаковими параметрами і групуються в типи ресурсів. У ІМ використані наступні основні типи ресурсів:

ТПотері - в ресурсі, даного типу зберігається поточне значення втрат за статтями (критерій W);

ТСклад - ресурси, представляють стан складу по кожному найменуванню товару. Їх параметри це - найменування товару, інформація замовлено чи товар даного найменування у виробника, час (день) наступної поставки, запас товару даного найменування на складі;

ТЗаказ - ресурси, представляють замовлення від клієнтів і містять інформацію про канал реалізації, від якого прийшов замовлення, найменування товару, замовлене кількості, термін відвантаження товарів на замовлення, часу приходу товару, ступеня виконання замовлення на поточний момент;

ТПоставка - ресурси, представляють заявки фірми виробника на поставку товарів та отримані поставки. Вони мають такі параметри, як найменування товару, на який замовлена або прийшла поставка, стан постачання, день, на який замовлена постачання, замовлене або поставлене (можлива недопоставка) кількість товару;

ТПлан - в ресурсі даного типу фіксуються зроблені заявки на поставки по всіх найменувань товарів. Аналізуючи зміни цього ресурсу в часі можна скласти квартальний план поставок (open-list), а також плани поставок на місяці, розбиті по тижнях.

Процеси в розглянутій системі описуються в термінах РДО-методу за допомогою модифікованих продукційних правил [3, 6]. У ІМ описані наступні можливі дії, протікають на фірмі:

Надходження замовлень від клієнтів в систему - генеруються на основі статистичної інформації;

Прийняття рішень про відвантаження товарів клієнтам. Дані дії моделюють відвантаження товарів за замовленнями, термін відвантаження яких менше або дорівнює поточного дня (якщо на складі досить товару даного найменування, при цьому в першу чергу обслуговуються замовлення з найменшим строком відвантаження, що обумовлено необхідністю зниження втрат від неможливості відвантаження товару в строк), при відвантаженні зменшується запас даного найменування товару на складі;

Прийняття рішень про заявках на поставку товарів: якщо кількість товару будь-якого найменування на складі знизилося до (або нижче) критичного рівня і для цього товару немає замовлених, але не отриманих поставок, то складається заявка на поставку даного товару, час приходу поставки задається очікуваним днем приходу, кількість, замовляються по даному найменуванню товару - величина постійна (система з постійним обсягом замовлення). Потім перевіряються запаси товарів всіх інших найменувань на предмет досягнення предкрітіческого рівня, і якщо такі є, то створюються заявки, параметри яких задаються за тим же принципом, що і для товару, рівень запасу якого знизився до критичного рівня, факт заявки на поставку фіксується у відповідних ресурсах типу ТСклад і типу ТПоставка;

Прихід поставок від виробника товарів. Якщо в системі є поставки, у яких призначений день приходу дорівнює поточного дня, то обчислюється значення кількості доставленого товару даного найменування з урахуванням статистичної інформації про недопоставки. Далі товар надходить на склад фірми, при цьому змінюються значення параметрів ресурсів типу ТСклад, відповідних товарах того найменування, на який прийшла поставка і знімається відмітка про наявність заявлених поставок. Ресурс типу ТПоставка знищується.

ІМ також здійснює розрахунок критерію, що включає, як вже зазначалося вище, такі складові:

Втрати від зберігання, які обчислюються щодня, коли відвантажені товари за всіма замовленнями на поточний день, з урахуванням денний вартості зберігання одиниці товару;

Втрати від оплати виробнику поставок, які обчислюються при замовленні поставок з урахуванням обсягу упаковки, обсягу вантажівки, вартості пробігу вантажівки і організаційних витрат на постачання (так як товари - гомеопатичні препарати, вага одиниці товару не накладає суттєвих обмежень на зберігання і транспортування, як обсяг упаковки);

Втрати від неможливості відвантаження замовлень клієнтам в строк - обчислюються кожен день для тих замовлень, які не відвантажені, і у яких термін відвантаження менше поточного дня, з урахуванням неустойки за затримку відвантаження замовленої одиниці даного товару протягом одного дня.

Моделювання здійснюється протягом кварталу. Керуючою інформацією для прийняття рішень про заявки на поставки в ІМ, як і в реальному системі є точки замовлень (критичні - Pi і предкрітіческіе - Pri рівні запасів товарів, де i - номер товару). Від вибору точок замовлень залежать одержувані в результаті моделювання складові втрат, і відповідно критерій оптимізації планів:

, ,

де N - кількість найменувань товарів.

оптимізаційна процедура

Нехай задані допустимі діапазони варіювання точок замовлень DPi - для критичних і DPri - Для предкрітіческіх рівнів замовлень.

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

; ,

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

Для використання ПГА необхідно кодування значень точок замовлень у двійкову форму. Спосіб кодування представлений на рис. 2. Особина являє собою бітову рядок-хромосому довжиною 350 біт. Гени у цьому рядку мають довжину в 7 біт і являють собою закодовані значення точок замовлень. Вибір довжини гена рівний 7 біт обумовлений тим, що гени в РДО представляються у вигляді цілочисельних параметрів типу Особи ресурсів. Ціле число в РДО представляється у вигляді двох байтів. З них один біт - знаковий. Із останніх п'ятнадцяти біт чотирнадцять використовуються для представлення точок замовлень.

Кодування
Відтворення

Схрещування

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

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

Так як сім'ю битами може бути представлено число від 0 до 127, необхідний перерахунок діапазонів критичних - DPi і предкрітіческіх рівнів - DPri в D діапазон від 0 до 127. Цей перерахунок здійснюється за формулами:

, ,

де i - номер товару, G2i-1 і G2i - представлення у вигляді десяткових чисел закодованих в семи бітах значень точок замовлень.

Маючи ці формули для будь-якої особи можливий зворотний перерахунок з генів особи в критичні і предкрітіческіе рівні запасів для кожного найменування товарів.

оптимізується величиною є функція придатності (ФП), що розраховується для особин. Використовувана нами реалізація ПГА з [9], знаходить особина з максимальною ФП, тому необхідно вибрати таку ФП, яка зростає зі зменшенням значення критерію W. Її вигляд визначено в результаті моделювання роботи фірми з типовими значеннями річних витрат на зберігання одиниці товару, неустойки за затримку відвантаження клієнтам одиниці товару кожного найменування на один день, обсягів упаковки, віднесених до одиниці товару, обсягу вантажівки, вартості поїздки однієї вантажівки і організаційних витрат на постачання товарів. При цьому було з'ясовано, що в сумарних втрати завжди присутня така складова, як втрати від зберігання. Зміна цієї складовою для різних комбінацій крапок замовлень невелике через невисокі значень річних витрат на зберігання. Тому як ФП була обрана показова функція, яка швидко зростає із зростанням показника ступеня:

, (*)

де H - функція придатності, Wmax - максимально можливе значення втрат, яке вибрано на підставі результатів моделювання з перевищенням максимальної отриманої величини сумарних втрат на два порядки. Якщо для будь-якої особи значення сумарних втрат перевищить Wmax, у цієї особи буде дуже мале значення функції придатності.

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

Початкова популяція генерується випадковим чином, при цьому створюються особи зі значеннями генів від 0 до 127. Число генеруються особин одно розміром покоління.

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

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

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

Експерименти проводилися на різних за напруженості (середньодобовий попит по кожному найменуванню товару) портфелях замовлень від клієнтів. Так як з-за великого числа характеристик і їх комбінацій важко привести інтегральну характеристику, однозначно що характеризує цей портфель, були проведені експерименти для трьох варіантів портфелів. Ці портфелі розрізнялися средни?? кількістю товару в замовленні по кожному найменуванню товару і каналу, а також інтервалами часу між парафіями замовлень по кожному з каналів.

Рис. 3. Інтервали між парафіями замовлень

Рис.4.

Значення цих характеристик портфелів замовлень наведено на рис. 3, 4. При цьому введена наступна нумерація каналів: 1 - канал великих оптовиків, 2 - канал магазинів, 3 - канал дилерів, 4 - канал представництв фірми.

Значення попиту за час доставки для всіх найменувань товарів і різних портфелів визначалися на основі згенерованих портфелів (середньодобовий попит, помножений на час доставки). Цей попит характеризує споживання товару з моменту видачі на нього заявки виробнику до його отримання на склад.

Для порівняння, на ІМ був змодельований випадок роботи фірми, коли значення точок замовлення призначалися евристичним шляхом. Вони були обрані таким чином:

критичні рівні бралися в середньому з дворазовим перевищенням величини середньодобового попиту помноженої на час доставки;

предкрітіческіе рівні бралися, виходячи з ймовірності приходу замовлення на товар даного найменування.

Оцінка сумарних втрат для цього випадку і для кожного з портфелів проводилася шляхом прогону моделі на інтервалі часу рівному кварталу з даним портфелем замовлень і даними точками замовлень.

Діапазони варіювання точок замовлень були обрані таким чином:

для критичних рівнів - В середньому з п'ятикратним перевищенням середньодобового попиту, помноженим на час доставки;

для предкрітіческіх рівнів діапазони були вибрані однаковими і рівними максимального значення предкрітіческіх рівнів для випадку вибору їх експертом - 400%.

Оцінка сумарних втрат може бути отримана на основі моделювання роботи фірми на кварталі для кращої по всіх поколінням особи. Оптимізація за допомогою ПГА проводилася для 20 особин в поколінні, 20 поколінь, імовірності схрещування - 0.7 і ймовірності мутації -- 0.06.

Рис. 5. Зміна значення ФП за їхніми для портфеля № 1

Результати експериментів з використанням ПГА представлені на рис.5. Тут наведено зміна функції придатності за поколінням. За результатами експериментів (рис. 5) можна відзначити, що зростання середнього значення функції придатності за популяціям (поколінням) (від 0,220357 * 103 до 0,388829 * 103 - для першого портфеля, від 0,132561 * 103 до 0,334439 * 103 - для другий портфеля, від 0,00155367 * 103 до 0,0135357 * 103 -- для третього портфеля) демонструє працездатність алгоритму, а максимальне значення ФП в перерахунку на критерій W дає стійку (в середньому близько 60%) зниження втрат у порівнянні з випадком призначення точок замовлення на основі середнього попиту за час доставки (табл. 2).

Висновок

Результати проведених експериментів показали ефективність комплексного застосування ІМ і ПГА до вирішення складних оптимізаційних задач планування поставок товарів на багато-номенклатурних склад торгової фірми, проте необхідні подальші дослідження, щоб вибрати параметрів ПГА, що забезпечують кращу збіжність, а, отже, і ефективність.

Підтверджена можливість розробки гібридних систем, комплексно використовують ІМ і оптимізаційних процедур на основі єдиного інструментального засобу - мови РДО, що говорить про його універсальності і гнучкості.

Список літератури

Ballow R.H. Product Storage and Warehousing// Basic Business Logistics. Transportation, Materials, Management, Physical Distribution/2-d edition. -- NY, Prentice-Hall International Edition, 1987. P. 192 - 272.

Емельянов В.В., Ясиновський С.І. Продукційні імітатор виробничих систем та процесів// Вісник машинобудування, 1992, № 5. С. 41 - 45.

Емельянов В.В., Ясиновський С.І. РДО - продукційні мову імітаційного моделювання складних дискретних систем: Навчальний посібник з курсів "Моделювання технологічних і виробничих процесів ". - М.: Изд-во МГТУ, 1995. - 91 с.

Емельянов В.В., Ясиновський С.І. Гібридна система для планування виробництва на основі генетичних алгоритмів, методів імітації та експертних систем// Известия ТРТУ, 1996, № 3. С. 4 - 9.

Reane F., Artiba A., Elmaghraby S.E. Sequencing on hybrid two stages flowshop to minimize makespan// ICOQM's proceedings Jaipur, II, 1996. P.572-579.

Emelyanov V.V., Yasinovsky S.I. An AI-based object-oriented tool for discrete manufacturing systems simulation// Journal of Intelligent Manufacturing, Vol.8, Num. 1, February 1997. P.49-59.

Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. - Addison Wesley Publishing Company, Inc., 1989. - 386 pp.

Holland J.H. Adaptive algorithms for discovering and using general patterns in growing knowledge-bases// Int. Journ. of Policy Analysis and Information Systems, 1980, P. 217 - 240.

Ємельянов В.В., Крючков М.Ю., Штаутмайстер Т. Динамічний оптимальний розкрій матеріалу з використанням генетичного алгоритму// Вісник МГТУ, сер.: Приладобудування, 1996, № 1, С. 78 - 86.