Автореферат (1137431), страница 2
Текст из файла (страница 2)
Алгоритмы разбиваются на три поколения.К первому поколению относятся простые эвристики, в основе которых заложен локальный поиск решения. Ко второму поколению относятся алгоритмы, основанные на методе математического программирования. Алгоритмыиз этой группы позволяют находить решения, близкие к оптимальным, и вряде случаев точные решения. К третьему поколению относятся алгоритмыпоиска точного решения и методы искусственного интеллекта.В разделе 1.4 приводится классификация Кордо, согласно которой все алгоритмы разбиваются на четыре фазы: построение начального приближения,локальная оптимизация, глобальная оптимизация, машинное обучение. Каждая фаза рассматривается отдельно.
Приводится обзор конструктивных алгоритмов (Моля-Джеймсона, Кларка-Райта, Кристофидеса-Монгоззи-Тасса),кластерных алгоритмов (Фишера-Джекумера, Брамера-Симчи-Леви) и алгоритмов для оптимизации отдельных маршрутов, основанных на λ-обменахОсмана. Рассматриваются генетические алгоритмы и методы машинного обучения (метод эластичных сетей, метод самоорганизующейся карты, метод муравьиных колоний).В разделе 1.5 содержатся выводы по первой главе. В течение прошлого десятилетия большое количество успешных и чрезвычайно эффективныхэвристик были предложены для решения ЗМТ с временными окнами.
Новые подходы дают все более точные результаты. Но при этом большинство6из них не в состоянии обеспечить хороший компромисс между качеством ипроизводительностью. Одновременное усовершенствование алгоритмов какс точки зрения эффективности, так и с точки зрения производительностиявляется открытой задачей. До недавнего времени основные усилия былисосредоточены на решении задач, содержащих до 1000 клиентов. В даннойработе рассматриваются задачи, содержащие до 10000 клиентов.В 2005 году Olli Bräysy для ЗМТ с временными окнами провел сравнительный анализ скорости и качества работы известных алгоритмов для 100 клиентов. Позже в 2010 году Michel Gendreau провел аналогичное тестирование для1000 клиентов.
Результаты экспериментов приведены на рис. 1. Эти исследования показали, что только конструктивные алгоритмы обладают высокойпроизводительностью. Алгоритмы, в которых используются дополнительныеэтапы оптимизации, дают более точные результаты, но существенно проигрывают по скорости работы.
Таким образом, алгоритмы делятся на две группы:либо обладающие высокой производительностью, либо высокой эффективностью оптимизации (по количеству задействованных агентов, по суммарнойдлине маршрутов). Данная работа посвящена разработке алгоритмов, которые обладали бы такой же производительностью как конструктивные алгоритмы, но более высокой степенью оптимизации.57.9Быстрые алгоритмы57.8Braysy et al.
(2004)Gehring and Homberger (1999)Homberger and Gehring (2005)57.757.6Эффективные алгоритмыLe Bouthillier and Crainic (2005)57.5Gehring and Homberger (2001, 2002)Le Bouthillier et al. (2005)57.457.3Pisinger and Ropke (2006)Ibaraki et al. (2008)Многофазный алгоритм*57.257.157.0Hashimoto and Yagiura (2008)0255075100125150175200225Рис.
1. Сравнительная характеристика работы алгоритмов на тестовыхпримерах, содержащих 1000 клиентов. По оси абсцисс — среднее времяработы алгоритма в минутах, по оси ординат — среднее количество задействованных агентов.* — многофазный алгоритм, описанный в диссертационной работеВо второй главе приводятся основные результаты работы.В разделе 2.1 приводится математическая постановка задачи. Рассматривается задача маршрутизации транспорта c временными окнами и дополнительными ограничениями по типам транспорта, приоритетам клиентов изонам обслуживания.7Опишем исходные данные:• Ориентированный граф G = (V, E), определяющий топологию дорожной сети.
На ребрах графа определены весовые функции, которые задают длину ребер d : E → R+ и время движения по ребру t : E → R+ .• Множество клиентов C, для которых задано местоположение v : C → V,интервал времени работы ts , tf : C → R+ , характеристики товаровq : C → Rk+ , приоритет p : C → N+ .• Множество агентов A. Для агентов задано местоположение в начале иконце маршрута vs , vf : A → V, зона обслуживания z : A×C → {0, 1},интервал времени работы ts , tf : A → R+ , ограничения на суммарныехарактеристики товаров qmax : A → Rk+ .Множество всевозможных путей в графе обозначим P.
График посещения клиентов назовем маршрутом агента. Каждый маршрут задается последовательностью клиентов {ci} и временами их посещения {ti }. Пусть R —множество всевозможных маршрутов. Маршрут r ∈ R агента a ∈ A будемназывать корректным, если выполнены ограничения:• по интервалу времени работы агента[ts(r), tf (r)] ⊂ [ts(a), tf (a)],• по интервалу времени обслуживанияti ∈ [ts(ci ), tf (ci)],• по грузоподъемностиXq(ci ) 6 qmax (a),i• по ограничениям на зоны обслуживанияz(a, ci ) = 1.Рассмотрим маршрут r ∈ R. Обозначим через np (r) количество клиентовв маршруте с приоритетом p.
Введем многомерную целевую функцию:f (r) = (n1 (r), . . . , np(r), −t(r), −d(r)) .При сравнении значений целевой функции будем использовать лексикографический порядок. Множество маршрутов агентов назовем расписанием. Множество всевозможных расписаний обозначим S. Определим целевуюфункцию расписания s ∈ S:Xf (s) =f (r).r∈s8Расписание s ∈ S будем называть корректным, если все маршруты агентов корректны и каждого клиента обслуживает не более, чем один агент.Необходимо максимизировать целевую функцию, то есть построить корректное расписание, при котором обслуживается максимальное количество клиентов, задействуется минимальное количество агентов и минимизируютсятранспортные расходы.В разделе 2.2 приводится общая схема работы алгоритма, которую можнопредставить в виде диаграммы:Построение редуцированного графаГруппировка клиентовПостроение начального приближенияОбмен сегментов маршрутовРазгрузка агентовПостобработкаРис.
2. Многофазный алгоритмРассматриваемый алгоритм является модифицированной версией алгоритма Османа. Алгоритм основан на множественном обмене сегментов маршрутов и представляет собой эвристику, использующую методы локальной оптимизации.
Для повышения быстродействия большое внимание уделяется вопросам производительности. Для минимизации количества задействованныхагентов вводится специальная операция — разгрузка агентов. Минимизациятранспортных расходов осуществляется в заключительной фазе работы алгоритма.В разделе 2.3 описывается построение редуцированного графа. Это ориентированный граф G′ = (V′, E′ ), в котором V′ = v(C) ∪ vs (A) ∪ vf (A) —множество выделенных вершин, а E′ ⊂ V′ × V′ — пути в исходном графе G.Редуцированный граф является аналогом матрицы расстояний между клиентами. Переход от исходного графа G к редуцированному графу G′ позволяетснизить размерность задачи.Задача сводится к многокритериальной задаче о поиске кратчайших путей в графе.
Отдельно рассматриваются одномерный, двумерный и многомерный случаи.Одномерный случай является хорошо изученной задачей с научной точкизрения. Для повышения скорости работы предлагается использовать алгоритмы с предподсчетом, например, метод иерархии автомагистралей.9Так как в исходной задаче задаются ограничения по времени, а минимизируются транспортные расходы, двумерный случай представляет особый интерес.
Необходимо найти подмножество оптимальных (Парето-минимальных)путей заданной мощности.Сведем задачу к одномерной. Введем новую весовую функцию, зависящую от параметра λ ∈ [0, 1]:w(e) = λd(e) + (1 − λ)t(e).Зафиксируем значение λ. Решим задачу о поиске кратчайшего пути в графе. Найденный путь будет оптимальным для двумерной задачи. Чтобы сформировать искомый набор оптимальных путей, будем варьировать параметр λ.Рассмотрим множество оптимальных путей (di, ti ).
Для каждого i построимграфик функции wi (λ) = λdi + (1 − λ)ti . Рассмотрим нижнюю часть плоскости, ограниченную данными графиками. Граница полученной фигуры будетломаной линией. Вершины этой ломаной позволяют найти искомые значенияпараметра λ.t2d1d3t3d2t1λ1λ4λ3λ5λ2Рис. 3. Динамическое вычисление параметра λБудем строить границу фигуры постепенно. Найдем параметры путей приλ1 = 0 и λ2 = 1. Построим графики функций w1, w2. Найдем точку пересечения — значение λ3 . Вычислим оптимальный путь, построим график функцииw3 .
Найдем значения λ4 и λ5 . Продолжим процесс до тех пор, пока не наберемнужное количество оптимальных путей.Приведенное решение хорошо работает на практике, несмотря на то, чтоне все оптимальные пути могут быть получены таким образом.При исследовании многомерного случая удалось обобщить задачу. Вместовесовой вектор-функции ребер вводится отношение частичного порядка намножестве путей и задача сводится к нахождению минимальных путей.На множестве путей P зададим отношение частичного порядка «6».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
