Rodolphe Farrando

Max-plus modeling and simulation of traffic on mass-transit lines: application to skip-stop policy and line with a junction

Keywords: operation

. The first constraint establishes a lower bound on the trains' run and station dwell times. The second constraint sets a minimum safe separation time between successive trains to prevent any risk of collision. Whenever possible, we formulate the models linearly using max-plus algebra. This algebra enables us to derive phase diagrams (or fundamental diagrams) analytically and interpret the principles of the physics of traffic.

In Chapter 3, based on the work in [23], we develop two models for a skipstop policy. We designate specific predetermined stations where we impose that every other train skips these stations to increase their speed. The first restricted model ensures that each origin-destination pair can be reached without passengers needing to transfer on the line. In the second model, we relax this constraint, and the unrestricted model only requires that a train stopping at a skippable station is followed by a train that skips this station. Through numerical simulations, we study the steady state of the train dynamics. Our findings are represented in fundamental diagrams that illustrate the line's frequency with and without the skip-stop policy as a function of the number of running trains. We compare these frequencies, assess potential benefits for the operator, analyze passenger travel times, and calculate the resulting savings or losses they may experience.

In Chapter 4 and Appendix A, we extend our model developed in the previous chapter to incorporate, as input to the model, the services defined by the operator (i.e., the stations where a train will stop and those it must skip). Furthermore, by adapting our model, we show that it can be linearly written in the max-plus algebra. Thanks to the algebraic formulation, we characterize the conditions under which the train dynamics admit a stationary regime and show that the asymptotic average growth rate of the train dynamics coincides with the unique max-plus eigenvalue of the matrix describing the train dynamics. The asymptotic average growth rate of the train dynamics is interpreted here as the asymptotic average train time headway. We apply our model to Paris metro Line 1 and analytically derive its phase diagram. We demonstrate the existence of three distinct phases: free flow, capacity, and congestion. We also show that the free-flow phase is piecewise linear: when the number of trains becomes significant, trains interact, limiting the increase of the train's frequency. We also analyze the impact of the choice of skippable stations, considering their number or the stopping patterns defined by the operator.

The previous chapter primarily models the operator's perspective regarding the iii iv skip-stop policy. Chapter 5, by including passenger arrival rates at stations and their origin-destinations, allows for a precise measurement of the impact of the skipstop policy on passengers. We construct a model for train dwell times based on the demand and the services defined by the operator. Similar to the previous chapter, we demonstrate that the model can be linearly formulated using max-plus algebra.

, we adapt the model to incorporate a change in the train running order at the merge of the line. Currently, a one-over-two rule is employed and has been previously modeled for the divergence and merge of the line. We modify the model to implement a first-in, first-out (FIFO) rule at the merge, enabling the first arriving train to enter the central section. Similar to Chapter 3, we utilize numerical simulations to derive our results. Initially, we construct the fundamental diagram of the line in the steady state of the train dynamics. Subsequently, with two potential disturbances on the line, we investigate how the change in rule at the convergence helps mitigate the impact of these disruptions.

Dans cette thèse, nous présentons un modèle mathématique à événements discrets pour les lignes de transport en commun qui fonctionnent avec des missions semidirectes et pour les lignes comportant une fourche. Le modèle est basé sur le système de signalisation utilisé dans le métro de Paris. La ligne est divisée en segments correspondant aux cantons réels de la ligne. La dynamique des trains dans notre modèle est basée sur deux contraintes qui ont été développées dans des études précédentes [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF][START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF]. La première contrainte établit une limite inférieure pour les temps de trajet et d'arrêt des trains. La deuxième contrainte fixe un temps de séparation minimum entre les trains successifs pour éviter tout risque de collision. Dans la mesure du possible, nous formulons les modèles de manière linéaire en utilisant l'algèbre max-plus. Cette algèbre nous permet de dériver des diagrammes de phase (ou diagrammes fondamentaux) de manière analytique et d'interpréter la physiques du trafic.

Dans le Chapter 3, basé sur le travail de [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF], nous développons deux modèles pour des missions semi-directes. Nous désignons des stations spécifiques prédéterminées où nous imposons qu'un train sur deux saute ces stations pour augmenter sa vitesse. Le premier modèle restreint garantit que chaque origine-destination peut être atteinte sans que les passagers aient besoin de changer de train sur la ligne. Dans le deuxième modèle, nous relâchons cette contrainte et le modèle non restreint exige seulement qu'un train s'arrêtant à une station pouvant être sautée soit suivi d'un train qui saute cette station. À l'aide de simulations numériques, nous étudions l'état stationnaire de la dynamique des trains. Nos résultats sont représentés dans des diagrammes fondamentaux qui illustrent la fréquence de la ligne avec et sans la politique de sauts en fonction du nombre de trains en circulation. Nous comparons ces fréquences, évaluons les avantages potentiels pour l'opérateur, analysons les temps de trajet des passagers et calculons les économies ou les pertes résultantes qu'ils peuvent connaître.

Dans les chapitres 4 et A, nous étendons notre modèle développé dans le chapitre précédent pour incorporer, en tant qu'entrée du modèle, les missions définis par l'opérateur (c'est-à-dire les stations où un train s'arrêtera et celles qu'il doit sauter). De plus, en adaptant notre modèle, nous montrons qu'il peut être écrit de manière linéaire dans l'algèbre max-plus. Grâce à la formulation algébrique, nous caractérisons les conditions sous lesquelles la dynamique des trains admet un régime stationnaire et montrons que le taux de croissance moyen asymptotique de la dynamique des trains coïncide avec l'unique valeur propre max-plus de la matrice décrivant la dynamique des trains. Le taux de croissance moyen asymptotique de la dynamique des trains est interprété ici comme l'intervalle moyen asymptotique des trains. Nous appliquons notre modèle à la ligne 1 du métro parisien et en dérivons analytiquement son diagramme de phase. Nous démontrons l'existence de trois phases distinctes : écoulement libre, capacité et congestion. Nous montrons égalei ii ment que la phase d'écoulement libre est linéaire par morceaux : lorsque le nombre de trains devient important, les trains interagissent, limitant l'augmentation de la fréquence des trains. Nous analysons également l'impact du choix des stations pouvant être sautées, en tenant compte de leur nombre ou des schémas d'arrêt définis par l'opérateur.

Le chapitre précédent modélise principalement la perspective de l'opérateur concernant la politique de sauts. Le Chapter 5, en incluant les taux d'arrivée des passagers aux stations et leurs origines-destinations, permet une mesure précise de l'impact de la politique de sauts sur les passagers. Nous construisons un modèle pour les temps d'arrêt des trains basé sur la demande et les missions définis par l'opérateur. De la même manière que dans le chapitre précédent, nous démontrons que le modèle peut être formulé de manière linéaire en utilisant l'algèbre max-plus. Nous établissons l'existence d'un état stationnaire pour la dynamique des trains et montrons que le taux de croissance moyen de la dynamique des trains correspond à l'intervalle moyen des trains. Par conséquent, nous pouvons construire un diagramme de phase pour la ligne en fonction de la demande des passagers. Nous analysons initialement l'effet de la variation du niveau de demande pour un profil de demande fixe. Ensuite, nous comparons deux profils de demande et évaluons les circonstances dans lesquelles la mise en oeuvre d'une politique de sauts bénéficie aux passagers.

Enfin, dans le Chapter 6, nous nous concentrons sur une ligne comportant un croisement. Une gestion efficace de la convergence de la ligne est essentielle pour assurer un écoulement fluide du trafic sur de telles lignes. À partir des résultats de [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF], nous adaptons le modèle pour incorporer un changement dans l'ordre de passage des trains au niveau de la fusion de la ligne. Actuellement, une règle de type un-sur-deux est utilisée et a été précédemment modélisée pour la divergence et la convergence de la ligne. Nous modifions le modèle pour mettre en oeuvre une règle de type "premier arrivé, premier sorti" (FIFO) au niveau de la convergence, permettant au premier train arrivé d'entrer dans la section centrale. De manière similaire au Chapter 3, nous utilisons des simulations numériques pour obtenir nos résultats. Initialement, nous construisons le diagramme fondamental de la ligne à l'état stationnaire de la dynamique des trains. Ensuite, avec deux perturbations potentielles sur la ligne, nous étudions comment le changement de règle à la convergence aide à atténuer l'impact de ces perturbations. and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 . . 84 5.12 Comparison of the analytical average waiting time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 2 . . 85

List of Figures

List of Tables

Chapter 1 Introduction

General introduction

Urban public transportation management is contradictory. While increasing ridership should increase revenue and improve service quality, exceeding a certain passenger threshold leads to decreased passenger satisfaction and lower service quality provided by the operator. Overcrowding causes delays and disruptions in the lines, further diminishing service quality. Dissatisfied users then turn to other modes of transportation, such as private cars, that may have a significant carbon footprint and generate number of externalities such as road accidents and noise. In 1960, the global population living in cities was around 36%. In 2021, this percentage increased to 60%. By 2050, it is projected to reach 70%. Moreover, cities account for nearly two-thirds of global energy consumption and produce over 70% of global greenhouse gas emissions. Organizing efficient and low-emission public transportation is necessary to mitigate cities' impact on these emissions and make passenger journeys as comfortable as possible. Delivering sufficient and high-quality service is crucial to provide an attractive alternative to private vehicles. In France, 80% of the population lives in urban areas, which is over 20% more than in 1960. Greater Paris is no exception to the rule. Between 1968 and 2020, 500,000 more people joined the region. Over the same period, many new transport lines have been opened to enable residents to travel by public transport. Since 1976, the number of trips made by car has decreased, especially since the 2000s, while at the same time, the number of trips made by public transport has increased. In the coming years, the network will continue to be extended, with the creation of new metro and tramway lines or the extension of existing lines [START_REF] Apur | Évolution des mobilités dans le Grand Paris Tendances historiques, évolutions en cours et émergentes[END_REF]. Moreover, the French government has announced its intention to develop a heavy rail network in the country's ten largest cities in order to increase the share of public transport in these cities [START_REF] Emmanuel Macron | annonce l'objectif de « développer un réseau de RER dans les dix principales villes françaises[END_REF].

In Greater Paris and in the rest of the world, metro lines are the backbone of a city's network (see Figure 1.1 for the network maps in Paris). The International Association of Public Transport (UITP) gives the following definition [68]: "Metros are very often the fastest and most energy-efficient way to get around a city. They run on electricity and can easily be powered by renewable energy sources. With lines circulating on segregated infrastructure, metros avoid traffic jams and can transport large amounts of people, making them the backbone of many cities." Thanks to its independence from other modes of transport, the metro can operate at high speed and frequency. Signaling systems have been developed to enable drivers to maintain 2 high speeds even when visibility is limited. When the lateral signaling is open (i.e., signals are green), safety is guaranteed, and the driver can proceed without fear of being too close to the preceding train. Depending on their level of recentness, there are different types of signaling systems that allow for reduced spacing between trains, as well as different driving modes and four grades of automation (GOA). GOA 1 includes speed control to prevent over-speeding. With GOA 2, the driver is always in the cabin and responsible for safety, but the train's operation is automatic. Finally, everything is fully automatic for GOA 3 and 4, with personnel on board in case of issues for grade 3 and no personnel for GOA 4. Most Paris metro lines operate at automation GOA 2, while two (and soon three) have reached grade 4 and are fully automated. However, all lines have a fixed block signaling system. Signals are placed along the line to ensure passenger safety.

After a gap caused by the COVID pandemic, public transport ridership has returned to pre-pandemic levels. In addition, public policy is seeking to attract more passengers to public transport in order to reduce pollution and greenhouse gas emissions in major cities. Although major network extension projects are underway, they will not alleviate the load on existing lines, which are already often saturated. The construction of new lines is not only very costly but often difficult due to the large number of existing construction underground. Therefore, it is necessary to adapt existing infrastructure to improve network capacity and passenger comfort.

[RQ1] What solutions can be envisaged to increase the capacity and comfort of existing lines?

RATP

The RATP (Régie Autonome des Transports Parisiens) Group is the third largest operator in the world [START_REF]Trafic annuel entrant par station du réseau ferré[END_REF]. Historically, it has been the operator of the Paris region's urban transportation, including the metro, bus, and tramway systems. The group is now present on all five continents and in 780 cities worldwide. It operates all types of transportation, from the metro to cable cars.

In the Paris region, RATP operates 16 metro lines, a portion of 2 suburban lines, the majority of the tramways, and all inner Paris and near-suburban bus lines (Figure 1.1). This thesis focuses on rail transportation modes without interaction with other modes of transport, i.e., the mass-transit lines 1 . The metro was initially designed to transport passengers within the city. Although some extensions have allowed it to serve the immediate suburbs, most stations (more than 80%) are within inner Paris.

The operation of metro lines is based on a timetable defined by the Métro, Transports et Services (MTS) department. However, in order to create the timetable, the MTS department requires operating data for the lines based on their characteristics and those of the rolling stock. These characteristics are calculated within the Génie Ferroviaire Unit (GEF), particularly in the MATYS team. For each metro line, and depending on the rolling stock, internal software calculates the train run times for each section of the line. The MATYS unit is also responsible for traffic simulation on these lines. Simulations are carried out using the OpenTrack software. The software allows for simulating a predefined timetable based on the line and rolling stock characteristics. The team also develops APIs for the software to add the necessary functionalities for their simulations. The software is used to simulate disturbances on one of the network lines and calculate the effects of these disturbances. The accuracy of the software allows for results close to what happens in reality. Some solutions are evaluated by the software to verify their long-term feasibility. However, the precision of the simulator requires a relatively long time to perform the calculations, which does not allow the operator to use it in the case of unexpected disturbances. Moreover, each disturbance has its own particularities, and a large number of simulations would be necessary to cover these different cases.

By making assumptions about the functioning of a metro line, it can be simplified in order to represent and analyze it mathematically. Using a dynamic model, traffic simulations can be performed more quickly than with a more complex simulator, allowing the model to be used in real-time to compare multiple situations. Finally, the mathematical analysis provides an additional understanding of the physical phenomena occurring on the line, which pure simulation does not allow. However, due to the loss of precision resulting from assumptions, the simulations may deviate from the real world. The trade-off between these two types of simulations must be made cautiously.

[RQ2] How to develop a model that allows simulating quickly train movement and have physical interpretations of the traffic ?

Skip-stop policies

In 2009, an inhabitant of Greater Washington mentioned how a skip-stop policy could improve the passenger experience on a specific line of the Washington network [START_REF] Offutt | Getting more out of Metro with skip-stop[END_REF]. His empirical study looked at the benefits and drawbacks of such a policy depending on the origin and destination of the line's riders. He mentioned the examples of Philadelphia and New York, where some metro lines operate with a skip-stop policy. Around the world, this policy has been implemented successfully in multiple cities such as Santiago de Chile, some cities in the USA, China, and some suburban lines in Paris. The principles of skip-stop policies are simple. Some stations, usually the less crowded, are skipped by some trains to increase their speed and improve the passengers' service level. However, the skip-stop policy can be distinguished into two categories: first, the express/local trains. As in New York City, the local train stops at all stations of the line, whereas the express only stops at selected stations. In this first case, there exist siding tracks for the express trains, allowing them to overtake local ones and thus not be slowed down. However, this express/local functioning necessitates siding tracks, which is often not the case on existing lines, and is difficult to build due to the high cost of the construction and the lack of space in the underground of cities. The second functioning, named in this thesis "skip-stop policy", applies to lines without siding tracks, and trains cannot overtake each other. For this skip-stop policy, the operator defines two types of trains, A and B. Especially for these trains, the operator defines a service A or B. A service is defined as the stopping pattern of the trains or the stations it must stop at the stations it must skip. For each lap around the line, a train performs a specific service. With these A/B services, there are three types of stations on the line: The stations designated as A and B are referred to as skippable stations. Two main service patterns are identified: with the alternating service pattern, skippable stations alternate between A and B stations, as shown in Figure 1.2a. In Figure 1.2b, the train operator has the freedom to choose which service stops at a skippable station. Thus, this pattern makes consecutive A or B stations possible.

Motivation & Objectives

The Application Cases

In this thesis, several lines of the network are considered to perform the applications of the models developed in Chapters 3 to 6. For the skip-stop policy, it refers to Paris metro line 1, and for the line with a junction, it refers to Paris metro line 13. Paris metro line 1 is the oldest and busiest line of the network. In order to increase its capacity and regularity, the line was fully automated in 2013 [50]. The line consists of 25 stations connecting the city's east and west sides, passing through several business districts, major tourist attractions, and some of the busiest stations in the network. Paris metro line 1 is represented in Figure 1.3, and its main characteristics are provided in Table 1.1. As for Paris metro line 13, it is one of the two lines in the metro network with a junction. It connects the northwest suburbs to the south of Paris, passing through the city center and certain business districts of the city. It is also one of the busiest lines in the network and has long been the only line connecting the inner suburbs to the city center. Due to its high ridership, the line has long suffered from overcrowding, prompting the authorities and RATP to modernize its infrastructure. The implemented actions have helped alleviate some saturation issues. However, in order to further increase the line's capacity and improve passenger comfort, similar to Paris metro lines 1 and 4, the line will be fully automated in the coming years. There are 32 stations on the line, 18 on the central section, 8 on the Saint-Denis branch, and 6 on the branch heading towards Asnières, see Figure 1

Motivations

The work carried out during this thesis was done in collaboration with the RATP group. The company, a major player in public transportation worldwide, seeks to innovate to improve how it operates existing lines and the comfort of its users. The diversity of transportation modes it operates, and the various possibilities of operation require the company to continuously develop its knowledge.

In the Greater Paris network, only some parts of suburban lines are operated with skip-stop services. However, in the face of existing network saturation problems, particularly on certain metro lines, exploring new ways of operating the lines can help find solutions to these saturation problems. Additionally, the modernization of the network also opens up new possibilities in disturbance management. On Paris metro line 13, the convergence point is one of the critical points of the line, and its management is crucial for traffic flow. With automation, operational constraints related to drivers will no longer need to be considered, and the regulation rules that can be implemented could be simplified.

From a scientific point of view, there are also multiple motivations. The complexity of metro line operations often makes it difficult to develop sufficiently simple mathematical models for in-depth analysis. Furthermore, due to their precision in faithfully reproducing train traffic on a line, existing simulation tools used in the company are computationally heavy and cannot be used instantaneously in the event of disturbances.

Objectives

This thesis can be divided into two parts. The first part focuses on the skip-stop policy, while the second part explores a line with a junction, specifically the train's running order at the convergence point of the line.

The objective of the first part is twofold. First, it is necessary to develop a mathematical model that represents the operation of a line when operated with a skip-stop policy. This model reproduces the dynamics of the trains and allows simulation of their movement on the line under defined traffic conditions. Secondly, it is shown that the model can be written linearly in the Max-plus algebra. This will enable us to analyze the results obtained using the linearity of the model, leading to a better understanding of the physics of traffic and the phenomena that occur on a metro line with a skip-stop policy. The operator seeks to determine the impact on passengers and whether implementing such a policy is beneficial for him and the passengers. We can compare the operation of a line with all-stop and skipstop policies and provide the operator with the necessary information about the quantified gains and losses resulting from the change in operating mode.

Operating a metro line in Paris or anywhere else in the world is often subject to numerous disturbances. These disturbances can take various forms. They can be minor, where their impact does not jeopardize the operator-defined timetable. They can be significant enough for the dispatcher to intervene in order to ensure the smooth flow of the line. Lastly, major disruptions require closing a section of the line or interrupting traffic for an extended period. In this last case, the entire operating program needs to be reconsidered, and the dispatchers try to maintain a minimum level of traffic despite these highly degraded situations. In the second case, disruptions affect traffic flow but do not jeopardize the operating program.

The role of dispatchers is crucial in minimizing the impact of these disruptions. This is particularly true on a line with a junction where the management of the convergence point is crucial. Exploring new ways to operate the convergence point can help dispatchers to better assess certain solutions when a disruption occurs on one of the line branches.

Contributions

This thesis presents a mathematical contribution to the modeling of metro lines and the interpretation of the physics of traffic. Our models take into account the main parameters governing the operation of a mass-transit line, enabling us to analyze train dynamics.

The dynamics are based on two constraints, which reproduce the operation in real metro lines. The first constraint sets a lower bound on the run times to ensure that trains adhere to speed limits determined by the track's configuration. The second constraint ensures that a train has completely exited a block before the next train can enter it; it reproduces the red signal state on metro lines. By calculating the departure times of trains at all signals along the line, our model operates as a discrete-event system. Unlike existing literature that primarily focuses on trains as primary parameters, our model considers the count of departures.

This approach enables us to effectively model skip-stop policies, which determine whether a train should stop or skip certain stations based on the departure count. Using simple rules, we develop a simulation model in the initial phase of our work to determine the average train frequency of a line implementing a two-service skip-stop policy. We quantify the benefits of this policy in terms of frequency and passenger satisfaction.

The train dynamics we develop are nonlinear, mainly due to the presence of a maximum function. Through the use of max-plus algebra, we demonstrate the possibility of linearly rewriting the dynamics in matrix form within this algebraic framework. Additionally, we establish that the only non-zero eigenvalue of the matrix corresponds to the average train-time headway of the line. With this result, we analytically derive the asymptotic regime of the dynamic system, which models the train dynamics for a line operating under a skip-stop policy. Furthermore, we interpret this regime in the context of traffic phases. The fundamental traffic diagram, representing the average train frequency as a function of the number of trains running on the line, is crucial for understanding mass transit operations. Notably, these contributions are entirely novel to the best of our knowledge.

Our research provides valuable insights for metro line operators. We demonstrate that the parity of the number of trains influences the evolution of train frequency and provide an interpretation of the derived fundamental diagram of the line. Moreover, we propose methods to evaluate the gains or losses from the operator's perspective directly in terms of train frequency. We extend these findings to consider passengers' arrival rates in our model and introduce multiple indicators to measure their perception of the skip-stop policy, such as waiting and travel time, as well as their comfort compared to an all-stop policy.

In the final part of our work, we explore new approaches to operating a line with a junction. Our mathematical formulation enables the consideration of a First-In-First-Out (FIFO) rule for the merge of the line. We analyze the steady state of the train dynamics and put forth several conjectures. Furthermore, we demonstrate how our formulation and model can be employed in disrupted situations. The model facilitates quick comparisons between different scenarios and can assist operators in effectively managing unexpected disturbances on the line.

Structure of the Manuscript

The manuscript is divided into six chapters. In Chapter 2 Background on masstransit research, we review publications related to this thesis's topic. Four main research areas are addressed, focusing on key articles in the field of public transportation. The subsequent part of the review focuses on articles that study the impact of a skip-stop policy on a mass-transit line and publications that concentrate on lines with junctions. Lastly, the final section mentions the key articles related to the max-plus algebra that we utilize in our thesis.

Chapter 3, Modeling & Simulating a Skip-Stop Policy, presents the modeling approach and initial results of the skip-stop policy. In this chapter, we develop the train dynamics on Paris metro line 1 using two different models. The first model ensures that each origin-destination is possible without requiring any connections on the line. The second model relaxes this constraint and only ensures that at every skippable station, one out of every two trains stops while the other skips the station.

In Chapter 4 Max-plus Modeling of a Two Services Skip-Stop Policy, we expand on the train dynamics from the previous chapter. Firstly, we include the services defined by the operator as input to the model. There are two alternating services on the line, and for each service, the operator specifies the stations where a train performing that service stops and the stations it should skip. By using the max-plus algebra, we can linearly represent the model, and thus, leveraging the properties of this algebra, we derive analytical formulas that provide the train time headway and frequency. We perform several analyses based on the number of skippable stations or the services that can be defined.

Chapter 5, Effect of the Passengers on a Two-Service Skip-Stop Policy, incorporates the passenger dimension into our model. On the one hand, we recalculate the train dwell times at each station based on the origin-destination matrix provided by the operator. With the implementation of skip-stop services, some passengers must choose a train that performs a specific service. We demonstrate how these passengers are accounted for in the calculation of dwell times. We formulate the train dynamics using standard algebra, and then, by using the max-plus algebra, we can linearly represent the dynamics. Similar to the previous chapter, we derive the frequency and average time headway. Furthermore, we develop indicators that measure the impact of the skip-stop policy on the line's passengers.

In Chapter 6 Impact of a FIFO Rule on a Line with a Junction, we focus on a line with a junction. Specifically, we compare different train sequencing rules at the line's convergence point. Through simulations, we examine the line frequency with a first-in-first-out (FIFO) rule at the steady state of the line. The line currently operates with a one-over-two rule, sometimes even during disturbances. We also investigate the effects of the FIFO rule when a disruption occurs on one of the branches.

Lastly, in Chapter 7 Conclusion, we review the main results we obtained in each chapter, and we also indicate what are the next steps of this thesis. We show the limitation of our work and how these limitations could be tackled to further develop our model.

Chapter 2

Background on Mass-Transit Research

This chapter provides a literature review of the existing work on four subjects. First, we give an overview of the general research on mass transit. Then, we focus our review papers focusing on the modeling and effect of skip-stop policies and papers related to line with junctions. As we use max-plus algebra, we give our resources on this subject. We give the main papers for the theoretical work and give also papers using max-plus algebra applied to transportation.

General Mass-Transit Research

Control strategies for metro or mass-transit lines are widely studied to improve line robustness and increase passenger comfort. Indeed, well-controlled lines increase the attractiveness for passengers. One of the key indicators of the performance of a mass transit line is the harmonization of train headway. It is the subject of many articles. [START_REF] Van Breusegem | Traffic modeling and state feedback control for metro lines[END_REF] first developed a control strategy to harmonize train headways. Similarly, [START_REF] Fernandez | Predictive Traffic Regulation for Metro Loop Lines Based on Quadratic Programming[END_REF] proposed a predictive traffic control model for loop metro lines. The model was then extended to have dwell time dependent on train headway and passenger arrival rate [START_REF] Martínez | Statistical dwell time model for metro lines[END_REF].

However, the arrival rate of passengers at the stations may not be consistent, [START_REF] Li | Robust Model Predictive Control for Train Regulation in Underground Railway Transportation[END_REF] consider an uncertain passenger arrival flow. In [START_REF] Li | Joint optimal train regulation and passenger flow control strategy for high-frequency metro lines[END_REF], schedule and headway deviations are minimized by combining dynamic train control and passenger flow control. Finally, the same authors develop a dynamic optimal control model to determine the automatic train control strategy to improve punctuality and regularity under frequent minor disruptions [START_REF] Li | Efficient Real-Time Control Design for Automatic Train Regulation of Metro Loop Lines[END_REF]. We also mention [START_REF] Yuan | Passenger flow control strategies for urban rail transit networks[END_REF], who developed passenger flow control strategies to decrease passenger waiting time and relieve the number of passengers stocked in stations. [START_REF] Moaveni | Metro Traffic Modeling and Regulation in Loop Lines Using a Robust Model Predictive Controller to Improve Passenger Satisfaction[END_REF] minimize the headway deviation and keep it as close as possible to the nominal headway. In addition, the authors develop a linear robust model predictive controller to compensate for disturbances and regulate traffic in the presence of operational constraints.

Since many papers deal with rail traffic robustness, some interesting reviews of the existing models are available: [START_REF] Cordeau | A Survey of Optimization Models for Train Routing and Scheduling[END_REF] studies train routing and scheduling models. In contrast, [START_REF] Lusby | A survey on robustness in railway planning[END_REF] focuses on scheduling stability. Similarly, in [START_REF] Goverde | Punctuality of railway operations and timetable stability analysis[END_REF], the stability and punctuality of rail operations are analyzed. Finally, [START_REF] Corman | A Review of Online Dynamic Models and Algorithms for Railway Traffic Management[END_REF] and [START_REF] Cacchiani | An overview of recovery models and algorithms for real-time railway rescheduling[END_REF] propose reviewing

Fundamental Diagram

The notion of a fundamental traffic flow diagram is an old one. [START_REF] Pipes | Car Following Models and the Fundamental Diagram of Road Traffic[END_REF] There are three characteristic points; point k j corresponds to the maximum vehicle density on the road. The k m point gives the road's capacity: when the vehicle density exceeds this point, the road enters a phase of congestion, which reduces the flow of vehicles. Beforehand, this is the free-flow phase. The last characteristic point, k c , shows that in the free-flow phase, there is a density beyond which the average vehicle speed begins to decrease. Vehicle speed is represented by the dashed blue curve. The existence of such a diagram has been detected empirically and described mathematically [START_REF] Farhi | The traffic phases of road networks[END_REF][START_REF] Farhi | Modélisation Minplus et Commande du Trafic de Villes Régulières[END_REF]. Other studies have extended the concept to the scale of a network: the macroscopic fundamental diagram (MFD). Its existence was examined in [START_REF] Geroliminis | Existence of Urban-Scale Macroscopic Fundamental Diagrams: Some Experimental Findings[END_REF], the analytical approximation in [START_REF] Daganzo | An Analytical Approximation for the Macroscopic Fundamental Diagram of Urban Traffic[END_REF], and the properties of a well-defined diagram in [START_REF] Geroliminis | Properties of a Well-Defined Macroscopic Fundamental Diagram for Urban Traffic[END_REF]. The MFD shows that adjacent roads share the same properties and a similar flow of vehicles. MFDs are very useful for traffic controllers to implement better control strategies to reduce congestion in the road network.

However, for rail lines, the fundamental diagrams are still in their early stages. There are many differences between road and rail networks. While roads can be considered continuous systems, rail networks must be considered discrete because of the signaling system. The fixed block signaling system divides the line into multiple "blocks" and limits the number of trains on the line. To ensure safety on the railroad line, a maximum of one train is allowed on each block between two signals.

[14] first collected beacon data on two very high-frequency lines in the Paris region. Using the data collected, they represent the flow of vehicles as a function of the number of trains that have passed over the beacon. They then adjust their data to show three different traffic regimes: uncongested, congested, and totally congested. Based on a microscopic model, [START_REF] Seo | Fundamental Diagram of Urban Rail Transit Considering Train-Passenger Interaction[END_REF] are able to derive a fundamental diagram of a rail transit line. The FD depicted in Figure 2.2 shows the relationship between train flow, train density, and passenger flow. Figure 2.3 shows the difference between the two signaling systems. With the moving block signaling system, the safety zone is defined by the rear of the preceding train rather than by the start of the next occupied block. This allows trains to run closer together while maintaining safety and increases overall line capacity. [START_REF] Diaz De Rivera | Illustrating the Implications of Moving Blocks on Railway Traffic Flow Behavior with Fundamental Diagrams[END_REF] explores the effect of moving blocks on the fundamental diagram of a line. They compare different spacing levels for a fixed block and a moving-block signal system. They show that the movable block does indeed increase line capacity and that the train density above which trains must slow down to ensure safety also increases.

BACKGROUND ON SKIP-STOP POLICY

As with road networks, it is also possible to study the fundamental diagram at a macroscopic level. [START_REF] Corman | Macroscopic Fundamental Diagrams for Train Operations -Are We There Yet?[END_REF] first explores the advantages of studying train traffic at a macroscopic level with a moving-block signaling system. However, for railway lines and networks, fundamental diagrams are still in their early phase. We aim to extend the knowledge of the rail fundamental diagram with our research.

Background on Skip-Stop Policy

As the demand for urban transportation systems, especially urban rail transit, continues to rise, operators and researchers are exploring innovative ways to enhance the efficiency of existing lines. One solution gaining popularity is the implementation of skip-stop policies. While this may make it challenging for passengers to determine their train, and some origin-destination pairs may require multiple trains, it has the potential to increase train speed, reduce total passenger travel and waiting time, and achieve objectives with fewer trains on the line [START_REF] Vukan | Urban transit: operations, planning and economics[END_REF].

Skip-stop policies can be implemented in both existing and new lines of public transport. [START_REF] Freyss | Continuous approximation for skip-stop operation in rail transit[END_REF] investigate the impact of station density on the objective function, considering passenger and operating costs, to determine the optimal density of AB stations based on line parameters such as line length or the number of trains. They describe skip-stop policies with continuous parameters like station density and recommend their use for long lines with high density and frequency.

Other studies expand on this work to minimize the generalized cost of passenger travel time and operator cost by employing more general skip-stop policies. [START_REF] Mei | Planning skip-stop transit service under heterogeneous demands[END_REF] perform realistic analyses by eliminating the initial assumption of spatially homogeneous demands. They compare the examined policies with all-stop policies and quantify the resulting savings. [START_REF] Fan | Planning skip-stop services with schedule coordination[END_REF] use a continuous approximation model for bus and train public transport services, incorporating three demand models and 14 operational schemes. They provide the percentage of advantages associated with skip-stop operation and additional savings from schedule coordination.

Furthermore, [START_REF] Cheng | Skip-stop operation plan for urban rail transit considering bounded rationality of passengers[END_REF] propose a model focusing on maximizing time and congestion cost savings. They utilize prospect theory to describe optimization objectives and select stop plans based on the calculated Pareto solution set. The study demonstrates a significant improvement in passenger travel time and comfort, assuming a line that allows overtaking. Similarly, [START_REF] Lee | Optimizing Skip-Stop Rail Transit Stopping Strategy using a Genetic Algorithm[END_REF] investigate different objective functions under various constraints to avoid train collisions. Their findings show that reducing vehicle travel time is possible by eliminating stations, despite increased waiting, transfer, and access times.

While the skip-stop policy models discussed above mainly concentrate on designing new lines, implementing this policy on existing lines requires considering actual constraints, such as station distance, line length, and passenger flow. [START_REF] Altazin | Rescheduling through stop-skipping in dense railway systems[END_REF] propose a disruption management model that skips stops to minimize recovery time during disturbances, developing an integer linear programming model that considers passenger waiting time.

To further optimize skip-stop patterns in specific situations, [START_REF] Yuan | An integrated optimization approach for passenger flow control strategy and metro train scheduling considering skip-stop patterns in special situations[END_REF] formulate a mixed integer programming model that minimizes the unused capacity of trains and the total number of waiting passengers at platforms. This approach allows for an increase in the average boarding rate of all stations, a reduction in passenger waiting behaviors, and a decrease in the average travel time of passengers.

Researchers have also explored the application of skip-stop policies in the regular operation of transportation systems. [START_REF] Cacchiani | An overview of recovery models and algorithms for real-time railway rescheduling[END_REF] develop mixed-integer linear programming models to plan stop patterns for high-speed lines, demonstrating a significant reduction in unsatisfied demand or insufficient capacity compared to the current case. Similarly, [START_REF] Niu | Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints[END_REF] presents a train schedule optimization model incorporating passenger demand data for short-term planning applications in high-speed lines.

[37] address the collaborative optimization of timetable scheduling, passenger flow control, and skip-stop patterns in a metro line. Their optimized train timetable effectively eases congestion at stations and improves the safety and service quality of the metro system, providing valuable practical insights into the solution and model robustness trade-off.

The objective in urban rail transport lines is often to reduce the total travel time while considering practical constraints using smart card data [START_REF] Hak | A Travel Behavior-Based Skip-Stop Strategy Considering Train Choice Behaviors Based on Smartcard Data[END_REF]. Various methods have been proposed to find the optimal arrangement of skip-stops. [START_REF] Ehab | Minimizing passenger travel time in URT system adopting skip-stop strategy[END_REF] linearize a non-linear integer mathematical model to minimize passenger travel time, resulting in a reduction of about 10%. On the other hand, [START_REF] Salama | Maximizing number of direct trips for a skip-stop policy in metro systems[END_REF] achieve a 16% reduction in travel time while sacrificing only 11% of direct trips using a binary quadratic programming model. [START_REF] Cao | Estimation method for a skipstop operation strategy for urban rail transit in China[END_REF] propose a model that minimizes the total waiting and travel time of passengers as well as the travel time of trains. Additionally, [START_REF] Cao | Robust and optimized urban rail timetabling using a marshaling plan and skip-stop operation[END_REF] incorporate a marshaling plan in the urban public transport schedule to improve robustness and reduce the total cost associated with passengers, operations, and reliability.

[66] quantify time savings resulting from implementing the skip-stop policy on a Seoul subway line during peak and off-peak hours. They conduct numerical simulations considering travel time, waiting time, and total system travel time for different scenarios and criteria. The results indicate significant reductions in total waiting or travel times. Similarly, [START_REF] Farrando | Traffic modeling and simulation on a mass transit line with skip-stop policy[END_REF] employ numerical simulation to estimate line frequency based on the number of trains running and compare passenger travel time with and without the skip-stop policy.

By exploring and applying skip-stop policies, operators and researchers aim to enhance the efficiency of urban transportation systems, improve passenger experience, and optimize resource utilization in existing and new lines.

Yet, the skip-stop policy is mainly tackled through optimization. The range of optimization criteria is broad, from passengers' travel time to optimal station density in a corridor. The latter case is interesting for lines under design, which is outside the scope of our work. Optimizing an existing metro line operated with a skip-stop policy requires the consideration of all its operating constraints. Indeed, all the line characteristics are fixed by topological constraints, and the station ridership levels are already given. For operators, skip-stop optimization can be done to select the train-stopping pattern. By comparing lines operated with skip-stop and all-stop policies, it is possible to evaluate the gains in terms of train frequency, passenger waiting time, or any other criteria defined in the optimization model. However, the solution might not be optimal if the problem is solved with heuristics. Moreover, it might be challenging to interpret the optimization results, especially if the number of decision variables is high. Finally, there is a gap in the cited papers explaining the physical phenomena and the train interaction.

BACKGROUND ON LINE WITH A JUNCTION

Background on Line with a Junction

In many networks worldwide, numerous lines have a junction. These junctions often occur in the city center or the busiest sections of the network, where trains from multiple directions converge. Such convergence points can involve multiple lines sharing tracks for a portion of their routes, as in Munich or Madrid. Alternatively, they can consist of a single line with multiple branches, like the Elizabeth line in London, Paris metro line 13, or RER lines A and B. These merging points or convergence areas are crucial for operators and dispatchers. Despite the prevalence of lines sharing tracks or featuring junctions, the existing literature on this topic remains relatively limited.

[35] developed a traffic controller for junctions aimed at minimizing the overall weighted delay for trains. They studied an event-based model that accounted for constraints imposed by the fixed-block signaling system. Using dynamic programming, they optimized the model and demonstrated cost improvements under their modeling assumptions. Another approach to achieving the same objective was presented by [START_REF] Ho | Railway Junction Conflict Resolution by Genetic Algorithm[END_REF], who utilized a simple genetic algorithm. Their algorithm found a near-optimal cost while reducing the computational burden. [START_REF] Rodriguez | A Constraint Programming Model for Real-Time Train Scheduling at Junctions[END_REF] introduced a constraint programming model for real-time train scheduling at junctions. Their work tackled the joint problem of resource allocation and activity scheduling, considering the influence of the signaling system on traffic management decisions. This approach enhanced traffic operations at a computational cost compatible with real-time management. The model was applied to a junction where high-speed, inter-city, and freight trains interacted. [START_REF] Törnquist | N-Tracked Railway Traffic Re-Scheduling during Disturbances[END_REF] presented an optimization approach to the problem of rescheduling railway traffic in an N-tracked network when disruptions occur. They developed multiple strategies allowing for track swapping, order changing, or both. Their approach employed a Mixed-Integer Linear Programming model applied to the south network of Sweden. Achieving results within a reasonable computation time required balancing model complexity and precision. [START_REF] Chen | Real-Time Train Rescheduling in Junction Areas[END_REF][START_REF] Chen | Modeling and Solving Real-Time Train Rescheduling Problems in Railway Bottleneck Sections[END_REF] proposed a decision support methodology for real-time train rescheduling in junction areas to optimize the weighted average delay. Their model addressed rescheduling problems at junctions and compared algorithm performance with the First-In-First-Out (FIFO) strategy. They examined different scenarios involving long or short delays and demonstrated good convergence performance and superior results compared to the FIFO strategy when applied to the Thameslink case in London. [START_REF] Eaton | Ant Colony Optimization for Simulated Dynamic Multi-Objective Railway Junction Rescheduling[END_REF] employed ant colony optimization algorithms to solve a simulated dynamic multi-objective railway rescheduling problem. In this dynamic problem, trains awaiting rescheduling were met with new arrivals in the system, while dispatchers aimed to optimize multiple objectives. Multiple algorithms were tested for various scenarios, evaluating their proximity to the optimum and computational costs. [START_REF] Galapitage | Optimal Real-Time Junction Scheduling for Trains with Connected Driver Advice Systems[END_REF] developed a system that combined realtime driving advice calculation with real-time junction scheduling to reduce delays at junctions. The system was simulated on a real network in the UK, enabling the detection of potential conflicts 20 minutes before their occurrence. This approach significantly reduced the number of delayed trains from 6.6 to 1.2 percent.

In [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF], the authors devised a discrete-event traffic model for a line with a junction. They derived the fundamental diagram of such a line, considering its central part and two branches. The study investigated eight different phases that revealed the impact of the number of trains and the difference in train numbers between the branches. These phases also highlighted the line's capacity and identified the threshold beyond which congestion occurs. In a subsequent work, [START_REF] Schanzenbächer | Comprehensive passenger demand-dependent traffic control on a metro line with a junction and a derivation of the traffic phases[END_REF] incorporated the passengers' arrival rate at stations into the model, leading to a derived fundamental diagram that accounted for the impact of passenger flows on line capacity. Finally, using the analytical results from the preceding paper, [START_REF] Schanzenbächer | Feedback Control for Metro Lines With a Junction[END_REF] optimized the running order of trains at the line's convergence point, carefully selecting the branch from which trains entered the central part based on traffic conditions.

Despite the significant number of lines with junctions worldwide, only a few articles treat this subject. However, it is essential to understand how the junctions work to improve the traffic on such lines. These lines often bring people from the suburbs to the city center. In addition, the comfort of public transport lines is essential to attract more passenger demand from other modes. Therefore, we are looking to fill this gap by studying these lines.

Max-plus Algebra

General Theory

The Max-plus algebra is the semi-ring (R max , ⊕, ⊗) where R max := R ∪ {-∞}, and ⊕ and ⊗ are the Max-plus sum and product defined respectively: a ⊕ b := max(a, b) and a⊗b := a+b, with a, b ∈ R∪{-∞}. The addition's zero element -∞ is denoted ε. The unity element 0 is denoted e. We have the same algebraic structure on the set of square matrices R n×n max , where the addition ⊕ is defined

(A ⊕ B) ij := A ij ⊕ B ij and (A ⊗ B) ij := k (A ik ⊗ B kj ).
The zero matrix is the matrix with null elements (equal to -∞). However, it is still denoted by ε. The unity matrix also denoted e, is diagonal, with all the diagonal elements equal to 0. As in the standard algebra, for a square matrix A ∈ R n×n max , we denote A k := A ⊗ A ⊗ . . . ⊗ A (k times). We then define A * := k≥0 A k . For a square matrix A ∈ R n×n max , we associate a directed graph denoted G(A) with n nodes, and whose arcs are defined as follows: an arc exists from node i to node j if A ji ̸ = ε. The value of A ji gives the weight of the arc going from i to j. Let us recall the following results [START_REF]Synchronization and Linearity: An Algebra for Discrete Event Systems[END_REF][START_REF] Gaubert | Theorie des systemes lineaires dans les dioides[END_REF].

A * = e ⊕ A ⊕ • • • ⊕ A n-1 .
Theorem 2.3. [4, Theorem 3.23] If A is irreducible, or equivalently if G(A) is strongly connected, there exists one and only one eigenvalue Λ (but possibly several eigenvectors). This eigenvalue is equal to the maximum cycle mean of the graph: Λ = max ρ |ρ| w /|ρ| l where ρ ranges over the set of cycles of G(A).

MAX-PLUS ALGEBRA

To have the uniqueness of the eigenvalue given by Theorem 2.3, the matrix A must be irreducible. If it is not the case, several eigenvalues may exist. The matrices we study in Chapters 4 and 5 are reducible, so we must find its other eigenvalues; see Appendix A for the complete analysis of the eigenvalues. In [START_REF] Gaubert | Theorie des systemes lineaires dans les dioides[END_REF], the results are extended to reducible matrices. Proposition

Application to Railway Traffic

The max-plus algebra is particularly suitable for discrete event systems. This algebra can be used in many different fields, from model predictive control to theoretical computer science. A review of the max-plus algebra in the history of discrete event systems can be found in [START_REF] Komenda | Max-plus Algebra in the History of Discrete Event Systems[END_REF]. It is also used in public transportation to model lines or timetables. In [START_REF] Rob | Railway Timetable Stability Analysis Using Max-plus System Theory[END_REF], an algebraic max-plus model allows studying the railway timetable stability and robustness to delays. Max-plus algebra can also be used for model predictive control [START_REF] De | Model predictive control for maxplus-linear discrete event systems[END_REF][START_REF] Van Den Boom | Modelling and control of discrete event systems using switching max-plus-linear systems[END_REF]. Our work also uses max-plus algebra modeling and theory to derive the traffic phases of a mass-transit line.

Our work is based on several papers using max-plus algebra. The first paper [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF] developed a discrete event model for a shuttle-operated line. A shuttle-operated line is a line without junctions and where trains run and stop at all stations of the line. In this paper, the authors derive the fundamental diagram of the line. It gives the average train frequency as a function of the number of trains running on the line, and it is represented in Figure 2.4. There exist three traffic phases in the fundamental 1. The free-flow phase, where the frequency increases with the number of trains.

2. The capacity phase gives the maximum frequency achievable on the line.

3. Finally, the congestion phase shows similar behavior as in road traffic. Trains interact with each other and are slowed down.

The analytical results of this paper can be found in Section 4.3, where we review the main theorem and propositions. This work has then been extended to a line with a junction [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF]. Similarly, a discrete event model is developed considering the characteristics of a line with a junction. The fundamental diagram, depicted in Figure 2 the number of trains on the branches of the line also impacts the line's frequency. There are 8 different phases on the line described in the paper. However, the phases are similar to those of Figure 2.4. In Section 6.2, we also review the analytical results of this paper.

The two previous papers consider the train dwell times as deterministic. The nominal times are fixed beforehand and not computed as a function of the passengers' arrival rates at stations. In [START_REF] Schanzenbächer | Demand-dependent supply control on a linear metro line of the RATP network[END_REF], the train's dwell time at stations can be extended to a certain limit to let passengers board. To offset this time extension, the train speed is increased, allowing them to stick to the nominal schedule. Finally, in [START_REF] Farhi | A discrete-event model of the train traffic on a linear metro line[END_REF], the possibility of increasing the train's speed is removed from the model; see Corollary 5.5 for the review of the analytical results.

Chapter 3 Modeling & Simulating a Skip-Stop Policy

This chapter is the first step in modeling and simulating skip-stop policies. We develop two mathematical models to explore the possible benefits of a skip-stop policy. In the first model, some stations are skipped by every other train, with the guarantee that each origin-destination pair is feasible without transfer. In the second model, this constraint is relaxed, and some ODs become impossible without transfer. We simulate the train dynamics based on a discrete event model to obtain the average train frequency and passengers' travel time. They are represented in the fundamental diagram, giving the headway or frequency as a function of the number of trains running on the line. We compare a skip-stop policy to an all-stop policy, i.e., all trains stop at all stations. We provide an overview of how this skip-stop policy can benefit the operator and passengers.

Modeling Approach for a Skip-Stop Policy

In this thesis, we present several traffic models for transit lines. An important part focuses on modeling skip-stop policies and their implementation's impact on the operator and passengers. All of our work on skip-stop policies is developed for shuttle lines. Shuttle lines are lines with two termini, and trains run from one terminus to another in both directions. Except for major disruptions, trains do not turn before the terminus. There is only one track in each direction, so overtaking is impossible. On Figure 3.1, we represent a shuttle line schematically. Our models use the existing fixed-block signaling system of the line. Throughout the line, signals are regularly arranged to maintain safety. They have two states: if the signal is green, a train can pass it and move on to the next. If the signal is red, a safety constraint forces the train to stop and wait for the signal to turn green. After each station, there is a signal that allows trains to leave the station, but there are also signals between stations. The vertical segments represent these signals on Figure 3.1. When the operator implements a skip-stop policy, certain trains must not stop at certain stations. These stations are called "skippable stations" and are represented by empty squares. The others, stations where all trains must stop, are called "mandatory stations" and are characterized by solid squares. In this chapter, we consider a period of 2 for skippable stations. We want a train that stops to alternate with a train that skips the station. Thus, every other train stops at skippable stations. We propose two traffic models: in the first one (see Section 3.1.5), we guarantee that the same train stops at all skippable stations. This constraint ensures that every OD pair of the line can be satisfied without transfer (i.e., without changing trains). In the second model, we relax this last constraint and consider that some OD pairs can be satisfied with one connection within the line (see Section 3.1.5). In Section 3.2, we assume that the train dynamics admit a stationary regime in both models and derive by numerical simulations the average train frequency for both models, given as functions of the total number of trains running.

Notations

Our model is an extension of the work developed in [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF]. The model is based on the current signaling system of a metro line, which is divided into segments. The end of the segments corresponds to a signal on the line. There are n segments and nodes, and the number of trains running is given by the variable m. The variables b j and bj = 1b j provide the initial state of the line: if there is a train in the initial state on segment j, we have b j = 1. Otherwise, we have b j = 0. Characteristic times are associated with each segment j of the line. The run time, dwell time, travel time, and safe separation time for a segment j are denoted by r j , w j , t j , and s j , respectively. Travel time is the sum of running and stopping times, i.e., t j = r j + w j , corresponding to the time required for a train to travel from node j -1 to node j. Our model aims at computing the variable d k j , the instant of the k th departure at each node j. Note that k indexes the number of departures and not the trains. Thus, we can compute the headway h k j between two trains at each node and for each iteration k.

With a skip-stop policy, we need to distinguish the stations between the skippable and mandatory ones. We define the set O as the set of all skippable stations. At these stations, we need to distinguish the run time, the dwell time, and thus the travel time for the trains that stop or skip these stations. We add the exponent l to these variables to make the distinction. If l = 0, the travel time t 0 j corresponds to a train that stops at station j, while l = 1 indicates the travel time of a train that skips the station. In the latter case, the train dwell time lower bound is equal to 0 (w 1 j = 0) as we do not require the train to stop. For all other nodes, the travel time is written without exponent. However, even if a train does not stop at a station, the departure k is counted. = {0, 1}: the exponent to differentiate the stopping pattern of a train at a skippable station. The value l j = 0 corresponds to a train stopping at the station j, whereas l j = 1 means that the train skips this station. b j ∈ {0, 1}: boolean variable of trains being on segment j at time zero, we have b j = 1 if there is a train on the segment j, and b j = 0. bj = 1b j ∈ {0, 1}: the opposite of b j d k j instant of the k th departure time from node j. Notice that k does not index trains but counts the number of departures. r l j the run time of a train on segment j in service l, i.e. from node j -1 to node j. In our case, l = 0 denotes a service stopping at all stations, while l = 1 denotes a service skipping secondary stations. w k,l j = d k ja k j : train dwell time corresponding to the k th arrival to-and departure from node j for case l. t k,l j = r l j + w k,l j : train travel time from node j -1 to node j, corresponding to the k th arrival to-and departure from node j for case l.

h k j = d k j -d k-1 j
: departure time headway at node j, associated to the (k -1) th and k th departures from node j. s j a safe separation time associated with node j.

We underline the notations to indicate the lower bounds of the above-mentioned variables. Respectively, r, t, w, h, and s denote the lower bound run, travel, dwell, headway, and safe separation times. We also denote these variables without subscript or superscript as the mean over j and k (asymptotic). Therefore, r, t, w, h, and s denote the asymptotic average run, travel, dwell, headway, and safe separation times. Using the notations, we can write the dynamics of the train. Our model is built on two constraints.

The Travel Time Constraint

This first constraint requires a departure not to occur before the considered train arrives at the considered node. The departure time at node j of a train must be greater than or equal to the departure time of the same train at the previous node j -1, plus the travel (run + dwell) time from node j -1 to node j. For example, if there is a train on segment j at time zero (i.e. if b j = 1), then the train making the k th departure at node j made the (k -1) th departure at node (j -1). On the other hand, if there is no train on segment j at time zero (i.e. if b j = 0), then the train performs the k th departure at both nodes (j -1) and j. In addition, we distinguish 3.1. MODELING APPROACH FOR A SKIP-STOP POLICY the cases of skippable stations from other nodes on the line.

d k j ≥ d k-b j j-1 + r j + w j = d k-b j j-1 + t j , ∀j / ∈ O (3.1) d k j ≥ d k-b j j-1 + r 0 j + w 0 j = d k-b j j-1 + t 0 j , if the train stops d k-b j j-1 + r 1 j + w 1 j = d k-b j j-1 + t 1 j , if the train skips ∀j ∈ O (3.2)

The Safe Separation Time Constraint

The safe separation time corresponds to a release time. In practice, a signal is red as soon as a train has departed from this signal and until the same train has departed from the next signal, plus a safe separation time, corresponding to the time for the train's rear to leave the segment. Thus, the safe separation time is not the same after a skippable station if the train has stopped or skipped the station.

Our model proposes a simplification and considers a unique safe separation time corresponding to a train that stops at the station, i.e., the longer safe separation time. The constraint requires that a departure from a given segment cannot occur if the next segment is not free of any train. For our model, the departure at node j of a train occurs when the train on segment j + 1 has departed, plus a given safe separation time s j . If there is no train at node j + 1 at time zero (i.e. if b j+1 = 0, and so bj+1 = 1), then the train which makes the k th departure at node j, makes also the k th departure at node j + 1. Therefore, the previous train has made the (k -1) th departure at node j + 1. On the contrary, if there is a train at node j + 1 (i.e., if b j+1 = 1, and so bj+1 = 0), the train making the k th departure on node j makes the (k + 1) th departure at node j + 1. Therefore, to summarize the two cases, the k th departure from node j is constrained by the (k -bj+1 ) th departure at node j + 1. Our model considers that the safe separation time is the same whether a train stops at or skips a station. Thus, it is not necessary to distinguish two cases as in the travel time constraint. We can write the safe separation time constraint as follows:

d k j ≥ d k-bj+1 j+1 + s j+1 . (3.3)

The Train Dynamics

We consider that the departure occurs as soon as both constraints are satisfied. We thus obtain the departure time by taking the maximum between the two constraints. The train dynamics are then written

d k j = max{d k-b j j-1 + t j , d k-bj+1 j+1 + s j+1 }, ∀j / ∈ O (3.4) d k j = max{d k-b j j-1 + t 0 j , d k-bj+1 j+1 + s 0 j+1 }, if the train stops max{d k-b j j-1 + t 1 j , d k-bj+1 j+1 + s 1 j+1 }, if the train skips , ∀j ∈ O (3.5)
We can use Equations (3.4) and (3.5) to simulate the train dynamics, but first, we must determine the condition for which a train stops or skips a skippable station. For this, we distinguish two models with two different rules, which we explain in the following sections.

The Models

Restricted Model

For this first model, we want to ensure that all origin-destination (OD) pairs are feasible without any connection. A train that stops at all skippable stations is followed by another train that skips all such stations. Therefore, we formulate our rule for determining whether a train stops as follows: if a train stops at the first skippable station o 1 , it must stop at all other skippable stations o i ∈ O. Similarly, a train that skips the first skippable station o 1 must skip all other skippable stations o i ∈ O. We write the dynamics of the trains for all the skippable stations according to the variable l j .

d k j = max{d k-b j j-1 + t l j j , d k-bj+1 j+1 + s j+1 } (3.6)
We need to find the rule to determine the value of l j . First, we use the departure parity for the first skippable station o 1 . Trains making an odd departure at o 1 must stop, while trains making an even departure must skip this station. We need to find a similar rule for all other skippable stations, i.e.,

∀o i ∈ O such that o i ̸ = o 1 . If o i p=o 1 +1
b p is even, trains making an odd departure at o 1 also make an odd departure at o i . An odd departure at o i corresponds to a train that stops. Finally, the following equations give the value of l for all skippable stations, ∀j ∈ O :

l j = 0 if      j = o 1 , and k is odd. j ̸ = o 1 , j p=o 1 +1 b p is even, and k is odd j ̸ = o 1 , j p=o 1 +1 b p is odd, and k is even (3.7) l j = 1 if      j = o 1 , and k is even j ̸ = o 1 , j p=o 1 +1 b p is odd, and k is odd j ̸ = o 1 , j p=o 1 +1
b p is even, and k is even

(3.8)
Let's take an example to illustrate the value of l j . Let's consider the train making the k th departure at node o 1 , with k odd. In this case, the train must stop at this first skippable station. The same train will make the k + o 2 p=o 1 +1 b p th departure at station o 2 . Thus, if o 2 p=o 1 +1 b p is even, the train makes an odd departure at node o 2 , whereas it makes an even departure if o 2 p=o 1 +1 b p is odd. Therefore, we find the conditions given in Equation (3.8).

Unrestricted Model

In the second model, we relax the OD service constraint (which requires, for the first model, that all OD pairs be feasible without connection). As a result, some OD pairs may become infeasible without connection. We only ensure that every skippable station (i.e., a station in O) is served every other time. Therefore, we only need to look at the parity of k to differentiate the cases. Concretely, ∀j ∈ O :

• the trains stop at the station j if k is odd.

• the trains do not stop at the station j if k is even.

And the following equations give the train dynamics, ∀j ∈ O.

d k j = max{d k-b j j-1 + t 0 j , d k-bj+1 j+1 + s j+1 }, odd k (3.9) d k j = max{d k-b j j-1 + t 1 j , d k-bj+1 j+1 + s j+1 }, even k (3.10)

Simulations

In this section, we present the first results of the impact of a skip-stop policy on the performance of the line and on the travel time of the passengers. We simulate the train dynamics developed in Section 3.1.4. We aim to give insights to the operator to evaluate the possible benefits of such a policy for a shuttle-type line. In Section 3.2.1, we study the average headway between trains and the frequency as a function of the number of trains running on the line. We also examine the trajectories of the trains to understand their interactions. Finally, we focus on the passengers' point of view in Section 3.2.3. In this first chapter, we do not consider the arrival flows of the passengers' demand, but we examine the travel time for each OD.

The models are applied to Paris metro line 1, see Figure 1.3. Among its 25 stations, 15 have interconnections with other network lines, while 10 are served only by line 1. In this chapter, we assume stations without interconnections with other lines in the network have lower passenger demand arrival rates and can be skipped every other time (skippable stations).

The Fundamental Diagrams of the Train Dynamics

The line's fundamental diagram gives a relationship between the line frequency (or line traffic flow) in vehicles per hour and the number of trains running on the line. Using the train dynamics, we can compute headway between two trains at all nodes on the line and for each iteration k. We study the asymptotic average train headway h obtained by taking the average on all nodes and with k → ∞. The following equations give the average train running headway and frequency.

h j = lim k→+∞ d k j /k, ∀j (3.11)
h = j h j /n (3.12) f = 1/h (3.13)
For every 0 < m < n, we simulate the train dynamics for a sufficiently large number of iterations K and estimate the asymptotic average train time-headway h and frequency f . For a line without a skip-stop policy, the papers using the same discretization showed that the steady state of the train dynamics exists and is equal to the limit defined by Equations (3.11) and (3.12). We consider in this chapter that the limit also exists for a line operated with a skip-stop policy. In Chapter 4, we prove that the steady state exists and is indeed equal to the limit when k → ∞.

For each value of m, we report the average train frequency to create the fundamental diagram of the line. Passengers going from or to skippable stations can only board trains serving their origin or destination. Thus, the average headway between two trains these passengers can board is doubled. For both models, we also represent the frequency of the line operated with an all-stop policy on the same diagram. It allows us to compare graphically the train frequencies. In Figures 3.2a and 3.2b, we show three different curves. The frequencies of the skip-stop models are shown in orange and green, respectively, for passengers boarding any train and for passengers boarding a specific train. The blue curve represents the frequency of the line with an all-stop policy. Three phases can be distinguished in both figures and for the three curves. The first phase corresponds to the free flow phase. The frequency increases with the number of trains. Beyond a certain number of trains (here about m = 55), there is the capacity phase. It corresponds to the maximum achievable frequency. When reached, adding trains does not decrease the average headway between two trains. After a train has departed from a signal, there is a minimum time before another train can depart from the same signal. The signal with the longest time limits the overall frequency of trains and gives the line's capacity. Finally, there is the congestion phase. When too many trains run on the line, they interact with each other (because of the safety separation constraint), inducing train congestion. However, there are also differences between the restricted and unrestricted models. The fundamental diagram of Figure 3.2a shows no apparent improvement in train frequency with our first model. At best, a slight improvement occurs when m is small. However, when m is close to the one that gives the maximum frequency, the two curves merge.

For the presented unrestricted model, the trains have more freedom as we relax 3.2. SIMULATIONS the constraint requiring that every OD pair be possible without a connection. In Figure 3.2b, the curves are distinguished. The average train frequency increases faster when a skip-stop policy is implemented. However, the maximum frequency and congestion phase remain unchanged.

Train Trajectories

To better understand the difference between the models and why there is no improvement with the restricted model, we represent the train trajectories on a small part of the line; about more than half of the stations in one direction from La Défense station to Hôtel de Ville. Figures 3.3a and 3.3b represent the trajectories for the restricted and unrestricted models with m = 50 trains running and for about 60 minutes. On the y-axis, stations in bold are mandatory, while stations in italics are skippable. When the corresponding number of trains is m = 50, the headway between trains is about 2 minutes, corresponding to the line's peak hour headway. On Figure 3.3a, the black dashed curve represents trains that stop at all stations, and the solid blue lines represent trains that do not stop at skippable stations. The other service slows down these trains. They often must wait in the interstation until the preceding trains leave the platform. The slower service, therefore, limits the trains' frequency.

On Figure 3.2b, with m = 50, the difference between the line operated with and without the skip-stop policy in train frequency is 1.4 trains per hour. There is also a significant saving in the number of trains moving. Indeed, to reach the train frequency given by the second model presented above, with m = 50, three more trains are needed with the model without a skip-stop policy. We can see on Figure 3.3b that there are fewer interstation stops than in the restricted model. Indeed, with the unrestricted model, the trains can circulate more freely on the line without congestion.

Passengers Point of View

As noted previously, passengers' arrival flows are not yet available. Therefore, this section is the first look at how waiting and travel times are affected in train operations. The previous paragraph examined the potential frequency gains to the operator with the two proposed models. Nevertheless, passengers are also significantly affected, either positively or negatively. Therefore, this section is the first step in measuring the benefits to passengers. To measure passenger gains or losses, we calculate the travel time between each OD pair for the line operated with and without a skip-stop policy and illustrate this with two examples; see Figure 3.4. The passenger travel time for a given OD includes the passenger waiting time at the origin station (a function of the train time headway) and the train travel time from the origin to the destination stations. These two figures were obtained by calculating the travel time of a passenger for each OD, first with an all-stop policy, denoted by T (i,j) , and with a skip-stop policy denoted by T s (i,j) . The difference between the two travel times is calculated as follows.

∆T (i,j) := T (i,j) -T s (i,j) , ∀i, j. (3.14)
For each OD pair (i, j), when ∆T (i,j) is greater than zero, passengers gain travel time with the skip-stop policy, while if ∆T (i,j) is negative, the travel with all-stop policy is

Time in minutes

Def.

E. Def

Neuilly Sablons

Maillot

Arg.

CDG

Geo. V

Roos. CE

Conc.

Tuil. PR Louvre

Chat.

HdV

Time in minutes

Def.

E. Def

Neuilly Sablons

Maillot

Arg.

CDG

Geo. V

Roos. CE

Conc.

Tuil.

PR Louvre

Chat. faster for that OD. In Figure 3.4, the blue and red squares indicate, respectively, the origins-destinations for which passengers lose or gain travel time when a skip-stop policy is implemented. To compute passenger waiting time, we assume that passengers arrive at stations uniformly regardless of their origin and destination. To compute the passengers' waiting time, we consider the steady state of the train dynamics, and thus, the headway between two trains is equivalent to the average train time headway h. We distinguish three cases:

HdV

1. The origin and destination are mandatory stations. We consider an average waiting time equal to half the headway, i.e., h/2.

2.

Either the destination is a skip station, or both are skip stations, but it is possible to reach the destination without making a connection. In this case,

SIMULATIONS

the waiting time is given by h because the passengers have to board a specific train.

3. Finally, the last case corresponds to impossible origin-destinations. Passengers must wait at both the origin and transfer stations. The average waiting time at the origin station is equal to the headway h, as is the waiting time at the transfer station. Indeed, once the passenger has alighted at the transfer station, he or she must wait for the next train, which will arrive after the average headway h. Consequently, the average waiting time is given by 2h for these ODs.

Restricted Model

We do not improve line frequency as noted in Section 3.2.1. Therefore, on average, train travel times are the same for each origin-destination. For some ODs, passenger waiting time is the same, but it increases for passengers going to or from a skippable station. Thus, some passengers do not lose time at best. Moreover, the readability for passengers is more complex, as they have to look to see which train stops at which station.

Unrestricted Model

The unrestricted model increases the frequency of trains, which reduces waiting time at mandatory stations and the travel time of trains. However, some passengers can only reach their destinations with a connection within the line. Waiting times for these passengers are considerably longer, as they have to wait for a train at two different stations. We measure the gains and losses in two cases, with the number of trains equal to 22 and 50. In the first case Figure 3.4a, the average headway between trains is about 6 minutes, corresponding to an off-peak headway.

In the second case Figure 3.4b, the headway between trains during peak hours is 2 minutes, corresponding to 50 trains running. In both figures, each square represents the difference in the travel time ∆T (i,j) for all origin-destinations i, j. The x and y axes represent the destination and origin; for readability purposes, only mandatory stations are written on the axis. The color of the squares becomes brighter as the difference (either negatively or positively) between the travel time increases. The red color shows the origin destinations for which the skip-stop policy benefits passengers. On the contrary, the blue squares indicate that passengers travel slower when the line is operated with a skip-stop policy. Finally, we set a lower and upper threshold for time lost or gained. Below or above 6 minutes gained or lost, the squares are the same color, bright red or blue respectively. Three trends emerge from these figures: first, ODs whose origin and destination are mandatory stations show significant savings. Moreover, the savings increase with the distance between the origin and destination. On the contrary, origin and destination stations that can only be reached by a transfer show significant time losses. Especially on Figure 3.4a, when the headway is high, about 40 origin destinations lose more than 6 minutes. However, this number drops to less than 10 ODs on Figure 3.4b. Finally, for all other ODs, headway plays an important role. For example, for the second origin station, on Figure 3.4a, all ODs are in blue, and passengers lose time. But on Figure 3.4b, as soon as the distance between origin and destination is high enough, the time loss due to waiting is compensated by the reduction of travel time. Finally, with a headway of about 6 minutes, each OD loses, on average, about 5 seconds of travel time, while there is a gain of 50 seconds with a time headway of 2 minutes. The skip-stop policy must be implemented at a high frequency to benefit to passengers. With a high frequency, the increase in waiting time is offset by the reduction in travel time.

D e f M a i . C d g R o o . C E C o n . P R C h a . H d v B a s . G L R D N a t . V i n . C h . v .

Destination

Conclusion

This first chapter takes the first step toward modeling skip-stop policies. We write equations that describe the train dynamics of a line operated by a skip policy. Using these equations, we proposed two different models. The first model requires every other train to stop at all skippable stations, thus ensuring that going from any station to another is possible without requiring a transfer. However, this model does not improve train frequency, as trains that stop at all stations can block other 3.3. CONCLUSION trains and limit frequency. In addition, passenger travel time remains the same or may even be longer depending on the OD. So there is no benefit to operators or passengers from this strategy.

On the other hand, if we relax the OD constraint, the frequency of trains at mandatory stations and passengers' travel time are improved. Therefore, the skipstop policy can be beneficial to both the operator and the passengers under specific conditions, which we examine in this chapter.

However, in this chapter, we could only obtain these results through numerical simulations. We assume that the steady state of the train dynamics exists and is given by the limit when the number of iterations tends to infinity. In the next chapter, we will prove our assumption. Furthermore, we cannot choose which trains should stop at which station. Therefore, in the next chapter, we extend our model to consider the trains' stopping pattern. In doing so, we aim to obtain analytical results that allow us to interpret all traffic phases in the fundamental diagram.

Finally, we first look at the possible benefits for the passengers'. However, their arrival rate at stations and their origin-destinations is not considered in the model. Even if our results give insights for both the operator and the passengers, further studies are necessary to assess precisely the global system operation.

Chapter 4

Max-plus Modeling of a Two-Service Skip-Stop Policy

With the train dynamics developed in the previous chapter, it is currently not feasible to establish specific services for the trains. Consequently, accurately calculating the passengers' perspective and measuring the effects of the skip-stop policy becomes challenging. In this chapter, we incorporate the services defined by the operator as input to the model. Additionally, we demonstrate that the train dynamics can be expressed linearly using the Max-plus algebra. Our model allows the derivation and interpretation of traffic physics and the impact of implementing a skip-stop policy on line frequency. We present our model on a unidirectional loop line and use Paris metro line 1 as a case study. This chapter focuses on the operator's point of view and evaluates the gains that a skip-stop policy can provide in terms of frequency. Through our model, we analytically derive a fundamental traffic diagram for the line. This diagram provides average train-time headway or frequency as a function of the number of running trains. We show the existence of three distinct phases: free-flow, capacity, and congestion. Moreover, we prove that the free-flow phase is piecewise linear and that it exists a number of running trains beyond which the trains interact with each other limiting the increase of the frequency. We also study the impact of the number of skippable stations or the stopping patterns defined by the operator. Finally, the frequency of the skip-stop policy is compared to an all-stop one to measure the gains that the operator should expect.

Modeling

In this section, we develop our mathematical model for the dynamics of the trains. The modeling is in the principles similar to Chapter 3; however, we recall all the notations and principles in this section. First, we describe the considered metro line with the main assumptions and then fix the notations. The train dynamics model is then described by two constraints, written on the train departure time variable.

We then analyze the model in the max-plus algebra, showing its linearity in this algebraic structure. Finally, we derive interesting formulas on the train dynamics' stationary regime using some max-plus algebra theorems.

Main Assumptions

The application of our model is any unidirectional loop line (line without junction) where trains run without overtaking, see Figure 3.1. We use the signaling system to discretize the line into several segments. Each segment ends in a node corresponding to a signal on the line. There are three types of nodes: stations where all trains stop (solid squares), stations that can be skipped (empty squares), and the other nodes corresponding to signals between stations. In this chapter, we first consider two different services, A and B, that alternate on the line.

Each segment is associated with characteristic times: the travel time, i.e., the sum of the run and dwell times, and the safe separation time. In the Paris metro network, all lines except the three less frequented ones are at least equipped with a grade of automation 2 (GOA 2) for the conduction. With GOA 2, the driving system manages the acceleration and braking of trains. Therefore, only station dwell times are nondeterministic. The passengers' arrival rate at stations directly influences the dwell times, as drivers need to wait for all passengers to alight and board the trains. With this grade of automation, the assumptions of non-deterministic dwell times might be too restrictive. This aspect is studied in Chapter 5. In addition, two lines in the network are fully automated (GOA 4), including our case study. On fully automated lines, the trains are driverless. Therefore, the system manages driving and does not require onboard staff, even in an emergency. Moreover, in all stations, platform screen doors prevent passengers from falling onto the tracks, increasing safety and diminishing the causes of disturbances. During operation, all nominal times are effectively achieved by all trains. There are still some small disturbances, but their occurrences are very low. In Table 4.1, we give some reliability data for our case study. First, the trains' reliability is provided by the percentage of the trains' number that actually run compared to the schedule. Then, the headway reliability measures the percentage of passengers who wait for a train less or as much as the reference headway. Since its full automation in 2013, the line has averaged about 100% on both indicators1 . Therefore, our deterministic run, dwell, and safe separation time assumption is not restrictive for a fully automated line. In future research, nondeterministic train dwell times will be considered to extend the model to lines with GOA 2 conduction systems. Still, in this paper, we assume that the train dwell times provided by the operator are sufficiently long to allow all passengers to get off and on the trains at every station. As mentioned in the introduction, our model aims to derive the train frequency as a function of the number of trains running on the line, the services provided by the operator, and other CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 35 parameters, such as lower bounds on train dwell times at stations, train running times on inter-stations, safe separation times of trains, etc. We give below the required notations for our model and then present the model.

Notations

To consider the train dynamics on the metro line, including the dynamics on the inter-stations, we discretize the line into segments (or blocks), as done by the signal system. The length of each segment must be bigger than or equal to the length of one train, plus a minimum safe separation distance between trains. The discretization is illustrated in Figure 3.1. Lower bounds on train run (r j ), dwell (w j ), and safe separation (s j ) times on every segment j are then derived from the ones on every inter-station, where we still distinguish the cases where the trains stop at or skip the station downstream of the considered segment. In particular, train run and dwell times are longer for the cases where trains stop than for the cases where they skip a station; when a train stops at a station, it must slow down and wait for passengers to alight and board. Our model aims to calculate the train departure times (denoted d k j for the k th departure from node j) at all line nodes. Then from this calculus, we derive interesting formulas, diagrams, and macroscopic behaviors. Let us consider the notations of Table 4.2, where the main variables of the train dynamics are indexed by node (j) and by a counter (k) counting the number of departures from (or arrivals to) a considered node. We notice here that the index k does not index the trains, but it counts their departures from (or arrivals to) every node j. Indexing the departures [START_REF] Van Breusegem | Traffic modeling and state feedback control for metro lines[END_REF] instead of trains [START_REF] Gill | Simulation analysis of transmission-based signalling systems for metro applications[END_REF] is a relatively new approach in the rail transit modeling literature. It allows us to write the model linearly in the Max-plus algebra and derive analytical formulas and diagrams on the train dynamics.

For each of the variables r k j , w k j , t k j , and s k j , there exists a lower bound denoted by the underlined variable. It corresponds to the minimum time defined by the line's constraint for the run and safe separation time or by the operator for the dwell time. With a skip-stop policy, the lower bound depends on the service performed by the 4.1. MODELING train. In Table 4.3, we give as, r p j , w p j , t p j , and w p j the lower bounds for the run, dwell, travel and safe separation time for the service p ∈ {A, B}. Moreover, we differentiate Let us now write the model using the notations of Tables 4.2 and 4.3. The main variable of the model is the train k th departure time d k j at every node j, and its calculation is based on two constraints. These two constraints have been developed in Sections 3.1.2 and 3.1.3, so remind the main principles of these constraints.

Travel Time Constraint

This first constraint requires a departure not to occur before the considered train arrives at the considered node. The trains have to respect the speed limits imposed by the line's characteristics. Thus, the departure at node j must be greater than the departure at the previous node j -1 of the same train. In this chapter, we consider the two services A and B, thus the travel time depends on the train service. The constraint is then written as follows:

d k j ≥      d k-b j j-1 + t A j , if the train performs service A, d k-b j j-1 + t B j , if the train performs service B. ∀j (4.1)

Safe Separation Time Constraint

The safe separation time corresponds to a release time. This constraint ensures that there are no collisions between trains. Thus, the next segment must be free of trains, and the departure at node j is possible after the departure of the previous train on segment j + 1, plus a given safe separation time s j . For this constraint, we do not distinguish between cases, since we take the largest value between the two services. So there is no need to distinguish between two cases as in the travel time constraint. We can write the safe separation time constraint as follows:

d k j ≥ d k-bj+1 j+1 + s j+1 (4.2)
Constraint (4.2) does not allow a train departure from segment j when segment j + 1 is not free. In practice, the signal system blocks the train on segment j. It ensures that train overtaking is not allowed.

The Train Dynamics

The train dynamics are obtained by combining the travel time and safe separation constraints. A train is considered to depart as soon as both constraints are satisfied.

d k j =      max{d k-b j j-1 + t A j , d k-bj+1 j+1 + s j+1 }, if the train performs service A max{d k-b j j-1 + t B j , d k-bj+1 j+1 + s j+1 }, if the train performs service B (4.3)
For node j and for each count k, we can evaluate the departure depending on the service of the train. Yet, we currently have no rule to define when a train makes a service or the other.

Services and Parity of Departure

We now have the dynamics of the trains, but we still need to determine the conditions under which a train stops at or skips a station. For example, the trains stop at skippable stations every other time. Thus, we can use the parity of departures. Indeed, if a train stops at a skippable station when making an odd departure, the next train making an even departure necessarily skips the station. In Chapter 3, a simple rule is set for skippable stations: trains making odd departures stop, and the even departures induce trains to skip stations. Nevertheless, ensuring that the trains make the services defined by the operators is impossible. Therefore, we give here a new rule that defines the behavior of the trains at skippable stations based on the parity of departures. We introduce the variables µ e j and µ o j , which are equal to either A or B. If µ e j = A, a train making an even departure at node j makes service A on this segment, and we also have µ o j = B. We need to ensure that the services defined by the operator are respected by the trains on all the nodes of the line. Therefore, we set a rule at each node to define if an even departure corresponds to a train performing service A or B.

µ e j := A if j q=1 b q is even B otherwise (4.4) µ o j := B if j q=1 b q is even A otherwise (4.5)
The variables µ e j and µ o j give the service associated with the departure parity for each node. For example, the train that makes the k th departure at the first node with k even is assigned service A, i.e., µ e 1 = A. We want to ensure that this train actually performs service A at all nodes on the line. For each node j, there is j q=1 b q 4.1. MODELING trains that will depart before the considered train arrives at station j. Therefore, it performs the k + j q=1 b q th departure at node j. If the number of trains j q=1 b q is even, then the considered train also makes an even departure, and we have µ e j = A. Otherwise, we have µ e j = B. With the definitions (Equations (4.4) and (4.5)), we can now rewrite the train dynamics according to the parity of the train departures. For readability purposes, we simplify the notation t µ o j j and t µ e j j into t µ o j and t µ e j .

d k j =      max{d k-b j j-1 + t µ e j , d k-bj+1 j+1 + s j+1 }, if k is even max{d k-b j j-1 + t µ o j , d k-bj+1 j+1 + s j+1 }, if k is odd (4.6)

Formulation in Max-plus Algebra

To analyze the dynamic model (Equation (4.6)), we propose in this section a formulation of this model in the Max-plus algebra. With this formulation, we obtain a linear model in this algebra. Then, we apply some results of the spectral theory of the Max-plus algebra to analyze the dynamic system and derive some interesting results.

Let us first rewrite our dynamic model (the train dynamics Equation (4.6)) in the Max-plus algebra of scalars. We obtain:

d k j =      t µ e j ⊗ d k-b j j-1 ⊕ s j+1 ⊗ d k-bj+1 j+1 , if k is even t µ o j ⊗ d k-b j j-1 ⊕ s j+1 ⊗ d k-bj+1 j+1 , if k is odd (4.7)
It is easy to see that each of the model's cases is linear in the Max-plus algebra.

Depending on the values of b j and bj , the departure d k j either depends on the previous iteration k -1 or on the current one k. We can divide these two cases and write the equations in matrix form. We obtain:

d k = Π 0 d k ⊕ Π 1 d k-1 , if k is even Φ 0 d k ⊕ Φ 1 d k-1 , if k is odd, (4.8)
where

d k := (d k 1 , . . . , d k n ) ′
is the vector giving the train departure times at all the nodes, and where the Max-plus matrices Π 0 , Π 1 , Φ 0 and Φ 1 are defined as follows.

(Π 0 ) (j,j-1) = t µ e j and (Φ 0 ) (j,j-1) = t µ o j if b j = 0 (Π 1 ) (j,j-1) = t µ e j and (Φ 1 ) (j,j-1) = t µ o j if b j = 1 (Π 0 ) (j-1,j) = s µ e j and (Φ 0 ) (j-1,j) = s µ o j if bj = 0 (Π 1 ) (j-1,j) = s µ e j and (Φ 1 ) (j-1,j) = s µ o j if bj = 1 Proposition 4.1.
1. The matrices Π 0 and Φ 0 are acyclic, i.e., their associated graphs do not contain any cycles.

The matrices Π *

0 and Φ * 0 are finite, i.e. Π k 0 = Φ k 0 = ε, for a sufficiently large k.

CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 39

Proof.

1. There exists in Π 0 and Φ 0 only arcs linking adjacent nodes. We also have 0 < m < n; thus, there exists at least one node j with b j = 1 and b j+1 = 0 that has only arcs going in and no going out. This node prevent any cycle in G(Π 0 ) and G(Φ 0 ). Besides, by definition bj = 1b j ̸ = b j . There exist no loop cycles in G(Π 0 ) and G(Φ 0 ).

2. From §3.7 of [4], if A contains no cycle, then A is nilpotent, that is, A k = ε for k sufficiently large. Proposition 4.2. The solutions of d k = Π 0 d k ⊕Π 1 d k-1 and d k = Φ 0 d k ⊕Φ 1 d k-1
exist and are unique. They are respectively given by

d k = Π * 0 Π 1 d k-1 and d k = Φ * 0 Φ 1 d k-1 .
Proof.

1. Proposition 4.1 show that there are no cycles and thus no cycle with positive weights. The existence of the solution comes directly from Theorem 2.1.

2. To prove the uniqueness of the solution, we use the proof of Theorem 2.1 developed in [START_REF]Synchronization and Linearity: An Algebra for Discrete Event Systems[END_REF]. The condition for uniqueness is given by A k = ε when k → ∞. Proposition 4.1 also shows that this condition is satisfied for Π k 0 and Φ k 0 , thus the solution is unique.

We can now apply Proposition 4.2 to the dynamic system (Equation (4.8)), and rewrite it as follows:

d k = Πd k-1 , if k is even Φd k-1 , if k is odd, (4.9)
where Π := Π * 0 Π 1 and Φ := Φ * 0 Φ 1 . Then, if we consider k odd, we have d k = Φd k-1 and d k-1 = Πd k-2 since k -1 is even. Therefore we have d k = ΦΠd k-2 . If we define Υ := ΦΠ, the dynamic is now written for an odd k, as follows:

d k = Υd k-2 (4.10)
For k even, we have

d k = Υ ′ d k-2 with Υ ′ := ΠΦ.

Main Theorem

In this section, we can use Equation (4.10) to derive the average train-time headway. First, we enunciate Theorem 4.3 and Corollary 4.5, giving the average train time headway and frequency of a line operated with a two-service skip-stop policy. Then, in Section 4.2.1, we make explicit the variables used in the theorem and their interpretation in terms of the physics of traffic. Finally, Appendix A gives the complete proof of Theorem 4.3.

Theorem Variables

Before giving the theorem statement, we first develop the notations used to obtain the average train-time headway. First, the average train time headway on a line 4.2. MAIN THEOREM depends on the number of running trains m, with different patterns emerging depending on whether the number of trains is odd or even. When there is an even number of running trains m, trains run the same service consistently. However, with an odd number of trains, the service changes every time a train reaches the terminus. For a train making its k th departure at the first node, its next departure at the same node will be the

(k + m) th ,
I ψ := {i 1 , i 2 , • • • , i ψ },
:= 2 max{T A , T B }, if ψ = 0 2 max p,I ψ {T p 1 i 1 ,i 2 + T p 2 i 2 ,i 3 + • • • + T p 2 i ψ ,i 1 }, otherwise T o ψ := (T A + T B ), if ψ = 0 2 max p,I ψ {T p 1 o,i 2 + T p 2 i 2 ,i 3 + • • • + T p 2 i ψ ,o
}, otherwise S := j s j , the sum of all the safe separation times.

The variables T e ψ and T o ψ depend on ψ, the number of nodes where the service changes for the calculation of the average train travel time. The set I ψ gives the nodes sorted in ascending order in the direction of the train at which the service changes. In the case where ψ = 0, the set I ψ is empty, and the average train travel time is given by either T A or T B . However, if ψ > 0, we have a non-empty set I ψ , and the average travel time is a combination of both services A and B. Consider an example with ψ = 4. With I ψ = {i 1 , i 2 , i 3 , i 4 } such that i 1 < i 2 < i 3 < i 4 , the average train travel time is given by given by the service p 1 . Then at node i 2 there is a change in the service change, and it is service B which gives the average travel time on that part of the line. Similarly, at nodes i 3 and i 4 , it is services p 1 and p 2 that give the average train travel time, respectively.

T p,I ψ = T p 1 i 1 ,i 2 + T p 2 i 2 ,i 3 + T p 1 i 3 ,i 4 + T p 2 i 4 ,i 1 .
| i 1 | | | i 2 | | | i 3 | i 4 T p 1 (i 1 ,i 2 ) T p 1 (i 3 ,i 4 ) T p 2 (i 2 ,i 3 ) T p 2 (i 4 ,i 1 )
In addition, it is the maximum value on all the sets of possible nodes which is considered in the Theorem 4.3. Thus, if the maximum is given by the set

I ψ = {i 1 , i 2 , i 3 , i 4 }, then we have ∀I ′ ψ = {i ′ 1 , i ′ 2 , i ′ 3 , i ′ 4 }, T p,I ψ ≥ T p,I ′ ψ .

Theorem and Corollaries

In Equation (4.10), the departure vector d k is determined by the departure vector d k-2 and the max-plus matrix Υ, which has a unique non-zero eigenvalue indicating the growth rate as it will be shown in Appendix A. This eigenvalue reflects the matrix's growth rate over two steps, as the k th departure is a function of the (k -2) th departure. The matrix's growth rate can be interpreted as the average train time headway, and in our dynamics, it specifically represents the average headway between two trains performing the same service.

Theorem 4.3. The train dynamics admit a stationary regime where the asymptotic average train time-headway of the line between two trains performing the same service is given by h e 2 and h o 2 for respectively an even and an odd number m of trains:

h e 2 (m) = max{h e fw , h min , h bw } (4.11) h o 2 (m) = max{h o fw , h min , h bw } (4.12) with 0 ≤ ψ ≤ |O|, h e fw = max ψ {T e ψ /(m + ψ)} and ψ even, h o fw = max ψ {T o ψ /(m + ψ)}, h min = max j {(t A j + t B j + 2s j )}, and h bw = 2S/(n -m).
Proof. The complete proof is given in Appendix A.

Corollary 4.4. The average train-time headway of the line between two trains is given by h e and h o for, respectively, an even and an odd number m of trains:

h e (m) = h e 2 (m)/2 (4.13) h o (m) = h o 2 (m)/2 (4.14)
Proof. Directly from one train being between two trains doing the same service.

The headway formulas differ based on the parity of the number of trains running. Specifically, if the number of trains is even, each train runs the same service, and it does not change its service at the line terminus. Whereas if it is odd, a train changes its service at the terminus; thus, each train alternates services from one lap to another. For example, at node j, a train that makes the k th departure will make the k + m th on its next departure from the same node, i.e., on the next lap. Because overtaking is impossible on the line, all other trains will depart at the same node. If m is even, the parity of k and k + m and the associated service are identical. On the contrary, the parity of k and k + m are not the same when the number of trains running is odd, and thus the services performed are not the same. We can express the average frequency of the line with Corollary 4.5.

Corollary 4.5. The asymptotic average train frequency of the line is given by f e (m) and f o (m) for, respectively, an even and an odd number m of trains:

f e (m) = min{f e fw , f max , f bw } (4.15) f o (m) = min{f o fw , f max , f bw } (4.16) with 0 ≤ ψ ≤ O, f e fw = 1/h e fw , f o fw = 1/h o fw , f max = 1/h min , and f bw = 1/h bw .
Proof. Directly from f = 1/h.

The headway and the frequency depend on three different terms. In Section 4.4, we represent and interpret the evolution of the headway and frequency in the fundamental diagram of the line. However, it is important to notice that the variables h e (m), h o (m), f e (m), and f o (m) correspond to a ratio between the number of moving trains and variables corresponding to the train travel times to go around the line. These variables are detailed in Section 4.2.1.

Review of the Results for a Line With an All-Stop Policy

This section reviews the main theoretical results for a loop line operated with an all-stop policy. The average train-time headway and frequency are denoted with the variables h a and f a Theorem 4.6. [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF] The asymptotic average time-headway h of the trains is given as follows.

h a (m) = max {h fw , h min , h bw } , (4.17)
with h fw = j t j /m, h min = max j {t j + s j }, and h bw = j s j /(nm).

Corollary 4.7. [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF] The asymptotic average frequency f of the trains is given as follows.

f a (m) = min {f fw , f max , f bw } (4.18)
with f fw = m/ j t j , f max = 1/h min and f bw = (nm)/( j s j ).

Note that t j corresponds to the train's travel time that stops at all stations. In the next sections of the chapter, we define T := j t j = j t 0 j , the travel time to go around the line by stopping at all stations, and S := j s j . 2). It is very useful for understanding line operation. In Section 4.2.2, we pointed out the differences between an even and odd number of trains running on the line. It also results in differences in train time headway and frequency. However, we can do the analyses for the case with an even number of trains and generalize them to the case with an odd number of trains since the shape of the fundamental diagrams is similar in both cases.

The fundamental diagram (see Figure 4.2) is divided into three main phases. In the first phase, corresponding to f e fw , the frequency increases with the number m of trains. The formula of f e fw depends on ψ, which makes this phase piecewise linear. In the second phase, the train frequency is constant, i.e., whether a train is added or removed, the frequency remains the same, provided that it does not cause a phase change. In the last phase, adding a train decreases the frequency.

Application Case

Description of the Line Characteristics

In the next sections of this paper, we use as a case study Metro line 1 of the Paris network operated by the RATP Group [START_REF]RATP Group: Moving towards a better city[END_REF]. Figure 1.3 and Table 4.5 show the line map and some of its characteristics.

The line consists of 25 stations connecting the east and west sides of the city, passing through multiple business districts, major tourist attractions, and some of the busiest stations on the system. It is the busiest line in the network [50]. The Paris network has 16 lines and is very dense. Common stations exist between some network lines (but operated on different tracks). It is possible to make connections between lines at these stations to reach one's destination. For example, Paris metro line 1 has 14 stations connecting with other rapid transit lines and one station with tramway lines. The line is now fully automated, and, as the busiest line in the network, the peak hour headway is less than 2 minutes. The line's rolling stock is homogeneous, and the trains are rubber-tired (53 MP05 in service). For this case study, we use data from RATP Group (the operator of Paris metro lines). The data provide each line segment's run, dwell, and safe separation time. These characteristic times are calculated using internal software, which considers the rolling stock's specifications and all the line's characteristics, such as the length or declivity of each segment.

Skippable Stations

We now describe the process for choosing which stations can be skipped and at which stations all trains must stop. We base our process on open data provided by the RATP Group [START_REF]Trafic annuel entrant par station du réseau ferré 2016[END_REF]. These data give the number of annual entries in all stations of the line. First, we assume that stations with a connection with another rapid transit line are served by all trains. It is because the strength of the Parisian network lies in its interconnections. It is, therefore, necessary to always allow passengers to be able to make their connections. Next, we establish that the ten less busiest stations with no connections can be skipped. In Section 4.4.2, we consider an alternate stopping pattern. For example, Table 4

The Traffic Phases of the Fundamental Diagram

The fundamental diagram is defined as the relationship between the train frequency in trains per hour and the number of running trains on the line. Using the formulas of Corollary 4.5, the fundamental diagram gives the average train frequency of the line for a given number of running trains m and with the lower bounds on the run, dwell, and safe separation times. In Figure 4.2, we represent the fundamental diagram of Line 1 that gives the asymptotic average train frequency evolution with the number of trains running in the line. Three phases are clearly notable: the free-flow phase corresponding to the growing part, the constant part corresponding to the capacity phase, and the decreasing part or congestion phase. To explain the phases and the physical phenomenon existing on the line, we represent the frequency for an even number of running trains, as the phases are similar for the even and odd cases. In Section 4.4.3, we explicit the differences between the even and odd cases.

The Free-Flow Phase

In the free-flow phase, the frequency increases with the number of trains. On a line operated without a skip-stop policy, this phase is linear. In our case, the equation that describes this phase is given by f e fw and depends on a variable ψ. The value of m changes the value of ψ, and thus f e fw is a piecewise linear function. It is bounded by the origin and the point m F on the x-axis such that m F (Proposition 4.8) corresponds to the train capacity of the line, the point where the maximum frequency f max is reached.

m o F = max ψ 1 α (T ψ f max -ψ) , with α = 1 if ψ is odd α = 2 if ψ is even (4.20)
Proof. We have by definition ψ ≥ 0 and T ψ > 0, ∀ψ ≥ 0. Thus f e ψ (m) = (m + ψ)/T ψ and f o ψ (m) = (αm +ψ)/T ψ are increasing and bijective as functions of m. Therefore, ∀l ∈ {e, o}, min ψ f l ψ (m) is increasing and bijective as a function of m. Then we have:

m l F := max{m, min ψ f ψ (m) ≤ f max }, by definition = m, such that min ψ f ψ ( m) = f max = max ψ f -1 ψ (f max ) Thus, m l F = max ψ {T ψ f max -ψ} , if l = e max ψ 1 α (T ψ f max -ψ) , if l = o
Since the frequency is piecewise linear, the slope of the line giving the evolution of the frequency, changes with the value of m. Therefore, it is possible to precisely determine the point E at which the slope changes for the first time. Moreover, this point corresponds to a flattening of the curve, which means that even if the frequency is still increasing, it is increasing more slowly.

m o E = min ψ T o 0 ψ αT o ψ -T o 0 , with α = 1 if ψ is even α = 2 if ψ is odd (4.22)
with ψ > 0.

Proof. Let l = e. We look for the value m such that, ∀ψ > 0: The proof uses the same arguments for l = o.

When a skip-stop policy is implemented on a line, the headway between two trains changes as trains move along the line. Consider two trains that follow each other. If the first train stops at a station that can be skipped, the following train must skip it, and the gap between the two trains is reduced. Conversely, the headway increases if the roles are reversed at the next station. An accordion phenomenon occurs on the line: trains get closer and further apart as they skip or stop at stations that can be skipped. In some cases, the headway decreases too much, and the second train must stop at a signal on the line to comply with the safety constraint because it is too close to the preceding train. Thus, the travel time of this train is limited by the slower first train. These cases are given by point E in Figure 4.2. Before point m l E , when ψ = 0, the frequency is given by m/T l (ψ=0) , with T l (ψ=0)

being the travel time for a round trip on the line. When the number m of trains is even, this travel time corresponds to the maximum between the two travel times for a round trip on the line performed with the two services. When m is odd, this travel time corresponds to the average of the two travel times for a round trip on the line performed with the two services. Trains complete one round trip with the travel time of one service and the second round trip with the travel time of the opposite service. None of the travel times limits the travel time for a round trip on the line performed with the two services. Therefore, it is given by T A and T B . On the contrary, trains perform the same service for an even number of m and have the same travel time on each round trip. Therefore, the larger value between T A and T B limits the travel time. During this phase, trains move freely on the line for the odd case, and none of them must stop at a signal to comply with a safety constraint. In the even case, at least one train moves freely, and it travels along the line without being blocked by another train performing the opposite service.

Beyond the number of running trains m E , the slope of the frequency decreases, which means that the average travel time of the trains increases. Between m E and m F , the accordion phenomenon that exists on the line creates interactions between trains that did not exist before m E . The line can be divided into multiple sections, where one service limits the travel time of all trains. If we take the same example as in Section 4.2.1, i.e., ψ = 2 and m is even, we have The line is divided into two sections, the first between i 1 and i 2 and the second between i 2 and i 1 . The services associated with the travel time of the trains in these two sections are opposite. For example, between i 1 and i 2 , service A gives the train's travel time, while the latter is given by service B between i 2 and i 1 . Thus, in terms of the physics of traffic, a train performing service B has its travel time limited by service A between i 1 and i 2 . And it is the opposite between nodes i 2 and i 1 . Moreover, if a train is limited by the other service on a section of the line, it is blocked at a node to ensure that the safety constraint is respected. These blockages are given in the travel times by the terms t p 1 i 1 + s i 1 and t p 2 i 2 + s i 2 . The T e ψ variables are divided into two terms: the first, denoted as j t p j , represents the sum of the train travel time to go around the line, and the second, written as i∈I ψ t i + s i , corresponds to the blockage time. Let ∆T ψ = T e ψ -T e ψ-2 be the difference between T e ψ , and T e ψ-2 . ∆T ψ is given in increases with ψ, and the increase is approximately constant with ∆T ψ ≤ ∆T ψ-2 . Moreover, we have I ψ-2 ⊆ I ψ , and the nodes in the sets correspond to signals before stations. As ψ increases, the value of the term j t p j also increases. Besides, when the number of trains is close to the line's capacity, this value is approximately the same as the travel time of a train stopping at all stations.

T e ψ>0 := 2   i 2 i 1 +1 t p 1 j + i 1 (mod n) i 2 +1 t p 2 j + t p 1 i 1 + s i 1 + t p 2 i 2 + s i 2   . 0 m E m F 100

The Capacity Phase

The second phase of the diagram corresponds to the train capacity of the line. The function that describes that part is independent of the number of trains and is defined between points F (Proposition 4.8) and G (Proposition 4.10).

Proposition 4.10. The number m G of trains corresponding to the end of the capacity phase is given by

m G = n -Sf max (4.23)
Proof. Directly from Theorem 4.3, we have:

h min = S/(n -m G ) ⇔ m G = n - S/h min
For every m satisfying m F ≤ m ≤ m G , the frequency remains constant and it is given by f max . This phase corresponds to the maximum frequency on the line. The segment with the maximum time (t µ A j + t µ B j + 2s j )/2 limits the headway, and adding one train on the line does not decrease the headway. It only extends the lap travel time.

From the passengers' point of view, the waiting time is still the same; they do not have to wait longer on the platform, but if m F ≤ m ≤ m G , trains experience conflicts as they have to stop between stations and, as a result, passengers suffer unnecessary stops between stations.

The Congestion Phase

Finally, the last phase is given by the line delimited by the points G = (m G , f max ) and H = (n, 0), the latter point is the intersection of the x-axis (f = 0) and the segment (f bw = (nm)/S). It corresponds to the train frequency decreasing phase of the diagram. During this phase, inserting a new train decreases the train frequency. This phase is already explained in [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF][START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part II -The Effect of Passenger Demand on the Traffic Phases[END_REF][START_REF] Farhi | A discrete-event model of the train traffic on a linear metro line[END_REF][START_REF] Schanzenbächer | Comprehensive passenger demand-dependent traffic control on a metro line with a junction and a derivation of the traffic phases[END_REF][START_REF] Schanzenbächer | Demand-Dependent Supply Control on a Linear Metro Line of the RATP Network[END_REF][START_REF] Farrando | Traffic modeling and simulation on a mass transit line with skip-stop policy[END_REF]. The fundamental diagram of road traffic presents a similar phase: when too many trains are running, trains interact with each other, creating congestion. The safe separation constraint determines the travel time around the line. Thus, it is given by the sum of all the safe separation times s j and no longer by the travel times t j . The operators should avoid this phase; keeping the trains at the depot is preferable to avoid congestion.

Difference Between the Even and Odd Cases

This section aims to compare the even and odd cases and evaluate their differences. As previously mentioned, the primary distinction lies in the services provided by trains. In the even case, a train always makes the same service, whereas in the odd case, a train switches its service every round. Consequently, the average travel time of trains differs in these two cases. To illustrate the differences, we have plotted the difference between the even and odd cases' frequency formulas in Figure 4.7 for all m values such that 0 < m < 80. When m > max(m e F , m o F ) = 65, the formulas are equivalent, and the frequency is identical for an even or odd number of trains. Before m o E , the frequency is higher with an odd number of trains, as demonstrated by Proposition 4.11. For all m, m o E ≤ m ≤ m e E , the slope in the frequency starts to flatten in the odd case, whereas it is still constant in the even case. Thus, the even case's frequency rises more quickly, and the difference diminishes to 0 beyond m e E until the line reaches the capacity. However, the maximum difference is about 0.20 trains per hour for approximately 43 trains in operation. In practice, this represents a negligible distinction in the headway between trains for passengers. As a result, for the remainder of this chapter, we do not distinguish between the even and odd cases and solely consider the simplest case, which is the even one.

Comparison of Different Services

Skip-stop policies aim to increase train speed on the line and reduce passenger wait times at the busiest stations served by all trains. The previous section discussed how the frequency of trains changes with the number m of trains. In this section, we aim to compare various parameters of skip-stop policies.

The primary factor affecting train frequency on the line is the services provided by the operator. The operator can modify two key parameters: the number of skippable stations and the stopping patterns. There are two primary stopping patterns: the alternating stopping pattern, where stations A and B alternate as skippable stations, CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 51

and the free assignment pattern, where two or more consecutive stations are served by the same service. We give tools to compare different services defined by the operator and emphasize the difference between a line operated with and without a skip-stop policy. The formulas for the congestion phase are the same regardless of the services performed by the train, because values of the s j are also the same. Thus, there is no difference in the frequency during this phase, and we focus our study on the differences in the free-flow and capacity phases. This section is structured as follows: firstly, we assess the impact of the number of skippable stations, while in Section 4.5.2, we evaluate the effect of the stopping pattern, with a specific focus on the number of consecutive stations served by the same service. Finally, in Section 4.5.3, we compare several scenarios of skip-stop policies to an all-stop one in order to give operator insights about the benefits of skip-stop policies.

Impact of the Layout and Number of Skippable Stations

When a train skips a station, it does not need to slow down or stop, which reduces its travel time, and when the train's travel time on the line changes, it affects the line frequency. Depending on the arrangement of the stations chosen, the impact on frequency can be different. Thus, we study the impact of the arrangement of skippable stations to evaluate the impact on the frequency of the line. To do this, we calculate the time saved by a train that does not stop at all stations on the line, excluding the terminus. We study in Figure 4.8 the percentage of total travel time this represents to evaluate each station's impact separately. At all stations, the speed at which trains enter the stations is about the same, as are the dwell times and the acceleration after departing the station. Thus, for all stations, a train saves about 100 seconds when it does not stop compared to a train 4.5. COMPARISON OF DIFFERENT SERVICES that stops, and the travel time for all stations decreases by about 2%. As a result, the choice of skippable stations has a similar impact on travel time and, therefore, on the frequency of the line.

B E R M A N P O R N A T R E U G A R B A S P A U H O T C H A L O U P A L T U I C O N C H A F R A G E O E T O A R G P O R L E S P O N E S P
On the other hand, the number of skippable stations on the line significantly impacts the line's frequency. Indeed, as the number of skippable stations increases, the speed of the trains also increases. In this section, we evaluate the frequency for different numbers of skippable stations, ranging from 2 to 19. Using the attendance levels given in [START_REF]Trafic annuel entrant par station du réseau ferré 2016[END_REF], the stations are sorted in ascending order. If the number of skippable stations is set to two, the two stations with the lowest attendance levels are selected. If the number is ten, the ten stations with the lowest attendance levels are selected, and so on. Note that we exclude the terminus for operational reasons. Finally, for each number of skippable stations, we calculate the average line frequency separately. The frequency of the line is shown in Figure 4.9 as a function of the number of trains in operation and the number of skippable stations.

In the figure, we also represent in blue the value m E beyond which the slope of the frequency changes, and in green m F the point after which the capacity is reached for each number of trains. In the congestion phase, the contour lines are vertical because regardless of the number of skippable stations, the s j value is constant for all j. However, in the free-flow phase, the contour lines are not vertical but slightly inclined as the number of skippable stations increases. Therefore, the frequency increases more rapidly as trains can move faster on the line due to the higher number of skippable stations. This trend is clearly visible in Figure 4.10, where the frequency is higher when the number of skippable stations increases.

However, the number of trains m E decreases as the number of skippable stations increases. This means that even if there is a greater increase, the moment when trains interact with each other and block on the line arrives earlier. the number m F is almost constant, showing that capacity is reached simultaneously regardless of the number of skipped stations. In Figure 4.10, the frequency for 2, 4, 6, 10, 14, and 18 skippable stations is given. On the x-axis we show the value of m 2 E , m 10 E , and m 18 E for 2, 10, and 18 stations. As the number of skippable stations increases, the value of m E decreases. However, the associated frequency value remains about constant. Regardless of the number of stations skipped, a threshold of the frequency f (m E ) exists above which the slope is decreasing. This bound depends on the line characteristics.

Number of Consecutive A or B Stations

A key factor for the frequency of a line operated with a skip-stop policy is the stopping pattern chosen by the operator. We have shown the different possibilities in Figure 1.2. The alternating stopping pattern (see Figure 1.2a), where stations A and B alternate on skip-stop stations, has been used in previous sections. However, any scheme called free assignment can be defined, as shown in Figure 1.2b. With a free assignment pattern, the operator freely chooses the arrangement of services on skip-stop stations. For example, service A can skip 8 stations, and service B only 2. However, with such an arrangement, the train's travel times of the services are not balanced, and the service with the longer travel time limits the average line frequency. The other service is slowed down, and the trains are blocked on different signals to ensure the safety constraint. Therefore, we only consider stop patterns with equivalent travel times, i.e., services with the same number of skipstop stations. With a fixed number of skip-stop stations, the operator can vary the number of consecutive skip-stop stations served by the same service:

• 1 consecutive station: the pattern for skippable stations is AB. It corresponds to an alternating stopping pattern.

• 2 consecutive stations: the pattern is AABB. There are two A stations followed by two B stations on skippable stations. This pattern repeats along all the skippable stations. • k consecutive stations: in this case we have k A stations followed by k B ones.

We define as ν ∈ {1, 2, 3, 4} the number of consecutive stations served by the same service, and we show the frequency in Figure 4.11.

0 m 1 E m 2 E m 3 E m 4 E 60 80 100
Number of trains m For each number ν ∈ {1, 2, 3, 4}, we show the value of m ν E and f (m ν E ) on the x and y axes, respectively. The value of m ν E decreases as the number of consecutive stations increases, and the number of trains beyond which the frequency slope starts to decrease is closer to the origin. However, when the number of trains is small, the frequency is approximately the same regardless of the stop pattern. In fact, each service skips the same number of stations with all patterns, and thus their travel times are equivalent. However, because a train stops at several consecutive skipstop stations when a faster train is blocked by the slower one over a larger section of the line, the travel time decreases for a longer period, and therefore, the number of trains m ν E is lower. As with the number of skip-stop stations, the number of trains beyond which the line capacity is reached is approximately the same for all four cases.

0 10 f (m 1 E ) f (m 2 E ) f (m 3 E ) f (m 4 E ) 40

Comparison of Several Scenarios with an All-Stop Policy

Skip-stop policies primarily aim to speed up trains on the line and decrease passenger waiting time at the most crowded stations, those served by all trains. The previous section explained the evolution of the train frequency as a function of the number m of trains and the different arrangements of the stations. In this section, we want to evaluate the gains or losses induced by the implementation of skip-stop policies. We compare several policies with a line operation where all trains stop at all stations. To make the comparison, we use the results found in [START_REF] Farhi | Traffic Modeling and Real-Time Control for Metro Lines. Part I -A Max-plus Algebra Model Explaining the Traffic Phases of the Train Dynamics[END_REF], and in CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 55 particular, Theorem 4.6 and Corollary 4.7, which give the asymptotic average train time-headway and frequency as functions of the number m of trains. This section is organized as follows: first, Section 4.5.3 describes several possible scenarios implemented on a linear metro line. Then, in Section 4.5.3, we visually analyze the scenarios' fundamental and commercial speed diagrams. Finally, in Section 4.5.3, we quantify the gains of the skip-stop policies over an all-stop policy.

Scenarios

Several scenarios are considered on Paris metro line 1.

1. The first scenario considers a low number of skippable stations, i.e., 6 stations and an alternate stopping pattern. In this scenario, the train's speed is increased, but the number of impossible origin destinations remains low.

2. In the second scenario, the number of skippable stations is doubled with still an alternate stopping pattern.

3. Finally, the last scenario considers a free assignment pattern for the skippable stations, with three consecutive stations served by the same service. In this scenario, the operator ensures that all passengers making short distances on the line can reach their destination without making a connection within the line because the origin and destination are not served by the same service.

Graphical Analysis

First, we visually compare the scenarios with the all-stop policy. Figure 4.12 represents the frequency and the commercial speed of the three scenarios and the all-stop policy. Both figures depict the all-stop policy with a black line and the blue, orange, and green lines the Scenarios 1, 2, and 3. Let us first observe the fundamental diagrams (Figure 4.12): the same pattern exists in the free flow phase. The colored curves move away from the black one before getting closer again. On the other hand, the point from which the two curves get closer is different, more or less distant from the origin. In Scenarios 1 and 3, when the curve approaches the line capacity, the gains become negligible, whereas, in Scenario 2, the gains remain important during the free-flow phase.

The gain is null during the capacity phase for all three frequencies and commercial speed scenarios. The segment limiting the frequency is before station Station, which is not a skippable station. Therefore, the skip-stop policy does not improve the line's capacity. The diagrams also show when the implementation benefits the operator and the passengers. For example, in Scenarios 1 and 3, when the gains become negligible, and the commercial speed is almost the same, the average travel time for passengers is equivalent, while passengers traveling from or to a skippable station have to wait for trains longer. Moreover, the more complex timetables reduce the readability for passengers. In the next section, we precisely calculate the gains for each number of running trains m and show how the point where the gain decreases is related to the scheme of the skip-stop policy.

Gains Quantification

Thanks to Theorems 4.3 and 4.6 and Corollaries 4.5 and 4.7, it is possible to quantify the gains (or losses) in terms of headway or frequency. The variables ∆h l σ (m) and ∆f l σ (m) give respectively the difference for the headway and frequency, with

∆h l σ (m) := h(m) -h l (m) (4.24) ∆f l σ (m) := f l (m) -f (m) (4.25)
∆h l σ (m) and ∆f l σ (m) are defined such that if they are positive, the skip-stop policy shows an improvement in the line operation, whereas if it is negative, then the skip-stop policy degrades the headway or the frequency. Figure 4.13 represents the evolution of ∆f l σ (m), ∀l ∈ {e, o} and ∀m such that 1 ≤ m ≤ 80, since beyond, the gain is constant and null. Indeed, the equations giving the frequency in the congestion phase are the same (f bw = (nm)/S = f l bw , ∀l ∈ {e, o} whether there is or not a skip-stop policy on the line). The solid lines and the dotted lines respectively correspond to l = e and l = o.

The gain in the capacity phase is constant and can be evaluated for both scenarios by looking at h min for the headway (Theorems 4.3 and 4.6) or f max for the frequency (Corollaries 4.5 and 4.7). ∀l ∈ {e, o}, ∆f l max = f l maxf max = 0. Now we consider the free-flow phase described in Section 4.4.2. During operation, the line is not operated at full capacity to keep some margins in case of disturbances. Thus, the number of trains running is below the capacity, and it corresponds to the free-flow phase in the fundamental diagram. In this phase, the gain depends on the number of running trains m and the services implemented by the operator. As we have seen in the traffic phase derivation, the free-flow phase is piecewise linear with a skip-stop policy, whereas the slope of the free-flow phase of a line with no skip-stop policy is constant. In Figure 4.13, we see that the variations in the slopes induce important variations in the gains. First, it increases before decreasing to the value calculated in the capacity phase, i.e., 0 for our case study. Using Corollaries 4.5

∆f o fw (m) = m T -min ψ αm + ψ T T o ψ (4.28) = max ψ m(αT -T o ψ ) + ψT T T o ψ , with α = 1 if ψ is odd α = 2 if ψ is even (4.29)
Using these equations, we can compute the number of trains for which the gain in frequency is maximum and the gain directly.

Proposition 4.12. ∀ψ 1 , ψ 2 , 0 ≤ ψ 1 < ψ 2 ≤ |O| such that T l ψ 1 < T < T l ψ 2 , and ψ 1 and ψ 2 correspond to the minimum in f l fw (m l * ), we have m e * and m o * the numbers of trains for which the gain is maximum respectively when the number of trains is even and odd.

1. For l = e m e * = ψ 2 T e ψ 1 -ψ 1 T e ψ 2 T e ψ 2 -T e ψ 1 (4.30) 2. For l = o m o * = ψ 2 T o ψ 1 -ψ 1 T o ψ 2 α 1 T o ψ 2 -α 2 T o ψ 1 , with α 1 = 1 if ψ 1 is odd α 1 = 2 otherwise α 2 = 1 if ψ 2 is odd α 2 = 2 otherwise (4.31)
and the maximum gain is given by ∆f e (m e * ) and ∆f e * (m o * ).

Proof. Taking the derivative of ∆f e fw and ∆f o fw , we obtain

1. (∆f e fw ) ′ = T -T e ψ T T e ψ
. The derivative is negative if T < T e ψ and positive if T > T e ψ . While T > T e ψ the gains increase, it starts to decrease when T < T e ψ . ∃ψ 1 , ψ 2 such that T e ψ 1 is the maximum value for which T > T e ψ 1 and T e ψ 2 is the maximum value for which T < T e ψ 2 . The maximum value is obtained at the intersection of the two lines m+ψ 1 T ψ 1 and m+ψ 2 T ψ 2

. We have . We have

m e * + ψ 1 T ψ 1 = m e * + ψ 2 T ψ 2 ⇔ m e * = ψ 2 T e ψ 1 -ψ 1 T e ψ 2 T e ψ 2 -
α 1 m o * + ψ 1 T ψ 1 = α 2 m o * + ψ 2 T ψ 2 ⇔ m o * = ψ 2 T o ψ 1 -ψ 1 T o ψ 2 α 1 T o ψ 2 -α 2 T o ψ 1
In Table 4.9, we report the critical values for the evolution of the gains for all the scenarios. ∀l ∈ {e, o}, m l E is the value from which the slope of the frequency in the free-flow phase starts to decrease, m l * the value for which the gain is maximum and m l F the end of the free flow phase.

Table 4.9: Critical values of the function of the gains on the line. Before m l E , the traffic on the line is fluid, and the frequency increases normally. From m l E and until m l * , the gains increase, but the operator should be careful because the trains might be stopped at inter stations on some line parts. In future work, we will study ways to avoid these delays. Note that in some cases, m l E and m l * coincide. After m l * , the gain starts to diminish. Depending on how close the number of trains is to m l F , the gains might not be beneficial enough to the operator and the passengers. Further study on travel time would also be performed to calculate the impact on the passengers' travel times. It is important to note that as train density increases on the line, the number of blockages and the unwanted waiting times between stations will also increase. As previously explained, this phenomenon should be carefully studied by operators. Finally, after m l F , the line's capacity is reached, and adding trains to the line only increases the unwanted stops between stations. Finally, the line performs better with the considered scenarios when the number of trains is even on the line; the characteristic points are farther from the origin. For example, in Scenario 1, we have m o E < 37 < 38 < m e E . Thus, going from 37 to 38 trains allows being again in the phase where the trains circulate freely on the line without small blockages and increase the frequency. For Scenario 2, similar observations can be made, but the numbers differ with m o E < 33 < 34 < m e E . Thus, the number of skippable stations and the stopping patterns change the characteristic 4.6. CONCLUSION values m o E and m e E . In general, the characteristic values are more interesting for the operator when for an even number of moving trains. The gains are slightly higher and as is the number of trains beyond which the slope of the line frequency decreases. However, further studies are necessary to verify if this is specific to our study case or general observation.

σ = 1 m l E ∆f l (m l E ) m l * ∆f l (m l * ) m l F ∆f l (m l F ) l = e
= 2 m l E ∆f l (m l E ) m l * ∆f l (m l * ) m l F ∆f l (m l F ) l = e

Conclusion

In this chapter, we provide several results. Firstly, we develop a model that allows us to represent a line that operates with a skip-stop policy. Our model considers two alternating and repeating services. The first part focuses on developing the model. Firstly, we develop the equations that allow us to give the constraints of the model. From these two constraints, we can write the train dynamics. We show that this train dynamics can be written linearly in the max-plus algebra. Using some results of the Max-plus algebra, we obtain the asymptotic average train time headway and the average train frequency and provide formal proof of our results. We show, in particular, that the headway and frequency depend on the parity of the number of trains running on the line. Moreover, we derive the fundamental diagram of the line, and we interpret all its traffic phases.

In the second part, we analyze the results by applying our model to an existing Paris metro line. The analytical results giving the frequency and average headway allow us to derive the fundamental diagram: the frequency or headway as a function of the number of trains running on the line. The diagram has three distinct phases: the free-flow phase, where the frequency increases with the number of trains, the capacity phase, which gives the maximum frequency or minimum headway; and finally, the congestion phase, where the frequency decreases with the number of trains increasing.

The free phase is piecewise linear: beyond a certain number of trains running on the line, the headway is reduced to the point that a train skipping a station may be too close to the one ahead of it. In this case, the train skipping the station must stop at a signal to ensure safety on the line.

We show that when the travel time of each service is well-balanced, the difference between even and odd cases can be neglected. Afterward, we study the impact of the number of stations that can be skipped or the different services that can be implemented by the operator. Finally, we compare different policies to a policy of all stops. We show that there exists a number of trains for which the gain in frequency is maximal.

However, this chapter focuses exclusively on the operator's point of view. It provides insights into the operational performance of the line when a skip-stop policy is implemented. In order to have a complete view of the impact of this policy on the line, we must also study the passengers' points of view. Indeed, their waiting time and travel time can be significantly changed. Additionally, in this chapter, we consider that the lower bounds on the train dwell times are the same for both services and are not affected by the skip-stop policy.

In the next chapter, we will modify our model to consider passengers' demand and services in the dwell times computations. On the other hand, we will study several criteria to measure the impact on the passengers of the line.

Chapter 5

Effect of the Passengers on a Two-Service Skip-Stop Policy

This chapter is a continuation of the work developed in the previous chapters. To complete the model, this chapter includes the point of view of passengers and their impact on the operation of the line. Indeed, in the previous chapter, we showed how frequency is improved with the skipstop policy, depending on the number of skippable stations or services implemented. However, the relevance of the policy can only be assessed by considering its impact on the line's passengers. Indeed, if frequency increases, but most passengers increase their travel time, then the policy's relevance needs to be investigated. Therefore, this chapter provides a discrete event model for a line operated with a two-service skip-stop policy. The model is described by two constraints giving the dynamics of the trains on the line. In addition, we also model the train dwell times as a function of the services defined by the operator and the passenger demand. Then, by linearly writing our model in the max-plus algebra, we provide analytical results with which we derive the fundamental diagram of the line. This diagram gives the average train time headway or frequency as a function of the number of trains running on the line. We also derive some indicators measuring the impact of a skip-stop policy on passengers. We show that when the number of trains running is sufficiently high, the increase in waiting time is offset by the decrease in time spent in the vehicle, thus improving the total travel time. Finally, we also compare the different demand profiles with the different travel behaviors of passengers, showing that the skip-stop policy particularly benefits passengers when there are many stations between their origin and destination.

The Model

In this chapter, we extend the model proposed in Chapter 4 by making the train dwell times dependent on the passenger flows. The constraints are similar to those developed in Chapter 4 and are detailed in Section 5.1.2. First, we explain how we model the passenger-dependant dwell times in Section 5.1.1 62 5.1. THE MODEL

Demand-Dependant Dwell Times

This section allows us to derive the formula for the train's dwell time w j at a station j. First, we give the formula for an all-stop policy and introduce the notations for the passengers' demand; see Table 5.1. Then, we detail how passenger demand and dwell times are changed in the case of the skip-stop policy; see Table 5.2.

All-Stop Policy Case

Passenger demand for the line is provided by the OD matrix λ. This matrix gives a demand profile, and the variable θ provides the demand level (or intensity variation) of this fixed profile. The variable θ represents the variation in demand that may exist over the days of the week. Indeed, from one day to the next, even if the profile remains identical, the number of passengers may vary. Each entry λ i,j gives the base arrival rate in passengers per second of passengers going from station i to station j for a 60-minute interval during all operations. Thus, the arrival rates are fixed and considered constant in this interval. For each station j, we can determine three indicators:

λ al j = i θλ i,j (5.1)
λ bo j = i θλ j,i (5.2)
λ in j = i l>j θλ i,l (5.3)
λ al j and λ bo j represent the passenger rates alighting and boarding at a station j. Besides, λ in j represents the rate of passengers in the train (excluding those alighting) at this station. The variable h gives the average headway between two trains. Thus, on average, the number of passengers boarding, alighting, and in the trains are given by the product of the rates and the average headway. We also define the variables α bo j and α al j , the number of passengers boarding and alighting per second. Therefore, the time for passengers to board and alight is given by N bo j /α bo j and N al j /α al j , respectively. However, the number of train passengers also influences the dwell times. When a train is crowded, the passengers staying on the train can obstruct those alighting and boarding the train. Therefore, there is in the dwell time a term considering these obstructions. The variable α in j gives the increase in seconds per passenger, and α in j N in j gives the time to add to the dwell time. When a train stops, there is a delay before the first passenger can board, and another delay between the moment the doors close and the train actually departs: it is defined as the technical time τ j . Finally, to compute the train's dwell time, we consider that passengers boarding follow those alighting and are uniformly distributed in the trains and on the platforms. We also consider the average train-time headway h for the computation, even if the headway between two trains is not precisely equal to the average value.

w j = τ j + θ λ al j α al + λ bo j α bo + λ in j α in h (5.8)
w j = τ j + θx j h (5.9) with x j = λ al j /α al j + λ bo j /α bo j + λ in j α in j , the passenger demand indicator at station j.

Skip-Stop Policy Case

For the skip-stop policy, the formula to evaluate the train's dwell time is identical; however, the indicator x j needs to be distinguished between x A j and x B j for the services A and B. Indeed, for the all-stop policy case, all the passengers can board the first train arriving at their origin station. When a line is operated with a skipstop policy, some passengers can board any train as their origin and destination are served by both services. Still, others need to board a train making a specific service as the origin, or the destination is only served by one service. We do not consider that the passengers staying on the platform are making the boarding longer. However, a new parameter α pl could be considered in a future extension to model the platform crowding.

One OD matrix per service The arrival rate of passengers from each origin i to destination j is provided by the OD matrix, denoted as λ i,j . Based on the train service, i.e., A or B, passengers arriving at a station are divided into two groups. We separate the arrival rates, λ A i,j and λ B i,j , for passengers traveling from origin i to destination j via trains A and B respectively. Multiple cases to consider in distinguishing between the matrices λ A i,j and λ B i,j .

1. ∀i, j ∈ AB. For this type of OD pair, the passengers can board any train. With arrival rate of passengers traveling from station i to station j with a train performing service p. ζ p j the proportion of passengers taking service p at station j, ∀j ∈ AB. λ al,p j sum of the passenger arrival rate alighting a train performing a service p at station j. λ bo,p j sum of the passenger arrival rate boarding a train performing a service p at station j. λ in,p j sum of the passenger arrival rate in a train performing a service p at station j. τ p j represents the technical time for the dwell time of a station j for service p. x p j := λ al,p j /α al j + λ bo,p j /α bo,p j + λ in,p j α in j , the passenger demand indicator at a station j for service p.

train A and B respectively, the arrival rates are given by λ A i,j = ζ A j • λ i,j and λ B i,j = ζ B j • λ i,j for services A and B.

2. In this second case, the origin and the destination are served by only one service, i.e., i and j ∈ P, and i or j / ∈ P. Passengers have to board a specific service to reach their destination. If i, j ∈ A, then λ A i,j = λ i,j and λ B i,j = 0, and if i, j ∈ B, then λ B i,j = λ i,j and λ A i,j = 0.

3. Finally, the last case corresponds to impossible origin destinations with a single train. The origin and destination are skippable stations and are not served by the same service. This forces passengers to make a transfer at an intermediate station i ′ where all trains stop. We have either i ∈ A, j ∈ B or i ∈ B, j ∈ A and i ′ ∈ AB. For i ∈ A, we add to the existing arrival rate λ A i,i ′ the arrival rate of the impossible OD λ A i,j , and we have λ B i,i ′ = 0. Furthermore, we have λ A i ′ ,j = 0, and similarly we add λ i,j to the arrival rate λ B i ′ ,j . For each of these original destinations, station i ′ is considered the same for all passengers; it corresponds to the station that allows passengers to reach their destination the fastest.

Dwell Times Computation To compute the dwell times of a line operated with a skip-stop policy, we use the same reasoning as Equations (5.7) to (5.9) but with the matrices distinguished with the services. The indicators on the arrival rates are now written, ∀p ∈ {A, B}. When the skip-stop policy is set, the average headway between two trains is also given by h. However, the matrices λ A and λ B give the arrival rates for a performing the service A or B. Yet, the average headway h corresponds to the headway between a train A and B. Therefore, the headway between two trains performing the same service is given by 2h. Finally, the dwell time w p j at a station j for the service p ∈ {A, B} is given by.

w p j = τ p j + θx p j 2h (5.14)
If a station j is not in A, the train A does not stop, and w A j must be equal to 0. With our distinguishing of the matrices, we have λ al,A j = λ bo,A j = 0 as the number of boarding and alighting passengers is 0. However, it is not the case that the third term λ in,p j α in,A j . Thus, the value of α in,A j is 0 if j / ∈ A.

α in,p j = α in , if j ∈ P 0, otherwise (5.15)

Constraints of the Train Dynamics

In Chapters 3 and 4, we developed the constraints to write out train dynamics. We considered a lower bound for the train's run, dwell, and safe separation times. However, in this chapter, the dwell times are now given as a function of the passenger demand. Therefore, we rewrite the constraints to consider this change and quickly remind the constraints principles.

1. The train travel time constraint: this first constraint ensures that the trains respect the speed limits, the technical time τ , and the dwell time. A train cannot depart a node j until it arrives at this node. Thus, the departure at a node j is given by the departure time of the same train at the node j -1 plus the travel time to reach j. The train performing the k th departure at node j performed the kb j th departure at node j -1. We distinguish the cases for both services and write the constraint as follows.

d k j ≥      d k-b j j-1 + t A j , if the train performs service A d k-b j j-1 + t B j , if the train performs service B (5.16) ⇔ d k j ≥      d k-b j j-1 + r A j + τ A j + w A j , if the train performs service A d k-b j j-1 + r B j + τ B j + w B j
, if the train performs service B (5.17)

2. The second constraint is called the safe separation time constraint. This constraint ensures safety on the line and avoids collisions by simulating the red state of the signal. For example, the departure at a node j cannot occur until 5.1. THE MODEL the next segment j + 1 is free. And the segment is free when the previous train (the k -bj th one) has departed plus a safe separation time. The constraint is written as follows.

d k j ≥ d k-bj+1 j+1 + s j+1 (5.18)
The safe separation time corresponds to a release time, i.e., the time necessary for a train to leave the segment after its departure. This release time is different if a train stops or skips a station. However, to simplify the model, we consider that the safe separation time is the same regardless of the service, and it is equal to the highest value between the two services. This constraint mainly influences the congestion phase, which is not the most interesting for operation.

Finally, the departure occurs as soon as the two constraints are satisfied. We obtain the followings train dynamics for all segments of the line; we have ∀j

d k j =        max d k-b j j-1 + r A j + τ A j + w A j , d k-bj+1 j+1 + s j+1 , if k corresponds to service A max d k-b j j-1 + r B j + τ B j + w B j , d k-bj+1 j+1 + s j+1 , if k corresponds to service B (5.19)

Formulation in Max-plus Algebra

In Sections 4.1.6 and 4.1.7, we explain how the Equation (5. [START_REF] Fan | Planning skip-stop services with schedule coordination[END_REF]) can be written in the max-plus algebra. See Section 2.4 for a review of the max-plus algebra.

Services and Parity of Departure

We can use a parity-based rule to determine when a train performs service A or B. Indeed, the services alternate cyclically, and a train doing service A on a node j is automatically followed by a train performing service B and reciprocally. The first train makes the k th with k odd (resp. even) the next one makes the k + 1 st departure with k + 1 even (resp. odd). We introduce the variables µ e j and µ o j , which are equal to A or B. If µ e j = A, a train making an even departure at node j performs service A on this segment, and we also have µ o j = B. We need to ensure that the services defined by the operator are respected by the trains on all the line nodes. Therefore, we set a rule at each node to define if an even departure corresponds to a train performing service A or B.

µ e j := A if j q=0 b q is even B otherwise (5.20) µ o j := B if j q=0 b q is even A otherwise (5.21)
With this rule, we ensure that a train performs the same service for the whole lap around the line. However, it can perform another service when passing through the terminus again. Thus, we can rewrite the train dynamics as a function of the parity CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 67 of the departure counts k, ∀j:

d k j =        max d k-b j j-1 + t µ e j j , d k-bj+1 j+1 + s j+1 , if k even max d k-b j j-1 + t µ o j j , d k-bj+1 j+1 + s j+1 , if k odd (5.22) ⇔ d k j =        max d k-b j j-1 + r µ e j j + τ µ e j j + w µ e j j , d k-bj+1 j+1 + s j+1 , if k even max d k-b j j-1 + r µ o j j + τ µ o j j + w µ o j j , d k-bj+1 j+1 + s j+1 , if k odd (5.23)

Model in Max-plus Algebra

Using the max-plus algebra and the parity rule, we rewrite Equations (5.22) and (5.23) as.

d k j =      d k-b j j-1 ⊗ t µe j ⊕ d k-bj+1 j+1 ⊗ s j+1 , if k even d k-b j j-1 ⊗ t µo j ⊕ d k-bj+1 j+1 ⊗ s j+1 , if k odd (5.24) ⇔ d k j =      d k-b j j-1 ⊗ r µ e j j ⊗ τ µ e j j ⊗ w µ e j j ⊕ d k-bj+1 j+1 ⊗ s j+1 , if k even d k-b j j-1 ⊗ r µ o j j ⊗ τ µ o j j ⊗ w µ o j j ⊕ d k-bj+1 j+1 ⊗ s j+1 , if k odd (5.25)
These equations are the same as those developed in the previous chapter, with the distinction that the dwell time is a function of the headway h and the demand indicator x. It is, therefore, possible to write similarly the Equations (5.24) and (5.25) using max-plus matrices.

d k =      Π 0 d k ⊕ Π 1 d k-1 , if k even Φ 0 d k ⊕ Φ 1 d k-1 , if k odd (5.26)
where

d k := d k 1 , . . . , d k n
is the vector giving the train departure times at all the nodes, and where the Max-plus matrices Π 0 , Π 1 , Φ 0 and Φ 1 are defined as follows.

(Π 0 ) (j,j-1) = t µ e j and (Φ 0 ) (j,j-1) = t µ o j if b j = 0 (Π 1 ) (j,j-1) = t µ e j and (Φ 1 ) (j,j-1) = t µ o j if b j = 1 (Π 0 ) (j-1,j) = (Φ 0 ) (j-1,j) = s j if bj = 0 (Π 1 ) (j-1,j) = s j if bj = 1
And, with Π := Π * 0 Π 1 and Φ := Φ * 0 Φ 1 , the train dynamics Equations (5.22) and (5.23) is written as follows.

d k =      Πd k-1 , if k even Φd k-1 , if k odd (5.27)

MAIN THEOREM

Finally, ∀k such that k is even, k -1 is odd and we have

d k = Πd k-1 = ΠΦd k-2 .
Finally, with Υ := ΠΦ, the train dynamics can be written as

d k = Υd k-2
(5.28)

Thanks to the steps above, we prove that the Equations (5.22) and (5.23) can be written linearly in the max-algebra. ∀k, the departure vector d k can be computed as a product of the departure vector d k-2 and the matrix Υ.

Main Theorem

In this section, we provide the average train-time headway in Theorem 5.1. It is obtained from the train dynamics Equation (5.28), and using the matrix properties. The variables used to derive the headway and frequency are given in Section 5.2.1. Then, we give the analytical results in Section 5.2.2

Theorem Variables

First, we detail the notations used in the Theorem 5.1 in Table 5.3. The average train time headway on a line depends on the number of running trains m, and on its parity. Indeed as explained in Chapter 4, trains always perform the same service when m is even, whereas trains change service every lap when the number of trains is odd. The two cases are differentiated by the exponent e for the even case and o for the odd case.

Then, the average train-time headway depends on the average train travel time, which can be divided into two parts, the train run time and the passengers' indicators variables. As explained in Section 4.2.1, these variables can be associated with one service, or be a combination of services A and B. The variable ψ gives the number of the service combinations, and the set I ψ gives the nodes at which there are these combinations. The set contains ψ distinct nodes sorted in the direction of the trains. When ψ = 0, we have I ψ = ∅, and there is no combinations. For ψ > 0, we take the same example as in Chapter 4, i.e. ψ = 4, I ψ = {i 1 , i 2 , i 3 , i 4 } and we take the example for variable R e I ψ as it is similar for R e I ψ , R e I ψ , and R e I ψ ; see Figure 4.1 for a schematic representation of the combinations. We have

R e p,I ψ = R p 1 i 1 ,i 2 + R p 2 i 2 ,i 3 + R p 1 i 3 ,i 4 + R p 2 i 4 ,i 1 .
The train run time is divided into four parts: between the nodes i 1 and i 2 , and between i 3 and i 4 , the average run time is given by services p 1 . Conversely, the service p 2 gives the average train run time between nodes i 2 and i 3 , and between nodes i 4 and i 1 .

Theorem and Corollaries

Using the variables developed in Table 5.3, we can write the theorem giving the average train time headway with demand-dependent dwell times.

Theorem 5.1. The train dynamics admit a stationary regime where the asymptotic average train time-headway of the line is given by h e and h o for respectively an even CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 69

:= R p , if ψ = 0 R p 1 i 1 ,i 2 + R p 2 i 2 ,i 3 + • • • + R p 2 i ψ ,i 1 , otherwise R o ψ := R A + R B , if ψ = 0 R p 1 o,i 2 + R p 2 i 2 ,i 3 + • • • + R p 2 i ψ ,o , otherwise X e p,I ψ := X p , if ψ = 0 X p 1 i 1 ,i 2 + X p 2 i 2 ,i 3 + • • • + X p 2 i ψ ,i 1 , otherwise X o p,I ψ := X A + X B , if ψ = 0 X p 1 o,i 2 + X p 2 i 2 ,i 3 + • • • + X p 2 i ψ ,o
, otherwise S := j s j , the sum of all the safe separation times.

and an odd number m of trains:

h e (m, θ) = max{h e fw,ψ , h min , h bw } (5.29) h o (m, θ) = max{h o fw,ψ , h min , h bw } (5.30) with h e fw,ψ = max ψ,p,I ψ {R e (p,I ψ ) /(m + ψ -2θX e (p,I ψ ) )}, h o fw,ψ = max ψ,p,I ψ {R o (p,I ψ ) /(m + ψ -2θX o (p,I ψ ) )}, h min = max j {(r A j + τ A j + r B j + τ B j + 2s j )/(2 -2θ(x A j + x B j
))}, and h bw = S/(nm).

Proof. One of the max-plus matrix Υ properties is its eigenvalue. Indeed, it corresponds to the average growth rate of the system, which, in our case, can be interpreted as the average train time headway. The matrix has an associated graph G(Υ) with arcs corresponding to the non-zero values in the matrix, and the weight of these arcs are the values of the non-zero entries. Finding the eigenvalue comes down to finding the maximum cycle mean of the graph G(Υ). The proof for the 5.2. MAIN THEOREM cycle is provided in Appendix A and gives the following results:

h e = max          max ψ,p,I ψ R e (p,I ψ ) +h e X e (p,I ψ ) m+ψ max j r A j +τ A j +r B j +τ B j +h e (x A j +x B j )+2s j 2 S n-m (5.31)
We need to solve the implicit formula given by the first two terms of the equation to obtain the average train-time headway. First,

h e = max ψ,p,I ψ R e (p,I ψ ) + h e X e (p,I ψ ) m + ψ (5.32) ⇔ h e -max ψ,p,I ψ R e (p,I ψ ) + h e X e (p,I ψ ) m + ψ = 0 (5.33) ⇔ min ψ,p,I ψ h e (m + ψ -X e (p,I ψ ) ) -R e (p,I ψ ) m + ψ = 0 (5.34) ∀(m + ψ) > X e (p,I ψ ) , the function f ψ (h) = (h(m + ψ -X e (p,I ψ ) ) -R e (p,I ψ ) -S (I ψ ) )(m + ψ)
is increasing and bijective ∀ψ and thus min ψ,p,I ψ f ψ (h) is also increasing and bijective. Thus, there exist a unique h such that min ψ,p,I ψ f ψ (h) = 0 and it is given by max ψ,p,I ψ f -1 ψ (0). We have

f -1 ψ (y) = (y(m+ψ)+R e (p,I ψ ) +S (I ψ ) )/(m+ψ-X e (p,I ψ ) ) ⇔ max ψ,p,I ψ f -1 ψ (0) = h e fw . Similarly, max j r A j + τ A j + r B j + τ B j + h l (x A j + x B j ) + 2s j 2 = h l (5.35) ⇔ min j h l (2 -x A j + x B j ) -(r A j + τ A j + r B j + τ B j + 2s j ) 2 = 0 (5.36)
Using the same arguments, ∀(x A j + x B j ) < 2, h l = max j f -1 (0) = h l min . Corollary 5.2. The asymptotic average train time-frequency of the line is given by f e (m) and f o (m) for respectively an even and an odd number m of trains:

f e (m, θ) = min f e fw,ψ , f min , f bw (5.37) f o (m, θ) = min f o fw,ψ , f min , f bw (5.38) with f e fw,ψ = max ψ,p,I ψ {(m + ψ -2θX e (p,I ψ ) )/R e (p,I ψ ) }, f o fw,ψ = max ψ,p,I ψ {(m + ψ - 2θX o (p,I ψ ) )/R o (p,I ψ ) }, f max = 1/
w e j (m, θ) = (τ A j + τ B j )/2 + θ(x A j + x B j )h e (m, θ) (5.39) w o j (m, θ) = (τ A j + τ B j )/2 + θ(x A j + x B j )h o (m, θ) (5.40)
Proof. Directly from Theorem 5.1 and w p j = τ p j + x p j 2h, ∀p ∈ {A, B}.

CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 71

Passengers Indicators

Before applying our model to the Paris metro line one, we detail the quantifiable impacts of the skip-stop policy implementation on the passengers. We do not consider any inconveniences resulting from increased complexity in readability. Additionally, we assume that the demand for the line remains constant despite any changes in its operation, and passengers needing to travel between stations not served by the same service follow the same route. For a passenger with an origin station i ∈ A (or B) and a destination station j ∈ B (or A), a connection must be made at a station i ′ ∈ AB to reach its destination. We assume that this connection is made at the station minimizing the travel time.

We evaluate the impact on passengers according to two main aspects. First, we compute the passengers' travel time in Section 5.3.3, which is the sum of the waiting and in-vehicle times. They are respectively given in Sections 5.3.1 and 5.3.2. Then, we study passengers' comfort by examining the number of passengers on trains in Section 5.3.4. We compare all these indicators to the line operated with an all-stop policy. The necessary notations to compute these different indicators are detailed in Table 5.4. We aim to compare the line's performance with and without the skipstop policy. We also differentiate between the skip-stop and all-stop policy variables using the superscript s on the skip-stop variables. Table 5.4: Notations for the computation of the indicators. The variables with and without the exponent s correspond to the skip-stop and all-stop policies, respectively.

All-stop Skip-stop Description w j w s j the dwell times at station j; ω i,j ω s i,j

the waiting times of passengers going from i to j; R i,j R s i,j

the in-vehicle times of passengers going from i to j; T i,j

T s i,j

the travel times of passengers going from i to j; ρ j ρ s j the number of passengers on platform j; σ j σ s j the number of passengers in the trains after the departure at station j; h(m, θ) h s (m, θ) the average train time headway for a given m and θ;

The Average Waiting Time

Let us first give the formulas for the average waiting time of passengers. We consider that the passengers arrive at the stations uniformly, regardless of the timetable. On mass-transit lines operated with a high frequency, it is reasonable to assume that passengers arrive uniformly without looking at the timetable. We study the two ways of operating the line.

• For an all-stop policy, all passengers can board the first train that arrives. With a uniform arrival rate, the average waiting time for a passenger is half the headway for all origin destinations. ω i,j = h(m, θ)/2, ∀i, j ∈ S (5.41)

• The passengers' waiting time with a skip-stop policy depends on their origins and destinations. Some passengers may board the first arriving train, while others might have to wait for a specific service. There are three different cases to be considered:

1. Passengers traveling to and from stations where all trains stop can board the first arriving train, resulting in an average waiting time of half the headway, and ∀i, j ∈ AB

ω s i,j = h s (m, θ)/2 (5.42)
2. In the second case, passengers must board a specific train. Two possibilities exist either the origin or the destination (∀i ∈ P and ∀j ∈ AB, or ∀i ∈ AB and ∀j ∈ P), or both the origin and destination are skippable stations, served by the same service (∀i, j ∈ P). The headway between two trains performing the same service is 2h s . Thus the average waiting time is given by.

ω s i,j = h s (m, θ) (5.43)
3. The last case is for passengers traveling from a station served by only one service to a station served exclusively by the other service. They must transfer at station i ′ ∈ AB to reach their destination. The waiting time is divided into two parts: passengers have to wait at the origin station, then at the transfer station, they have to wait for the departure of the train (i.e., its dwell time given by x p i ′ h s ) they were on, and then for the next train that serves their destination. The waiting time is given by:

ω s i,j = (2 + x p i ′ )h s (m, θ) (5.44)
The dwell time at the station i ′ is given by h

s x p i ′ , with p = A if i ∈ A and p = B if i ∈ B.
Using Equations (5.41) to (5.44) and the OD matrix of passengers' arrival rates, we can compute the average waiting time for all the passengers:

ω(m, θ) = i j θλ i,j ω i,j (m, θ) i j θλ i,j = h(m, θ)/2 (5.45) ωs (m, θ) = i j θλ i,j ω s i,j (m, θ) i j θλ i,j = i j λ i,j ω s i,j (m, θ) i j λ i,j (5.46)

The Average In-Vehicle Time

The in-vehicle time is the other part of the total passengers' travel time and refers to the duration they spend inside the trains. In-vehicle is calculated by adding the train's run and dwell times at each station along the route (except the destination station's dwell time). The run time between stations i and j is determined by the variables R i,j and R s i,j for lines operating with and without a skip-stop policy. In the former case, all passengers have the same run time, while in the latter, the run time depends on the train service each passenger is on for the same OD. CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 73

• For the line with an all-stop, the in-vehicle time from station i to station j is calculated as.

R i,j (m, θ) = j-1 q=i+1
(r q + θx q h(m, θ)) + r j (5.47)

• For the skip-stop policy, the three cases depending on the passengers' origin and destination, need to be distinguished.

1. ∀i, j ∈ AB: in this case, passengers board the first train arriving at platform i, and the in-vehicle time depends on the train and the passenger boards. Since passengers are assumed to be equally distributed between trains A and B, the in-vehicle time from i to j is the average between the two services, and it is given by

R s i,j (m, θ) = j-1 q=i+1 (r A q + θx A q 2h s (m, θ)) + r A j + j-1 q=i+1 (r B q + θx B q 2h s (m, θ)) + r B j /2
(5.48)

2. ∀i, j ∈ P, or ∀i ∈ AB, j ∈ P, or ∀i ∈ P, j ∈ AB. In this case, the passenger can only board one train serving the origin and destination.

R s i,j (m, θ) = j-1 q=i+1
(r p q + θx p q 2h s (m, θ)) + r p j (5.49)

3. ∀i ∈ P, ∀j ∈ P. The passengers need to take a train to reach platform i ′ ∈ AB to connect to platform j. The in-vehicle time is divided into two parts: the time in the train performing service p to reach station i and the time in the train doing service p to reach station j.

R s i,j (m, θ) = i ′ -1 q=i+1 (r p q + θx p q 2h s (m, θ)) + r p i ′ + j-1 q=i ′ +1 (r p q + θx p q 2h s (m, θ)) + r p j (5.50)
The average in-vehicle times for the line operated with and without a skip-stop policy are defined by R and Rs , such that:

R = i j R i,j λ i,j i j λ i,j
(5.51)

Rs = i j R s i,j λ i,j i j λ i,j (5.52)

The Average Travel Time

Now that we have the average wait and in-vehicle times, we can calculate the passengers' travel time. The travel time for each origin-destination pair is the sum of the wait time and in-vehicle time. Hence, we can express the travel time for the all-stop and skip-stop policies and the difference between the travel times as T i,j , T s i,j , and ∆T (m, θ), respectively.

T i,j (m, θ) = ω i,j (m, θ) + R i,j (m, θ) (5.53) T s i,j (m, θ) = ω s i,j (m, θ) + R s i,j (m, θ) (5.54)
∆T i,j (m, θ) = T i,j (m, θ) -T s i,j (m, θ) = ∆ω i,j (m, θ) + ∆R i,j (m, θ) (5.55)
As for the waiting time and the in-vehicle time, we can evaluate the average travel time for all line passengers and the difference with the all-stop policy with the following formulas.

T = i j T i,j λ i,j i j λ i,j
(5.56)

T s = i j T s i,j λ i,j i j λ i,j (5.57)
∆T = T (m, θ) -T s (m, θ) = ∆ω(m, θ) + ∆R(m, θ) (5.58)
To have a gain in the average travel time for passengers, the saved run time must be greater than the time lost due to the increase in the waiting time, i.e., ∆ω(m, θ) < ∆R(m, θ).

The Number of Passengers on Trains

During peak hours, overcrowding is a common problem on congested train lines, and a possible solution is to implement a skip-stop policy. However, this study assumes an unlimited train capacity, implying that all passengers can board the trains.

The number of passengers on trains after departure from the station j is given by the variables σ j and σ s j for the all-stop and skip-stop policies, respectively. For each service of the skip-stop policy, the number of passengers σ A j and σ B j in trains is different, as it depends on the demand of each service.

σ j (θ) = h(θ) i≤j≤l θλ i,l (5.59)
σ p j (θ) = 2h s (θ) i≤j≤l θλ p i,l , ∀p ∈ {A, B} (5.60)
The variable σ s j represents the mean passenger count in trains A and B, which is calculated as σ s j = (σ A j + σ B j )/2. Equation (5.61) gives the difference between the number of passengers.

∆σ j = σ j -σ s j . (5.61)
CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 75

Review of the Analytical Results for the All-Stop Policy

Before deriving some indicators to evaluate the impact of a skip-stop policy on the passengers, we quickly review the results obtained in [START_REF] Farhi | A discrete-event model of the train traffic on a linear metro line[END_REF]. With these results, we can compare the line's operations.

Theorem 5.4. [22, Theorem 3.2] If ∀j, x j < 1, and if j x j < m, then, the train dynamics with h(m, θ) = max {h fw , h min , h bw } (5.62)

with h fw = j (r j + τ j )/(mθ j x j ), h min = max j {(r j + τ j + s j )/(1θx j )} and h bw = j s j /(nm).

Corollary 5.5. [22, Corollary 3.3] Under the conditions of Theorem 5.4, the average asymptotic train frequency f is given as follows.

f (m) = min {f fw , f max , f bw } (5.63)
with f fw = (mθ j x j )/ j (r j + τ j ), f max = 1/h min and f bw = (nm)/ j s j .

Corollary 5.6. [22, Corollary 3.4] Under the conditions of Theorem 5.4, the average asymptotic dwell times

w j (m, θ) = τ j + x j h(m, θ) (5.64)
The variables r j , τ j , and s j without exponent correspond to the characteristic times when the line is operated with an all-stop policy, and all trains stop at all stations.

The Traffic Phases at the Steady State

We can apply our model to a real network line, the Paris metro line 1, as in Chapter 4. This section aims to see the effect of the level of demand θ on the average train time headway between and frequency; therefore, we consider a fixed demand profile. In addition, this section focuses on the operator's point of view by studying the line frequency with the fundamental diagram of the line. Finally, we provide some mathematical formulas describing these diagrams to help operators better understand the physics of traffic.

In Section 5.6.1, we detail the rule to select the skippable stations according to the demand profile. This section uses the same rule based on the number of passengers boarding and alighting at each station: the 12 less crowded ones are considered skippable, and an alternating stopping pattern (see Figure 1.2) is implemented to obtain our results. We can represent in Figure 5.1 the analytical results on the fundamental diagram for the skip-stop policy of the Paris metro line 1. The fundamental diagram illustrates the average train frequency on the line as a function of the number of running trains m and the demand level θ and is constructed using the formulas obtained in Corollary 5.2. The formulas consider the train's run times, the demand profile, and the demand level parameters. In Figure 5.1, the threedimensional representation of the fundamental diagram is given as a function of the number m of running trains and the demand level θ. This visualization method 5.5. THE TRAFFIC PHASES AT THE STEADY STATE allows the phases of the line to be observed distinctly. Three characteristic phases exist for a given demand level (see also Section 4.4.2). The first phase corresponds to the free-flow phase, where the frequency grows as the number of trains increases. The second phase, the capacity phase, is defined as the line's maximum achievable frequency: there is a segment where the time required for trains to leave this segment limits the entire line's frequency. Finally, the congestion phase occurs when the number of trains on the line is too high, leading to congestion. In this latter phase, a train that has to wait for the previous train to leave the next segment obstructs another train behind it, and so on. On Figure 5.2, we represent the evolution of the line capacity as a function of the demand level θ to see the effect of the demand level on the line's capacity; the maximum frequency decreases as the demand level increases. It is a piecewise linear function of the demand level θ that can be divided into three parts. First, ∀θ < 1.82, the segment giving the maximum frequency is a signal between two stations. For this segment j, the dwell times w A j , w B j , and the technical times τ A j , τ B j are equal to 0. Thus, the maximum frequency is given by (r A j + r B j + 2s j )/2, which is constant regardless of the value of θ. For 1.82 ≤ θ < 7.25, the segment giving the line's capacity is the station La Defense. Here, both the demand indicator and the run times impact the line capacity; the increase of θ decreases the maximum frequency as the dwell time increase with the demand indicator. Finally, ∀θ ≥ 7.25, the station Esplanade limits the frequency. The station has the highest value of the indicators x A j and x B j , and the dwell time dominates the other values in the computation of the maximum frequency f max . Finally, θ ≥ 10.1, and beyond this value, the theorem conditions are not respected and the frequency is null. the line for the given demand profile.

min j 2(1 -θ(x A j + x B j )) r A j + τ A j + r B j + τ B j + 2s j ≥ 0 ⇔ θ ≤ 1/ min j x A j + x B j (AB)
• Finally, the line (BC) gives the maximum number of trains the operator can set on the line.

min j n -m S ⇔ m ≤ n (BC)
The other points in Figure 5.4 correspond to the intersection of the different traffic phases of the line. We have the following two propositions.

Proposition 5.7. The maximum number of trains on the line before reaching the line capacity is given by m e D and m o D for an even and an odd number of trains.

m l D (θ) = max ψ R l ψ f max (θ) + 2θX l ψ (θ) -ψ (5.65)
Proof. ∀ψ, θ, l ∈ {e, o}, f l ψ (m) = (m + ψ -2θX l ψ )/R l ψ are increasing and bijective as a function of m. Therefore, ∀l ∈ {e, o}, min ψ f l ψ (m) is increasing and bijective as a function of m. Then we have:

m l F := max{m, min ψ f l ψ (m) ≤ f max }, by definition = m, such that min ψ f l ψ ( m) = f max = max ψ (f l ψ ) -1 (f max ) Thus, m l D (θ) = max ψ R l ψ f max (θ) + 2θX l ψ (θ) -ψ
Proposition 5.8. The number m E of trains corresponding to the end of the capacity phase is given by m

E (θ) = n -Sf max (θ) (5.66)
CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 79

Proof. Directly from Theorem 5.1 and Corollary 5.2, we have:

f max (θ) = (n - m G )/S ⇔ m E = n -Sf max (θ)
By using Proposition 5.7, we can derive the lines (D 1 D 2 ), (D 2 D 3 ), and (D 3 A) to represent the maximum number of trains that can run on the line before reaching its capacity. The points D 2 and D 3 correspond to the segment change where the maximum achievable frequency is obtained. Similarly, Proposition 5.8 provides the lines (E 1 E 2 ), (E 2 E 3 ), and (E 3 B), which indicate the number of trains beyond which the line enters its congestion phase. ∀θ < 1.82, the segment giving the capacity is not a station but a signal between two stations. As mentioned above, the maximum frequency is constant for signals between stations but the slope of the frequency decreases. Thus, the number of trains before reaching the line capacity increases.

This section focuses on the operator's point of view, while the following section concentrates on the passengers' point of view. Lines are always operated with a number of trains corresponding to the free-flow phase. Indeed, after the line capacity adding trains would neither enhance the frequency nor the transport capacity. Hence, in Section 5.6, we restrict our analysis to the free-flow phase.

The Effect of the Skip-Stop Policy on the Passengers

Now that we have derived and analyzed the main analytical results of a skip-stop policy with demand-dependent dwell times, we focus our study on the passengers' point of view. The frequency improvement for the operator is essential, but as we showed in Chapter 4, the number of skippable stations should be increased to maximize the gains. However, a skipped station increases the passengers' waiting time, and their travel times can increase despite the improved run times. Therefore, we compute several indicators to measure the passengers' gains and losses. These indicators are developed in Section 5.3. First, in Section 5.6.1, we study two different origin-destination matrices corresponding to two demand profiles. Then, we study the impact of the demand profiles, and finally, we compute the indicators. In this section, we look at multiple values of the demand level θ, but to make the results clearer, we only show the values ∀θ ≤ 3 and depict mainly the results for θ = 1, θ = 2, and θ = 3.

OD Matrix and Skippable Stations

The demand profiles

It is important to select the skippable stations so that the number of passengers traveling from or to a skippable station is lower than a defined threshold. We study two different demand profiles denoted as λ 1 and λ 2 . They are represented in Figures 5.5a and 5.5b. The arrival rates are identical for these two matrices, but the travel demand profile differs.

Although the overall number of passengers in the system remains unchanged, the number of stations that passengers travel through may vary. In Figure 5.5, the arrival rates of each origin-destination i, j are represented with colored squares. The color of the squares darkens as the arrival rates increase. With the first demand profile λ 1 (Figure 5.5a), the darker squares are located near the diagonal, showing short travel for the passengers. However, with the second demand profile λ 2 (Figure 5.5b), the travel distance is longer, and the squares are lighter near the diagonal. We measure the number of stations each passenger travels through between their origin and destination, with a minimum count of 0 when passengers reach the next station and a maximum of 23 for trips between one terminus and the other. In Figure 5.6, the number of passengers is inversely proportional to the number of stations traveled. Over half of the passengers travel through less than five stations between their origin and destination, with the highest count for those reaching the nearest station. In contrast, Figure 5.7 shows that the number of passengers is more evenly distributed according to the length of their trip.

C d v B ér S M P V N a t . R D G L B a s . S P H d v C h a . L o u . P R T u i C o n . C E R o o . G V C D G A r g . M a i
C d v B ér S M P V N a t . R D G L B a s . S P H d v C h a . L o u . P R T u i C o n . C E R o o . G V C D G A r g . M a i

Skippable Stations

We can determine the rule to select the skippable stations. Two constraints exist: first, a terminus can not be a skippable station. The second constraint is on readability for passengers -the station must be skippable in both directions. The rule is defined as follows. The number of passengers going from or to skippable stations must be lower than a threshold compared to the total number of passengers. The total number of passengers is given by N p := i j λ i,j and the number of passengers going from or to skippable stations is given by N s := i∈P j∈P λ i,j . Finally, the ratio N s /N p must be lower than the threshold κ, i.e., N s /N p < κ.

For each station j, we have the sum of the passengers with destination j and the passengers with origin j, i.e., i λ i,j + i λ j,i . The stations are then sorted in ascending order, and the skippable stations are the less crowded. For our case study, we set the threshold as κ = 0.5. For the two demand profiles λ 1 and λ 2 , the number of skippable stations equals 12. However, the skippable stations are not the same:

• For λ 1 , the stations are the following: Louvre-Rivoli, Tuileries, Argentine, Bérault, Saint-Paul, George V, Les Sablons, Hotel de Ville, Palais-Royal, Porte de Vincennes, Pont de Neuilly, Saint-Mandé.

• and for λ 2 they are: Argentine, Louvre-Rivoli, Tuilerie, Palais-Royal, Les Sablons, George V, Pont de Neuilly, Porte Maillot, Concorde, Franklin D. Roosevelt, Saint-Paul, Champs-Elysées.

In the first case, the stations are linearly spaced on the line, with skippable stations alternating with mandatory stations. In the second case, from stations Saint Paul to Pont de Neuilly, there are 15 stations, and 12 of them are skippable. It shows that many passengers travel from one end of the line to the other.

Impact of the Demand Profile on the Line Operation

Before computing the passengers' indicators developed in Section 5.3, we study the average train time headway for the two demand profiles λ 1 and λ 2 and compare them to a line operated with an all-stop policy. Indeed, the headway directly impacts the passengers as it is included in the computation of the passengers' waiting and invehicle times. First, we compare the frequencies of the two demand profiles, where we have 12 skippable stations in both cases. This comparison allows us to assess the effect of demand profiles on the operator when implementing a skip-stop policy. The analytical frequencies are shown in Figure 5.8 for a fixed demand, with θ = 1.

The frequencies for the two demand profiles λ 1 and λ 2 are indicated by solid blue and green dashed lines. Although the frequency is slightly lower for the second profile, the difference is minimal, with a maximum difference of about 0.7 trains per hour. For the operator, the demand profile does not significantly influence the results regarding frequency.

Furthermore, we can also examine the headway differences between skip-stop and all-stop policies. Figures 5.9 and 5.10 illustrate the headway variation based on the number of running trains for two different demand levels. Additionally, Table 5.5 provides different values for three train counts.

The headway is higher for the second demand profile, mainly when the number of trains is low. However, the two figures become quite similar as we approach the line's capacity. Moreover, in Table 5.5, for m=50, the headway differences for the two demand profiles are almost identical. However, when m=20, the difference is more significant, especially when the demand level is high. Table 5.5: Difference between average analytical train time headway with and without the skip-stop policy.

Impact of the Skip-Stop Operation on the Passengers

We now compute the indicators developed in Section 5.3 for both demand profiles λ 1 and λ 2 . We compare the line operated with and without the skip-stop policy for each indicator and demand profile. Moreover, we also show several levels of demand θ. Also, in Tables 5.6 to 5.9, we give the precise number for the indicators for three numbers of running trains, m = 20, m = 35, and m = 50. The last number corresponds to almost the line's capacity, and the two others correspond to off-peak and peak-hour numbers. In Table 5.6, we give the average train-time headway for each of the number of trains, the level of demand θ, and for the all-stop and skipstop policies. For the all-stop case, the waiting time is directly given by dividing the headway by two.

The Average Waiting Time

Let us first evaluate the average waiting time of passengers. We recall that we consider that the passengers arrive at the stations uniformly, regardless of the timetable. Whether for λ 1 or λ 2 , the average waiting time for passengers increases with the skip-stop policy. Even though passengers traveling to and from a mandatory station see their waiting time decrease, all other passengers must wait longer. Furthermore, the time lost by some passengers is not compensated by those who gain time. The proportion of these passengers represents only half of all passengers, meaning the other half loses time. We can compute the difference between the waiting time of the passengers with and without the all-stop policy with ∆ω = ωωs .

We give the results of this difference ∆ω in Table 5.7 for all values of θ and m = 20, m = 35, and m = 50. The gap narrows when the number of trains increases. We differentiate between passengers traveling to and from mandatory stations, who will save time, and others with a skippable station as origin and/or destination. As the gap in the average train time headway between the two policies narrows, on the one hand, the waiting time of passengers who need to make a transfer to reach their destination decreases. On the other hand, the time saved by passengers traveling to When the number of trains is low, passengers traveling to and from a location served by two different services lose a lot of time. They have to wait a long time at the origin and then at the intermediate station where they transfer. Their waiting time adds considerably to the average waiting time for all passengers. As the number of trains increases and the interval between trains decreases, these passengers can significantly reduce their waiting time, thus reducing the gap in waiting time between the two policies.

On the other hand, the gap is smaller for the λ 2 demand profile than for the λ 1 profile. Indeed, the percentage of people traveling to and from a mandatory station is slightly higher for λ 2 . The average intervals are similar for both demand profiles, so the waiting time is lower for λ 2 .

The Average In-Vehicle Time

The in-vehicle time refers to the duration passengers spend inside trains and is an essential component of their total travel time. It is calculated by considering the train's run and dwell times at each station along the route, excluding the dwell time at the destination station. Similarly to waiting time, we analyze the in-vehicle times for both all-stop and skip-stop policies using the demand profiles λ 1 and λ 2 (shown in Figures 5. [START_REF] Corman | A Review of Online Dynamic Models and Algorithms for Railway Traffic Management[END_REF] profiles. Passengers benefit from time savings as trains do not stop at all stations. Their travel time is shortened by eliminating the need for trains to slow down and stop at skippable stations. The most significant advantage lies in reducing dwell time, as deceleration and acceleration times become less significant. The dwell time is directly influenced by the demand indicator x j at each station. The skip-stop policy decreases the train time headway between trains, resulting in comparable demand indicators. Consequently, the dwell time at mandatory stations decreases, allowing trains to save time by skipping some stops and reducing the overall invehicle time for passengers. Ultimately, as the number of trains increases and the gap between headways for the all-stop and skip-stop policies narrows, the difference between in-vehicle times becomes more pronounced.

Comparing the in-vehicle times for the two demand profiles, λ 2 shows higher values. For instance, with m = 50 and θ = 1, the average in-vehicle time for passengers is approximately 380 seconds for λ 1 , whereas it is around 680 seconds for λ 2 . This difference is explained by the fact that the second demand profile involves longer travel distances for passengers, with origins and destinations further away than the first demand profile. Consequently, the distance between the origin and destination logically influences the in-vehicle time. Furthermore, the benefits of the skip-stop policy are more pronounced with the second demand profile, as passengers are more likely to encounter skippable stations and save time during their journey.

The Average Travel Time

Finally, we can calculate the passengers' travel time. The travel time for each origindestination pair is the sum of the waiting and in-vehicle times. Hence, we can express the travel time for the all-stop and skip-stop policies and the difference between the travel times for each origin-destination or all passengers with Equations (5.53) to (5.58). First, we focus on the average travel time for all the passengers.

The Average Travel Time for All Passengers First, we are interested in the passengers' travel time in the system, so we calculate the average travel time for passengers, and we can compare this average for the cases with and without a skipstop policy. Then, we represent the evolution of the average travel time for both demand profiles, with the number of trains ranging from 15 to 55 and three different demand levels in Figures 5. [START_REF] Daganzo | An Analytical Approximation for the Macroscopic Fundamental Diagram of Urban Traffic[END_REF] The formula to determine the system gain is given by ∆T = ∆ω + ∆ R (Equation (5.58)), which means that the increase in the passengers' waiting time must be less than the time they are gain in the vehicles to observe a positive gain. For λ 1 Table 5.9: Difference in the average travel time in seconds. and θ = 1 or 2, the average travel time from all-stop to skip-stop increases when the number of trains is small. The time passengers gain in the trains is insufficient to compensate for the time lost by those waiting longer. For θ = 3, there is a slight improvement in travel time, but it remains relatively low. In Table 5.9, we can see that for m = 50, which corresponds to a train time headway of about 75 seconds, passengers lose an average of 5 seconds, gain nothing, or gain approximately 6 seconds for demand levels 1, 2, and 3. On the other hand, for the second demand profile, there is a gain for passengers regardless of the number of trains and the demand level. This gain is explained by the fact that the time saved by passengers thanks to the reduction in time spent on trains more than offsets the increase in waiting time. Furthermore, for a demand level of 1, the gain is almost constant regardless of the number of trains, demonstrating a clear advantage regardless of the headway chosen by the operator.

The Travel Time per OD We now examine the time gained or lost for each origin-destination pair to better understand the disparities based on origin-destination pairs. To do this, we set the following values to represent our results: m = 50 and θ = 1. In Figure 5.17, we represent the time gained or lost for each origindestination pair in a heatmap. Figures 5.17a and 5.17b respectively represent both demand profiles λ 1 and λ 2 . We can clearly see the differences in skippable stations in these figures. The red or violet squares indicate an origin-destination pair where passengers lose time, while the blue or green squares indicate pairs that improve passenger travel time. Skippable stations can be identified by the rows or columns in the figure with a dominant red color. In the first case, these rows and columns CHAPTER 5. EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 89 are separated by others, while in the second case, these rows are consecutive toward the middle of the row. Furthermore, the closer the two skippable stations are, the more significant the time lost. Indeed, changing trains causes a significant loss of time, and sometimes it has to be done further away from the destination, resulting in an increase in travel time in addition to the increased waiting time. Overall, the maximum travel time gained and lost is roughly the same regardless of the two demand profiles, with approximately 150 seconds lost and 130 seconds gained for θ = 1. To visualize the time gained or lost based on the demand, we multiply the time difference ∆T (i,j) with the associated demand for each origin-destination pair λ (i,j) . Again, for both demand profiles, we represent the results as a heatmap, where each square represents an origin-destination pair, and its color represents the passenger seconds; see Figure 5.18. When an origin-destination pair has a significant time gain or loss, but the demand is low, the associated square becomes lighter, indicating that 90 5.6. THE EFFECT OF THE SKIP-STOP POLICY ON THE PASSENGERS this pair does not play a significant role in the average passenger travel time. In Figure 5.18a, most of the squares are lighter, but some, whether losses or gains, stand out. Therefore, the OD pairs with the highest ridership do not necessarily save the most time. The figure has no dominant color, with as many red squares as blue squares, which explains why the average time gained is close to 0. However, in Figure 5.18 for the second demand profile, we can see that many green squares stand out, and the violet squares have significantly lightened. Some of the most frequented OD pairs are the ones that allow travelers to save the most time.

C h .v . B e r S M P V N a t R D G L B a s S P H d V C h a L o u P R T u i C o n C E R o o . G V C D G A
Finally, we can compare the number of people gaining or losing time when the skip-stop policy is implemented. To do this, we calculate the percentage of people who gain or lose time. If, for an origin-destination pair, there is a time gain, we add the number of people from that OD pair to the group of people gaining time, and vice versa. For the first demand profile, when m is small, there is no significant difference between the number of people gaining and losing time, with 56% and 44%, respectively. As we approach the line capacity when m = 50, slightly more people are gaining time, but the percentage remains below 70%. However, for the second demand level, the percentage of travelers gaining time is much higher, reaching over 80% and up to 90% when approaching the line capacity.

In Section 5.6.1, the rule defined to select the skippable stations ensures that less than half of the passengers are negatively affected by the skip-stop policy, i.e., those traveling to and/or from a skippable station, for both demand profiles. With the first demand profile, only a few passengers traveling to and/or from a skippable station gain time. Again, the short distance traveled overall by passengers does not allow them to compensate for the time lost in waiting with the time gained from the increase in the train speed. However, this is the case for the second demand profile, where many passengers who wait longer at their origin station will still gain time.

The Passenger Comfort

After calculating various time indicators for passengers, we now focus on comfort, precisely the number of passengers on the train. Indeed, this is one of the key criteria for passenger satisfaction. Furthermore, disruptions on a line can arise from overcrowded trains. Passenger exchanges at stations become more complicated, leading to door blockages and consequently slowing down the operation of the line. We use the derived Equations (5.59) to (5.61) from Section 5.3. In this section, we again compare the skip-stop and all-stop policies. In the equations, the number of passengers on the trains is calculated considering arrival rates and the train time headway. However, we do not consider the capacity of the trains. Nevertheless, to understand the train occupancy rate, we represent it in the figures. It is indicated theoretically in the following figures. Two capacities can be considered: comfort capacity and maximum capacity. The former considers four passengers per square meter, and the latter considers six passengers per square meter [START_REF] Stif | Receuil des actes administratifs du STIF[END_REF].

For the two demand profiles, we present two different figures. In the first one, with a fixed number of trains at 50, we provide the average number of passengers1 per train with and without the skip-stop policy for two different demand levels at each station. In the second figure, we represent the percentage of passenger savings in the trains compared to the train's capacity. If the capacity is given by cap, we have 100 × ∆σ j (θ)/cap, which gives the percentage of capacity saved thanks to the skipstop policy. Figures 5.21 and 5.22 represent this percentage. For the two demand profiles, the skip-stop policy allows for a decrease in the number of passengers per train regardless of the demand level. Moreover, depending on the demand level, the percentage rises to 20% and 25% of the capacity on the busiest section of the line.

In Figures 5.23 and 5.24, we show the evolution of the number of passengers on the line for the two policies and two demand levels. The colored curves represent the number of passengers for the skip-stop policy, while the black curves represent the number for the all-stop policy. The solid and dotted lines differentiate the two For the first demand profile, the line is not overcrowded. The right part of the figure, which represents one direction, is well below capacity. Although an improvement is visible, the passenger experience is similar for both policies. In the other direction, on the left part, the line is more crowded. The skip-stop policy improves passenger comfort because, for both demand levels θ = 1 and θ = 2, the comfort capacity is not reached only when a skip-stop policy is implemented.

For the second demand profile, the trains are more crowded. As passengers take longer trips, they accumulate throughout the line to travel toward the terminus. As a result, the comfort capacity is exceeded in both directions, as is the maximum capacity in the first direction on the left part of the figure. However, when θ = 1, the skip-stop policy prevents exceeding this maximum capacity and improves overall comfort.

Furthermore, we emphasize that the demand indicator x j directly depends on the number of passengers on the trains and increases with this number. In addition to increased comfort, reducing the number of passengers allows trains to spend less time at stations, thereby improving the line's performance. Finally, the number of passengers arriving at the station is the same for skip-stop and all-stop policies. The decrease in the number of passengers on the trains means more people are waiting on the platforms. The increased comfort on the trains is accompanied by decreased comfort on the platforms. If the number of people on the platforms becomes too high, circulation can be affected, and passenger exchanges can become more complex. There can also be safety issues due to overcrowding. However, in our case study, Line 1 of the Paris Metro is equipped with platform screen doors, which ensure passenger safety.

Conclusion

We have presented in this chapter a discrete event mathematical model for a line operated with a skip-stop policy, where two alternating services are considered. Moreover, the train dwell time at platforms is modeled as a function of the services the operator provides, the travel demand, and the average train-time headway. The model explains how services and passenger demand are considered and dwell times for both services are determined. The model is written linearly in the Max-plus algebra, allowing interesting analytical results to be derived. The average headway, frequency, and dwell times are derived as functions of the number of running trains, the services defined by the operator, and other line characteristics. The advantages and drawbacks of the skip-stop policy are also discussed. Increasing the train time headway between two trains stopping at skippable stations increases the average waiting time for passengers, but it can decrease the passenger travel time under certain conditions. When trains skip stations, their speed increases, and the time lost by increased waiting time is offset by lower in-vehicle time. In this chapter's last section, we studied different OD matrices significantly impacting the computed indicators. We show that the skip-stop policy is particularly beneficial when the number of stations between the passengers' origin and destination is high.

In the next step, we will work on the development of an optimization tool that would give the best skip-stop arrangement depending on the origin-destination matrix of passenger arrivals and the line's characteristics. Especially our rule to select the skippable stations might be too restrictive. We also intend to relax the assumption of the infinite passenger capacity of trains in the future. Chapter 6

Impact of a FIFO Rule on a Line with a Junction

This chapter focuses on a different application from the previous chapters: line 13 of the Paris metro. This line is different in that it has a junction, i.e., a central part that divides into two branches. The line's convergence or merge (the point where the two branches meet in the central section) is a key point in the operation. The branches have approximately the same demand and travel time, so trains must run alternately to the two branches at the divergence of the line. At convergence, the same rule applies as at divergence. The company ensures that this order is respected as far as possible. Indeed, due to operational constraints, it is necessary to maintain the running order except in the event of major disturbances or traffic disruptions.

With the planned automation of the line, driver-related operational constraints can be relaxed, and the running order of trains at convergence can be modified. This work tests the impact of a new running order rule on the line's train frequency and enables the operator to estimate the gains linked to train frequency. Indeed, frequency and reliability are key factors in the smooth running of a metro system. High frequency means short intervals between trains, which is important to meet passenger demand during peak hours. Reliability is equally important, as passengers expect to be able to rely on the metro system to arrive at their destination on time. Unexpected delays and service interruptions can lead to inconvenience and frustration, negatively impacting the overall passenger experience.

This chapter, therefore, proposes a discrete-event traffic model for a metro line with a junction. It is based on the line's existing signaling system and determines train departure times at all nodes on the line.

In addition, the model estimates the average interval and frequency of trains. We apply our model to line 13 of the Paris metro, which is not currently operated with a FIFO (First-In-First-Out) rule on the junction. We aim to evaluate the effect of a FIFO rule on the nominal frequency at steady state. In relation to the current line operation, we also test the FIFO rule as a daily disturbance control strategy. At the steady state, we show that train frequency is maximized, whatever the distribution ure 1.4). Our model is based on the currently used line signaling system. The line consists of one track for each direction, which does not allow trains to overtake each other. On the divergence, the tracks divide into two separate branches. Eventually, the two branches merge at the start of a central section. Here, a signal system regulates train traffic, allowing trains from one branch to enter the central section while preventing those from other branches from doing so to prevent collisions. Thus, the line is discretized into segments ending in a node corresponding to a signal. Three types of nodes must be distinguished. First, we have the divergence of the line, denoted by (0, n 0 ), where the trains go to one or the other of the two branches. Then, the merge of the line, denoted by (0, 0), where the trains come from the branches to the central part. Finally, all the other nodes, where the trains run without interacting with another branch. Each segment (u, j) has some characteristic times r u,j , w u,j , t u,j , and s u,j respectively run, dwell, travel and safe separation times.

We denote by r (u,j) , w (u,j) , t (u,j) , and s (u,j) , respectively the lower bound for the run, dwell, travel and safe separation times on the segment (u, j). The model calculates the k th departure times d k (u,j) at all nodes (u, j) and is based on two constraints. Note that k indexes the number of departures, not the trains. It is the counter of the number of departures at each line node. On lines without a junction, the counter k grows uniformly for all the line nodes. The model evaluates the k th departure at all nodes at each iteration. However, for lines with junctions, the growth rate of the counter k is not the same for the central part and the branches. For example, with a symmetrically operated junction, only half of the departures made on the nodes of the central part are made on the nodes of each branch. In Table 6.2, we show how the different values of the counter evolve. Especially we consider k as the counter on the central part and k 1 and k 2 as the counters on branches 1 and 2.

6.1. THE MODEL

Constraints & Train Dynamics

We now explicit the constraints of our model. The mathematical formulation of the constraints depends on the type of nodes of the line. However, for all nodes, the interpretations are the same. Thus, we give the constraints and the interpretations for the nodes out of the junction.

Constraints out of the Junction

The constraints are given for all the nodes except the divergence and the merge. ∀u ∈ U, we have j ∈ J(u)\{1, n u }. There are two constraints: one on the travel time (run + dwell) and one on the safe separation time.

1. The travel time constraint takes into account the line's characteristics. The trains' movement on the line is constrained by the maximum speed achievable on a segment giving the minimum run time r (u,j) , and by the minimum dwell times at stations. For each segment, the travel time is equal to the sum of the run and dwell times, i.e., t (u,j) = r (u,j) + w (u,j) . The departure of a train on a node (u, j) is constrained by its departure at the previous node (u, j -1) plus the minimum travel time to go from node j -1 to node j. The train making the k th departure at node (u, j) has made the (kb (u,j) ) th departure at node (u, j -1).

d k (0,j) ≥ d k-b (0,j) (0,j-1) + t (0,j) , if u = 0 (6.1) d ku (u,j) ≥ d ku-b (u,j) (u,j-1) + t (u,j) , otherwise (6.2)
2. The second constraint ensures safety on the line by avoiding potential collisions between trains. A train can only enter a segment if it is free of other trains. Thus, the departure at a node (u, j) occurs when the train preceding the one departing from node (u, j) has made its departure at node (u, j + 1) plus a safe separation time s (u,j+1) . The departure of the preceding train is given by k -b(u,j+1) . This safe separation time guarantees that the end of the preceding train has also left the segment.

d k (0,j) ≥ d k-b(0,j+1) (0,j+1) + s (0,j+1) , if u = 0 (6.3) d ku (u,j) ≥ d ku-b(u,j+1) (u,j+1) + s (u,j+1) , otherwise (6.4)

Constraints on the Divergence

The divergence is the last point (0, n 0 ) of the central part, and it has connections with the first points (1, 0) and (2, 0) of both branches 1 and 2. We consider a divergence with a symmetrical operation, where trains go alternately to one or the other branch. Since every other train goes to either branch, we can use a rule based on parity on this node. Thus, odd and even departures correspond to trains going to Branch 1 and 2. With this parity rule, we ensure that the order is always guaranteed whatever the order on the merge of the line. Even if multiple successive trains enter the central part from the same branch, the same train will alternate towards branches 1 and 2 when reaching the divergence.

1. On the central part, u = 0 and j = n 0 . The travel time constraint is given by

d k (0,n 0 ) ≥ d k-b (0,n 0 )
(0,n 0 -1) + t (0,n 0 ) (6.5)

For the safe separation constraint, the departure of a train to a branch is only constrained by the preceding train going to the same branch. Therefore, the safe separation constraint is given by

d k (0,n 0 ) ≥        d (k+1)/2-b(1,1) (1,1) + s (1,1) , if k odd d k/2-b(2,1) (2,1)
+ s (2,1) , if k even (6.6)

2. The k th entry on branch u ∈ {1, 2} can be evaluated with

d ku (u,1) ≥ d k-b (0,1)
(0,n 0 ) + t (0,1) (6.7)

d ku (u,1) ≥ d ku-b(u,2) (u,2) + s (u,2) (6.8) with k = 2k u -1 if u = 1, and k = 2k u if u = 2.

Constraints on the Merge

For the merge, the rule is different. We set the first train arriving on the merge to enter the central part. Thus, the parity-based rule cannot be used at this line node. The equations are given below.

1. Central part, u = 0

d k (0,1) ≥ min u∈{1,2} d ku-b (u,nu)
(u,nu-1) + t (u,nu) (6.9)

d k (0,1) ≥ d k-b(0,2) (0,1)
+ s (0,2) (6.10) with k u , u ∈ {1, 2} the departure counter corresponding to the last train which entered the central part from branch u.

2. Branch u, u ∈ {1, 2} d ku (u,nu) ≥ d ku-b (u,nu) (u,nu-1) + t (1,nu) (6.11) d ku (u,nu) ≥ d k-b(u,nu+1) (0,1)
+ s (u,nu+1) (6.12)

On the divergence, the parity-based rule allows expressing the departure counter k u of each branch as a function of the departure count k of the central part. Nevertheless, with the FIFO rule on the merge, two or more trains from a branch can enter the central part consecutively. Thus, the counters k u are updated each time a train enters the central part from branch u, i.e., k u = k u + 1 each time a train from branch u enters the central part.

6.2. REVIEW OF THE ANALYTICAL RESULTS WITH A ONE-OVER-TWO RULE

Review of the Analytical Results with a Oneover-Two Rule

This section reviews the results obtained in [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF], where a discrete-event model deriving the traffic phases of the train dynamics on a line with a junction is developed.

The authors consider a one-in-two rule on divergence and merging of lines. With a one-over-two rule, at the divergence, one train goes to Branch 1 and the next one goes to Branch 2, while at the merge, one train enters the central part from Branch 1 and the next one enters from Branch 2. This alternation is repeated during the whole operation. One of the main results is Corollary 6.2, which gives the train frequency as a function of two variables: m, the number of trains running, and ∆m, the difference in the number of trains between Branch 1 and Branch 2. Let us consider the notations of Table 6.1.

Corollary 6.2. [58, Corollary 1] The asymptotic average train frequency on the central part f 0 and on the branches f 1 = f 2 are given as follows:

f 0 (m, ∆m) = 2f 1 = 2f 2 = min{f fw ; f max ; f bw ; f br }, with f fw = max m -∆m T 0 + T 1 , m + ∆m T 0 + T 2 f max = 1/max j {t j + s j } f bw = max m -∆ m S 0 + S 1 , m + ∆ m S 0 + S 2 f br = max 2(n 2 -∆m) T 1 + S 2 , 2(n 1 + ∆m) S 1 + T 2
Using Corollary 6.2, we can plot the train frequency in a fundamental diagram and derive the traffic phases of a line with a junction. [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF] show the existence of eight phases in the diagram. For a fixed value of ∆m, we get back to the three phases of a line without a junction: the free-flow phase, corresponding to an increase in line frequency when the number of running trains m also increases. Next, the capacity phase gives the maximum frequency of the line. Finally, the last phase is called the congestion phase. Running trains interfere with each other, creating congestion on the line. The operator must avoid this last phase because the average train travel time and passenger discomfort increase.

In this work, we focus our study on the free flow phase given by f fw and the capacity phase given by f max . The frequency starts to decrease as soon as the congestion phase is reached, corresponding to the number of trains denoted as m C . For the Paris metro line 13, we have m C = 68 trains. Thus, the value of m is defined such that 1 ≤ m ≤ m C = 68. The phases and characteristic points of the fundamental diagram are described in [START_REF] Schanzenbächer | Feedback Control for Metro Lines With a Junction[END_REF][START_REF] Schanzenbächer | Max-plus modeling of traffic on passenger railway lines with a junction: fundamental diagram and dynamic control[END_REF].

The fundamental diagram for the studied values of m is depicted on Figure 6.2. We can see that for a fixed value of m that the train frequency varies with the value of ∆m. The black lines represent the curves of the ∆m as a function of m, giving for each m the values ∆m for which the train frequency is maximum. In the free flow phase, a unique value ∆m * maximizes the frequency for any fixed m. It is given by Proposition 6.3. In Figure 6.2, the frequency is obtained directly using the formulas of Corollary 6.2. In this figure, it is important to notice the triangular shape of the frequency contour line; the frequency increases along with the number of trains until the line's capacity is reached. Moreover, the frequency decreases for a fixed m when the value of ∆m gets farther from the optimal value ∆m * . Finally, it is also important to note that the ∆m value is fixed in time.

The Steady State Train Dynamics

In this section, we simulate the train dynamics with multiple values of the number of trains m and the initial difference in the number of trains between the two branches ∆m 0 . This section derives the asymptotic train frequency of the line by numerical simulations, with interpretations of the derived results. We first represent the line's fundamental diagram; then, we study the asymptotic value of ∆m k . Finally, we give some conjectures on the analytical results on the line's frequency and the ∆m k value.

Fundamental Diagrams

The fundamental diagrams, Figures 6.2 and 6.3, represent the line frequency as a function of the number of trains m and the difference in the number of trains between the two branches ∆m. In Figure 6.3, we represent the diagram with the FIFO 6.3. THE STEADY STATE TRAIN DYNAMICS rule on the merge. Note that unlike the Figure 6.2, the asymptotic average train frequency values are obtained by numerical simulation. We compute the asymptotic train time headway on each part u of the line with the following formula: h sim,u = j (lim k→∞ d k (u,j) /k)/n u ≈ j (d K (u,j) /K)/n u , for a sufficiently large K. Then using the relation f sim,u = 1/h sim,u , we can directly obtain the frequency of the part u. In a similar way to the one-in-two rule, we obtain that the frequency on the central part is equal to twice the frequency of the branches, that is, f sim,0 = 2f sim,1 = 2f sim,1 . Figure 6.3 shows the frequency of the central part of the line. As mentioned above, the value of ∆m k changes after all iterations. Thus, the y-axis represents the starting value ∆m 0 . With the FIFO model, the contour lines are now parallel with the y-axis. Therefore, regardless of the initial value ∆m 0 , the asymptotic frequency of the line is the same. For the operator, it removes a variable to take care of when planning the line operation. The steady state is always reached, giving the maximum frequency possible for each m. However, the FIFO rule does not improve the maximum frequency nor diminish the optimal number of trains m * .

Convergence of the Sequence ∆m k , k ≥ 0

Let us now study the evolution of the value of ∆m k at each iteration k. To see its evolution, we represent two figures: Figure 6.4 depicts three points for all number of running trains m: the black ones represent the initial value ∆m 0 chosen randomly, the red squares correspond to asymptotic simulated value ∆ m, with

∆ m := lim k→∞ k ∆m k k ≈ ∆m K K (6.15)
for a sufficiently large K, and the blue dots are the values obtained using Proposition 6.3, i.e. the optimal value ∆m * with a one-over-two rule on the merge. ure 6.4 can be separated into three parts. ∀m < m A = 20 the simulated value ∆ m is either 0 or 1, and in particular, it is 0 if the number of trains is odd and 1 when it is even regardless of the starting value. In the second part, ∀m A ≤ m < m * , the mean value is the same as the optimal value given by the Proposition 6.3. Finally, in the third part, ∀m * ≤ m ≤ m C , the mean value seems to depend on ∆m 0 but converges to a value such that it is in the range of the values giving the maximum frequency.

Figure 6.5 focuses on a specific value of m, we take here m = 51. We want to see the effect of the starting value ∆m 0 on the asymptotic simulated one ∆ m. We take six different values of ∆m 0 showing the evolution of ∆m k as a function of the number of iterations. The dashed line corresponds to the optimal value ∆m * (see Proposition 6.3). It is important to notice that this value is theoretical and not necessarily an integer number; in our case, ∆m * ≈ 1.8, and the closest integer value is 2. Figure 6.5 shows that the value of ∆m k changes from the first iterations to get closer to ∆m * . After a small number (less than 20) of iterations, the ∆m value stabilizes, and two kinds of behavior are noticeable. First, the curves with an even ∆m 0 converge mainly to 2, sometimes oscillating between 0 and 2 (around k = 100). When ∆m 0 is odd, the curves oscillate around the value of ∆m * , 1 and 3, and the value is constant for some iterations in a row. In Proposition 6.1, we showed that the parity of ∆m k could not change. When the starting value is odd, it cannot converge to the closest integer, and thus it will oscillate between the two values around ∆m * . In both cases, the average value of ∆m k seems to converge toward ∆m * .

Conjectures

With our previous observations and Proposition 6.1, we can make some conjectures on the line performance when a FIFO rule is set at the merge. We can make the following conclusions on the value of ∆m k when k → ∞.

1. ∀m ≤ m A , lim k→∞ ∆ mk ∈ {0, 1}, depending on the parity of m. The ∆m * value is not unique during the capacity phase.

Thus, the frequency is maximized for any ∆m 0 starting value. Therefore, we have f sim (m) = f (m, ∆m * ).

FIFO as a Regulation Strategy for Disturbances

As mentioned in the introduction, the merge is one of the critical points of a line with a junction. Indeed, a disturbance on one of the branches can significantly impact the frequency of the whole line. Besides, the impact can be more significant if the operator respects the trains' running order on the merge. This section studies the line frequency of two different disturbances occurring on the line. These are daily disturbances that affect the line for a short period: 1. the first example considers a train that makes a longer stop at a specific node on a branch.

2. in the second example, the speed of the trains is reduced on a portion of a branch.

We study the effect of these disturbances on the line frequency with the FIFO rule on the merge, and we compare it to the current one-over-two rule. In both examples, we consider that the line is at its steady state before the beginning of the disturbance. Trains are initially distributed uniformly on the line. Except for the disturbed part of the line, the minimum run and dwell times (the travel times) are respected.

Dwell Time Extension on one Branch

During line operation, some inconveniences occur, especially on platforms where interactions with passengers are important. For example, a passenger may block the closing of the doors, thus extending the dwell time in a station. Here the dwell time is twice the theoretic headway, ∼ 200 seconds. In such a situation, to keep the order defined in the planning, the operator waits for the disturbed train even if it will disturb a train coming from the other branch. In Figure 6.6, the blue and orange curves represent the frequency for the oneover-two and FIFO rules on the merge. When the disturbance occurs, the effect on the central part is not instantaneous. Indeed, the trains ahead of the disturbance continue their route and arrive on time at the merge. The central part train frequency decreases once all the trains ahead of the disturbed one have arrived on the merge. With the one-over-two rule on the merge, the next train arriving on the merge from the non-disturbed branch will have to wait until the disturbed one enters the central part. On the contrary, only the trains on the disturbed branch will be late with the FIFO rule. The trains on the other branch enter the central part as soon as they arrive; the value of ∆m will thus change. However, the train frequency decreases slightly because of the disturbances, but it is better absorbed with a FIFO rule.

Reduce Speed on One Branch

For example, because of the failure of the signaling system, trains have to reduce their speed for safety reasons. Therefore, the travel time on this portion of the line 6.4. FIFO AS A REGULATION STRATEGY FOR DISTURBANCES is longer. The system failure lasts around 10 minutes, and the segments affected are defined as F. In this example, the run time of a portion of Branch 2 increases by two. Thus, ∀j such that (2, j) ∈ F, the new travel time is equal to 2r (u,j) + w (u,j) . The system failure lasts around 10 minutes. Figure 6.7 is similar to Figure 6.6, the blue and orange curves respectively represent the one-over-two and the FIFO rules. The shape of the curve is similar, with a decrease in the frequency after the beginning of the disturbance. This time, the impact on the frequency is, bigger regardless of the rule. Indeed, the travel time is changed, and thus the maximum frequency decreases. Using Proposition 6.3, it is possible to determine the new optimal ∆m * value with the new circulation conditions: ∆m * = 5.95.

In Figure 6.8, we plot the value of ∆m * as a function of iterations with the FIFO rule on the merge. Before the perturbation and until the first disturbed train CHAPTER 6. IMPACT OF A FIFO RULE ON A LINE WITH A JUNCTION 109 arrives on the merge, the value is stable. However, the value of ∆m k changes to the new ∆m * as soon as the disturbance reaches the central part. Once conditions have returned to nominal, the value of ∆m k changes again to be similar to before the disturbance. The FIFO rule allows the line not to lose too much frequency and to re-increase it more quickly. In addition, we also reach the steady state faster than with the one-in-two rule on the merge.

Conclusion

In this chapter, we presented a mathematical model describing the operation of a metro line with a junction. At the merge of the junction, a FIFO rule is implemented to let the first train arriving enter the central part. In our application case (Paris metro line 13), the rule currently applied on the merge is a one-over-two due to operating constraints. As the line will be fully automated in the coming years, some of these constraints will be removed, and the operating strategy for the merger will be simplified. In this chapter, we provide the first step to numerically measure the impact of the new operating possibilities on the line. This chapter is divided into two parts: first, we studied the steady state of the train dynamics, i.e., the train frequency when there are no disturbances on the line. When the line is operated with a one-over-two rule on the line merge, the parameter ∆m (the difference in the number of trains between the two branches) greatly influences the train frequency of the line. The numerical simulations performed in this chapter showed that the parameter ∆m does no longer influence the frequency. With the FIFO rule, we showed that ∆m could change at each iteration and converges towards the optimal value ∆m * , maximizing the train frequency. Therefore, the train frequency is maximized with the FIFO rule for trains running on the line.

In the second part of the chapter, we run numerical simulations to show how the train frequency varies under disturbances. Two examples have been presented: in the first one, a train has to dwell longer than planned on one branch, while in the second example, the travel time is longer on a portion of one branch. We showed that this new FIFO rule reduces the impact of the disturbance in both frequency intensity and recovery time. Furthermore, ∆m changes over time to adapt to the disturbed conditions of the line, which is more robust against disturbances.

This work is the first step toward a better understanding of the operation of a metro line with a junction. In future research, we first aim to prove our conjectures analytically. Moreover, we will work on the extension of the 1/2 for unbalanced lines. Finally, we will focus on a real-time version of our model to better understand the improvement the FIFO rule can make on the train frequency in case of disturbances. Currently, the dwell times are stable even with disturbances, but when the train time headway increases, the stock of passengers on the platform can increase and, thus, make the dwell time longer.

Chapter 7 Conclusion

Summary

This thesis aims to tackle transport operators' challenges, particularly the RATP group. As governments increasingly limit individual vehicle usage in cities and promote public transportation, it becomes crucial to ensure sufficient service capacity, especially for existing transport lines that often suffer from saturation issues. The focus of this thesis is to explore analytical methods for enhancing the capacity of these systems. We use mathematical models to develop simulation models and express them linearly in the max-plus algebra whenever possible. Our models are built upon the existing signaling system of the Paris metro lines and are guided by two constraints. The first constraint considers the train's travel time, while the second constraint ensures safety by including a safe separation time, guaranteeing adequate spacing between trains. Each model assumes that all trains adhere to the defined lower bounds for both run and safe separation times. On the other hand, the dwell times can be calculated based on passenger demand, considering the arrival rates at stations as discussed in Chapter 5. In Chapters 3 to 6, we develop simulation models that enable efficient computations of train dynamics. Notably, the models presented in Chapters 4 and 5 can be expressed linearly in the max-plus algebra, facilitating a physical interpretation of the traffic dynamics.

In Chapter 3, we constructed a simulation model to investigate the impact of a skip-stop policy involving two services on a mass-transit line. The findings of this model indicated that when an operator aims to introduce a service that stops at all stations along the line, the frequency does not improve, resulting in no advantages for either the operator or passengers. In a subsequent model, we examined the scenario where some origin-destination pairs are only accessible by making a transfer on the line. This model demonstrated that compared to an all-stop policy, the line frequency could be increased, and depending on the specific origin-destination pair, passengers could save time.

To provide accurate estimations of the benefits an operator can expect, we incorporate the operator-defined services as input data and express the model linearly in the max-plus algebra. Our study explores various services that can be implemented or the number of stations that can be skipped. Thanks to some existing results of the max-plus algebra theory, we identify the conditions under which the train dynamics exhibit a stationary regime. Furthermore, we derive the fundamental traffic diagrams for the train dynamics, which offer valuable insights. These diagrams depict frequency evolution as a function of the number of running trains on the line. They reveal the existence of three distinct traffic phases: the free-flow phase, characterized by increasing frequency; the capacity phase indicating the maximum achievable frequency on the line; and the congestion phase. Each phase is subjected to mathematical analysis and interpreted from a physics of traffic perspective. With the implementation of a skip-stop policy, we observe an accordion effect between trains as they skip stations and get closer or move away from each other. This phenomenon can lead to blockages when a train that has skipped a station gets too close to the preceding train. We examine different skip-stop policy configurations and analyze the differences in frequency as well as the advantages they offer compared to the all-stop policy.

To accurately assess the impact on passengers, we incorporate their arrival rates and origin-destination patterns into the model. The dwell time at stations is determined based on these input data. We demonstrate the influence of passenger demand levels, initially focusing on a fixed demand profile. By utilizing indicators such as waiting time for passengers and the number of passengers in trains, we calculate the effects for two different demand profiles. In particular, the demand profile highlights the relevance of the skip-stop policy for passengers. When most passengers have short-distance trips in the demand profile, the average gains are minimal unless the number of trains is sufficiently high. Conversely, in the demand profiles where passengers travel longer distances, the acceleration of trains facilitated by the skip-stop policy allows them to save time on average throughout their journey regardless of the number of trains.

The simulation model we developed also enables testing new regulations in the event of an incident on a line. One critical aspect for the smooth operation of Paris metro line 13 is managing the merge, where the three sections of the line converge. Currently, the operator has implemented a one-over-two rule at the merge for operational purposes. However, with automation in sight, this rule may change. In Chapter 6, we present a model for managing the convergence using a FIFO (First-In-First-Out) rule and analyze its impact in the presence of two types of disturbances. The FIFO rule improves traffic flow and mitigates the impact of the incident. The difference in the number of trains between the two branches adjusts dynamically to maximize the frequency in the disrupted situation.

Perspectives

In Chapter 6, we investigate the application of the FIFO rule to a line with a junction, demonstrating its potential to reduce the impact of disruptions. However, our research primarily emphasizes the average headway between trains rather than the standard deviation. Changing the running order may not be sufficient to ensure a consistently high level of service during disturbances. A more detailed examination of the train time headway could offer valuable insights for enhancing the overall passenger experience.

In a broader context, our model can be extended to other applications, allowing for generalizations. Firstly, concerning the skip-stop policy, the proof provided in Appendix A for Chapters 4 and 5 forms the foundation for extending the model to skip-stop policies with more than two services. By adapting our description of train dynamics, similar analytical results can be obtained for a wider range of services. For instance, instead of alternating between services A and B, it is possible to introduce a third service C or incorporate a sequence of two services A followed by one service B. Furthermore, the development of optimization models can determine the most suitable services for a given line, considering all relevant parameters and passenger demand rates. The optimization can be modeled with our analytical results, allowing for identifying service strategies that optimize operational efficiency based on specific line characteristics and passenger demand.

The train dynamics models developed in Chapters 3 to 6 are based on the Paris metro signaling system, which utilizes two-state signals. However, suburban lines employ a different signal system with three states, including a yellow state that allows trains to pass at a reduced speed. Incorporating this feature into our model would enable us to extend our research to a broader range of lines within the Paris network.

In Chapter 5, the dwell times of trains depend on constant passenger arrival rates at stations, although in reality, these rates may vary even during peak hours. We could modify the input origin-destination matrix to account for this variability to introduce a dynamic version that captures the changing arrival rates.

Additionally, our current model assumes that all trains operate at the lower bound of the line's characteristic times. However, in practice, minor disturbances can affect train running or dwell times individually. By leveraging the properties of stochastic max-plus algebra, we could adapt the model to incorporate stochasticity and assess its impact on the line's dynamics.

Lastly, while this thesis primarily studies the steady state of train dynamics, it would be interesting to investigate the transient regime in simulations. Specifically, exploring how to reach the steady state most efficiently could provide operators valuable insights into recovering the nominal headway as quickly as possible following a disturbance. A.7. CYCLES 1. m even:

(a) The weight of these cycles is greater than m/2, which means more arcs are involved in the cycle. To illustrate these cycles, we take a simple example, depicted in Figure A.3a, such that m = 4, ψ = 2, and ∀i 1 , i 2 ∈ I, j 1 < j 2 ≤ i 1 < j 3 ≤ i 2 < j 4 . The same reasoning works for any positions of the nodes and any number of nodes i 1 , • • • , i ψ ∈ I with ψ even. The weight of this example is given by: |ρ| w = Υ (j 1 ,i 2 ) + Υ (i 2 ,i 1 ) + Υ (i 1 ,j 1 ) (A.36) = Φ (i 1 ,j 2 ) + Π (j 2 ,j 1 ) + Φ (i 2 ,j 3 ) + Π (j 3 ,i 1 ) + Φ (j 1 ,j 4 ) + Π (j 4 ,i 2 ) (A.37) with a weight of m/2 + ψ/2. The headway h e fw,ψ>0 is equal to half the maximum cycle mean for a fixed ψ: h e fw,ψ>0 = max

|ρ|
p 1 ,p 2 ,i 1 ,••• ,i ψ          i 1 i ψ +1 t p 1 q + (t p 1 i ψ + s i ψ ) + • • • + i 2 i 1 +1 t p 2 q + (t p 2 i 1 + s i 1 ) m + ψ          (A.41)
(b) ψ odd, even if there are elementary cycles in the matrix, their mean is always upper bounded by other cycles. We take an example with m = 2 and ψ = 1.

|ρ| w = Υ (j 1 ,i 1 ) + Υ (i 1 ,j 2 ) + Υ (j 2 ,j 1 ) (A.42) = Φ (j 1 ,j 2 ) + Π (j 2 ,i 1 ) + Φ (i 1 ,j 1 ) + Π (j 1 ,j 2 ) + Φ (j 2 ,i 1 ) + Π (i 1 ,j 1 ) (A. The length of this cycle is 3 = m + 1. The cycle mean is given by

ρ = T A + T B + t A i 1 + s i 1 + t B i 2 + s i 2 m + 1 ≤ max{ T A + T B m , t A i 1 + s i 1 + t B i 1 + s i 1 1 } ≤ max{ 2T A m , 2T B m , t A i 1 + s i 1 + t B i 1 + s i 1 1 }
This cycle is upper-bounded by the cycles giving either h fw or h min . (a) ψ odd, e.g., ψ = 1: in this case, the cycle is composed of two arcs of Υ.

To ensure that trains do not change their service in the middle of the line, the position of the first train needs to coincide with τ one of the termini.

A.7. CYCLES Consider τ = j 1 ≤ i 1 < j 2 < j 3 then the weight of the cycle is given by |ρ| w = Υ j 1 ,j 2 + Υ j 2 ,j 1 = Υ τ,j 2 + Υ j 2 ,τ (A.46) = Φ τ,j 3 + Π j 3 ,j 2 + Φ j 2 ,i 1 + Π t p 2 q . The length of this cycle is |ρ| l = 2 = m/2 + ψ/2. The headway corresponding to this cycle ∀ψ > 0 and ψ odd is half of the maximum of these cycles:

h o fw,ψ>0 = max p 1 ,i 1 ,••• ,i ψ          i 1 τ +1 t p 2 q + i 2 i 1 +1 t p 1 q + • • • + τ i ψ +1 t p 1 q + t p 1 i 1 + s i + • • • + t p 2 i ψ + s i ψ m + ψ          (A .50)
(b) ψ even, e.g., ψ = 2: in the case where ψ is even, the cycle does two laps around the line. Consider τ = j 1 ≤ i 1 ≤ i 2 < j 3 < j 3 ; the weight of this cycle is equal to |ρ| w = Υ j 1 ,j 2 + Υ j 2 ,i 1 + Υ i 1 ,j 3 + Υ j 3 ,j 1 (A.51) = Φ j 1 ,j 3 + Π j 3 ,j 2 + Φ j 2 ,i 2 + Π i 2 ,i 1 + Φ i 1 ,j 1 + Π j 1 ,j 3 + Φ j 3 ,j 2 + Π j 2 ,j 1 (A.52)

= j 1 j 3 +1 t p 2 q + j 3 j 2 +1 t p 2 q + j 2 i 2 +1 t p 2 q + (t p 2 i 2 + s i 2 ) + i 2 i 1 +1 t p 1 q + (t p 1 i 1 + s i 1 ) + i 1 j 1 +1 t p 2 q + j 1 j 3 +1 t p 1 q + j 3 j 2 +1 t p 1 q + j 2 j 1 +1 t p 1 q (A.53) = i 1 i 2 +1 t p 2 q + (t p 2 i 2 + s i 2 ) + i 2 i 1 +1
t p 1 q + (t p 1 i 1 + s i 1 ) + T p 1 (A.54)

If the starting point of the cycle is j 2 , then we have the weight equals to

|ρ| w = i 1 i 2 +1 t p 1 q + (t p 1 i 2 + s i 2 ) + i 2 i 1 +1
t p 2 q + (t p 2 i 1 + s i 1 ) + T p 2 and the weight is equal to |ρ| l = 4 = m + ψ/2. By looking at the maximum of this kind of cycle we obtain the headway ∀ψ > 0 and even h o fw,ψ>0 = max

p 1 ,i 1 ,••• ,i ψ          T p 2 + i 2 i 1 +1 t p 1 q + i 3 i 2 +1 t p 2 q + • • • + i 1 i ψ +1 t p 2 q + t p 1 i 1 + s i + • • • + t p 2 i ψ + s i ψ 2m + ψ

A.7.4 Maximum Value of Combination and Details on the Nodes

Proposition A.3. ∀ψ > 0, it exists the following property for h e fw and h o fw :

1. ∀i q , i q ′ ∈ {i 1 , • • • , i ψ }, i q ̸ = i q ′ , o < i q < i ′ q < o ′ , ∀o, o ′ ∈ O two consecutive nodes of this set.

2. The value ψ is bounded by the number of skippable stations, i.e ψ ≤ |O|.

Proof. We make the proof for h e fw , the reasoning being the same for h o fw . Let us consider o, o ′ ∈ O such that they are two consecutive nodes in this set, and i, i ′ , i ′′ , i ′′′ ∈ {i 1 , • • • , i ψ } such that i < o < i ′ < i ′′ < o ′ < i ′′′ . We have i ′ q=i+1 t µe q = i ′ q=i+1 t µo q . ∀p 1 , and ∀i 1 , • • • , i, i ′ , i ′′ , i ′′′ , • • • , i ψ ∈ I:

|ρ| w = i 2 q=i 1 +1 t p 1 q + • • • + i ′ q=i+1 t p 2 q + i ′′ q=i ′ t p 1 q + i ′′′ q=i ′′ +1 t p 2 q + • • • + i 1 q=i ψ +1
t p 2 q + (t p 1 i 1 + s i 1 ) + The length of this cycle is given by |ρ| l = m+ψ 2 . The headway corresponding to this cycle is given by

h ψ =   i 2 q=i 1 +1 t p 1 q + • • • + i 1 q=i ψ +1
t p 2 q + (t The first part of the maximum function is equivalent to a cycle with ψ -2 nodes (the maximum is sought on the nodes {i 1 , • • • , i ψ-2 }). Since h (ψ-2) is the maximum of all cycles of this type, the first part of the maximum is dominated by h (ψ-2) .

The second part is dominated by the line's capacity given by h min . Therefore, h ψ ≤ max{h (ψ-2) , h min }, ∀ψ. Moreover, ∀ψ > |O|, there are at least two nodes i, i ′ such that o < i < i ′ < o ′ , so h ψ ≤ max{h Θ , h min }, ∀ψ > 0, ⇔ ψ ≤ |O|.

A.7.5 The Congestion Phase

The same reasoning of section Appendix A.7.2 is used to find the cycle in the opposite direction of the train. ∀i ∈ {1, • • • , n -m}, ji ∈ J we have Υ ( ji , ji+2 ) = Φ ( ji , ji+1 ) + Π ( ji+1 , ji+2 ) . Combining all these arcs, the cycle ρ has the following weight: s q + j1 q= jn-m +1 s q = q s q = S

1. 1 57 5. 1

 1571 Paris railway network map. . . . . . . . . . . . . . . . . . . . . . . . 1.2 Scheme of a AB skip-stop policy. The above and below paths correspond respectively to the stopping patterns of service A and B. . . . . 1.3 Paris metro line 1 map. The line comprises 25 stations and crosses the city from East to West. . . . . . . . . . . . . . . . . . . . . . . . 1.4 Paris metro line 13 map. The line has two branches and a central part. 2.1 Typical fundamental diagram for road traffic. . . . . . . . . . . . . . 2.2 Fundamental diagram for a rail transit line derived in [63]. . . . . . . 2.3 Comparison of the fixed block and moving block signaling system. . . 2.4 Fundamental diagram of a shuttle-operated line. . . . . . . . . . . . . 2.5 Fundamental diagram of a line with a junction. . . . . . . . . . . . . 3.1 Schematic representation of a unidirectional loop metro line discretized following the signaling system. Solid squares, empty squares, and vertical segments correspond to stations with mandatory stops, skippable stations, and signals between two stations. . . . . . . . . . . . . . . . 3.2 Fundamental diagrams obtained by simulation. The three curves represent the frequency for an all-stop policy in blue and for the skip-stop policy in orange and green. . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Space-time diagram for both models with m = 50 trains running on the line. The solid blue and dashed black lines differentiate the two services on the line. The trajectories are given for a 60-minute interval and on a limited section of the line. . . . . . . . . . . . . . . . . . . . 3.4 Heat-map of the difference in travel time ∆T (i,j) between the unrestricted model and all stop-policy for all origin-destinations i, j. Figure 3.4a shows the difference when m = 22 and Figure 3.4b when m = 50. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Example of the average travel time T ψ , with ψ = 4 . . . . . . . . . . 4.2 The frequency fundamental diagram of Metro line 1 for an even number of trains m. Three phases are visible: the free-flow phase until m F (Proposition 4.8), where the frequency increases, the capacity phase until m G (Proposition 4.10), where the line reaches a plateau and the congestion phase where the frequency decreases. The point m E (Proposition 4.9) corresponds to a change in the slope of the frequency line in the free-flow phase. . . . . . . . . . . . . . . . . . . 4.3 The headway fundamental diagram of Metro line 1 for an even number of trains m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x LIST OF FIGURES 4.4 The frequency fundamental diagram of Metro line 1 for an odd number of trains m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.5 The headway fundamental diagram of Metro line 1 for an odd number of trains m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.6 Values of ∆T ψ as a function of ψ. . . . . . . . . . . . . . . . . . . . . 48 4.7 Difference in the frequency between the even and odd case. . . . . . . 50 4.8 Percentage of the difference in the travel time according to the chosen skippable station. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.9 Frequency of the Paris metro line 1 as a function of the number of running trains and the number of skippable stations. The green and blue lines give the value of m E and m F for each number of skippable stations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.10 Frequency as a function of the number m of running trains for five different numbers of skippable stations: 2, 6, 10, 14, and 18. . . . . . 53 4.11 Frequency as a function of the number m of running trains for four different number of stopping patterns: alternating A and B stations with 1, 2, 3 and 4 consecutive skippable stations served by the same service. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.12 Frequency of the three scenarios and all stop-policy in blue, orange, green, and black. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.13 Evolution of the gains of the frequency as a function of the number of trains. The blue, orange, and green curves show the gains for Scenarios 1, 2, and 3. The solid and dashed lines differentiate the cases for an even and odd number of running trains. . . . . . . . . . . Frequency with a skip-stop policy as a function of the number of moving trains and the demand level on the line at peak hour. . . . . . 76 5.2 Evolution of the maximum frequency f max as a function of the level of demand θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.3 Contour frequency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.4 Contour lines with characteristic points. . . . . . . . . . . . . . . . . 78 5.5 Origin-destination matrices with the two demand profiles. . . . . . . . 80 5.6 Count of the number of passengers per number of stations between origin and destination for the demand profile λ 1 in a 60-minute interval. 80 5.7 Count of the number of passengers per number of stations between origin and destination for the demand profile λ 2 in a 60-minute interval. 81 5.8 The analytical average train frequency for the two demand profiles. . 83 5.9 Comparison of the average analytical train time headway for the skipstop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.10 Comparison of the average analytical train time headway for the skipstop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.11 Comparison of the analytical average waiting time for the skip-stop

  . . . . . . . . . . . . . . . . . . . . . . 4.8 Table showing the difference between the services of the scenarios on the skippable stations in one direction. The bold stations are termini, and the stations written in italics show the difference between the scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Critical values of the function of the gains on the line. . . . . . . . . . 5.1 Notations for passenger demand for the all-stop policy case. . . . . . 5.2 Notations for passenger demand for the skip-stop policy case, ∀p ∈ {A, B}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Theorem 5.1 variables . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Notations for the computation of the indicators. The variables with and without the exponent s correspond to the skip-stop and all-stop policies, respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Difference between average analytical train time headway with and without the skip-stop policy. . . . . . . . . . . . . . . . . . . . . . . . 5.6 Average analytical average train time headway. . . . . . . . . . . . . . 5.7 Difference in the average waiting time ∆ω in seconds. . . . . . . . . . 5.8 Difference between the skip-stop and all-stop policies in the average in-vehicle time in seconds. . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Difference in the average travel time in seconds. . . . . . . . . . . . . 6.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Evolution of the counter k, k 1 , k 2 , and ∆m k at the divergence and the merge of the line. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Paris railway network map.

  Alternating service. A and B stations are alternating. Free assignment service. A and B stations are chosen freely.

Figure 1 . 2 : 3 .

 123 Figure 1.2: Scheme of a AB skip-stop policy. The above and below paths correspond respectively to the stopping patterns of service A and B.

EÉFigure 1 . 3 :

 13 Figure 1.3: Paris metro line 1 map. The line comprises 25 stations and crosses the city from East to West.

  .

  4.

Figure 1 . 4 :

 14 Figure 1.4: Paris metro line 13 map. The line has two branches and a central part.

12 2. 1 .

 121 GENERAL MASS-TRANSIT RESEARCH existing strategies for recovering traffic from a line under disruption.

  mentioned the existence of such diagrams for road networks. The fundamental traffic flow diagram represents the relationship between road traffic flow (vehicles/hour) and traffic density (vehicles/km). A typical fundamental diagram is given in Figure 2.1. The x and y-axes indicate the vehicle density k and the traffic flow q on the road.

Figure 2 . 1 :

 21 Figure 2.1: Typical fundamental diagram for road traffic.

Figure 2 . 2 :

 22 Figure 2.2: Fundamental diagram for a rail transit line derived in [63].

Figure 2 . 3 :

 23 Figure 2.3: Comparison of the fixed block and moving block signaling system.

Definition 1 .

 1 [START_REF]Synchronization and Linearity: An Algebra for Discrete Event Systems[END_REF] Definition 2.18] (Cycle mean) The mean weight of a path ρ is defined by |ρ| w /|ρ| l , where |ρ| w denotes the sum of the weights of the individual arcs of this path, and |ρ| l denotes the length of the path. If such a path is a cycle, one talks about the mean weight of the cycle or simply the cycle mean.

Theorem 2 . 1 .

 21 [START_REF]Synchronization and Linearity: An Algebra for Discrete Event Systems[END_REF] Theorem 3.17] If there are only cycles of non-positive weight in G(A), there is a solution to x = Ax ⊕ b, which is given by x = A * b. Moreover, if the cycle weights are negative, the solution is unique.

Theorem 2 . 2 .

 22 [START_REF]Synchronization and Linearity: An Algebra for Discrete Event Systems[END_REF] Theorem 3.20] If G(A) has no cycle with positive weight, then

Figure 2 . 4 :

 24 Figure 2.4: Fundamental diagram of a shuttle-operated line.

. 5 .

 5 The authors show that

Figure 2 . 5 :

 25 Figure 2.5: Fundamental diagram of a line with a junction.

22 3. 1 .Figure 3 . 1 :

 22131 Figure 3.1: Schematic representation of a unidirectional loop metro line discretized following the signaling system. Solid squares, empty squares, and vertical segments correspond to stations with mandatory stops, skippable stations, and signals between two stations.

  one service freq. for two services on big stations freq. on low-demand stations (a) Fundamental diagram for the restricted model.

Frequency

  [train/h] freq. for one service freq. for two services on big stations freq. on low-demand stations (b) Fundamental diagrams for the unrestricted model.

Figure 3 . 2 :

 32 Figure 3.2: Fundamental diagrams obtained by simulation. The three curves represent the frequency for an all-stop policy in blue and for the skip-stop policy in orange and green.

CHAPTER 3 .

 3 MODELING & SIMULATING A SKIP-

  Trajectories of the trains for the restricted model.

  Trajectories of the trains for the unrestricted model.

Figure 3 . 3 :

 33 Figure 3.3: Space-time diagram for both models with m = 50 trains running on the line. The solid blue and dashed black lines differentiate the two services on the line. The trajectories are given for a 60-minute interval and on a limited section of the line.

  Number of moving trains m = 22 for the unrestricted model. Number of moving trains m = 50 for the unrestricted model.

Figure 3 . 4 :

 34 Figure 3.4: Heat-map of the difference in travel time ∆T (i,j) between the unrestricted model and all stop-policy for all origin-destinations i, j.Figure 3.4a shows the difference when m = 22 and Figure 3.4b when m = 50.

Figure 3 .

 3 Figure 3.4: Heat-map of the difference in travel time ∆T (i,j) between the unrestricted model and all stop-policy for all origin-destinations i, j.Figure 3.4a shows the difference when m = 22 and Figure 3.4b when m = 50.

k

  departure's counter; n number of segments; m number of trains running on the line; L length of the line in kilometers; b j ∈ {0, 1}, the initial positions. b j = 1 if there is a train on segment j at time 0, b j = 0 otherwise; bj := 1b j ; d k j k th train departure time at node j; a k j k th train arrival time at node j; r k j train run time from node (j -1) to node j; w k j = d k ja k j the train dwell time at node j ; t k j := r k j + w k j travel time on segment j (from node j -1 to node j); s k j train safe separation time at node j; h k j = d k jd k-1 j : train time-headway at node j.

CHAPTER 4 .

 4 MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 37

Figure 4 .

 4 Figure 4.1 shows an example of the different parts of the travel time on a schematic representation of the line. Between the nodes i 1 and i 2 the travel time is

Figure 4 . 1 :

 41 Figure 4.1: Example of the average travel time T ψ , with ψ = 4

CHAPTER 4 . 43 4. 4

 4434 MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY The Steady State of the Train Dynamics This section analyzes the results and formulas found in Theorem 4.3 and Corollary 4.5. First, Section 4.4.1 presents the case of application of the model. Then, we derive the traffic phases, represented in the fundamental diagram, i.e., the relationship between the train frequency in trains per hour and the number of running trains (Section 4.4.

CHAPTER 4 .Figure 4 . 2 :Proposition 4 . 8 .

 44248 Figure 4.2: The frequency fundamental diagram of Metro line 1 for an even number of trains m. Three phases are visible: the free-flow phase until m F (Proposition 4.8), where the frequency increases, the capacity phase until m G (Proposition 4.10), where the line reaches a plateau and the congestion phase where the frequency decreases. The point m E (Proposition 4.9) corresponds to a change in the slope of the frequency line in the free-flow phase.

Figure 4 . 3 :

 43 Figure 4.3: The headway fundamental diagram of Metro line 1 for an even number of trains m.

(

  Similarly, to the proof of Proposition 4.8 we have f ψ (m), and thus max ψ (m(T e ψ -T e 0 ) + ψ)/T e 0 T e ψ , increasing and bijective. Therefore, the solution is unique and m = min ψ f

CHAPTER 4 .Figure 4 . 4 :

 444 Figure 4.4: The frequency fundamental diagram of Metro line 1 for an odd number of trains m

Figure 4 . 5 :

 45 Figure 4.5: The headway fundamental diagram of Metro line 1 for an odd number of trains m

Figure 4 . 6 :

 46 Figure 4.6: Values of ∆T ψ as a function of ψ.

Figure 4 . 6 .

 46 The value of T ψ CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY 49

4. 5 .

 5 COMPARISON OF DIFFERENT SERVICES Proposition 4.11. For ψ = 0, f o 0 ≥ f e 0 , i.e., the frequency increases faster or equally with an odd number of trains than with an even one. With f o 0 = 2m/(T A + T B ) and f e 0 = m/ max{T A , T B }.Proof. By definition max{T A , T B } ≥ (T A +T B )/2 and so ∀m ≥ 0, 2m/(T A +T B ) ≥ m/(max{T A , T B }), ⇔ f o 0 ≥ f e 0 .

Figure 4 . 7 :

 47 Figure 4.7: Difference in the frequency between the even and odd case.

10

  Percentage of decrease in the travel time

Figure 4 . 8 :

 48 Figure 4.8: Percentage of the difference in the travel time according to the chosen skippable station.

FrequencyFigure 4 . 9 :

 49 Figure 4.9: Frequency of the Paris metro line 1 as a function of the number of running trains and the number of skippable stations. The green and blue lines give the value of m E and m F for each number of skippable stations.

Figure 4 . 10 :

 410 Figure 4.10: Frequency as a function of the number m of running trains for five different numbers of skippable stations: 2, 6, 10, 14, and 18.

4. 5 .

 5 COMPARISON OF DIFFERENT SERVICES • ...

Figure 4 . 11 :

 411 Figure 4.11: Frequency as a function of the number m of running trains for four different number of stopping patterns: alternating A and B stations with 1, 2, 3 and 4 consecutive skippable stations served by the same service.

Figure 4 . 12 :

 412 Figure 4.12: Frequency of the three scenarios and all stop-policy in blue, orange, green, and black.

CHAPTER 4 . 57 l

 457 MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP POLICY ∈ {e, o} and σ ∈ {1, 2, 3} indicating the scenario.

Figure 4 . 13 :

 413 Figure 4.13: Evolution of the gains of the frequency as a function of the number of trains. The blue, orange, and green curves show the gains for Scenarios 1, 2, and 3. The solid and dashed lines differentiate the cases for an even and odd number of running trains.

58 4. 5 .

 585 COMPARISON OF DIFFERENT SERVICES and 4.7 we can calculate the gains ∀m with the following equations:

CHAPTER 5 .

 5 EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 63

  ζ A j ∈ (0, 1) and ζ B j = 1ζ A j the proportion of passengers boarding the 5.1. THE MODEL

  EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 65

Corollary 5 . 3 .

 53 h min , and f bw = (nm)/S. Proof. Directly from Theorem 5.1 and f = 1/h. The asymptotic average train dwell time of the line is given by w e (m) and w o (m) for respectively an even and an odd number m of trains:

0 2 4 6 8 10 NFigure 5 . 1 :

 1051 Figure 5.1: Frequency with a skip-stop policy as a function of the number of moving trains and the demand level on the line at peak hour.

CHAPTER 5 .Figure 5 . 2 :FrequencyFigure 5 . 3 :Figure 5 . 4 :

 5525354 Figure 5.2: Evolution of the maximum frequency f max as a function of the level of demand θ

  for the OD pair ×10 3 (a) First demand profile λ 1 .

  for the OD pair ×10 3 (b) Second demand profile λ 2 .

Figure 5 . 5 :

 55 Figure 5.5: Origin-destination matrices with the two demand profiles.

3 Figure 5 . 6 :

 356 Figure 5.6: Count of the number of passengers per number of stations between origin and destination for the demand profile λ 1 in a 60-minute interval.

CHAPTER 5 . 3 Figure 5 . 7 :

 5357 Figure 5.7: Count of the number of passengers per number of stations between origin and destination for the demand profile λ 2 in a 60-minute interval.

λ 1 λ 2 m

 2 = 20 m = 35 m = 50 m = 20 m = 35 m = 50 θ = 1 21.

CHAPTER 5 .Figure 5 . 8 :

 558 Figure 5.8: The analytical average train frequency for the two demand profiles.

Figure 5 . 9 :Figure 5 . 10 :

 59510 Figure 5.9: Comparison of the average analytical train time headway for the skipstop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 .

Figure 5 . 11 :

 511 Figure 5.11: Comparison of the analytical average waiting time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 .

CHAPTER 5 .Figure 5 . 12 :

 5512 Figure 5.12: Comparison of the analytical average waiting time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 2 .

Figure 5 . 13 :Figure 5 . 14 :

 513514 Figure 5.13: Comparison of the analytical average in-vehicle time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 .

CHAPTER 5 .Table 5 . 8 :

 558 EFFECT OF THE PASSENGERS ON A TWO-SERVICE SKIP-STOP POLICY 87 Difference between the skip-stop and all-stop policies in the average invehicle time in seconds. λ 1 λ 2 m = 20 m = 35 m = 50 m = 20 m = 35 m = 50 θ = 1 33.

  and 5.16.

Figure 5 . 15 :

 515 Figure 5.15: Comparison of the average travel time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 1 .

88 5 . 6 .Figure 5 . 16 :

 56516 Figure 5.16: Comparison of the average travel time for the skip-stop and all-stop policies with θ = 1 and θ = 3 for the demand profile λ 2 .

λ 1 λ 2 m

 2 = 20 m = 35 m = 50 m = 20 m = 35 m = 50 θ = 1 -42.

  A r g M a i. S a b P d N E s p . Difference for the demand profile λ 1 . C h .v . B e r S M P V N a t R D G L B a s S P H d V C h a L o u P R T u i C o n C E R o o . G V C D G A r g M a i. S a b P d N E s p . Difference for the demand profile λ 2 .

Figure 5 . 17 :

 517 Figure 5.17: Difference in the travel time for each OD pair ∆T i,j without and with a skip stop policy.

  Result of the product of ∆T i,j and λ 2 i,j .

Figure 5 . 18 :

 518 Figure 5.18: Results of the product of the difference obtained in Figure 5.17 and the OD matrices λ 1 and λ 2 .

Figures 5 .

 5 [START_REF] Fan | Planning skip-stop services with schedule coordination[END_REF] and 5.20 represent these percentages for the two demand profiles λ 1 and λ 2 , and for two different demand levels, θ = 1 and θ = 2. The different line styles differentiate the percentage of people gaining or losing time and the demand levels.

Figure 5 . 19 :

 519 Figure 5.19: Percentage of the passengers gaining or losing time with the demand profile λ 1 .

CHAPTER 5 .Figure 5 . 20 :

 5520 Figure 5.20: Percentage of the passengers gaining or losing time with the demand profile λ 2 .

92 5 . 6 .Figure 5 . 21 :

 56521 Figure 5.21: Percentage of passengers saving on trains relative to train capacity between skip-stop and full-stop policies and demand profile λ 1 . The number of trains m is set to 50 and 0 ≤ θ ≤ 3.

CHAPTER 5 .Figure 5 . 22 :

 5522 Figure 5.22: Percentage of passengers saving on trains relative to train capacity between skip-stop and full-stop policies and demand profile λ 2 . The number of trains m is set to 50 and 0 ≤ θ ≤ 3.

94 5 .Figure 5 . 23 :Figure 5 . 24 :

 5523524 Figure 5.23: Average number of passengers in the trains along the line for θ = 1 and θ = 2, m = 50, and the first demand profile λ 1 .

Figure 6 . 1 :

 61 Figure 6.1: Schematic representation of line 13 Paris. The line has three parts: the central part and Branches 1 and 2.

CHAPTER 6 .

 6 IMPACT OF A FIFO RULE ON A LINE WITH A JUNCTION 103 Proposition 6.3. [57, Proposition 2] ∀m such that 0 < m < m * , ∆m * (m) is unique, and is given by ∆m * (m) = m∆T /2T , with m * the minimum number of trains for which the frequency is equal to the maximum frequency f max .The value ∆m * (m) is not unique in the capacity phase. Its value is included in an interval I(m), such that ∀m * < m ≤ m C and ∀∆m ∈ I(m) = [∆m * min (m), ∆m * max (m)], f (m, ∆m) = f max . The equations giving the interval I for the capacity phase can also be found in[START_REF] Schanzenbächer | Feedback Control for Metro Lines With a Junction[END_REF][START_REF] Schanzenbächer | Max-plus modeling of traffic on passenger railway lines with a junction: fundamental diagram and dynamic control[END_REF].

Figure 6 . 2 :

 62 Figure 6.2: Fundamental diagram with symmetrical operated junction.

Figure 6 . 3 :

 63 Figure 6.3: Fundamental diagram of Paris metro line 13 with a FIFO rule on the merge.

Fig- CHAPTER 6 .Figure 6 . 4 :

 664 Figure 6.4: Comparison between the asymptotic simulated value ∆ mk and the optimal values ∆m * (Proposition 6.3).

Figure 6 . 5 :

 65 Figure 6.5: Evolution of ∆m k as a function of the departure k. Six different values of ∆m 0 are set.

Figure 6 . 6 :

 66 Figure 6.6: Evolution of the train frequency with a dwell time extension on one branch with the FIFO and the one over-two rule on the merge.

Figure 6 . 7 :

 67 Figure 6.7: Evolution of the frequency with a reduced speed.

Figure 6 . 8 :

 68 Figure 6.8: Evolution of ∆m k during disturbed operation.

4 |ΠΦ (j 1 ,j 4 ) 3 |Π

 4143 (j 2 ,j 1 ) Φ (i 1 ,j 2 ) Π (j 3 ,i 1 ) Φ (i 2 ,j 3 ) Π (j 4 ,i 2 ) (j 2 ,j 1 ) Φ (i 1 ,j 2 ) Π (j 3 ,i 1 ) Φ (j 1 ,j 3 ) (b) Here ψ = 1.

Figure A. 3 :

 3 Figure A.3: Two examples of cycles for an even (Figure A.3a) and odd (Figure A.3b) number m of trains. Both cycles go around the line once. In both cases, the cycles can either begin at j 1 or j 2 . The matrices Π and Φ are inverted in the latter case.

  |ρ|

2 .

 2 m odd: We also take two simple examples for the odd case to illustrate the cycles. In both examples, we take m = 3, and we take respectively ψ = 1 (Figure A.3b) and ψ = 2 (Figure A.4) in the first and second example.

3 |Π (j 2 ,j 1 )Φ (j 3 ,j 2 )Π (j 1 ,j 3 ) 3 | i 2 Φ

 321321332 (a) Arcs of the first lap. (j 2 ,j 1 )Π (i 1 ,j 2 ) Π (i 2 ,j 3 ) Φ (j 3 ,i 1 ) Φ (j 1 ,i 2 )(b) Arcs of the second lap.

Figure A. 4 :

 4 Figure A.4: The second type of cycle that exists when m is odd. The cycle goes around the line twice.

  |ρ| w = Υ ( j1 , j3 ) + • • • + Υ ( jn-m-1 , j1 ) = Φ ( j1 , j2 ) + Π ( j2 , j3 ) + • • • + Φ ( jn-m-1 , jn-m ) + Π ( jn-m , j1 ) = j2 q= j1 +1 s q + j3 q= j2 +1 s q + • • • + jn-m q= jn-m-1 +1

  1.1 Table with some of the line characteristics. . . . . . . . . . . . . . . . 3.1 Notations for the model. . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Average reliability data per year for our case study. . . . . . . . . . . 4.2 General notations for train dynamics. . . . . . . . . . . . . . . . . . . 4.3 Notations related to the skip-stop policy. . . . . . . . . . . . . . . . . 4.4 Notations related to the skip-stop policy. . . . . . . . . . . . . . . . . 4.5 Table with some of the line characteristics. . . . . . . . . . . . . . . . 4.6 Example of the alternate stopping patterns on the line. Only the skippable stations are written in the table. . . . . . . . . . . . . . . . 4.7 Table of the studied scenarios.

Table 1 .

 1 1: Table with some of the line characteristics.

	Conduction Stat.	Len.	Trav. time Ridership Min. head.
	Automated	25	16,6 km ∼33 min 184,4 Mill.	110 sec.

  2.4 gives us the other eigenvalues of our matrix.

	Proposition 2.4. [29, Proposition 2.2.3 on p. 132] ε is an eigenvalue of A if and
	only if a node exists in G(A) with no successor nodes (i.e., without outgoing arcs).

Table 3 . 1 :

 31 Notations for the model.

	n	number of segments
	O m	= {o 1 , o 2 , • • • } the set of all skippable stations. total number of trains
	l j

Table 4 .

 4 1: Average reliability data per year for our case study.

	Year	2013 2014 2015 2016 2017
	Trains' reliability 101.6 100.1 100.4 100.6 101.2
	Headway reliability 99.2 99.4 99.7 99.6 99.6
	Year	2018 2019 2020 2021
	Trains' reliability	99.6 100.1 100.1 102
	Headway reliability 99.3 99.4 99.4 99.3

Table 4 .

 4 2: General notations for train dynamics.

Table 4 .

 4 3: Notations related to the skip-stop policy. the train safe separation time ∀j. Note that in our model, we do not consider different safe separation times; they are the same whether a train stops at a j ∈ O station or not; A the set of stations at which the train performing service A stop; B the set of stations at which the train performing service B stop; AB = A ∩ B the set of mandatory stations, i.e., where all trains stop; O = A△B the set of skippable stations, i.e., where trains stop every other time.

	r p j w p j t p j s j	lower bound for the train run time for the service p ∈ {A, B} from node j -1 to node j, ∀j; lower bound for dwell time for the service p at node j, p ∈ {A, B} ; := r p j + w p j lower bound for train travel time for the service p ∈ {A, B}; lower bound for

different sets of stations. A and B give the stations where a train performing service A and B stops. The intersection of these sets AB gives the mandatory stations where all trains stop. Finally, the symmetric difference gives the stations of A and B but not their intersection and thus gives all the skippable stations O.

Table 4 .

 4 as all other trains on the line must have passed before it can depart again. The parity of k and (k + m) is the same if m is even and different if m is odd. When m is odd, the service changes with each successive lap, as determined by the parity of the departure at the first node. Different variables are listed for the two cases, with the superscripts e or o indicating whether the number of running trains is even or odd for each variable. Besides the number of running trains m, the average train travel times denoted T e ψ , T o ψ , or S, to go around the line significantly impact the headway and frequency. The notations are detailed in Table4.4. 4: Notations related to the skip-stop policy.

p ∈ {p 1 , p 2 } design any service. If p 1 = A, we have p 2 = B, and if p 1 = B, we have p 2 = A; ψ ∈ {0, • • • , n}, the number of nodes at which the service associated in T e ψ and T o ψ changes; o the first node of the line;

Table 4 .

 4 5: Table with some of the line characteristics.

	Conduction Stat.	Len.	Trav. time Ridership Min. head.
	Automated	25	16,6 km ∼33 min 184,4 Mill.	110 sec.

Table 4 .

 4 .6 shows an alternate service example on a line sample from station La Défense to station Château de Vincennes. All the results we explain in Section 4.4.2 are generalizable to any stopping pattern. 6: Example of the alternate stopping patterns on the line. Only the skippable stations are written in the table.

	Name P. de Neuilly Sablons	Arg.	George V Tui.
	Service	B	A	B	A	B
	Name	Louvre-R	St. Paul P. de Vinc. St. Man. Bér.
	Service	A	B	A	B	A

Table 4 . 7 :

 47 Table of the studied scenarios. The scenarios are summarized in Table 4.7. Moreover, Table 4.8 shows the station's types for the three scenarios. Scenario 1 has indeed fewer skippable stations. And the table shows how the stopping pattern changes between Scenarios 2 and 3.

	Scenario Nb. of skipped stations Stopping pattern
	1	6 (in both directions)	AB
	2	12 (in both directions)	AB
	3	12 (in both directions)	AAABBB

Table 4 . 8 :

 48 Table showing the difference between the services of the scenarios on the skippable stations in one direction. The bold stations are termini, and the stations written in italics show the difference between the scenarios.

		Def. PdN Sab. Arg. CdG G.V Tui.
	Scen. 1 AB	AB	A	B	AB	A	AB
	Scen. 2 AB	B	A	B	A	B	A
	Scen. 3 AB	B	B	B	A	A	A
		Lou. St. P. GdL PdV St.M. Ber. CdV
	Scen. 1	A	B	AB AB	B	AB AB
	Scen. 2	B	A	B	A	B	A	AB
	Scen. 3	B	B	B	A	A	A	AB

  is the maximum value for which α 2 T < T o ψ 2 . The maximum value is obtained at the intersection of the two lines α 1 m+ψ 1

	CHAPTER 4. MAX-PLUS MODELING OF A TWO-SERVICE SKIP-STOP
	POLICY	59
	and T o ψ 2 T ψ 1	and α 2 m+ψ 2 T ψ 2
		ψ 1

T e ψ 1 2. Similarly the derivative (∆f o fw ) ′ = αT -T o ψ T T o ψ is negative if αT < T o ψ and positive if αT > T o ψ . ∃ψ 1 , ψ 2 such that T o ψ 1 is the maximum value for which α 1 T > T o

Table 5 .

 5 1: Notations for passenger demand for the all-stop policy case. λ i,j base arrival rate of passengers traveling from station i to station j . θ ∈ R + , the passenger demand level for a fixed demand profile. α al passenger alighting rate in passenger per second. α bo passenger boarding rate in passengers per second. α in increase rate in seconds per passenger due to the crowding.

	λ al j λ bo j λ in j	sum of the passenger arrival rate alighting at station j. sum of the passenger arrival rate boarding at station j. sum of the passenger arrival rate in the train at station j.
	τ j	represents the technical time for the dwell time of a station j. It
		corresponds to the time taken to open and close the doors.
	x j	:= λ al j /α al j + λ bo j /α bo j + λ in j α in j , the passenger demand indicator at a
		station j.
		w j = τ j +	N al j α al +	N bo j α bo + N in j α in	(5.7)

Table 5 .

 5 2: Notations for passenger demand for the skip-stop policy case, ∀p ∈ {A, B}.

	λ p i,j

Table 5 .

 5 3: Theorem 5.1 variables p ∈ {p 1 , p 2 } design any service. If p 1 = A, we have p 2 = B, and if p 1 = B, we have p 2 = A; ψ ∈ {0, • • • , n}, the number of nodes at which the service associated in T e ), the sum of the run and technical times of a train to go from the first node of the line τ to any node i 1 with service p;

	ψ

Table 5 .

 5 6: Average analytical average train time headway.The average passenger waiting times are shown in Figures 5.11 and 5.12 for both all-stop and skip-stop policies. The all-stop and skip-stop waiting times have black and colored (blue and green) curves, while the solid, dashed-dotted, and dotted lines correspond to the different demand levels. The waiting times are computed using Equations (5.41) to(5.44) and are given for a range of train frequencies from 15 to 50, corresponding to the free-flow phase.

		λ 1		λ 2
		m = 20 m = 35 m = 50 m = 20 m = 35 m = 50
	θ = 1	h 210.03 113.31 h s 168.30 96.17	77.58 67.32	222.80 116.92 196.53 104.79	79.26 71.44
	θ = 2	h 243.69 122.43 h s 213.92 109.52	81.75 73.60	281.07 131.20 236.02 115.05	85.57 76.07
	θ = 3	h 290.19 133.15 h s 247.47 117.68	86.40 77.20	380.61 149.44 295.39 127.55	92.97 81.33

Table 5 .

 5 7: Difference in the average waiting time ∆ω in seconds.

		λ 1			λ 2
	m = 20 m = 35 m = 50 m = 20 m = 35 m = 50
	θ = 1 -75.94	-41.70	-28.73	-51.69	-28.44	-19.61
	θ = 2 -83.74	-43.99	-29.81	-55.69	-29.90	-20.32
	θ = 3 -92.88	-46.50	-30.96	-56.05	-31.25	-21.03
	and from mandatory stations decreases.

  Result of the product of ∆T i,j and λ 1 i,j .

	r g M a i. S a b P d N E s p . D e f (a) C h .v . Destination Ch.v. Ber SM PV Nat RD GL Bas SP HdV Cha Lou PR Tui Con CE Roo. GV CDG Arg Mai. Sab PdN Esp. Def Origin -20 -10 0 10 20 Passenger seconds ×10 4 B e r S M P V N a t R D G L B a s S P H d V C h a L o u P R T u i C o n C E R o o . G V C D G A r g M a i. S a b P d N E s p . D e f Destination Ch.v. Ber SM PV Nat RD GL Bas SP HdV Cha Lou PR Tui Con CE Roo. GV CDG Arg Mai. Sab PdN Esp. Def

  The comparison is made during the peak hour since this is the critical period of operation. The operating margins are reduced to maximize the frequency, especially in the study case, Paris metro line 13, one of the busiest lines of the network. A frequency f = 35 trains per hour, or equivalently an interval h = 100 seconds, is set to meet the passenger demand. The number of running trains is m = 51, set in the following examples to achieve this frequency. CHAPTER 6. IMPACT OF A FIFO RULE ON A LINE WITH A JUNCTION 107

  + t p 1 i 1 + s i 1 + t p 2 i 2 + s i 2 (A.39)and the length is equal to 2 = m/2 + ψ/2. If ψ is odd, then m/2 + ψ/2 is not a natural number which is not possible. We can generalize to any even ψ

		i 1			j 2		i 2	j 3
				t µo q +		t µe q +	t µo q +	t µe q + t µe i 1 + s i 1
		p=j 2	j 4	j 1	j 4	j 3	i 1	(A.38)
		+	t µo q +	t µe q + t µe i 2 + s i 2
				j 1		i 2
		i 2			i 1
	=	t p 1 q +	t p 2
		i 1			i 2
		i 1						i 2
	|ρ| w =	i ψ +1	t p 1			i 1 +1	t p 2 q + (t p 2 i 1 + s i 1 )	(A.40)

w = q q + (t p 1 i ψ + s i ψ ) + • • • +

  = T A + T B + t A i 1 + s i 1 + t B i 1 + s i 1 (A.45)

	j 1		j 2		i 1
		t µo q +		t µe q + t µe i 1 + s i 1 +		t µo q
	p=j 2	j 1	i 1	j 2	j 1	i 1	(A.44)
	+	t µe q +	t µo q + t µo i 1 + s i 1 +	t µe q
		j 2		i 1		j 1

w =

  i 1 ,τ (A.47) If the cycle starts at i 1 instead of τ , the weight of the cycle becomes

			τ	j 3		j 2	i 1
			=	t p 2 q +	t p 2 q +	t p 2 q + (t p 2 i 1 + s i 1 ) +	t p 1 q	(A.48)
			j 3 +1	j 2 +1		i 1 +1	τ +1
			τ				i 1
			=	t p 2 q + (t p 2 i 1 + s i 1 ) +	t p 1 q	(A.49)
			i 1 +1			τ +1
	|ρ| w =	τ i 1 +1	t p 1 q + (t p 1 i 1 + s i 1 ) +	i 1 τ +1

  • • • + (t p 2 i + s i ) + (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) + • • • + (t p 2 i ψ + s i ψ ) + (t p 2 i + s i ) + (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) + • • • + (t p 2 i ψ + s i ψ ) p 1 i 1 + s i 1 ) + • • • + (t p 2 i + s i ) + (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) + • • • + (t p 2 i ψ + s i ψ )

	128											A.7. CYCLES
			i 2				i ′′′				i 1
	|ρ| w =	q=i 1 +1	t p 1 q + • • • +	q=i+1	t p 2 q + • • • +	q=i ψ +1	t p 2
		i 2			i ′			i ′′			i ′′′	i 1
	|ρ| w =	q=i 1 +1	t p 1 q + • • • +	q=i+1	t p 2 q +	q=i ′	t p 2 q +	q=i ′′ +1	t p 2 q + • • • +	q=i ψ +1	t p 2

q + (t p 1 i 1 + s i 1 ) + • • • q + (t

  p 1 i 1 + s i 1 ) + • • • + (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) + • • • + (t p 2 i ψ + s i ψ ) /(m + ψ) + (t p 1 i 1 + s i 1 ) + • • • + (t p 2 i ψ + s i ψ ) + (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) /(m + (ψ -2) + 2) +1 t p 1 q + • • • + i 1 q=i ψ +1 t p 2 q + (t p 1 i 1 + s i 1 ) + • • • + (t p 2 i ψ + s i ψ ) m + (ψ -2) , (t p 1 i ′ + s i ′ ) + (t p 2 i ′′ + s i ′′ ) 2 (A.58)

							(A.56)
		
			i 2		i 1
	=		q=i 1 +1	t p 1 q + • • • +	q=i ψ +1	t p 2	(A.57)
				i 2
	≤ max	q=i 1

q

In the Paris network, some mass-transit lines share tracks with other suburban, high-speed, or freight lines. However, this is not the case for the parts operated by the RATP group, so these cases fall outside the scope of our study.

Some punctuality values exceed 100%. On certain days, the company may have run more trains than scheduled.

4.4. THE STEADY STATE OF THE TRAIN DYNAMICS

We consider the average between the two services because the number of passengers on each train for both services is roughly equivalent. This makes it easier to compare with the all-stop policy.

96 6.1. THE MODEL of trains on the three parts of the line (the central part and the two branches). Next, we study train frequency in two disruptive situations that often occur on a metro line. We show that the FIFO rule reduces the impact of these disruptions in time and intensity. This work is the first step towards seeing the evolution of frequency on a line with a junction.

The Model

In this section, we develop our model. It considers a First-In-First-Out (FIFO) rule on the merge of a line with a junction. First, we give a schematic representation of the line and the notations necessary for the train dynamics. Then, we clarify our model's two constraints. Finally, we also give some properties of our model. the number of segments on branch u. J(u) = {1, . . . , n u } the set of indices of the branch u. b (u,j) boolean variable giving the initial state of the line. b (u,j) = 1 if there is a train the segment j of the branch u, b (u,j) = 0 otherwise. b(u,j) = 1b (u,j) . m u the number of trains on branch u. m u m u the total number of running trains on the line. r k (u,j) k th run time at the segment j of the branch u. w k (u,j) k th dwell time at the segment j of the branch u. t k (u,j) = r k (u,j) + w k (u,j) , k th travel time at the segment j of the branch u. s k (u,j) k th safe separation time at the segment j of the branch u. h k (u,j)

Notions & Line Discretization

k th headway at the segment j of the branch u. d k (u,j)

k th departure at the segment j of the branch u; the train dynamics of our model evaluate all the departures at each iteration k. ∆m := m 2m 1 is the difference between the number of trains on Branch 2 and 1 at the initial state. mu := n um u , ∀u ∈ U. m := m0 + m1 + m2 . ∆ m := m2 -m1 . T u := j t (u,j) , ∀u ∈ U. S u := j s (u,j) , ∀u ∈ U. We consider that the trains depart when both constraints are satisfied for all the line nodes. Therefore, the departure is equal to the maximum value given by the two constraints; for example, out of the junction, we have

+ s (u,j+1) .

Counters & Dynamic Number of Trains

In the next section, we simulate the line's train dynamics to obtain the line's asymptotic average train time-headway (estimated at each node (u, j) by h (u,j) = lim k→∞ d k (u,j) /k). The asymptotic average train frequency at a node (u, j) is then estimated as f (u,j) = 1/h (u,j) . Before that, we give some properties on the evolution of the number of trains on each branch with the new FIFO rule on the merge and the departure counters k u for each branch.

Dynamic Number of Trains on the Branches with the FIFO Rule

Let m k u be the number of trains on the part u of the line after each iteration k. In [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF], the model uses a one-over-two rule on the divergence and the merge, and the trains' running order is defined such that when a train pulls to Branch u at the divergence, the train entering the central part comes from the same branch. Thus, ∀u m k u is constant and independent of the iterations k when a one-over-two rule is set on the line. Therefore, ∀u, k, we have m k u = m k-1 u +1-1 = m u , and ∆m k = ∆m. However, with the FIFO rule on the merge of the line, the train leaving the central part can pull to a branch while the one entering the central part can come from the other one. With m k in,u := 1 (resp. m k out,u := 1) if a train pulls to (resp. leaves) the branch u at the k th departure, and 0 otherwise, we have

, Moreover, if a train enters or leaves Branch 1 (resp. 2), there is no train entering or leaving Branch 2 (resp. 1); thus

. Finally, note that there is always one train leaving and one entering the central part at every iteration. Therefore the number of trains on the central part is constant, m k 0 = m 0 . Let us define the dynamic difference in the number of trains between Branch 2 and Branch 1 for each k,

(6.13) Proposition 6.1. The parity of ∆m k is constant ∀k, i.e.

with α ∈ {-1, 0, 1}.

Proof.

In the following sections, we study the asymptotic behavior of ∆m k and its impact on the train frequency on the line in nominal and disturbed operations.

Evolution of the Counters and the Difference in the Number of Trains between the Two Branches

As mentioned above, the growth rate of the departure counters is not the same for the central part and the branches. We give in Table 6.2 an example of the evolution of the values of k, k 1 , and k 2 . We also give the evolution of ∆m k , the difference in the number of trains between the two branches. In [START_REF] Schanzenbächer | A discrete event traffic model explaining the traffic phases of the train dynamics in a metro line system with a junction[END_REF], the variable ∆m significantly impacts the train frequency. With our FIFO rule, this value change after each iteration k, and thus, it will impact the value of the train frequency. Table 6.2: Evolution of the counter k, k 1 , k 2 , and ∆m k at the divergence and the merge of the line.

Divergence, (0, n 0 ) Merge, (0, 0)

This table shows a simple example of the evolution of the counters. For the divergence, the alternations of the trains to the branches give directly k = 2k 1 -1 and k = 2k 2 . For the merge, there exists a relation between the three counters: k = k 1 + k 2 . However, it is impossible to give a relation of k with only k 1 or k 2 . In this example, we have the first two trains from Branch 2 entering the central part and four trains from Branch 1. Thus, we have

The first train departing from the last node of Branch 1 arrives at the merge after the two first of Branch 2. Similarly, the third train departing on the last node of Branch 2 arrives after the fourth train departing from Branch 1. This example also shows how the running order on the merge influences the values of ∆m k .

Appendix A

Proof of Theorem 4.3

A.1 Insights

In this section, we prove the main theorem of the paper and thus the existence of a stationary regime for the train dynamics; and, thus, to derive the asymptotic average train time headway corresponding to the dynamics given as

The train dynamics being linear in the Max-plus algebra, it then admits a stationary regime where the asymptotic average growth rate lim k→∞ d k j /k for every variable d j is interpreted as the asymptotic average train time-headway on node j. We show below that the asymptotic average growth rate and train time-headway are the same for every variable d j (node j). It is known that for a Max-plus linear system, the average asymptotic growth rates are given by the eigenvalues of the Max-plus matrix defining the linear system. Therefore, to find the train time headway, we need to find the eigenvalues of the matrix Υ. The eigenvalues are given by the cycle means of the matrix. In the case of an irreducible matrix A, the eigenvalue is unique and equal to the maximum cycle mean of its associated graph. However, the matrix Υ is reducible and admits multiple eigenvalues. We show in Appendix A.6 that the maximum cycle mean of the graph G(Υ) is the only non-zero (̸ = ε) eigenvalue. Thus it corresponds to the asymptotic average growth rate of the dynamics. Therefore, our goal is to list all the cycles of the graph G(Υ) associated with the matrix Υ. As Υ = ΦΠ, the weights of the arcs of G(Υ) are the results of the products of the arcs of G(Φ) and G(Π). The shape of these two matrices depends on the value of the initial positions of the trains b. The Appendix A.2 derives the notations that differentiate the nodes with and without trains at the initial state. In Appendices A.3 to A.5, we show that even if the matrices are different for each initial position, similar patterns exist. First, the non-zero entries of Π and Φ are the same. Then, we show that it is possible to determine the value of each non-zero entry depending on the type of the beginning and end nodes. Therefore, we also determine the values of the product of Φ and Π, giving the weights of the arcs of G(Υ). Finally, in Appendix A.7, all the cycles that exist in the graph G(Υ) are given. We give in Appendix A.7.4 a proposition that shows that the number of cycles involved in the theorem depends on the number of skippable stations.

A.2 Notations & Preliminary Remarks

A.2.1 Preliminary Remarks

1. The line is a closed system, which means that for a line with n segments,

2. The reasoning is exactly the same for the matrices Π = Π * 0 Π 1 and Φ = Φ * 0 Φ 1 . The non-zero entries of both matrices depend only on the values of b j , and bj , and these values depend on the service and are described by µ e for Π, while µ o contains the service characteristics for Φ. Therefore, the first part of the proof is only clarified for the matrix Π. We still detail all the equations for both matrices.

3. To simplify the readability, all the proof is written in conventional algebra.

A.2.2 Notations

In this proof, we use some specific notations slightly different from those introduced in the modeling section. They are detailed below. τ is the node corresponding to the terminus. By convention, we set it as the first node of the line without loss of generality.

A.3 The Max-plus Inverse of the Matrices

By definition, we have ∀j ∈ J, bj = 1b j , which mean that we have either (Π 0 ) (j,j-1) = t j or (Π 0 ) (j-1,j) = s j , so the graph G(Π 0 ) associated to Π 0 is acyclic, i.e Π 0 is nilpotent, that is Π k 0 = 0 for a k sufficiently large. The largest k for which ∃i, j such that (Π k 0 ) (i,j) ̸ = 0 depends on the initial position of the trains. All the non-zeros entries of the matrix Π 0 are in the upper diagonal, (Π 0 ) (j,j+1) ̸ = 0, and the lower diagonal elements, (Π 0 ) (j,j-1) ̸ = 0.

• ∃i, i ′ such that (Π 3 0 ) (i,i ′ ) ̸ = 0 if and only if three consecutive segments j, j + 1, j + 2 exist such that either

Therefore, the largest value of k for which (Π k 0 ) (j ′ ,j-1) and (Π k 0 ) (j,j ′ ) is equal to the maximum between the number of consecutive segments j, j + 1,

We now explicit the non-zeros values of Π * 0 and Φ * 0 :

• Let j ′ ≥ j and Γ = j ′j + 1 be the number of consecutive segments such that

and (Φ * 0 ) (j+γ,j-1) = j+γ q=j t µo q (A.2)

• Let Γ = j′ -j +1 be the number of consecutive segments such that bj = bj +1 =

The section details the arcs in the graphs G(Π). We recall that the G(Φ) arcs are the same except for the weight. Two main cases are possible 1. ∀j ∈ J such that b j+1 = 1, we have (Π 1 ) (j+1,j) = t µe j+1 . The j th column of Π has non-zero entries if and only if

• The diagonal elements of Π * 0 are equal to 0, thus Π (j+1,j) = (Π * 0 ) (j+1,j+1) + (Π 1 ) (j+1,j) = 0 + t µe j+1 = t µe j+1 .

• The number Γ of consecutive segment with no train at the initial state Γ is equal to Γ = j ′j -1, with j ′ the closest segment with b j ′ +1 = 1 in the direction of traffic (if j ′ = j + 1, there is no segment with no train and Γ = j ′j -1 = 0). Using equation Equation (A.1), we obtain ∀γ,

and Φ (j+1+γ,j) = j+1+γ q=j+1 t µo q (A.7)

• Since (Π 1 ) (j+1,j) = t µe j+1 , we have (Π * 0 ) (j,j+1) = s j+1 . Let Γ = j -j′ be the number of consecutive segments with a train at the initial position, with j′ ∈ J the closest segment (in the opposite direction of the trains) with bj′ = 1. Then ∀γ, 0 ≤ γ < Γ Π (j-γ,j) = (Π * 0 ) (j-γ,j+1) (Π 1 ) (j+1,j) = j+1 q=j+1-γ s q + t µe j+1 (A.8)

and Φ (j-γ,j) = j q=j-γ s q + (t µo j+1 + s j+1 ) (A.10)

In the case where γ = 0, we have Π (j,j) = t µe j+1 + s j+1 and Φ (j,j) = t µo j+1 + s j+1 .

2. The second case when there is no train on the segment j ∈ J such that bj = 1 and (Π 1 ) ( j-1, j) = sj. Likewise, the three same cases exist such that the jth column of Π has non-zeros entries but in the opposite direction.

• Π ( j-1, j) = (Π * 0 ) ( j-1, j-1) + (Π 1 ) ( j-1, j) = 0 + sj = sj = Φ ( j-1, j)

• Let j ′ be the first segment in the direction of the train where b j ′ = 1.

APPENDIX A. PROOF OF THEOREM 4.3 119

Then Γ = j ′ -jq , ∀γ, 0 ≤ γ < Γ we have

t µe q + (t µe j + sj) (A.12)

and Φ ( j+γ, j) = j+γ q= j+1

t µo q + (t µo j + sj) (A.13)

If γ = 0, then Π ( j, j) = t µe j + sj and Φ ( j, j) = t µo j + sj • Finally, the number Γ of successive segments with no train in the opposite direction of traffic is defined as Γ = j -j′ -1, with j′ the closest segment with j′ = 1 in the direction of traffic. We obtain ∀γ,

and

A.5 Properties of the Matrices Π and Φ

The arcs of Υ are an alternation of the arcs of Π and Φ and an alternation of µ e and µ o . We have ∀q ∈ {1, . . . , n} µ e j := A if j q=0 b q is even B otherwise (A.17)

Using Equations (A.17) and (A.18), it is possible to determine the link between the services A, B and the parity variables µ e and µ o depending on the initial state.

Proposition A.1. ∀j, j ′ , j ′′ ∈ J, such that j 1 ≤ j ≤ j ′ ≤ j ′′ ≤ j m . And, ∀i ∈ I such that j < i < j ′ :

and

Proof.

1. ∀i such that j < i < j ′ , the parity of value of i q=0 b q is constant, thus µ e,i and µ o,i are also constant, i.e µ e,i = p 1 and µ o,i = p 2 .

2. Directly from the previous point, the arcs Π (i,jq+1) (or Φ (i,j ′ ) ) and Φ (j ′ ,i) (or Π (j ′ ,i) ) have weights associated to opposite services.

3. ∀i, i ′ , j < i < j ′ < i ′ < j ′′ , we have µ e i = µ o i ′ ̸ = µ e i ′ = µ o i , since the parity of i q=0 b q and i ′ q=0 b q is different. And thus,

Remark 1. The strict inequality case for j 1 ≤ j ≤ j ′ ≤ j ′′ ≤ j m requires m > 4.

The same reasoning hold for m ≤ 3. For example, if m = 1, Π (j ′ ,j) = j (mod n) j+1 t p 1 q = q t p 1 q , and Φ (j ′ ,j) = q t p 2 q A.6 Reducible Matrix

Both matrices Π and Φ are reducible, making the matrix Υ reducible. There is at least one column with only null values. Theorem 2.2 is valid for strongly connected graphs, i.e., to irreducible matrices. This theorem is generalized to reducible matrices under some conditions.

Proposition A.2. The matrix Υ has only one non-zero eigenvalue equal to the maximum cycle mean of its associated graph.

Proof. From Theorem 2.2, there exists only one eigenvalue for the matrix if the graph is strongly connected. Nevertheless, this eigenvalue exists in the case of reducible matrices. From Proposition 2.4, the nodes with no successors in a matrix give eigenvalues equal to ε.

All the nodes graph G(Υ) excluded from the cycles are nodes with no successors. Thus, the only non-zero eigenvalue is given by the maximum cycle mean of its associated graph.

A.7 Cycles

We remind that our dynamic is written d k = Υd k-2 , which means that the growth rate of the matrix is equal to twice the headway.

A.7.1 Capacity Phase

To find the line capacity, we use Equations (A.9) and (A.12) in the specific case where γ = 0 or γ = 0. ∀q, we have by definition either b q+1 = 1 or bq+1 = 1. In the 121 first case, we have Π (q,q) = t µe q+1 + s q+1 and Φ (q,q) = t µo q+1 + s q+1 and in the second case Π (q+1,q+1) = t µe q+1 + s q+1 and Φ (q+1,q+1) = t µo q+1 + s q+1 . Thus ∀q Υ (q,q) = Φ (q,q) + Π (q,q) = t µo q+1 + s q+1 + t µe q+1 + s q+1 , if b q+1 = 1 (A. [START_REF] Fan | Planning skip-stop services with schedule coordination[END_REF])

To find the maximum cycle mean of the cycles looping on one node, we need to take the maximum overall q. The maximum cycle mean ρ max is given by ρ max = max q t p 2 q + s q + t p 1 q + s q = max q t A q + s q + t B q + s q and therefore h min = max q (t A q + s q + t B q + s q )/2 (A.21)

A.7.2 Free-Flow Phase without Combinations

For the free-flow phase, we examine the cycles such that ψ = 0. These cycles combine arcs linking the nodes with a train at the initial states. ∀j, j ′ , j ′′ ∈ J such that j 1 ≤ j ≤ j ′ ≤ j ′′ ≤ j m , we have Υ (j ′′ ,j) = Φ (j ′′ ,j ′ ) + Π (j ′ ,j) , and this arc has a weight of 1. We need to distinguish the cases where the number m of trains is even or odd.

1. m even: If we denote by ρ 1 the path starting at j 1 and ρ 2 the path starting at j 2 , we have for the weights:

and

In both cases, there are m arcs of the matrices Π and Φ and so m/2 arcs of Υ, i.e. |ρ| l = m/2. Finally, by taking the maximum between ρ 1 and ρ 2 , the headway is given by half of the maximum: 1a andA.1b, the cycles can either start respectively at j 1 or j 4 , or j 2 or j 4 and the weight of the cycles are respectively given by: Φ (j 3 ,j 2 ) + Π (j 2 ,j 1 ) Υ (j 3 ,j 1 )

+ Φ (j 1 ,j 4 ) + Π (j 4 ,j 3 ) Υ (j 1 ,j 3 )

= T A , and

(a) Cycle beginning at either node j 1 or j 3 .

|

m odd:

In the case where m is odd, there is only one possible path. The starting node does not influence the cycle. The weight of this cycle is given by: Π (j 2 ,j 1 ) + Φ (j 3 ,j 2 ) + Υ (j 2 ,j 3 )

A.7.3 Free-Flow Phase with Combinations

Now consider all free-flow phase cycles with ψ > 0. These cycles also go in the direction of traffic but combine arcs defined by Equations (A.6), (A.7), (A.12) and (A.13).

Unlike the case where ψ = 0, the arcs of the matrices Π and Φ can connect some nodes j ∈ J to other nodes i ∈ I or vice versa. We can use Proposition A.1 to emphasize the alternation of services during cycles. We know that the cycle alternates arcs of the matrices Π and Φ, and we want to know if the values allocated in µ e and µ o for two consecutive arcs are the same or opposite services. Two cases are possible:

1. If the end node of an arc is a node j ∈ J, the values allocated in the weights of this arc and the following one belong to the same service.

2. If the end node of an arc is a node i ∈ I, this arc's weight and the next one's weight contain values of opposite services.

We show some examples for a fixed number m of trains and ψ before generalizing to all m and ψ values. Again, there is a difference between the cases where m is even and odd.

129

The length of this path is given by |ρ| l (nm)/2. The headway is thus directly given by this cycle divided by two: Remark 2. The cycles are again different depending on the parity of n-m. Indeed, for an odd nm the path ρ ′ is given by ρ ′ = q sq+ q sq (n-m)

= ρ which gives the same headway.

There are other cycles in the opposite direction of the train. They are the combination of arcs used to find h bw and those detailed in Equation (A.9). These cycles are similar to those that give h e fw and h o fw . ∀ ī1 , • • • , īψ , the cycle is defined as ρ = ī2 q= ī1 +1 s q + • • • + ī1 q= īψ +1 s q + (t p 1 ī2 +1 + s i 2 ) +