Graph methods for solving the unconstrained and constrained optimal assignment problem for locomotives on a single-line railway section. (English. Russian original) Zbl 1466.90018
Autom. Remote Control 82, No. 5, 780-797 (2021); translation from Avtom. Telemekh. 2021, No. 5, 45-67 (2021).
Summary: We propose a new graph model of transportation on a single-line railway section. Based on a given freight-train delivery schedule, we construct an acyclic graph with vertices denoting deliveries and arcs indicating the possibility of successive implementation of these deliveries by some locomotive. This model of the problem permits applying static graph algorithms to find an optimal locomotive assignment plan. The search for a solution of the problem without time constraints on the locomotives is reduced to finding a minimal path cover of an acyclic graph. Each path in the cover corresponds to a sequence of deliveries carried out by one locomotive. If there are temporary constraints on the locomotives (maintenance breaks), not all paths in the cover can remain valid: for some locomotives, none of the established delivery sequences can be performed from start to finish. In this case, one more solution stage is added, at which the cover is transformed in such a way that all new paths describe a sequence of deliveries that can be carried out by a given set of locomotives under given time constraints.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C35 | Programming involving graphs or networks |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C38 | Paths and cycles |
Keywords:
graph model; minimal path cover of graph; constrained cover of graph; optimal assignment problemReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993), Englewood Cliffs: Prentice Hall, Englewood Cliffs · Zbl 1201.90001 |
| [2] | Lovász, L.; Plummer, M., Matching Theory (1986), Budapest: Akadémiai Kiadó, Budapest · Zbl 0618.05001 |
| [3] | Adel’son-Vel’skii, G. M.; Dinits, E. A.; Karzanov, A. V., Potokovye algoritmy (Flow Algorithms) (1975), Moscow: Nauka, Moscow |
| [4] | Sedgewick, R., Algorithms in C++ (1992), Boston: Addison-Wesley, Boston · Zbl 0826.68025 |
| [5] | Erusalimskii, Ya. M.; Skorokhodov, V. A.; Kuz’minova, M. V.; Petrosyan, A. G., Grafy s nestandartnoi dostizhimost’yu: zadachi, prilozheniya (Graphs with Nonstandard Reachability: Problems, Applications) (2009), Rostov-on-Don: Izd. Yuzhn. Fed. Univ., Rostov-on-Don |
| [6] | Erusalimskii, Ya.M., Flows in networks with nonstandard reachability, Izv. Vyssh. Uchebn. Zaved. Severo-Kavkaz. Region. Estestv. Nauki, 2012, no. 1, pp. 5-7. |
| [7] | Matyukhin, V.G., Shabunin, A.B., Kuznetsov, N.A., and Takmazian, A.K., Rail transport control by combinatorial optimization approach, 11th IEEE Int. Conf. Appl. Inf. Commun. Technol. (2017), Conf. Proc., 2017, vol. 1, pp. 419-422. |
| [8] | Takmaz’yan, A. K.; Shabunin, A. B., Application of the optimal network flow method to the problem of locomotive selection for freight trains at the Eastern range, Vychislit. Tekhnol., 23, 6, 94-106 (2018) |
| [9] | Zhilyakova, L.Yu., Kuznetsov, N.A., Matyukhin, V.G., Shabunin, A.B., and Takmaz’yan, A.K., Graph model of the distribution of locomotives for freight traffic on a linear section of the railway. The problem of inclusion-maximum schedule cover, Probl. Upr., 2018, no. 3, pp. 65-75. |
| [10] | Ahuja, R. K.; Liu, J.; Orlin, J. B.; Sharma, D.; Shughart, L. A., Solving real-life locomotive scheduling problems, Transp. Sci., 39, 4, 503-517 (2005) · doi:10.1287/trsc.1050.0115 |
| [11] | Jaumard, B. and Tian, H., Multi-column generation model for the locomotive assignment problem, Proc. 16th Workshop Algorithmic Approaches Transp. Model. Optim. Syst. (ATMOS’16) (2016), pp. 6:1-6:13. |
| [12] | Azanov, V.M., Buyanov, M.V., Ivanov, S.V., Kibzun, A.I., and Naumov, A.V., Optimization of the locomotive fleet intended for the transportation of freight trains, Tr. 3-i nauchno-tekh. konf. ISUZhT-2016 (Proc. 3rd Sci.-Tech. Conf. ICSRT-2016) (2016), pp. 94-96. |
| [13] | Lazarev, A. A.; Musatova, E. G., The problem of trains formation and scheduling: integer statements, Autom. Remote Control, 74, 12, 2064-2068 (2013) · Zbl 1292.90056 · doi:10.1134/S0005117913120084 |
| [14] | Arkhipov, D.I., Lazarev, A.A., and Musatova, E.G., Using the programming method in constraints to solve the problem of assigning locomotives and locomotive crews to freight transportation, Tr. 6-i Mezhdunar. nauchno-tekh. konf. “Intellektual’nye sistemy upravleniya na zheleznodorozhnom transporte” ISUZhT-2017 (Proc. 6th Int. Sci.-Tech. Conf. “Intelligent Control Systems in Railway Transport” ICSRT-2017) (Moscow, 2017), Moscow: OAO NIIAS, 2017, pp. 56-59. |
| [15] | Gainanov, D. N.; Kibzun, A. I.; Rasskazova, V. A., The decomposition problem for the set of paths in a directed graph and its application, Autom Remote Control, 79, 2217-2236 (2018) · Zbl 1407.05105 · doi:10.1134/S000511791812010X |
| [16] | Boesch, F. T.; Gimpel, J. F., Covering the points of digraph with point-disjoint paths and its application to code optimization, J. Assoc. Comput. Mach., 24, 2, 192-198 (1977) · Zbl 0359.05027 · doi:10.1145/322003.322005 |
| [17] | Noorvash, Sh., Covering the vertices of a graph by vertex-disjoint paths, Pac. J. Math., 58, 1, 159-168 (1975) · Zbl 0264.05122 · doi:10.2140/pjm.1975.58.159 |
| [18] | Jackson, B.; Ordaz, O., Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey, Discrete Math., 84, 3, 241-254 (1990) · Zbl 0726.05043 · doi:10.1016/0012-365X(90)90130-A |
| [19] | Chvátal, V. and Erdős, P., A note on Hamiltonian circuits, Discrete Math., 1972, no. 2, pp. 111-113. · Zbl 0233.05123 |
| [20] | Aleskerov, F. T.; Habina, E. L.; Schwartz, D. A., Binarnye otnosheniya, grafy i kollektivnye resheniya (Binary Relations, Graphs, and Collective Decisions) (2012), Moscow: Fizmatlit, Moscow · Zbl 1277.91001 |
| [21] | Rubchinskii, A. A., Diskretnye matematicheskie modeli. Nachal’nye ponyatiya i standartnye zadachi (Discrete Mathematical Models. Initial Concepts and Standard Problems) (2014), Moscow: Direkt-Media, Moscow |
| [22] | Kalyaev, I. A.; Kapustyan, S. G., Multi-agent management method for smart internet production, Robototekhnika i tekhnicheskaya kibernetika, No. 1 (18) (Robotics and Technical Cybernetics no. 1 (18)) (2018), St. Petersburg: TsNII RTK, St. Petersburg |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
