Маршрутизация в условиях ограничений: задача о посещении мегаполисов

Рассматриваются задачи маршрутизации перемещений с условиями предшествования и динамическими ограничениями, включающими зависимость от списка заданий (выполненных на момент перемещения или, напротив, еще не выполненных). Стоимости перемещений также могут зависеть от списка заданий. Объектами посещения являются мегаполисы (непустые конечные множества), что отвечает возможной многовариантности перемещений. В качестве основного метода исследования используется широко понимаемое динамическое программирование в реализации, не предусматривающей (при наличии условий предшествования) построения всего массива значений функции Беллмана.
Отдельно рассматриваются процедура построения “полного” решения, включая определение оптимальных маршрута и трассы (траектории), и процедура, обеспечивающая нахождение значения задачи (глобального экстремума), которое может использоваться при тестировании эвристических алгоритмов.
Для решения маршрутных задач большой размерности, осложненных ограничениями, типичными для листовой резки на станках с числовым программным управлением, построен эффективный эвристический алгоритм. Для задач умеренной размерности проведено сравнение достигаемых результатов с оптимальным, доставляемым динамическим программированием.

Статья представлена к публикации членом редколлегии: А. А. Лазарев