Все выпуски

Получены достаточные условия, обеспечивающие сохранение оптимальности маршрута обхода множества вершин при вставке новой вершины между двумя последовательными (в смысле существующего оптимального маршрута) вершинами, а также при удалении вершины с последующим соединением предшествующей и последующей вершин существующего оптимального пути. Проведен ряд экспериментов, демонстрирующих области устойчивости для задачи коммивояжера на плоскости.

Получены необходимые и достаточные условия, обеспечивающие сохранение оптимальности маршрута обхода множества вершин при вставке новой вершины между двумя последовательными (в смысле существующего оптимального маршрута) вершинами. Предложен алгоритм построения областей устойчивости, проведен ряд экспериментов для задачи коммивояжера на евклидовой плоскости.

В работе рассматривается проблематика снижения сложности $NP$-трудных задач с помощью использования близких задач, для которых оптимальное или приемлемое решение уже известно. Для задач многоагентной маршрутизации применяется методика, основанная на кластеризации сети, согласованной с маршрутами коммивояжера на каждом кластере и построения маршрутов, учитывающих ограничение временных окон доставки. Приводится математическая модель, которой соответствует блок псевдобулевой условной оптимизации с ограничениями в виде дизъюнктивных нормальных форм, допускающей полиномиальную разрешимость и блок временных ограничений. Результаты по выбору метаэвристик на основе близких задач используются в программе по доставке товаров многими агентами потребителям, расположенным в вершинах инфраструктурной дорожной сети региона.

В работе формализуется задача оптимизации сопутствующего производства на гибких или реконфигурируемых производствах. В рассматриваемой постановке на входе задан набор обязательных изделий, требуется решить две взаимосвязанные подзадачи: 1) для каждого изделия из набора обязательных сформировать группу дополнительных изделий, которые могут быть произведены без изменения состояния производства, и 2) определить порядок переналадок производства между группами дополнительных изделий, а также «точки входа и выхода» в каждую из групп. В настоящей работе указанные подзадачи рассматриваются последовательно: первая подзадача сведена к задаче поиска клики максимального веса в ориентированном графе, вторая - к кластерной задаче коммивояжера. В ходе масштабных вычислительных экспериментов изучен выигрыш от применения эффективных современных методов решения обеих подзадач в сравнении с жадным решением, моделирующим рациональные действия человека-оператора в условиях большой размерности исходной комплексной задачи и ограниченного времени, имеющегося для ее решения.