Механизмы расчета задач выбора маршрута в Дополнительный модуль ArcGIS Network Analyst – Маршрут, Ближайший пункт обслуживания и Матрица Источник-Назначение – основаны на известном алгоритме поиска кратчайших путей Дейкстры. Каждый из этих механизмов расчета реализует два типа алгоритма поиска пути. Первый тип – поиск точного кратчайшего пути, а второй – иерархический поиск пути для повышения быстродействия. Классический алгоритм Дейкстры решает задачу поиска кратчайшего пути при помощи неориентированного, неотрицательного, взвешенного графа. Для использования в контексте реальных данных о транспортных перевозках этот алгоритм модифицируется с учетом пользовательских параметров, таких как ограничения, связанные с односторонним движением и поворотами, импеданс узлов, барьеры и ограничения для стороны улицы, при этом минимизируется заданный пользователем стоимостный атрибут. Быстродействие алгоритма Дейкстры улучшается при использовании более эффективных структур данных, таких как d-кучи. Кроме того, алгоритм должен иметь возможность моделировать местоположения в любой точке ребра, а не только на узлах пересечения.
Алгоритм Дейкстры
Классический алгоритм Дейкстры решает задачу поиска кратчайшего пути с одной исходной точкой на взвешенном графе. Для поиска кратчайшего пути от начального положения s к конечному положению d алгоритм Дейкстры поддерживает набор соединений, S, чей кратчайший путь от s уже был рассчитан. Алгоритм многократно выполняет в наборе поиск узла с минимальной оценкой кратчайшего пути, добавляет его в набор узлов S и обновляет оценки кратчайшего пути всех соседей этого узла, которые не входят в S. Алгоритм будет выполняться до тех пор, пока узел назначения не будет добавлен в набор S.
Маршрут
Этот механизм расчета использует известный алгоритм Дейкстры, который описан выше.
Ближайший пункт обслуживания
Этот механизм расчета использует алгоритм с несколькими источниками и несколькими назначениями на основе алгоритма Дейкстры. Он предусматривает возможность вычисления только кратчайших путей, если они входят в заданную ограниченную зону, или решения задачи для фиксированного числа ближайших пунктов обслуживания.
Матрица Источник-Назначение
Механизм расчета Матрица Источник-Назначение использует алгоритм с несколькими источниками и несколькими назначениями на основе алгоритма Дейкстры. Он предусматривает возможность вычисления только кратчайших путей, если они входят в заданную ограниченную зону, или решения задачи для фиксированного числа ближайших пунктов назначения. Механизм расчета Матрица Источник-Назначение аналогичен механизму расчета Ближайший пункт обслуживания, за исключением того, что он не позволяет определить форму получившегося кратчайшего пути для снижения накладных расходов и повышения быстродействия.
Иерархическая маршрутизация
Поиск точного кратчайшего пути в наборе сетевых данных государственного масштаба занимает много времени из-за большого числа ребер, по которым нужно вести поиск. Для улучшения быстродействия наборы сетевых данных могут моделировать естественную иерархию в транспортной системе, где выбор федеральной автострады предпочтительнее дорог местного значения. После создания иерархической сети применяется модифицированный алгоритм Дейкстры для двух направлений с целью вычисления маршрута между исходной и конечной точками.
Общая задача в данном случае – минимизировать импеданс и обеспечить присутствие в сети иерархий более высокого порядка. Для решения задачи иерархической маршрутизации ведется одновременный поиск из исходного и конечного местоположений, а также точек стыковки или въезда на дороги верхнего уровня, а затем – поиск по дорогам верхнего уровня, пока не встретятся сегменты из источника и назначения. Поскольку поиск ограничен иерархией верхнего уровня, он затрагивает меньшее количество ребер, что повышает быстродействие. Следует отметить, что это эвристический алгоритм; его цель – высокое быстродействие и хорошие решения, но он не гарантирует, что будет найден кратчайший путь. Для успешной работы эвристического алгоритма необходимо подключить иерархию высшего уровня, поскольку он не спускается на уровень ниже при достижении тупикового конца.
В общем случае целесообразно использовать этот механизм расчета в иерархической сети, где ребрам присваиваются весовые коэффициенты на основе времени в пути. Он имитирует обычные поездки по сети автомагистралей.
Вариант задачи о коммивояжере для механизма расчета Маршрут (Route)
Механизм расчета Маршрут может создать оптимальную последовательность остановок по маршруту. Эта задача коммивояжера или TSP. Это называется задачей о коммивояжере TSP – комбинаторная задача, для которой не существует прямого метода определения оптимальной последовательности. Чтобы быстро найти подходящие решения для задач такого рода, используются эвристические алгоритмы. Внедрение TSP в Network Analyst также позволяет управлять временными окнами на остановках; это означает, что он выполняет поиск оптимальной последовательности посещения остановок с минимальным запаздыванием.
Механизм расчета задачи о коммивояжере прежде всего создает матрицу Источник-Назначение для всех остановок, которые нужно включить в последовательность, и использует алгоритм запрещенного поиска оптимальной последовательности остановок. Запрещенный поиск – это метаэвристический алгоритм для решения комбинаторных задач. Он относится к категории алгоритмов локального поиска. Точная реализация запрещенного поиска защищена патентом, но она была широко исследована и проработана специалистами Esri для быстрого получения хороших результатов.
Задача выбора маршрута транспорта с временными окнами
Задача выбора маршрута транспорта (vehicle routing problem, VRP) – это расширенный вариант задачи о коммивояжере (TSP). В TSP один набор остановок располагается в оптимальной последовательности. В VRP группу заказов необходимо назначить набору маршрутов или транспортных средств таким образом, чтобы минимизировать общую стоимость пути. Здесь также требуется учитывать реальные ограничения, включая вместимость транспортного средства, временные окна доставки и способности водителя. Решение VRP учитывает эти ограничения и минимизирует целевую функцию, состоящую из эксплуатационных расходов и предпочтений пользователя, таких как важность временного окна встречи.
Механизм расчета VRP сначала создает матрицу Источник-Назначение, содержащую стоимости кратчайшего маршрута между всеми местоположениями заказов и складов в сети. Используя эту матрицу, механизм расчета вырабатывает первоначальное решение, по очереди размещая заказы на самом подходящем маршруте. Затем первоначальное решение совершенствуется путем переупорядочения заказов на каждом маршруте, а также путем перемещения и обмена заказов между маршрутами. Эвристический алгоритм, используемый в этом процессе, основан на метаэвристике запрещенного поиска и защищен патентом, но он исследовался и прорабатывался специалистами Esri в течение многих лет и позволяет быстро получить хорошие результаты.
Область обслуживания
Механизм расчета Область обслуживания также основан на алгоритме Дейкстры обхода сети. Его цель состоит в том, чтобы вернуть подмножество подключенных объектов границ таким образом, чтобы они находились в пределах заданного сетевого расстояния или сокращения затрат. Кроме того, он может возвращать линии, классифицированные по набору граничных значений, в которые может попасть ребро. Механизм расчета Область обслуживания может строить линии и/или полигоны, окружающие эти линии.
Полигоны создаются путем буферизацией линий на основе введенного пользователем расстояния. Кроме того, пользователи могут создавать полигоны высокого качества, чтобы полигоны содержали область, которая располагается ближе к пройденным линиям, чем к непройденным - до указанного пользователем расстояния.
Размещение-распределение
Механизм расчета Размещение-распределение предназначен для задачи размещения пункта обслуживания. При N потенциальных пунктах обслуживания и M точках спроса с весовыми коэффициентами необходимо выбрать подмножество пунктов обслуживания, P, такое чтобы сумма взвешенных расстояний от каждого пункта M до ближайшего пункта P была минимальной. Это комбинаторная задача типа «Из N выбрать P», и пространство ее решений исключительно широкое. Оптимальные решения нельзя получить, изучив все комбинации. Например, даже небольшая задача типа «Из 100 выбрать 10» содержит более 17 триллионов комбинаций. Кроме того, механизм расчета Размещение-распределение может решать множество различных задач размещения, например по достижению минимального взвешенного импеданса, максимального покрытия или целевой доли рынка. Для решения задач размещения-распределения применяется эвристика.
Механизм расчета Размещение-распределение сначала создает матрицу Источник-Назначение, содержащую стоимости кратчайшего маршрута между всеми пунктами обслуживания и точками спроса в сети. Затем он вырабатывает отредактированный вариант матрицы, используя процедуру, которая называется редактированием Хиллсмана. Эта процедура редактирования позволяет использовать тот же общий эвристический алгоритм механизма расчета для решения множества типов задач. Затем механизм расчета Размещение-распределение создает совокупность полуслучайных решений и применяет эвристический алгоритм подстановки вершин (метод Тейца и Барта) для получения группы более точных решений. Затем метаэвристика объединяет эту группу хороших решений для получения лучших решений. Когда дальнейшие улучшения невозможны, метаэвристический алгоритм возвращает лучшее решение. Комбинация отредактированной матрицы, полуслучайных начальных решений, эвристического алгоритма подстановки вершин и уточняющей метаэвристики позволяет быстро получить результаты, близкие к оптимальным.
Более подробно о выполнении анализа размещения-распределения