Алгоритмы решения задачи маршрутизации транспорта

Диссертация на соискание учёной степени кандидата технических наук

Специальность 05.13.18 (Математическое моделирование, численные методы и комплексы программ)

Научный руководитель: доктор технических наук, профессор Костюк Юрий Леонидович

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

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

Математическая формулировка этой задачи широко известна как задача маршрутизации транспорта (ЗМТ). Существует ряд разновидностей ЗМТ с различными дополнительными условиями, позволяющими учитывать грузоподъёмность транспортных средств и другие ограничения для более полного представления деталей реальной действительности. ЗМТ является обобщением известной задачи коммивояжёра (ЗК) на случай построения сразу нескольких замкнутых маршрутов, проходящих через некоторую общую вершину, называемую депо. ЗМТ и ЗК принадлежат к классу задач дискретной оптимизации и являются NP-трудными. Не существует методов нахождения их точных решений и проверки оптимальности приближённых за полиномиальное время. Известен точный алгоритм решения ЗМТ на основе метода ветвей и границ, но в силу чрезмерно быстрого роста времени вычислений его невозможно применять для задач с более чем 25–30 вершинами.

Один из первых приближённых алгоритмов решения ЗМТ был предложен в 1964 г. (G. Clarke и J. W. Wright). В 1970-х и 1980-х годах исследования были продолжены, и полученные результаты составили группу так называемых классических алгоритмов (J. .B. Bramel, N. Christofides, B. .E. Gillett, J. Renaud и др.). Эти алгоритмы заложили основные типы подходов к приближённому решению ЗМТ. С середины 1990-х годов исследования сосредоточились в направлении так называемых метаэвристик. Название метаэвристик указывает на то, что они не являются законченными эвристиками, готовыми для применения, а только представляют собой некоторый метод для построения законченной эвристики для конкретной задачи. Большинство из них основаны на наблюдениях за явлениями живой и неживой природы. Важной их особенностью является способность к преодолению точки локального минимума для продолжения поиска, поэтому потенциально они способны находить более качественные решения по сравнению с классическими эвристиками. Наибольший интерес вызывают следующие методы: поиск с исключениями (M. Gendreau, A. Hertz, G. Laporte, I. H. Osman и др.), моделируемый и детерминированный отжиг (I. H. Osman и др.), генетический алгоритм (J. L. Blanton, G. Jeon и др.), алгоритм на основе муравьиных колоний (B. Bullnheimer и др.) и нейронные сети (Y. Matsuyama и др.). В последние десять лет исследования уклонились в основном в сторону обработки сложных видов ограничений. В отечественной научной литературе решением задач маршрутизации транспорта занимались: А. О. Алексеев, М. Ю. Ахлебинский, И. И. Меламед, С. И. Сергеев, И. Х. Сигал и др.

Большое количество работ, посвящённых метаэвристикам, создали ситуацию неопределённости в научном мире, не позволяя однозначно определить наилучший алгоритм для практического внедрения. Метаэвристики содержат дискретные и непрерывные параметры, управляющие их работой и требующие выполнения процедуры вариации значений для получения удачной законченной эвристики. Подбор параметров необходимо выполнять не только для разных типов задач, но зачастую даже для каждого нового набора входных данных. Если поиск с исключениями содержит только 1–2 дискретных параметра, то моделируемый отжиг содержит ряд непрерывных параметров, делающих процедуру вариации практически невозможной. Генетический алгоритм и алгоритм на основе муравьиных колоний в процессе работы обрабатывают очень большой массив данных, приводящий к длительным вычислениям, а также содержат большое количество управляющих параметров.

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

Целью настоящей работы является получение приближённых алгоритмов решения ЗМТ, способных выполнять построение маршрутов для входных данных, содержащих до 1000 вершин и более при использовании матрицы стоимостей переездов и до 1000000 вершин при использовании геометрической информации. В рамках указанной цели были поставлены следующие задачи:

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

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

Научная новизна работы.

Предложена модификация приближённого метода двухфазного решения ЗМТ, использующая на этапе кластеризации алгоритм сбалансированного дихотомического деления вершин на группы и позволяющая строить приближённые алгоритмы, обладающие трудоёмкостью порядка O(n²), показывающие при математическом моделировании снижение времени работы и улучшения качества решений для задач, содержащих 200 вершин и более, по сравнению с распространёнными метаэвристиками. На основе предложенной модификации приближённого метода двухфазного решения ЗМТ разработаны и реализованы алгоритмы решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.
Предложена модификация алгоритма сбалансированного деления вершин на группы с использованием геометрической информации, обладающая трудоёмкостью O(n log²n) и позволяющая решать сбалансированную ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ с несколькими депо для входных данных, содержащих до 1000000 вершин.
Получена оценка погрешности замены несимметричной матрицы стоимостей переездов симметричной, необходимой для применения на практике известных и предложенных приближённых алгоритмов решения различных видов ЗМТ, не способных работать с несимметричной матрицей.

Теоретическая значимость работы заключается в следующем:

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

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

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

Внедрение результатов работы. Результаты диссертационной работы в виде созданного программного приложения внедрены в промышленную геоинформационную систему IndorGIS.

Основные защищаемые положения:

Модификация приближённого метода двухфазного решения ЗМТ на основе принципа сбалансированного дихотомического деления вершин на группы, а также алгоритмы, созданные на её основе, для решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.
Модификация алгоритма сбалансированного деления вершин на группы с использованием геометрической информации для решения различных видов ЗМТ.
Оценка погрешности замены несимметричной матрицы стоимостей переездов симметричной.
Реализация предложенных алгоритмов решения различных видов ЗМТ в виде библиотеки классов.

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

XLV Международной научно-студенческой конференции "Информационные технологии" в г. Новосибирске в 2007 г.
Международной научно-практической конференции "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2007 г.
VII всероссийской научно-практической конференции с международным участием
"Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2008 г.
VIII всероссийской научно-практической конференции с международным участием "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2009 г.

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

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