Содержание к диссертации
Введение
1 Обзор существующих алгоритмов решения ЗМТ 11
1.1 Классификация ЗМТ 11
1.2 Методы оптимизации 13
1.2.1 Метод ветвей и границ 13
1.2.2 Методы линейной оптимизации 14
1.2.3 Генетические алгоритмы 16
1.2.4 Метод имитации отжига 17
1.2.5 Поиск с запретами 19
1.3 Классификация Фишера 19
1.4 Классификация Кордо 21
1.4.1 Построение начального приближения 22
1.4.2 Локальная оптимизация приближения 23
1.4.3 Глобальная оптимизация 25
1.4.4 Машинное обучение 27
1.5 Выводы 30
2 Многофазный алгоритм 32
2.1 Постановка задачи 32
2.2 Общая схема работы алгоритма 34
2.3 Построение редуцированного графа 35
2.3.1 Одномерный случай 36
2.3.2 Двумерный случай 36
2.3.3 Многомерный случай 39
2.4 Метод фиктивных клиентов 52
2.5 Построение начального приближения 54
2.6 Обмен сегментов маршрутов 55
2.6.1 Ускорение операции обмена сегментов 55
2.6.2 Поиск оптимального обмена сегментов 59
2.7 Разгрузка агентов 62
2.8 Постобработка 63
2.9 Выводы 64
3 Аспекты реализации 66
3.1 Система PlanVidia 66
3.2 Архитектура PlanVidia 68
3.2.1 Эксплуатация системы 68
3.2.2 Основные части системы 69
3.2.3 Назначение системы 70
3.2.4 Функциональность системы 71
3.2.5 Внутренняя структура системы 71
3.2.6 Расчетный модуль 73
3.2.7 Потоки данных 74
3.3 Формирование исходных данных 76
3.3.1 Построение графа дорог 76
3.3.2 Геокодирование 78
4 Практические результаты 80
4.1 Процедура тестирования 80
4.1.1 Открытое тестирование 80
4.1.2 Внешнее тестирование 81
4.2 Примеры проектов 81
4.2.1 Антверпен 81
4.2.2 Бельгия 84
4.3 Визуальное тестирование 85
4.3.1 Обслуживание изолированных клиентов 85
4.3.2 Распределение кластеров между агентами 85
4.3.3 Привязка клиентов к ребрам графа 87
4.4 Результаты экспериментов 88
4.4.1 Алгоритм начального построения 88
4.4.2 Зависимость результатов от размеров групп . 88
4.4.3 Тестовые наборы Геринга и Хомбергера 89
4.4.4 Задачи большой размерности 90
4.4.5 Вариация параметров оптимизации 91
4.4.6 Эффективность оптимизации 92
4.4.7 Сравнение расчетных данных с экспериментальными 93
4.4.8 Проекты компании CapVidia 95
4.4.9 Параллельные вычисления 96
4.5 Выводы 97
Литература 101
- Методы линейной оптимизации
- Ускорение операции обмена сегментов
- Внутренняя структура системы
- Сравнение расчетных данных с экспериментальными
Введение к работе
Актуальность работы. Задачи маршрутизации являются ключевыми в областях транспортных перевозок, перемещения и логистики и представляют огромный практический интерес. В решении подобных задач заинтересованы многие организации, например, службы скорой помощи, интернет-магазины, оптовые базы, автотранспортные предприятия, компании, занимающиеся грузоперевозками.
В работе рассматриваются задачи оптимизации на графах больших размерностей, возникающие в транспортной логистике, не имеющие эффективных алгоритмов нахождения точного решения. Исследуемый класс задач является вариацией задач маршрутизации транспорта с временными окнами и дополнительными ограничениями.
Задача формулируется следующим образом. Есть множество клиентов и множество агентов. Агенты обслуживают клиентов. Обслуживание заключается в доставке (сборе) товара (предоставлении услуг). Каждый товар имеет набор характеристик (вес, объем, стоимость и др.). Для каждого агента заданы местоположение в начале и в конце рабочего дня, интервал работы, ограничения на суммарные доставляемые характеристики товара. Для каждого клиента заданы интервал времени, в течение которого должен быть доставлен товар, характеристики товара, который он должен получить, и приоритет. Необходимо обслужить максимальное количество клиентов с учетом приоритетов так, чтобы были выполнены временные ограничения и ограничения на суммарные характеристики доставляемых товаров. При этом нужно минимизировать суммарные накладные расходы (время работы, время простоя, суммарные транспортные расходы, количество задействованных агентов и т.д.).
Рассматриваемый класс задач представляет интерес с научной точки зрения. В данном направлении на протяжении последних сорока лет ведутся интенсивные исследования. Огромное количество входных параметров, с одной стороны, делают задачу настолько сложной, что многие существующие алгоритмы либо не применимы, либо плохо адаптируемы к практике. С другой стороны, эта же особенность предоставляет простор для новых исследований.
Первые приближенные алгоритмы были созданы в 1970-х годах (Clarke С, Wright J.W.). В 1980-е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook Т., Russel R.A., Christofides N., Mingozzi A., Toth P.). С середины 1990-х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau М., Osman I.H., Matsuyama Y.). В последние десять лет исследования склонились в сторону обработки сложных видов ограничений (Frazzoli Е., Bullo F.).
Главной целью большинства исследователей является повышение качества результатов счета. При этом скорость работы алгоритмов уходит на второй план. В то же время высокий темп роста 1Т-индустрии и интернет-технологий приводит к необходимости создания программных продуктов, ориентированных на широкий круг пользователей. Для задач массового обслуживания количество клиентов может достигать нескольких тысяч, но при этом время работы не должно превышать заданного временного порога. Таким образом, поиск алгоритмов, способных находить решения приемлемого качества за заданное время, становится все более актуальной задачей.
Целью работы является разработка моделей и алгоритмов для практического решения задач маршрутизации транспорта на графах больших размерностей, содержащих до 10 000 клиентов.
Задачами исследования являются:
Разработка моделей и на их основе приближенных алгоритмов для решения многокритериальной задачи о поиске кратчайших путей.
Разработка новых и ускорение существующих алгоритмов для решения задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями.
Методы исследования. В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов.
Научная новизна. В диссертации получены следующие основные научные результаты, которые выносятся на защиту:
Предложен и исследован приближенный алгоритм для построения Па-рето-минимальных путей в двумерном случае.
Предложено обобщение многокритериальной задачи на случай графов с произвольно заданным частичным порядком и построен алгоритм для ее решения.
Предложен метод фиктивных клиентов для снижения размерности задачи.
Создан и исследован алгоритм построения начального приближения, основанный на решении задачи о назначениях.
Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с 0{п) до 0(log п), где п -- общее количество клиентов в маршрутах.
С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано, что выполнение данного условия позволяет сократить количество разрезов с 0(п2) до 0(п).
7. Разработан многофазный эвристический алгоритм для приближенного решения задачи маршрутизации транспорта с временными окнами, позволяющий учитывать такие дополнительные ограничения, как множественность депо, приоритеты клиентов, зоны обслуживания, множественность характеристик товаров.
Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке C++ и протестированы в операционных системах Windows, Linux. Для практического использования создана динамическая библиотека, которая в настоящее время внедрена в программном комплексе PlanVidia.
Достоверность результатов подтверждена строгими доказательствами и результатами численных расчетов.
Апробация результатов работы. По результатам, полученным в данной работе, были сделаны доклады на следующих российских и международных конференциях:
Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 2000
Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2001
Научная конференция «Ломоносовские чтения», Москва, 2003
Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2005
Международный семинар по компьютерной алгебре и информатике, Москва, 2005
Шестая международная конференция памяти академика А.П. Ершова «Перспективы систем информатики», Новосибирск, 2006
Всероссийская конференция студентов, аспирантов, молодых ученых «Технологии Microsoft в теории и практике», Москва, 2008
Публикации. Основные результаты работы изложены в 10 научных статьях, среди которых 6 -- в тезисах докладов [3-5,7-9], 3 -- в рецензируемых российских периодических изданиях [1,2,6], из которых 2 статьи [1,2] опубликованы в журналах из списка ВАК и 1 статья в международном рецензируемом журнале [10].
Личный вклад соискателя. Все исследования, результаты которых изложены в диссертационной работе, проведены лично соискателем в процессе научной деятельности. Из совместных публикаций в диссертацию включен лишь тот материал, который непосредственно принадлежит соискателю.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 115 страницах, содержит 39 иллюстраций. Библиография включает 113 наименований.
Автор выражает глубокую признательность к.ф.-м.н, в.н.с. Панкратьеву Евгению Васильевичу за научные консультации и поддержку.
Методы линейной оптимизации
Генетические алгоритмы основаны на идее, заимствованной из генетических процессов биологических организмов. Биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора. Подражая этому процессу, генетические алгоритмы позволяют отбирать наиболее приспособленные решения, если те соответствующим образом закодированы. Чтобы достичь желаемой цели как можно быстрее, разработчик должен правильно установить законы эволюции.
Основные принципы генетических алгоритмов были сформулированы в 1975 году Голландом [68]. Впервые эта идея была применена к решению оптимизационных задач Растригиным в середине 70-х годов [21]. Примерно через десять лет появились теоретические обоснования данного подхода [97]. На сегодняшний день генетические алгоритмы доказали свою конкурентоспособность при решении многих сложных задач оптимизации [8], особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено.
Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов. Затем на каждом шаге эволюции с помощью вероятностного оператора селекции выбирается пара решений. Оператор скрещивания по данной паре строит новое решение, которое затем подвергается небольшим случайным модификациям, которые принято называть мутациями. После этого новое решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.
Метод имитации отжига основан на идее, заимствованной из статистической механики. Он отражает поведение расплавленного материала при отвердевании с применением процедуры отжига (управляемого охлаждения) при температуре, последовательно понижаемой до нуля. В процессе медленного управляемого охлаждения кристаллизация расплава сопровождается глобальным уменьшением его энергии, однако допускаются ситуации, в которых она может на какое-то время возрастать (в частности, при подогреве расплава для предотвращения слишком быстрого его остывания). Благодаря допустимости кратковременного повышения энергетического уровня, возможен выход из ловушек локальных минимумов энергии, которые возникают при реализации процесса. Только понижение температуры до абсолютного нуля делает невозможным какое-либо самостоятельное повышение энергетического уровня расплава.
Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения в его окрестности выбирается некоторое решение и, если разность целевой функции между новым и текущим решением не превосходит заданного порога с&, то новое решение заменяет текущее. В противном случае выбирается новое соседнее решение. В зависимости от способа задания последовательности различают три типа пороговых алгоритмов: Последовательное улучшение: с& = 0 — локальный спуск с монотонным улучшением функции. Пороговое улучшение: lim с& = 0 — вариант локального поис-ка, когда допускается ухудшение целевой функции до некоторого заданного порога, и этот порог последовательно снижается до нуля. Имитация отжига: Ck — случайная величина с математическим ожиданием E(ck) = h - вариант локального поиска, когда допускается произвольное ухудшение целевой функции, но вероятность такого перехода обратно пропорциональна величине ухудшения Р(х,у) = exp(-Af/tk). Метод отжига является достаточно популярным алгоритмом для решения задач оптимизации. Он позволяет преодолевать локальные экстремумы и находить оптимальное решение. Плата за это — медленная работа алгоритма в случае большой размерности целевой функции, так как множество шагов по окрестности допустимых решений осуществляется в случайных, ненужных направлениях [17]. Основоположником алгоритма поиска с запретами является Гловер, который предложил принципиально новую схему локального поиска [62,63]. Она позволяет алгоритму не останавливаться в точке локального экстремума, как это происходит в стандартном алгоритме локального спуска, а путешествовать от одного локального оптимума к другому в надежде найти среди них оптимальное решение. Суть метода заключается в том, что он хранит историю решений, в которых уже побывал. На основании этой информации строится список запретов, и при выборе очередного решения рассматриваются не вся окрестность, а лишь та ее часть, которая не входит в список запретов. Таким образом, алгоритм блуждает от одного локального минимума к другому в поисках глобального минимума. Поиск с запретами позволяет добиться высокой эффективности в комбинации с пороговыми алгоритмами.
Ускорение операции обмена сегментов
. Рассмотрим случайную перестановку {х{} и последовательность минимальных элементов щ = min(xj), j і. Тогда в последовательности {щ} в среднем содержится O(logn) различных элементов.
Доказательство. Обозначим /(п) — математическое ожидание количества различных элементов в последовательности {а{\. Построим рекуррентное соотношение для f{ri). Последовательности {а{\ можно разделить на п классов по значению первого элемента. Пусть а\ = к. Если элементы последовательности Х{ к убрать из рассмотрения, получим новые последовательности {x j} и {a j}. Количество различных элементов в последовательности {a j} на единицу меньше, чем количество различных элементов в последовательности {а }. Количество элементов в последовательности {x j} равно п — к, следовательно, среднее количество различных элементов в последовательности {а } будет /(п — к) + 1. Учитывая, что все события а\ = к равновероятны, получаем рекуррентное соотношение:
По лемме последовательность ai является кусочно-постоянной, причем количество таких кусочков O(logn). Так как мы можем обновлять информацию на любы подотрезках, среднее количество таких операций будет O(logn). Чтобы быстро вычислять границы соответствующих подотрезков, нужно хранить индексы разрывов последовательности {а }.
Обновление значений tmax(Q) производится аналогично tmin(ci) по схеме, описанной выше. Теперь рассмотрим как осуществляется склейка двух сегментов. Проверка корректности сводится к проверке неравенства: Сама операция склейки является обратной операцией для операции разбиения. Обновление информации в узлах дерева производится аналогично операции разбиения. Теорема 3. При описанном способе хранения информации о маршрутах операция обмена выполняется за время 0(log2n). Доказательство. Любой обмен сегментов маршрутов может быть представлен как композиция четырех разбиений и четырех склеек. Для каждой такой операции требуется 0(\ogn) запросов на обновление информации в дереве. Каждый запрос выполняется за время O(logn). Следовательно, общее время составляет 0(logn2). Общая схема оптимизации заключается в том, что из всех способов обмена сегментов маршрутов выбирается оптимальный, и только после этого производится сам обмен. Описанная процедура повторяется до тех пор, пока происходит улучшение целевой функции. Оценим трудоемкость данной схемы. Пусть п — количество клиентов в рассматриваемых маршрутах. Тогда общее количество сегментов будет 0(пА). На практике ограничивают длину сегментов некоторой константой и, таким образом, сокращают количество рассматриваемых сегментов до 0(п2). Без применения описанной выше структуры данных операция обмена осуществляется за 0(п) времени, следовательно, суммарное время составляет 0(п3). Ниже по тексту предлагается способ ускорения этой фазы до 0(nlog2n). Учитывая, что мы рассматриваем только корректные маршруты, не все сегменты можно менять друг с другом и не все обмены приводят к улучшению результатов. Поэтому необходимо минимизировать общее количество пар сегментов и рассматривать лишь наиболее перспективные из них. Заметим, что при обмене сегментов значение целевой функции изменяется благодаря тому, что мы пару ребер AD и ВС заменяем на пару ребер АС и BD. Ребра, по которым происходит переклейка сегментов, назовем разрезом. Значение Сначала найдем все разрезы с положительной величиной, для которых времена посещения точек А, С и J5, D примерно одинаковы. Эти требования связаны с тем, что нам подходят лишь те разрезы, для которых можно выполнять обмены сегментов. Будем считать, что разрез удовлетворяет нашему требованию, если выполняется условие фильтрации Так как функции tmjn и tmax монотонные, мы можем существенно сократить перебор пар ребер путей, образующих разрез. Лемма. Рассмотрим пару маршрутов г І, І Є {1,2}. Пусть U — время агента в пути, t\ — время простоя агента, щ — количество клиентов в маршруте, t = min(i,2), t = max(i,2)» n = max(ni,7i2). Тогда количество разрезов, удовлетворяющих условию фильтрации, не превосходит 0(t /t - п2 + п). Доказательство. Среднее время передвижения агента между клиентами составляет t [ = U/щ. Диапазон возможного времени обслуживания клиента не превосходит i!{. Следовательно, для каждой пары соседних клиентов из первого маршрута существует не больше чем ( i/ 2 + 1) вариантов выбора пары соседних клиентов для второго маршрута. Следовательно, общее количество искомых разрезов не превосходит что и требовалось доказать. Доказательство. Для доказательства теоремы нужно рассмотреть предел при t — 0 и воспользоваться леммой, сформулированной выше. С увеличением количества клиентов в маршрутах, время простоя агентов уменьшается, следовательно, время работы данной фазы оптимизации составляет 0(nlog2n).
Внутренняя структура системы
Тестирование осуществлялось на тестовые наборах Соломона (1987), Геринга и Хомбергера (1999).
Исходные наборы данных содержат от 100 до 1000 клиентов и одно центральное депо. Заданы ограничения по грузоподъемности агентов. Задачи разбиты на классы Rl, R2, CI, С2, RC1, RC2. Каждый класс содержит от 8 до 12 тестовых примеров. В Rl, R2 клиенты располагаются случайным образом на плоскости. В Сі, С2 клиенты объединяются в группы (кластеры). В RC1, RC2 применяется смешанное распределение клиентов. Все тестовые примеры из одного класса имеют одно и то же распределение клиентов на плоскости. Количество клиентов с ограничением по времени варьируется от 25% до 100%. В R1, CI, RC1 задан узкий интервал времени работы клиентов и маленькая грузоподъемность агента. В R2, С2, RC2 используются более широкие окна работы клиентов, большая грузоподъемность агентов.
Сравнение полученных результатов осуществлялось по трем критериям: количество задействованных агентов, средняя длина маршрутов, среднее время работы.
Проверка работы алгоритмов осуществлялась на данных, предоставляемых компанией CapVidia. Тестирование осуществлялось в течение нескольких месяцев. Расчеты проводились ежедневно. Оценка качества проводилась по количеству обслуженных клиентов, количеству задействованных агентов, суммарной длине маршрутов, среднему времени работы программы.
Исходные данные, на которых получались неудовлетворительные результаты, подвергались тщательной ручной проверке. Затем расчетные данные преобразовывались в маршрутные листы и передавались транспортным предприятиям. Так сопоставлялись расчетные и реальных графики движения агентов.
В результате тестирования удалось не только повысить качество оптимизации, но так же существенно ускорить работу отдельных фаз алгоритма. В этом проекте 7618 клиентов и 23 агента. Суммарный объем работ существенно превышает суммарные возможности агентов. Необходимо обслужить максимальное количество клиентов. Видно, что основное время у агентов уходит на обслуживание клиентов и лишь небольшая часть на перемещение. Это связано с большой плотностью клиентов на карте. В этом проекте 184 клиента и 22 агента. В данном случае удается обслужить всех клиентов. Необходимо минимизировать количество задействованных агентов. Полученный результат — 15 агентов. значительная часть времени агента уходит на перемещение. Это связано с тем, что плотность клиентов достаточно низкая. В некоторых случаях агенты вместо того, чтобы обслуживать группу клиентов, обслуживают изолированных клиентов. В результате детального анализа стало понятно, что эта ситуация имеет место в следующих случаях: обслуживание клиентов с более высоким приоритетом; обслуживание клиентов, которые встречаются по пути движения к другой группе; обслуживание клиентов с жесткими ограничениями по времени или зонам обслуживания; отсутствие сгруппированных клиентов. Все перечисленные выше ситуации является допустимыми и не являются ошибками. Если у нас есть несколько групп клиентов и такое же количество агентов, как правило, каждому агенту нужно назначить свою группу кли- ентов. Но на практике распределение клиентов между агентами может происходить по другим принципам. В результате может возникнуть ситуация, когда несколько агентов начинают делить между собой несколько групп клиентов. Из-за этого конечный результат получается хуже.
Сравнение расчетных данных с экспериментальными
Компания ежедневно нанимает 25 агентов для обслуживания 450-500 электрических узлов. Необходимо выбрать минимальное количество агентов с требуемыми навыками и рассчитать кратчайшие маршруты посещений клиентов. Среднее время расчета составляет 5 минут.
Газетное агентство ежедневно развозит 20 различных газетных выпусков и журналов в 4000 киосков. Каждый киоск требует поставки определенного числа выпусков не позже строго определенного срока поставки. Необходимо выбрать оптимальные транспортные средства и рассчитать общую стоимость поставки. Среднее время расчета составляет 45 минут.
Крупный пивоваренный завод обслуживает 28 000 кафе, используя для этого 120 агентов. Ежедневно обслуживается 700-800 кафе. Необходимо обеспечить равномерную нагрузку между всеми агентами. Среднее время расчета составляет 30 минут.
Служба безопасности осуществляет непрерывное патрулирование 1500 мест при помощи 65 агентов. Необходимо минимизировать количество задействованных агентов. Среднее время расчета составляет 20 минут. Компания обслуживает 5 000 клиентов. Ежедневно осуществляется сбор мусора и доставка в одно из пяти ближайших депо. Для организации работы используется 250 транспортных средств. Необходимо минимизировать количество машин и обеспечить их равномерную загрузку. Среднее время расчета составляет 1 час.
Компания в среднем обслуживает 1500 клиентов в день. Доставка воды осуществляется 35 агентами. Клиенты имеют разный приоритет. Необходимо выбрать агентов и составить расписание для обслуживания приблизительно 6 000 клиентов. Среднее время расчета 30 минут.
В рамках программы СКИФ союзного государства проводились испытания по распараллеливанию алгоритмов построения редуцированного графа. Количество процессоров варьировалось от 1 до 22. В ходе испытаний коэффициенты утилизации суммарной частоты процессоров оказались не ниже 50%. Тестирование проводилось при помощи Т-системы на базе центра мультипроцессорных систем института программных систем РАН. Результаты были представлены на конференции «Высокопроизводительные вычисления и их приложения» [9]. 1. При сопоставлении полученных данных с результатами, опубликованными в работе Майкла Гендро (2010), было показано, что многофазный алгоритм обладает как высокой скоростью работы, так и высокой степенью оптимизации. 2. При тестировании алгоритма на задачах большой размерности, содержащих от 5000 до 10000 клиентов, максимальное время работы составило 94 минуты. Полученные результаты доказывают возможность практического использования многофазного алгоритма. 3. При вариации вспомогательных параметров на фиксированных входных данных были получены следующие результаты: Конечные результаты имеют небольшой разброс, следовательно, алгоритм может применяться на практике без необходимости тонкой настройки параметров. Неиспользованное время работы агентов составило не более 6% от общего времени. Показано, что при увеличении числа клиентов в решении суммарная длина маршрутов уменьшается, то есть оптимизация транспортных расходов неявно происходит на всех этапах работы алгоритма. 4. Для задач массового обслуживания суммарная эффективность оказалась не менее 85%. 5. При сопоставлении расчетных и фактических данных среднее отклонение по числу клиентов составило 15%, по длине — 8%. 6. Компания CapVidia проводила независимое тестирование программного продукта PlanVidia. Проверка осуществлялась на задачах от 7 разных поставщиков данных. Количество клиентов варьировалось от 1000 до 5000. Время расчета составило от 30 до 60 минут. Полученные результаты были одобрены заказчиками и с некоторыми из них были достигнуты договоренности о промышленной эксплуатации PlanVidia. В настоящее время существует несколько промышленных инсталляций PlanVidia. 7. В рамках программы СКИФ союзного государства проводились испытания по распараллеливанию алгоритмов построения редуцированного графа. В ходе испытаний коэффициенты утилизации суммарной частоты процессоров оказались не ниже 50% на 20-ти процессорном кластере. Полученные результаты доказывают возможность распараллеливания алгоритмов, описанных в работе.
Похожие диссертации на Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей
