Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
max-plus algebra; strongly connected road network; scheduling
max-plus algebra; strongly connected road network; scheduling
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.
References:
[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 10.1016/j.tre.2003.08.005 | MR 1031470
[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
[3] Braker, J. G.: Algorithms and Applications in Timed Discrete Event Systems. PhD Thesis, Delft University of Technology, 1993. MR 2714745
[4] Castelli, L., Pesenti, R., Ukovich, W.: Scheduling multimodal transportation systems. Europ. J. Oper. Res. 155 (2004), 603-615. DOI 10.1016/j.ejor.2003.02.002 | MR 2054682
[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 10.1109/tits.2010.2048313
[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 10.1016/s1474-6670(17)42067-2
[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 10.1016/0191-2615(86)90019-6
[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 10.1109/icsmc.1998.725397
[9] Febbraro, A. Di, Sacco, N.: 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] Etschmaier, M. M.: Fuzzy controls for maintenance scheduling in transportation systems. Automatica 16 (1980), 255-264. DOI 10.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: 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 | MR 3600889
[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 10.1016/j.laa.2010.01.014 | MR 2810660
[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 10.1515/9781400865239 | MR 2188299
[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 10.1109/tii.2009.2038691
[17] James, S. J., James, C., Evans, J. A.: Modelling of food transportation systems - a review. Int. J. Refrigeration 29 (2006), 947-957. DOI 10.1016/j.ijrefrig.2006.03.017
[18] Levin, A.: Scheduling and fleet routing models for transportation systems. Transport. Sci. 5 (1971), 232-255. DOI 10.1287/trsc.5.3.232 | MR 0293994
[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 10.1287/trsc.12.3.232
[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 10.1023/a:1008315821604 | MR 1791847
[22] Subiono: On Classes of Min-max-plus Systems and their Applications. PhD Thesis, Delft University of Technology, 2000. MR 1897646
[23] Subiono, Fahim, K.: On computing supply chain scheduling using max-plus algebra. Appl. Math. Sci. 10 (2016), 477-486. DOI 10.12988/ams.2016.618
Search
Partner of
