К вопросу о применении минимаксной задачи коммивояжера к проблемам авиационной логистики

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