
In this paper, the problem of existence-uniqueness and global exponential stability of periodic solution (i.e., stationary oscillation) for a class of nonlinear delay systems with impulses was studied. Some new sufficient conditions ensuring the existence of stationary oscillation for the addressed equations were derived by using the inequality technique that has been reported in recent publications. Our proposed method, which is different with the existing results in the literature, shows that nonlinear delay systems may admit a stationary oscillation using proper impulsive control strategies even if it was originally unstable or divergent. As an application, we considered the single species logarithmic population model and established a new criterion to guarantee the existence of positive stationary oscillation. Some numerical examples and their computer simulations were also given at the end of this paper to show the effectiveness of our development control method.
Citation: Shipeng Li. Impulsive control for stationary oscillation of nonlinear delay systems and applications[J]. Mathematical Modelling and Control, 2023, 3(4): 267-277. doi: 10.3934/mmc.2023023
[1] | Raúl M. Falcón, Víctor Álvarez, José Andrés Armario, María Dolores Frau, Félix Gudiel, María Belén Güemes . A computational approach to analyze the Hadamard quasigroup product. Electronic Research Archive, 2023, 31(6): 3245-3263. doi: 10.3934/era.2023164 |
[2] | Doston Jumaniyozov, Ivan Kaygorodov, Abror Khudoyberdiyev . The algebraic classification of nilpotent commutative algebras. Electronic Research Archive, 2021, 29(6): 3909-3993. doi: 10.3934/era.2021068 |
[3] | Jiuda Huang, Chao Han, Wuju Wei, Chengjun Zhao . Analysis of long-term maintenance decision for asphalt pavement based on analytic hierarchy process and network level optimization decision. Electronic Research Archive, 2023, 31(9): 5894-5916. doi: 10.3934/era.2023299 |
[4] | Enrique Ferres-López, Eugenio Roanes-Lozano, Angélica Martínez-Zarzuelo, Fernando Sánchez . One-sided differentiability: a challenge for computer algebra systems. Electronic Research Archive, 2023, 31(3): 1737-1768. doi: 10.3934/era.2023090 |
[5] | Qiuning Du, Fang Li . Some elementary properties of Laurent phenomenon algebras. Electronic Research Archive, 2022, 30(8): 3019-3041. doi: 10.3934/era.2022153 |
[6] |
Kengo Matsumoto .
|
[7] | Quanguo Chen, Yong Deng . Hopf algebra structures on generalized quaternion algebras. Electronic Research Archive, 2024, 32(5): 3334-3362. doi: 10.3934/era.2024154 |
[8] | Ping Zhou, Hossein Jafari, Roghayeh M. Ganji, Sonali M. Narsale . Numerical study for a class of time fractional diffusion equations using operational matrices based on Hosoya polynomial. Electronic Research Archive, 2023, 31(8): 4530-4548. doi: 10.3934/era.2023231 |
[9] | Wenbin Zheng, Jinjin Li, Shujiao Liao . Decision self-information based on parameterized fuzzy β neighborhood and its application in three-way multi-attribute group decision-making. Electronic Research Archive, 2022, 30(12): 4553-4573. doi: 10.3934/era.2022231 |
[10] | Juping Yang, Junguo Wang, Yongxiang Zhao . Simulation of nonlinear characteristics of vertical vibration of railway freight wagon varying with train speed. Electronic Research Archive, 2022, 30(12): 4382-4400. doi: 10.3934/era.2022222 |
In this paper, the problem of existence-uniqueness and global exponential stability of periodic solution (i.e., stationary oscillation) for a class of nonlinear delay systems with impulses was studied. Some new sufficient conditions ensuring the existence of stationary oscillation for the addressed equations were derived by using the inequality technique that has been reported in recent publications. Our proposed method, which is different with the existing results in the literature, shows that nonlinear delay systems may admit a stationary oscillation using proper impulsive control strategies even if it was originally unstable or divergent. As an application, we considered the single species logarithmic population model and established a new criterion to guarantee the existence of positive stationary oscillation. Some numerical examples and their computer simulations were also given at the end of this paper to show the effectiveness of our development control method.
Rail transportation is an important mode of transportation around the world. It is a reliable and efficient way to transport goods and people over long distances. According to a literature review on resilience in railway transport systems, rail transportation is a critical infrastructure that plays a vital role in the economy and society[1,2].
Railway interlocking is a safety-critical system that ensures trains do not collide on the tracks. It is a complex problem that has been studied extensively in the literature. One source that provides an overview of railway signalling principles is Pachl [3]. Recent research has explored the use of artificial intelligence to detect faults in railway signal interlocking systems [4]. Other researchers have compared different methods for verifying the safety of railway interlockings [5]. There has also been work on developing formal model-based methodologies to support railway engineers in specifying and verifying interlocking systems [6]. Overall, the railway interlocking problem is an important and active area of research with many different approaches being explored.
Ensuring the compatibility of switch positions and signal indications at a railway station is crucial for safety. Interlocking is a safety measure that prevents improper changes to traffic signals and turnout switches. A railway station consists of sections connected by traffic signals and turnouts, which define the possible movement of trains. A route is a sequence of connected sections that a train can travel along partitioned into several blocks. To prevent collisions and dangerous situations, two trains may never be in the same block of a route. Two intersection routes (or the relevant blocks thereof) must be allocated to trains at the same time, to prevent collisions. Once a route is set and a train receives the signal to proceed, all switches and signals along the route are locked until the train has passed through.
A possible classification of computer-based railway interlocking systems could be as follows:
● Route-table based: For every route request, an algorithm checks its feasibility using a "control table". The software consists of a single algorithm, independent of the topology.
● Geographical: The interlocking program is made up of instances of software objects that mimic the behavior of physical objects. The configuration of this program depends on the topology. Within this category, we can distinguish between:
– Route-based: Routes are defined a priori, and their definitions constitute data shared by the instantiated objects.
– On-demand route definition: There is no a priori definition of routes. Instead, a train's request to the interlocking system is given only as the final destination that the train must reach. Instantiated software objects are responsible for exploring possible routes to the destination and choosing one of them. Our approach lies in this category.
Classical railway interlocking systems are route-based and the compatibility of routes is decided (usually by human experts) in advance [7] (although unacceptable errors have been found in real railway interlocking systems [8]).
Some modern railway interlocking systems can make decisions on the fly. This makes them more flexible as routes are not predetermined. However, before authorizing any changes to signals or switch positions, it is necessary to check if two trains would travel on intersecting routes (including the same route) and potentially collide. If this is the case, changes are not made and it may be necessary to wait for a train to leave the station.
The first railway interlocking systems were developed in the nineteenth century (they were complex mechanical devices with levers and interacting bars). Typical railway interlocking systems of the mid twentieth century were based on the use of electric relays and needed complicated electric circuits translating the connectivity of the railway station. In the 1980's, the first computer-controlled railway interlocking systems are installed [9,10,11,12]. The first geographical railway interlocking system installed in Spain is dated on 1993 [13].
All modern railway interlocking systems are computer based (either geographical or route-based). Naive implementations of geographical algorithms may run into exponential complexity problems concerning the running time needed for finding safe routes through the railway network. Efficient data validation for geographical interlocking systems has also been studied [14]. Another approach to verifying geographically distributed interlocking systems is through model checking using UMC [15]. The approach presented here describes the configuration of the railway station through a single algebraic structure in which safety can be checked by a single algebraic operation. The main goal of our work is mainly theoretical. Nevertheless, it has the limitation that it cannot be certified and applied in practice. However we think that our approach can also be used for simulations that do not require certification credit and it is interesting from a theoretical point of view. Indeed, our approach represents a step on our research on proposing algorithms to solve railway interlocking problems for any railway station using an algebraic model similar to those used in Artificial Intelligence for implementing expert systems based on polynomials, ideals, and Groebner basis [16]. Our proposal offers significant advantages over previous approaches. The motivation for our work is as follows:
● Our approach relates two seemingly different fields: computational algebra and interlocking problems. Indeed the model we propose here proves that an interlocking problem can be solved by applying a division algorithm. This relation is not only interesting and inspiring from a theoretical point of view, but also has certain practical benefits: a possible proposal for improvement in the division algorithm in the field of computational algebra directly results in faster performance in solving interlocking problems.
● By expressing the interlocking problem as an algebraic system similar to those used in expert systems, we can address problems related to expert systems in railway stations. We believe that once the problem is described in algebraic terms, it will be possible to develop expert systems based on these algebraic systems to solve more complex problems in the future. For example, such systems could detect which signals and switches cannot change the state due to safety concerns and provide recommendations for changing the configuration of switches and signals to allow trains to move safely to specific locations.
● Unlike our previously proposed models that used algebraic systems [17,18,19], the model we propose now has great advantages over the others:
– It eliminates the need for calculating Groebner bases, a task that is known to be very slow due to its exponential complexity. Indeed, in contrast to our previous approaches, the present model guarantees a linear complexity.
– As a result, our new model is much faster than our previous models and has been shown to have linear complexity.
– In contrast to our previous approaches, we use different polynomials to represent the static and dynamic topology of the railway station. The static topology is represented by a set of polynomials while the dynamic topology is represented by a monomial. Another monomial is used to represent the position of trains. This allows for immediate updates to the polynomials representing the problem when there are changes in train positions or the configuration of the railway station.
The paper is structured as follows. In Section 2 we discuss other approaches related to the one proposed here. In Section 3 we propose a possible formalisation of the concepts related to a railway interlocking system. In Section 4 we describe our method (as a black box) for determining the safety of a proposed situation in a railway interlocking system. In Section 5 the worst case complexity of the new model in calculated. In Section 6 the extension of the model to trains occupying more than one section of the layout is detailed. In Section 7 we show that the new model is much faster than previous ones. Finally, in Section 8 we set our conclusions.
An overview of different existing approaches to decision making in a railway interlocking system is given afterwards.
The paths (lists of consecutive sections) along the railway station are called routes. An example can be a route from an entrance of a station to a given track beside a certain platform. Establishing a route requires setting the turnouts and colour light signals along the route appropriately.
Many approaches have been applied to decision making in a railway interlocking system. Although out of date, [20] includes an interesting annotated bibliography.
In the classic approaches, the routes of the railway interlocking system are predefined. Moreover, the compatibility of routes is determined in advance (traditionally by human experts). They are usually denoted tabular railway interlocking systems.
The railway interlocking system is usually denoted geographical if the problem is translated into computational notation and decisions are made on the fly.
Geographical approaches do not depend on the track layout of the railway station. An inference engine extracts knowledge in a rule-based expert system and is independent of the given rules and facts stated as true. Similarly, a geographical railway interlocking system can decide upon the safety of any proposed situation in any given railway station.
The [21] uses a theorem prover implemented in a higher-order logic to decide on the safety of a situation. This work is revisited using an annotated logic program with temporal reasoning in [22].
Meanwhile, [7] uses ordered binary decision diagrams to model railway interlocking systems.
A specific work for the Slovak National Railways is [23], that uses Z notation.
Another specific work, in this case for the Danish State Railways is [24], that uses the Vienna Development Method (VDM).
The [25] presents an early but sophisticated formal model that can deal with complex topologies including reversing loops and reversing triangles. It uses Petri nets and graphs and is implemented in Objective-C and PROLOG.
Another model (component-based) is used in the interesting approach [26,27,28]. The railway station is abstracted as a set of connected components.
Another example is [29], where CAD, RailML, and logic programming are used. It is applied to a Norwegian railways station.
A very interesting approach that also uses RailML to describe the topology of the railway station and UML class diagrams and is applied to a Dutch station is [30].
We will describe afterwards some models for decision making in railway interlocking systems designed and implemented by the authors. All these models are topologically-independent and do not have restrictions on the direction of the trains.
● Model based on the use of graphs [31]: Our approach is based on graph theory and Boolean matrices (adjacency matrices). This approach is slow and can only be applied to small railways stations because, although the matrices are sparse, their number of rows and columns is the number of sections of the network.
● Algebraic model [17,32]: Here, our approach is based on algebraic terms which requires calculating a Groebner basis [33,34] of a polynomial ideal. Since the algorithm for calculating this Groebner basis involves a long time, this approach is not suitable for large stations.
● Model based on Boolean propositional logic [35]: This approach is based on propositional logic: sections are represented by Boolean propositional variables and connectivity between sections are represented by a Boolean propositional formula. The safety of a railway station is detected by solving a SAT problem for each section in the railway station. All techniques, like DPLL [36], to solve a SAT problem involve exponential complexity. However, the high number of SAT problems required in this approach makes it impossible for large stations.
● Logic-algebraic model [18]: The advantage with respect to the algebraic model mentioned above is that in this case, the polynomial ring where computations take place is Boolean and consequently, Groebner bases and normal forms calculations required are much faster. In fact, this model is much faster than the three previous ones. However, the algorithm for calculating a Groebner basis involves high complexity computations and therefore, this approach is not suitable for large stations.
● ASP model [37]: This approach is based on the answer set programming (ASP) paradigm. Connectivity and safety relations are defined by relations and derived relations through logic programming. This approach is further more efficient than previous ones and may be suitable for larger railway stations. However, this is not a polynomial complexity approach and consequently, it is not scalable.
● Model based on preprocess and Boolean Polynomials: An algebraic approach that represents the proposed configuration of the railway station and the position of the trains using Boolean polynomials and Groebner bases is detailed in [19]. The set of polynomials for which the Groebner basis is computed does not depend on the position of the trains. A new Groebner basis has to be computed if any changes in the aspect of the colour light signals or the position switches take place. Although faster than previous approaches, it can still be slow if the railway station is really large.
As may be seen, many of these approaches are based on translating the topology of the railway station into polynomials with several variables and require calculating Groebner bases since they are usually required to solve many algebraic problems involving polynomials with several variables. Unfortunately, calculating a Groebner basis requires a very long time, and consequently, all these approaches are not suitable for very large railway stations with many trains since they need a long time to make a decision upon the safety of the proposed situation.
In this paper, we propose a completely new algebraic approach that does not require computing Groebner bases and is much faster than our previous ones. In our approach, the computational complexity of deciding upon the safety of a proposed situation is linear with respect to the number of sections and trains in the railway station (see Section 5). Therefore, it is completely suitable for very large railway stations (even if there are many trains involved).
In this section we will define some formal concepts that allow us to prove the validity of our approach.
A railway station is a set of sections {S1…SN} and a binary relation defining the connection between sections by means of colour light signals and turnouts. There may be trains placed in the sections of a railway station. In this paper, we will initially consider that each train is placed in just one section. Nevertheless, we will generalize our results for the general case that a train can be placed in different sections in Section 6.
A colour light signal is defined as (Si,Sj), a pair of connected sections. If the indication of the colour light signal is proceed, then a train may pass from section Si to section Sj. If the indication of the colour light signal is stop, then trains are not allowed to pass from section Si to section Sj.
A turnout is defined as (Si,Sj,Sk), an array of three connected sections. If the switch of the turnout is in the direct track position, then a train may pass from section Si to section Sj (and conversely). If the switch of the turnout is in the diverted track position, then a train may pass from section Si to Sk (and conversely).
The potential connectivity of a railway station derives from the situation of the colour light signals and the situation of the turnouts (that is, from the so called topology of the station). We define the relation E for describing the potential connectivity between sections. Formally, E is a set of pair of sections (i,j) indicating that the section Si is connected to section Sj (by means of a colour light signal and/or a turnout).
Definition 3.1. We define the set E⊂Z×Z as:
E={(i,j)|SiisconnectedtoSjorSjisconnectedtoSibymeansofacolourlightsignaloraturnout} |
Consequently, the relation E is symmetric.
Remark 3.1. In the case that there are a series of n turnouts, we assume the presence of intermediate sections between them. Consequently, in a railway station, each section is connected to a maximum of three other sections on each extreme through a turnout. This means that each section can be connected to a maximum of six other sections. Therefore, the size of E is less than or equal to 6⋅N where N is the number of sections. As a result, the number of elements in E, is O(N).
The indications of the colour light signals and the position of the switches of the turnouts (that is, the configuration of the railway station) define if a section is reachable from another. A configuration of the railway station is defined by a subset P⊆E. (Si,Sj)∈P if and only if it is possible to pass from the section Si to the section Sj according to the indications of the colour light signals and the position of the switches of the turnouts (obviously a necessary condition is that section Si is connected to section Sj).
Remark 3.2. In this model of railway interlocking systems we assume that if the switch of the turnout (Si,Sj,Sk) is in the direct track position, a train is not allowed to pass from Sk to Si. Similarly, if the switch of the turnout (Si,Sj,Sk) is in the diverted track position, a train should not try to pass from Sj to Si. We will consider that turnouts are always properly protected by colour light signals.
Remark 3.3. Two sections are connected by means of either a colour light signal or a turnout, but not both. If the latter was the case, we introduce a section in between (like S9 between S10 and (S2,S3,S9) in Figure 3.2). Similarly, we include sections between two semaphores or turnouts.
Remark 3.4. Note that, despite the fact that turnouts can be long apparatuses, they are not considered sections in this model, but connections between sections.
The set P determines the possible paths of the railway station. A path is a list of sections [u1…un] such that for every i (ui,ui+1)∈P. The set P fulfills the following important property: For every pair of sections i and j, there is at most one path in P from section i to section j.
Remark 3.5. For the property in the previous paragraph to hold we are considering paths defined by P (not by E). Besides, we are considering in this model only "usual" railway terminus stations or railway overtaking stations (unlike toy trains where one side of the overtaking station is connected to the other side). In these "usual" stations, we have that for every pair of sections i and j, there is at most one path in P from section i to section j.
Example 3.1. Let us consider the railway station of Figure 3.1.
As may be seen, the railway station is divided into sections S1…S11 and there are seven colour light signals (for example, there is a colour light signal between sections S1 and S2) and two turnouts (for example, a turnout connecting sections S2, S3 and S9). Note that signalling is on the right hand side of the track.
According to Definition 3.1, the set E is:
E={(1,2),(2,9),(9,10),(10,11),(11,6),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)(2,1),(9,2),(10,9),(11,10),(6,11),(3,2),(4,3),(5,4),(6,5),(7,6),(8,7)} |
Note that the set E is defined independently from the specific configuration of the elements of the railway station (from the indications of the colour light signals and the positions of the switches of the turnouts).
Let us consider the configuration depicted in Figure 3.2. The position of the switches of the turnouts is represented by:
● a small segment, if the switch is in the direct track position (see for instance the turnout between sections S2 and S3,S9 in Figure 3.2), or
● a small angle, if the switch is in the diverted track position (see for instance the turnout between sections S6 and S5,S11 in Figure 3.2).
In view that the figures are printed in black and white, the aspect of the colour light signals will be represented by a black circle (indication stop) or white circle (indication proceed).
Now, we will determine the subset P⊆E given by the indications of the colour light signals and the position of the switches of the turnouts in Figure 3.2:
P={(1,2),(9,10),(10,11),(2,3),(3,4),(11,6),(6,7),(7,8),(2,1),(11,10),(5,4),(3,2),(6,11),(8,7)} |
As may be seen, (10,9)∉P because the indication of the colour light signal connecting sections S10 and S9 is stop. In the same way, (2,9)∉P because the switch of the turnout (S2,S3,S9) is in direct track position.
We would like to emphasize here that remark 3.5 holds in Figure 3.2. Although it is apparent that there are sections connected by more than one path, there are no loops once P is defined. That is to say, for every sections i and j there is at most one path in P from i to j.
Let us formally define the set P.
Definition 3.2. We define the subset P⊆E as the set of (i,j)∈E such that exactly one of these conditions holds (with the conditions imposed in this model the conditions are mutually exclusive):
● It is always possible to pass from section Si to section Sj (regardless of the configuration of the railway station).
For example, (2,1)∈P in the configuration of Figure 3.2 since it is always possible to pass from section S2 to section S1.
● There is a colour light signal (Si,Sj) and its indication is proceed.
For example, (1,2)∈P in the configuration of Figure 3.2 since the indication of the colour light signal (S1,S2) (controlling the pass from section S1 to section S2) is proceed.
● There is a turnout (Si,Sj,Sk) or a turnout (Sj,Si,Sk) and its switch is in the direct track position.
For example, (2,3)∈P and (3,2)∈P in the configuration of Figure 3.2 since the switch of the turnout (S2,S3,S9) is in the direct track position.
● There is a turnout (Si,Sk,Sj) or a turnout (Sj,Sk,Si) and its switch is in the diverted track position.
For example, (6,11)∈P and (11,6)∈P in the configuration of Figure 3.2 since the switch of the turnout (S6,S5,S11) is in the diverted track position.
Definition 3.3. We define the multiset Q as the set of sections in which a train is placed: the number of times that element i appears in Q represents the number of trains located in section Si.
We will consider that Q is a multiset instead of a set, since Q will have repeated elements in case that two different trains are placed in the same section (which is dangerous).
Definition 3.4. Let us consider a railway station and let the relation E describe its potential connectivity (see Definition 3.1). A railway interlocking problem is an ordered pair (P,Q), where P is the set of Definition 3.2, describing a certain configuration of the elements of the railway station (indications of the colour light signals and positions of the switches of the turnouts) and Q is the multiset of Definition 3.3, describing the positions of the trains.
Definition 3.5. We will say that the railway interlocking problem (P,Q) is in a dangerous situation if and only if there are two lists of integers [u1,…un] and [v1,…vm] such that all the following conditions hold:
(1) For all 0<i<n, we have that (ui,ui+1)∈P. That is to say, consecutive sections in the list [u1,…un] must be connected.
(2) For all 0<j<m, we have that (vj,vj+1)∈P. That is to say, consecutive sections in the list [v1,…vm] must be connected.
(3) {u1,v1}⊆Q. That is to say, there must be a train in u1 and v1.
(4) un=vm. That is to say, both paths reach the same section (there is a possible collision).
(5) For all 1<i<n ui∉Q and for all 1<j<m vj∉Q. That is to say, intermediate sections in the list must be free of trains so that trains from from section u1 and section v1 may reach section un=vm.
(6) For all 1<i<n and for all 1<j<m we have ui≠vj. That is to say, the possible collision happens at the end of the paths.
(7) For all i≠j we have ui≠uj. That is to say, the path [u1,…un] does not contain cycles.
(8) For all i≠j we have vi≠vj. That is to say, the path [v1,…vm] does not contain cycles.
We will say that the railway interlocking problem (P,Q) is in a safe situation if and only if (P,Q) is not in a dangerous situation.
Example 3.2. Let us recall the railway station of Figure 3.1 and its possible configuration shown in Figure 3.2. Figure 3.3 depicts the placement of one train in section S1 and another train in section S10. Therefore, in this case: Q={1,10}
Clearly, this situation is safe:
● the train located in section S1 could stay in section S1 or move to sections S1,S2,S3,S4,
● the train located in section S10 could stay in section S10 or move to sections S11,S6,S7,S8.
Example 3.3. However, if a new train were allocated in section S8, that is to say Q={1,8,10} (Figure 3.4), the situation would turn into a dangerous one: the trains situated in sections S10 and S8 could collide in sections S7 and S8. Following the formalization of Definition 3.5:
● lists [10,11,6,7] and [8,7] fulfil the conditions Definition 3.5 (representing a possible collision in section S7),
● lists [10,11,6,7,8] and [8] fulfil the conditions Definition 3.5 (representing a possible collision in section S8).
Example 3.4. In case the aspect of the colour light signal between section S10 and section S11 were changed, now indicating stop, the situation would be safe again (Figure 3.5).
In this section we will extensively describe our algebraic approach based on the use of polynomials. As we will see, the potential connectivity of a railway station is represented by a set of polynomials with coefficients in the field Z2. A specific configuration of the railway station is represented by a polynomial with coefficients in the same field. The same happens with a specific placement of trains in the railway station. In order to detect whether a proposed situation is dangerous or not, we only need to check if the remainder of dividing a polynomial by a set of polynomials is zero or not.
Our approach is based on defining a set of polynomials in the variables ti,lij and mij, where:
● ti: a variable ti is considered for each section Si in the railway station.
● lij,mij: two variables, lij and mij, are considered for each pair of sections Si and Sj when (i,j)∈E. That is to say, we consider the variables lij and mij if the topology of the station allows to pass from section Si to section Sj (in some configuration of the railway station).
We will work hereinafter in the polynomial ring
A=Z2[lij,…,mij,…,ti,…] |
and we will use the lexicographical order given by lij>mij>ti. The set of polynomials representing the potential connectivity of the railway station, the polynomial describing the specific configuration of the railway station and the polynomial describing the specific placement of trains in the railway station are constructed as follows.
The list of polynomials E representing the railway station. Through the set E (see Definition 3.1, the set of ordered pairs of integer numbers describing the potential connectivity of a railway station, we will define E as the list of polynomials of A formed by:
● ∀(i,j)∈E, the two polynomials:
gij=lijljiti+mijmjititj |
g′ij=lijmjiti+mijmjititj |
● For each variable ti:
t2i |
As may be seen, the list of polynomials E depends only on E and, therefore, it is defined independently from the specific configuration of the elements of the railway station (from indications of the colour light signals and the position of the switches of the turnouts).
The polynomial p representing a given configuration of the railway station. For each set of ordered pairs of integers P⊆E representing a given configuration of the railway station (see Definition 3.2), we will consider the monomial p∈A:
p=∏(i,j)∈Plij∏(i,j)∈E−Pmij |
As may be seen, this monomial is defined according to the configuration of the railway station in the following way (note that the symbol | represents the relation is a divisor of or divides, for example, xz|xyz because xz divides xyz):
● If it is always possible to pass from section Si to section Sj (regardless of the configuration of the railway station), then lij|p.
● If there is a colour light signal between section Si and section Sj, then:
– if the indication of the colour light signal is proceed, then lij|p.
– if the indication of the colour light signal is stop, then mij|p.
● If there is a turnout connecting section Si to either section Sj or section Sk then:
– if the switch is in the straight track position, then lijljimikmki|p.
– if the switch is in the diverted track position, then liklkimijmji|p.
As may be seen, a variable lij in p represents that it is possible to pass from section Si to section Sj. In the same way, a variable mij in p represents that it is not possible to pass from section Si to section Sj
The polynomial q representing the placement of the trains. Let us consider that there are trains placed in sections Si1,…,Sim. We define the monomial q∈A:
q=m∏i∈Qti |
As may be seen, a variable ti in q represents that there is a train in section Si.
Here we will summarize the steps required to solve a railway interlocking problem.
Step 1. Given a railway station by the set describing its potential connectivity, E, we obtain the list E.
We would like to emphasize that this list E is calculated only once for every railway interlocking problem associated to E. We do not need to recalculate this set if there are movements of trains or if there are changes in the configuration of the railway station. Besides, this set only contains 2K+N polynomials (where K is the size of E and N is the number of sections).
Step 2. Given a configuration of the railway station, P, we calculate the monomial p.
As may be seen, for every change of the configuration in the railway station, we need to calculate p, but this monomial contains K variables where K is O(N).
Step 3. Given a placement of the trains, Q, we need to calculate the monomial q.
As may be seen, for every change of the placement of the trains, we need to calculate q, but this monomial contains at most N variables.
Step 4. In order to solve the (P,Q) railway interlocking problem we need to compute:
NR(p⋅q,E) |
where NR represents the remainder of the monomial pq respect to the list E. If this value is 0, the railway interlocking problem is in a dangerous situation, otherwise it is in a safe situation (see Theorem A.11). This may be calculated with any Computer Algebra System (CAS). In this paper we will use the CAS CoCoA 5.2 [38,39].
As we will see in Section 7, all these steps can be completed in less than 1 s for very large railway stations using a conventional computer.
We will use the CAS CoCoA in order to show how to solve some railway interlocking problems for the railway station of Example 3.1 (depicted in Figure 3.1) using the algebraic approach proposed in this paper.
Example 4.1. Let us recall the potential connectivity of the railway station of Example 3.1. Let us remember that in this case:
E={(1,2),(2,9),(9,10),(10,11),(11,6),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)(2,1),(9,2),(10,9),(11,10),(6,11),(3,2),(4,3),(5,4),(6,5),(7,6),(8,7)} |
The process starts as follows:
Step 1. We define the polynomial ring and the list E corresponding to the topology of this railway station as described in Section 4.1. The variables of the polynomial ring are:
● variables: t1…t11 (since this railway station contains 11 sections)
and
● variables: l1,2,l2,9,l9,10,l10,11,l11,6,l2,3,l3,4,l4,5,l5,6,l6,7,l7,8,
l2,1,l9,2,l10,9,l11,10,l6,11,l3,2,l4,3,l5,4,l6,5,l7,6,l8,7,
m1,2,m2,9,m9,10,m10,11,m11,6,m2,3,m3,4,m4,5,m5,6,m6,7,m7,8,
m2,1,m9,2,m10,9,m11,10,m6,11,m3,2,m4,3,m5,4,m6,5,m7,6,m8,7
In CoCoA syntax:
useZZ/(2)[l1_2,l2_9,l9_10,l10_11,l11_6,l2_3,l3_4,l4_5,l5_6,l6_7,l7_8,l2_1,l9_2,l10_9,l11_10,l6_11,l3_2,l4_3,l5_4,l6_5,l7_6,l8_7,m1_2,m2_9,m9_10,m10_11,m11_6,m2_3,m3_4,m4_5,m5_6,m6_7,m7_8,m2_1,m9_2,m10_9,m11_10,m6_11,m3_2,m4_3,m5_4,m6_5,m7_6,m8_7,t[1..11]],lex; |
The polynomials in the list E are defined as described in Section 4.2.
● l1,2l2,1t1+m1,2m2,1t1t2 (because (1,2)∈E),
● l1,2m2,1t1+m1,2m2,1t1t2 (because (1,2)∈E),
● …
In CoCoA syntax:
E:=[l1_2∗l2_1∗t[1]+m1_2∗m2_1∗t[1]∗t[2],l1_2∗m2_1∗t[1]+m1_2∗m2_1∗t[1]∗t[2],l2_9∗l9_2∗t[2]+m2_9∗m9_2∗t[2]∗t[9],l2_9∗m9_2∗t[2]+m2_9∗m9_2∗t[2]∗t[9],l9_10∗l10_9∗t[9]+m9_10∗m10_9∗t[9]∗t[10],l9_10∗m10_9∗t[9]+m9_10∗m10_9∗t[9]∗t[10],l10_11∗l11_10∗t[10]+m10_11∗m11_10∗t[10]∗t[11],l10_11∗m11_10∗t[10]+m10_11∗m11_10∗t[10]∗t[11],l11_6∗l6_11∗t[11]+m11_6∗m6_11∗t[11]∗t[6],l11_6∗m6_11∗t[11]+m11_6∗m6_11∗t[11]∗t[6],l2_3∗l3_2∗t[2]+m2_3∗m3_2∗t[2]∗t[3],l2_3∗m3_2∗t[2]+m2_3∗m3_2∗t[2]∗t[3],l3_4∗l4_3∗t[3]+m3_4∗m4_3∗t[3]∗t[4],l3_4∗m4_3∗t[3]+m3_4∗m4_3∗t[3]∗t[4],l4_5∗l5_4∗t[4]+m4_5∗m5_4∗t[4]∗t[5],l4_5∗m5_4∗t[4]+m4_5∗m5_4∗t[4]∗t[5],l5_6∗l6_5∗t[5]+m5_6∗m6_5∗t[5]∗t[6],l5_6∗m6_5∗t[5]+m5_6∗m6_5∗t[5]∗t[6],l6_7∗l7_6∗t[6]+m6_7∗m7_6∗t[6]∗t[7],l6_7∗m7_6∗t[6]+m6_7∗m7_6∗t[6]∗t[7],l7_8∗l8_7∗t[7]+m7_8∗m8_7∗t[7]∗t[8],l7_8∗m8_7∗t[7]+m7_8∗m8_7∗t[7]∗t[8],l2_1∗l1_2∗t[2]+m2_1∗m1_2∗t[2]∗t[1],l2_1∗m1_2∗t[2]+m2_1∗m1_2∗t[2]∗t[1],l9_2∗l2_9∗t[9]+m9_2∗m2_9∗t[9]∗t[2],l9_2∗m2_9∗t[9]+m9_2∗m2_9∗t[9]∗t[2],l10_9∗l9_10∗t[10]+m10_9∗m9_10∗t[10]∗t[9],l10_9∗m9_10∗t[10]+m10_9∗m9_10∗t[10]∗t[9],l11_10∗l10_11∗t[11]+m11_10∗m10_11∗t[11]∗t[10],l11_10∗m10_11∗t[11]+m11_10∗m10_11∗t[11]∗t[10],l6_11∗l11_6∗t[6]+m6_11∗m11_6∗t[6]∗t[11],l6_11∗m11_6∗t[6]+m6_11∗m11_6∗t[6]∗t[11],l3_2∗l2_3∗t[3]+m3_2∗m2_3∗t[3]∗t[2],l3_2∗m2_3∗t[3]+m3_2∗m2_3∗t[3]∗t[2],l4_3∗l3_4∗t[4]+m4_3∗m3_4∗t[4]∗t[3],l4_3∗m3_4∗t[4]+m4_3∗m3_4∗t[4]∗t[3],l5_4∗l4_5∗t[5]+m5_4∗m4_5∗t[5]∗t[4],l5_4∗m4_5∗t[5]+m5_4∗m4_5∗t[5]∗t[4],l6_5∗l5_6∗t[6]+m6_5∗m5_6∗t[6]∗t[5],l6_5∗m5_6∗t[6]+m6_5∗m5_6∗t[6]∗t[5],l7_6∗l6_7∗t[7]+m7_6∗m6_7∗t[7]∗t[6],l7_6∗m6_7∗t[7]+m7_6∗m6_7∗t[7]∗t[6],l8_7∗l7_8∗t[8]+m8_7∗m7_8∗t[8]∗t[7],l8_7∗m7_8∗t[8]+m8_7∗m7_8∗t[8]∗t[7],t[1]∧2,t[2]∧2,t[3]∧2,t[4]∧2,t[5]∧2,t[6]∧2,t[7]∧2,t[8]∧2,t[9]∧2,t[10]∧2,t[11]∧2]; |
Step 2. Let us now consider the configuration of Example 3.1 (Figure 3.2). In this configuration:
P={(1,2),(9,10),(10,11),(2,3),(3,4),(11,6),(6,7),(7,8),(2,1),(11,10),(5,4),(3,2),(6,11),(8,7)}E−P={(2,9),(4,5),(5,6),(9,2),(10,9),(4,3),(6,5),(7,6)} |
so we define the monomial p as follows:
p=l1,2m2,9l9,10l10,11l11,6l2,3l3,4m4,5m5,6l6,7l7,8l2,1m9,2m10,9l11,10l6,11l3,2m4,3l5,4m6,5m7,6l8,7 |
As may be seen, the variable m29 appears in the monomial p since it is not possible to pass from section S2 to section S9. Similarly, the variable l12 appears in p since it is possible to pass from section S1 to section S2.
In CoCoA syntax:
p:=l1_2∗m2_9∗l9_10∗l10_11∗l11_6∗l2_3∗l3_4∗m4_5∗m5_6∗l6_7∗l7_8∗l2_1∗m9_2∗m10_9∗l11_10∗l6_11∗l3_2∗m4_3∗l5_4∗m6_5∗m7_6∗l8_7; |
Example 4.2. Let us now consider the placement of trains of Example 3.2 (Figure 3.3): there are two trains located in sections 1 and 10, respectively.
Step 3. In this case: Q={1,10}. Therefore, we define the monomial
q=t1t10 |
In CoCoA syntax:
q:=t[1]∗t[10]; |
Step 4. In order to solve the railway interlocking problem (P,Q) we need to check whether NR(pq,E)=0 or not. In CoCoA syntax:
NR(p∗q,E)=0; |
As the output of CoCoA is "false", the proposed situation is safe.
Example 4.3. Let us now consider the placement of trains of Example 3.3 (Figure 3.4) instead: a new train is placed in section S8. We only need to perform Steps 3 and 4.
Step 3. We need to recalculate the polynomial q. Now: Q={1,10,8}, and, therefore, we define the monomial
q=t1t10t8 |
In CoCoA syntax:
q:=t[1]∗t[10]∗t[8]; |
Step 4. Again, we need to check whether NR(pq,E)=0 or not. In CoCoA syntax:
NR(p∗q,E)=0; |
The output of CoCoA is "true" in this case. Consequently, the proposed situation is dangerous.
Example 4.4. If the aspect of the colour light signal between section S10 and section S11 were changed, now indicating stop (see Figure 3.5 in Example 3.4), we would only need to recompute Steps 2 and 4.
Step 2. We need to recalculate the polynomial p. Now we have:
P={(1,2),(9,10),(2,3),(3,4),(11,6),(6,7),(7,8),(2,1),(11,10),(5,4),(3,2),(6,11),(8,7)}E−P={(2,9),(10,11),(4,5),(5,6),(9,2),(10,9),(4,3),(6,5),(7,6)} |
and therefore:
p=l1,2m2,9l9,10m10,11l11,6l2,3l3,4m4,5m5,6l6,7l7,8l2,1m9,2m10,9l11,10l6,11l3,2m4,3l5,4m6,5m7,6l8,7 |
(l10,11 has been substituted by m10,11). In CoCoA syntax:
p:=l1_2∗m2_9∗l9_10∗m10_11∗l11_6∗l2_3∗l3_4∗m4_5∗m5_6∗l6_7∗l7_8∗l2_1∗m9_2∗m10_9∗l11_10∗l6_11∗l3_2∗m4_3∗l5_4∗m6_5∗m7_6∗l8_7; |
Step 4. We need to check if the situation is dangerous. In CoCoA syntax:
NR(p∗q,E)=0; |
returns "false". Consequently, the proposed situation is safe.
In this section, we will provide the intuition behind the choice of polynomials and the reason why the division algorithm provides the solution for detecting whether an interlocking problem is in a dangerous situation or not.
As may be seen in the previous section, in order to detect if an interlocking problem (P,Q) is in a dangerous situation we need to check if NR(pq,E)=0. Although the definition NR is not simple and requires many technical details, we provide the intuition behind the value NR(pq,E): the remainder of the polynomial, pq by a list of polynomials E.
In the same way as ordinary division (for polynomials with one variable and natural numbers), the division of a polynomial p (with several variables) by a list of polynomials G=[f1…fm] is p=α1f1+…αmfm+r. The value NR(p,G) just denotes r, the remainder of the division.
The algorithm for calculating NR(p,G), in the same way as ordinary division, involves calculating intermediate dividends: it sets r0=pq and for each step i, it choose a polynomial f∈G and obtain a new intermediate dividend ri+1, fulfilling
ri=f⋅zi+1+ri+1 |
where zi+1 is another polynomial. The new intermediate dividend ri+1 is a polynomial 'simpler'* than ri. The last intermediate dividend rn is one such that it not possible to obtain a polynomial rn+1 simpler than rn. By definition, the value NR(pq,E) is the last intermediate dividend rn. That is to say, NR(p,G)=rn. In Definition A.6 in Appendix A we give more details of this operator.
* Obviously, in order to provide a formal definition, it is required to consider many mathematical issues: define when ri+1 is simpler than ri (this is done by means of leading terms of the polynomial); analyze if the output takes into account the election of f when several choices are possible. All these mathematical questions are deeply considered in [34]. We will briefly describe them in Section A.
In our approach, we calculate NR(pq,E) where pq represents the interlocking problem (P,Q). As we will see in Appendix A, each intermediate dividend ri is a polynomial with the form piqi such that ri represents an interlocking problem (Pi,Qi). This interlocking problem (Pi,Qi) is strongly related to (P,Q). Indeed, (Pi,Qi) is in a dangerous situation if and only if (P,Q) is in a dangerous situation. By means of this property, we can, consequently, detect if (P,Q) is in a dangerous situation by checking if (Pn,Qn) (the interlocking problem associated to rn=NR(pq,E)) is in a dangerous situation. Besides, we will prove in Appendix A another important property: the interlocking problem (Pn,Qn) is in a dangerous situation if and only if rn=0. By means of these two properties we conclude that (P,Q) is in a dangerous situation if and only if NR(pq,E)=0. We will prove all these previous results in Appendix A.
We will illustrate all these ideas by means of an example. We will consider the intermediate dividends of NR(pq,E) for the interlocking problem in Figure 3.4 and the interlocking problems associated to them in Figure 4.1.
● The interlocking problem A in Figure 4.1 is the same as the interlocking problem in Figure 3.4. The monomial pA and qA are the following:
– pA=l1,2m2,9l9,10l10,11l11,6l2,3l3,4m4,5m5,6l6,7l7,8l2,1m9,2m10,9l11,10l6,11l3,2m4,3l5,4m6,5m7,6l8,7
– qA=t1t10t8
● In the interlocking problem A in Figure 4.1 there is a train located in section s10 that can pass from s10 to s11. We can use the polynomial g10,11=l10,11l11,10t10+m10,11m11,10t10t11∈E in the algorithm of division and we have that:
pAqA=z1⋅g10,11+r1 |
where:
– z1=l1,2m2,9l9,10l11,6l2,3l3,4m4,5m5,6l6,7l7,8l2,1m9,2m10,9l6,11l3,2m4,3l5,4m6,5m7,6l8,7t1t8. The monomial zB is irrelevant for our purpose.
– r1=pBqB is the first intermediate dividend, where pB and qB are monomials describing the interlocking problem B in Figure 4.1:
* pB=l1,2m2,9l9,10m10,11l11,6l2,3l3,4m4,5m5,6l6,7l7,8l2,1m9,2m10,9m11,10l6,11l3,2m4,3l5,4m6,5m7,6l8,7
* qB=t1t10t8t11
The interlocking problems A and B are closely related: A is in a dangerous situation if and only if B is in dangerous situation.
● In the interlocking problem B in Figure 4.1 there is a train located in section s8 that can pass from s8 to s7. We can use the polynomial g8,7=l8,7l7,8t8+m8,7m7,8t8t7∈E in the algorithm of division and we have that:
pBqB=z2⋅g8,7+r2 |
where:
– z2=l1,2m2,9l9,10m10,11l11,6l2,3l3,4m4,5m5,6l6,7l2,1m9,2m10,9m11,10l6,11l3,2m4,3l5,4m6,5m7,6t1t10t11. The monomial zC is irrelevant for our purpose.
– r2=pCqC is the second intermediate dividend, where pC and qC are monomials describing the interlocking problem C in Figure 4.1:
* pC=l1,2m2,9l9,10m10,11l11,6l2,3l3,4m4,5m5,6l6,7m7,8l2,1m9,2m10,9m11,10l6,11l3,2m4,3l5,4m6,5m7,6m8,7
* qC=t1t10t8t11t7
In the same way, the interlocking problems B and C are closely related: B is in a dangerous situation if and only if C is in dangerous situation.
● In the interlocking problem C in Figure 4.1 there is a train located in section s11 that can pass from s11 to s6. We can use the polynomial g11,6=l11,6l6,11t11+m11,6m6,11t11t6∈E in the algorithm of division and we have that:
pCqC=z3⋅g11,6+r3 |
where:
– z3=l1,2m2,9l9,10m10,11l2,3l3,4m4,5m5,6l6,7m7,8l2,1m9,2m10,9m11,10l3,2m4,3l5,4m6,5m7,6m8,7t1t10t1t10t8t7. The monomial zD is irrelevant for our purpose.
– r3=pDqD is the third intermediate dividend, where pD and qD are monomials describing the interlocking problem D in Figure 4.1:
* pD=l1,2m2,9l9,10m10,11m11,6l2,3l3,4m4,5m5,6l6,7m7,8l2,1m9,2m10,9m11,10m6,11l3,2m4,3l5,4m6,5m7,6m8,7
* qD=t1t10t8t11t7t6
In the same way, the interlocking problems C and D are closely related: C is in a dangerous situation if and only if D is in dangerous situation.
● In the interlocking problem D in Figure 4.1 there is a train located in section s7 that can pass from s7 to s6. We can use the polynomial g′6,7=l6,7m7,6t6+m6,7m7,6t7t6∈E in the algorithm of division and we have that:
pDqD=z4⋅g′6,7+r4 |
where:
– z4=l1,2m2,9l9,10m10,11m11,6l2,3l3,4m4,5m5,6m7,8l2,1m9,2m10,9m11,10m6,11l3,2m4,3l5,4m6,5m8,7t1t10t8t11t7. The monomial zE is irrelevant for our purpose.
– r4=pEqE is the fourth intermediate dividend, where pE and qE are monomials describing the interlocking problem E in Figure 4.1:
* pE=l1,2m2,9l9,10m10,11m11,6l2,3l3,4m4,5m5,6m6,7m7,8l2,1m9,2m10,9m11,10m6,11l3,2m4,3l5,4m6,5m7,6m8,7
* qE=t1t10t8t11t7t26
● In the interlocking problem E in Figure 4.1 there are two trains located in section s6 (we will say that it as a trivial interlocking problem), and, therefore, the interlocking problem E is in a dangerous situation. Consequently, our original interlocking problem A is also in a dangerous situation. We can use the polynomial t26∈E in the algorithm of division and we have that:
pEqE=z5⋅t26+r5 |
where
– z5=l1,2m2,9l9,10m10,11m11,6l2,3l3,4m4,5m5,6m6,7m7,8l2,1m9,2m10,9m11,10m6,11l3,2m4,3l5,4m6,5m7,6m8,7t1t10t8t11t7. The monomial zE is irrelevant for our purpose.
– r5=0.
We have that r5 is the last intermediate dividend. Therefore, NR(pAqA,E)=r5=0.
In this section we will discuss that the complexity of every step of our approach is linear. We will consider that N is the number of sections in the railway station and K is the size of the set E (see Definition 3.1).
Step 1. Obtaining E. The number of variables of the polynomial ring is N+3K. Since K is O(N), we have that the number of variables is O(N). The number of polynomials in E′ is N+2K. Since K is O(N) (see Remark 3.1), we have that the number of polynomials is O(N). Each polynomials is the sum of two monomials at most. Consequently, the time complexity of this step is O(N).
Step 2. Calculating the polynomial p. Since the number of variables in the polynomial ring is O(N), we have that the time complexity of this step is O(N).
Step 3. Calculating the polynomial q. Since the number of variables in the polynomial ring is O(N), we have that the time complexity of this step is O(N).
Step 4. Checking NR(pq,E)=0. The complexity of generic algorithms for calculating the normal remainder of a polynomial pq with respect to a list of polynomials like E strongly depends on the structure used for representing the polynomials and the kind of polynomials in the list (E in our case). The polynomials in E are just sum of two monomials with a constant number of variables and pq is a monomial with a high number of variables. In Appendix B we describe an algorithm with complexity O(N) for calculating this task when pq and the polynomials in E fulfill these characteristics.
Till now, we have analysed the case where trains are placed just in one section. Here we will see that the railway interlocking problems for trains placed in more than one section can be reduced to railway interlocking problems for trains placed in one section.
Let us consider a railway interlocking problem (P,Q). Lets us suppose that a train is placed in sections {Sv1,…,Svm}, where (vi,vi+1)∈E, i∈{1…m−1}. Clearly, the proposed railway interlocking problem is equivalent to consider that the train is just in Sv1 and that it is possible to pass from section Svi to Svi+1 and from section Svi+1 to Svi for every i∈{1…m−1}. In other words, if there are colour light signals along the train occupying more than one section, it is considered that the indication of them all is proceed, whichever their real indications are. This can be achieved by considering the railway interlocking problem (P′,Q) where:
P′=P∪{(vi,vi+1)|(vi,vi+1)∉P,i∈{1…m−1}}∪∪{(vi+1,vi)|(vi+1,vi)∉P,i∈{1…m−1}} |
instead of (P,Q).
Consequently, we can reduce the general case to the specific one in which every train is placed in just one section.
Example 6.1. We will illustrate this in the example of the railway station with the specific configuration depicted in Figure 3.2 (Example 3.1, Section 3). There we have:
E={(1,2),(2,9),(9,10),(10,11),(11,6),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)(2,1),(9,2),(10,9),(11,10),(6,11),(3,2),(4,3),(5,4),(6,5),(7,6),(8,7)}P={(1,2),(9,10),(10,11),(2,3),(3,4),(11,6),(6,7),(7,8),(2,1),(11,10),(5,4),(3,2),(6,11),(8,7)} |
In Figure 6.1, we have a situation in which some trains are placed in more than one section: there is a train placed in sections [S1,S2] and there is a train placed in sections [S3,S4,S5].
The general railway interlocking problem of Figure 6.1 is equivalent to the railway interlocking problem (P′,Q′) depicted in Figure 6.2, in which all trains are placed in just one section, and where:
P′=P∪{(1,2),(2,1),(3,4),(4,3),(4,5),(5,4)}=={(1,2),(9,10),(10,11),(2,3),(3,4),(11,6),(6,7),(7,8),(2,1),(11,10),(5,4),(3,2),(6,11),(8,7),(4,3),(4,5)}Q′={1,3,8} |
In this section we analyse the performance of the approach presented in this paper, comparing it with other previous algebraic approaches. Indeed, we have made a comparison between the times required to decide upon the safety of a proposed situation in very large stations, with different numbers of sections (N) and trains (M). As may be seen, the new method proposed is always much more efficient than the other approaches proposed by the authors. This is possible because the present approach has worst case linear complexity (see Section 5).
In Table 1, we show the times required to decide upon the safety of different proposed situations (we have not included model in [31] because its performance is very poor bad for large stations). These times refer to the average performance of ten different configurations (both safe and unsafe) of a railway station with N sections and M trains involved.
N = 52 | N = 156 | N = 260 | N = 520 | N = 780 | N = 1040 | N = 1560 | |
M = 5 | M = 15 | M = 25 | M = 50 | M = 75 | M = 100 | M = 150 | |
Model described in [35] | 10.23 s | 250.250 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [17] | 15.356 s | 380.368 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [18] | 1.124 s | 38.292 s | 554.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [19] | 0.320 s | 0.920 s | 2.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [37] | 0.020 s | 0.047 s | 1.038 s | 16.458 s | >1 h | >1 h | >1 h |
Our approach in CoCoA | <0.001s | 0.015 s | 0.015 s | 0.078 s | 0.156 s | 0.250 s | 0.610 s |
Indeed, our new approach takes always less than 1 second to decide upon the safety of the proposed situation, even when the number of sections is huge, while the other approaches are much slower. In this case the first column corresponds to the track layout of a former Spanish railway station. The next columns correspond to concatenating that station with itself several times (we have observed that there are no significant changes in the performance of our approach if we add these stations in parallel by means of turnouts).
Time of our approach include the four steps in Section 4.2: it includes the calculation of the polynomials of the polynomials for the topology, configuration and trains.
Madrid-Chamartín-Clara Campoamor is the biggest railway station in Spain. Now it has 21 passing tracks of two gauges (15 of the Iberian gauge, traditionally used in Spain and Portugal, and 6 of the standard gauge, used in the Spanish high-speed lines) [40]. The railway station is under renovation and it will have in the next future 25 passing tracks (13 of Iberian gauge and 12 of standard gauge) [41]. We have considered in Table 2 the track layout of this railway station when all its tracks were of Iberian gauge (in order to consider a real world example as big as possible). This stations contains 250 sections, 81 semaphores, 100 turnouts.
M = 10 | M = 20 | M = 30 | M = 50 | M = 100 | |
Model described in [37] | 646 ms | 799 ms | 1045 ms | 1124 ms | 1522 ms |
Model described in [19] | 2340 ms | 2340 ms | 2340 ms | 2340 ms | 2340 ms |
Our approach | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms |
In this paper we have presented a new algebraic model for detecting dangerous situation in a railway station. According to this model, the position of trains in a railway station configuration is considered unsafe if and only if the remainder of a certain monomial (representing the configuration and the current position of the trains) divided by a list of polynomials vanishes. This connects two seemingly different fields: computer algebra and interlocking problems. Not only is this interesting from a theoretical perspective, but it also offers practical advantages. We have implemented this in CoCoA, resulting in very short program code. In this way, any improvement in the implementation of division algorithms immediately results in faster performance in our program. We have compared execution times with other fast models previously implemented by the authors and found that our approach eliminates the need to calculate a Groebner basis. Besides, our approach can be used as 'accelerated-time simulations', allowing for the analysis of different modifications in a railway network without the need to physically implement them with the enormous cost that it would require [42,43,44,45].
However, our approach has a significant limitation. While it is mathematically interesting, Computer Algebra Systems have not been certified for use in safety-critical implementations[46]. Obtaining ad hoc certification is much more costly than certifying a search engine over a table. As a result, our approach currently has no chance of being implemented in real-world systems. Nevertheless, we believe that our approach has value from a mathematical perspective and can be extended in several directions:
● Develop a library that allows for easy definition of the list E for any topology; that defines switch changes and semaphore colors through functions and train movements. Updates to the polynomials p and q through multiplication and division of variables.
● Develop a graphical environment that allows for the visual design of a station and obtains the polynomials in E, p, and q in a computer algebra system like CoCoA.
● Extend our model. Although usual stations do not contain cycles and for each pair of sections there is only one path, it would be interesting from a theoretical point of view to extend the model so that this restriction is not necessary.
● Study alternatives for general graphs, not just those derived from railway stations.
● Extend the interlocking problem to include other problems related to expert systems in railway stations, such as automatically detecting which semaphores and switches cannot be changed because they would imply a dangerous situation. Since our approach expresses the interlocking problem as an algebraic system similar to those used for implementing expert systems [16], we believe that our model can be easily integrated into these expert systems.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This work was partially supported by the research project PID2021-122905NB-C21 (Government of Spain).
This paper is dedicated to the memory of Eugenio Roanes-Lozano. Eugenio passed away suddenly just days after submitting this paper. He was an exceptional researcher in various fields, one of which was his extraordinary passion for trains, with numerous publications on the subject. This paper represents the culmination of his research in this area. Eugenio was a significant figure to us in many ways: as a researcher, teacher, colleague, and most importantly, as a friend. We would like to highlight his immense humanity. Eugenio, it was not yet time for you to take your last train. You will be deeply missed.
The authors declare there are no conflicts of interest.
In this section, we will formally prove that the new algebraic approach works.
Distinguishing different kinds of railway interlocking problems
Given the details of a railway station through its potential connectivity, E (see Definition 3.1), we will study the relation between different possible railway interlocking problems for this railway station.
We will start defining when railway interlocking problem is trivial.
Definition A.1. Given the potential connectivity of railway station, E, a configuration in it, P, and a placement of trains, Q, we say that the railway interlocking problem (P,Q) is trivial if and only if Q contains two repeated elements.
Obviously, a trivial railway interlocking problem is always in a dangerous situation (because there is more than one train at a certain section).
We will define a transitive relation between railway interlocking problems (see Definition A.2). To illustrate the intuition behind this definition, consider Figure A.1. On the right side of the figure, there is a railway interlocking problem A where a train is in Section Si (i.e., i∈Q), and can move from section Si to section Sj. From this interlocking problem A, we can derive another railway interlocking problem, B, illustrated on the left side of the figure. In this interlocking problem, B, there is another train in section Sj but sections Si and Sj are now separated: it is no longer possible to move from Section Si to section Sj or vice versa. We say that the interlocking problem B is derived from A. Problems B and A are closely related. According to Proposition A.1 we can detect if A is in a dangerous situation by analyzing B. That is to say, A is in a dangerous situation if and only if B is in a dangerous situation. As may be seen, the first and the third items of the formal definition (see Definition A.2) extend this idea so that this relation is reflective and transitive. The relation "is derived from" records possible train movements (Q2 contains both old and new train positions) while changing the configuration of the possible movements in the railway network (P2 does not correspond to the configuration resulting from the train movement from i to j).
Definition A.2. Let (P1,Q1) and (P2,Q2) be two possible railway interlocking problems in a railway station detailed by E. We will say that (P2,Q2) is immediately derived from (P1,Q1) if and only if ∃(i,j)∈P1 such that:
● i∈Q1
and
● P2=P1−{(i,j),(j,i)}
and
● Q2=Q1∪{j}
We define the relation "derived from" as the transitive and reflexive closure of the "immediately derived from'" relation. That is to say: (P2,Q2) is derived from (P1,Q1) if and only if
● P1=P2 and Q1=Q2
● (P1,Q1) is immediately derived from (P2,Q2)
● there is a railway interlocking problem (P3,Q3) of E such that (P2,Q2) is derived from (P3,Q3) and (P3,Q3) is derived from (P1,Q1).
(The key idea underlying the second condition is that if there is a train in a section Si and (i,j)∈P, we can consider instead that such train can reach Sj, adding that section to Q2 and to erase (i,j) and (j,i) from P2 –if they belong to P2.)
In Figure 4.1 there are more examples of this relation: the interlocking problem B is derived from A, C is derived from B, D is derived from C, E is derived from D.
Proposition A.1. Let (P1,Q1) and (P2,Q2) be two railway interlocking problems in a railway station detailed by E such that (P2,Q2) is derived from (P1,Q1). We have that:
(P1,Q1)isinadangeroussituation⇔(P2,Q2)isinadangeroussituation. |
Proof. As (P2,Q2) is derived from (P1,Q1), from Definition A.2 it follows that we can suppose that (i,j)∈P1, i∈Q1, P2=P1−{(i,j),(j,i)} and Q2=Q1∪{j}.
⇒) (P1,Q1) is in a dangerous situation. Let [u1,…un] and [v1…vm] be two paths fulfilling Definition 3.5 for (P1,Q1).
We will consider the following cases:
Case ∃k<n such that uk=j and uk+1=i. By (7) in Definition 3.5, we have that for every 1≤k′≤k uk′≠i and, therefore, (uk′,uk′+1)∉{(i,j),(j,i)}. Therefore, [u1…uk] and [j] fulfil all conditions in Definition 3.5 for (P2,Q2).
Case ∃k′<m such that vk′=j and vk′+1=i. It is analogous to the previous case.
Case ∃k<n such that uk=i and uk+1=j. Since i∈Q1, by (5) in Definition 3.5, we have that u1=i.
We will consider the following subcases:
v1=i. Then [u1] and [v1] fulfil all conditions in Definition 3.5 for (P2,Q2).
v1≠i. Since u1=i, by (6) in Definition 3.5, we have that for every 1≤k′<m, vk′≠i. Besides, we have that vm≠i since vm=un≠u1=i, by (4) and (7) in Definition 3.5 (since we are considering that n>1 in this case). Therefore, (vk′,vk′+1)∉{(i,j),(j,i)}.
Since u1=i, by (7) in Definition 3.5 we have that for every 2≤k≤n uk≠i, and therefore, (uk,uk+1)∉{(i,j),(j,i)}.
Consequently, [u2,…un] and [v1…vm] fulfil all conditions in Definition 3.5 for (P2,Q2).
Case ∃k′ such that vk′=i and vk′+1=j. It is analogous to the previous case.
Case for every 1≤k<n (uk,uk+1)∉{(i,j),(j,i)} and for every 1≤k′<m (vk′,vk′+1)∉{(i,j),(j,i)}. It is immediate to prove that [u1,…un] and [v1…vm] fulfil all conditions in Definition 3.5 for (P2,Q2).
⇐) Let [u1…un] and [v1…vm] be paths fulfilling Definition 3.5 for the railway interlocking problem (P2,Q2). Since P2⊂P1, we have that for every 1≤k<n (uk,uk+1)∈P1 and that for every 1≤k′<m (vk′,vk′+1)∈P1. We will consider the following cases:
Case 1. u1=j=v1. We have that [i,j] and [j] are paths fulfilling Definition 3.5 for (P1,Q1).
Case 2. u1≠j≠v1. We have that [u1…un] and [v1…vm] are paths fulfilling Definition 3.5 for (P1,Q1).
Case 3. u1=j≠v1. We have that v1≠i. Otherwise, we would have that [v1,u1…,un] and [v1…vm] would be two different paths from v1 to vm=un for (P1,Q1) and this is excluded (see Remark 3.5). Consequently, [i,u1…un] and [v1…vm] are paths fulfilling Definition 3.5 for (P1,Q1) because:
● (i,u1)=(i,j)∈P1.
● {v1,i}⊆Q1 because i∈Q1, v1≠i, and, since v1≠j v1∈Q1.
Case 4. v1=j≠u1. It is analogous to the previous case.
Although every trivial railway interlocking problem is in a dangerous situation, not all railway interlocking problems in a dangerous situations are trivial ones. However, a trivial railway interlocking problem can be derived from any railway interlocking problem in a dangerous situation (Theorem A.1).
Theorem A.1. A railway interlocking problem (P,Q) is in a dangerous situation if and only if a trivial railway interlocking problem is derived from (P,Q).
Proof. ⇒) Let us suppose that (P,Q) is in a dangerous situation.
Let [u1,…,un] and [v1,…,vm] be paths fulfilling Definition 3.5. That is to say, we have that un=vm, (ui,ui+1)∈P, (vi,vi+1)∈P, u1∈Q and v1∈Q.
We'll proceed by induction on the sum of the lengths of the two paths, n+m.
Case n = m = 1: The paths are [u1] and [v1]. Since u1=v1 we have that this is a trivial railway interlocking problem.
Case n>1 or m>1. Let us suppose that n>1 (the case m>1 is identical). Since (u1,u2)∈P and u1∈Q, we have that (P2,Q2)=(P−{(u1,u2),(u2,u1)},Q∪{u2}) is derived from (P,Q). Then (P2,Q2) is in a dangerous situation because the paths [u2,…,un] and [v1,…,vm] fulfil the conditions in Definition 3.5. By induction hypothesis, a trivial railway interlocking problem is derived from (P2,Q2), and therefore, this trivial railway interlocking problem is derived from (P,Q).
⇐) Let us suppose that a trivial railway interlocking problem is derived from the railway interlocking problem (P,Q). As a consequence of Definition A.1, a trivial railway interlocking problem is always in a dangerous situation, and therefore, by Proposition A.1, we have that (P,Q) is in a dangerous situation too.
Algebraic Preliminaries. Some introductory notes about polynomial rings
In this section we will briefly describe some results about polynomial rings that we will need to prove the validity of our approach (see, for instance, [34], for a detailed introduction to the topic).
Definition A.3. A monomial in x1,…,xN is a product of the form xα11⋅xα22⋅…xαNN. An element in the polynomial ring K[x1,…,xN] is a polynomial in the variables x1,…,xN whose coefficients lie in the field K, that is, a finite linear combination of monomials with coefficients in K:
∑α=(α1,α2,...,αN)a(α1,α2,...,αN)xα11xα22…xαNN |
where a(α1,α2,...,αN)∈K and α1,α2,...,αN∈Z≥0, written sometimes, for the sake of brevity
∑αaαxα , aα∈K , α∈ZN≥0 |
If a(α1,α2,...,αN)≠0 then a(α1,α2,...,αN)xα1xα2…xαN is called a term. If K=Q, an example of polynomial in Q[x1,x2,x3] is p=2x21+7x1x2x3−x3+12x2x3.
Later in this paper we will focus on the case K=Z2. An element in the polynomial ring A=Z2[x1,…,xN] is a polynomial in the variables x1,…,xN whose coefficients lie in the field Z2={0,1}. An example of this kind of polynomials is p=x1x2+x3+x2x3. We must take into account that the coefficients lie in Z2, and therefore, we have that, for instance, (since 1+1 = 0 in Z2):
x1x2+x3x4+x3x4=x1x2+(1+1)x3x4=x1x2 |
The algebraic structure ideal is key in our approach.
Definition A.4. An ideal of a commutative ring is a subring that verifies that the product of any element of the ring by any element of the subring belongs to the subring.
Example A.1. For instance, the set of even numbers is an ideal of Z. For example, the set of polynomials in Z[x] with a trailing coefficient equal to 0 (i.e., the multiples of x) form an ideal of Z[x].
Proposition A.2. Given a set of polynomials G={f1,…,fm}⊆K[x1,…,xN], the smallest ideal containing G, denoted ⟨f1,…,fm⟩, turns out to be:
⟨f1,…,fm⟩={α1f1+…αmfm|α1,…,αm∈K[x1,…,xN]} |
Notation A.1. For the sake of simplicity, if G is a list of polynomials, we will denote ⟨G⟩ the ideal generated by the polynomials in G.
Once an order for the variables is given, for instance x1>x2>…>xm, a total order for the monomials can be defined (see [34], pp. 52–57). Although there are many monomial orderings, we will use the pure lexicographical order in this paper. Simplifying it, if we have, for instance, x<y and the monomials x2y=xxy and x3=xxx, think of them as if they were words to be ordered in a dictionary: xxx<xxy.
Definition A.5. The leading monomial of a polynomial p∈K[x1,…,xN], denoted LM(p), is its greatest monomial with respect to the chosen monomial ordering. The corresponding term is its leading term, and is denoted LT(p).
Example A.2. For example, in R[x1,x2,x3] with x1>x2>x3 and the lexicographic monomial order:
LM(2x21+7x1x2x3−x3+12x2x3)=x21 |
and
LT(2x21+7x1x2x3−x3+12x2x3)=2x21 |
Remark A.1. In this paper we will focus on the case K=Z2, and, obviously, in these polynomial rings: LT(p)=LM(p).
Theorem A.2. Once the monomial ordering is defined in K[x1,…,xN], the division of a polynomial p by an ordered m- list of polynomials G=(f1,…,fm) can be defined. This division outputs:
p=α1f1+…+αmfm+r |
where α1,…,αm,r∈K[x1,…,xN] and either r=0 or r is a linear combination of monomials, none of which is divisible by any of LT(f1)…LT(fm).
A proof can be found in (see [34], pp. 62–64).
Notation A.2. The polynomial r, remainder of p on division by G, will be denoted NR(p,G) or ¯pG.
The proof in [34] (pp. 62–64) provides an algorithm to find the polynomials α1,…αm,r∈K[x1,…,xN] in Theorem A.2. In each step of this algorithm we obtain an intermediate-dividend. We will require only some of the first intermediate-dividends of this algorithm.
Definition A.6. Given p∈K[x1,…,xN] and an ordered m- list of polynomials G=(f1,…,fm)⊆K[x1,…,xN], we recursively define the first-intermediate-dividends of p on division by G, r0,…,rn∈K[x1,…,xN], as follows:
● r0=p,
● if i>0 then
– if ∃j∈{1,…,m} such that LT(fj)|LT(ri) then
ri+1=ri−LT(ri)LT(fk)fk |
where k is the minimum j such that LT(fj)|LT(ri),
– if ∀j∈{1,…,m},LT(fj)⧸|LT(ri) then rn=ri.
According to the proof [34] (pp. 62–64), we have:
Proposition A.3. Let p∈K[x1,…,xN] and let G=(f1,…,fm)⊆K[x1,…,xN] be an ordered m- list of polynomials. Let r0,…rn∈K[x1,…,xN] be the first-intermediate-dividends of p on division by G. We have that:
rn=0ifandonlyifNR(p,G)=0 |
Groebner bases are very special ideal bases: among other nice properties, they allow to decide whether a polynomial belongs to the ideal or not (see Theorem A.3). As we wil see, Grobener bases will play an important role in the proof in our main result, Theorem A.11.
Theorem A.3. Let p be a polynomial in K[x1,…,xN] and let G be a Groebner basis for an ideal I⊂K[x1,…,xN]. Then we have that:
p∈I⇔NR(p,G)=0 |
A proof can be found in [34] (Proposition 1 and Corollary 2, pp. 79–80).
Notation A.3. Let p1,p2∈K[x1,…,xN]. LCM(p1,p2) denotes least common multiple of p1 and p2.
Definition A.7. Let p1,p2∈K[x1,…,xN]. The S-polynomial of p1 and p2 is:
S(p1,p2)=LCM(LM(p1),LM(p2))LT(p1)p1−LCM(LM(p1),LM(p2))LT(p2)p2 |
Remark A.2. Obviously, in case the polynomial ring considered is A=Z2[x1,…,xN], the − in Definition A.7 can be substituted by a +.
Remark A.3. In case the polynomial ring considered is A=Z2[x1,…,xN], if p∈A, p≠0, then LM(p)=LT(p).
The following theorem allows to verify if G is a Groebner basis:
Theorem A.4. Let I be a polynomial ideal in K[x1,…,xN] and let G={f1,…,fm} be a basis of I. Then:
GisaGroebnerbasis⇔¯S(fi,fj)G∗=0 |
(where G∗ is an an ordered m- list of the polynomials in G, ordered in some way).
A proof can be found in [34] (Theorem 6, pp. 82–85).
The railway interlocking problem in algebraic terms
Given a railway station and the description, E, of its potential connectivity between sections (see Definition 3.1), we will define the list E′ from the list E (see Section 4.1) as follows:
E′=E∪⋃(i,j)∈Em2ij |
Lemma A.5. Let E be the description of the potential connectivity between sections of a railway station. Then:
E′isaGroebnerbasisof⟨E′⟩. |
Proof. It is enough to prove that ∀f1,f2∈E′, ¯S(f1,f2)E′=0. But the elements of E′ are of the form gij or g′ij or t2i or m2ij, and, although tedious, it can be easily checked by hand or using a CAS, that in the 42 possible combinations, the S-polynomial vanishes.
Hereinafter, p and q are the polynomials representing the given configuration of the railway station, P, and the placement of the trains, Q, respectively (see Section 4.1).
Lemma A.6. Let (P,Q) be a railway interlocking problem for a railway station whose connectivity is described by E. Let r0,r1…rn be the first-intermediate-dividends of pq on division by any chosen ordering of the elements E′. Then:
i) ∀i∈{0,…,n−1} there is a railway interlocking problem (Pi,Qi) derived from (P,Q) such that ri=piqi.
ii) If NR(pq,E′)=0 the railway interlocking problem (P,Q) is in a dangerous situation.
Proof.
i) For i=0, we have that r0=pq and, therefore, (P0,Q0)=(P,Q) is a railway interlocking problem derived from (P,Q).
Suppose that 0<i<n, ri−1=pi−1qi−1 and (Pi−1,Qi−1) is a railway interlocking problem derived from (P,Q). We will prove that ri represents a railway interlocking problem, (Pi,Qi), derived from (P,Q). According to Definition A.6, we have that:
ri=ri−1−LT(ri−1)LT(fk)fk |
where fk is a polynomial in E′ such that LT(fk)|LT(ri−1). We have also that LT(ri−1)=LT(pi−1qi−1)=pi−1qi−1, where pi−1 is a monomial that contains only variables of the kind lxy and mxy, and qi−1 is a monomial that contains only variables of the kind tx (see Section 4.1).
We have that fk≠t2k. Otherwise, we would have that ri=0, and therefore, i=n (but we have supposed that i<n).
We have that fk≠m2xy because pq is a monomial where the exponent of the mxy variables is at most 1.
Consequently, there are two cases left:
Case fk=gxy. We have that gxy is of the form:
gxy=lxylyxtx+mxymyxtxty.
Since LT(fk)|LT(ri−1) we have that LT(gx,y)=lxylyxtx|pi−1qi−1. Thus, we have that lxylyx|pi and tx|qi (remember that pi−1 is a monomial that contains only variables of the kind lxy and mxy, and qi−1 is a monomial that contains only variables of the kind tx). Consequently:
– pi−1 is of the form pi−1=p′⋅lxylyx where p′ is a monomial.
– qi−1 is of the form qi−1=q′⋅tx where q′ is a monomial.
Therefore, we have that
ri=ri−1−LT(ri−1)LT(fk)fk=p′⋅mxymyxq′⋅txty |
We define:
– pi=p′⋅mxymyx
– qi=q′⋅txty
Just observe that pi is a monomial that contains the same variables as pi−1 except that lx,y and ly,x in pi−1 have respectively turned to be mx,y and my,x. In the same way, qi is a monomial that contains all the variables in qi−1 and also the variable ty. Consequently, we have that ri=piqi are polynomials representing the railway interlocking problem (Pi,Qi) where Pi=Pi−1−{(x,y),(y,x)} and Qi=Qi−1∪{y}.
Case fk=g′x,y. We have that g′xy is of the form:
g′xy=lxymyxtx+mxymyxtxty.
Since LT(fk)|LT(ri−1) we have that LT(g′x,y)=lxymyxtx|pi−1qi−1. Thus, we have that lxymyx|pi and tx|qi (remember that pi−1 is a monomial that contains only variables of the kind lxy and mxy, and qi−1 is a monomial that contains only variables of the kind tx). Consequently:
– pi−1 is of the form pi−1=p′⋅lxymyx where p′ is a monomial
– qi−1 is of the form qi−1=q′⋅tx where q′ is a monomial
Therefore, we have that:
ri=ri−1−LT(ri−1)LT(fk)fk=p′⋅mxymyxq′⋅txty |
We define:
– pi=p′⋅mxymyx
– qi=q′⋅txty
Just observe that pi is a monomial that contains the same variables as pi−1 except that lx,y in pi−1 has turned to be mx,y. In the same way, qi is a monomial that contains all the variables in qi−1 and also the variable ty. Consequently, we have that ri=piqi is a monomial representing the railway interlocking problem (Pi,Qi) where Pi=Pi−1−{(x,y)}=Pi−1−{(x,y),(y,x)} (just observe that (y,x)∉Pi−1) and Qi=Qi−1∪{y}.
Consequently, we have that ri=piqi represents that the interlocking problem (Pi,Qi) is derived from (Pi−1,Qi−1). By the transitivity property of the derived relation between railway interlocking problems (see Definition A.2), we have that (Pi,Qi) is also derived from (P,Q).
ⅱ) According to Proposition A.3, we have that rn=NR(pq,E′)=0. Consequently,
0=rn−1−LT(rn−1)LT(fk)fk |
That is to say, pn−1qn−1=pn−1qn−1LT(fk)fk
Since pn−1qn−1 is a monomial, we have that fk must be also a monomial. Consequently, fk cannot be either of the form gij or the form g′ij. Besides, fk cannot be either of the form m2i since pq is a monomial where the exponent of the mij variables is at most 1. Therefore, we have that fk=t2x.
Since LT(fk)|LT(rn−1), we have that t2x|pn−1qn−1, and consequently, the interlocking problem (Pn−1,Qn−1) is a trivial railway interlocking because Qn−1 contains a repeated element x. Therefore, (Pn−1,Qn−1) is in a dangerous situation.
By ⅰ) we have that (Pn−1,Qn−1) is derived from (P,Q). Since (Pn−1,Qn−1) is in a dangerous situation, by Theorem A.1, we have that (P,Q) is also in a dangerous situation.
Lemma A.7. Let (P,Q) be a railway interlocking problem for a railway station described by E. We have that:
NR(pq,E)=NR(pq,E′) |
Proof. Since the algorithm for calculating NR(pq,E′) in Lemma A.6 discards the case fk=m2ij, we have that NR(pq,E)=NR(pq,E′).
According to previous results (see ii in Lemmas A.6 and A.7), we have a sufficient condition to detect if an interlocking problem (P,Q) is in a dangerous situation: if NR(pq,E)=0 then the interlocking problem (P,Q) is in a dangerous situation. Now, we will prove that this is also a necessary condition: if the interlocking problem (P,Q) is in a dangerous situation, then NR(pq,E)=0. This proof is more complicated and requires translating the problem in terms of a ideal membership problem. An important result for the proof will be that E′ is a Groebner basis.
Lemma A.8. Let (P0,Q0) be a trivial railway interlocking problem for a railway station described by E. We have that:
p0q0∈⟨E′⟩ |
Proof. According to Definition A.1, i must appear more than once in Q0. Let k be the number of times i appears in Q0. Since k≥2, we have that k=m+2 where m≥0. Therefore, we have that q0 is of the form q0=q′⋅tki=q′⋅tm+2i=q′⋅tmi⋅t2i where q′ is a monomial. Consequently, p0q0=p0⋅q′⋅tmi⋅t2i∈⟨E′⟩ since t2i∈E′.
Lemma A.9. Let (P1,Q1) and (P2,Q2) be two railway interlocking problems for a railway station described by E such that (P2,Q2) is derived from (P1,Q1). We have that:
p1q1∈⟨E′⟩⇔p2q2∈⟨E′⟩ |
Proof. Let (i,j)∈P1 be such that i∈Q1
and P2=P1−{(i,j),(j,i)}
and Q2=Q1∪{j}.
Since i∈Q1 and Q2=Q1∪{j}, we have that q1 and q2 are of the form (for a certain monomial q):
q1=q⋅ti
q2=q⋅titj
Since (i,j)∈P1 we have that li|p1.
We will consider two cases:
Case (j,i)∈P1. We have that lji|p1. Since P2=P1∪{(i,j)(j,i)}, we have that p1 and p2 are of the form (for a certain monomial p):
p1=p⋅lijlji
p2=p⋅mijmji
Besides, we have that gij=lijljiti+mijmjititj∈E′. Therefore, we have that:
pq⋅gij=pq⋅lijljiti+pq⋅mijmjititj=p1q1+p2q2
Consequently,
p1q1∈⟨E′⟩⇔p2q2∈⟨E′⟩ |
Case (j,i)∉P1. We have that mji|p1. Since P2=P1∪{(i,j),(j,i)}, we have that the monomials p1,p2 are of the form (where p is a certain monomials):
p1=p⋅lijmji
p2=p⋅mijmji
Besides, we have that g′ij=lijmjiti+mijmjititj∈E′. Therefore, we have that:
pq⋅g′ij=pq⋅lijmjiti+pq⋅mijmjititj=p1q1+p2q2
Consequently,
p1q1∈⟨E′⟩⇔p2q2∈⟨E′⟩ |
We have the following theorem:
Theorem A.10. Let (P,Q) be a railway interlocking problem for a railway station described by E.
(P,Q)isinadangeroussituation⇔pq∈⟨E′⟩ |
Proof. ⇒) Let (P,Q) be a railway interlocking problem in a dangerous situation. According to Theorem A.1, we have that a trivial railway interlocking problem is derived from (P,Q). According to Lemmas A.8 and A.9, we have that pq∈⟨E′⟩.
⇐) Suppose that pq∈⟨E′⟩. Since E′ is a Groebner basis (see Lemma A.5), we have, by Theorem A.3, that NR(pq,E′)=0. Consequently, by Lemma A.6, we have that (P,Q) is in a dangerous situation.
Since the list E′ is indeed a Groebner basis (see Lemma A.5), the ideal membership problem of the previous theorem can be easily solved (see Theorem A.11).
Theorem A.11. Let (P,Q) be a railway interlocking problem for a railway station described by E. We have that:
(P,Q)isinadangeroussituation⇔NR(pq,E)=0 |
Proof. This is a immediate consequence of Theorem A.3, Lemma A.5, Theorem A.10 and Lemma A.7.
Here we will propose an efficient algorithm for calculating NR(p,E) for the specific case that:
● The coefficients of polynomials lie in Z2.
● p is a monomial.
● E={gi} is a list of polynomials such that each gi is the sum of two monomials pi and qi. That is to say, gi=pi+qi where pi>qi. We will use the notation LT(gi)=pi and M(gi)=qi.
In this specific case, the general algorithm for calculating NR can be simplified since all intermediate dividends are monomials and the algorithm can run in O(N) if we use appropriate data structures:
● In order to represent p=∏jxjvj we use the array [v1…vN]. An empty array [] will represent the monomial p=0. We will use this data structure to represent the intermediate dividends of the algorithm. For example, we represent the monomial p=x1x32 by means of the array p:[1,3,0,…,0].
● In order to represent the monomials pi and qi in gi=pi+qi we use a list with the form {(xi,vi)}. In this case a list {(xj,vj)} will represent the monomial qi=∏jxjvj. For example, we represent the monomial qi=x1x32 by means of the list {(x1,1),(x2,3)}.
● In order to represent the polynomial gi=pi+qi, we use two lists: one for representing pi, another for representing qi. For example, for E={g1,g2,g3} where g1=x1x2+x2x3;g2=x22+x5x6;g3=x3+x5 we represent each polynomial gi in the following way:
– g1=x1x2+x2x3 is represented by these two lists: LT(g1)={(1,1),(2,1)};M(g1)={(2,1),(3,1)}.
– g2=x22+x5x6 is represented by these two lists: LT(g2)={(2,2)};M(g2)={(5,1),(6,1)}.
– g3=x3+x5 is represented by these two lists: LT(g3)={(3,1)};M(g3)={(5,1)}.
● For each variable xj we consider Fxj, the list of the polynomials gi∈E such that the variables are in LT(g): that is to say, there is some natural e such that (xj,e)∈LT(g). For example, in case that E=[g1,g2,g3]=[x1x2+x2x3,x22+x5x6,x3+x5], we have that:
– Fx1={g1} because x1 appears in the monomial LT(g1).
– Fx2={g1,g2} because x2 appears in the monomials LT(g1) and LT(g2).
– Fx3={g3} because x2 appears in the monomial LT(g3).
– Fx4=Fx5=Fx6=∅ because x4,x5,x6 do not appear in LT(gi) for any gi.
● For each polynomial gi, we consider Vgi, the set of the variables that are in M(gi). For example, in case that E=[g1,g2,g3]=[x1x2+x2x3,x22+x5x6,x3+x5], we have that:
– Vg1={2,3} because x2 and x3 appears in M(g1).
– Vg2={5,6} because x5 and x6 appears in M(g2).
– Vg3={5} because x5 appears in M(g3).
The algorithm for calculating the remainder of a monomial p with respect to a list of polynomials E is the following:
NR(int[]monomial,listofpolynomialsE)(1)int[]p=Clonemonomial(2)CalculateF_iforeveryvariablei(3)CalculateV_gforeverypolynomialginE(4)Stack<Polynomial>check=E(5)do(6)g=check.Pop();(7)if(CanBeUsedToReduce(g,p))(8)Reduce(g,p);(9)if(p==[])return;(10)foreachVariablejinV_g)(11)foreach(PolynomialfinF_j)(12)check.Push(f);(13)while(check.Count>0);(14)returnp; |
The algorithm CanBeUsedToReduce(g,p) outputs true if LT(g)‖p (that is to say, if the polynomial g can be used to reduce the monomial p). This algorithm is very simple and checks for every (a,b)∈LT(g) if p[a]>b. Since the size of LT(g) is constant in our algebraic model, this algorithm runs in O(1).
The algorithm Reduce(g,p) calculates a new intermediate dividend (that is to say, reduces the monomial p with respect to the polynomial g). This algorithm is also very simple due to the data structures used. For every (a,b)∈LT(g) and (a,c)∈M(g), we update p[a] with the value p[a]−b+c. Since the size of the sets LT(g) and M(g) are constant in our algebraic model, this algorithm runs in O(1).
The algorithm uses a stack, check, in which the algorithm stores the polynomials gi that may be used to reduce the monomial p. The algorithm NR runs in O(N) since the step Reduce can only be applied N times at most and every time the monomial is reduced, the number of polynomials added to check is constant.
[1] | W. M. Haddad, V. Chellaboina, S. G. Nersesov, Impulsive and Hybrid Dynamical Systems: Stability, Dissipativity, and Control, New Jersey: Princeton University Press, 2006. https://doi.org/10.1515/9781400865246 |
[2] | X. Li, S. Song, Impulsive Systems With Delays: Stability and Control, Singapore: Springer, 2022. https://doi.org/10.1007/978-981-16-4687-4 |
[3] |
J. Cao, G. Stamov, I. Stamova, S. Simeonov, Almost periodicity in impulsive fractional-order reaction-diffusion neural networks with time-varying delays, IEEE Trans. Cybern., 51 (2021), 151–161. https://doi.org/10.1109/TCYB.2020.2967625 doi: 10.1109/TCYB.2020.2967625
![]() |
[4] |
X. Yang, Y. Liu, J. Cao, L. Rutkowski, Synchronization of coupled time-delay neural networks with mode-dependent average dwell time switching, IEEE Trans. Neural Netw. Lear. Syst., 31 (2020), 5483–5496. https://doi.org/10.1109/TNNLS.2020.2968342 doi: 10.1109/TNNLS.2020.2968342
![]() |
[5] |
S. Novo, R. Obaya, V. M. Villarragut, Asymptotic behavior of solutions of nonautonomous neutral dynamical systems, Nonlinear Anal., 199 (2020), 111918. https://doi.org/10.1016/j.na.2020.111918 doi: 10.1016/j.na.2020.111918
![]() |
[6] |
L. Qiang, B.-G. Wang, X.-Q. Zhao, Basic reproduction ratios for almost periodic compartmental models with time delay, J. Differ. Equ., 269 (2020), 4440–4476. https://doi.org/10.1016/j.jde.2020.03.027 doi: 10.1016/j.jde.2020.03.027
![]() |
[7] | S. Niculescu, Delay Effects on Stability: A Robust Control Approach, New York: Springer-Verlag, 2001. https://doi.org/10.1007/1-84628-553-4 |
[8] | K. Gopalsamy, Stability and Oscillations in Delay Differential Equations of Population Dynamics, Dordrecht: Kluwer Academic Publishers, 1992. https://doi.org/10.1007/978-94-015-7920-9 |
[9] |
I. M. Stamova, G. T. Stamov, On the practical stability with respect to h-manifolds of hybrid Kolmogorov systems with variable impulsive perturbations, Nonlinear Anal., 201 (2020), 111775. https://doi.org/10.1016/j.na.2020.111775 doi: 10.1016/j.na.2020.111775
![]() |
[10] |
L. Chen, J. Sun, F. Chen, L. Zhao, Extinction in a Lotkaolterra competitive system with impulse and the effect of toxic substances, Appl. Math. Model., 40 (2016), 2015–2024. https://doi.org/10.1016/j.apm.2015.09.057 doi: 10.1016/j.apm.2015.09.057
![]() |
[11] |
M. Niedzwiecki, M. Ciolek, New semicausal and noncausal techniques for detection of impulsive disturbances in multivariate signals with audio applications, IEEE Trans. Signal Process., 65 (2017), 3881–3892. https://doi.org/10.1109/TSP.2017.2692740 doi: 10.1109/TSP.2017.2692740
![]() |
[12] |
T. Wei, X. Xie, X. Li, Persistence and periodicity of survival red blood cells model with time-varying delays and impulses, Math. Model. Control, 1 (2021), 12–25. https://doi.org/10.3934/mmc.2021002 doi: 10.3934/mmc.2021002
![]() |
[13] |
T. Nagashio, T. Kida, Y. Hamada, T. Ohtani, Robust two-degrees-of-freedom attitude controller design and flight test result for engineering test satellite-Ⅷ spacecraft, IEEE Trans. Control Syst. Techn., 22 (2014), 157–168. https://doi.org/10.1109/10.1109/TCST.2013.2248009 doi: 10.1109/10.1109/TCST.2013.2248009
![]() |
[14] |
I. Stankovic, I. Orovic, M. Dakovic, S. Stankovic, Denoising of sparse images in impulsive disturbance environment, Multimed. Tools Appl., 77 (2018), 5885–5905. https://doi.org/10.1007/s11042-017-4502-7 doi: 10.1007/s11042-017-4502-7
![]() |
[15] |
T. Wei, X. Li, Fixed-time and predefined-time stability of impulsive systems, IEEE/CAA J. Automa. Sin., 10 (2023), 1086–1089. https://doi.org/10.1109/JAS.2023.123147 doi: 10.1109/JAS.2023.123147
![]() |
[16] |
X. Tan, C. Xiang, J. Cao, W. Xu, G. Wen, L. Rutkowski, Synchronization of neural networks via periodic self-triggered impulsive control and its application in image encryption, IEEE Trans. Cybern., 52 (2022), 8246–8257. https://doi.org/10.1109/TCYB.2021.3049858 doi: 10.1109/TCYB.2021.3049858
![]() |
[17] | T. Yang, Impulsive Control Theory, Berlin: Springer, 2001. https://doi.org/10.1007/3-540-47710-1 |
[18] |
X. Li, S. Song, J. Wu, Exponential stability of nonlinear systems with delayed impulses and applications, IEEE Trans Autom. Control, 64 (2019), 4024–4034. https://doi.org/10.1109/TAC.2019.2905271 doi: 10.1109/TAC.2019.2905271
![]() |
[19] |
X. Li, X. Yang, J. Cao, Event-triggered impulsive control for nonlinear delay systems, Automatica, 117 (2020), 108981. https://doi.org/10.1016/j.automatica.2020.108981 doi: 10.1016/j.automatica.2020.108981
![]() |
[20] |
G. Ballinger, X. Liu, Existence, uniqueness and boundedness results for impulsive delay differential equations, Appl. Anal., 74 (2000), 71–93. https://doi.org/10.1080/00036810008840804 doi: 10.1080/00036810008840804
![]() |
[21] |
S. Arora, M. T. Mohan, J. Dabas, Existence and approximate controllability of non-autonomous functional impulsive evolution inclusions in Banach spaces, J. Differ. Equ., 307 (2022), 83–113. https://doi.org/10.1016/j.jde.2021.10.049 doi: 10.1016/j.jde.2021.10.049
![]() |
[22] |
H. Leiva, Controllability of the impulsive functional BBM equation with nonlinear term involving spatial derivative, Syst. Control Lett., 109 (2017), 12–16. https://doi.org/10.1016/j.sysconle.2017.09.001 doi: 10.1016/j.sysconle.2017.09.001
![]() |
[23] |
J. Yan, B. Hu, Z.-H. Guan, Controllability criteria on discrete-time impulsive hybrid systems with input delay, IEEE Trans. Syst. Man Cybern.: Syst., 53 (2023), 2304–2316. https://doi.org/10.1109/TSMC.2022.3212533 doi: 10.1109/TSMC.2022.3212533
![]() |
[24] |
T. Zhang, J. Zhou, Y. Liao, Exponentially stable periodic oscillation and Mittag effler stabilization for fractional-order impulsive control neural networks with piecewise Caputo derivatives, IEEE Trans. Cybern., 52 (2022), 9670–9683. https://doi.org/10.1109/TCYB.2021.3054946 doi: 10.1109/TCYB.2021.3054946
![]() |
[25] |
J. Alzabut, T. Abdeljawad, On existence of a globally attractive periodic solution of impulsive delay logarithmic population model, Appl. Math. Comput., 198 (2008), 463–469. https://doi.org/10.1016/j.amc.2007.08.024 doi: 10.1016/j.amc.2007.08.024
![]() |
[26] |
J. Alzabut, G. Stamov, E. Sermutlu, On almost periodic solutions for an impulsive delay logarithmic population model, Math. Comput. Model., 51 (2010), 625–631. https://doi.org/10.1016/j.mcm.2009.11.001 doi: 10.1016/j.mcm.2009.11.001
![]() |
[27] |
Z. Yang, D. Xu, Existence and exponential stability of periodic solution for impulsive delay differential equations and applications, Nonlinear Anal.: Theo. Meth. Appl., 64 (2006), 130–145. https://doi.org/10.1016/j.na.2005.06.014 doi: 10.1016/j.na.2005.06.014
![]() |
[28] |
A. Weng, J. Sun, Globally exponential stability of periodic solutions for nonlinear impulsive delay systems, Nonlinear Anal. Theo. Meth. Appl., 67 (2007), 1938–1946. https://doi.org/10.1016/j.na.2006.08.019 doi: 10.1016/j.na.2006.08.019
![]() |
[29] |
X. Li, M. Bohner, An impulsive delay differential inequality and applications, Comput. Math. Appl., 64 (2012), 1875–1881. https://doi.org/10.1016/j.camwa.2012.03.013 doi: 10.1016/j.camwa.2012.03.013
![]() |
[30] | D. Yue, S. Xu, Y. Liu, Differential inequality with delay and impulse and its applications to design of robust control, Control Theo. Appl., 16 (1999), 519–524. |
1. | Antonio Hernando, José Luis Galán-García, Gabriel Aguilera-Venegas, A novel way to build expert systems with infinite-valued attributes, 2024, 9, 2473-6988, 2938, 10.3934/math.2024145 | |
2. | Antonio Hernando, José Luis Galán-García, Gabriel Aguilera-Venegas, A fast and general algebraic approach to Railway Interlocking System across all train stations, 2024, 9, 2473-6988, 7673, 10.3934/math.2024373 | |
3. | Antonio Hernando, Gabriel Aguilera-Venegas, José Luis Galán-García, Sheida Nazary, An interlocking system determining the configuration of rail traffic control elements to ensure safety, 2024, 9, 2473-6988, 21471, 10.3934/math.20241043 | |
4. | Antonio Hernando, José Luis Galán–García, Yolanda Padilla–Domínguez, María Ángeles Galán–García, Gabriel Aguilera–Venegas, A library in CoCoA for implementing railway interlocking systems, 2025, 466, 03770427, 116594, 10.1016/j.cam.2025.116594 |
N = 52 | N = 156 | N = 260 | N = 520 | N = 780 | N = 1040 | N = 1560 | |
M = 5 | M = 15 | M = 25 | M = 50 | M = 75 | M = 100 | M = 150 | |
Model described in [35] | 10.23 s | 250.250 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [17] | 15.356 s | 380.368 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [18] | 1.124 s | 38.292 s | 554.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [19] | 0.320 s | 0.920 s | 2.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [37] | 0.020 s | 0.047 s | 1.038 s | 16.458 s | >1 h | >1 h | >1 h |
Our approach in CoCoA | <0.001s | 0.015 s | 0.015 s | 0.078 s | 0.156 s | 0.250 s | 0.610 s |
M = 10 | M = 20 | M = 30 | M = 50 | M = 100 | |
Model described in [37] | 646 ms | 799 ms | 1045 ms | 1124 ms | 1522 ms |
Model described in [19] | 2340 ms | 2340 ms | 2340 ms | 2340 ms | 2340 ms |
Our approach | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms |
N = 52 | N = 156 | N = 260 | N = 520 | N = 780 | N = 1040 | N = 1560 | |
M = 5 | M = 15 | M = 25 | M = 50 | M = 75 | M = 100 | M = 150 | |
Model described in [35] | 10.23 s | 250.250 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [17] | 15.356 s | 380.368 s | >1 h | >1h | >1 h | >1 h | >1 h |
Model described in [18] | 1.124 s | 38.292 s | 554.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [19] | 0.320 s | 0.920 s | 2.180 s | >1 h | >1 h | >1 h | >1 h |
Model described in [37] | 0.020 s | 0.047 s | 1.038 s | 16.458 s | >1 h | >1 h | >1 h |
Our approach in CoCoA | <0.001s | 0.015 s | 0.015 s | 0.078 s | 0.156 s | 0.250 s | 0.610 s |
M = 10 | M = 20 | M = 30 | M = 50 | M = 100 | |
Model described in [37] | 646 ms | 799 ms | 1045 ms | 1124 ms | 1522 ms |
Model described in [19] | 2340 ms | 2340 ms | 2340 ms | 2340 ms | 2340 ms |
Our approach | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms | 0.14 ms |