This paper presents a new formulation and solution of a mixed-integer program for the hierarchical orthogonal hypergraph drawing problem, and the number of hyperedge crossings is minimized. The novel feature of the model is in combining several stages of the Sugiyama framework for graph drawing: vertex ordering, the assignment of vertices’ x-coordinates, and orthogonal hyperedge routing. The hyperedges of a hypergraph are assumed to be multi-source and multi-target, and vertices are depicted as rectangles with ports on their top and bottom sides. Such hypergraphs are used in data-flow diagrams and in a scheme of cooperation. The numerical results demonstrate the correctness and effectiveness of the proposed approach compared to mathematical heuristics. For instance, the proposed exact approach yields a reduction of the number of crossings compared to that obtained by using a mathematical heuristic for a dataset of non-planar graphs.
30 September 2024 in Proceedings of Voronezh State University. Series: Economics and Management
Предмет: Одной из основных задач управления на железнодорожных путях необщего пользования является сбор грузовых вагонов на выделенных путях с целью формирования состава, предназначенного к отправке со станции. Оптимизационная математическая модель позволит автоматизировать этот процесс и повысить эффективность и рациональность решений, принимаемых транспортными диспетчерами. Цель: Статья посвящена формированию математической постановки для задачи сборки грузовых составов на путях необщего пользования железнодорожной станции ветвистого типа при помощи маневрового локомотива. Метод: Модель разработана на базе методов и подходов к поиску точного решению задач многокритериальной целочисленной оптимизации. Результаты: Апробация модели выполнена на синтетических исходных данных для выделенного участка железнодорожных путей ветвистой грузовой станции. Полученные числовые результаты демонстрируют возможность использования модели для решения поставленной задачи за приемлемое время.