Modeling and analysis of the Metro-bus public transport system in Mexico city using timed event Petri nets and max-plus algebra

Research output: Contribution to conferencePaper

Abstract

In this paper an algorithm for computing a generalized eigenmode of reducible regular matrices over the max-plus algebra is applied to the Metro-bus public transport system in Mexico city. A timed event Petri net model is constructed from the data table that characterizes the transport system. A max-plus recurrence equation, with a reducible and regular matrix, is associated to the transport system timed event Petri net. Next, given the reducible and regular matrix of finite size i.e., a matrix such that in each one of its rows has at least one finite element and whose communication graph is not strongly connected, the problem consists in giving an algorithm which will tell us how to compute its generalized eigenmode over the max plus algebra, which indeed has an idempotent semiring, or also called dioid, mathematical structure. The notion of generalized eigenmode, as its name says, results to be a genaralization of the notion of eigenvalues and eigenvectors for the case when the matrix under study is irreducible i.e., has a communication graph which is strongly connected. The solution to the problem is achieved by studying some type of recurrence equations. In fact, by transforming the reducible regular matrix into a block upper triangular form, called normal form, and considering a very specific recurrence equation, an explicit mathematical characterization is obtained, upon which the algorithm is constructed. The generalized eigenmode obtained sets a timetable for the transport system. Another alternative algorithm for computing a generalized eigenmode of a reducible and regular matrix, is Howard's algorithm which is based on a policy iteration improvement procedure which in numerical examples has proven to be very efficient. The paper is organized as follows. In section 2, the concept of max-plus algebra is defined, its algebraic structure is also described. Matrices and graphs are presented, the spectral theory of matrices is discussed, finally the problem of solving linear equations is addressed. Section 3, starts by introducing the concept of generalized eigenmode. Once this has been done, it continues by discussing, how to compute the generalized eigenmode for recurrence equations for the cases of irreducible and reducible matrices, Mth order recurrence equations are also treated. In section 4, the algorithm is formally presented. In section 5, max-plus recurrence equations for timed event Petri nets are introduced. Section 6, presents the metro-bus public transport system. Finally, in section 7, some conclusions are given.
Original languageAmerican English
Pages1685-1691
Number of pages1515
StatePublished - 1 Dec 2009
Event18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation: Interfacing Modelling and Simulation with Mathematical and Computational Sciences, Proceedings -
Duration: 1 Dec 2009 → …

Conference

Conference18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation: Interfacing Modelling and Simulation with Mathematical and Computational Sciences, Proceedings
Period1/12/09 → …

Fingerprint

Dive into the research topics of 'Modeling and analysis of the Metro-bus public transport system in Mexico city using timed event Petri nets and max-plus algebra'. Together they form a unique fingerprint.

Cite this