Об одной задаче маршрутизации с оптимизацией точки старта-финиша

Аннотация

Рассматривается одна оптимизирующая процедура для решения задачи последовательного обхода мегаполисов при наличии условий предшествования и функций стоимости, зависящих от списка заданий. Исследуется постановка замкнутой в следующем смысле задачи: стартовая точка (база процесса) и терминальное состояние должны совпадать (аналог замкнутой задачи коммивояжера). Данное условие естественно для целого ряда прикладных задач, связанных с проведением серий однородных процедур с элементами маршрутизации. Так, в частности, в задачах, связанных с листовой резкой деталей на машинах с ЧПУ, при работе с сериями деталей, отвечающих одному и тому же раскройному плану, режущий инструмент следует возвращать в точку старта для проведения повторных операций. В такой постановке задача оптимизации точки старта представляет не только теоретический, но и определенный практический интерес. На уровне математической постановки необязательно требовать упомянутого возврата в точку старта: данное условие может быть отражено посредством введения соответствующей терминальной функции, аргументом которой является последняя из точек посещения контуров детали. Такой подход позволяет охватить и некоторые более общие случаи, когда задается стоимость терминального состояния, включающая в виде параметра точку старта. В результате точки старта и финиша связываются функциональной зависимостью в виде цены, определяющей качество финального состояния процесса. Данное представление используется в статье.