| Title:
|
Generalized public transportation scheduling using max-plus algebra (English) |
| Author:
|
Subiono |
| Author:
|
Kistosil, Fahim |
| Author:
|
Adzkiya, Dieky |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
54 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
243-267 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
max-plus algebra |
| Keyword:
|
strongly connected road network |
| Keyword:
|
scheduling |
| MSC:
|
15A15 |
| MSC:
|
15F10 |
| idZBL:
|
Zbl 06890418 |
| idMR:
|
MR3807713 |
| DOI:
|
10.14736/kyb-2018-2-0243 |
| . |
| Date available:
|
2018-05-30T15:59:46Z |
| Last updated:
|
2020-01-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147192 |
| . |
| Reference:
|
[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. MR 1031470, 10.1016/j.tre.2003.08.005 |
| Reference:
|
[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 1204266 |
| Reference:
|
[3] Braker, J. G.: Algorithms and Applications in Timed Discrete Event Systems..PhD Thesis, Delft University of Technology, 1993. MR 2714745 |
| Reference:
|
[4] Castelli, L., Pesenti, R., Ukovich, W.: Scheduling multimodal transportation systems..Europ. J. Oper. Res. 155 (2004), 603-615. MR 2054682, 10.1016/j.ejor.2003.02.002 |
| Reference:
|
[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. 10.1109/tits.2010.2048313 |
| Reference:
|
[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. 10.1016/s1474-6670(17)42067-2 |
| Reference:
|
[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. 10.1016/0191-2615(86)90019-6 |
| Reference:
|
[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. 10.1109/icsmc.1998.725397 |
| Reference:
|
[9] Febbraro, A. Di, Sacco, N.: On modelling urban transportation networks via hybrid Petri nets..Control Engrg. Practice 12 (2004), 1225-1239. 10.1016/j.conengprac.2004.04.008 |
| Reference:
|
[10] Etschmaier, M. M.: Fuzzy controls for maintenance scheduling in transportation systems..Automatica 16 (1980), 255-264. 10.1016/0005-1098(80)90035-7 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 3600889, 10.1007/s10626-016-0235-4 |
| Reference:
|
[13] Goverde, R. M. P.: Punctuality of Railway Operations and Timetable Stability Analysis..PhD Thesis, Delft University of Technology, 2005. |
| Reference:
|
[14] Gursoy, B. B., Mason, O.: Spectral properties of matrix polynomials in the max algebra..Linear Algebra Appl. 435 (2011), 1626-1636. MR 2810660, 10.1016/j.laa.2010.01.014 |
| Reference:
|
[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. MR 2188299, 10.1515/9781400865239 |
| Reference:
|
[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. 10.1109/tii.2009.2038691 |
| Reference:
|
[17] James, S. J., James, C., Evans, J. A.: Modelling of food transportation systems - a review..Int. J. Refrigeration 29 (2006), 947-957. 10.1016/j.ijrefrig.2006.03.017 |
| Reference:
|
[18] Levin, A.: Scheduling and fleet routing models for transportation systems..Transport. Sci. 5 (1971), 232-255. MR 0293994, 10.1287/trsc.5.3.232 |
| Reference:
|
[19] Koelemeijer, G. Soto y: On the Behaviour of Classes of Min-max-plus Systems..PhD Thesis, Delft University of Technology, 2003. |
| Reference:
|
[20] Stein, D. M.: Scheduling dial-a-ride transportation systems..Transport. Sci. 12 (1978), 232-249. 10.1287/trsc.12.3.232 |
| Reference:
|
[21] Subiono, Woude, J.W. van der: Power algorithms for (max,+)- and bipartite (min,max,+)-systems..Discrete Event Dynamic Systems 10 (2000), 369-389. MR 1791847, 10.1023/a:1008315821604 |
| Reference:
|
[22] Subiono: On Classes of Min-max-plus Systems and their Applications..PhD Thesis, Delft University of Technology, 2000. MR 1897646 |
| Reference:
|
[23] Subiono, Fahim, K.: On computing supply chain scheduling using max-plus algebra..Appl. Math. Sci. 10 (2016), 477-486. 10.12988/ams.2016.618 |
| . |
