Publication e-STA e-STA 2004-4




144.16 Ko


Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi=""
        <identifier identifierType="DOI">10.23723/545:2004-4/20034</identifier><creators><creator><creatorName>Jean-Louis Boimond</creatorName></creator><creator><creatorName>Sébastien Lahaye</creatorName></creator><creator><creatorName>L. Houssin</creatorName></creator></creators><titles>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Thu 21 Mar 2019</date>
	    <alternateIdentifier alternateIdentifierType="bitstream">1a6434152dd6c50a5d8971b91d82d1b178273e24</alternateIdentifier>
            <description descriptionType="Abstract"></description>

MODÉLISATION ET COMMANDE DE RÉSEAUX DE BUS URBAINS DANS L’ALGÈBRE DES DIOIDES MODELLING AND CONTROL OF URBAN BUS NETWORKS IN DIOIDS ALGEBRA L. Houssin ∗ S. Lahaye ∗ J.L. Boimond ∗ ∗ Laboratoire d’Ingénierie des Systèmes Automatisés, 62, avenue Notre Dame du Lac, 49000 Angers, France Résumé: On applique les outils algébriques des dioides à l’étude réseaux de bus urbains. En particulier, on montre que cette théorie peut être utilisé pour le calcul de tables d’horaires Abstract: We aim at applying dioids algebraic tools to the study of urban bus networks. In particular, we show how they can be used for timetables synthesis. Mots clés: Systèmes à événements discrets, dioides, réseaux de bus, synthèse de tables d’horaires Keywords: Discrete Event System, dioids, bus networks, timetables synthesis 1. INTRODUCTION Discrete Event Dynamic Systems (DEDS) subject to synchronization phenomena can be modeled by linear equations in a particular algebraic struc- ture called dioid or idempotent semi-ring. For about twenty years, this property has motivated the elaboration of a ”new” linear system the- ory. Indeed, concepts such as state representation, transfer matrix, optimal control, correctors syn- thesis and identification theory have been trans- posed from conventional linear system theory to the considered algebraic structure (Baccelli et al., 1992). Applications of this theory have essen- tially concerned manufacturing systems (Menguy et al., 2000; Lahaye et al., 2003a), communica- tion networks (Le Boudec and Thiran, 2001) and transportation networks (Braker, 1993; de Vries et al., 1998). In the latter, the focus has been on modelling, performance evaluation and stability analysis of railway networks. For our concern, we are interested in applying dioids algebraic tools to the study of urban bus networks. The piloting of these networks can be seen as a two steps process. Firstly, a so-called operating schedule is defined for ”mean condi- tions”. In particular, timetables are defined at each stop to specify times at which buses should theoretically run. These timetables are used to inform passengers and, at particular stops, to re-synchronize buses. The second step consists in regulation operations: in reaction to current conditions (breakdown of a bus, modifications of traffic flows, etc.), a supervisor 1 may decide of adjustments from the operating schedule (transfer passengers, stop or reroute buses, etc.). In (Lahaye et al., 2003b), we have proposed a first approach aiming at modelling some of these regulation operations. In practice, such a model may be used as a tool to aid decisions since it allows evaluating relevance of adjustments. In this paper, the focus is rather on the first stage described above. In fact, we propose a model for urban bus networks functioning according to their operating schedule. We then show how dioid tech- niques 2 can be used for the synthesis of timeta- bles. As described in (Ceder et al., 2000) this problem is crucial, and aims notably at maximiz- ing connections between buses from different lines. The outline of the paper is as follows. In §2, we recall elements of dioid theory as well as principles of DEDS description and control over dioids. In §3, we describe how bus networks operate, and a model is introduced. In §4, the method for timetables synthesis is proposed. An application to an elementary bus network is proposed in §5. 2. PRELIMINARIES 2.1 Elements of dioid theory Definition 1. (Dioid). A dioid is a set D with two inner operations denoted ⊕ and ⊗. The sum is as- sociative, commutative, idempotent (∀a ∈ D, a ⊕ a = a) and admits a neutral element denoted ε. The product is associative, distributes over the sum and admits a neutral element denoted e. The element ε is absorbing for the product. In a dioid D, the equivalence : a  b ⇔ a = a ⊕ b defines a partial order relation. Definition 2. (Complete dioid). A dioid is said to be complete if it is closed for infinite sums and if product distributes over infinite sums too. The sum of all its elements is generally denoted . A complete dioid has a structure of complete lattice (Baccelli et al., 1992, §4) , i.e. two elements in a complete dioid always have a least upper bound namely a ⊕ b and a greatest lower bound denoted a ∧ b =  {x|xa, xb} x. Example 1. The set Z = Z∪{+∞, −∞} endowed with the max operator as sum and the classical sum as product is a complete dioid, denoted Zmax 1 Visualizing evolutions inside the network and communi- cating with bus drivers. 2 The proposed approach is mainly based on residuation theory. and usually called (max, +) algebra, with ε = −∞ and e = 0. Theorem 1. The implicit equation x = ax ⊕ b defined over a complete dioid admits x = a∗ b as least solution with a∗ = +∞ i=0 ai and a0 = e. The star operator ∗ is usually called Kleene star. 2.2 Residuation theory A mapping f defined from a complete dioid D into a complete dioid C is said to be isotone if a, b ∈ D, a b ⇒ f(a) f(b). Residua- tion theory (Blyth and Janowitz, 1972) defines ”pseudo-inverses” for some isotone mappings de- fined over ordered sets such as dioids (Cohen, 1998). More precisely, if the greatest element of set {x ∈ D|f(x) b} exists for all b ∈ C, then it is denoted f (b) and f is called residual of f. The isotone mapping La : x → a ⊗ x defined in a complete dioid is residuated. The greatest solution to a ⊗ x b exists and is equal to L a(b), also denoted b a or a ◦ \b. We furthermore have the following formulæ (see (Baccelli et al., 1992, §4.4)). x ab = a ◦ \x b (1) x a∗ x (2) a∗ ◦ \x a∗ = x a∗ (3) Theorem 2. (Baccelli et al., 1992, Th. 4.56) Let f : D → C and g : C → B. If f and g are residuated then g ◦ f is residuated and (g ◦ f) = f ◦ g . Definition 3. (Mapping restriction). Let f : D → C a mapping and A ⊆ D. We denote f|A : A → C the mapping defined by equality f|A = f ◦ Id|A where Id|A : A → D is the canonical injection. A constrained residuation problem (Cohen, 1998) consists in finding the greatest solution to f(x) b not in the whole D but only in a subset A of D. More precisely, being given a residuated mapping f we aim at solving: f|A(x) = f ◦ Id|A(x) b. (4) Proposition 1. If the canonical injection Id|A is residuated, then the constrained residuation prob- lem (4) admits an optimal solution denoted f |A(b). Proof : Thanks to theorem 2, if Id|A is residuated, then so is f ◦ Id|A, and the greatest solution to (4) is given by f |A(b) = (f ◦ Id|A) (b) = Id |A ◦ f (b) (5) 2 2.3 Representation of DEDS using dioids Dioids algebra enables to model DEDS involving (only) synchronization phenomena. For instance, by dating each event, i.e. by associating with each event a discrete function x (resp. u and y for an input and an output) called dater 3 , it is possible to get a linear state representation:  x(k) = Ax(k − 1) ⊕ Bu(k) y(k) = Cx(k). (6) An analogous transform to Z-transform (used to represent discrete-time trajectories in classi- cal theory) can be introduced for daters. The γ- transform of a dater x(k) is defined as the fol- lowing formal power series: x =  k∈Z x(k)γk . Indeed, variable γ can be interpreted as the back- ward shift operator in event domain. The set of formal power series in one variable γ and coeffi- cients in Zmax is a dioid denoted Zmaxγ. State representation (6) becomes in Zmaxγ:  x = γAx ⊕ Bu y = Cx. (7) Considering the earliest functioning of the system, we select the least solution of the first equation of (7) which is given according to theorem 1 by x = (γA)∗ Bu. This leads to y