Гуценко Олег Олександрович

Тема: Автоматизована підсистема планування та координації роботи торговельних агентів

Содержание:

1. Цілі та задачі
2. Актуальність роботи
3. Наукова новизна
4. Плановані практичні результати
5. Огляд досліджень і розробок по темі
6. Математичні методи розв'язання задачі
7. Висновок
8. Список літератури

Цілі та задачі

Підприємство займається продажами продукції в торгові точки (ТТ). З цією метою торговий агент (ТА) відвідує ввірені йому ТТ з певною періодичністю. На кожного ТА доводитися 60-100 ТТ. Кожен ТА підпорядковується своєму безпосередньому начальнику - менеджеру з продаж (МП), задача якого - визначити набір ТТ для відвідування протягом тижня. У кожного МП в підпорядкуванні знаходиться 8-15 ТА. Численність ТТ позначимо Tij, численність ТА позначимо Ci. Загальна схема роботи на даний момент виглядає наступним чином:

1. МП складає щоденний розклад відвідання ТА торгових точок в залежності від ряду факторів: періодичність відвідувань ТТ, важливість відвідування в певний день тижня, важливість відвідування в певний час доби і т.п. В один день може бути відвідана обмежена кількість ТТ.
2. Після визначення розкладу для ТА, вже існуюча підсистема визначення оптимального маршруту складає оптимальний обхід ТТ в рамках кожного дня.

ТТ характеризується набором параметрів: Tij{P,Q,t}.

Р – періодичність відвідування ТТ.

Q – важливість відвідування ТТ в певний часовий інтервал.

t – час доби для відвідування ТТ.

Підсистему складання розкладів відвідувань ТТ можна представити у вигляді наступної схеми.

Рисунок 1 — Загальна схема роботи підсистеми

Задача підсистеми - складання оптимального маршрута руху ТА у межах всього робочого періода. Ціль: покращити ефективність підсистеми складання розкладу відвідувань ТТ, зменшити витрату пального, покращити якість обслуговування ТТ.

Актуальність роботи

Вирішення задачі складання розкладів залежить від задачі визначення переліку ТТ за наступними параметрами: час відвідування ТТ - tij , періодичність відвідування ТТ - Pij. Залежно від цих параметрів може змінюватися число відвідувань на кожен день, тому що змінюється довжина прохідного шляху. Отже актуальність задачі полягає у складанні оптимальних наборів ТТ для відвідування в кожен день тижня. Т.ч. МП має скласти набори L{D,T,C}
D – день тижня.
Т – безліч ТТ для відвідування.
С – ТА.
Це дозволить ввести в існуючу систему зворотний зв'язок і підвищити ефективність підсистеми складання розкладу відвідувань ТТ. Після модернізації роботу підсистеми можна представити в наступному вигляді:

Рисунок 2 - Загальна схема роботи підсистеми після модернізації

Т.ч. МП отримає можливість враховувати розклад відвідувань ТТ на етапі формування набору ТТ для відвідування L{D,T,C,K}, де К - коефіцієнт корисної дії (ККД) маршруту.

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

W – кількість робочих днів тижня для ТА.

S - функція визначення довжини оптимального маршруту за обраними ТТ.

Облік можливих маршрутів та їх ефективності на етапі формування набору ТТ дозволить підвищити ККД ТА, врахувати вимоги до відвідування ТТ, що в підсумку дозволить підвищити дохід компанії.
Основним примітним аспектом є зв'язок задачі складання оптимального розкладу в рамках усього періоду з підсистемою знаходження оптимальних шляхів.
На поточний момент існує безліч систем, які дозволяють вирішити подібні задачі, в основному вони орієнтовані на сектор логістики перевезень. Однак більша частина складає оптимальний маршрут лише в рамках частини періоду, наприклад робочого дня. А також не враховує індивідуальні специфіки роботи підприємств, наприклад важливість відвідувань ТТ в певний часовий період доби і т.п. Таким чином, стає очевидною необхідність у подальших розробках і дослідженні в даній галузі наукової діяльності.

Наукова новизна

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

Плановані практичні результати

За допомогою даної системи передбачається отримати засіб для:
– складання оптимального розкладу відвідування торговельних точок;
– регулювання пересування агентів по торгових точках. Облік можливих маршрутів та їх ефективності на етапі формування розкладу дозволить підвищити ККД ТА, врахувати вимоги до відвідування ТТ, що в результаті дозволить підвищити дохід компанії.

Огляд досліджень і розробок по темі

На ринку розробок можна виділити наступні продукти:
– 1С БІТ: НОВА Управління транспортною логістикою ред. 3.0
– АТ–Автотрекер: Автотранспорт 2.0 Продукт «1С БІТ: НОВА Управління транспортною логістикою 3.0» є частиною системи 1С–Підприємство 8.0 і дозволяє контролювати переміщення агентів, супроводжуючи процес документами і керувати поставками продукції в точки розповсюдження. Дану роботу з планування поставок і обходу точок за маршрутним листом проводить логіст диспетчер вручну або за допомогою автоматизованих модулів даних продуктів. Можливості системи управління транспортною логістикою:
– управління адресами доставки;
– управління замовленнями на доставку;
– управління графіками доступності транспорту і роботи водіїв;
– автоматичне і ручне планування маршрутів доставки;
– облік витрат і доходів за рейсом;
– аналіз вантажоперевезень;
– гнучкий, зручний інтерфейс (налагодження відображення без використання конфігуратора);
– проста інтеграція з різними конфігураціями на платформі 8;
– можливість інтеграції з системами GPS моніторингу транспорту.

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

АТ–Автотрекер: Автотранспорт 2.0.

Функціонал системи охоплює діяльність диспетчерських і аналітичних служб автотранспортних підприємств і підрозділів, та надає наступні можливості:
– облік індивідуальних завдань на транспортні засоби;
– автоматизація введення завдань: шаблони та розклади;
– планування роботи транспортних засобів у часі;
– планування роботи персоналу на транспортних засобах;
– виписка подорожніх листів;
– інтеграція з системою моніторингу «Автотрекер» (об'єкти, транспортні засоби);
– оперативний контроль виконання завдань;
– планування та облік сервісних і ремонтних робіт (вартість, трудовитрати, запчастини та витратні матеріали, зайнятість транспортних засобів та персоналу);
– облік показників роботи транспортних засобів (пробіг, час, показники, що налаштовуються користувачем);
– облік ПММ: планові і фактичні показники, гнучкий розрахунок норм витрати, інтеграція з даними моніторингу;
– облік експлуатаційних витрат;
– введення і систематизація даних про автопарк – транспортні засоби, персонал, документи, структура автопарку;
– облік зайнятості транспортних засобів та персоналу;
– довгострокове планування роботи транспорту і персоналу;
– аналітична звітність;
– робота в режимі тонкого клієнта та WEB–інтерфейс;

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

Основні споживачі цих продуктів:
– оптово–дистриб'юторські компанії;
– транспортно–логістичні компанії;
– експедиторські компанії;
– кур'єрські служби;
– магазини побутової техніки;
– інкасаторські служби;

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

Математичні методи розв'язання задачі

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

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

Серед природних методів виділяють - метод відпалу (різновид методу Монте-Карло). Однак даний метод має недолік: у холодному стані метод стає таким же «жадібним» як градієнтний спуск. Крім того, як і еволюційні методи, метод відпалу неточний. Серед еволюційних методів було вирішено використовувати ГА, незважаючи на те, що ГА поступається в швидкості методу відпалу. ГА легко масштабуються, що вкрай важливо у вирішенні даного завдання; ГА не є «жадібним», що дозволяє використовувати його для задач з великою кількістю локальних мінімумів в просторі рішень.

Розглянемо застосування еволюційних обчислень для вирішення поставленого завдання. Введемо додаткові обмеження:
1. . Робочий день ТА становить 8 годин. Виходячи з того, що середній час відвідування ТТ становить Т часу, а середня швидкість пересування ТА становить 40 км / г маємо обмеження на тривалість робочого дня при складанні розкладу, де N - кількість км в день, К - кількість точок:

KT+N/40<8      (2)

2. За тиждень ТА повинен відвідати всі ТТ, що належать йому рівно стільки разів, скільки вказано в періоді відвідування ТТ.
Розглянемо структуру ГА для вирішення поставленого завдання.
В якості представлення хромосоми візьмемо таблицю.

На перетині коду ТТ та відповідного дня тижня виставляється 1 у разі відвідання цієї ТТ у цей робочий день або 0, якщо ТТ не відвідується в цей день.
Зазначене подання дозволяє використовувати всі необхідні генетичні оператори: кросинговер, мутацію, селекцію, репродукцію і т.і.
Розглянемо докладно реалізацію кросинговеру. Вирішено використовувати двоточковим частково-відповідний (partially-mapped - PMX) кросинговер. Для цього у випадковому порядку вибираємо дві «січні» осередки в таблицях батьків: A[i;j], Z[i1;j1]. Потім проводимо обмін усіма генами, рядок і стовпець яких задовольняють умовам:

iL – номер рядка гена в таблиці особини.
iС – номер стовпця гена в таблиці особини.
Для наочності візьмемо приклад з двома хромосомами-батьками, і випадково обраними «січними» осередками: A[2;2], Z[3;4].

Після виконання кросинговеру з заданими січними осередками буде отримано наступні два нащадка:

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

Оператор мутації реалізується наступним чином: у випадковому порядку вибирається номер стовпця і рядка гена, після чого значення гена інвертується (змінюється з 1 в 0 або назад: з 0 в 1).

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

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

Рисунок 3 - Загальна схема роботи ГА. Анімація складається з 18 кадрів з затримкою в 50 мс поміж кадрами; затримка для повторного відображення складає 1с; кількість циклів відображення не обмежена; об'єм 47,5 кБ.

Висновок

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

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

1. Скобцов Ю.А. «Основы эволюционных вычислений».— Учебное пособие.— Донецк: ДонНТУ, 2008. — С. 326.
2. Седжвик Р. Фундаментальные алгоритмы [Текст]. – Киев: Азимут-Украина, 2003. – С. 154-190.
3. Майника Э. – Алгоритмы оптимизации на сетях и графах [Текст]. – Санкт-Питербург: Unipress, 2009. – С. 91-115.
4. Beck, Ken – Extreme Programming Explained: Embrace Change [Text] / [Текст]. Atlanta, GA: Cokesbury Book, 2009. – C. 50-55.
5. Мудров В.И. Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.
6. Ingber L., Mondescu R. P. Optimization of Trading Physics Models of Markets — IEEE Trans. Neural Networks. 12(4). 2001. P. 776-790.
7. Ingber L., Rosen B. Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison — Mathematical and Computer Modelling. 16(11). 1992. P. 87-100.
8. Konstantin Boukreev. Genetic Algorithm and Traveling Salesman Problem [Електронний ресурс]. — Режим доступу: http://www.generation5.org/content/2001/tspapp.asp
9. Andy Thomas. Solving the Travelling Sales Man Problem using a Genetic Algorithm [Електронний ресурс]. — Режим доступу: http://www.generation5.org/content/2001/ga_tsp.asp
10. Zach Garner. An Introduction to Genetic Programming [Електронний ресурс]. — Режим доступу: http://www.generation5.org/content/2000/ga00.asp