Marszrutowanie niejednorodnej floty pojazdów w regularnej strukturze dróg transportowych

• Autorzy: Bocewicz G. , Muszyński W. , Banaszak Z.

Warianty tytułu

EN

Heterogeneous fleet vehicle routing and scheduling subject to mesh-like route layout constraints

• Języki publikacji: PL

Abstrakty

PL

Zachowanie Systemu Transportu Materiałowego (STM) obejmujące różne rodzaje transportu musi być dopuszczalne w sensie bezkolizyjnej, wolnej od zatorów realizacji operacji transportu, tak, aby możliwa była realizacja współbieżnych przepływów materiałowych. Skoro strumienie przepływów materiałowych, przebiegające różnymi możliwymi marszrutami determinują zachowanie STM, istotnym zagadnieniem jest poszukiwanie odpowiedzi na pytanie, w jakich rodzajach struktur STM możliwe jest zagwarantowanie pożądanego zachowania i jak takie pożądane zachowanie systemu można osiągnąć. Tego rodzaju pytania są typowymi pytaniami w zagadnieniach marszrutowania, które należą do problemów obliczeniowo trudnych. Odpowiednie ich sformułowanie, dla regularnych i fraktalo-podobnych struktur może prowadzić do znaczącej redukcji problemów obliczeniowych. Tego rodzaje struktury umożliwiają ewaluacje możliwych marszrut i harmonogramowanie operacji transportowych wzdłuż ścieżek transportowych w czasie wielomianowym. Rozważane w pracy marszruty przepływów, wykonywane przez STM, są kolejno wykonywanymi operacjami transportu, za pomocą wózków AGV, oraz operacjami produkcyjnymi wykonywanymi na odpowiednich maszynach. W pracy założono, że operacje te są wykonywane w zamkniętych pętlach sieci, dla których potencjalne konflikty są rozwiązywane w oparciu o reguły priorytetowania dostępu do współdzielonych zasobów. Istota problemu polega na znalezieniu wystarczających warunków zapewniających osiągnięcie w systemie STM ustalonego stacjonarnego zachowania cyklicznego. Proponowana metoda jest zilustrowana przykładem.

EN

The behavior of a Material Transportatian System (MTS) encompassing movement of various transport modes has to be admissible, i.e. collision- and congestion-free, as to guarantee deadlock-free different flows of concurrently transported goods. Since the material flows following possible machining routes serviced by MTS determine its behavior the following questions occur: what kind of MTS structure can guarantee a given behavior, and what admissible behavior can be reachable in a given MTS structure? These questions are typical for vehicle routing problems which are computationally hard. Their formulation within the framework of mesh-like and fractal-like structures enables, however, to get a significant reduction on the size. Such structures enable to evaluate admissible routings and schedules following flow-paths of material transportalion in a polynomial time. Considered in the paper production routes followed by MTS are serviced by operations subsequently executed on AGVs and machine tools. Assuming transport operations are executed by AGVs arranged in a streaming closed-loops network where potential conflicts are resolved by priority dispatching rules assigned to shared resources the main problem boils down to the searching for sufficient conditions guaranteeing MTS cyclic steady state behavior. Implementation of proposed conditions is illustrated through multiple examples.

Słowa kluczowe

PL

systemy robotów; droga transportowa; pojazdy; marszrutowanie

EN

robot systems; transport path; vehicles; route

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2016
• Tom: z. 195, t. 1
• Strony: 289--299
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Bocewicz G.

• Wydział Elektroniki i Informatyki, Politechnika Koszalińska, Śniadeckich 2, 75-453 Koszalin

autor

Muszyński W.

• Katedra Cybernetyki i Robotyki, Wydział Elektroniki, Politechnika Wrocławska, Janiszewskiego 11-17, 50-372 Wrocław

autor

Banaszak Z.

• Wydział Elektroniki i Informatyki, Politechnika Koszalińska, Śniadeckich 2, 75-453 Koszalin

Bibliografia

• [1] Bocewicz G., Muszyński W., Banaszak Z., Models of multimodal networks and transport processes. Bulletin of the Polish Academy of Sciences, Technical Sciences, Vol. 63, No. 3, 2015, 635-650
• [2] Bocewicz G., Nielsen I., Banaszak Z., Automated Guided Vehicles Fleet Match-up Scheduling with Production Flow Constraints. Engineering Applications of Artificial Intelligence, Vol. 30, 2014, 49-62.
• [3] Bocewicz G., Wójcik R., Banaszak Z.,Pawlewski P., Multimodal Processes Rescheduling: Cyclic Steady States Space Approach. Mathematical Problems in Engineering, 2013: 1-24. Article ID 407096
• [4] Brito J., Campos C., Castro J.P., Martinez F.J., Melian B., Moreno J.A., Moreno J.M., Fuzzy Vehicle Routing Problem with Time Windows, L. Magdalena, M. Ojeda-Aciego, J.L. Verdegay (eds): Proceedings of IPMU'08, Torremolinos (Malaga), 2008, 1266-1273
• [5] Cheng C. H., Balakrishnan J., Multi-Period Planning and Uncertainty Issues in Cellular Manufacturing: A Review and Future Directions, The European Journal of Operational Research, 177, 2007, 281-309
• [6] Eguia I.,Lozano S., Racero J., Guerrero F., Cell design and loading with alternative routing in cellular reconfigurable manufacturing systems, In: 7th IFAC Conference on Manufacturing Modelling, Management, and Control, Russia, 2013, 1744-1749
• [7] Fazlollahtabar, H., Saidi-Mehrabad M. Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems: A Review Study. Journal of Intelligent & Robotic Systems. Springer, Vol. 77, Issue 3, 525-545.
• [8] Friedrich M. A multi-modal transport model for integrated planning. Proceedings of 8th World Conference on Transport Research. 1999, 1-14
• [9] Gambardella L.M., Taillard E., Agazzi G. A multiple ant colony system for vehicle routing problems with time windows. In D. Come, M. Dorigo, & F. Glover (Eds.), New ideas in optimization, London: McGraw-Hill, 1999, 63-79
• [10] Khayat G.E., Langevin A., Riope D., Integrated Production and Material Handling Scheduling Using Mathematical Programming and Constraint Programming. European Journal of Operational Research, Vol. 175, Issue 3, 2006, 1818-1832
• [11] Kumar S.N., Panneerselvam R., A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm. Intelligent Information Management, 7, 2015,181-194
• [12] Pradhananga R., Taniguchi E., Yamada T., Ant colony system based routing and scheduling for hazardous material transportation, Procedia – Social and Behavioral Sciences, Vol. 2, Issue 3, 2010, 6097-6108
• [13] Silva A.-L., Critical Analysis of Layout Concepts: Functional Layout, Cell Layout, Product Layout, Modular Layout, Fractal Layout, Small Factory Layout. In: Challenges and Maturity of Production Engineering: competitiveness of enterprises, working conditions, environment. Proc. of the XVI International Conference on Industrial Engineering and Operations Management, Sao Carlos, Brazil, 20l0, 1-13
• [14] Sitek P., Wikarek J., A hybrid framework for the modelling and optimisation of decision problems in sustainable supply chain management. International Journal of Production Research, Vol. 53(21), 2015, 1-18
• [15] Wan Y.-T., Material Transport System Design In Manufacturing, PhD dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, May 2006
• [16] Qiu L., Hsu W.-J., Huang S.-Y., Wang H., Scheduling and routing algorithms for AGVs: a survey. International Journal of Production Research, Vol. 40, Issue 3, 2002, 745-760

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.