Автореферат (1137431), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Подмножество минимальных элементов множества P ⊂ P будем обозначать P ∗ .Подмножество путей, начинающихся в вершине u, а заканчивающихсяв верSmin∗шине v, будем обозначать Puv . Множество P= u,v∈V Puv будем называть множеством локально-минимальных путей. Необходимо найти вселокально-минимальные пути, начинающиеся в заданной вершине.10Учитывая, что количество различных отношений частичного порядка растет экспоненциально при увеличении размеров графа, сформулированная задача в общем виде не имеет эффективного решения.Началом пути p ранга k будем называть путь p{k}, полученный из p удалением k последних ребер и соответствующих вершин.

Будем решать задачу впредположении выполнения условия минимальности, которое является аналогом неотрицательности весовой функции и заключается в том, что длиналюбого начала пути не больше длины самого пути, а в случае, когда путьявляется кратчайшим, то и любое его начало также является кратчайшимпутем:∀p ∈ P ⇒ p{1} 6 p;∀p ∈ Pmin ⇒ p{1} ∈ Pmin .Для заданной вершины s ∈ V необходимо найти множество Ps ⊂ Pminлокально-минимальных путей, начинающихся в вершине s. Для решения задачи построим цепочку вложенных множеств Ps0 ⊂ Ps1 ⊂ . . . ⊂ Ps :Ps0 = ∅;Ps1 = (Ps \ Ps0 )∗ ∪ Ps0 ;···Psi+1 = (Ps \ Psi )∗ ∪ Psi ;···Теорема 1. Существует n такое, что Psn = Ps .Множество Q ⊳ P = (Q ∪ P )min \ P будем называть фильтрацией множества Q относительно множества P .

Термин «фильтрация» имеет простойсмысл: пути множества Q просеиваются, при этом остаются только минимальные пути, для которых во множестве P не существует путей меньшихлибо равных данным. Продолжением множества P будем называть множество P = {p ⊂ P : p{1} ∈ P }.Теорема 2. Psi+1 = (Psi ⊳ Psi )∗ ∪ Psi .При помощи полученного рекуррентного соотношения можно найти искомое множество Ps . В этом случае количество операций сравнения будетO(|E|2 |Ps |2 ).В разделе 2.4 описывается метод фиктивных клиентов. Суть метода заключается в том, что сначала клиенты объединяются в группы, которые объявляются фиктивными клиентами. После этого решается задача на множестве фиктивных клиентов.

Очевидно, что при таком подходе возрастаетскорость решения, но при этом может понижаться качество расчета. Чтобыполностью описать метод, необходимо ответить на ряд смежных вопросов:как осуществлять группировку, как вводить расстояние между фиктивнымиклиентами, как определять их вес и время обслуживания.11Метод фиктивных клиентов является универсальным и может применяться в сочетании с произвольными алгоритмами решения ЗМТ. Варьируя размеры групп клиентов, можно легко получать новые эвристики. Данный методможет стать новым направлением для исследований.Опишем способ группировки, который используется в работе. Изначальноразбиваем клиентов на группы с одинаковыми приоритетами и зонами обслуживания. В пределах каждой группы строим минимальное остовное дерево.В качестве веса используем время передвижения по ребру.

Начиная с листьев объединяем клиентов в группы. Производим склейку до тех пор, покаэто возможно. Информацию о группе храним в виде свободных маршрутов.Благодаря возможности разбиения маршрута на сегменты удается решитьпроблему монолитности групп.Таблица 1. Зависимость длины маршрутов от размеров группыK1248R11376138914071423R21078115112461339C1940921961993C2668657676726RC11546156015891626RC21246137817151493АгентыКлиентыВ разделе 2.5 описан новый конструктивный алгоритм для решения задачи маршрутизации транспорта.

Построение начинается с расписания, в котором агенты перемещаются из точек старта в точки финиша. Добавлениеклиентов в маршруты происходит итерационно. На каждом шаге алгоритмастроится двудольный граф, одна доля которого — множество агентов, другаядоля — множество необслуженных клиентов. Вес ребер определяется как изменение целевой функции ∆if (r).

Целевая функция является многомерной,поэтому рассматривается только значения ненулевых компонент вектора сминимальным индексом i. Клиенты с нулевым изменением соответствующейкомпоненты выбрасываются из рассмотрения. Затем решается задача о назначениях при помощи венгерского алгоритма. Время работы описанного алгоритма составляет O(m2 n), где n — количество клиентов, m — количествоагентов.Рис.

4. Распределение клиентов между агентамиПрименение задачи о назначениях может служить основой и для другихэвристик, например, для параллельной эвристики PFIH (Potvin, 1995).12Таблица 2. Сравнение результатов различных эвристик начального построенияАлгоритмТекущийIoannou (2001)Solomon (1987)R1137613701436R2107813101402C1940865951C2668662692RC1154615121596RC2124614831682В разделе 2.6 описывается процедура обмена сегментов маршрутов. Данная операция является трудоемкой, но в то же время достаточно часто применяется для задач маршрутизации. При помощи обменов сегментов можнокак производить вставку новых клиентов, так и выполнять оптимизацию существующих маршрутов.Общая схема оптимизации заключается в том, что из всех способов обмена сегментов маршрутов выбирается оптимальный, и только после этогопроизводится сам обмен.

Описанная процедура повторяется до тех пор, пока происходит улучшение целевой функции. Оценим трудоемкость даннойсхемы.Пусть n — количество клиентов в рассматриваемых маршрутах. Тогдаобщее количество сегментов будет O(n4 ). На практике, чтобы уменьшить количество сегментов до O(n2 ), обычно ограничивают их длину некоторой константой. Так как операция обмена требует O(n) времени, суммарное времясоставляет O(n3 ). В диссертации предлагается способ ускорения этой фазыдо O(n log2 n).Чтобы быстро оценивать корректность операций обмена, необходимо уметьбыстро вычислять характеристики сегментов маршрутов. Для линейных параметров, таких как суммарные характеристики объектов, достаточно длякаждого клиента хранить суммарные характеристики маршрута, заканчивающегося в нем. Для быстрого пересчета зон обслуживания нужно для каждого клиента создать отображение, которое задает суммарное количество клиентов в маршрутах, попадающих в указанную зону.

Аналогично можно пересчитывать приоритеты клиентов. Для учета ограничений по времени будемдля каждого клиента хранить минимальное tmin и максимальное tmax время начала обслуживания. Хранить информацию о маршрутах будем в виденеявного декартова дерева с дополнительными операциями дерева отрезков.Теорема 3. При описанном способе хранения информации о маршрутахоперация обмена выполняется за время O(log2 n).При обмене сегментов значение целевой функции изменяется благодарятому, что пара ребер AD и BC заменяется на пару ребер AC и BD. Ребра,по которым происходит обмен, будем называть разрезом.

Значениеt(AC) + t(BD) − t(AD) − t(BC)назовем величиной разреза. Таким образом, наша задача сводится к поискупары сегментов, у которых суммарная величина разрезов максимальна.13ACBDРис. 5. Обмен сегментов маршрутовЧтобы операция обмена оказалась корректной, времена посещения клиентов A, C и B, D должны быть примерно одинаковыми.

Будем считать, чторазрез удовлетворяет этому требованию, если выполняется условие фильтрации[tmin(A), tmax(C)] ∩ [tmin(B), tmax(D)] 6= ∅.Теорема 4. В плотных маршрутах (в которых время простоя агентов близко к нулю) количество разрезов, удовлетворяющих условию фильтрации, непревосходит O(n).С увеличением количества клиентов в маршрутах, время простоя агентовуменьшается, следовательно, время работы фазы оптимизации для плотныхмаршрутов составляет O(n log2 n).Вставка новых клиентов в маршрут является частным случаем операцииобмена сегментов и осуществляется по схеме, описанной выше.В разделе 2.7 описывается способ минимизации общего количества задействованных агентов. Будем по очереди исключать агентов из рассмотрения.Для этого маршрут агента объявим свободным и всех клиентов будем считать необслуженными. Затем произведем оптимизацию при помощи обменовсегментов маршрутов.

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

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

Характеристики

Список файлов диссертации