Designing an Optimal Route Network for the Synchronized Trans Gadjah Mada Electric Bus (TGMEB) using Max-Plus Algebra

Franciscus Budi Pranatta, Marcellinus Andy Rudhito, Dewa Putu Wiadnyana Putra

Abstract


We develop an optimal route network and synchronized timetable for the Trans Gadjah Mada Electric Bus (TGMEB), designed to cover the entire campus with 4 buses and 28 stops. Using literature review, field observation, and online mapping, we create three network candidates-one-, two-, and three-terminal-and model each as a max-plus linear discrete-event system. Service period and periodic departures are derived from eigenvalue-eigenvector analysis and implemented in Scilab 5.5.2 with a max-plus toolbox. The two-terminal layout performs best: its average inter-stop travel time is 32% faster than the other alternatives while keeping departures synchronized and coverage intact. The results confirm that jointly selecting the network architecture and its timetable yields superior campus operations. This is the first campus-scale study that co-designs a multi-terminal electric-bus route network and synchronized timetable via max-plus algebra, optimizing departure throughput and average inter-stop travel time. Unfortunately, this design has not been tested on the field.

Keywords


Eigenvalues; Discrete Event System; Max-Plus Algebra; Optimal; Synchronization; Trans Gadjah Mada; Transportation Modelling.

Full Text:

PDF

References


I. Sugiarto, F. J. Permana, and A. Yosep, "Bus schedule modelling in Bandung, Indonesia, using max-plus algebra," IOP Conf Ser Mater Sci Eng, vol. 830, no. 2, pp. 1-6, 2020, doi: 10.1088/1757-899x/830/2/022004.

T. Šfiligoj and A. Peperko, "A max-plus algebraic model of bus bunching and control strategies," in Transportation Research Procedia, Elsevier B.V., 2025, pp. 88-94. doi: 10.1016/j.trpro.2025.02.013.

F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and linearity : an algebra for discrete event systems. Paris: Wiley, 2001. Accessed: Feb. 02, 2024. [Online]. Available: https://www.rocq.inria.fr/metalau/cohen/documents/BCOQ-book.pdf

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

M. A. Rudhito, Aljabar Max-Plus dan Penerapannya. Yogyakarta: Sanata Dharma University Press, 2016.

Z. Liu, "A Novel Model for Train Operation Adjustment in High-Speed Railway based on Max-plus Algebra," International Journal of Circuits, Systems and Signal Processing, vol. 14, pp. 881-887, 2020, doi: 10.46300/9106.2020.14.114.

R. Farrando, N. Farhi, Z. Christoforou, and A. Urban, "A Max-Plus Model Deriving the Effect of a Skip-Stop Policy on the Train Frequency of a Mass Transit Line," SSRN Electronic Journal, pp. 2509109_1-2509109_10, 2022, doi: 10.2139/ssrn.4089614.

E. Carnia, R. Wilopo, H. Napitupulu, N. Anggriani, and A. K. Supriatna, "Modified Kleene Star Algorithm Using Max-Plus Algebra and Its Application in the Railroad Scheduling Graphical User Interface," Computation, vol. 11, no. 1, pp. 1-13, 2023, doi: 10.3390/computation11010011.

J. Uyttendaele, "Timetable compression using max-plus automata applied to large railway networks," TOP, vol. 31, no. 2, pp. 414-439, 2023, doi: 10.1007/s11750-022-00641-5.

K. Sagawa, "A Railway Timetable Scheduling Model based on a Max-Plus-Linear System," 2020 59th Annual Conference of the Society of Instrument and Control Engineers of Japan, SICE 2020, pp. 1575-1580, 2020.

M. Hoekstra, "Control of Delay Propagation in Railway Networks Using Max-Plus Algebra," Delft University of Technology, Delft, 2020. Accessed: Feb. 02, 2024. [Online]. Available: http://resolver.tudelft.nl/uuid:b5816386-0ed9-4760-a6de-f0db0c3a5226

W. Winarni, "Penjadwalan Jalur Bus dalam Kota dengan Model Petrinet dan Aljabar Max-Plus (Studi Kasus Busway TransJakarta)," CAUCHY: Jurnal Matematika Murni dan Aplikasi, vol. 1, no. 4, pp. 192-206, 2011, doi: 10.18860/ca.v1i4.1796.

A. Nait-Sidi-Moh, M. A. Manier, and A. El Moudni, "Spectral analysis for performance evaluation in a bus network," Eur J Oper Res, vol. 193, no. 1, pp. 289-302, Feb. 2009, doi: 10.1016/j.ejor.2007.08.047.

H. Newcomb, Modeling Bus Bunching with Petri Nets and Max-Plus Algebra. Portland State University Library, 2014. doi: 10.15760/honors.66.

X. Qiu, L. Tao, P. Li, and J. Yang, "Synchronization Optimization Model of BRT System Based on Max-Plus Algebra Petri Net," ICTE 2013, pp. 911-917, 2013, doi: 10.1061/9780784413159.134.

C. Wang and Y. Tao, "Locally and globally optimal solutions of global optimisation for max-plus linear systems," IET Control Theory & Applications, vol. 16, no. 2, pp. 219-228, 2021, doi: 10.1049/cth2.12219.

D. Merdekawati, "Closed Shop Scheduling Optimisation using Max-Plus Automata," J Phys Conf Ser, vol. 1341, no. 4, 2019, doi: 10.1088/1742-6596/1341/4/042015.

A. Edthofer, "Train schedule analysis and optimization with the max-plus automaton," 32nd European Modeling and Simulation Symposium, EMSS 2020, pp. 161-164, 2020, doi: 10.46354/i3m.2020.emss.022.

J. Xu, T. van den Boom, and B. De Schutter, "Optimistic optimization for model predictive control of max-plus linear systems," Automatica, vol. 74, pp. 16-22, 2016, doi: 10.1016/j.automatica.2016.07.002.

J. Xu, B. De Schutter, and T. J. J. van den Boom, "Model predictive control for max-plus-linear systems via optimistic optimization," IFAC Proceedings Volumes, vol. 47, no. 2, pp. 111-116, 2014, doi: 10.3182/20140514-3-fr-4046.00063.

P. M. Dower, "An Adaptive Max-Plus Eigenvector Method for Continuous Time Optimal Control Problems," Springer INdAM Series, pp. 211-240, 2018, doi: 10.1007/978-3-030-01959-4_10.

H. Zhang, Y. Tao, and Z. Zhang, "Strong solvability of interval max-plus systems and applications to optimal control," Systems & Control Letters, vol. 96, pp. 88-94, 2016, doi: 10.1016/j.sysconle.2016.07.005.

M. Akian, "An Adaptive Multi-Level Max-Plus Method for Deterministic Optimal Control Problems," IFAC-PapersOnLine, vol. 56, no. 2, pp. 7448-7455, 2023, doi: 10.1016/j.ifacol.2023.10.628.

C. Wang, Y. Tao, and H. Yan, "Optimal input design for uncertain max-plus linear systems," International Journal of Robust and Nonlinear Control, vol. 28, no. 16, pp. 4816-4830, 2018, doi: 10.1002/rnc.4285.

B. G. Fitzpatrick, K. Holmbeck-Cannell, M. Laffin, and Y. Wang, "Optimal perimeter patrol via max-plus probability," 2014 American Control Conference, pp. 5248-5253, 2014, doi: 10.1109/acc.2014.6859306.

B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work. Princeton: Princeton University Press, 2006. [Online]. Available: http://about.jstor.org/terms

Subiono, "Aljabar Min-Max Plus dan Terapannya," 2015.

D. Systemes, "Scilab," 2015, Scilab Enterprises, France: 5.5.2. Accessed: Jan. 20, 2025. [Online]. Available: https://www.scilab.org/news/scilab-552-release

S. Subiono, D. Adzkiya, and K. Fahim, "Toolbox Aljabar Max-Plus dan PetriNet," 2016, Departemen Matematika, Institut Teknologi Sepuluh Nopember, Surabaya: MAXPLUSV04032016. Accessed: Oct. 23, 2024. [Online]. Available: http://koncomatematika.blogspot.com/2016/05/cara-menginstall-toolbox-max-plus-scilab.html




DOI: http://dx.doi.org/10.30829/zero.v9i2.25392

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Publisher :
Department of Mathematics
Faculty of Science and Technology
Universitas Islam Negeri Sumatera Utara Medan
✉Email: zero_journal@uinsu.ac.id
☎WhatsApp: 085270009767 (Admin Official)
SINTA 2 Google Scholar CrossRef Garuda DOAJ