Geodesic
Generalized public transportation scheduling using max-plus algebra
Kybernetika, Tome 54 (2018) no. 2, pp. 243-267 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2018-2-0243
Classification : 15A15, 15F10
Keywords: max-plus algebra; strongly connected road network; scheduling 
@article{10_14736_kyb_2018_2_0243,
     author = {Subiono and Kistosil, Fahim and Adzkiya, Dieky},
     title = {Generalized public transportation scheduling using max-plus algebra},
     journal = {Kybernetika},
     pages = {243--267},
     year = {2018},
     volume = {54},
     number = {2},
     doi = {10.14736/kyb-2018-2-0243},
     mrnumber = {3807713},
     zbl = {06890418},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0243/}
}
TY  - JOUR
AU  - Subiono
AU  - Kistosil, Fahim
AU  - Adzkiya, Dieky
TI  - Generalized public transportation scheduling using max-plus algebra
JO  - Kybernetika
PY  - 2018
SP  - 243
EP  - 267
VL  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0243/
DO  - 10.14736/kyb-2018-2-0243
LA  - en
ID  - 10_14736_kyb_2018_2_0243
ER  - 
%0 Journal Article
%A Subiono
%A Kistosil, Fahim
%A Adzkiya, Dieky
%T Generalized public transportation scheduling using max-plus algebra
%J Kybernetika
%D 2018
%P 243-267
%V 54
%N 2
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-2-0243/
%R 10.14736/kyb-2018-2-0243
%G en
%F 10_14736_kyb_2018_2_0243
Subiono; Kistosil, Fahim; Adzkiya, Dieky. Generalized public transportation scheduling using max-plus algebra. Kybernetika, Tome 54 (2018) no. 2, pp. 243-267. doi: 10.14736/kyb-2018-2-0243

[1] Arnold, P., Peeters, D., Thomas, I.: Modelling a rail/road intermodal transportation system. Transport. Res. Part E: Logist. Transport. Rev. 40 (2004), 255-270. | DOI | MR

[2] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity, an Algebra for Discrete Event Systems. John Wiley and Sons, 1992. | MR

[3] Braker, J. G.: Algorithms and Applications in Timed Discrete Event Systems. PhD Thesis, Delft University of Technology, 1993. | MR

[4] Castelli, L., Pesenti, R., Ukovich, W.: Scheduling multimodal transportation systems. Europ. J. Oper. Res. 155 (2004), 603-615. | DOI | MR

[5] Chen, B., Cheng, H. H.: A review of the applications of agent technology in traffic and transportation systems. IEEE Trans. Intell. Transport. Systems 11 (2010), 485-497. | DOI

[6] Cochet-Terrasson, J., Cohen, G., Gaubert, S., McGettrick, M., Quadrat, J.-P.: Numerical computation of spectral elements in max-plus algebra. In: Proc. IFAC Conference on System Structure and Control, 1998, pp. 699-706. | DOI

[7] Crainic, T. G., Rousseau, J.-M.: 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

[8] Febbraro, A. Di, Sacone, S.: 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

[9] Febbraro, A. Di, Sacco, N.: On modelling urban transportation networks via hybrid Petri nets. Control Engrg. Practice 12 (2004), 1225-1239. | DOI

[10] Etschmaier, M. M.: Fuzzy controls for maintenance scheduling in transportation systems. Automatica 16 (1980), 255-264. | DOI

[11] Fahim, K., Hanafi, L., Ayu, F.: Monorail and tram scheduling which integrated Surabaya using max-plus algebra. In: International Seminar on Innovation in Mathematics and Mathematics Education, 2014.

[12] Fahim, K., Subiono, Woude, J. W. van der: On a generalization of power algorithms over max-plus algebra. Discrete Event Dynamic Systems 27 (2017), 181-203. | DOI | MR

[13] Goverde, R. M. P.: Punctuality of Railway Operations and Timetable Stability Analysis. PhD Thesis, Delft University of Technology, 2005.

[14] Gursoy, B. B., Mason, O.: Spectral properties of matrix polynomials in the max algebra. Linear Algebra Appl. 435 (2011), 1626-1636. | DOI | MR

[15] Heidergott, B., Olsder, G. J., Woude, J.W. van der: Max Plus at Work-Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications. Princeton University Press, 2006. | DOI | MR

[16] Herrero-Perez, D., Martinez-Barbera, H.: Modeling distributed transportation systems composed of flexible automated guided vehicles in flexible manufacturing systems. IEEE Trans. Industrial Informatics 6 (2010), 166-180. | DOI

[17] James, S. J., James, C., Evans, J. A.: Modelling of food transportation systems - a review. Int. J. Refrigeration 29 (2006), 947-957. | DOI

[18] Levin, A.: Scheduling and fleet routing models for transportation systems. Transport. Sci. 5 (1971), 232-255. | DOI | MR

[19] Koelemeijer, G. Soto y: On the Behaviour of Classes of Min-max-plus Systems. PhD Thesis, Delft University of Technology, 2003.

[20] Stein, D. M.: Scheduling dial-a-ride transportation systems. Transport. Sci. 12 (1978), 232-249. | DOI

[21] Subiono, Woude, J.W. van der: Power algorithms for (max,+)- and bipartite (min,max,+)-systems. Discrete Event Dynamic Systems 10 (2000), 369-389. | DOI | MR

[22] Subiono: On Classes of Min-max-plus Systems and their Applications. PhD Thesis, Delft University of Technology, 2000. | MR

[23] Subiono, Fahim, K.: On computing supply chain scheduling using max-plus algebra. Appl. Math. Sci. 10 (2016), 477-486. | DOI

Cité par Sources :