Аннотация:
Предложена новая графовая модель перевозок на линейном участке железной дороги. На основе заданного графика перевозок грузовых составов строится ациклический граф, вершины которого обозначают перевозки, а дуги — возможность последовательного осуществления их некоторым локомотивом. Такая модель задачи позволяет применить для нахождения оптимального плана назначений локомотивов статические графовые алгоритмы. Поиск решения в задаче без временных ограничений на локомотивы сводится к поиску минимального покрытия ациклического графа путями. Каждый путь в покрытии соответствует последовательности перевозок, осуществляемых одним локомотивом. При наличии временных ограничений на локомотивы (их уход на техническое обслуживание) не все пути в найденном покрытии могут остаться допустимыми — для некоторых локомотивов ни одна из найденных последовательностей перевозок не может быть выполнена от начала до конца. В этом случае добавляется еще один этап решения, на котором найденное покрытие преобразуется таким образом, что все новые пути описывают последовательности перевозок, которые можно осуществить данным множеством локомотивов с заданными временными ограничениями.
Ключевые слова:
графовые модели, минимальное покрытие графа путями, покрытие графа с ограничениями, задача об оптимальном назначении.
Образец цитирования:
Л. Ю. Жилякова, Н. А. Кузнецов, “Графовые методы решения задачи об оптимальном назначении локомотивов на линейном участке железной дороги — без ограничений и с ограничениями”, Автомат. и телемех., 2021, № 5, 45–67; Autom. Remote Control, 82:5 (2021), 780–797
\RBibitem{ZhiKuz21}
\by Л.~Ю.~Жилякова, Н.~А.~Кузнецов
\paper Графовые методы решения задачи об оптимальном назначении локомотивов на линейном участке железной дороги~--- без ограничений и с ограничениями
\jour Автомат. и телемех.
\yr 2021
\issue 5
\pages 45--67
\mathnet{http://mi.mathnet.ru/at15722}
\crossref{https://doi.org/10.31857/S0005231021050044}
\elib{https://elibrary.ru/item.asp?id=45738675}
\transl
\jour Autom. Remote Control
\yr 2021
\vol 82
\issue 5
\pages 780--797
\crossref{https://doi.org/10.1134/S0005117921050040}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000656916600004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85107373879}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at15722
https://www.mathnet.ru/rus/at/y2021/i5/p45
Эта публикация цитируется в следующих 1 статьяx:
Bing Li, Ce Yun, Guanglan Xu, Xiaoqian Zhou, Hua Xuan, Giulio E. Cantarella, “Optimization of Simultaneous Delivery and Pickup Wagon Scheme on Hybrid Siding Network of Railway Terminal”, Discrete Dynamics in Nature and Society, 2022 (2022), 1
Цитирование в формате AMSBIB
Обратная связь: