Authors A.N. Shabelnikov
Month, Year 07, 2015 @en
Index UDC 519.178
Abstract The class of scheduling problems relating to the definition of optimal scheduling of transport units and the order of their movement as an example of problems of formation, dissolution of trains in marshalling yards. We give formal setting of several variants of these tasks. From a mathematical point of view, the task scheduling related to the definition of optimal schedules, routes and order of traffic units classified as np-complete problems, for which well established metaheuristic algorithms based on ideas directed random search and allows to find optimal or close to These solutions np-complex tasks in a reasonable time. This paper presents a brief analysis of metaheuristic algorithms for solving problems of scheduling in rail transport, and the example of management tasks in the order of dissolution of the compositions hump is considered a new scheduling algorithm based on random search with restrictions. The article discusses the general metaheuristic approach to solving them. On the basis of this approach, we propose a new probabilistic local search algorithm with restrictions. The algorithm carries out a local search in the space of possible solutions using the procedures of intensification and diversification of the search based on an adaptive randomization parameter changing neighborhood. Results of numerical experiments showing the effectiveness of the algorithm. On the basis of numerical experiments we have found the optimal parameters of the algorithm: parameter randomization and the length of the list of prohibitions. At a certain test cases for particular cases of the problem in 93 % of the algorithm to find the best solution. For example, the maximum error of the rest of the algorithm does not exceed 5 %, which confirms the efficiency of the algorithm for solving a number of particular problems scheduling.

Download PDF

Keywords Dispatching; metaheuristic algorithm; genetic algorithm; probabilistic search; local search with restrictions; local neighborhood of decision.
References 1. Guda A.N., Dolgiy A.I., Kovalev S.M. Evolyutsionnye metody on-line dispetcherizatsii na osnove temporal'nykh modeley [Evolutionary methods on-line scheduling based on temporal models], Vestnik RGUPS [Vestnik RGUPS], 2014, No. 4, pp. 42-49.
2. Dolgiy I.D., Kovalev S.M., Krivolapov S.V. Optimizatsiya grafikov dvizheniya poezdov na osnove metodov evolyutsimonnogo modelirovaniya [Optimization of schedules of trains on the basis of methods of simulation evolyutsionnogo], Intellektual'nye modeli i myagkie vychisleniya v iskusstvennom intellekte: Sbornik nauchnykh trudov 7-y Mezhdunarodnoy
nauchno-tekhnicheskoy konferentsii [Intelligent models and soft computing in artificial intelligence: proceedings of the 7th International scientific and technical conference]. Kolomna 2013. In 3 books. Vol. 1, pp. 862-868.
3. Shabel'nikov A.N. i dr. Sistemy avtomatizatsii sortirovochnykh gorok na osnove sovremennykh komp'yuternykh tekhnologiy: Uchebnik dlya vuzov zh/d transporta [The automation system of sorting yards on the basis of modern computer technology: Textbook for universities railway transport], By ed A.N. Shabel'nikova. Rostov-on-Don: RGUPS, 2010, 436 p.
4. Glover F. Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 1986, pp. 533-549.
5. Reeves C.R., ed. Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publishing, 1993.
6. Boroznov V.O., Popov G.A. Sistemnyy analiz raboty sortirovochnoy stantsii na osnove metoda «derevo tseley» [The system analysis of sorting station's work on the basis of the method "tree of objectives"], Vestn. Astrakhan. gos. tekhn. un-ta. Ser. upravlenie, vychisl. tekhn. inform. [Vestnik of Astrakhan State Technical University. Series: Management, Computer Science and
Informatics], 2009, No. 2, pp. 13-21.
7. Glover F. Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 1986, No. 131, pp. 533-549.
8. Glover F. and Laguna M. Tabu Search. Norwell: Kluwer Academic Publishers, 1997.
9. Allen J.F. Towards a General Theory of Action and Time, Artificial Intelligence, 1984, No. 23(2).
10. Papadimitriou C.H. and Steiglitz K. Combinatorial Optimization – Algorithms and Complexity. New York: Dover Publications, 1982.
11. Panteleev A.V. Metody global'noy optimizatsii: Metaevristicheskie strategii i algoritmy [Methods of global optimization: a Metaheuristic strategies and algorithms]. Moscow: Izd-vo Vuzovskaya kniga, 2013, 244 p.
12. L. Moccia J.-F. Cordeau, G. Laporte. An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows, Journal of the Operational Research Society, 2012, No. 63, pp. 232-244.
13. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computation]. Moscow: Fizmatlit, 2012, 260 p.
14. Shcherbina O.A. Metaevristicheskie algoritmy dlya zadach kombinatornoy optimizatsii [Metaheuristic algorithms for combinatorial optimization problems], Tavricheskiy vestnik informatiki i matematiki [Taurida Journal of Computer Science Theory and Mathematics], 2014, No. 1 (24), 24 p.
15. Rudnev A.S. Veroyatnostnyy poisk s zapretami v zadache upakovki [Probabilistic search with exclusions in the task of packing], Diskretnyy analiz i issledovanie operatsiy [Diskretnyi Analiz i Issledovanie Operatsii. Iyul'-avgust 2009, Vol. 16, No. 4, pp. 61-86.
16. Stьtzle T. Iterated local search for the quadratic assignment problem, European Journal of Operational Research, November 2006 Vol. 174, Issue 3, pp. 1519-1539.
17. Pham D.T. & Karaboga D. Intelligent Optimisation Techniques, Springer-Verlag, London, 2000.
18. Dorigo M. Optimization, Learning and Natural Algorithms. PhD, Politecnico di Milano, 1992.
19. Yaghini M., Foroughi A. & Nadjari B. Solving railroad blocking problem using ant colony optimization algorithm, Applied Mathematical Modelling, 2011, No. 35, pp. 5579-5591.
20. Maniezzo V., Stutzle T. & Vob, S. Matheuristics: hybridizing metaheuristics and mathematical programming. New York, Springer, 2009.

Comments are closed.