# The time slot allocation problem in liberalised passenger railway markets: a
multi-objective approach

Nikola Bešinovića, Ricardo García-Ródenasb, María Luz López-Garcíab, Julio
Alberto López-Gómezc †, José Ángel Martín-Baosb †Corresponding Author
aTechnische Universität Dresden, Dresden, Germany; bEscuela Superior de
Informática, Universidad de Castilla-La Mancha, Ciudad Real, Spain; cEscuela
de Ingeniería Minera e Industrial de Almadén, Universidad de Castilla-La
Mancha, Almadén, Spain

###### Abstract

The liberalisation of the European passenger railway markets through the
European Directive EU 91/440/EEC states a new scenario where different Railway
Undertakings compete with each other in a bidding process for time slots. The
infrastructure resources are provided by the Infrastructure Manager, who
analyses and assesses the bids received, allocating the resources to each
Railway Undertaking. Time slot allocation is a fact that drastically
influences the market equilibrium. In this paper, we address the time slot
allocation problem within the context of a liberalized passenger railway
market as a multi-objective model. The Infrastructure Manager is tasked with
selecting a point from the Pareto front as the solution to the time slot
allocation problem. We propose two criteria for making this selection: the
first one allocates time slots to each company according to a set of
priorities, while the second one introduces a criterion of fairness in the
treatment of companies to incentive competition. The assessment of the impact
of these rules on market equilibrium has been conducted on a liberalized high-
speed corridor within the Spanish railway network.

###### keywords:

Time Slot Allocation Problem; liberalised passenger railway markets; multi-
objective optimisation

††articletype: ARTICLE TEMPLATE

##  1 Introduction

In the last years, the European Directive EU 91/440/EEC has produced a
significant change in the European passenger railway markets. This directive
aims to facilitate the adoption of the Community railways to the Single Market
and to increase their efficiency. To do that, it is intended to separate the
infrastructure management from the provision of transport services and ensure
access to the networks of the Member States for Railway Undertakings. The
European so-called 4th railway package (EU Regulation 2016/2338) aims to
remove the remaining barriers to the creation of a single European rail area.
Additionally, the updated legislation includes the proposal to open up
domestic passenger railways to new entrants and services from December 2019.
This way, Railway Undertakings will be able either to offer competing
services, such as a new train service on a particular route, or to bid for
public service rail contracts through tendering.

The objectives of competition in the railway industry encompass several key
aspects, including fare reduction (Vigren (2017)), enhanced service
frequencies (as discussed in Tomeš et al. (2016)), and improved timetables (Li
et al. (2019), Yang et al. (2023)), among other factors. These efforts
collectively aim to stimulate higher demand for railway services.

Two common market integrations are present: vertical and horizontal. The
former represents a single operator (the so-called incumbent operator or
national railway undertaking) that operates in a monopoly situation and
assumes a captive demand, which was customary in the member states of the
European Union. The latter, also known as open passenger railway market, new
railway operators (the so-called entrants) compete with each other for the
time slot to which rail services are allocated. However, the expected
transition from a vertical to a horizontal market has been very difficult
(Nash (2008), Cantos-Sánchez, Pastor Monsálvez, and Serrano-Martínez (2021)).
Some of the barriers that entrants face and that jeopardise fair competition
among operators are: inferior resources with respect to the incumbent operator
or the lack of regulations to ensure fair competition, among others (Ristić,
Stojadinović, and Trifunović (2022)).

In a liberalised passenger railway system, there are three main interrelated
actors: the Infrastructure Manager (IM), the Railway Undertakings (RUs) and
the demand, which is represented by passengers. The IM is the owner and the
manager of the railway infrastructure. The RUs, also known as train operating
companies, are the companies that offer rail services to passengers using the
infrastructure of the IM. Finally, the demand corresponds to passengers who
want to make use of rail services to satisfy their transport needs for
reaching from their origin to destination. The dynamics in a liberalised
passenger railway system is the following: (i) the IM assigns capacities,
which means a maximum number of time slot in which to operate, to each RU;
(ii) the RUs, taking into account their assigned resources, place their bids
to the IM in order to obtain a set of time slot in which to operate; (iii) the
IM allocates time slot to the RUs, taking into account the bids received and
the capacities assigned; and (iv) passengers choose one trip or another
according to the final offer.

The dynamics described above define a complex system of relationships between
the actors, in which the particular interests of each of them conflict with
the optimal performance of the system. The IM has a central role in the whole
system, as their decisions to allocate time slots to different RUs may affect
the equilibrium of the system and even lead to a monopoly situation. It is a
critical process in order to guarantee fair competition between the RUs, since
an unfair allocation or one that benefits the incumbent operator may affect
the profitability and performance of the other RUs and the whole system
(Broman and Eliasson (2019)).

In this context, there is a need to design optimal decision-making procedures
in open passenger railway markets which guarantee equal treatment for all RUs
involved in order to improve the socially efficient use of the railway system.
It motivates the purpose of this paper: study how the decisions made by the IM
when allocating time slots have an impact on the equilibrium state and
determine the benefit of RUs.

Time slot allocation can be addressed using different approaches (Broman,
Eliasson, and Aronsson (2022)): to carry it out, the IM can use an auction-
based criterion or set different prices for each time slot in order to
encourage certain frequencies. In this work, the latter situation is analysed
with the aim of considering how the IM should act when all companies are
willing to pay such an amount and the role of IM is that of an arbiter of bids
rather than a selfish role of maximising its own profit.

This work proposes a new framework for Time Slot Allocation in Open railway
markets (TSA-OPEN) problem in markets where multiple RUs operates under
competition. For this purpose, TSA-OPEN problem is considered within an
equilibrium model. Thus, for each of the RUs in the market, we obtain what
their bid for operating rights in the time slots will be. This bid is so-
called “strategy” and can be made up, in turn, of different requests or bids
that the company can make with a given probability. The TSA-OPEN problem is
formulated as a multi-objective optimisation problem as the IM has to deal
with the conflicting interests of the different RUs. The canonical objective
function of this problem is the profit function of the RUs. However, it
remains unknown because its computation would require access to confidential
data from them. In order to propose a criterion that can be shared by all
participants, the distance between the time slot requested and the time slot
allocated is transformed into a criterion that is transparent and known to all
participants. The solution of this problem leads to multiple admissible
solutions on what is known as the Pareto front. However, although any of these
solutions is acceptable, the market equilibrium situation varies considerably.
Two different criteria are proposed for the selection of such solutions by the
IM: (1) the IM allocates time slots to each RU according to a set of
priorities, (2) the allocation is made on the basis of a fairness criterion in
order to treat all RUs equally. We conducted computational experiments to
assess the real impact of the decisions made by the IM on the system. The
scenario under analysis is the liberalized high-speed corridor in the Spanish
railway market, which connects Madrid and Barcelona. We examined the criteria
mentioned above while assuming that all features of RUs are equal, and our
findings demonstrated significant differences based on the applied criterion.

The following are the main contributions of this article:

  * •

A mathematical multi-objective optimisation formulation of the time slot
allocation problem for multiple RUs is provided. This formulation places the
role of the IM at the centre as the arbiter in the deployment of the competing
market.

  * •

Two selection criteria are introduced to assign the time slot: the use of
priorities in the treatment of RUs and the application of an equity rule to
treat all of them equally.

  * •

An equilibrium model is proposed in order to integrate TSA-OPEN into the
bidding process of RUs to achieve a market equilibrium.

  * •

TSA-OPEN problem using the two proposed selection criteria are solved by using
heuristic and exact approaches and their performance is compared.

  * •

The experiments conducted in this paper provide numerical evidence of how the
criterion used by the IM significantly influences the equilibrium state,
consequently affecting the economic performance of the RUs.

  * •

As a result of the above, the proposed framework constitutes a first fair
approach to solve TSA-OPEN. The results underline the importance that the
criteria employed by IM must be known by the RUs.

Finally, the rest of the paper is organised as follows. Section 2 reviews the
literature related to the time slot allocation problem. Then, section 3
describes the methodology employed in this work, including the necessary
background about liberalised passenger railway systems and the formulation of
TSA-OPEN problem. Later, section 4 describes the heuristics to solve the TSA-
OPEN problem. Section 5 shows the experiments carried out and the results
obtained in a high-speed corridor in the Spanish railway network. Finally,
section 6 summarises the conclusions and further works derived from this work.

##  2 Related work

In this section, the most recent methods for time slot allocation in
classical/closed/monopolistic and open/liberalised railway markets are
discussed. Then, the reviewed methods for liberalised passenger railway
markets are compared to the proposed time slot allocation methods of this
paper. Summarily, Table 2 shows this comparison. Finally, the scientific gaps
are stated.

###  2.1 Classical railway market

Before the appearance of the EU regulations, which opened the door to the
liberalisation of the European railways markets, the most common organisation
of them was a completely integrated vertical and horizontal structure (Ait-Ali
(2020)). It means there was a single actor which had a monopoly on the system,
acting as IM and RU (Ait Ali and Eliasson (2019)). This way, the time slot
allocation in this type of system was closed, opaque and carried out
internally by the actor who monopolised the market (Ait-Ali (2020)).

The absence of competition in this market structure meant the aim of the time
slot allocation problem was to build a feasible train timetable which
maximised the profit of the company (Caprara et al. (2007)) and not violate
track capacities and other operational constraints. In this kind of market,
this problem is called the Track Allocation Problem (TAP) or Train Timetabling
Problem (TTP). More formally, Schlechte (2012) formulated this problem in the
following way: given a macroscopic railway model and a set of train slot
requests, the solution of TTP will be the subset of train requests which will
be addressed as well as their exact arrival and departure times of the trains
which will provide the service.

The most traditional approaches to address this problem in single-track
railway networks are Integer Linear Programming (ILP) and Mixed-Integer Linear
Programming (MILP) models (Carey and Lockwood (1995), Higgins, Kozan, and
Ferreira (1996)). In order to solve the problem, a wide variety of methods
have been applied. Due to the fact that TTP is an NP-hard problem, solution
approaches based on heuristics have been widely applied, such as greedy
heuristics (Cai, Goh, and Mees (1998)), tabu search and genetic algorithms
(Higgins, Kozan, and Ferreira (1997)).

TTP problem in general railway networks has also been traditionally addressed
by means of graph theoretic formulations (Caprara, Fischetti, and Toth
(2002),Caprara et al. (2006)). Departing from these works, many other
modifications have been proposed, leading to ILP models and Lagrangian relaxed
ones which are also solved by means of heuristic algorithms (Cacchiani,
Caprara, and Toth (2008)). Interested readers can consult Lusby et al. (2011)
for more information on such models and solutions.

###  2.2 Liberalised railway market

Under the new regulation, state-owned companies (incumbents) have given rise
to the IM and RUs. In the EU, two models have emerged. The first involves
splitting the incumbent company into two independent entities —one focused on
network management and the other on transportation. This scenario is
exemplified by the Spanish and Italian railway markets. The second structure
entails replacing the incumbent company with a holding company comprising two
separate entities. France and Germany are instances whose railway markets
follow this arrangement. The market structure’s impact is pivotal in fostering
competition. Table 1 lists the names of the companies in these railway
markets.

Country | Railway undertakings | Infrastructure Manager
---|---|---
Spain | RENFE, OUIGO, IRYO | ADIF
Italy | Trenitalia, Italo | RFI
France | SNFC VOYAGEURS, Trenitalia | SNFC Réseau
Germany | DB | DB Netz

Table 1: Examples of open markets

In liberalised or open-access railway systems, competition marks the
development of models to represent this type of market. Thus, the models built
must take into account the conflicting interests between the IM, the different
RUs and also the interests of passengers in order to maximise the profit of
all actors involved and contribute to social welfare. This way, the existing
approaches are more focused on passenger’s behaviour and on the fair
allocation of time slots to the RUs regarding the classic models, which are
mainly focused on railway operations.

TSA-OPEN is a key problem to ensuring fair competition in competitive and
open-access railway markets. It can be broadly defined as follows: given a set
of RUs, a set of time slots, the capacities of each RUs to operate them and
the bids of the different RUs to operate the time slot, the result of TSA-OPEN
will be an allocation of the time slot to the different RUs. According to
Broman, Eliasson, and Aronsson (2022), fairness is one of the most important
features that a TSA-OPEN method must meet. It is the task of IM to allocate
time slots to different RUs taking into account the capacities of each one and
solving the conflicts between them. A conflict or conflict state occurs when
two or more RUs apply for access to the same track at the same time (Schlechte
(2012)). In open-access competitive railway markets, conflict situations are
frequent, since they are encouraged by the number of RUs in the market and the
amount of traffic on the network among others (Broman, Eliasson, and Aronsson
(2022)).

Traditionally, the time slot allocation problem has been solved through
negotiations between the IM and the RUs, voluntary agreements and other simple
criteria (Stojadinovic, Boskovic, and Bugarinovic (2019)). However, these
methods are not very effective in competitive and open-access markets (Broman,
Eliasson, and Aronsson (2022)). Currently, the main methods to solve the time
slot allocation problem are grouped into three main approaches (Broman,
Eliasson, and Aronsson (2022)): based on administrative and collaborative
procedures (ACP), approaches based on social cost-benefit analysis (CBA) and
allocation based on Willingness-to-pay (WTP).

The first approach for time slot allocation methods is based on ACP. This
approach is used in all European Union (EU) countries and consists of applying
a set of simple and pre-defined criteria to solve conflicts. Concerning this
approach, Broman, Eliasson, and Aronsson (2022) describes the case of the
Belgium railway market, where the IM classifies the train services according
to priorities and when the conflict occurs, the least-priority class of
service is adapted. Another recent example is Trafikverket (2020). In this
document, the time slot allocation procedure of the Swedish railway market is
described. In it, the different RUs submit their time slot request to the IM
according to the national network statement. Then, the IM makes the allocation
solving minor conflicts by means of small adjustments. Major conflicts are
solved by means of informal discussions between the involved RUs. If an
agreement is not reached, the IM solves the conflict using a set of rules of
pre-defined criteria. The main advantages of administrative and collaborative
procedures are usually that they are very clear and simple (Broman, Eliasson,
and Aronsson (2022)). However, their main drawbacks are related to their
problems of treating all companies fairly.

CBA is the second main approach for solving the time slot allocation problem.
It is a very well-known methodology in the transportation field. However, the
literature applying this approach to the time slot allocation problem is
scarce. The fundamentals of CBA consist of defining all costs and benefits of
the time slot allocation procedure in economical terms and summing up in order
to know the extent to which the method designed contributes to welfare.
Because of this, the main characteristic of a CBA time slot allocation
procedure is fairness. However, the need to recover enough data from the
system (RUs and passengers) to design it, could affect the achievement of the
remaining good properties. Recently, Ait Ali, Warg, and Eliasson (2020)
proposed a CBA based method for allocation and timetable comparison. For
further reading, readers are referred to Broman, Eliasson, and Aronsson
(2022), where their authors propose a mixed method which combines
administrative procedures and CBA allocation.

Finally, WTP methods constitute the last approach to solving the time slot
allocation problem. It is a very common approach, especially in competitive
and open access markets, where multiple RUs compete between them in an auction
or bidding process. This way, the RUs are sorted according to how much money
they are willing to pay for a time slot. The main advantages of WTP methods
are usually their simplicity and manageability. However, these methods
normally suffer from a lack of transparency and above all from a lack of
fairness. There are many efforts in literature to develop fairer WTP methods
based on auctions. Some of these works are Kuo and Miller-Hooks (2015), where
a combinatorial auction was employed in ongoing allocation schemes, Talebian,
Zou, and Peivandi (2018), which proposes a negotiation approach in vertically
integrated railway systems employing game-theoretic concepts and Stojadinovic
et al. (2019), where an algorithm for iterative time slot allocation is
proposed under a scheme of hybrid auctions. Finally, another related example
is Stojadinovic, Boskovic, and Bugarinovic (2019), where their authors propose
an allocation algorithm based on auctions to make the allocation.

Reference |  | Railway System |  | Framework
---|---|---|---|---
|  | Country |  Type of transport |  | Approach |  Model |  Method | Implementation | Fairness
Broman, Eliasson, and Aronsson (2022) |  | Belgium |  Freight and passengers |  | ACP |  Rule-based |  Priorities | Theoretical | ✗
Trafikverket (2020) |  | Sweeden |  Freight and passengers |  | ACP |  Rules and negotiation-based |  Agreement and priorities | Theoretical | ✗
Ait Ali, Warg, and Eliasson (2020) |  | Sweeden |  Passengers (commuter-trains) |  | CBA |  Mathematical modelling |  Computing loss of societal benefits | Simulation | ✓
Stojadinovic, Boskovic, and Bugarinovic (2019) |  | European |  Passengers |  | WTP |  Negotiation |  Agreement and auction | Theoretical | ✗
Kuo and Miller-Hooks (2015) |  | Synthetic |  Freight |  | WTP |  Auctions Modelling |  Optimisation | Simulation | ✗
Talebian, Zou, and Peivandi (2018) |  | Synthetic |  Freight and Passengers |  | WTP |  Game-Theory: Equilibrium problem |  Optimisation | Simulation | ✓
Stojadinovic et al. (2019) |  | European |  Passengers |  | WTP |  Mathematical modelling |  Hybrid auctions | Simulation | ✗
Broman, Eliasson, and Aronsson (2022) |  | Synthetic |  Passengers |  | Hybrid |  ACP and CBA |  Welfare losses | Theoretical | ✓
This paper: priority and equity rules |  | Spanish |  Passengers |  | ACP |  Mathematical modelling |  Optimisation | Simulation | ✓

Table 2: Comparison of state-of-the-art works related to time slot allocation.

Table 2 shows a comparison of the discussed works related to time slot
allocation in liberalised passenger railway markets. Derived from this table,
it is possible to conclude the following: first, there are many works which
propose theoretically time slot allocation procedures, there is therefore a
need to implement and validate the proposed allocation methods experimentally.
Second, the references indicated in the table as fair do not always guarantee
equal treatment among all companies. This is because, when the allocation is
based on WTP, the allocation may be unfair as not all RUs have the same
resources. On the other hand, when the allocation is based on CBA, the study
of these indicators is not always possible as it requires data that is often
not available and it may favour the incumbent operator and make it more
difficult for new entrants to compete. This way, there is a gap in designing
allocation approaches that ensure equal treatment of all companies and that
are simple and easy to implement.

In this paper, we focus on the liberalized Spanish railway market as our
reference case. This market presents challenges for the application of WTP-
based approaches due to the absence of auction mechanisms employed by the IM.
Additionally, the CBA approach faces difficulties due to the requirement of
reliable socio-economic data, limiting its transparency. Instead, we adopt an
ACP-based approach.

Notably, an aspect that remains unexplored in the existing literature is the
assessment of the impact of TSA-OPEN on competitive dynamics. To address this
gap, we introduce two criteria that offer distinct treatments of the RUs. The
priority criterion reflects the strategic dominance situation of the
incumbent, while the fairness criterion advocates for equal treatment of all
RUs. Both of these developed methods are characterized by their simplicity and
practicality in terms of design and implementation. This study aims to shed
light on the implications of these criteria for competition in the railway
market.

##  3 The time slot allocation problem in open railway markets

In this section, a mathematical formalization of TSA-OPEN is provided. To
achieve this, the foundation of a liberalized railway market is initially
presented. Subsequently, the TSA-OPEN problem is formulated as a multi-
objective optimization problem. The objective of the IM is to select one of
the solutions from the Pareto front to be implemented in the system. In this
article, two criteria are proposed for choosing a solution from the Pareto
front: a priority-based rule and an equity rule. The first criterion can be
viewed as administrative and collaborative procedures based on priorities,
while the second is designed to promote equity in the treatment of the RU.

###  3.1 Liberalised Railway Markets

Figure 1 shows a scheme of a liberalised passenger railway market stated on
the basis of the Spanish case. The railway system is composed of three main
actors: a public company, the so-called IM that provides the infrastructure
and a set of private companies. The second one is RUs, that operate on the
railway network. A specific RU is denoted by $o$ and the set of RUs by means
of the set $\mathcal{O}$. Finally, the third main actor is the demand, which
is represented by passengers. In a liberalised or open railway market, an
equilibrium situation, in terms of the profit between RUs, is desirable in
order to promote competition, enhance the service frequencies and reduce
fares.

Figure 1: General scheme of a liberalised railway system and time slot
allocation problem.

The IM selects one or several corridors for liberalization. The primary
responsibility of the IM is to create a set of packages, each characterized by
its capacity, which will be auctioned to a group of RUs. Based on the various
offers received and technical considerations, the IM allocates these packages
among a subset of RUs that have submitted bids. The capacity of the package
assigned to RU $o$ is represented as $k_{o}$. This corresponds to the fraction
of the time slots that each RU can apply for in the auction process.
Therefore, this company may operate in up to $k_{o}|{\cal R}|$ time slots,
where $|{\cal R}|$ represents the total number of time slots in the corridor.
These capacity assignments restrict the requests of each RU. Capacity
allocation is the initial factor that influences whether fair competition
exists among the RUs.

A time slot, represented as $r$, is linked to a train route, including its
arrival and departure times at stations. To be more precise, it is a segment
on a space-time diagram where a train operates without conflicts.

Once the capacity assignment is carried out, the RUs are ready to make their
bids to the IM in order to obtain the operating rights in a time slot. To do
that, the RUs need to take into account the capacities that have been
previously assigned to them. The bids are modelled by a vector of binary
variables, whose length is equal to the number of time slots. This way, a bid
made by $o$ company is denoted by $y_{o}$ vector. The value of each component
of the vector $y_{o}$ is equal to $1$ when the corresponding time slot is
requested by RU $o$ and $0$ otherwise. Equation (1) shows this formalisation.

$y_{o}=[y_{or_{1}},y_{or_{2}},...,y_{o|\mathcal{R}|}].$ (1)

Note that for the binary variable $y_{o}$ to be feasible, it must satisfy the
capacity restriction modelled by Equation (2) which prevents the RU $o$ from
bidding for more time slots than it has capacity allocated to it.

$\sum_{r\in{\cal R}}y_{or}\leq k_{o}|{\cal R}|.$ (2)

After the bids placement, the IM allocates the time slots to each RU. To do
that, the IM resolves conflicts present in the request $y_{o}$ concerning
other RUs, transforming it into a conflict-free request denoted as $x_{o}$. A
conflict occurs when a time slot is requested by more than one RU. The result
of the allocation process for RU $o$ is the allocation vector $x_{o}$ shown in
Equation (3). It must be noted that the value $1$ in an element of $x_{o}$
means that the corresponding time slot has been assigned by the IM to the
company $o$. Otherwise, the value in that element will be $0$.

$x_{o}=[x_{or_{1}},x_{or_{2}},...,x_{o|\mathcal{R}|}].$ (3)

In summary, the IM receives a feasible bid $y$ of RUs, and then IM will
provide an allocation of time slot $x$ free of conflicts. Equation (4)
abstracts this procedure as a mapping ${\cal A}$.

$x=\mathcal{A}(y).$ (4)

###  3.2 TSA-OPEN modelling

One of the most important objectives of IM is to provide a fair allocation
between the RUs involved in the market. Fairness must be a key criterion if it
is intended to promote the development of competition between RUs in the
market, without excluding any of them, and thus offering passengers better
travel alternatives.

The IM acts as an arbitrator, who allocates the time slot considering the
specific objectives of each RU. The profit or payoff of RU $o$ is represented
by the function $F_{o}({x}_{o},{x}_{-o})$, where $x_{o}$ represents the
allocation to RU $o$ and $x_{-o}$ represents the allocation to the rest of the
RUs. Therefore, the IM should keep in mind the following multi-objective
problem in the definition of allocation method $\cal A$.

maximize $\displaystyle
F=[F_{1}({x}_{1},{x}_{-1}),\ldots,F_{o}({x}_{o},{x}_{-o}),\ldots,F_{|{\cal
O}|}({x}_{|{\cal O}|},{x}_{-{|{\cal O}|}})]$ (5) subject to:
$\displaystyle\sum\limits_{r^{\prime}\in{\cal R}}h^{r}_{or^{\prime}}=y_{or}$
(6) $\displaystyle\sum\limits_{r^{\prime}\in{\cal
R}}h^{r^{\prime}}_{or}=x_{or}$ (7) $\displaystyle
h^{r}_{or^{\prime}}\in\\{0,1\\}$ (8)

Constraints (6)-(8) represent the possibility of re-timing a time slot,
introducing auxiliary variables $h^{r}_{or^{\prime}}$. These variables take
the value $1$ if the time slot $r$ requested by RU $o$ is re-timed to the time
slot $r^{\prime}$.

If $\mathcal{P}$ represents the Pareto front of the problem (5)-(8), the IM
should employ an allocation criterion that satisfies the condition:

$x={\cal A}(y)\in{\cal P}.$

Otherwise, there would exist an allocation decision that would be more
beneficial for all RUs. The IM is unaware of the multi-objective problem due
to the unavailability of economic data from the RUs. To address this, a
simplified and transparent version that can be understood by all involved
parties is proposed. It is based on minimizing the discrepancies between the
time slots requested by the RUs and the allocations ultimately made by the IM.

In this new formulation, the aim of each RU $o$ is to minimise its total
deviation $D_{o}$, that is, the sum of the deviations of all the requested
time slots. Formally, it is noted by Equation (9).

$D_{o}=\sum_{r\in{\cal R}}\delta_{or},$ (9)

where $\delta_{or}$ is the deviation of the rescheduled time slot $r$
requested by operator $o$ and is computed by the Equation (10).

$\delta_{or}=\frac{1}{2}\sum_{r^{\prime}\in{\cal
R}}|y_{or}-h^{r}_{or^{\prime}}||t_{r}-t_{r^{\prime}}|,$ (10)

being $t_{r}$ the time instant of time slot $r$ and $t_{r^{\prime}}$ is the
time instant of the re-timed time slot $r^{\prime}$.

The deviation-based formulation leads to the following multi-objective
optimisation problem which will be addressed by the IM to solve TSA-OPEN
problem:

maximize $\displaystyle D=[D_{1},...,D_{o},...,D_{|\mathcal{O}|}]$ (11)
subject to: $\displaystyle(\ref{eq:const1})-(\ref{eq:const3})$

Solving TSA-OPEN problem allows to obtain a solution from the Pareto front.
The following subsections describe two different criteria or approaches to
choose Pareto optimum solutions: the first is based on a priority rule
approach and the second is based on an equity rule.

###  3.3 TSA-OPEN modelling: priority rule

The first criterion proposed in this paper to choose a Pareto optimum is the
priority rule. In this approach, the requests of the RUs are served according
to a set of priorities that determine which RU is served first, which second
and so on. Usually, priorities are related to the capacity allocated to the
RUs. This way, the RU with the highest capacity will be served first while the
RU with the lowest assigned capacity will be served last.

The priority rule means that an iterative process is carried out. In each
iteration, an allocation problem is solved for a RU according to their
priorities. This way, at the start of the resolution process, no time slot has
been allocated to any RU. Then, according to the priorities of each of the
RUs, the one with the highest priority will be selected and its requested time
slot will be allocated, as none have been allocated previously. Later, the
next RU in order of priority will be selected and the allocation procedure
will be repeated. However, in this case, it is possible that conflicts may
occur and that the second RU has requested time slots that have already been
allocated to the first RU, so in this case the IM shall re-plan those slots
trying to minimise the deviation from the requested time slot. This iterative
process will be carried out for all the RUs. As the allocation is carried out
for a new RUs, an increasing number of conflicts will arise. This is due to
the additional slots allocated to previously served RUs, being necessary to
re-plan the time slot allocated to each one.

Let’s assume that the RUs have been prioritized in the order
$o_{1},\ldots,o_{|\cal O|}$, and suppose that all companies
$\\{o1,\ldots.o^{\prime}-1\\}$ have been analyzed, calculating their
respective allocation variables $x_{or}$. Then, for the time slot allocation
for company $o^{\prime}$, the IM will minimize its deviation:

Minimize $\displaystyle D_{o^{\prime}}$ (12) Subject to:
$\displaystyle\sum_{r^{\prime}\in{\cal
R}}h^{r}_{o^{\prime}r^{\prime}}=y_{o^{\prime}r},\ \ \ \forall r\in{\cal R}$
(13) $\displaystyle\sum_{r^{\prime}\in{\cal
R}}h^{r^{\prime}}_{o^{\prime}r}=x_{o^{\prime}r},\ \ \ \forall r\in{\cal R}$
(14) $\displaystyle\delta_{o^{\prime}r}=\frac{1}{2}\sum_{r^{\prime}\in{\cal
R}}|y_{o^{\prime}r}-h^{r}_{o^{\prime}r^{\prime}}||t_{r}-t_{r^{\prime}}|,\ \ \
\forall r\in{\cal R}$ (15) $\displaystyle D_{o^{\prime}}=\sum_{r\in{\cal
R}}\delta_{o^{\prime}r}$ (16) $\displaystyle
x_{o^{\prime}r}+\sum_{o\in\\{o1,\cdots,o^{\prime}-1\\}}x_{or}\leq 1,\ \ \
\forall r\in{\cal R}$ (17) $\displaystyle
h^{r}_{o^{\prime}r^{\prime}}\in\\{0,1\\},\ \ \ \forall r,r^{\prime}\in{\cal
R}$ (18)

where the constraints (13)-(14) models replanning time slots, the constraints
(15)-(16) define the computation of the deviation for the RU $o^{\prime}$, and
the constraint (17) prevents a time slot from being allocated to more than one
RU. Note that the variables $x_{or}$ in Equation (17) have been computed in
prior iterations and, in this formulation, they act as parameters. Finally,
constraint (18) shows the binary nature of replanning variables.

Priority rule modelling is an ACP time slot allocation approach which,
although simple and practical, represents the strategic dominance of the
incumbent RU in the market. In the next section, an equity rule approach is
proposed in order to ensure a fair allocation to all the RUs in the system.

###  3.4 TSA-OPEN modelling: equity rule

In contrast to the method introduced earlier, where the RUs are treated
unequally, we introduce a method to ensure a fairer allocation. The proposed
criterion, named equity rule, tries to balance the deviations suffered between
RUs. In this case, the optimization model aims to minimise the total sum of
deviations across all RUs within the market. However, it also enforces a
constraint to limit the maximum difference that can be observed between the
deviations experienced by the RUs.

The equity criterion is related to the capacity assigned to each RU. In this
paper, the proposed approach imposes that the total displacement for the time
slot of the RU $o$ must be proportional to the size of its operating capacity,
which is noted by $D_{o}=k_{o}\Delta$. However, due to the discrete nature of
this constraint, it is not always possible to achieve exact equality in
maintaining this proportionality. To address this limitation, a tolerance
parameter $\varepsilon$ is introduced to ensure its satisfaction.

Given the time slot requests $y$ by the RUs, we calculate the total number of
requested time slot as
$n_{y}=\sum_{o\in\mathcal{O}}\sum_{r\in\mathcal{R}}y_{or}$, and the IM
formulates the TSA-OPEN problem under the equity rule as (19):

Minimize $\displaystyle\sum_{o\in\cal O}D_{o}$ (19) Subject to:
$\displaystyle\sum_{r^{\prime}\in{\cal R}}h^{r}_{or^{\prime}}=y_{or},\hskip
14.22636pt\forall o\in{\cal O},\forall r\in{\cal R}$ (20)
$\displaystyle\sum_{r^{\prime}\in{\cal R}}h^{r^{\prime}}_{or}=x_{or},\hskip
14.22636pt\forall o\in{\cal O},\forall r\in{\cal R}$ (21)
$\displaystyle\delta_{or}=\frac{1}{2}\sum_{r^{\prime}\in{\cal
R}}|y_{or}-h^{r}_{or^{\prime}}||t_{r}-t_{r^{\prime}}|,\hskip 14.22636pt\forall
o\in{\cal O},\forall r\in{\cal R}$ (22) $\displaystyle D_{o}=\sum_{r\in{\cal
R}}\delta_{or},\hskip 14.22636pt\forall o\in{\cal O}$ (23)
$\displaystyle\sum_{o\in{\cal O}}x_{or}\leq 1,\hskip 14.22636pt\forall
r\in{\cal R}$ (24) $\displaystyle\Delta=\frac{1}{n_{y}}\sum_{o\in{\cal
O}}\sum_{r\in{\cal R}}\delta_{or}$ (25)
$\displaystyle\Delta-\varepsilon\leq\frac{1}{k_{o}\cdot
n_{y}}D_{o}\leq\Delta+\varepsilon,\hskip 14.22636pt\forall o\in{\cal O}$ (26)
$\displaystyle h^{r}_{or^{\prime}}\in\\{0,1\\}\hskip 14.22636pt\forall
r,r^{\prime}\in{\cal R},\forall o\in{\cal O}$ (27)

where the constraints (20)-(23) and (27) are similarly formulated as for the
priority rule, but they apply to all RUs collectively. Constraint (24) ensure
a time slot is only allocated to one RU. The constraint (25) computes the
average deviation for the time slot and it is denoted by $\Delta$ and the
constraint (26) imposes that the average deviation for all RUs is equal to
$\Delta$ plus or minus an error $\varepsilon$.

##  4 Assessing TSA-OPEN in liberalized markets: an equilibrium game

The purpose of this article is twofold. First, it seeks to establish precise
guidelines for ${\cal A}$ to ensure transparent and equitable allocation of
time slots. Since the conceptual method ${\cal A}$ for assigning time slots
affects the equilibrium of the open railway system, the second objective is to
evaluate the impact of these guidelines on competition. To accomplish this,
tools must be developed for assessing the rules $\cal A$. In this section, we
introduce an equilibrium game approach as a model for the open railway market,
in which the TSA-OPEN $x=\mathcal{A}(y)$ is a component of this equilibrium
model.

The equilibrium problem at hand can be stated as a game in which the players
are RUs and the strategies are the time slot requests $y$. The RUs need to
determine which strategies to employ and with what probability to request them
from the IM in order to maximise their payoff functions. For example, let’s
suppose a RU which has two request options: $y_{1}$ and $y_{2}$. This RU is
interested in knowing the probability values $p_{1}$ and $p_{2}$, such as
$p_{1}+p_{2}=1$, where $p_{1}\geq 0$ and $p_{2}\geq 0$, for playing these
requests to maximize its profit.

The payoff function $F$ corresponds to the economic revenue of the RU which is
computed as the difference between the revenues from ticket sales and the
costs of operating the time slot together with the costs of acquisition and
depreciation of rolling stock.

The revenue obtained from ticket sales for the time slot $r$ can be computed
by $b_{r}=\sum_{\omega\in{\cal W}}g_{r\omega}z_{r\omega},$ where $g_{r\omega}$
is the demand of the time slot $r$ in the origin-destination pair $\omega$ and
$z_{r\omega}$ is the ticket price of for the origin-destination trip $\omega$
at time slot $r$. The revenue from ticket sales for RU $o$ is computed as

$J_{o}(x_{o},x_{-o})=\sum_{r\in{\cal R}}x_{or}b_{r}.$ (28)

Note that the expression (28) is a simplification of the problem, in which it
is assumed the number of passengers attended by a service depends only on the
allocated time slot.

Concerning cost for RU $o$, it consists of two components. The first part is
associated with the operative costs and the second with investment costs to
provide the established services. The operational costs $f_{or}$ take into
account the network access variable cost fixed by IM and the staff and
operational costs by ticketing, advertisement, passenger attendance, drivers,
and so on. Regarding investment costs, RU $o$ has to assume the cost of
leasing rolling material to offer the service ($C_{o}$). Thus, the investment
costs will depend on the number of units and the typology necessary to deploy
the service. It is assumed all trains have the same typology and the rolling
stock costs depend on the minimum number of trains needed to operate all
accepted time slots. In investment costs, the maintenance costs are also
included as well as the depreciation costs of the rolling stock. It is
considered that the fixed cost to network access $c_{a}$ has already been
incurred by RUs. It does not affect the choice of time slot but is included to
adjust the balance sheet of RU. The minimum number of trains needed to operate
the service network (time slot) is denoted by $n_{T}(x_{o})$. This introduces
the investment needs of the operator and investment costs. Finally, the payoff
function for a RU $o$, given the time slot allocated to it ($x_{o}$) and the
time slot allocated to the rest of RUs ($x_{-o}$) is defined as

$F_{o}(x_{o},x_{-o})=J_{o}(x_{o},x_{-o})-\sum_{r\in{\cal
R}_{o}}f_{or}x_{or}-C_{o}n_{T}(x_{o})-c_{a}.$ (29)

Let’s consider $\mathbf{p}_{o}=(\cdots,p_{y_{o}},\cdots)$ as a probability
distribution over the set of strategies that the RU $o$ can employ
($y_{o}\in{Y}_{o}$). Then, for a game strategy
$y=(y_{o_{1}}\cdots,y_{o_{|{\cal
O}|}})\in{Y}={Y}_{1}\times\cdots\times{Y}_{|{O}|}$, its probability of being
applied is given by: $p_{y}=\prod_{s=1}^{|{\cal O}|}p_{y_{o_{s}}},$ and
therefore, the expected benefit for RU $o$ is:

$\displaystyle u_{o}(\mathbf{p}_{o},\mathbf{p}_{-o})$ $\displaystyle=$
$\displaystyle\sum_{y\in{Y}}p_{y}F_{o}(x_{o},x_{-o}),$ (30) $\displaystyle x$
$\displaystyle=$ $\displaystyle{\cal A}(y).$ (31)

In an equilibrium scenario, no RU can unilaterally enhance their expected
economic outcomes. We will now mathematically formulate this situation:

######  Definition 4.1 (Nash equilibrium bid).

A strategy profile $\mathbf{p}^{*}_{{\mathbf{y}}}$ for the bid is a Nash
equilibrium if for all $o\in{\cal O}$, for all $\mathbf{p}_{{\mathbf{y}}_{o}}$
and for all $y_{o}\in Y_{o}$

$u_{o}(\mathbf{p}_{{\mathbf{y}}_{o}},\mathbf{p}^{*}_{{\mathbf{y}}_{-o}})\leq
u_{o}\left(\mathbf{p}^{*}_{{\mathbf{y}}}\right).$ (32)

It is worth noting that the allocation rule $\cal A$ impacts the profit
$u_{o}(\mathbf{p})=\sum_{y\in Y}p_{y}F_{o}\left(\,{\mathcal{A}}(y)\,\right)$
and, consequently, alters the equilibrium situation. This is the effect we aim
to analyze.

Furthermore, it should be noted that calculating the equilibrium situation
requires determining $x={\cal A}(y)\hbox{ for all }y\in Y$. The proposed
models are based on integer linear programming111Note that the absolute value
of a magnitude appearing in constraints (15) and (22) can be modelled using
linear programming through the following trick:
$\displaystyle|x|=x^{+}+x^{-}$ $\displaystyle x=x^{+}-x^{-}$ $\displaystyle
x^{+}\geq 0,x^{-}\geq 0$ . While commercial solvers efficiently handle these
models, the set $Y$ presents a vast number of alternatives, necessitating the
resolution of a substantial number of these problems. Consequently, to
streamline the incorporation of $\cal A$ into an equilibrium computation
method, it is advisable to employ heuristic algorithms for its calculation. In
the following two subsections, we introduce such algorithms for each of the
rules.

###  4.1 Priority rule

In order to solve TSA-OPEN problem considering the priority rule modelled in
section 3, a heuristic algorithm is proposed. In this method, the set of
priorities that define the order in which the RUs will be attended is
considered to be given. For example, priorities may be directly related to the
capacities of the RUs in such a way that the more capacity a RU has, the more
priority it has. Thus, the IM starts to allocate time slots for the company
which has the highest priority and so on. The allocation is done assuming that
the previous time slot has already been allocated and re-planning the
conflicting time slot to the nearest available one. To illustrate this
solution procedure, Algorithm 1 shows the pseudo-code of a heuristic algorithm
for TSA-OPEN problem based on the priority rule.

1:$\mathcal{O},\mathcal{R},y_{1},y_{2},...,y_{|\mathcal{O}|}$

2:$x$

3:function TSA-OPEN using priority rule

4: – Priorities vector with the ordered indexes of the RUs to be served –

5: Priorities $=[o_{1},o_{2},o_{3},...,o_{|}\mathcal{O}|]$

6: – Solve an allocation problem for each RU–

7: for $i=1:|\mathcal{O}|$ do

8: – Select RU by priority –

9: $o^{\prime}=\mathcal{O}[Priorities[i]]$

10: for $r$ requested time slot by o do

11: if $r$ is available then

12: – Direct allocation of free time slot –

13: $x_{o^{\prime}r}=y_{o^{\prime}r}$

14: else

15: – Re-timing of conflicting time slot –

16: $h^{r^{\prime}}_{o^{\prime}r}=1$ where $r^{\prime}$ is the closet
available time slot of the requested $r$.

17: – Allocate the re-timing time slot –

18: $x_{o^{\prime}r^{\prime}}=1$

19: end if

20: end for

21: end for

22:end function

Algorithm 1 Pseudocode for solving heuristically TSA-OPEN problem using a
priority rule

This algorithms departs from a vector of priorities defined in line $3$. It
contains a priority value for each RU which will determine the order in which
the requests of each one will be processed with respect to the other RUs.
Then, in line $5$, a for loop is used to select, in the first place, the RU
with the highest priority and whose requests will be handled. Once the RU to
be served is determined, a nested for loop in line $8$ goes through the
requests made by the RU, so that if the requested time slot is free, it is
directly allocated to that RU (line $11$) and if it has already been
allocated, the nearest available time slot is assigned (line $16$).

###  4.2 Equity rule

The heuristic method for solving TSA-OPEN problem using the equity rule
modelled in section 3 is shown below. The objective of the TSA-OPEN problem is
to minimize the overall deviation of the time slots requested by all the RUs
in the system while simultaneously ensuring that the discrepancies between RUs
do not differ excessively. The equity criterion is established on the basis of
the assigned capacity to each RU. This way, the IM will allocate a time slot
to the RU which, at a given time, has received the least number of time slots
in relation to its capacity. The requests of the RUs are iteratively
processed. In each iteration $t$, the relationship between the allocated time
slots and the total capacity of a given RU (the value $\phi^{t}$ ) is
recalculated in order to determine which RU’s request is to be served in that
iteration. This process continues until all the requests made by the companies
are fulfilled. The calculation of $\phi_{o}^{t}$ values is shown in Equation
(33).

$\phi^{t}_{o}=\frac{\sum_{r\in\mathcal{R}}x^{t}_{or}}{k_{o}},$ (33)

where $x^{t}_{or}$ represents the value of the variable $x$ at iteration $t$.
After computing the $\phi_{o}^{t}$ values for each RU $o$ then IM process the
first request from the RU with the lowest value of $\phi_{o}^{t}$. If the time
slot requested is free, it is directly allocated to the RU. If not, it is re-
timed. Algorithm 2 shows the pseudocode of the heuristic algorithm to solve
time slot allocation based on equity rule criterion.

1:$\mathcal{O},\mathcal{R},k,y_{1},y_{2},...,y_{|\mathcal{O}|}$

2:$x$

3:function TSA-OPEN using equity rule

4: – Initialise $\phi$ values to infinity –

5: $\phi=[]$

6: for $o=1:|\mathcal{O}|$ do

7: $\phi[o]=+\infty$

8: end for

9: – Check RUs requests –

10: $y=[y_{1},y_{2},...,y_{|\mathcal{O}|}]$

11: – Computes the total number of requests received –

12: $n_{y}=\sum_{o\in{\cal O}}\sum_{r\in{\cal R}}y_{or}$

13: – Iterative request processing –

14: for $t=1:n_{y}$ do

15: – Recalculate $\phi_{o}$ values –

16: $\phi_{o}=\frac{\sum_{r\in\mathcal{R}}x_{or}}{k_{o}}$

17: $o^{\prime}=\underset{o\in{\cal O^{*}}}{\hbox{Arg min}}\\{\phi_{o}\\}$;
where ${\cal O}^{*}$ is the set of RU’s with time slots that need to be
allocated

18: Let $r$ be the next time slot of RU $o^{\prime}$ to be processed.

19: if $r$ request can be satisfied then

20: $x_{o^{\prime}r}=1$

21: else

22: $h^{r^{\prime}}_{o^{\prime}r}=1$ where $r^{\prime}$ is the closet
available time slot of the requested $r$.

23: – Allocate the re-timing time slot –

24: $x_{o^{\prime}r^{\prime}}=1$

25: end if

26: end for

27:end function

Algorithm 2 Pseudocode for solving heuristically TSA-OPEN problem using an
equity rule

In this algorithm, lines $3-6$ defines a $\phi$ vector which contains the
initial $\phi$ values for all the RUs in the market. Initially, these values
are equals to $\infty$. Then, lines $8-10$ allow to obtain the total number of
requests issued to the IM by all the RUs. A for loop in line $12$ goes through
all the requests, processing them one by one. In each iteration, $\phi$ values
are computed for each RU. It will allow to determine the RU whose request is
to be addressed in each iteration. Once the company to be served is
identified, if the time slot requested is free it will be directly allocated
(line $18$), if not, the closest available time slot will be assigned (line
$22$).

##  5 Numerical Experiments

This section presents computational experiments using the proposed TSA-OPEN
approach, applying both the priority and the equity rule criteria. The results
provided in this section will allow us to answer the following three Research
Questions (RQs):

  * RQ1.

How does the use of the two rules proposed in the IM affect the equilibrium
situation?

  * RQ2.

How does the use of heuristic methods instead of exact methods impact the
equilibrium situation?

  * RQ3.

Are the conclusions still valid if we had used the exact methods to calculate
the equilibrium situation?

For these purposes, Section 5.1 describes the considered Spanish railway
corridor between Madrid and Barcelona. In section 5.2, the impact of the two
allocation rules is analysed with respect to the profit of each RU (RQ1).
Later, section 5.3 shows the performance of heuristic algorithms against the
exact models (RQ2). Finally, section 5.4 discusses if the conclusions obtained
will still be valid if the experiments were carried out using the exact
algorithms (RQ3).

###  5.1 Experimental settings: the Spanish railway market

The experimental scenario corresponds to the Spanish passenger railway market.
Specifically, the Madrid-Barcelona high-speed corridor has been considered.
For this purpose, two origin-destination (O-D) pairs have been established:
$\omega_{1}=(\text{Madrid},\text{Barcelona})$ and
$\omega_{2}=(\text{Barcelona},\text{Madrid})$. The demand varies throughout
the day according to the distribution given in Almodóvar and García-Ródenas
(2013), which has been considered for the two pairs $\omega_{1}$ and
$\omega_{2}$. Figure 2 shows the number of passengers travelling in each time
slot according to that distribution. We consider that if a company operates in
a specific time slot $r$, it captures the entire demand assigned to that time
slot.222Given the levels of demand, this is a reasonable assumption.

Figure 2: Demand distribution

In the Spanish railway market, there are three RUs: RENFE (the incumbent
operator), OUIGO and IRYO, and referred as to $RU_{1}$, $RU_{2}$ and $RU_{3}$
and they are denoted respectively as $o_{1}$, $o_{2}$, and $o_{3}$. Regarding
planning time, it is considered one day of operation, starting at 06:15 and
ending at 23:15, with a time slot every half hour. Therefore, a total of $35$
time slots in 30-minute intervals are available for each of the origin-
destination pairs. In order to study the impact of the allocation policy
adopted by the IM on the competition between RUs, the following assumptions
are made. First, all operators have allocated the same capacity, denoted as
$k_{o}=25\%$, allowing them a maximum capacity of operating 8 time slot per
direction. This is to consider all RUs equally and the results obtained are
solely the consequence of the actions of IM. Second, all RUs employ identical
rolling stock and ticket prices. Otherwise, the results obtained could be the
result of the policy price or rolling stock difference, rather than the result
of the IM’s policy.

A comprehensive cost framework has been adopted for this analysis. Thus, the
ticket price has been set to $70$ euros. The same rolling stock unit can
operate several time slots if the time constraints allow it. The model
calculates the minimum number of rolling stock units that a RU needs to
operate all allocated time slots. Finally, a daily amortisation cost of 11,490
euros has been included for each unit of rolling stock that the RU needs to
have available to serve its time slots. This cost reflects the depreciation
and maintenance expenses associated with the rolling stock units. Furthermore,
the direct operational cost of each time slot amounts to $2,950$ euros per
slot. This cost factor encompasses various components, such as power
consumption and personnel expenses. By considering these cost factors in our
analysis, it is intended to provide an economic evaluation that accounts for
both the revenue generation potential through ticket sales and the necessary
expenditure required to operate the services efficiently. Table 3 summarises
the parameters employed in the computational experiments.

The heuristic algorithms have been coded using the MATLAB programming language
and run on a Windows 10 at 4 GHz AMD FX-8370 eight-core processor with 32 GB
of RAM. Regarding exact algorithms, CPLEX has been used to solve TSA-OPEN
problem. The equilibrium model shown in (32) has been solved in two stages:
(1) the computation of the set of feasible strategies has been carried out
according to García Rodenas et al. (2023), (2) the equilibrium problem is
solved in this set by using the algorithm described and implemented in
Chatterjee (2009).

EXPERIMENTAL SETTINGS
---
Name | Notation | Formulation | Value
O-D pairs | $\mathcal{W}$ | $\mathcal{W}=\\{\omega_{1},\omega_{2}\\}$ | $\mathcal{W}=\\{(\text{Madrid},\text{Barcelona}),(\text{Barcelona},\text{Madrid})\\}$
RUs | $\mathcal{O}$ | $\mathcal{O}=\\{o_{1},o_{2},o_{3}\\}$ | $\mathcal{O}=\\{RENFE,OUIGO,IRYO\\}$
Time slot | $\mathcal{R}$ | $\mathcal{R}=\\{r_{1},r_{2},r_{3},..,r_{35}\\}$ | $\mathcal{R}=\\{06:15,06:45,07:15,...,23:30\\}$
Capacities | $k$ | $k=[k_{1},k_{2},k_{3}]$ | $k=[25\%,25\%,25\%]$
Ticket price | $z_{rw}$ |  | 70€
Daily amortization cost | $C_{o}$ |  | 11490€
Cost operational slot | $f_{or}$ |  | 2950€

Table 3: Experimental settings set in the numerical experiments

###  5.2 RQ1. How does the use of the two rules proposed in the IM affect the
equilibrium situation?

In this subsection, the equilibrium problem defined in the equation (32)
considering both priority and equity rules has been solved. The equilibrium
situation is composed by a set of strategies for each RU. A pure strategy is
defined as a single time slot request (bid). Furthermore, a combined strategy
is a set of pure strategies which are played by the RUs with a probability
value. Table 4 shows the obtained equilibrium state for both rules using the
heuristic algorithms designed. The column one is associated to the kind of
rule, the column two represents the probability to use a combined strategy.
Then, columns three and four details the RU and the corresponding origin-
destination pair. Finally, column $y_{o}$ shows the request of each RU while
column $x_{o}$ represents the time slot finally allocated by the IM.

According to Table 4, the solution of the TSA-OPEN problem with priority rule
consists of a combined strategy for $RU_{2}$ (composed by two pure strategies,
which are played with probabilities $p_{y1}=0.5628$ and $p_{y2}=0.4372$) and
one pure strategy for $RU_{1}$ and $RU_{3}$ which are employed with
probability one.

Similarly, Table 4 also shows the equilibrium situation when solving the TSA-
OPEN problem considering the equity rule. The equilibrium situation in this
case also leads to a combined strategy composed of two pure strategies for
$RU_{2}$. However, while the probabilities in the case of the priority rule
for each of the simple strategies were similar, in this case, the probability
of $RU_{2}$ playing the first simple strategy is $p_{y1}=0.0415$ while the
probability of playing the second simple strategy is $p_{y2}=0.9585$.

Rule Probability ($p_{y}$) RU $\omega$ $y_{o}$ $x_{o}$ Priority Rule
$p_{y1}=0.5628$ RU 1 $\omega_{1}$ [7:45, 8:15, 8:45, 9:45, 14:45, 15:15,
18:15, 19:15] [7:45, 8:15, 8:45, 9:45, 14:45, 15:15, 18:15, 19:15]
$\omega_{2}$ [7:15, 7:45, 8:45, 13:45, 15:45, 18:15, 18:45, 20:15] [7:15,
7:45, 8:45, 13:45, 15:45, 18:15, 18:45, 20:15] RU 2 $\omega_{1}$ [7:45, 8:15,
9:45, 14:45, 15:15, 18:15, 19:15, 20:45] [7:15, 9:15, 10:15, 14:15, 15:45,
18:45, 19:45, 20:45] $\omega_{2}$ [7:15, 7:45, 8:45, 14:45, 17:45, 18:15,
18:45, 20:15] [6:45, 8:15, 9:15, 14:45, 17:45, 19:15, 19:45, 20:45] RU 3
$\omega_{1}$ [6:45, 7:45, 13:15, 14:45, 15:15, 18:15, 19:15, 20:15] [6:15,
6:45, 13:15, 13:45, 16:15, 17:45, 20:15, 21:15] $\omega_{2}$ [7:15, 7:45,
13:15, 13:45, 15:45, 18:45, 20:15, 20:45] [6:15, 9:45, 13:15, 14:15, 16:15,
17:15, 21:15, 21:45] $p_{y2}=0.4372$ RU 1 $\omega_{1}$ [7:45, 8:15, 8:45,
9:45, 14:45, 15:15, 18:15, 19:15] [7:45, 8:15, 8:45, 9:45, 14:45, 15:15,
18:15, 19:15] $\omega_{2}$ [7:15, 7:45, 8:45, 13:45, 15:45, 18:15, 18:45,
20:15] [7:15, 7:45, 8:45, 13:45, 15:45, 18:15, 18:45, 20:15] RU 2 $\omega_{1}$
[7:45, 8:45, 9:45, 14:45, 15:15, 16:45, 18:15, 19:15] [7:15, 9:15, 10:15,
14:15, 15:45, 16:45, 18:45, 19:45] $\omega_{2}$ [7:15, 7:45, 13:15, 13:45,
15:45, 19:45, 20:15, 20:45] [6:45, 8:15, 13:15, 14:15, 16:15, 19:45, 20:45,
21:15 ] RU 3 $\omega_{1}$ [6:45, 7:45, 13:15, 14:45, 15:15, 18:15, 19:15,
20:15 ] [6:15, 6:45, 13:15, 13:45, 16:15, 17:45, 20:15, 20:45] $\omega_{2}$
[7:15, 7:45, 13:15, 13:45, 15:45, 18:45, 20:15, 20:45] [6:15, 9:15, 12:45,
14:45, 15:15, 19:15, 21:45, 22:15] Equity Rule $p_{y1}=0.0415$ RU 1
$\omega_{1}$ [7:45, 8:15, 13:15, 14:45, 15:15, 18:15, 19:15, 19:45] [8:15,
9:15, 12:45, 14:15, 14:45, 19:15, 20:45, 21:45] $\omega_{2}$ [7:15, 7:45,
8:45, 13:45, 15:45, 16:45, 18:15, 18:45] [7:45, 8:45, 9:45, 13:15, 16:45,
17:15, 19:45, 20:15] RU 2 $\omega_{1}$ [6:45, 7:45, 8:15, 15:15, 18:15, 19:15,
19:45, 20:45] [7:15, 8:45, 9:45, 15:45, 18:45, 19:45, 20:15, 22:15]
$\omega_{2}$ [7:15, 7:45, 8:45, 13:45, 15:45, 18:15, 18:45, 20:15] [8:15,
9:15, 10:15, 14:45, 16:15, 18:45, 19:15, 20:45] RU 3 $\omega_{1}$ [8:15, 9:45,
13:15, 14:45, 16:45, 18:15, 19:15, 19:45] [7:45, 10:15, 13:45, 15:15, 17:15,
17:45, 18:15, 21:15] $\omega_{2}$ [7:15, 7:45, 13:45, 15:15, 15:45, 18:15,
18:45, 19:45] [6:45, 7:15, 14:15, 15:15, 15:45, 17:45, 18:15, 21:15]
$p_{y2}=0.9585$ RU 1 $\omega_{1}$ [7:45, 8:15, 13:15, 14:45, 15:15, 18:15,
19:15, 19:45] [8:15, 9:15, 12:45, 15:45, 16:15, 19:15, 20:45, 21:45]
$\omega_{2}$ [7:15, 7:45, 8:45, 13:45, 15:45, 16:45, 18:15, 18:45] [7:45,
8:45, 9:45, 13:15, 16:45, 17:15, 19:15, 20:15] RU 2 $\omega_{1}$ [6:45, 8:15,
9:15, 13:15, 15:15, 16:45, 18:15, 19:15] [7:15, 8:45, 9:45, 14:15, 14:45,
17:15, 19:45, 20:15] $\omega_{2}$ [7:15, 8:45, 13:15, 15:45, 16:45, 18:15,
20:15, 20:45] [8:15, 9:15, 13:45, 16:15, 17:45, 19:45, 20:45, 21:15] RU 3
$\omega_{1}$ [8:15, 9:45, 13:15, 14:45, 16:45, 18:15, 19:15, 19:45] [7:45,
10:15, 13:45, 15:15, 17:45, 18:15, 18:45, 21:15] $\omega_{2}$ [7:15, 7:45,
13:45, 15:15, 15:45, 18:15, 18:45, 19:45] [6:45, 7:15, 14:15, 15:15, 15:45,
18:15, 18:45, 21:45]

Table 4: Equilibrium solution using the heuristic algorithms and considering
the priority and equity rules

In order to answer RQ1, a two-fold analysis is going to be carried out. It
will take into account the time slot allocation and the economic revenue
associated with each of the RUs. This way, the impact of the two rules in the
equilibrium situation will be assessed.

On the one hand, the allocation results will be discussed. Figures 3 and 4
show the time slot allocated to the different RUs and the demand captured in
each one. Concretely, the abscissa axis represents each of the time slots
while the ordinate axis represents the number of passengers travelling in each
time slot, according to the optimal strategies of the RUs 333It is worth
noting that the optimal strategy for RUs consists of employing two simple
strategies with different probabilities. Here, only one is represented for
simplicity.. Finally, the colour of the bar represents the RU to which the
time slot has been assigned and on which the passengers are travelling. In
addition, each sub-figure displays this information for an origin-destination
pair.

Concerning the allocation using priority rule, Figures 3(a) y 3(b), the time
slots with the highest demand are allocated to RU 1, i.e. the one that in the
priority rule is served first. Similarly, the time slots with the lowest
demand are assigned by the algorithm to the RU with the lowest priority.
Graphically, both figures show how the IM’s actions cause the players’ actions
to be dominated, i.e. $RU_{1}$ imposes its criterion on $RU_{2}$ and $RU_{3}$
and, in turn, $RU_{2}$ imposes its criterion on $RU_{3}$. The priority rule
ensures a preference for the RU 1 that can lead to a market imbalance and
ultimately to a monopoly situation.

(a) $\omega_{1}$

(b) $\omega_{2}$

Figure 3: Time slot allocation under Priority Rule: Heuristic solution

Concerning the allocation using equity rule, Figures 4(a) y 4(b), the main
difference with respect to the obtained results from the priority rule is that
the allocation of the time slots capturing the highest demand are distributed
equally among all RUs. Thus, it can be seen that for the two origin-
destination pairs, the RUs in the market manage to obtain the operating rights
of slots that capture high demand, just as they also receive the rights of
other slots where the number of passengers is not as large.

(a) $\omega_{1}$

(b) $\omega_{2}$

Figure 4: Time slot allocation under Equity Rule: Heuristic solution

On the other hand, the economic revenue of the RUs is going to be analysed in
order to evaluate the equilibrium situation provided by the solution of TSA-
OPEN using priority and equity rule. Table 5 shows, for each of the RUs in the
market, the number of time slots that have been assigned in each origin-
destination pair. In this case, as the capacity of each RU is 25%, each of
them receives a total of $16$ time slots, eight in each origin-destination
pair. In addition, the table also shows the total number of passengers served
by the RUs in the assigned time slots in each pair, as well as the total
number of passengers served. The fact that decimal numbers appear in these
data is because the results in the table are aggregated over the combined
strategy, so the total number of passengers is the number of passengers served
in each simple strategy multiplied by the probability of playing each simple
strategy. Finally, the table also shows the number of rolling stock units that
each RU needs to serve the assigned services as well as the total benefit
obtained calculated through the equation (29). These values are also computed
over the combined strategy, so decimal numbers may appear. These values are
obtained after applying an algorithm to compute the minimum number of trains
which are required to meet planned schedules.

$\cal A$ RUs $\mathbf{OD}_{1}$ Pass. $|{\cal R}_{1}|$ $\mathbf{OD}_{2}$ Pass.
$|{\cal R}_{2}|$ Total Passengers Rolling Stocks Revenue Priority rule $o_{1}$
3657 8 3521 8 7178 6 330320 $o_{2}$ 2779.5 8 2725.9 8 5505.4 5.6 218262
$o_{3}$ 1977.4 8 2010.5 8 3987.9 4.9 119945 Equity rule $o_{1}$ 2433.3 8 2908
8 5341.4 5 213244.8 $o_{2}$ 3171 8 2460.9 8 5631.9 5.1 232628.4 $o_{3}$ 2550.5
8 2889.5 8 5440 5 220146.8

Table 5: Economical results of solving TSA-OPEN problem using heuristic
algorithms

According to the results of Table 5, it is possible to check and contrast the
results provided by Figures 3 and 4. In the first row, which corresponds to
the results of the priority rule, there is an imbalance in the market in
favour of the $RU_{1}$, since it captures many more passengers than the rest
of the RUs and, therefore, has much greater economic benefits than the rest.
Therefore, the impact of priority rule over the equilibrium situation is
negative, since it leads to a situation of dominance of the RU 1 which
produces an imbalance in the market, causing some RUs to go out of business
and, ultimately, leading to a monopoly situation in the market.

Concerning the results of the equity rule which are shown in the second row of
Table 5, it is possible to observe a completely different market situation. In
this case, the number of passengers captured by the RUs does not differ as
significantly as in the previous case, which is also reflected in the number
of rolling stock units that each RU needs (the same in this case) and in the
economic benefits of all of them, which is much more balanced. Therefore, it
is possible to verify that the equity rule impacts the equilibrium situation
positively, guaranteeing that all RUs involved obtain similar benefits, which
enables competition within the market.

###  5.3 RQ2. How does the use of heuristic methods instead of exact methods
impact the equilibrium situation?

With the purpose of studying the performance of the two heuristic algorithms
proposed to solve TSA-OPEN problem using priority and equity rule, exact
algorithms have also been used to solve both problems. Concretely, TSA-OPEN
problem was solved using CPLEX. The results obtained by CPLEX in solving the
problem using the priority and the equity rule are shown below.

On the one hand, Figure 5 shows the allocation results provided by heuristic
and exact algorithms when TSA-OPEN problem with priority rule is solved. In
this figure, an image matrix composed of three rows and two columns can be
observed. Each row corresponds to a different RU in the market, while each
column corresponds to a different origin-destination pair. Thus, Figures 5(a)
and 5(b) correspond to $RU_{1}$ in both directions when applying the priority
rule. For each figure in the matrix, a so-called ring diagram shows the
requested and allocated slots, where the outer ring with the thickest line
represents the requested slots by the RUs, the middle ring shows the
allocation provided by the heuristic algorithm while the inner ring with the
thinnest line corresponds to the allocation obtained by the exact algorithm.

(a) $RU_{1}:\omega_{1}$

(b) $RU_{1}:\omega_{2}$

(c) $RU_{2}:\omega_{1}$

(d) $RU_{2}:\omega_{2}$

(e) $RU_{3}:\omega_{1}$

(f) $RU_{3}:\omega_{2}$

Figure 5: TSA-OPEN solution under priority rule. Each row represents a RU in
the market and each column an origin-destination pair. The graphs compare the
requested time slot (outer ring) to those one allocated by using heuristic
(middle ring) and exact (inner ring) algorithms.

Analysing Figure 5 it is possible to contrast that, for $RU_{1}$, the
allocation provided for both heuristic and exact algorithms is the same in the
two origin-destination pairs. Regarding $RU_{2}$, the allocation for the first
pair obtained by both algorithms is also the same. However, the allocation
provided for the second pair $\omega_{2}$ is slightly different in both
algorithms, allocating six of the eight time slots equally by both algorithms.
Finally, something very similar happens with $RU_{3}$, where the allocation
for $\omega_{1}$ origin-destination pair is the same using both exact and
heuristic algorithms, but in the case of the second pair, only five of the
eight time slots are allocated equally by both algorithms. In this test
scenario in which all companies have the same capacity, the priorities were
assigned to $RU_{1}$, $RU_{2}$ and $RU_{3}$ respectively (note that if
priorities were assigned according to the capacity of the RUs, the incumbent
operator will be favoured). As can be seen in this figure, the coincidence of
both algorithms in the solution is an indicator of the quality of the proposed
heuristic algorithm.

On the other hand, Figure 6 shows the results of heuristic and exact
algorithms when TSA-OPEN is solved by means of equity rule. Here, the results
are quite different. However, these results are reasonable since, under this
approach, the time slots are proportionally distributed according to the RUs’s
capacities. In this case, the solutions of exact and heuristic approaches are
different. Thus, it is possible to check that, for $RU_{1}$, only four and
three time slots respectively are equally assigned by both algorithms for the
two origin-destinations pairs. For $RU_{2}$ in the $\omega_{1}$ pair, two time
slots are equally assigned by heuristic and exact algorithms while in
$\omega_{2}$, there are three time slots. Finally, regarding $RU_{3}$, only
one time slot is assigned by both heuristic and exact algorithms for the first
pair, while in the second origin-destination pair, three time slots are
equally assigned by both algorithms.

(a) $RU_{1}:\omega_{1}$

(b) $RU_{1}:\omega_{2}$

(c) $RU_{2}:\omega_{1}$

(d) $RU_{2}:\omega_{2}$

(e) $RU_{3}:\omega_{1}$

(f) $RU_{3}:\omega_{2}$

Figure 6: TSA-OPEN solution under equity rule. Each row represents a RU in the
market and each column is an origin-destination pair. The graphs compare the
requested time slot (outer ring) to those allocated by using heuristic (middle
ring) and exact (inner ring) algorithms.

In order to summarize the results of Figures 5 and 6, Table 6 shows a study of
the deviation of each of the RUs. The deviation for a RU is the sum of the
time differences between the time slot it requested and the time slot it was
finally allocated. Thus, the smaller the deviation, the more the allocation of
time slot was in line with the RU’s request, while the larger the deviation,
the greater the discrepancy between the time slot requested and those finally
allocated to the RU. This way, Table 6 shows this comparison. It is possible
to check the performance of heuristic and exact algorithms is similar when the
priority rule is employed, since the deviation for $RU_{1}$ and $RU_{2}$ is
the same, while the difference in the deviation of $RU_{3}$ is only half an
hour, it means, only one time slot deviation. Thus, the total deviation using
the priority rule is around twenty hours. However, in the case of equity rule,
the differences are greater. The heuristic approach exhibits an average
deviation of approximately ten hours, whereas the exact approach yields half
the deviations for all the RUs.

$\mathcal{A}$ | Algorithm | $D_{o1}$ | $D_{o2}$ | $D_{o3}$ | Total Deviation
---|---|---|---|---|---
Priority Rule | Heuristic | 0 | 6h 30m | 13h 30m | 20h
Exact | 0 | 6h 30m | 13h | 19h 30m
Equity Rule | Heuristic | 15h 30m | 12h | 8h 30m | 36h
Exact | 6h 30m | 5h | 5h | 16h 30m
Table 6: Deviation analysis of TSA-OPEN solutions

The results provided by Table 6 seem to indicate that, when solving the TSA-
OPEN problem with priority rule, it is indifferent to use heuristic and exact
algorithms. However, when attempting to address the TSA-OPEN problem using the
equity rule, exact algorithms ensure an optimal allocation of time slots with
respect to the disparity between the requests made by the different carriers.
To validate this observation from the table and considering that temporal
disparity differs from the economic outcomes each of the RUs would achieve, we
will reevaluate the equilibrium strategy using exact methods. The outcomes are
presented in Table 7.

From Table 7, it can be seen that in terms of the allocation results with
priority rule, the economic benefits obtained are very similar (slightly
higher) than those obtained by the heuristic algorithms, both in terms of the
number of passengers travelling on each company and the benefit obtained by
each of them. These results, therefore, are in line with those obtained in
Table 6, which showed how the discrepancy obtained for each of the companies
by the heuristic and exact algorithms was similar, although slightly better
than that obtained by the exact algorithms.

On the other hand, the results obtained when the exact algorithms are used to
solve the TSA-OPEN problem with the equity rule are striking. In this
particular case, both the number of passengers and the economic benefit
obtained by each of the RUs differ significantly from those obtained by the
heuristic algorithms. These economic differences are due to the discrepancy
obtained by the heuristic algorithms and the exact algorithms (see Table 6).
However, the results obtained by the exact algorithms, despite guaranteeing a
smaller discrepancy between the RUs’ requests and the time slots finally
allocated, maintain a significant imbalance in terms of the number of
passengers travelling on each RU and the profits of each RU, showing a non-
equilibrium solution with respect to the exact algorithms.

Despite this negative outcome regarding the quality of the heuristic using the
equity rule, there is a significant highlight: when addressing the TSA-OPEN
problem with the equity rule, it becomes evident that the RUs can learn how
the IM operates and devise a strategy that leads to an equilibrium ensuring
equal or similar profits for all of them. Therefore, if the IM sets a rule
that is transparent and does not lead to a dominant strategy of one over the
others, the RUs will come to play a strategy that allows them to reach an
equilibrium situation and perceive similar profits. In other words, what is
important is not only that the discrepancy between requested and allocated
time slots is small, but that all RUs in the market are treated equally by the
IM.

$\cal A$ TOCs $\mathbf{OD}_{1}$ $|{\cal R}_{1}|$ $\mathbf{OD}_{2}$ $|{\cal
R}_{2}|$ Passengers Rolling Stocks Revenue Priority rule $o_{1}$ 3657 8 3521 8
7178 6 330320 $o_{2}$ 2779.5 8 2780 8 5559.5 5 228517.7 $o_{3}$ 2021.2 8
2071.2 8 4092.4 5.1 124374.7 Equity rule $o_{1}$ 3134.8 8 3178.2 8 6313 5
281260.6 $o_{2}$ 2649.9 8 2411.8 8 5061.7 5 193192.5 $o_{3}$ 2614.7 8 2816.2 8
5430.9 5 219512.1

Table 7: Economical results of solving TSA-OPEN problem using exact algorithms

###  5.4 RQ3. Are the conclusions still valid if we had used the exact methods
to calculate the equilibrium situation?

To answer this question, it is necessary to start from the results obtained in
the previous section. As indicated in Table 7 compared to Table 5, the results
obtained by the heuristic and exact algorithms for the resolution of the TSA-
OPEN with priority rule are similar in terms of discrepancy, number of
passengers captured and economic benefits obtained by the RUs. In both cases,
it can be observed that the priority rule imposes a dominance of the RU 1 over
the rest in the market, which jeopardises the situation of liberalisation and
competition. Therefore, in this case, the conclusions are the same whether
exact or heuristic algorithms are used to solve the TSA-OPEN problem.

However, when addressing the TSA-OPEN problem with an equity rule, the
conclusions differ based on whether heuristic or exact algorithms are employed
for problem-solving. As demonstrated in the previous section, the use of exact
algorithms ensures an optimal alignment between the time slots requested by
the RUs and those ultimately assigned. However, this criterion has not been
employed as the criterion $x={\cal A}(y)$ in the equilibrium calculation (see
Equations (30)-(31)), and as a result, it does not lead to a balance in the
benefits received by the companies. To obtain a definitive answer for R3 in
the case of the equity rule, equilibrium calculation using exact methods for
the allocation is required. The challenge lies in the necessity to solve a
large number of linear programming problems, which is the motivation behind
utilizing heuristic methods.

One can postulate the response to R3 for the equity rule using exact methods
based on the insights gained from heuristic approaches. In alignment with the
results presented in the previous section, where all companies achieve
comparable revenues despite a substantial divergence between the requested and
allocated time slots, it becomes apparent that these companies familiarize
themselves with the operations of the IM and formulate strategies to attain an
equilibrium in which they all receive equal benefits.

The conjecture to assert that the RUs will reach an equitable equilibrium,
i.e. indistinguishable companies achieve the same revenue, is as follows: If
the method utilized, denoted as ${\cal A}(y)$, were universally known among
all RUs, and furthermore, if ${\cal A}$ possessed the property that swapping
the requests $y_{o}$ of two RUs results in the IM reciprocally swapping the
time slot assignments, then the equilibrium would indeed be equitable, and the
role of the IM would be neutral in this context.

##  6 Conclusions and further works

The European passenger railway markets are progressing steadily towards the
creation of a common and unified railway area, where multiple RUs compete with
each other for operating rights in time slots, which means a greater supply
for passengers and an opportunity to improve rail services. This evolution,
which is marked by the competitive aspect of the liberalised rail markets, is
leading to changes in railway planning, operation and management, which
require new models and algorithms for their efficient resolution.

This paper is a novel research work about the modelling of open passenger
railway systems. The first contribution is the modelling of TSA-OPEN problem,
which is mathematically formulated in order to capture the conflicting
objectives of the RUs in a liberalised passenger railway market like the
Spanish one.

Efficiently solving the TSA-OPEN problem is a pivotal concern for fostering
competition in the passenger railway market. In this study, we demonstrate
that any criterion ${\cal A}$ employed by the IM must select points from the
Pareto front. We propose two solution approaches with these characteristics:
the priority rule and the equity rule. Both criteria are straightforward to
implement using linear programming and entail low computational costs.
Additionally, we have introduced heuristic versions of these criteria in this
study, driven by the necessity to compute the equilibrium state to study these
rules, although these heuristics are not required for practical
implementation.

Additionally, this paper presents a case study designed to evaluate the
performance of the two proposed approaches. The study focuses on the Madrid-
Barcelona corridor within the Spanish railway market. The objective of this
experiment is to investigate the function of the IM in time slot allocation
with the aim of promoting competition between the RUs and preventing the
emergence of a monopolistic situation. Heuristic and exact algorithms have
been applied to solve TSA-OPEN problem using both priority and equity rules.

The comparison between heuristic and exact algorithms has led to the
conclusion that both approaches obtain similar solutions when TSA-OPEN problem
is solved using the priority rule. However, this approach tends to benefit the
operator with the highest priority, exhibiting relevant differences between
the revenues of the different RUs.

Furthermore, we have found that the heuristic equity rule achieves a fair
equilibrium, wherein indistinguishable players obtain identical revenue. This
demonstrates that the use of this rule by the IM assigns it a neutral role in
the market. Additionally, we have observed that the heuristic rule yields
results that deviate significantly from the optimal solutions obtained through
the exact method.

The discussion of question R3 leads us to speculate that the exact equity rule
also attains a fair equilibrium. However, the fact that the exact method
produces deviations closer to the initial requests of the various companies
makes it more practical. It allows the RUs to anticipate the outcomes of their
actions and reach the equilibrium state more quickly.

The dynamics in a liberalised railway passenger system are complex and require
novel models to capture. For future works, it is intended to extend this model
in order to represent the complete dynamics in a liberalised railway market.
It will lead to a more complex game-theoretic model which represents
competition in liberalised passenger railway markets, taking into account
optimal strategies, demand modelling and equilibrium prices.

## Acknowledgements

This work was supported by grant PID2020-112967GB-C32 funded by
MCIN/AEI/10.13039/501100011033 and by ERDF A way of making Europe.

## References

  * Ait-Ali (2020) Ait-Ali, Abderrahman. 2020. “Methods for Capacity Allocation in Deregulated Railway Markets.” PhD diss.
  * Ait Ali and Eliasson (2019) Ait Ali, Abderrahman, and Jonas Eliasson. 2019. _Railway capacity allocation: a survey of market organizations, allocation processes and track access charges_. Technical Report 2019:1.
  * Ait Ali, Warg, and Eliasson (2020) Ait Ali, Abderrahman, Jennifer Warg, and Jonas Eliasson. 2020. “Pricing commercial train path requests based on societal costs.” _Transportation Research Part A: Policy and Practice_ 132: 452–464. https://doi.org/https://doi.org/10.1016/j.tra.2019.12.005, https://www.sciencedirect.com/science/article/pii/S0965856419303829.
  * Almodóvar and García-Ródenas (2013) Almodóvar, M, and R García-Ródenas. 2013. “On-line reschedule optimization for passenger railways in case of emergencies.” _Computers & Operations Research_ 40 (3): 725–736. https://doi.org/https://doi.org/10.1016/j.cor.2011.01.013, https://www.sciencedirect.com/science/article/pii/S0305054811000256.
  * Broman and Eliasson (2019) Broman, Emanuel, and Jonas Eliasson. 2019. “Welfare effects of open access competition on railway markets.” _Transportation Research Part A: Policy and Practice_ 129: 72–91. https://doi.org/https://doi.org/10.1016/j.tra.2019.07.005, https://www.sciencedirect.com/science/article/pii/S0965856418305615.
  * Broman, Eliasson, and Aronsson (2022) Broman, Emanuel, Jonas Eliasson, and Martin Aronsson. 2022. “Efficient capacity allocation on deregulated railway markets.” _Journal of Rail Transport Planning & Management_ 21: 100294. https://doi.org/https://doi.org/10.1016/j.jrtpm.2021.100294, https://www.sciencedirect.com/science/article/pii/S2210970621000597.
  * Cacchiani, Caprara, and Toth (2008) Cacchiani, Valentina, Alberto Caprara, and Paolo Toth. 2008. “A column generation approach to train timetabling on a corridor.” _4OR_ 6 (2): 125–142. https://doi.org/10.1007/s10288-007-0037-5, https://doi.org/10.1007/s10288-007-0037-5.
  * Cai, Goh, and Mees (1998) Cai, X, C J Goh, and ALISTAIR I Mees. 1998. “Greedy heuristics for rapid scheduling of trains on a single track.” _IIE Transactions_ 30 (5): 481–493. https://doi.org/10.1023/A:1007551424010, https://doi.org/10.1023/A:1007551424010.
  * Cantos-Sánchez, Pastor Monsálvez, and Serrano-Martínez (2021) Cantos-Sánchez, Pedro, José Manuel Pastor Monsálvez, and Lorenzo Serrano-Martínez. 2021. “Vertical and Horizontal Separation in the European Railway Sector and its Effects on Productivity.” _International Encyclopedia of Transportation: Volume 1-7_ 1 (2): 503–507. https://doi.org/10.1016/B978-0-08-102671-7.10092-2, http://www.jstor.org/stable/40600020.
  * Caprara, Fischetti, and Toth (2002) Caprara, Alberto, Matteo Fischetti, and Paolo Toth. 2002. “Modeling and Solving the Train Timetabling Problem.” _Operations Research_ 50: 851–861. https://doi.org/10.1287/opre.50.5.851.362.
  * Caprara et al. (2007) Caprara, Alberto, Leo Kroon, Michele Monaci, Marc Peeters, and Paolo Toth. 2007\. “Chapter 3 Passenger Railway Optimization.” In _Transportation_ , edited by Cynthia Barnhart, Gilbert B T Handbooks in Operations Research Laporte, and Management Science, Vol. 14, 129–187. Elsevier. https://www.sciencedirect.com/science/article/pii/S0927050706140037.
  * Caprara et al. (2006) Caprara, Alberto, Michele Monaci, Paolo Toth, and Pier Luigi Guida. 2006. “A Lagrangian heuristic algorithm for a real-world train timetabling problem.” _Discrete Applied Mathematics_ 154 (5): 738–753. https://doi.org/https://doi.org/10.1016/j.dam.2005.05.026, https://www.sciencedirect.com/science/article/pii/S0166218X05003045.
  * Carey and Lockwood (1995) Carey, Malachy, and David Lockwood. 1995. “A Model, Algorithms and Strategy for Train Pathing.” _Journal of the Operational Research Society_ 46 (8): 988–1005. https://doi.org/10.1057/jors.1995.136, https://doi.org/10.1057/jors.1995.136.
  * Chatterjee (2009) Chatterjee, Bapi. 2009. “An optimization formulation to compute Nash equilibrium in finite games.” _Proceedings of International Conference on Methods and Models in Computer Science, ICM2CS09_ 1–5. https://doi.org/10.1109/icm2cs.2009.5397970.
  * García Rodenas et al. (2023) García Rodenas, Ricardo, Nikola Besinovic, María Luz López-García, Julio Alberto López-Gómez, and José Ángel Martín-Baos. 2023. _Game-Theoretic Modeling of Competition in the Liberalized Passenger Railway Market_. Technical Report.
  * Higgins, Kozan, and Ferreira (1996) Higgins, A, E Kozan, and L Ferreira. 1996. “Optimal scheduling of trains on a single line track.” _Transportation Research Part B: Methodological_ 30 (2): 147–161. https://doi.org/https://doi.org/10.1016/0191-2615(95)00022-4, https://www.sciencedirect.com/science/article/pii/0191261595000224.
  * Higgins, Kozan, and Ferreira (1997) Higgins, A, E Kozan, and L Ferreira. 1997. “Heuristic Techniques for Single Line Train Scheduling.” _Journal of Heuristics_ 3 (1): 43–62. https://doi.org/10.1023/A:1009672832658, https://doi.org/10.1023/A:1009672832658.
  * Kuo and Miller-Hooks (2015) Kuo, April, and Elise Miller-Hooks. 2015. “Combinatorial auctions of railway track capacity in vertically separated freight transport markets.” _Journal of Rail Transport Planning & Management_ 5 (1): 1–11. https://doi.org/https://doi.org/10.1016/j.jrtpm.2014.12.001, https://www.sciencedirect.com/science/article/pii/S2210970614000675.
  * Li et al. (2019) Li, Dewei, Tianyu Zhang, Xinlei Dong, Yonghao Yin, and Jinming Cao. 2019. “Trade-off between efficiency and fairness in timetabling on a single urban rail transit line under time-dependent demand condition.” _Transportmetrica B: Transport Dynamics_ 7 (1): 1203–1231. https://doi.org/10.1080/21680566.2019.1589598, https://doi.org/10.1080/21680566.2019.1589598.
  * Lusby et al. (2011) Lusby, Richard M, Jesper Larsen, Matthias Ehrgott, and David Ryan. 2011. “Railway track allocation: models and methods.” _OR Spectrum_ 33 (4): 843–883. https://doi.org/10.1007/s00291-009-0189-0, https://doi.org/10.1007/s00291-009-0189-0.
  * Nash (2008) Nash, Chris. 2008. “Passenger railway reform in the last 20 years – European experience reconsidered.” _Research in Transportation Economics_ 22 (1): 61–70. https://doi.org/https://doi.org/10.1016/j.retrec.2008.05.020, https://www.sciencedirect.com/science/article/pii/S0739885908000152.
  * Ristić, Stojadinović, and Trifunović (2022) Ristić, Bojan, Nikola Stojadinović, and Dejan Trifunović. 2022\. “Conditions for effective on-track competition in the European passenger railway market: A yardstick for regulations.” _Transport Policy_ 119: 1–15. https://doi.org/https://doi.org/10.1016/j.tranpol.2022.02.006, https://www.sciencedirect.com/science/article/pii/S0967070X22000452.
  * Schlechte (2012) Schlechte, Thomas. 2012. “Railway Track Allocation: Models and Algorithms.” PhD diss., Saarbrücken, Germany.
  * Stojadinovic, Boskovic, and Bugarinovic (2019) Stojadinovic, Nikola, Branislav Boskovic, and Mirjana Bugarinovic. 2019. “Bridging the gap between infrastructure capacity allocation and market-oriented railway: An algorithmic approach.” _Transport_ 34: 1–14. https://doi.org/10.3846/transport.2019.11035.
  * Stojadinovic et al. (2019) Stojadinovic, Nikola, Branislav Boskovic, Dejan Trifunovic, and Sladana Jankovic. 2019. “Train path congestion management: Using hybrid auctions for decentralized railway capacity allocation.” _Transportation Research Part A: Policy and Practice_ 129: 123–139. https://doi.org/https://doi.org/10.1016/j.tra.2019.08.013.
  * Talebian, Zou, and Peivandi (2018) Talebian, Ahmadreza, Bo Zou, and Ahmad Peivandi. 2018. “Capacity allocation in vertically integrated rail systems: A bargaining approach.” _Transportation Research Part B: Methodological_ 107: 167–191. https://doi.org/https://doi.org/10.1016/j.trb.2017.12.001, https://www.sciencedirect.com/science/article/pii/S0191261517301042.
  * Tomeš et al. (2016) Tomeš, Zdeněk, Martin Kvizda, Monika Jandová, and Václav Rederer. 2016\. “Open access passenger rail competition in the Czech Republic.” _Transport Policy_ 47: 203–211. https://doi.org/https://doi.org/10.1016/j.tranpol.2016.02.003, https://www.sciencedirect.com/science/article/pii/S0967070X16300397.
  * Trafikverket (2020) Trafikverket. 2020. _Network Statment 2020_. Technical Report. Swedish Transport Administration.
  * Vigren (2017) Vigren, Andreas. 2017. “Competition in Swedish passenger railway: Entry in an open access market and its effect on prices.” _Economics of Transportation_ 11-12: 49–59. https://doi.org/https://doi.org/10.1016/j.ecotra.2017.10.005, https://www.sciencedirect.com/science/article/pii/S2212012217300977.
  * Yang et al. (2023) Yang, Ruixia, Baoming Han, Qi Zhang, Zhenyu Han, and Yuxuan Long. 2023. “Integrated optimization of train route plan and timetable with dynamic demand for the urban rail transit line.” _Transportmetrica B: Transport Dynamics_ 11 (1): 93–126. https://doi.org/10.1080/21680566.2022.2040064, https://doi.org/10.1080/21680566.2022.2040064.