Задача нахождения оптимального расписания работы агентов на графах больших размерностей
В работе рассматривается оптимизационные задачи на графах большой размерности, не имеющие эффективных алгоритмов нахождения точного решения.
Задача составления оптимального расписания работы агентов ОАО «Невинномысский Азот», обслуживающих клиентов. Обслуживание заключается в доставке некоторой продукции. Каждый объект доставки может иметь несколько характеристик (например, массу, размер, стоимость и т.д.). Для каждого агента заданы начало и конец движения, интервал работы, ограничения на суммарные характеристики объектов. Для каждого клиента заданы интервал времени, в течение которого должна быть оказана услуга, время, затрачиваемое на оказание услуги, и характеристики объекта, который он хочет получить или отдать. Под расписанием будем понимать график работы каждого агента: выбор маршрутов движения и времени обслуживания. Графики должны быть составлены так, чтобы были обслужены все клиенты и выполнены ограничения по времени и характеристикам объектов. Расписание необходимо составить таким образом, чтобы минимизировать общие затраты агентов (например, время работы, суммарные транспортные расходы, количество задействованных агентов и др.).
В работе описывается математическая постановка задачи. Приводится метод декомпозиции исходной задачи на более простые независимые подзадачи, алгоритмы решения которых приводятся в [3]. В заключении рассматриваются достоинства и недостатки методов, изложенных в данной работе.
1 Математическая постановка задачи
Рассматривается ориентированный граф G=(V,E) большой размерности, на рёбрах которого задан набор характеристик. В графе выделено подмножество вершин V' c V (V'=A u C, где A c V — множество, наперед заданных точек, в которых агенты начинают и заканчивают свою работу, а C c V множество вершин — местоположения клиентов). В работе используется алгоритм сведения задачи оптимизации на графе G к задаче оптимизации на графе G'=(V',E'), где множество E' — всевозможные кратчайшие пути в графе G между вершинами из V'. Оптимизация состоит в поиске маршрутов, минимизирующих значение целевой функции F.
Таким образом, исходную задачу можно разбить на две подзадачи:
1) построение по исходному графу G преобразованного графа G';
2) решение оптимизационной задачи на графе G'.
Хотя для первой подзадачи существуют эффективные методы решения, если вектор характеристики ребра одномерный (алгоритмы Дейкстры, Флойда-Уоршолла, Джонсона и др [1]), но если характеристики ребра имеют размерность 2 и более (в нашем случае e c E, назовем вектор e c RxR, e=(e^d,e^t), где e^d,e^t — длина и время движения), то данные алгоритмы становятся непригодными. Для решения данной задачи будем использовать алгоритм нахождения кратчайшего пути по первой компоненте характеристики ребра от заданной вершины до всех вершин графа при наложении ограничениях на остальные компоненты. Данный алгоритм приводится в [3].
К сожалению, для решения второй подзадачи в настоящее время эффективных алгоритмов не существует. Кроме того, нет и общей теории построения алгоритмов нахождения приближённых решений. Поэтому для каждой конкретной задачи приходится искать свой способ решения. Общая идеология для нашего случая решения второй подзадачи приводится во втором разделе.
2 Метод решения задачи нахождения оптимального расписания работы агентов
Построение расписания можно разбить на три этапа:
1) распределение клиентов между агентами (разбиение множества C на m непересекающихся подмножеств);
2) выбор порядка обслуживания клиентов для каждого агента;
3) оптимизация маршрута каждого агента при фиксированном порядке обслуживания клиентов.
Таким образом, суммарные ограничения по характеристикам для каждого агента проверяются на первом этапе, ограничения на вершины — на первых двух, а на третьем этапе проверяются временные ограничения.
При распределении клиентов между агентами и выборе их порядка обслуживания используются итерационные методы. В данной работе за основу взяты эволюционные методы. В начале, мы строим колонию (множество приближённых решений), а далее эта колония начинает мутировать, т. е. изменяться по определённым законам. При этом некоторые особи колонии (приближённые решения) исчезают, некоторые появляются, часть особей изменяется. В нашем случае особями колонии являются расписания. В качестве мутаций рассматриваются перестановки частей маршрутов, входящих в расписание, между собой (несколько последовательно обслуживаемых клиентов одного агента и несколько последовательно обслуживаемых клиентов другого агента меняются местами с сохранением порядка обслуживания). Применение таких мутаций позволяет производить быстрый перерасчёт ограничений и значения целевой функции (в случае её аддитивности). Для быстрого определения временных ограничений необходимо хранить данные выбора оптимальных рёбер, полученных на третьем этапе решения задачи. Применяется два вида мутаций: направленные и случайные. В результате применения направленных мутаций значение целевой функции уменьшается. Это позволяет достаточно быстро находить локальный минимум функции. Применение случайных мутаций позволяет выйти из окрестности локального минимума и даёт дополнительные возможности для нахождения глобального минимума целевой функции. Для повышения эффективности алгоритма необходимо согласовывать количество применений направленных и случайных мутаций.
При решении задачи можно использовать две различные стратегии:
1) рассматриваются только корректные расписания;
2) рассматриваются всевозможные расписания.
Первая стратегия предполагает, что на каждом шаге решения задачи рассматриваются только корректные расписания и маршруты. Такое ограничение затрудняет поиск применимых мутаций, но гарантирует построение корректного расписания. Вторая стратегия заключается в том, что мы рассматриваем всевозможные маршруты и изменяем целевую функцию таким образом, что она начинает учитывать степень «некорректности» расписания.
Для начального построения колонии используются различные эвристические методы. Неплохие начальные приближение дают методы имитации течения времени, когда незанятым в данный момент времени агентам назначаются ещё не обслуженные клиенты. Например, всем свободным агентам назначаются клиенты так, чтобы суммарные характеристики маршрутов были бы минимальными.
Заключение
В работе описано несколько различных подходов для построения алгоритмов поиска приближённых решений оптимизационных задач на графах больших размерностей. Описаны возможные эвристические подходы для повышения общей скорости работы. Алгоритмы, приведённые в данной работе, применялись на модели и дали достаточно неплохие результаты. Тестирование проводилось на множестве практических задач [2], в том числе и на задачах, описанных в начале работы. В качестве сеток дорог рассматривались модели карт Ставропольского края. Самый большой граф, на котором проводилось тестирование, содержал 6148 вершин, 7439 рёбер и 180 точек обслуживания. Алгоритмы, приведённые в данной работе, достаточно хорошо распараллеливаются и дают высокий коэффициент утилизации при увеличении числа процессоров [4]. Недостатком вышеизложенных методов является тот факт, что заранее невозможно предсказать результаты работы программы. К сожалению, бывают случаи, когда результаты неудовлетворительны. Наличие таких результатов связано с тем фактом, что задачи имеют большую вычислительную сложность. Построение универсального алгоритма невозможно в предположении выполнения гипотезы о том, что класс P полиномиально — вычислимых задач не совпадает с классом NP-полных задач, т. е. P = NP.
Задача составления оптимального расписания работы агентов ОАО «Невинномысский Азот», обслуживающих клиентов. Обслуживание заключается в доставке некоторой продукции. Каждый объект доставки может иметь несколько характеристик (например, массу, размер, стоимость и т.д.). Для каждого агента заданы начало и конец движения, интервал работы, ограничения на суммарные характеристики объектов. Для каждого клиента заданы интервал времени, в течение которого должна быть оказана услуга, время, затрачиваемое на оказание услуги, и характеристики объекта, который он хочет получить или отдать. Под расписанием будем понимать график работы каждого агента: выбор маршрутов движения и времени обслуживания. Графики должны быть составлены так, чтобы были обслужены все клиенты и выполнены ограничения по времени и характеристикам объектов. Расписание необходимо составить таким образом, чтобы минимизировать общие затраты агентов (например, время работы, суммарные транспортные расходы, количество задействованных агентов и др.).
В работе описывается математическая постановка задачи. Приводится метод декомпозиции исходной задачи на более простые независимые подзадачи, алгоритмы решения которых приводятся в [3]. В заключении рассматриваются достоинства и недостатки методов, изложенных в данной работе.
1 Математическая постановка задачи
Рассматривается ориентированный граф G=(V,E) большой размерности, на рёбрах которого задан набор характеристик. В графе выделено подмножество вершин V' c V (V'=A u C, где A c V — множество, наперед заданных точек, в которых агенты начинают и заканчивают свою работу, а C c V множество вершин — местоположения клиентов). В работе используется алгоритм сведения задачи оптимизации на графе G к задаче оптимизации на графе G'=(V',E'), где множество E' — всевозможные кратчайшие пути в графе G между вершинами из V'. Оптимизация состоит в поиске маршрутов, минимизирующих значение целевой функции F.
Таким образом, исходную задачу можно разбить на две подзадачи:
1) построение по исходному графу G преобразованного графа G';
2) решение оптимизационной задачи на графе G'.
Хотя для первой подзадачи существуют эффективные методы решения, если вектор характеристики ребра одномерный (алгоритмы Дейкстры, Флойда-Уоршолла, Джонсона и др [1]), но если характеристики ребра имеют размерность 2 и более (в нашем случае e c E, назовем вектор e c RxR, e=(e^d,e^t), где e^d,e^t — длина и время движения), то данные алгоритмы становятся непригодными. Для решения данной задачи будем использовать алгоритм нахождения кратчайшего пути по первой компоненте характеристики ребра от заданной вершины до всех вершин графа при наложении ограничениях на остальные компоненты. Данный алгоритм приводится в [3].
К сожалению, для решения второй подзадачи в настоящее время эффективных алгоритмов не существует. Кроме того, нет и общей теории построения алгоритмов нахождения приближённых решений. Поэтому для каждой конкретной задачи приходится искать свой способ решения. Общая идеология для нашего случая решения второй подзадачи приводится во втором разделе.
2 Метод решения задачи нахождения оптимального расписания работы агентов
Построение расписания можно разбить на три этапа:
1) распределение клиентов между агентами (разбиение множества C на m непересекающихся подмножеств);
2) выбор порядка обслуживания клиентов для каждого агента;
3) оптимизация маршрута каждого агента при фиксированном порядке обслуживания клиентов.
Таким образом, суммарные ограничения по характеристикам для каждого агента проверяются на первом этапе, ограничения на вершины — на первых двух, а на третьем этапе проверяются временные ограничения.
При распределении клиентов между агентами и выборе их порядка обслуживания используются итерационные методы. В данной работе за основу взяты эволюционные методы. В начале, мы строим колонию (множество приближённых решений), а далее эта колония начинает мутировать, т. е. изменяться по определённым законам. При этом некоторые особи колонии (приближённые решения) исчезают, некоторые появляются, часть особей изменяется. В нашем случае особями колонии являются расписания. В качестве мутаций рассматриваются перестановки частей маршрутов, входящих в расписание, между собой (несколько последовательно обслуживаемых клиентов одного агента и несколько последовательно обслуживаемых клиентов другого агента меняются местами с сохранением порядка обслуживания). Применение таких мутаций позволяет производить быстрый перерасчёт ограничений и значения целевой функции (в случае её аддитивности). Для быстрого определения временных ограничений необходимо хранить данные выбора оптимальных рёбер, полученных на третьем этапе решения задачи. Применяется два вида мутаций: направленные и случайные. В результате применения направленных мутаций значение целевой функции уменьшается. Это позволяет достаточно быстро находить локальный минимум функции. Применение случайных мутаций позволяет выйти из окрестности локального минимума и даёт дополнительные возможности для нахождения глобального минимума целевой функции. Для повышения эффективности алгоритма необходимо согласовывать количество применений направленных и случайных мутаций.
При решении задачи можно использовать две различные стратегии:
1) рассматриваются только корректные расписания;
2) рассматриваются всевозможные расписания.
Первая стратегия предполагает, что на каждом шаге решения задачи рассматриваются только корректные расписания и маршруты. Такое ограничение затрудняет поиск применимых мутаций, но гарантирует построение корректного расписания. Вторая стратегия заключается в том, что мы рассматриваем всевозможные маршруты и изменяем целевую функцию таким образом, что она начинает учитывать степень «некорректности» расписания.
Для начального построения колонии используются различные эвристические методы. Неплохие начальные приближение дают методы имитации течения времени, когда незанятым в данный момент времени агентам назначаются ещё не обслуженные клиенты. Например, всем свободным агентам назначаются клиенты так, чтобы суммарные характеристики маршрутов были бы минимальными.
Заключение
В работе описано несколько различных подходов для построения алгоритмов поиска приближённых решений оптимизационных задач на графах больших размерностей. Описаны возможные эвристические подходы для повышения общей скорости работы. Алгоритмы, приведённые в данной работе, применялись на модели и дали достаточно неплохие результаты. Тестирование проводилось на множестве практических задач [2], в том числе и на задачах, описанных в начале работы. В качестве сеток дорог рассматривались модели карт Ставропольского края. Самый большой граф, на котором проводилось тестирование, содержал 6148 вершин, 7439 рёбер и 180 точек обслуживания. Алгоритмы, приведённые в данной работе, достаточно хорошо распараллеливаются и дают высокий коэффициент утилизации при увеличении числа процессоров [4]. Недостатком вышеизложенных методов является тот факт, что заранее невозможно предсказать результаты работы программы. К сожалению, бывают случаи, когда результаты неудовлетворительны. Наличие таких результатов связано с тем фактом, что задачи имеют большую вычислительную сложность. Построение универсального алгоритма невозможно в предположении выполнения гипотезы о том, что класс P полиномиально — вычислимых задач не совпадает с классом NP-полных задач, т. е. P = NP.
- 0
- 31 января 2011, 03:56
- комментировать
