МАРШРУТИЗАЦИЯ В УСЛОВИЯХ ОГРАНИЧЕНИЙ: ЗАДАЧА О ПОСЕЩЕНИИ МЕГАПОЛИСОВ

Resultado de pesquisa: Articlerevisão de pares

Resumo

Рассматриваются задачи маршрутизации перемещений с условиями предшествования и динамическими ограничениями, включающими зависимость от списка заданий (выполненных на момент перемещения или, напротив, еще не выполненных). Стоимости перемещений также могут зависеть от списка заданий. Объектами посещения являются мегаполисы (непустые конечные множества), что отвечает возможной многовариантности перемещений. В качестве основного метода исследования используется широко понимаемое динамическое программирование в реализации, не предусматривающей (при наличии условий предшествования) построения всего массива значений функции Беллмана. Отдельно рассматриваются процедура построения "полного" решения, включая определение оптимальных маршрута и трассы (траектории), и процедура, обеспечивающая нахождение значения задачи (глобального экстремума), которое может использоваться при тестировании эвристических алгоритмов. Для решения маршрутных задач большой размерности, осложненных ограничениями, типичными для листовой резки на станках с числовым программным управлением, построен эффективный эвристический алгоритм. Для задач умеренной размерности проведено сравнение достигаемых результатов с оптимальным, доставляемым динамическим программированием.
Idioma originalRussian
Páginas (de-até)96-117
Número de páginas22
RevistaАвтоматика и телемеханика
Número de emissão11
Estado da publicaçãoPublished - 2016

GRNTI

  • 50.00.00 AUTOMATION. COMPUTER ENGINEERING

Level of Research Output

  • VAK List

Citar isto