Kybernetika 54 no. 2, 243-267, 2018

Generalized public transportation scheduling using max-plus algebra

 Subiono, Kistosil Fahim and Dieky AdzkiyaDOI: 10.14736/kyb-2018-2-0243

Abstract:

In this paper, we discuss the scheduling of a wide class of transportation systems. In particular, we derive an algorithm to generate a regular schedule by using max-plus algebra. Inputs of this algorithm are a graph representing the road network of public transportation systems and the number of public vehicles in each route. The graph has to be strongly connected, which means there is a path from any vertex to every vertex. Let us remark that the algorithm is general in the sense that we can allocate any number of vehicles in each route. The algorithm itself consists of two main steps. In the first step, we use a novel procedure to construct the model. Then in the second step, we compute a regular schedule by using the power algorithm. We describe our proposed framework for an example.

Keywords:

max-plus algebra, strongly connected road network, scheduling

Classification:

15A15, 15F10

paper.pdf

References:

  1. P. Arnold, D. Peeters and I. Thomas: Modelling a rail/road intermodal transportation system. Transport. Res. Part E: Logist. Transport. Rev. 40 (2004), 255-270.   DOI:10.1016/j.tre.2003.08.005
  2. F. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat: Synchronization and Linearity, an Algebra for Discrete Event Systems. John Wiley and Sons, 1992.   CrossRef
  3. J. G. Braker: Algorithms and Applications in Timed Discrete Event Systems. PhD Thesis, Delft University of Technology, 1993.   CrossRef
  4. L. Castelli, R. Pesenti and W. Ukovich: Scheduling multimodal transportation systems. Europ. J. Oper. Res. 155 (2004), 603-615.   DOI:10.1016/j.ejor.2003.02.002
  5. B. Chen and H. H. Cheng: A review of the applications of agent technology in traffic and transportation systems. IEEE Trans. Intell. Transport. Systems 11 (2010), 485-497.   DOI:10.1109/tits.2010.2048313
  6. J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. McGettrick and J.-P. Quadrat: Numerical computation of spectral elements in max-plus algebra. In: Proc. {IFAC} Conference on System Structure and Control, 1998, pp. 699-706.   DOI:10.1016/s1474-6670(17)42067-2
  7. T. G. Crainic and J.-M. Rousseau: Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem. Transport. Res. Part B: Methodological 20 (1986), 225-242.   DOI:10.1016/0191-2615(86)90019-6
  8. A. Di Febbraro and S. Sacone: Hybrid modelling of transportation systems by means of {Petri} nets. In: Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1998, pp. 131-135.   DOI:10.1109/icsmc.1998.725397
  9. A. Di Febbraro and N. Sacco: On modelling urban transportation networks via hybrid {Petri} nets. Control Engrg. Practice 12 (2004), 1225-1239.   DOI:10.1016/j.conengprac.2004.04.008
  10. M. M. Etschmaier: Fuzzy controls for maintenance scheduling in transportation systems. Automatica 16 (1980), 255-264.   DOI:10.1016/0005-1098(80)90035-7
  11. K. Fahim, L. Hanafi and F. Ayu: Monorail and tram scheduling which integrated {S}urabaya using max-plus algebra. In: International Seminar on Innovation in Mathematics and Mathematics Education, 2014.   CrossRef
  12. K. Fahim, Subiono and J. W. van der Woude: On a generalization of power algorithms over max-plus algebra. Discrete Event Dynamic Systems 27 (2017), 181-203.   DOI:10.1007/s10626-016-0235-4
  13. R. M. P. Goverde: Punctuality of Railway Operations and Timetable Stability Analysis. PhD Thesis, Delft University of Technology, 2005.   CrossRef
  14. B. B. Gursoy and O. Mason: Spectral properties of matrix polynomials in the max algebra. Linear Algebra Appl. 435 (2011), 1626-1636.   DOI:10.1016/j.laa.2010.01.014
  15. B. Heidergott, G. J. Olsder and J.W. van der Woude: Max Plus at Work-Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications. Princeton University Press, 2006.   DOI:10.1515/9781400865239
  16. D. Herrero-Perez and H. Martinez-Barbera: Modeling distributed transportation systems composed of flexible automated guided vehicles in flexible manufacturing systems. IEEE Trans. Industrial Informatics 6 (2010), 166-180.   DOI:10.1109/tii.2009.2038691
  17. S. J. James, C. James and J. A. Evans: Modelling of food transportation systems - a review. Int. J. Refrigeration 29 (2006), 947-957.   DOI:10.1016/j.ijrefrig.2006.03.017
  18. A. Levin: Scheduling and fleet routing models for transportation systems. Transport. Sci. 5 (1971), 232-255.   DOI:10.1287/trsc.5.3.232
  19. G. Soto y Koelemeijer: On the Behaviour of Classes of Min-max-plus Systems. PhD Thesis, Delft University of Technology, 2003.   CrossRef
  20. D. M. Stein: Scheduling dial-a-ride transportation systems. Transport. Sci. 12 (1978), 232-249.   DOI:10.1287/trsc.12.3.232
  21. Subiono and J.W. van der Woude: Power algorithms for (max,+)- and bipartite (min,max,+)-systems. Discrete Event Dynamic Systems 10 (2000), 369-389.   DOI:10.1023/a:1008315821604
  22. Subiono: On Classes of Min-max-plus Systems and their Applications. PhD Thesis, Delft University of Technology, 2000.   CrossRef
  23. Subiono and K. Fahim: On computing supply chain scheduling using max-plus algebra. Appl. Math. Sci. 10 (2016), 477-486.   DOI:10.12988/ams.2016.618