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