Реферат на тему «Разработка компьютеризированной системы оптимального распределения и доставки лекарственных средств»

  1. Цель и задачи данного исследования
  2. Актуальность темы
  3. Предполагаемая научная новизна
  4. Предполагаемая практическая ценность
  5. Обзор исследований и разработок по теме
  6. Постановка задачи исследования
  7. Математическая модель задачи
  8. Муравьиный алгоритм
  9. Заключение
  10. Список литературы

Цель и задачи исследования

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

В рамках данной работы были поставлены следующие задачи:

· Охарактеризовать объект и оценить требования к разрабатываемой системе

· Провести анализ методов, моделей, алгоритмов и инструментальных средств, для построения и оптимизации маршрутов доставки товаров

· Провести выбор и обоснование метода для выполнения поставленной цели

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

Актуальность темы

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

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

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

Предполагаемая научная новизна

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

Предполагаемая практическая ценность

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

Обзор исследований и разработок по теме

Система ArcLogistics

Продукт компании ESRI(США), одной из мировых лидеров в разработке, создании и продвижении геоинформационных систем. ArcLogistics – это инструмент диспетчера, ежедневно планирующего работу парка транспортных средств, чья работа включает в себя расчет оптимальных маршрутов, создание маршрутных листов, построение отчетов, анализ пробега и оценку эффективности работы. ArcLogistics предназначен для пользователей, не являющихся специалистами в области ГИС. Интерфейс программы прост в освоении и использовании.

Основные преимущества ArcLogistics:

· Оптимальное использование парка транспортных средств.

· Наличие карт дорог на всю территорию Европы (включая Россию).

· Совместимость с другими программными продуктами и форматами данных ESRI.

· Гибкие настройки характеристик транспортных средств.

· Возможность интеграции с внешними информационными системами.

· Инструменты создания отчетов и путевых листов.

· Использование зон ответственности водителей и оперативное внесение изменений (барьеров).

Возможности:

Построение оптимальных маршрутов позволяет снизить пробег автомобилей и стоимость эксплуатации автопарка, а также улучшить качество обслуживания клиентов компании. В ArcLogistics учитываются различные свойства автомобилей, такие как грузоподъемность, максимальное количество заказов, масса, стоимость часа работы или километра пробега. В зависимости от задач, можно выбирать режим максимальной экономии и режим приоритета своевременной доставки заказа. Одной из важнейших логистических задач является геокодирование, т.е. поиск на карте точки или отрезка, соответствующего текстовому адресу, указанному в заказе. ArcLogistics позволяет максимально автоматизировать этот процесс, снизить нагрузку на оператора и уменьшить время, требующееся на обработку заказов. Есть возможность привязки автомобилей к определенным зонам обслуживания, учета препятствий на дорогах. Составление маршрутных листов и отчетов реализовано с помощью программы Crystal Reports, которая позволяет генерировать отчеты на основе запросов к самым распространенным типам баз данных, в том числе к базам данных ArcGIS. С помощью стандартных инструментов Crystal Reports пользователь может сделать собственные шаблоны отчетов, которые потом будут использоваться в повседневной работе. ArcLogistics является самостоятельным приложением не требующим установки других программных продуктов ArcGIS.

Система MapXPlus

Система компании «Транс сис». Основной задачей программного комплекса MapXPlus является автоматизация транспортной логистики, т.е. планирование маршрутов доставки продукции клиентам, с минимальными затратами и с учетом ряда факторов и критериев. Система относится к классу систем TMS и решает задачи транспортной логистики. Также есть возможность создавать графики доставки, которые покажут, в какое время товар будет доставлен клиенту. Перед сокращением, покупкой или обновлением автопарка можно определить наиболее эффективный модельный ряд для потребностей бизнеса.

Задачи, решаемые системой MapXPlus:

· Планирование маршрутов доставки товара с одного или нескольких складов на множество торговых точек с минимальными затратами.

· Работа как централизованно, так и с несколькими центрами планирования доставок.

· Ситуационное моделирование, оптимизация парка автомобилей и определение количественно-качественных характеристик при его формировании.

· Планирование работы как своего автопарка, так и привлекаемых (наемных) транспортных средств с расчетом затрат по заданным тарифам.

· Создание и анализ моделей доставки товаров с учетом комбинаций критериев и факторов, влияющих на эффективность работы.

· Поддержка форматов работы Van-salling и Pre-salling.

· Выявление торговых точек, доставка груза в которые является невыгодной.

Система «Деловая карта»

Деловая карта – система разработанная компанией ИНГИТ.

Возможности системы «Деловая карта»:

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

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

По размещению клиентов на карте можно делать отбор для маршрутов объезда, контролируя протяженность, количество клиентов, а также суммарные загрузки, например, общий вес или количество мест, соотнося эти данные с грузоподъемность или вместимостью транспорта.

Система автоматической прокладки маршрутов автотранспорта с учетом организации дорожного движения обеспечивает получение реального маршрута автомобиля для объезда клиентов, выбранных из базы по любым запросам или отобранным по карте с учетом весовых и количественных ограничений. Обеспечивается калькуляция маршрутов по любым алгоритмам, задаваемым пользователями.

Уникальная технология расчетов для доставки грузов обеспечивает мгновенный расчет маршрутов целого парка автотранспорта для исполнения всего объема дневных заказов. При расчетах учитываются грузоподъемность и вместимость транспорта, требования срочности заказов и времени исполнения, оптимизация движения с учетом дорожных знаков, ограничения на время или протяженность маршрутов, с тем, чтобы например, доставить хлеб в торговые точки горячим и пр. Система представления результатов позволяет выдать каждому водителю распечатку его дневной работы. Обеспечивается динамическое представление работы транспорта по доставке заказов, т.е. на любой момент времени, можно видеть на карте где находятся транспортные средства и чем занимаются, т.е. разгружаются, загружаются, или следуют в очередной пункт.

Постановка задачи исследования

Рассматривается сетка дорог с большим количеством узлов – перекрестков, тупиков и точек обслуживания, через которые должны пройти маршруты движения транспорта. Сетке дорог ставится в соответствие ориентированный граф, вершинами которого являются узлы данной сетки, а ребрами – отрезки дорог между узлами (движение по дороге может быть односторонним).[1] Каждому ребру приписывается длина – расстояние между соответствующими узлами. Решение поставленной задачи развоза товаров осуществляется в два этапа. На первом этапе решается задача разбиения региона на компактные зоны обслуживания – направления (группирование объектов-получателей для каждого маршрута). Эту задачу будем называть задачей кластеризации. На втором этапе решается задача нахождение оптимального по заданному критерию (суммарному расстоянию, времени, стоимости доставки) порядка объезда получателей для каждого маршрута. Эту задачу будем называть задачей маршрутизации[2].

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

Таким образом, расстояния между объектами задаются квадратной матрицей расстояний C = [i, j] размерности n x n, где C[i, j] – расстояние от пункта i до пункта j. Необходимо отметить, что, в общем случае, матрица расстояний не является симметричной (одностороннее движение, сложные транспортные развязки и т.д.).[3]

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

Имеется N точек, которые должен обойти автомобиль с минимальными затратами. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть автомобиль должен вернуться на склад;

· в каждой из точек автомобиль должен побывать точно один раз, то есть надо обязательно обойти все точки, при этом не побывав ни в одной точке дважды.

Для расчета затрат существует матрица условий, содержащая затраты на переход из каждой точки в другую, при этом считается, что переход из точки в саму себя запрещен (в матрице вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат[3].

Математическая модель задачи

N – число точек.

Cij , i, j = 1…N – матрица затрат, где Cij – затраты на переход из i-й точки в j-ю.

Xij – матрица переходов со значениями:

Xij = 1, если автомобиль совершает переход из i-й точки в j-ю,

Xij = 0, если не совершает перехода,

где i, j = 1..N и i<>j.

Критерий:

, (1)

где Сij – матрица стоимости переходов,

Xij – матрица переходов, где xij = 0, если переход совершен и xij = 1 в противном случае.

Ограничения:

, i = 1…N (2)

, j = 1...N (3)

Ui - Uj + N * Xij <= N-1, i, j = 1…N, i <> j. (4)

Условие (2) означает, что автомобиль из каждой точки выезжает только один раз; условие (3) - въезжает в каждую точку только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N точек, и не содержащего замкнутых внутренних петель. На рисунке 1 черным прямоугольником изображен склад, а кругами - аптеки, по которым необходимо развести лекарства.

Рисунок 1 – Схема доставки лекарственных средств

Муравьиный алгоритм

Идея муравьиного алгоритма - моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным[10].

Рисунок 2 – Схема работы муравьиного алгоритма

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются точками, которые должен посетить автомобиль, а веса рёбер отражают расстояния проезда. Эта задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность[8].

С учетом поставленной задачи правила выбора пути муравьем описываются следующим образом:

1. Муравьи имеют собственную «память». Поскольку каждый город может быть посещён только один раз, то у каждого муравья есть список уже посещённых городов – список запретов. Обозначим через Jik список городов, которые необходимо посетить муравью k, находящемуся в городе i.

2. Муравьи обладают «зрением» – видимость есть эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами ηij=1/Dij.

3. Муравьи обладают «обонянием» – они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьёв. Количество феромона на ребре (i,j) в момент времени t обозначим через τij(t) .

4. На этом основании мы можем сформулировать вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:

, (5)

Где α,β- параметры, задающие веса следа феромона. При α = 0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Заметим, что выбор города является вероятностным, правило (5) лишь определяет ширину зоны города j; в общую зону всех городов Jik бросается случайное число, которое и определяет выбор муравья. Правило (5) не изменяется в ходе алгоритма, но у двух разных муравьёв значение вероятности перехода будут отличаться, т.к. они имеют разный список разрешённых городов[8].

5. Пройдя ребро (i,j), муравей откладывает на нём некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть Tk(t) есть маршрут, пройденный муравьём k к моменту времени t; Lk(t) – длина этого маршрута, а Q – параметр, имеющий значение порядка длины оптимального пути. Тогда откладываемое количество феромона может быть задано в виде

, (6)


Правила внешней среды определяют, в первую очередь, испарение феромона. Пусть p = [0,1] есть коэффициент испарения, тогда правило испарения имеет вид

,(7)

где m – количество муравьёв в колонии.

В начале алгоритма количества феромона на рёбрах принимается равным небольшому положительному числу. Общее количество муравьёв остаётся постоянным и равным количеству городов, каждый муравей начинает маршрут из своего города.[7]

Заключение

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

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

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

1. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. // Высшая школа, М. – 1980, 300 с.

2. Е. П. Липатов. Теория графов и её применения // Знание, М. – 1986, 32 с.

3. Новиков Ф.А. Дискретная математика для программистов // Питер, Санкт-Петербург – 2001, 304 с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ // МЦНМО, М. – 2000, 960 с.

5. Dorigo M., Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation – 1997, pp. 53-66.

6. Dorigo M., G. Di Caro, Gambardella L. M. Ant Algorithms for Discrete Optimization // Artificial Life – 1999, pp. 137-172.

7. Джонс М.Т. Программирование искусственного интеллекта // ДМК Пресс, М. – 2004, 312 с.

8. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях – 2003, №4, сс.70-75.

9. Чураков Михаил. Муравьиные алгоритмы [электронный ресурс]. – Режим доступа: http://rain.ifmo.ru/cat/data/theory/unsorted/ant-algo-2006/article.pdf

10. Алгоритмы муравьиной колонии [электронный ресурс]. – Режим доступа: http://ru.science.wikia.com/wiki/Алгоритмы_муравьиной_колонии