|
Автоматика и телемеханика, 2016, выпуск 11, страницы 96–117
(Mi at14599)
|
|
|
|
Эта публикация цитируется в 29 научных статьях (всего в 29 статьях)
Тематический выпуск
Маршрутизация в условиях ограничений: задача о посещении мегаполисов
А. Г. Ченцовab, П. А. Ченцовab a Институт математики и механики им. Н. Н. Красовского УрО РАН, Екатеринбург
b Уральский федеральный университет, Екатеринбург
Аннотация:
Рассматриваются задачи маршрутизации перемещений с условиями предшествования и динамическими ограничениями, включающими зависимость от списка заданий (выполненных на момент перемещения или, напротив, еще не выполненных). Стоимости перемещений также могут зависеть от списка заданий. Объектами посещения являются мегаполисы (непустые конечные множества), что отвечает возможной многовариантности перемещений. В качестве основного метода исследования используется широко понимаемое динамическое программирование в реализации, не предусматривающей (при наличии условий предшествования) построения всего массива значений функции Беллмана.
Отдельно рассматриваются процедура построения “полного” решения, включая определение оптимальных маршрута и трассы (траектории), и процедура, обеспечивающая нахождение значения задачи (глобального экстремума), которое может использоваться при тестировании эвристических алгоритмов.
Для решения маршрутных задач большой размерности, осложненных ограничениями, типичными для листовой резки на станках с числовым программным управлением, построен эффективный эвристический алгоритм. Для задач умеренной размерности проведено сравнение достигаемых результатов с оптимальным, доставляемым динамическим программированием.
Образец цитирования:
А. Г. Ченцов, П. А. Ченцов, “Маршрутизация в условиях ограничений: задача о посещении мегаполисов”, Автомат. и телемех., 2016, № 11, 96–117; Autom. Remote Control, 77:11 (2016), 1957–1974
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at14599 https://www.mathnet.ru/rus/at/y2016/i11/p96
|
Статистика просмотров: |
Страница аннотации: | 312 | PDF полного текста: | 45 | Список литературы: | 45 | Первая страница: | 18 |
|