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

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

Содержание:

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