Scheduling for Multi-modal Cyclic Transport Systems

eng Article in English DOI:

send Grzegorz Bocewicz *, Zbigniew Banaszak ** * Politechnika Koszalińska - Wydział Elektroniki i Informatyki - Katedra Podstaw Informatyki i Zarządzania ** Politechnika Warszawska - Wydział Zarządzania

Download Article

Abstract

This paper concerns the domain of the multimodal transportation systems composed of buses, trains, trams and subways lines and focuses on the scheduling problems encountered in these systems. Transportation Network Infrastructure (TNI) can be modeled as a network of lines providing cyclic routes for particular kinds of stream-like moving transportation means. Lines are connected by common shared change stations. Depending on TNI timetabling the time of the trip of passengers following different itineraries may dramatically differ, e.g. the same distances along the north-south, and east-west directions may require different travel time. So, the mine question regards of TNI schedulability, e.g. the guarantee the same distances in arbitrarily assumed directions will require approximate traveled time. Considered timetabling problem belongs to NP-hard ones. The declarative model of TNI enabling to formulate cyclic scheduling problem in terms of the constraint satisfaction one is our main contribution. At last, the simulated results manifest the promising properties of the proposed model.

Keywords

constraints programming, cyclic scheduling, declarative modeling, multimodal processes, multimodal transport system

Harmonogramowanie multimodalnych cyklicznych systemów transportowych

Streszczenie

W artykule podejmowana jest problematyka harmonogramowania marszrut pasażerskich realizowanych w multimodalnych systemach komunikacji (MSK) miejskiej obejmujących linie autobusowe, tramwajowe, pociągowe, a także linie metra i linie promowe. MSK modelowany jest jako sieć linii komunikacji miejskiej realizujących swoje cykliczne marszruty transportowe zadaną liczba odpowiednich środków transportu pasażerskiego, tzn. autobusów, tramwajów, pociągów itp. Przyjmuje się, że linie te umożliwiają przesiadanie się pasażerów na wspólnie dzielonych stacjach przesiadkowych. Rozważany problem dotyczy doboru takiej struktury i organizacji ruchu poszczególnych linii, które zapewnią podobne czasy przejazdu (na podobnych dystansach) podróżnych przemieszczających się w różnych kierunkach. Problem ten należy do problemów NP-trudnych. Proponowane w pracy rozwiązanie przyjmuje model deklaratywny MSK sprowadzając rozważany problem harmonogramowania do postaci deterministycznego problemu spełniania ograniczeń. Zamieszczone przykłady implementacji tego problemu w języku programowania z ograniczeniami potwierdzają użyteczność zaproponowanego modelu harmonogramowania MSK.

Słowa kluczowe

harmonogram cykliczny, model deklaratywny, programowanie w logice ograniczeń, transport multimodalny

Bibliography

  1. Bocewicz G., Banaszak Z., Wójcik R.: Design of admissible schedules for AGV systems with constraints: a logic-algebraic approach, [in:] Nguyen N.T., Grzech A., et al. (eds.): Agent and Multi-Agent Systems: Technologies and Applications, ”Lecture Notes in Artificial Intelligence”, Vol. 4496, Springer-Verlag, Berlin-Heidelberg, 2008, 578-587.
  2. Bocewicz G., Banaszak Z.: Declarative approach to cyclic scheduling of multimodal processes, [in:] Golińska P., (ed.): EcoProduction and Logistics, Vol. 1, Springer-Verlag, Berlin-Heidelberg, 2012 [in print].
  3. Levner E., Kats V., Alcaide D., Pablo L, Cheng T.C.E.: Complexity of cyclic scheduling problems: A state-of-the-art survey, ”Computers & Industrial Engineering”, Vol. 59, Issue 2/2010, 352-361.
  4. Polak M., Majdzik P., Banaszak Z., Wójcik R.: The performance evaluation tool for automated prototyping of concurrent cyclic processes. Fundamenta Informatice, „ISO Press”, Vol. 60, No. 1-4, 2004, 269-289.
  5. Song .J.-S., Lee T.-E.: Petri net modeling and scheduling for cyclic job shops with blocking, “Computers & Industrial Engineering”, Vol. 34, No. 2, 1998, 281-295.
  6. Soon-Ki Heo, Kyu-Hwang Lee, Ho-Kyung Lee, In-Beum Lee, Jin Hyun Park: A New Algorithm for Cyclic Scheduling and Design of Multipurpose Batch Plants, ”Ind. Eng. Chem. Res.”, 42 (4), 2003, 836-846.
  7. Wang, B., Yang, H., Zhang, Z.-H.: Research on the train operation plan of the Beijing-Tianjin inter-city railway based on periodic train diagrams, ”Tiedao Xuebao/Journal of the China Railway Society”, Vol. 29 (2), 2007, 8-13.
  8. Von Kampmeyer T.: Cyclic scheduling problems, Ph.D. Dissertation, Fachbereich Mathematik / Informatik, Universität Osnabrück, 2006.