Optimization of periodic unitary online schedule of transport tasks of highway road trains

• Autorzy: Oliskevych M.

Identyfikatory

DOI

10.21307/tp. 2018.13.1.10

• Języki publikacji: EN

Abstrakty

EN

The paper is devoted to the problem of optimization of transport tasks’ execution schedule. The exploitation of a group of interdependent highway road trains is considered. The task differs from the known ones by limitations of the duration of a cycle within which a maximum number of goods transportation orders must be fulfilled. There are also limited intervals of time when loading and unloading of vehicles is permitted at appropriate points of a transport network. The solution of the problem consists in distributing a given number of road trains between orders, finding the shortest path for each of them, and determining the time of their departure and arrival provided the absence of idle runs and with minimal time delays of the process. It is shown that a maximum numer of completed tasks are proportional to the duration of the cycle up to a certain limit only. The optimization is carried out for two options: in the absence and presence of restrictions on repeatability of freight flows from one point. The used algorithm guarantees an exact solution for an acceptable period of time for a small-dimensional task.

Słowa kluczowe

EN

scheduling; transport cycle; process delay; routing

PL

harmonogramowanie; cykl transportowy; opóźnienie procesu; trasowanie

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Transport Problems
• Rocznik: 2018
• Tom: T. 13, z. 1
• Strony: 111--122
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Oliskevych M.

• L’viv Polytechnic National University, Institute of Engineering Mechanics and Transport, Vehicle Operation and Repair Department 32, Bandery Str., 79000 Lviv, Ukraine

Bibliografia

• 1. Танаев, В.С. & Сотсков, Ю.Н. & Струсевич В.А. Теория расписаний. Многостадийные системы. Москва: Наука. 1989. 328 p. [In Russian: Tanaev, V.S. & Sotskov, Y.N. & Strusevich, V.A. Theory of schedules. Multistage systems. Moscow: Science].
• 2. Blazewicz, J. & Ecker, K. & Pesch, E. & Schmidt, G. & Weglarz, J. Handbook on Scheduling. From Theory to Applications. Berlin/New York: Springer. 2007. 647 p.
• 3. Dorit, S. & Hochbauma, A. L. Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discrete Optimization. 2006. Vol. 3. P. 327–340 Available at: http://www.sciencedirect.com/science/article/pii/S1572528606000454
• 4. Wojakowski, P. & Warżołek, D. The classification of scheduling problems under production uncertainty. Research in logistic & production. 2014. Vol. 4. No. 3. P. 245-255. Available at: http://www.research.logistyka-produkcja.pl/images/stories/Numer_14/6.pdf
• 5. Романова, А.А. & Сервах, В.В. Оптимизация выпуска однотипных деталей на основе циклических расписаний. Дискретный анализ и исследование операций. 2008. Vol. 15. Nr. 5. P. 47-60. Available at: http://math.nsc.ru/publishing/DAOR/content/2008/05/47.pdf [In Russian: Romanova, A.A. & Servakh, V.V. Optimization of the release of the same parts on the basis of cyclic schedules. Discrete analysis and operations research].
• 6. Draper, D. & Jonsson, A. & Clements, D. & and Joslin, D. Cyclic scheduling. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. 1999. P. 6-17. Available at: https://ti.arc.nasa.gov/m/pub-archive/48h/0048%20(Jonsson).pdf
• 7. Zimmermann, H.J. Fuzzy Set Theory and Its Applications. Fourth Edition. London. Kluwer Academic Publishers. 2001. 514 p.
• 8. Bocewicz, G. & Wójcik, R. & Z. Banaszak, Z-A. & Pawlewski, P. Multimodal Processes Rescheduling: Cyclic Steady States Space Approach. Mathematical Problems in Engineering. 2013. Available at: http://dx.doi.org/10.1155/2013/407096
• 9. Herroelen, W. & Demeulemeester, E. & De Revck, B. A classification scheme for project scheduling problems. Katholieke Universiteit Leuven. 1997. Available at: http://econ.kuleuven.ac.be/tew/academic/prodbel
• 10. Tretyakov, A.V. Automation of scheduling for periodic real-time systems. Proceedings of the Institute for System Programming. 2012. Vol. 22. P. 375-400. Available at: http://www.ispras.ru/proceedings/docs/2012/22/isp_22_2012_375.pdf
• 11. Akan, B. & Ameri, E.A. & Curuklu, B. Scheduling for Multiple Type Objects Using POPStar Planner. In: Proceedings of the 19th IEEE International Conference on Emerging Technologies and Factory Automation. Barcelona. 2014. P. 1-7. Available at: http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-26465
• 12. Kampmeyer, T. Cyclic Scheduling Problems. Dissertation. Fachbereich Mathematik / Informatik Universitat Osnabruck. Available at: http://webdoc.sub.gwdg.de/ebook/dissts/Osnabrueck/Kampmeyer2006.pdf
• 13. Лазарев, А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации. PhD thesis. Москва: МГТУ. 2007. 36 p. [In Russian: Lazarev, A. A. Methods and algorithms for solving scheduling problems for one and several instruments and their application for combinatorial optimization problems. PhD thesis. Moscow: MSTU].
• 14. Meireles, R. Simulation modelling of Vitória-Minas closed-loop Rail Network. Vitória, ES.: UFES. 2010.
• 15. Bektas, T. The multiple travelling salesman problem: an overview of formulations and solution procedures. Omega. 2006. Vol. 34. No. 3. P. 209-219. Available at: http://www.sciencedirect.com/science/article/pii/S0305048304001550
• 16. Базилевич, Р. & Кутельмах, Р. Дослідження ефективності існуючих алгоритмів для розв’язання задачі комівояжера. Вісник Національного університету “Львівська політехніка”: Комп’ютерні науки та інформаційні технології. 2009. No. 650. P. 235-244. [In Ukrainian: Bazylevych, R. & Kutelmah, R. Research of efficiency of existing algorithms for solving the traveling salesman problem. Proceedings of the National University "Lviv Polytechnic", Computer Science and Information Technology].
• 17. Castro, L.N. & Zuben, F.J. Artificial Immune Systems. Part I – Basic Theory and Applications. Technical Report. TR – DCA 01/99. December, 1999.
• 18. Kroon, L.G. & Dekker, R. & Vromans, M.J. C. M. Cyclic Railway Timetabling: A Stochastic Optimization Approach. Springer Verlag. LNCS. Algorithmic Methods for Railway Optimization. 2007. Vol. 4359. P. 41-66.
• 19. Prytula, N. & Yeleyko, Y. & Prytula, M. Problems and algorithms of distribution of discrete streams on networks. Visnyk Lviv Univ. Ser. Appl. Math. Comp. Sci. 2006. No. 11. P. 244-254.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018)