Generalized public transportation scheduling using max-plus algebra

Kistosil Fahim Subiono; Fahim Kistosil; Dieky Adzkiya

Kybernetika (2018)

  • Volume: 54, Issue: 2, page 243-267
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Subiono, Kistosil Fahim, Kistosil, Fahim, and Adzkiya, Dieky. "Generalized public transportation scheduling using max-plus algebra." Kybernetika 54.2 (2018): 243-267. <http://eudml.org/doc/294798>.

@article{Subiono2018,
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.},
author = {Subiono, Kistosil Fahim, Kistosil, Fahim, Adzkiya, Dieky},
journal = {Kybernetika},
keywords = {max-plus algebra; strongly connected road network; scheduling},
language = {eng},
number = {2},
pages = {243-267},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Generalized public transportation scheduling using max-plus algebra},
url = {http://eudml.org/doc/294798},
volume = {54},
year = {2018},
}

TY - JOUR
AU - Subiono, Kistosil Fahim
AU - Kistosil, Fahim
AU - Adzkiya, Dieky
TI - Generalized public transportation scheduling using max-plus algebra
JO - Kybernetika
PY - 2018
PB - Institute of Information Theory and Automation AS CR
VL - 54
IS - 2
SP - 243
EP - 267
AB - 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.
LA - eng
KW - max-plus algebra; strongly connected road network; scheduling
UR - http://eudml.org/doc/294798
ER -

References

top
  1. Arnold, P., Peeters, D., Thomas, I., 10.1016/j.tre.2003.08.005, Transport. Res. Part E: Logist. Transport. Rev. 40 (2004), 255-270. MR1031470DOI10.1016/j.tre.2003.08.005
  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. MR1204266
  3. Braker, J. G., Algorithms and Applications in Timed Discrete Event Systems., PhD Thesis, Delft University of Technology, 1993. MR2714745
  4. Castelli, L., Pesenti, R., Ukovich, W., 10.1016/j.ejor.2003.02.002, Europ. J. Oper. Res. 155 (2004), 603-615. MR2054682DOI10.1016/j.ejor.2003.02.002
  5. Chen, B., Cheng, H. H., 10.1109/tits.2010.2048313, IEEE Trans. Intell. Transport. Systems 11 (2010), 485-497. DOI10.1109/tits.2010.2048313
  6. Cochet-Terrasson, J., Cohen, G., Gaubert, S., McGettrick, M., Quadrat, J.-P., 10.1016/s1474-6670(17)42067-2, In: Proc. IFAC Conference on System Structure and Control, 1998, pp. 699-706. DOI10.1016/s1474-6670(17)42067-2
  7. Crainic, T. G., Rousseau, J.-M., 10.1016/0191-2615(86)90019-6, Transport. Res. Part B: Methodological 20 (1986), 225-242. DOI10.1016/0191-2615(86)90019-6
  8. Febbraro, A. Di, Sacone, S., 10.1109/icsmc.1998.725397, In: Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1998, pp. 131-135. DOI10.1109/icsmc.1998.725397
  9. Febbraro, A. Di, Sacco, N., 10.1016/j.conengprac.2004.04.008, Control Engrg. Practice 12 (2004), 1225-1239. DOI10.1016/j.conengprac.2004.04.008
  10. Etschmaier, M. M., 10.1016/0005-1098(80)90035-7, Automatica 16 (1980), 255-264. DOI10.1016/0005-1098(80)90035-7
  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, 10.1007/s10626-016-0235-4, Discrete Event Dynamic Systems 27 (2017), 181-203. MR3600889DOI10.1007/s10626-016-0235-4
  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., 10.1016/j.laa.2010.01.014, Linear Algebra Appl. 435 (2011), 1626-1636. MR2810660DOI10.1016/j.laa.2010.01.014
  15. Heidergott, B., Olsder, G. J., Woude, J.W. van der, 10.1515/9781400865239, Princeton University Press, 2006. MR2188299DOI10.1515/9781400865239
  16. Herrero-Perez, D., Martinez-Barbera, H., 10.1109/tii.2009.2038691, IEEE Trans. Industrial Informatics 6 (2010), 166-180. DOI10.1109/tii.2009.2038691
  17. James, S. J., James, C., Evans, J. A., 10.1016/j.ijrefrig.2006.03.017, Int. J. Refrigeration 29 (2006), 947-957. DOI10.1016/j.ijrefrig.2006.03.017
  18. Levin, A., 10.1287/trsc.5.3.232, Transport. Sci. 5 (1971), 232-255. MR0293994DOI10.1287/trsc.5.3.232
  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., 10.1287/trsc.12.3.232, Transport. Sci. 12 (1978), 232-249. DOI10.1287/trsc.12.3.232
  21. Subiono, Woude, J.W. van der, 10.1023/a:1008315821604, Discrete Event Dynamic Systems 10 (2000), 369-389. MR1791847DOI10.1023/a:1008315821604
  22. Subiono, On Classes of Min-max-plus Systems and their Applications., PhD Thesis, Delft University of Technology, 2000. MR1897646
  23. Subiono, Fahim, K., 10.12988/ams.2016.618, Appl. Math. Sci. 10 (2016), 477-486. DOI10.12988/ams.2016.618

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.