Cодержание

    Введение

1.   Общая постановка задачи

2.   Задача кластеризации

3.   Задача маршрутизации

4.   Предметная интерпретация

Заключение

Литература

Приложение.

Введение

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

Для обеспечения эффективного решения перечисленных задач с целью увеличения суммарной прибыли компании предназначена система оптимизации доставки товаров автотранспортом «Диспетчер» [1]. Отметим, что в названии системы термин оптимизация используется не в строгом математическом смысле (optimum – неулучшаемый), а как устоявшийся в биснес-приложениях термин, характеризующий эффективность и результативность процесса сокращения затрат.

  Система «Диспетчер» разработана в ООО ИК «Сибинтек» – дочерней структуре Нефтяной Компании «Юкос».

Общая схема функционирования системы «Диспетчер» приведена на рис. 1.

Система «Диспетчер», учитывая приоритеты срочности исполнения заказов, позволяет осуществлять:

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

·                    расчёт оптимальных, с точки зрения транспортных и складских расходов, схем доставки товаров на объекты с использованием промежуточных складов;

·                    расчёт оптимальных, с точки зрения транспортных расходов и временных затрат, расписаний доставки товаров получателям от поставщиков и со складов с учётом приоритетов срочности заказов, времени доставки и погрузки-выгрузки;

·                    оптимальный выбор поставщиков товаров для каждого потребителя на основе расчёта минимальной суммарной стоимости товара и его доставки.

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

Система «Диспетчер» включает в себя пользовательский интерфейс, модули оптимизации, подсистему ввода заявок и их приоритетов, использующую информацию из Торговой системы (ТС); подсистему ввода и обработки матрицы расстояний, использующую информацию из Геоинформационной системы (ГИС); подсистему вывода на электронную карту оптимальных маршрутов движения автотранспорта, передающую информацию в ГИС; подсистему формирования отчетных (выходных) форм и документов – маршрутных листов и накладных.

Схемы, экранные формы, отчетные (выходные) формы и документы системы «Диспетчер» вынесены в Приложение.

Авторы выражают искреннюю признательность член-корр. РАН В.В.Белецкому за поддержку на всех этапах выполнения работы и труд по редактированию рукописи.

1.     Общая постановка задачи

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

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

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

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

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

2. Задача кластеризации

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

2.1. Аппарат нечетких множеств

Метод основан на выборе транзитивно ближайших сообщений [2].

При данном подходе каждому объекту сообщению ставится в соответствие пункт на карте. Пункты характеризуются расстояниями между собой.

Пусть е = max a(i, j) по всем i, j - максимальный элемент матрицы расстояний А.

Тогда матрица В = [b(i, j)] размерности n x n, где b(i, j) = 1 - а(i, j) / е

задает нечеткое отношение сходства. 0 ≤ b(i, j) ≤ 1.

Транзитивное замыкание нечеткого отношения сходства задается матрицей D = [d(i, j)] размерности n x n. 0 ≤ d(i, j) ≤ 1.

D = В U В² U В³ U … U Вⁿ,

где U – операция объединения нечетких отношений (MAX).

В² = B o B представляет собой  (Max - min)-композицию нечеткого отношения самого на себя.

b² (x, z) = MAX [MIN (b(x, y), b(y, z))].

                  y

В^k+1 = B^k o B - (Max - min)-композиция нечетких отношений B^k и B.

b ^k+1 (x, z) = MAX [MIN (b^k(x, y), b(y, z))].

   y

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

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

2.2. Раскраска графов

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

Ставится задача раскраски вершин такого графа несовместимости при различных условиях (ограничениях, критериях), среди которых:

- Минимальная раскраска графа (получение минимального числа компактных групп).

- Раскраска графа в заданное число красок (разбиение на группы, соответствующие парку автотранспорта).

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

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

2.3. Частотно-матричный метод

Подход к постановке задачи аналогичен предыдущему, но в качестве исходной модели рассматривается матрица инциденций Q = [q(i, j)]. Столбцам матрицы соответствуют, буквы - объекты (пункты на карте), строкам – подмножество, определяемое словесным отношением S_i, i=1, 2, …, n, и q(i, j) = 1, если в i-е слово входит j-я буква, и q(i, j) = 0 – в противном случае.

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

На основе построенной матрицы определяется частотная матрица отношений F = Q^T x Q, элементы которой f(i, j) используются для целенаправленного нахождения ближайших объектов и включения их в одну группу. В основе данного подхода лежит аппарат дифференцирования дискретных моделей [3].

2.4. Близость (на практике)

Алгоритм учитывает заявки, поступившие от потребителей.

Исходной моделью является матрица расстояний А = [а(i, j)] размерности n x n, где а(i, j) – расстояние от пункта i до пункта j.

Ищется самая удаленная точка (пункт) и к ней последовательно добавляются ближайшие с учетом роста группы. В матрице А ищется строка, сумма элементов которой максимальна. Соответствующий ей пункт вносится в группу. i₁ – координата строки.

Ищется ближайший пункт к внесенному в решение – минимальный элемент матрицы А в столбце i₁. Соответствующий ей пункт вносится в группу. i₂ – координата строки.

Ищется пункт ближайший к внесенным в решение – минимальная сумма элементов матрицы А в столбцах i₁ и i₂. Соответствующий ей пункт вносится в группу. i₃ – координата строки.

И так далее. На очередном шаге k ищется пункт ближайший к внесенным в решение k пунктам i₁, i₂, i₃…, i_k - это минимальная сумма элементов матрицы А в указанных столбцах.

Процесс завершается, если величина заявки в очередной точке (пункте) i_k+1 больше остатка rest, равного разности между максимально возможной величиной суммарных заявок (загрузка авто средства) и суммой заявок от всех включенных в решение пунктов i₁, i₂, i₃…, i_k.

В зависимости от порядка организации перевозок пункт i_k+1 может быть внесен в решение с числом выполненных заявок rest. В этом случае повышается общая загрузка авто средств, но пункт, будет посещаться неоднократно.

3. Задача маршрутизации

Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров) должен объехать всех получателей товаров внутри одной зоны обслуживания. Он выезжает из некоторого пункта и должен вернуться в него же в конце путешествия. Предполагается, что коммивояжер никогда не бывает дважды в одном пункте. Расстояния между получателями товаров задаются с помощью квадратной матрицы расстояний С = [с(i, j)] размерности k x k, где k – количество получателей товаров, с(i, j) – расстояние от получателя i до получателя j. Отметим, что, в общем случае, матрица расстояний не является симметричной. Диагональные элементы матрицы расстояний равны нулю.

Задача коммивояжера состоит в таком объезде всех получателей, чтобы суммарное пройденное расстояние было минимальным. Следует выбрать один оптимальный маршрут из (k-1)! возможных.

Если количество получателей невелико: (k < 13), то решение может быть получено с использованием простого метода перебора.

С ростом размерности задачи (13 ≤ k ≤ 15), целесообразно использовать метод ветвей и границ. Другое название этого же метода – метод поиска по дереву решений. Опишем основные шаги решения задачи коммивояжера этим методом. Вначале находится некоторое допустимое решение (допустимый маршрут). После этого на каждом шаге поиска оптимального решения множество всех оставшихся маршрутов разбивается на два подмножества. В первое подмножество включаются те маршруты, которые содержат некоторую выделенную дугу, во второе подмножество включаются те решения, которые эту выделенную дугу не содержат. Для каждого подмножества вычисляется нижняя граница стоимостей всех решений, вырастающих из этого подмножества. С помощью найденных границ проводят дальнейшее разбиение подмножеств допустимых маршрутов. Алгоритм метода возвращается всякий раз, когда стоимость текущего частичного решения равняется или превосходит стоимость лучшего решения, найденного до сих пор. В конечном итоге остается один из оптимальных маршрутов. Отметим, что в некоторых задачах при использовании метода ветвей и границ объем вычислений может оказаться близким к объему вычислений методом перебора.

Для задач бóльшей размерности (k > 15) метод ветвей и границ становится неприемлемым. В этом случае наиболее эффективным оказывается метод имитации отжига, основанный на аналогии с физическими эффектами, возникающими при охлаждении расплавленных металлов. При быстром охлаждении расплава последний обычно затвердевает, приобретая аморфные структуры расположения отдельных атомов. Эта неупорядоченная структура представляет собой одно из метастабильных состояний с локальным минимумом энергии. Однако перевести систему из расплава в кристаллическое состояние все же можно, если воспользоваться техникой отжига, заключающейся в очень медленном охлаждении системы с течением времени.

Алгоритм метода имитации отжига применительно к задаче коммивояжера [3] состоит в построении последовательности укорачивающихся допустимых маршрутов с использованием локализованных мутаций, затрагивающих ровно два произвольно взятых пункта объезда. Пусть  - некоторый допустимый маршрут протяженности . Мутация, затрагивающая пункты  и , заключается в том, что  и  меняются местами в последовательности объезда. Она приводит к новому маршруту  протяженности . Обозначим . В соответствии с алгоритмом метода имитации отжига результат мутации безоговорочно принимается, если она привела к сокращению протяженности маршрута: . Результат мутации принимается с некоторой вероятностью , если в результате мутации протяженность маршрута не уменьшилась: . Если мутация принята, то новый маршрут используется в качестве нового допустимого маршрута. Если же мутация отвергается, то допустимый маршрут остается прежним. Построение последовательности маршрутов продолжается до тех пор, пока протяженности маршрутов уменьшаются. Имитация отжига заключается в том, что значение параметра Н, играющего роль температуры, от мутации к мутации уменьшается и стремится к нулю. Подбирая подходящую скорость уменьшения температуры, можно добиться того, что последовательность допустимых маршрутов будет стремиться к оптимальному маршруту.

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

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

В ряде случаев эффективными оказываются популярные в настоящее время адаптивно поисковые алгоритмы, основанные на эволюционных факторах получения решения, - генетические алгоритмы [4].

4. Предметная интерпретация

Система «Диспетчер» апробирована на реальных исходных данных двух регионов Нефтяной Компании «Юкос» (Липецкая и Воронежская области) и показала свою эффективность при решении практических задач развоза товаров для магазинов автозаправочных комплексов (АЗК).

Моделирование показало, что внедрение системы в рамках одного региона (области) позволит при обеспечении неукоснительного выполнения всех заявок от магазинов АЗК на поставку авто-аксессуаров и продовольственных товаров заданным количеством автотранспорта сократить за счет оптимизации пробег автотранспорта в среднем на 20%, стоимость поставки – в среднем на 15%.

На рис. 2-3, в качестве примера, представлены некоторые экранные формы (справочник товаров и меню для задания входных параметров для системы «Диспетчер»). На рис. 4 приведены выходные документы, включающие оптимальные маршруты и расписания движения автотранспорта с указанием общей протяженности маршрута, расстояний между магазинами при АЗК, времени прибытия и убытия из магазинов, количества выгружаемых упаковок.

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

Система «Диспетчер» может быть также использована для решения задачи оптимизации доставки топлива от нефтебаз (терминалов) до АЗК, и обеспечить решение задач, связанных с вторичным распределением нефтепродуктов.

Отметим, что описанный в настоящей работе метод построения товародвижения на разветвленной сети дорог состоит в поэтапном решении задач кластеризации и маршрутизации. Аналогичные идеи разбиения процесса решения исходной задачи на такие этапы используются и в других прикладных областях. Так, например, в [5] на основе концепции групповой технологии, объединяющей комплекс методов типизации технологических процессов и разработки групповых маршрутных и операционных технологических процессов, представлено решение задачи повышения эффективности серийного механообрабатывающего производства. Детали группируются по конструктивно-технологическим признакам, а затем порядок запуска деталей из одной группы на станок рассчитывается с помощью решения задачи коммивояжера.

Заключение

Основные результаты работы состоят в следующем:

1. Рассмотрены математические модели, лежащие в основе системы оптимизации доставки товаров автотранспортом «Диспетчер», предназначенной для сокращения затрат на транспортировку грузов на разветвленной сети дорог.

2. Предложено решение задачи развоза товаров, состоящее из двух этапов:

-         разбиение региона на компактные зоны обслуживания (кластеризация);

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

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

4. Приводятся результаты использования системы «Диспетчер» при решении задач транспортировки грузов на разветвленной сети дорог для регионов Нефтяной Компании «Юкос».

Литература

1.     Смирнов М.И., Хайруллин Р.З., Кожахмедов Т.И., Павлов А.А. Свидетельство об официальной регистрации программы для ЭВМ № 2001611583 от 22 ноября 2001 года. Выдано Российским агентством по патентам и товарным знакам (РОСПАТЕНТ).

2.     Кофман А. Введение в теорию нечетких множеств. М., Радио и связь, 1982.

3.      Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логическое управление распределенными системами. М., Энергоатомиздат, 1991.

4.     Clement R.P., Wren A. Genetic Algorithms and Bus-Driver Scheduling. International Conference for Computer-Aided Transport Scheduling, Lisbon, Portugal, 1993.

5.     Блехерман М.Х. Гибкие производственные системы. Организационно – экономические аспекты. М., Экономика, 1988.

Приложение