Автореферат (1137431), страница 4
Текст из файла (страница 4)
Если частичнаяразгрузка приводит к ухудшению результатов, нужно вернуться к первоначальному расписанию и переходить к разгрузке следующего агента.14В разделе 2.8 описана процедура минимизации транспортных расходовпри заданном порядке посещения клиентов. Для заданного маршрута r ∈ Rнужно выбрать ребра редуцированного графа так, чтобы минимизироватьтранспортные расходы и не нарушить ограничения по времени.
Будем решатьзадачу при помощи метода динамического программирования.Обозначим Ei ∈ E′ — подмножество ребер, соединяющих i-го и (i +1)-го клиентов. Разобьем отрезок [ts(r), tf (r)] на n равных частей точкамиf (r)ti = (n−1)ts(r)+it. Обозначим d[i, j] длину корректного кратчайшего маршnрута, соединяющего первые j клиентов, время движения вдоль которого непревосходит ti . Если указанного маршрута не существует, будем считать, чтофункция не определена. Значения d[i′, j + 1] будем пересчитывать динамически по значениям d[i, j], поочередно перебирая ребра Ei. Если воспользоваться тем, что d[i, j] — невозрастающая функция по первому параметру,можно каждое ребро Ei рассматривать не более одного раза.
Следовательно,общее время работы будет O(nk + m), где k — общее количество клиентов,m = |E0| + . . . + |Ek | — суммарное количество ребер. Значение параметра nнужно выбирать максимально большим, но так, чтобы этот этап оптимизациивыполнялся достаточно быстро. Поскольку большинство состояний недостижимы, на практике алгоритм работает значительно быстрее, чем предполагает теоретическая оценка.В разделе 2.9 содержатся выводы по второй главе. Стоит отметить, что всефазы алгоритма независимо друг от друга могут применяться как составныечасти для построения новых или оптимизации существующих алгоритмов решения ЗМТ. Техника ускорения операции обмена сегментов маршрутов может применяться для таких операторов как 2-Opt, Or-Opt, 2-Opt*, Relocate,Exchange, Cross-Exchange и Geni-Exchange, которые широко используются внастоящее время.
Кроме этого, для алгоритмов, использующих случайныепреобразования (метаэвристики), можно уменьшить количество некорректных преобразований, осуществляемых в процессе формирования окрестностирешения, и, как следствие, ускорить их работу.В третьей главе рассматриваются вопросы практической реализации ииспользования предложенных алгоритмов.Алгоритмы, описанные в данной работе, были реализованы в программном продукте PlanVidia, общая информация о котором приводится в разделе 3.1.15Рис.
6. Система PlanVidiaPlanVidia была разработана с ориентацией на крупные обслуживающиеорганизации, работающие в регионах с большим географическим разбросом.Эта система позволяет определить минимальное количество агентов для ежедневного обслуживания сотен клиентов с учетом их географического местоположения, временных ограничений и приоритетов. PlanVidia поддерживаети упрощает работу диспетчера при помощи интерактивного графического интерфейса. Основные возможности PlanVidia: долгосрочное и краткосрочноепланирование, оптимальное распределение нагрузки в течение рабочего дня,оптимальное планирование в соответствии с бизнес-логикой, динамическоепланирование, анализ и контроль расписания.В разделе 3.2 описывается архитектура системы. Система представляет собой клиент-серверное приложение, которое позволят производить распределенные вычисления.
Благодаря синхронизации доступа к базе данных,обеспечивается многопользовательская работа операторов.Система включает в себя следущие подсистемы: сервер проектов, базаданных, графический клиент, вычислительный модуль, клиент экспорта иимпорта данных.16Рис. 7. Архитектура системыКаждая подсистема, в свою очередь, состоит из компонент. Перечислимнаиболее важные из них: Threading — управление потоками, Remoting — взаимодействие работы компонент, Logging — централизованный сбор информации и запись в лог-файл, ProjectServer — менеджер проектов, Cache —кеширование данных, MapRepository — менеджер карт, JobManager — балансер нагрузки, JobProcessor — менеджер задач, Solver — расчетный модуль,ThickClient — клиент для доступа к информации, расположенной на сервере,ProjectManager — компонент, обеспечивающий взаимодействие сервера проектов и пользовательского интерфейса.В разделе 3.3 рассматриваются вопросы подготовки исходных данных.Поставщики картографических данных предоставляют информацию о дорожной сети в виде графа с запрещенными маневрами.
Эти маневры задают правила движения транспорта и учитывают такие знаки, как «разворотзапрещен», «запрещен сквозной проезд» и другие. Таким образом, на исходном графе напрямую применять стандартные алгоритмы невозможно. Чтобырешить эту проблему, нужно построить расширенный граф, который будетучитывать эти ограничения.Рис. 8. Запрещенные и разрешенные маневрыПреобразовать смешанный граф в ориентированный достаточно просто,но вот устранить запрещенные маневры задача нетривиальная.
Обычно запрещенные маневры состоят из двух смежных ребер, но из-за наличия ограничений по полосам движения в некоторых случаях маневры могут включать17в себя большее количество ребер. Чтобы построить граф, который бы содержал в себе информацию о запрещенных маневрах, необходимо некоторыевершины исходного графа размножить.Рис.
9. Построение расчетного графаИнформация о клиентах поступает в виде GPS-координат или точныхадресов. Необходимо осуществить привязку к графу дорог. Привязка осуществляется к основанию проекции.Рис. 10. Привязка клиентов к графу дорогВ четвертой главе приводятся результаты тестирования. В разделе 4.1описывается процедура тестирования, в разделе 4.2 приводятся примеры проектов. В разделе 4.3 описываются результаты визуального тестирования. Вразделе 4.4 приводятся результаты экспериментов. В разделе 4.5 содержатсяосновные выводы по данной главе:1. При сопоставлении полученных данных с результатами, опубликованными в работе Michel Gendreau (2010), было показано, что многофазный алгоритм обладает как высокой скоростью работы, так и высокойстепенью оптимизации.2.
При тестировании алгоритма на задачах большой размерности, содержащих от 5000 до 10000 клиентов, максимальное время работы составило 94 минуты. Полученные результаты доказывают возможность практического использования многофазного алгоритма.183. При вариации вспомогательных параметров на фиксированных входных данных были получены следующие результаты:• Конечные результаты имеют небольшой разброс, следовательно,алгоритм может применяться на практике без необходимости тонкой настройки параметров.• Неиспользованное время работы агентов составило не более 6% отобщего времени.• Показано, что при увеличении числа клиентов в решении суммарная длина маршрутов уменьшается, то есть оптимизация транспортных расходов неявно происходит на всех этапах работы алгоритма.4.
Для задач с высокой плотностью клиентов для оценки полученного расписания вводится понятие эффективность — отношение суммарноговремени обслуживания к суммарному времени работы агентов. Для задач массового обслуживания суммарная эффективность оказалась неменее 85%.5. При сопоставлении расчетных и фактических данных среднее отклонение по числу клиентов составило 15%, по длине — 8%.6. Компания CapVidia проводила независимое тестирование программного продукта PlanVidia.
Проверка осуществлялась на задачах от 7 разных поставщиков данных. Количество клиентов варьировалось от 1000до 5000. Время расчета составило от 30 до 60 минут. Полученные результаты были одобрены заказчиками и с некоторыми из них былидостигнуты договоренности о промышленной эксплуатации PlanVidia.В настоящее время существует несколько промышленных инсталляцийPlanVidia.7. В рамках программы СКИФ союзного государства проводились испытания по распараллеливанию алгоритмов построения редуцированногографа. В ходе испытаний коэффициенты утилизации суммарной частоты процессоров оказались не ниже 50% на 20-ти процессорном кластере.Полученные результаты доказывают возможность распараллеливанияалгоритмов, описанных в работе.19ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫСозданы и исследованы новые алгоритмы и методы:1.
Приближенный алгоритм решения бикритериальной задачи о поискекратчайших путей.2. Псевдополиномиальный алгоритм для решения задачи о поиске кратчайших путей на графах с произвольно заданным частичным порядком.3. Алгоритм построения начального приближения, основанный на решении задачи о назначениях.4. Многофазный алгоритм для решения задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями (приоритеты клиентов, зоны обслуживания, характеристики товаров).5. Метод фиктивных клиентов.Улучшены существующие результаты:6.
Разработана структура данных для быстрого выполнения обменов сегментов маршрутов. Скорость работы возросла с O(n) до O(log2 n).7. При помощи разрезов и условия фильтрации ускорена процедура поиска оптимальных обменов сегментов маршрутов с O(n3 ) до O(n log2 n).Разработаны программные продукты:8. Программный комплекс PlanVidia для практического решения задачмаршрутизации с временными окнами и дополнительными ограничениям.В работе рассмотрены задачи маршрутизации транспорта с временнымиокнами и дополнительными ограничениями, приведен обзор научных публикаций за последние 40 лет. Опубликованы научные работы [1-10].Практические исследования доказывают высокую скорость работы и практическую значимость полученных алгоритмов.20ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ ВРАБОТАХПубликации в журналах, входящих в перечень ВАК:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
