автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей

На нравах рукописи

Чернышев Сергей Владленович

Модели, методы и алгоритмы эффективного

решения задачи маршрутизации транспорта на графах больших размерностей

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2011

- 1 ДЕК 2011

005004261

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

Научный руководитель:

кандидат технических наук, доцент Чеповский Андрей Михайлович

Официальные оппоненты:

доктор физико-математических наук, профессор Старков Сергей Олегович

кандидат технических наук Гаврилов Александр Викторович

Ведущая организация:

Московский физико-технический институт (Государственный университет)

Защита состоится 21 декабря 2011 года в 12 часов 00 мин. на заседании диссертационного совета Д 212.048.09 при Национальном исследовательском университете «Высшая школа экономики» по адресу: 105187, Москва, ул. Кирпичная, д. 33, ауд. 505.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики».

Автореферат разослан « ноября 2011 г.

Ученый секретарь диссертационного совета доктор технических наук

В.А. Фомичев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Первые приближенные алгоритмы были созданы в 1970-х годах (Clarke G., Wright J.W.). В 1980-е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook Т., Rüssel R.A., Christofides N., Mingozzi A., Toth Р.). С середины 1990-х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau M., Osman I.H., Matsuyama Y.). В последние десять лет исследования склонились в сторону обработки сложных видов ограничений (Frazzoli Е., Bullo F.).

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

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

Задачами исследования являются:

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

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

Методы исследования. В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов.

Научная новизна. В диссертации получены следующие основные научные результаты, которые выносятся на защиту:

1. Предложен и исследован приближенный алгоритм для построения Па-рето-минимальных путей в двумерном случае.

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

3. Предложен метод фиктивных клиентов для снижения размерности задачи.

4. Создан и исследован алгоритм построения начального приближения, основанный на решении задачи о назначениях.

5. Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с 0(п) до 0(1оц2 п), где п — общее количество клиентов в маршрутах.

6. С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано, что выполнение данного условия позволяет сократить количество разрезов с 0(п2) до 0(п).

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

Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке С++ и протестированы в операционных системах Windows, Linux. Для практического использования создана динамическая библиотека, которая в настоящее время внедрена в программном комплексе PlanVidia.

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

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

1. Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 2000

2. Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2001

3. Научная конференция «Ломоносовские чтения», Москва, 2003

4. Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2005

5. Международный семинар по компьютерной алгебре и информатике, Москва, 2005

6. Шестая международная конференция памяти академика А.П. Ершова «Перспективы систем информатики», Новосибирск, 2006

7. Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2008

Публикации. Основные результаты работы изложены в 10 научных статьях, среди которых 6 — в тезисах докладов [3-5,7-9], 3 — в рецензируемых российских периодических изданиях [1,2,6], из которых 2 статьи [1,2] опубликованы в журналах из списка ВАК и 1 статья в международном рецензируемом журнале [10].

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 115 страницах, содержит 39 иллюстраций. Библиография включает 113 наименований.

Автор выражает глубокую признательность к.ф.-м.н, в.н.с. Панкратьеву Евгению Васильевичу за научные консультации и поддержку.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведен подробный обзор задач маршрутизации транспорта (ЗМТ) и известных алгоритмов ее решения.

В разделе 1.1 рассматриваются ЗМТ с дополнительными ограничениями, приводится их классификация.

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

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

В разделе 1.4 приводится классификация Кордо, согласно которой все алгоритмы разбиваются на четыре фазы: построение начального приближения, локальная оптимизация, глобальная оптимизация, машинное обучение. Каждая фаза рассматривается отдельно. Приводится обзор конструктивных алгоритмов (Моля-Джеймсона, Кларка-Райта, Кристофидеса-Монгоззи-Тасса), кластерных алгоритмов (Фишера-Джекумера, Брамера-Симчи-Леви) и алгоритмов для оптимизации отдельных маршрутов, основанных на А-обменах Османа. Рассматриваются генетические алгоритмы и методы машинного обучения (метод эластичных сетей, метод самоорганизующейся карты, метод муравьиных колоний).

В разделе 1.5 содержатся выводы по первой главе. В течение прошлого десятилетия большое количество успешных и чрезвычайно эффективных эвристик были предложены для решения ЗМТ с временными окнами. Новые подходы дают все более точные результаты. Но при этом большинство

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

В 2005 году Olli Bräysy для ЗМТ с временными окнами провел сравнительный анализ скорости и качества работы известных алгоритмов для 100 клиентов. Позже в 2010 году Michel Gendreau провел аналогичное тестирование для 1000 клиентов. Результаты экспериментов приведены на рис. 1. Эти исследования показали, что только конструктивные алгоритмы обладают высокой производительностью. Алгоритмы, в которых используются дополнительные этапы оптимизации, дают более точные результаты, но существенно проигрывают по скорости работы. Таким образом, алгоритмы делятся на две группы: либо обладающие высокой производительностью, либо высокой эффективностью оптимизации (по количеству задействованных агентов, по суммарной длине маршрутов). Данная работа посвящена разработке алгоритмов, которые обладали бы такой же производительностью как конструктивные алгоритмы, но более высокой степенью оптимизации.

57.9 57.8 57.7 57.6 57.5 57.4 57.3 57.2 57.1 57.0;

O Braysy et al. (2004) r

O Gehring and Homberger (1999) |_

O Homberger and Gehring (2005) i

O Le Bouthillier and Crainic (2005) O Gehring and Homberger (2001, 2002) O Le Bouthillier et al. (2005)

Быстрые алгоритмы Эффективные алгоритмы

I Многофазный алгоритм*

О Pisinger and Röpke (2006) О Ibaraki et al. (2008)

Hashimoto and Yagiura (2008)

"0 25 50 75 100 125 150 175 200 225 Рис. 1. Сравнительная характеристика работы алгоритмов на тестовых примерах, содержащих 1000 клиентов. По оси абсцисс — среднее время работы алгоритма в минутах, по оси ординат — среднее количество задействованных агентов.

* — многофазный алгоритм, описанный в диссертационной работе

Во второй главе приводятся основные результаты работы.

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

Опишем исходные данные:

• Ориентированный граф G = (V,E), определяющий топологию дорожной сети. На ребрах графа определены весовые функции, которые задают длину ребер d : Е —> R+ и время движения по ребру t: Е —> R+.

• Множество клиентов С, для которых задано местоположение v : С V, интервал времени работы ts,tf : С —> R.+, характеристики товаров q : С —У R+, приоритет р : С N+.

• Множество агентов А. Для агентов задано местоположение в начале и конце маршрута vs, Vf : А —> V, зона обслуживания z : А х С —> {0,1}, интервал времени работы ts, tf : А —» R+, ограничения на суммарные характеристики товаров qmax : А —> Rij..

Множество всевозможных путей в графе обозначим Р. График посещения клиентов назовем маршрутом агента. Каждый маршрут задается последовательностью клиентов {с;} и временами их посещения {¿¡}. Пусть R — множество всевозможных маршрутов. Маршрут г 6 R агента а 6 А будем называть корректным, если выполнены ограничения:

• по интервалу времени работы агента

[t.(r),t,(r)] С [ts(a),tf(a)],

• по интервалу времени обслуживания

U 6 [ts(ci),tf(ci)],

• по грузоподъемности

Ч^') ^ Чтах(а),

i

• по ограничениям на зоны обслуживания

z (а,С{) = 1.

Рассмотрим маршрут г € R. Обозначим через пр(г) количество клиентов в маршруте с приоритетом р. Введем многомерную целевую функцию:

f(r) = (n1(r),...,ni)(r),-t(r),-d(r)).

При сравнении значений целевой функции будем использовать лексикографический порядок. Множество маршрутов агентов назовем расписанием. Множество всевозможных расписаний обозначим S. Определим целевую функцию расписания s 6 S:

f(s) = £fM-

res 8

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

В разделе 2.2 приводится общая схема работы алгоритма, которую можно представить в виде диаграммы:

Рис. 2. Многофазный алгоритм

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

В разделе 2.3 описывается построение редуцированного графа. Это ориентированный граф С = (У,Е'), в котором V' = у(С) и у8(А) и ^(А) — множество выделенных вершин, а Е' С V' х V' — пути в исходном графе в. Редуцированный граф является аналогом матрицы расстояний между клиентами. Переход от исходного графа С к редуцированному графу С позволяет снизить размерность задачи.

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

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

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

Сведем задачу к одномерной. Введем новую весовую функцию, зависящую от параметра Л € [0,1]:

w(e) = Ad(e) + (1 - A)t(e).

Зафиксируем значение А. Решим задачу о поиске кратчайшего пути в графе. Найденный путь будет оптимальным для двумерной задачи. Чтобы сформировать искомый набор оптимальных путей, будем варьировать параметр А. Рассмотрим множество оптимальных путей Для каждого i построим

график функции Wi(А) = Аdi + (1 — A)t,-. Рассмотрим нижнюю часть плоскости, ограниченную данными графиками. Граница полученной фигуры будет ломаной линией. Вершины этой ломаной позволяют найти искомые значения параметра А.

Будем строить границу фигуры постепенно. Найдем параметры путей при А1 — 0 и Аг = 1. Построим графики функций ■Ш1,и>2- Найдем точку пересечения — значение а3. Вычислим оптимальный путь, построим график функции адз. Найдем значения А4 и а5. Продолжим процесс до тех пор, пока не наберем нужное количество оптимальных путей.

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

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

На множестве путей Р зададим отношение частичного порядка Подмножество минимальных элементов множества Р С Р будем обозначать Р*. Подмножество путей, начинающихся в вершине и, а заканчивающихся в вершине V, будем обозначать Ри„. Множество Ртт = Уц Р*и будем называть множеством локально-минимальных путей. Необходимо найти все локально-минимальные пути, начинающиеся в заданной вершине.

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

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

Ур р{1} < р;

Vр 6 Р™" => р{1} € РтЫ.

Для заданной вершины я 6 V необходимо найти множество Р„ С Ртт локально-минимальных путей, начинающихся в вершине е. Для решения задачи построим цепочку вложенных множеств С Рд1 С ... С Р3:

К+1 = (Р, \ Р1У и

Теорема 1. Существует п такое, что Р™ = Р3.

Множество <2 <Р = (<5 и Р)тш \ Р будем называть фильтрацией множества С} относительно множества Р. Термин «фильтрация» имеет простой смысл: пути множества <3 просеиваются, при этом остаются только минимальные пути, для которых во множестве Р не существует путей меньших либо равных данным. Продолжением множества Р будем называть множество Р = {р С

Р : р{!> е Р}.

Теорема 2. Р'+1 = (Р| < Р')* и Р'.

При помощи полученного рекуррентного соотношения можно найти искомое множество Ря. В этом случае количество операций сравнения будет 0(|Е|2|Р8|2).

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

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

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

Таблица 1. Зависимость длины маршрутов от размеров группы

К М Й2 С1 С2 ЙС1 ЙС2

1 1376 1078 940 668 1546 1246

2 1389 1151 921 657 1560 1378

4 1407 1246 961 676 1589 1715

8 1423 1339 993 726 1626 1493

В разделе 2.5 описан новый конструктивный алгоритм для решения задачи маршрутизации транспорта. Построение начинается с расписания, в котором агенты перемещаются из точек старта в точки финиша. Добавление клиентов в маршруты происходит итерационно. На каждом шаге алгоритма строится двудольный граф, одна доля которого — множество агентов, другая доля — множество необслуженных клиентов. Вес ребер определяется как изменение целевой функции Д^г). Целевая функция является многомерной, поэтому рассматривается только значения ненулевых компонент вектора с минимальным индексом г. Клиенты с нулевым изменением соответствующей компоненты выбрасываются из рассмотрения. Затем решается задача о назначениях при помощи венгерского алгоритма. Время работы описанного алгоритма составляет 0(т2п), где п — количество клиентов, т — количество агентов.

Рис. 4. Распределение клиентов между агентами

Применение задачи о назначениях может служить основой и для других эвристик, например, для параллельной эвристики РИН (Ро1;ут, 1995).

Алгоритм R1 R2 CI C2 RC1 RC2

Текущий 1376 1078 940 668 1546 1246

Ioannou (2001) 1370 1310 865 662 1512 1483

Solomon (1987) 1436 1402 951 692 1596 1682

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

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

Пусть п — количество клиентов в рассматриваемых маршрутах. Тогда общее количество сегментов будет 0(п4). На практике, чтобы уменьшить количество сегментов до 0[п2), обычно ограничивают их длину некоторой константой. Так как операция обмена требует 0(п) времени, суммарное время составляет 0(п3). В диссертации предлагается способ ускорения этой фазы до 0(nlog2ra).

Чтобы быстро оценивать корректность операций обмена, необходимо уметь быстро вычислять характеристики сегментов маршрутов. Для линейных параметров, таких как суммарные характеристики объектов, достаточно для каждого клиента хранить суммарные характеристики маршрута, заканчивающегося в нем. Для быстрого пересчета зон обслуживания нужно для каждого клиента создать отображение, которое задает суммарное количество клиентов в маршрутах, попадающих в указанную зону. Аналогично можно пересчитывать приоритеты клиентов. Для учета ограничений по времени будем для каждого клиента хранить минимальное tm;n и максимальное tmax время начала обслуживания. Хранить информацию о маршрутах будем в виде неявного декартова дерева с дополнительными операциями дерева отрезков.

Теорема 3. При описанном способе хранения информации о маршрутах операция обмена выполняется за время 0(log2n).

При обмене сегментов значение целевой функции изменяется благодаря тому, что пара ребер AD и ВС заменяется на пару ребер АС и BD. Ребра, по которым происходит обмен, будем называть разрезом. Значение

t{AC) +1(BD) - t{AD) - t(BC)

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

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

[ит(Л),иах(С)] п [^п(В)^гаах(£>)] ф 0.

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

С увеличением количества клиентов в маршрутах, время простоя агентов уменьшается, следовательно, время работы фазы оптимизации для плотных маршрутов составляет 0(пк^2п).

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

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

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

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

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

Обозначим Ei € Е' — подмножество ребер, соединяющих г-го и (г + 1)-го клиентов. Разобьем отрезок [ts(r), tf(r)] на п равных частей точками ti = ("~1)t'W+ltf(r)- Обозначим d[i, j] длину корректного кратчайшего маршрута, соединяющего первые j клиентов, время движения вдоль которого не превосходит i,-. Если указанного маршрута не существует, будем считать, что функция не определена. Значения d[i',j + 1] будем пересчитывать динамически по значениям d[z,j], поочередно перебирая ребра Ег. Если воспользоваться тем, что d[i,j] — невозрастающая функция по первому параметру, можно каждое ребро Ei рассматривать не более одного раза. Следовательно, общее время работы будет 0(пк + т), где к — общее количество клиентов, т = \Eq\ + ... + |i?it| — суммарное количество ребер. Значение параметра п нужно выбирать максимально большим, но так, чтобы этот этап оптимизации выполнялся достаточно быстро. Поскольку большинство состояний недостижимы, на практике алгоритм работает значительно быстрее, чем предполагает теоретическая оценка.

В разделе 2.9 содержатся выводы по второй главе. Стоит отметить, что все фазы алгоритма независимо друг от друга могут применяться как составные части для построения новых или оптимизации существующих алгоритмов решения ЗМТ. Техника ускорения операции обмена сегментов маршрутов может применяться для таких операторов как 2-Opt, Or-Opt, 2-Opt*, Relocate, Exchange, Cross-Exchange и Geni-Exchange, которые широко используются в настоящее время. Кроме этого, для алгоритмов, использующих случайные преобразования (метаэвристики), можно уменьшить количество некорректных преобразований, осуществляемых в процессе формирования окрестности решения, и, как следствие, ускорить их работу.

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

Алгоритмы, описанные в данной работе, были реализованы в программном продукте PlanVidia, общая информация о котором приводится в разделе 3.1.

Р1апУ1&а была разработана с ориентацией на крупные обслуживающие организации, работающие в регионах с большим географическим разбросом. Эта система позволяет определить минимальное количество агентов для ежедневного обслуживания сотен клиентов с учетом их географического местоположения, временных ограничений и приоритетов. Р1апУ1сНа поддерживает и упрощает работу диспетчера при помощи интерактивного графического интерфейса. Основные возможности Р1ап\^сНа: долгосрочное и краткосрочное планирование, оптимальное распределение нагрузки в течение рабочего дня, оптимальное планирование в соответствии с бизнес-логикой, динамическое планирование, анализ и контроль расписания.

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

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

Рис. 7. Архитектура системы

Каждая подсистема, в свою очередь, состоит из компонент. Перечислим наиболее важные из них: Threading — управление потоками. Remoting — взаимодействие работы компонент, Logging — централизованный сбор информации и запись в лог-файл, ProjectServer — менеджер проектов, Cache — кеширование данных. MapRepository менеджер карт, JobManager балансер нагрузки, JobProcessor — менеджер задач, Solver — расчетный модуль, ThickClient — клиент для доступа к информации, расположенной на сервере, ProjectManager — компонент, обеспечивающий взаимодействие сервера проектов и пользовательского интерфейса.

В разделе 3.3 рассматриваются вопросы подготовки исходных данных.

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

J ^- t '1' Í

—1-г- - © ф tr—

Рис. 8. Запрещенные и разрешенные маневры

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

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

«1

#

Рис. 9. Построение расчетного графа

Информация о клиентах поступает в виде СРБ-координат или точных адресов. Необходимо осуществить привязку к графу дорог. Привязка осуществляется к основанию проекции.

В четвертой главе приводятся результаты тестирования. В разделе 4.1 описывается процедура тестирования, в разделе 4.2 приводятся примеры проектов. В разделе 4.3 описываются результаты визуального тестирования. В разделе 4.4 приводятся результаты экспериментов. В разделе 4.5 содержатся основные выводы по данной главе:

1. При сопоставлении полученных данных с результатами, опубликованными в работе Michel Gendreau (2010), было показано, что многофазный алгоритм обладает как высокой скоростью работы, так и высокой степенью оптимизации.

2. При тестировании алгоритма на задачах большой размерности, содержащих от 5000 до 10000 клиентов, максимальное время работы составило 94 минуты. Полученные результаты доказывают возможность практического использования многофазного алгоритма.

Рис. 10. Привязка клиентов к графу дорог

3. При вариации вспомогательных параметров на фиксированных входных данных были получены следующие результаты:

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

• Неиспользованное время работы агентов составило не более 6% от общего времени.

• Показано, что при увеличении числа клиентов в решении суммарная длина маршрутов уменьшается, то есть оптимизация транспортных расходов неявно происходит на всех этапах работы алгоритма.

4. Для задач с высокой плотностью клиентов для оценки полученного расписания вводится понятие эффективность — отношение суммарного времени обслуживания к суммарному времени работы агентов. Для задач массового обслуживания суммарная эффективность оказалась не менее 85%.

5. При сопоставлении расчетных и фактических данных среднее отклонение по числу клиентов составило 15%, по длине — 8%.

6. Компания СарАЛсНа проводила независимое тестирование программного продукта Р1апУ1сПа. Проверка осуществлялась на задачах от 7 разных поставщиков данных. Количество клиентов варьировалось от 1000 до 5000. Время расчета составило от 30 до 60 минут. Полученные результаты были одобрены заказчиками и с некоторыми из них были достигнуты договоренности о промышленной эксплуатации Р1апУ1сИа. В настоящее время существует несколько промышленных инсталляций Р1апУМ1а.

7. В рамках программы СКИФ союзного государства проводились испытания по распараллеливанию алгоритмов построения редуцированного графа. В ходе испытаний коэффициенты утилизации суммарной частоты процессоров оказались не ниже 50% на 20-ти процессорном кластере. Полученные результаты доказывают возможность распараллеливания алгоритмов, описанных в работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

Созданы и исследованы новые алгоритмы и методы:

1. Приближенный алгоритм решения бикритериальной задачи о поиске кратчайших путей.

2. Псевдополиномиальный алгоритм для решения задачи о поиске кратчайших путей на графах с произвольно заданным частичным порядком.

3. Алгоритм построения начального приближения, основанный на решении задачи о назначениях.

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

5. Метод фиктивных клиентов. Улучшены существующие результаты:

6. Разработана структура данных для быстрого выполнения обменов сегментов маршрутов. Скорость работы возросла с 0(п) до 0(\о%2 п).

7. При помощи разрезов и условия фильтрации ускорена процедура поиска оптимальных обменов сегментов маршрутов с 0(п3) до 0{п к^2 п).

Разработаны программные продукты:

8. Программный комплекс Р1апУ1с11а для практического решения задач маршрутизации с временными окнами и дополнительными ограничениям.

В работе рассмотрены задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями, приведен обзор научных публикаций за последние 40 лет. Опубликованы научные работы [1-10].

Практические исследования доказывают высокую скорость работы и практическую значимость полученных алгоритмов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В

РАБОТАХ

Публикации в журналах, входящих в перечень ВАК:

1. Чернышев C.B. Локальная оптимизация путей в задачах маршрутизации автотранспорта с временными окнами // УМН. 2009. Т. 64, № 1. С. 165-166.

2. Чернышев C.B. Обобщение многокритериальной задачи о нахождении кратчайших путей в ориентированном графе // Вестник МГУ. Сер. 1, Математика. Механика. 2007. № 6. С. 1-8.

Другие публикации:

3. Бабенко М.А., Панкратьев Е.В., Чеповский A.M., Чернышев C.B. Оптимизационные задачи на графах, возникающие в транспортной логистике // Перспективы систем информатики: шестая международная конференция памяти академика А.П. Ершова. Рабочий семинар «Наукоемкое программное обеспечение» (Новосибирск, Академгородок, 28-29 июня 2006 г.). Новосибирск: изд-во института систем информатики СО РАН, 2006. С. 31-32.

4. Инюхин A.B., Панкратьев Е.В., Чеповский A.M., Чернышев C.B. Использование Т-системы для преобразования графа дорог в задаче оптимизации маршрутов движения // Высокопроизводительные вычисления и их приложения: труды Всерос. науч. конф. (Черноголовка, 30 октября - 2 ноября 2000 г.). М.: изд-во МГУ, 2000. С. 220-223.

5. Лахно А.П., Чернышев C.B. Модификация метода Османа в задачах маршрутизации автотранспорта с временными окнами // Технологии Microsoft в теории и практике программирования: труды V Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 1-2 апр. 2008 г.) М.: Вузовская книга, 2008. С. 229-230.

6. Панкратьев Е.В., Чеповский A.M., Черепанов Е.А., Чернышев C.B. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей // Фундаментальная и прикладная математика. 2003. Т. 9, Xs 1. С. 235-251.

7. Панкратьев Е.В., Чеповский A.M., Черепанов Е.А., Чернышев C.B. Нахождение наборов оптимальных маршрутов на больших сетках дорог геоинформационных систем // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: материалы 10 междунар. науч.-техн. конф. (Рязань, 14-16 ноября 2001 г.). Рязань: изд-во Рязанской гос. радиотехн. акад., 2001. С. 240-241.

8. Чернышев С.В. Обобщение задачи нахождения кратчайших путей в ориентированном графе // Технологии Microsoft в теории и практике программирования: труды Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 17-18 февр. 2005 г.). М.: изд-во МГТУ им. Н. Э. Баумана, 2005. С. 138.

9. Чернышев С.В. Построение начального приближения в задаче маршрутизации с ограничениями по времени и другими вспомогательными условиями // Технологии Microsoft в теории и практике программирования: труды Всерос. конф. студентов, аспирантов и молодых ученых (Москва, 2-3 марта 2006 г.). М.: изд-во МГТУ им. Н. Э. Баумана, 2006. С. 139.

10. Chepovskii A.M., Cherepanov Е.А., Chernyshev S.V. Pankratiev E.V., Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs // Journal of Mathematical Sciences. 2005. Vol. 128, № 6. P. 3487-3495.

Лицензия ЛР № 020832 от «15» октября 1993 г. Подписано в печать 16 ноября 2011г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1.

Тираж 100 экз. Заказ № 127 Типография издательства ГУ-ВШЭ, 125319, г. Москва, Кочновский пр-д., д. 3

Введение

1 Обзор существующих алгоритмов решения ЗМТ

1.1 Классификация ЗМТ .И

1.2 Методы оптимизации

1.2.1 Метод ветвей и границ.

1.2.2 Методы линейной оптимизации.

1.2.3 Генетические алгоритмы.

1.2.4 Метод имитации отжига.

1.2.5 Поиск с запретами.

1.3 Классификация Фишера.

1.4 Классификация Кордо.

1.4.1 Построение начального приближения.

1.4.2 Локальная оптимизация приближения.

1.4.3 Глобальная оптимизация

1.4.4 Машинное обучение.

1.5 Выводы.

2 Многофазный алгоритм

2.1 Постановка задачи.

2.2 Общая схема работы алгоритма

2.3 Построение редуцированного графа.

2.3.1 Одномерный случай.

2.3.2 Двумерный случай.

2.3.3 Многомерный случай

2.4 Метод фиктивных клиентов.

2.5 Построение начального приближения.

2.6 Обмен сегментов маршрутов.

2.6.1 Ускорение операции обмена сегментов.

2.6.2 Поиск оптимального обмена сегментов.

2.7 Разгрузка агентов.

2.8 Постобработка.

2.9 Выводы.

3 Аспекты реализации

3.1 Система Р1апУ1сНа.

3.2 Архитектура РкпУМа.4.

3.2.1 Эксплуатация системы.

3.2.2 Основные части системы

3.2.3 Назначение системы.

3.2.4 Функциональность системы.

3.2.5 Внутренняя структура системы.

3.2.6 Расчетный модуль.

3.2.7 Потоки данных.

3.3 Формирование исходных данных.

3.3.1 Построение графа дорог.

3.3.2 Геокодирование.

4 Практические результаты

4.1 Процедура тестирования

4.1.1 Открытое тестирование.

4.1.2 Внешнее тестирование.

4.2 Примеры проектов.

4.2.1 Антверпен.

4.2.2 Бельгия.

4.3 Визуальное тестирование.

4.3.1 Обслуживание изолированных клиентов.

4.3.2 Распределение кластеров между агентами.

4.3.3 Привязка клиентов к ребрам графа.

4.4 Результаты экспериментов

4.4.1 Алгоритм начального построения

4.4.2 Зависимость результатов от размеров групп

4.4.3 Тестовые наборы Геринга и Хомбергера.

4.4.4 Задачи большой размерности.

4.4.5 Вариация параметров оптимизации

4.4.6 Эффективность оптимизации.

4.4.7 Сравнение расчетных данных с экспериментальными

4.4.8 Проекты компании СарУ1(На.

4.4.9 Параллельные вычисления.

4.5 Выводы.

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

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

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

Рассматриваемый класс задач представляет интерес с научной точки зрения. В данном направлении на протяжении последних сорока лет ведутся интенсивные исследования [7,28,30,33-36,39,44,46,47,49, 50,52-57,59-61,67,69-74,77,80,83,85-88,90-93,95,96,99,100,103-107, 109,111]. Огромное количество входных параметров, с одной стороны, делают задачу настолько сложной, что многие существующие алгоритмы либо не применимы, либо плохо адаптируемы к практике. С другой стороны, эта же особенность предоставляет простор для новых исследований.

Первые приближенные алгоритмы были получены в 1970-х годах (Clarke G. [39], Wright J.W. [61]). В 1980-е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook Т., Rüssel R.A., Christofides N., Mingozzi A., Toth P. [44, 107]). С середины 1990-х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau M., Osman I.H., Matsuyama Y. [7,28,34,35,86,90,100]). В последние десять лет исследования склонились в основном в сторону обработки сложных видов ограничений (Frazzoli Е., Bullo F. [30,50,56]).

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

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

Задачами исследования являются:

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

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

Методы исследования. В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов.

Научная новизна. В диссертации получены следующие основные новые результаты, которые выносятся на защиту:

1. Предложен и исследован приближенный алгоритм для построения Парето-минимальных путей в двумерном случае.

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

3. Предложен метод фиктивных клиентов для снижения размерности задачи.

4. Создан и исследован алгоритм построения начального приближения, основанный на решении задачи о назначениях.

5. Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с 0(п) до 0(log2n), где п — общее количество клиентов в маршрутах.

6. С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано, что выполнение данного условия позволяет сократить количество разрезов с 0(п2) до 0(п).

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

Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке С++ и протестированы в операционных системах Windows, Linux. Для практического использования создана динамическая библиотека, которая в настоящее время внедрена в программном комплексе PlanVidia.

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

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

1. Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 2000

2. Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2001

3. Научная конференция «Ломоносовские чтения», Москва, 2003

4. Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2005

5. Международный семинар по компьютерной алгебре и информатике, Москва, 2005

6. Шестая международная конференция памяти академика А. П. Ершова «Перспективы систем информатики», Новосибирск, 2006

7. Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2008

Публикации. Основные результаты работы изложены в 10 научных статьях, среди которых б — в тезисах докладов [2,9,14,19,25,27], 3 — в рецензируемых российских периодических изданиях [18,24,26], из которых 2 статьи [24,26] опубликованы в журналах из списка ВАК и 1 статья в международном рецензируемом журнале [38].

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

Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 115 страницах, содержит 39 иллюстраций. Библиография включает 113 наименований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

Созданы и исследованы новые алгоритмы и методы:

1. Приближенный алгоритм решения бикритериальной задачи о поиске кратчайших путей.

2. Псевдополиномиальный алгоритм для решения задачи о поиске кратчайших путей на графах с произвольно заданным частичным порядком.

3. Алгоритм построения начального приближения, основанный на решении задачи о назначениях.

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

5. Метод фиктивных клиентов.

Улучшены существующие результаты:

6. Разработана структура данных для быстрого выполнения обменов сегментов маршрутов. Скорость работы возросла с 0(п) до О (log2 тг).

7. При помощи разрезов и условия фильтрации ускорена процедура поиска оптимальных обменов сегментов маршрутов с 0(пъ) до 0(п log2 п).

Разработаны программные продукты:

8. Программный комплекс PlanVidia для практического решения задач маршрутизации с временными окнами и дополнительными ограничениям.

В работе рассмотрены задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями, приведен обзор научных публикаций за последние 40 лет. Опубликованы научные работы [2,9,14,18,19,24-27,38].

Практические исследования доказывают высокую скорость работы и практическую значимость полученных алгоритмов.

1. Ахо A.B., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильяме, 2000. 384 с.

2. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 336 с.

3. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2008. 330 с.

4. Вирт Н. Алгоритмы и структуры данных. СПб: Невский Диалект, 2008. 352 с.

5. Глебов Н.И., Кочетов Ю.А., Плясунов A.B. Методы оптимизации. Новосибирск: изд-во Новосиб. гос. ун-та, 2006. 105 с.

6. Еремеев A.B. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации: дисс. канд. физ.-мат. наук. Омск, 2000. 119 с.

7. Кнут Д.Э. Искусство программирования для ЭВМ. М.: Мир, 1978. 2303 с.

8. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 с.

9. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильяме, 2005. 1296 с.

10. Краснов М.В. Многокритериальная задача о кратчайших путях для всех пар узлов графа // Современные проблемы математики и информатики: сб. науч. тр. Вып. 3. Ярославль: изд-во ЯрГу, 2000. С. 62-66.

11. Лебедев С.С., Ковалевская М.И. Множители Лагранжа в простейшей задаче размещения. Исследования по дискретной оптимизации. М.: Наука, 1976. С. 170-180.

12. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 200 с.

13. Лопатин A.C. Методы отжига. Электронный ресурс. Спб, 2005. URL: http://www.cs-seminar.spb.ru/reports/52.pdf (дата обращения: 12.11.2010).

14. Панкратьев Е.В., Чеповский A.M., Черепанов Е.А., Чернышев C.B. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей // Фундаментальная и прикладная математика. 2003. Т. 9, № 1. С. 235-251.

15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1984. 512 с.

16. Растригин J1.A. Случайный поиск — специфика, этапы истории и предрассудки // Вопросы кибернетики. 1978. Вып. 33. С. 3-16.

17. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352 с.

18. Ульянов М.В. Ресурсно-эффективные компьютерные алгоритмы. Разработка и анализ. М.: Физматлит, 2008. 303 с.

19. Чернышев C.B. Локальная оптимизация путей в задачах маршрутизации автотранспорта с временными окнами // УМН. 2009. Т. 64, № 1. С. 165-166.

20. Чернышев C.B. Обобщение многокритериальной задачи о нахождении кратчайших путей в ориентированном графе // Вестник МГУ Сер. 1, Математика. Механика. 2007. № 6. С. 1-8.

21. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows / E. Taillard et al. // Transportation Science. 1997. Vol. 31. P. 170-186.

22. An algorithm for the traveling salesman problem / J. D.Little et al. // Operations Research. 1963. Vol. 11. P. 972-989.

23. An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows / O. Bráysy et al. // Transportation Science. 2008. Vol. 42, № 3. P. 371-386.

24. ArcLogistics Route: A Complete Routing and Scheduling Solution: An ESRI White Paper. October, 2004. NY: ESRI, 2004. 12 p.

25. Atserias A., Bonet M.L., Levy J. On Chvátal Rank and Cutting Plane Proofs // Electrnic Colloquium on Computational Complexity: Report. № 40. 2003. 12 p.

26. Baker E., Schaffer J. Computational experience with branch exchange heuristics for vehicle routing problem with time window constraints // American Journal of Mathematical and Management Sciences. 1987. Vol. 6, № 3,4. P. 261-300.

27. Bráysy O., Gendreau M. Vehicle Routing Problem with Time Windows, Part II: Metaheuristics // Transportation Science. 2005. Vol. 39, № 1. P. 119-139.

28. Bráysy O. Genetic Algorithms for the Vehicle Routing Problem with Time Windows // Arpakannus. 2001. Vol. 1 (special issue on Bioinformatics and Genetic Algorithms). P. 33-38.

29. Bramel J.B., Simchi-Levi D. A location based heuristic for general routing problems // Operations Research. 1995. Vol. 43, № 4. P. 649.

30. Brumbaugh-Smith J., Shier D. An empirical investigation of some bicriterion shortest path algorithms. // European Journal of Operational Research. 1989. Vol. 43, № 2. P. 216-224.

31. Chepovskii A.M., Cherepanov E.A., Chernyshev S.V. Pankratiev E.V., Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs // Journal of Mathematical Sciences. 2005. Vol. 128, № 6. P. 3487-3495.

32. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research. 1964. Vol. 12, № 4. P. 568-581.

33. Climaco J.C.N., Pascoal M.M.B. Finding non-dominated bicriteria shortest pairs of disjoint simple paths // Computers and Operations Research. 2009. Vol. 36, № 11. P. 2892-2898.

34. Colorni A. Ant system for job-shop scheduling // Belgrian Journal of Operation Research, Statistics and Computer Science. 1994. Vol. 34. P. 39-53.

35. Colorni A. Distributed optimization by ant colonies // Proceedings of the European Conference on Artificial Life. Paris: Elsevier, 1991. P. 134-142.

36. Computing many-to-many shortest paths using highway hierarchies / S. Knopp et al. // Proceedings of Workshop on Algorithm Engineering and Experiments (ALENEX 2007). New Orleans: ALENEX, 2007. P. 36-45.

37. Cook T.M., Russell R.A. A simulation and statistical analysis of stochastic vehicle routing with timing constraints // Decision Sciences. 1978. Vol. 9, № 4. P. 673-687.

38. Costa D. Ants can colur graphs // Journal of the Operational Research Society. 1997. Vol. 48. P. 275-305.

39. Csiszar S. Route Elimination Heuristic for Vehicle Routing Problem with Time Windows // Acta Polytechnica Hungarica. 2005. Vol. 2, № 2. P. 77-89.

40. Desaulniers G., Lessard F., Hadjar A. Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows // Transportation Science. 2008. Vol. 42, № 3. P. 387-404.

41. Durbin R., Willshaw D. An analogue approach to the travelling salesman problem using an elastic net method // Nature. 1987. Vol. 326, № 6114. P. 689-691.

42. Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints / T. Ibaraki et al. // Transportation Science. 2005. Vol. 39, № 2. P. 206-232.

43. Favaretto D., Moretti E., Pellegrini P. Ant colony system for a VRP with multiple time windows and multiple visits // Journal of Interdisciplinary Mathematics. 2007. Vol. 10, № 2. P. 263-284.

44. Finding cuts in the TSP: A preliminary report / Center for Discrete Mathematics & Theoretical Computer Science / D. Appletgate et al.j Piscataway, USA: DIMACS, Rutgers University, 1995. 64 p.

45. Fisher M.L., Jaikumar R. A generalized assignment heuristic for vehicle routing // Networks. 1981. Vol. 11, № 2. P. 109-124.

46. Fisher M.L., Jôrnsten K.O., Madsen O.B. Vehicle Routing with Time Windows: Two Optimization Algorithms // Operations Research. 1997. Vol. 45, № 3. P. 488-492.

47. Fisher M.L. Optimal Solution of Vehicle Routing Problems Using Minimum K-trees // Operations Research. 1994. Vol. 42, № 4. P. 626642.

48. Fisher M.L. Vehicle Routing // Handbooks in Operations Research And Management Science. Amsterdam: NorthHolland, 1995. P. 1-33.

49. Frazzoli E., Bullo F. Decentralized algorithms for vehicle routing in a stochastic time-varying environment // Decision and Control. 2004. Vol.4. P. 3357-3363.

50. Geoffrion A.M., McBride R. Lagrangian Relaxation Applied to Facility Location Problems // AIIE Transactions. 1978. Vol. 10. P. 40-48.

51. Ghaziri H. Solving routing problems by a self-organizing map // Artificial Neural Networks. Amsterdam: North-Holland, 1991. P. 829834.

52. Ghaziri H. Supervision in the self-organizing feature map: Applicaiton to the vehicle routing problem // Meta-Hueristics: Theory and Applications. Boston: Kluwer Academic Publishers, 1996. P. 651-660.

53. Gillett B.E., Miller L.R. A heuristic algorithm for the vehicle dispatch problem // Operations Research. 1974. Vol. 22, № 2. P. 340-349.

54. Glover F. Tabu Search — Part I. // ORSA Journal on Computing. 1989. Vol. 1, № 3. P. 190-206.

55. Glover F. Tabu Search — Part II. // ORSA Journal on Computing. 1989. Vol. 2, № 1. P. 4-32.

56. Goldberg A., Kaplan H., Werneck R. Reach for A: Efficient point-to-point shortest path algorithms. Technical Report MSR-TR-2005-132. Silicon Valley: Microsoft Research, 2005. 41 p.

57. Hamacher H.W., Ruzika S., Tjandra S.A. Algorithms for time dependent bicriteria shortest path problem // Discrete Optimization. 2006. Vol. 3, № 3. P. 238-254.

58. Hansen P. Bicriterion path problems // Lectures Notes in Economics and Mathematical Systems. 1979. Vol. 177. P. 109-127.

59. Heuristic Method for Vehicle Routing Problem with Time Window / K. C.Tan et al. // Artifical Intelligence in Engineering. 2000. Vol. 15. P. 281-285.

60. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann-Arbor: University of Michigan Press, 1975. 183 p.

61. Irnich S. A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics // INFORMS Journal on Computing. 2008. Vol. 20, № 2. P. 270-287.

62. K-Path Cuts for the Vehicle Routing Problem with Time Windows / N. Kohl et al. // Proceedengs of NOAS'97. Copenhagen: Copenhagen University, 1997. P. 307-340.

63. Kallehaug B. Larsen J. Madsen O.B., Lagrangean Duality Applied On Vehicle Routing With Time Windows // Informatics and Mathematical modelling: Technical Report. Kgs. Lyngby: Technical University of Denmark, 2001. 34 c.

64. Kawamura H. Cooperative search based on pheromone communication for vehicle routing problems // IEEE Transactions on Fundmentals of Electronics, Communications and Computer Sciences. 1998. Vol. E81-A, № 6. P. 1089-1096.

65. Kim K., Kim S., Sahoo S. Waste collection vehicle routing problem with time windows // Transportation Science. 2005. Vol. 39, № 1. P. 119-139.

66. Kindervater G., Savelsbergh M.W. Vehicle routing: Handling edge exchanges // Local Search in Combinatorial Oprimization. Chichester: Wiley, 1997. P. 337-360.

67. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing // Science. 1983. Vol. 20, № P. .-671.680

68. Kohonen T. Self-Jrganization and Associative Memory. Berlin: Springer-Verlag, 1988. 312 p.

69. Kolen A.W., Ran A.H., Trienekens H.W. Vehicle Routing with Time windows // Operations Research. 1987. Vol. 35, № 2. R 266-273.

70. Land A.H., Doig A.G. An autmatic method of solving discrete programming problems // Econometrica. 1960. Vol. 28. R 497-520.

71. Levine M.S. Finding the Right Cutting Planes for the TSP // Proceedings of Algorithm Engineering and Experimentation, International Workshop (ALENEX'99). Baltimore: Springer, 1999. P. 266-281.

72. Lim A., Zhang X. A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows // INFORMS Journal on Computing. 2007. Vol. 19, №3. P. 443-457.

73. Martins E.Q. On a multicriteria shortest path problem // European Journal of Operational Research. 1984. Vol. 16, № 2. P. 236-245.

74. Martins E.Q.V., Santos J.L.E. The labelling algorithm for the multiobjective shortest path problem: Internal Technical Report. / CISUC, Departamento de Matemática, Universidade de Coimbra, Portugal. 1999. 24 p.

75. Matsuyama Y. Self-organization via competition, cooperation and categorization applied to extended vehicle routing problem // Proceedings of the International Joint Conference on Neural Network. Seattle: WA, 1991. P. 385-390.

76. Mote J., Murthy I., Olson D.L. A parametric approach to solving bicriterion shortest path problems // European Journal of Operational Research. 1991. Vol. 53, № 1. P. 81-92.

77. Mukai N., Feng J., Watanabe T. Heuristic Approach Based on Lambda-Interchange for VRTPR-Tree on Specific Vehicle Routing Problem with Time Windows . // LNAI. 2004. Vol. 3029. P. 229238.

78. New heuristics for the vehicle routing problem / J. F.Cordeau et al. // Logistics Systems: Design and Optimization. New York: Springer, 2005. P. 279-297.

79. Ohlmann J.W., Fry M.J., Thomas B.W. Route Design for Lean Production Systems // Transportation Science. 2008. Vol. 42, № 3. P. 352-370.

80. Oliver I.M., Smith D.J., Holland J.R. A Study of Permutation Crossover Operations on the Traveling Salesman Problem // Proc. 2nd Int. Conf. on Genetic Algorithm. Hillsdale, NJ: Lawrence Erlbaum Associates, 1987. P. 224-230.

81. Ombuki B., Ross B.J., Hanshar F. Multi-objective Genetic Algorithms for Vehicle Routing Problem with Time Windows // Applied Intelligence. 2006. Vol. 24, № 1. P. 17-30.

82. Osman I.H. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem // Annals of Operations Research. 1993. Vol. 41, № 4. P. 421-452.

83. Potvin J.Y., Rousseau J.M. An exchange heuristic for routing problems with time windows // Journal of Operational Research Society. 1995. Vol. 46. P. 1433-1446.

84. Renaud J., Bostor F.F., Laporte G. An improved petal heuristic for the vehicle routing problem // Journal of Operational Research. 1995. Vol.47. P. 329-336.

85. Rüssel R.A. An effective heuristics for the m-tour travelling salesman problem with some side conditions. // Operations Research. 1977. Vol. 25. P. 517-524.

86. Savelsbergh M.W. An efficient implementation of local search algorithms for constrained routing problem // European Journal of Operational Research. Vol. 47, № 1. 1990. P. 75-85.

87. Savelsbergh M.W.P. Local search in routing problems with time windows // Annals of Operations Research. 1985. Vol. 4, № 1. P. 285305.

88. Schwefel H.P. Numerical optimization of computer models. New York: John Wiley & Sons, Inc., 1981. P. 389.

89. Schultes D. Fast and exact shortest path queries using highway hierarchies: Master's thesis. Universität des Saarlandes, 2005. 68 p.

90. Shaw P. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems // Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. London: Springer-Verlag, 1998. P. 417-431.

91. Sigauke C., Talukder H.M. A Modified Osman's Simulated Annealing and Tabu Search Algorithm for the Vehicle Routing Problem // Asor bulletin. 2003. Vol. 22, № 3. P. 9-14.

92. Skriver A.J.V. A classifications of bicriterion shortest path (bsp) algorithms // Asia-Pacific Journal of Operational Research. 2000. Vol. 17, № 2. P. 199-212.

93. Skriver A.J.V., Andersen K.A. A label correcting approach for solving bicriterion shortest-path problems // Computers and Operations Research. 2000. Vol. 27, № 6. P. 507-524.

94. Solomon M.M. Algorithm for Vehicle Routing and Scheduling Problem with Time Window Constraints // Operations Research. Vol. 35, № 2. 1987. P. 254-265.

95. Solomon M.M., Baker E., Schaffer J. Vehicle routing and scheduling problems with time window constraints: Efficient implementations of solution improvement procedures // Vehicle routing: Methods and srudies. Amsterdam: North-Holland, 1988. P. 85-106.

96. The VRP with Time Windows / J. F.Cordeau et al. // SIAM Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2001. P. 157-193.

97. The vehicle routing problem / N. Christofïdes et al. // Combinatorial Optimization. 1979. P. 315-338.

98. Thorup M. Undirected single-source shortest paths with positive integer weights in linear time // Journal of the ACM. Vol. 46, № 3. 1999. P. 362-394.

99. Toth P., Vigo D. An overview of vehicle routing problems // The Vehicle Routing Problem: SIAM Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2002. P. 1-24.

100. TSP cuts which do not conform to the template paradigm / D. Appletgate et al. // Computational Combinatorial Optimization, LNCS. 2001. Vol. 2241. P. 261-303.

101. Vacic V., Sobh T.M. Vehicle Routing Problem with Time Windows // International Scientific Journal of Computing. 2004. Vol. 3, JVfi 2. P. 72-80.

102. Vincke P. Problèmes multicritères // Cahiers du Centre d'Etudes de Recherche Opérationelle. 1974. Vol. 16. P. 425-439.

103. Williams J.W. Heapsort // Communications of the ACM. 1964. Vol. 7, № 6. P. 347-348.