A game theoretic model for re-optimizing a railway timetable

Abstract

In the Nineties of the last century the European Commission decided to open the railway market to competition, allowing different railway companies to operate on the same network. Under this framework Infrastructure Managers have to allocate capacity in order to define the timetable, dealing with possible slot conflicts between competing Transport Operators.

An efficient train scheduling requires collecting a lot of information from the Transport Operators, but it may not be in their interests to reveal their private information. Therefore, it may be useful for real-world applications to design methods that provide incentives to Transport Operators for cooperating with the aim of increasing their utility; moreover, this may result in an improvement of the efficiency even for the Infrastructure Managers, so they also have incentives for favouring the cooperation.

In this paper we propose a game theoretical model in which the agents (Transport Operators) exchange information on their needs and are compensated by a possible increasing of their utility. This approach represents the situation as a coalition formation problem. In particular, we refer to the C-Solution proposed by Gerber (Rev Econ Design 5:149-175, 1), which is applied to some examples, each with different features. This model requires that information is revealed to a small number of competitors. This is rather important in a market currently still characterized by operator reluctance to an indiscriminate diffusion of information. Furthermore, the low dimension of the problem allows having a low computational complexity.

Eur. Transp. Res. Rev. (2014) 6:113125 DOI 10.1007/s12544-013-0116-y

ORIGINAL PAPER

A game theoretic model for re-optimizing a railway timetable

Vito Fragnelli & Simona Sanguineti

Received: 11 July 2011 /Accepted: 1 August 2013 /Published online: 30 August 2013 # The Author(s) 2013. This article is published with open access at SpringerLink.com

AbstractThe Setting In the Nineties of the last century the European Commission decided to open the railway market to competition, allowing different railway companies to operate on the same network. Under this framework Infrastructure Managers have to allocate capacity in order to define the timetable, dealing with possible slot conflicts between competing Transport Operators. The Problem An efficient train scheduling requires collecting a lot of information from the Transport Operators, but it may not be in their interests to reveal their private information. Therefore, it may be useful for real-world applications to design methods that provide incentives to Transport Operators for cooperating with the aim of increasing their utility; moreover, this may result in an improvement of the efficiency even for the Infrastructure Managers, so they also have incentives for favouring the cooperation.

The Proposal In this paper we propose a game theoretical model in which the agents (Transport Operators) exchange information on their needs and are compensated by a possible increasing of their utility. This approach represents the situation as a coalition formation problem. In particular, we refer to the C-Solution proposed by Gerber (Rev Econ Design 5:149 175, 1), which is applied to some examples, each with different features. This model requires that information is revealed to a small number of competitors. This is rather important in a market currently still characterized by operator reluctance to an indiscriminate diffusion of information. Furthermore, the low dimension of the problem allows having a low computational complexity.

Keywords Coalition formation . NTU-game . Railway scheduling . Slot allocation

1 Introduction

The typical framework in the European railway industry in the past century was the presence of monopolistic state-owned companies in all countries. These integrated companies managed both infrastructure and service. As this type of organization revealed a lot of inefficiencies (deficits, low quality, etc.), in the 1990s the European Commission decided to open the market to competition. The reform process began with the directive 440/91, followed by different packages of directives,1 First of all, the Commission asked for separating the management of infrastructure from the management of the service. In this way the infrastructure becomes available for several operators through competition in the market or competition for the market. In such a competitive view, the definition of the railway timetable and the resolution of possible conflicts between operators become crucial tasks.

In particular, the European Commission emphasizes the concept of non-discriminatory access to the railway market and asks for a higher level of transparency of the sector. Railway undertakings are invited to reveal more information about market conditions. Unfortunately at the current state-ofart of the research, there not exists a method to allocate capacity able to satisfy the condition of non-discriminatory access. The literature identifies different methodologies for capacity allocation that we briefly set out afterwards and that draw on auction theory or mathematical programming.

1 We refer to directives EEC 18-19/95, EU 12-13-14/2001 and EU 49-50-51/2004.

V. Fragnelli (*)

Dipartimento di Scienze e Tecnologie Avanzate, Viale Teresa Michel 11, 15121 Alessandria, Italye-mail: [email protected]

S. SanguinetiDipartimento di Economia e Metodi Quantitativi, Via Vivaldi 5, 16126 Genova, Italye-mail: [email protected]

114 Eur. Transp. Res. Rev. (2014) 6:113125

The increase of competition implies the need to use scientific methods of decision in order to optimize the allocation of available resources, particularly the scheduling of trains. Other elements that increase the complexity of the problem are the large dimension of the network and the interconnection with the timetables of boundary countries, due to international trains. For these reasons the problem was approached, at least theoretically, in many different ways, from the classical manual to the most sophisticated software.

The manual approach starts, in general, from the existing timetable and tries to improve it, or just to update it, taking into account the requirements for insertions and/or eliminations of trains. This approach depends on a suitably skilled and experienced timetable expert, who has knowledge about how well the old timetables worked.

Referring to the sophisticated software approaches it is possible to consider an optimal timetable as the solution of mathematical programming problems whose data consist of the topology of the network (lines and stations), the technical characteristics of the tracks and of the trains, the demand for transport and the utility functions of the trains operators (TOs). It is possible to assume as unknown the leaving time and the travel time of each train and, consequently, to state as constraints the headway times between trains and some requirements arising from the technical characteristics and from the quality of services to the users; under these conditions it is possible to search for the maximum of the global utilities (see [2]). Due to the dimension and computational complexity of the problem, these approaches may produce a timetable that is an approximate optimum; moreover the objective function is based on the global utility of the TOs, so that there is the possibility to improve the schedule looking at the utility of each agent.

In this paper we propose a new approach, rooted in cooperative game theory; more precisely, we use a cooperative game without transferable utility (NTU-game), that considers the role of each TO. The idea is to introduce small changes in the current schedule, after which a small set of TOs is better off, without affecting the utility of the others. Even if a large number of non cooperative models for transportation problems were developed in the past (see [3]), to the best of our knowledge there do not exist applications of NTU-games to railway slot allocation that deal both questions of coalition formation and payoff distribution. Our idea is to start from a railway timetable proposed by an Infrastructure Manager (IM), whose efficiency may be improved, involving a small number of agents, operating trains on the same line in a short period of time, that agree on exchanging more information on their preferences, moving from a non cooperative setting to a cooperative one. In this way we exploit the inefficiencies in the current timetable due to limited information exchange, which in its turn depends on the competitive environment which the TOs operate in. Our aim is twofold. First, we want

to obtain a new timetable that allows improving the utility of the TOs that decide to cooperate. Second, we are interested in getting also a numerical solution of the problem, in the sense that the rearrangement of the scheduling may require that some agents accept to be worst off from the point of view of the utility associated to their final scheduling but they are compensated with a monetary amount from those agents who are better off, after a larger increasing of their utility associated to their final scheduling (see Example 1). This implies that we have the necessity to compute not only the scheduling, but also a fair compensation system for providing incentives to the agreement. In order to reach this aim, we refer to the C-Solution proposed by Gerber [1] for three reasons. First, it does not necessarily favour the formation of the grand coalition, i.e. an agreement involving all the cooperating TOs; second, it takes into account the possibility that the agents have in other coalitions; third, it offers also the possibility to obtain the amount of compensations, if allowed. Next, we consider a different setting in which the agents look only for improving their utilities via a better scheduling, without compensations among them. In this scenario, we refer to a generalization of the bargaining approach, introduced by Nash [4] for two agents (see Examples 2, 3, 4).

The paper is organized as follows. In the next section we summarize some papers that deals with the problem of determining an efficient scheduling of the trains; in Section 3 we recall some basic definitions of game theory; Section 4 is devoted to the C-Solution by Gerber [1], the main instrument we need in our approach; in Section 5 we formalize our problem; Section 6 presents some simple examples of possible situations and related solutions; Section 7 concludes.

2 Previous approaches

This section highlights some papers that inspired our research. First, we remark that there exists a wide literature on capacity allocation issues in railway. For example, several models proposed in the literature aim to solving the scheduling problem focusing on a certain objective function under predefined constraints to optimality, such as periodic time windows constraints [5], or introduce stochastic disturbances [6]; Fischetti et al. [7] focused on robustness improvement of a given solution; Ho et al. [8], after remarking that multi-objective optimization approaches often end with feasible solutions because of the constraints on computation time, propose a method for designing the scheduling based on Particle Swarm Optimization that considers the negotiations rounds among the IM and the TOs. Another interesting field is that of simulation tools, possibly combined with other instruments and approaches. In this case timetables are generated by time-stepping simulation using train motion differential equations. SIMONE, OpenTrack and RailSys are some of the commercial

Eur. Transp. Res. Rev. (2014) 6:113125 115

simulation programs available in the railway industry (see [10, 11] and [12]). Wong and Ho [9] consider a competitive setting, where the IM and the TOs negotiate on the access fees and service requests, accounting learning techniques that allow for improving the resulting scheduling after several rounds; the model is solved via simulation. Simulation is used also by Meijer [13] that analyzes the Dutch railways situation from the point of view of gaming. For going deeper, we address to An assessment of Railway Capacity [14]; a recent survey on the state-of-art of railway timetable and traffic management is [15].

Now, we briefly recall some interesting works based on auction theory and mathematical programming. In Binary Conflict Ascending Price mechanism (BICAP) (see [16]) agents bid to have access to railroad and they are free to increase their bids in order to compete for the available slots. The mechanism works like a set of simultaneous ascending auctions, one for each train to be operated, and bids are submitted in real time. Three elements are involved: a set of feasible outcome allocations, a message space through which agents interact each other and with the allocation authority, and an outcome rule setting how these messages could determine a unique outcome starting from the feasible set of allocations. The allocation process maximizes the total value of bids from trains with feasibility constraints. Each agent could submit increasing bids for trains in a continuous time auction. The mechanism checks if the new bid is higher for a given train than the current bid. The potential allocation of a certain period of time is defined as the set of bids that cause no conflict and maximizes the sum of all feasible allocations. Only the highest bids are kept as information by the mechanism. A new allocation is computed and the auction ends when there are no further increases in the bids after a certain period of time. The experiments carried out by the authors confirm that a decentralized mechanism can solve some of the technical aspects of the rail scheduling problem and yield to an efficient allocation of tracks. Moreover, the design consistency appears strong.

A different approach was proposed by Nilsson [17], addressing two strongly related challenges: The optimization problem, related to the mathematical aspects, and the incentive problem, referred to the need to make operators reveal their value of track access, i.e. with the need to acquire information about the operators value-of-access. Firstly, the interested operators have to register their preferred trains departures and arrivals. They also include alternatives to the preferred path and submit also a set of bids, one for each alternative path. Each bid indicates the operators willingness-to-pay for the preferred departure-arrival path as well as for the alternative paths. Secondly, the IM identifies the value-maximizing allocation, i.e. the timetable which generates the largest possible aggregate value of bids. For each train path a set of prices is calculated, given the demand

schedules and bids which have been submitted. These are the prices the operators have to pay in order to run their trains. Thirdly, the information acquired is sent back to operators for further considerations. If there are no conflicts for path between operators, all get their preferred choices and the process can be terminated. If not, one or more operators have not been allocated exactly what they asked for. Finally, these last operators have the opportunity to reconsider their initial train path specifications. The whole process is repeated as long as anyone wants to make changes in bids or departure specifications. Another important point is that the IM could address problem that are indirectly related to timetabling. The result of the allocation process may also provide other relevant information like that about scarcity of capacity. Using the suggested techniques, scarcity will manifest itself in high track user charges, signalling that users value of access is high. The process may therefore create relevant information for the investment planning process useful to decide if track supply should be expanded or not.

The paper by Caprara et al. [18] introduces a model based on a graph. They consider a single line. Each station along the line is represented by a set of 2880 nodes: 1440 indicating the arrival time and 1440 indicating the departure time (to the nearest minute). The oriented arcs are of two sorts: those connecting a departure node of one station to an arrival node of the next station (representing the train travelling between the stations) and those connecting an arrival node to a departure node of the same station (representing the stopping time of the train in the station). A path, i.e. a sequence of arcs from a departure station to an arrival station represents the travel of a train from its origin to its destination. Suitable constraints avoid undesired results. The solution provides a set of paths that maximize the total utility of the trains, on the basis of the difference from their optimal departure time from the originating station (shift, that can be positive if the train leaves later or negative if the train leaves earlier) and of the delay in the travel time (stretch, that is supposed to be only non negative, as the trains ask for the minimal travel time). Further modifications of the basic model allow taking into account multiple tracks in the stations or simple networks, like a line with two branches Caprara et al. [19].

Recently, Borndrfer et al. [20] used an iterative combinatorial auction that takes place in a sequel of rounds. Each round consists of two stages. In the first stage, each operator submits simultaneously a set of bids that, jointly with the set of standing bids, represents the set of live bids. In the second stage the optimization machinery is applied on the set of live bids and computes the set of bids accepted in the round, which becomes the new set of standing bids. During the optimization process the auctioneer must determine a conflict-free slot schedule that maximizes the network proceeds. They denote optimal allocation problem (OPTRA) the winner determination problem that is a so called multi-commodity flow

116 Eur. Transp. Res. Rev. (2014) 6:113125

problem with additional constraints solved with integer programming techniques. The auction ends when for a fixed number of rounds, the total proceed does not change.

Finally, we mention the approaches by Lalive and Schmutzler [21] that analyze which impact the competition may have on the reduction of the costs and the improvement of the scheduling, measured via the frequencies of the trains represented by the ratio between train kilometres per year and the length of a line, and by Kuo and Miller-Hooks [22] that consider a specific form of cooperation that leads the different TOs to pool their trains.

3 Recall of game theory

In this section we introduce some classical definitions of game theory that will be used through the paper. We start by defining a cooperative game without transferable utility.

Definition 1 A cooperative game without transferable utility (NTU-game) is a couple G = (N, V), where N={1, , n} is the player set and V is the characteristic function that maps each coalition SN in the set of its feasible payoffs, with the conditions:

& V(S)RS;

& V(S) is closed and non-empty; & V S

V S

R

S

i.e. the starting payoff or the minimum that players can guarantee if they do not reach an agreement.

Many solutions were proposed for a bargaining problem; here we recall three classical ones that we use in this paper:

& the Nash solution [4]:

N F; d

argmax

iN xidi

xF; xd

& the Kalai-Smorodinsky solution [23]:

K F; d

argmax

x1d1

a1d1

( )

where ai=max{xi R | x F, xd}, i N. & the Egalitarian solution [24]:

E F; d

argmax x1d1 xndn

xndn

andn

xF; xd

xF; xd

n o

The Nash solution corresponds to the Pareto efficient point that maximizes the product of the increasing of utility for the agents.

The Kalai-Smorodinsky solution produces the Pareto efficient point for which the increasing of utility for the agents is proportional to their maximal increasing.

The Egalitarian solution determines the Pareto efficient point that assigns to each agent the same increasing of utility.

The third condition is called comprehensiveness, and represents the possibility of the players to dispose any amount from their payoffs (R

S denotes the non negative orthant

of RS).

Definition 2 A cooperative game with transferable utility (TU-game) is a couple G=(N, v), where N={1, , n} is the player set and v is the characteristic function that associates to each coalition SN a real value representing its worth, with v()=0.v(S) can be interpreted as the maximum total payoff that the players in S may obtain independently from the other agents.

Given a TU-game (N, v) it is always possible to define the associated NTU-game (N, V) where V(S)={(xi)iS RS, s.t.

iS xi v(S)}.

Another important element in this paper is the bargaining problem, introduced by Nash [4] with two players and generalized as follows.

Definition 3 A bargaining problem is a couple (F, d), where FRn is the feasibility set, i.e. the closed, convex, bounded and non-empty set of payoffs which players can agree on after bargaining and d=(d1, , dn), d F is the disagreement point,

4 C-Solution

In this section, we shortly recall the coalition formation method of Gerber [1], addressing to the original paper for more details. The method is based on the dynamic solution of a suitable abstract game [25]. A nice characteristic of this process is that the final numerical solution, the C-Solution, specifies not only which coalitions form, but assigns a payoff to each player, starting from its power in the other coalitions (outside opportunities).

4.1 Abstract Games

We recall some basic concepts about abstract games, which are the simplest idea of a game.

& An abstract game is a couple (X, dom) where X is an arbitrary set and dom X X is a binary relation on X, called domination; given x, y X, x is accessible from y, or

Eur. Transp. Res. Rev. (2014) 6:113125 117

& A reduced game with respect to the coalition S, or V S, is the game:

V S T

V T

if T S

y RNT

yx, if x = y or if there exist z1, , zm X s.t.

x=z1 dom z2 dom dom zm-1 dom zm = y& An elementary dynamic solution is a set SX that satisfies the following conditions:

1. x S, y X \ Sy is not accessible from x (elements not in S are not accessible from elements of S).

2. x, y Syx and xy (two elements in S are accessible one another).

& The dynamic solution is the set P that is union of all elementary dynamic solutions.

& For dynamic solutions the following theorem (Theorem 1 in [1]) holds: If X is finite, then P is non-empty.

4.2 Assumptions

In the following we suppose (cf. [1]) that:

& An NTU-game is a set of pure bargaining games

H S={(F S, d S)}, SN, where F S is the feasible region and dS is the disagreement point.& Each player can join to one coalition.& The players bargain over utility distribution in each game.

In practice, the players have to face two intertwined decision problems: which coalition to form and which payoff vector to choose from the bargaining region for the members of each coalition. Other approaches to coalition formation problems mainly search for an allocation of the worth of the grand coalition (see [26]).

4.3 Tools

& A bargaining solution is a function S : HSRS

yxT

( n o if T S

& A feasibility function is a function VS : {xRSN|xxS}RSN that returns a feasible allocation for coalition S if the solution of V S associated to outside opportunities is infeasible:

SV x

S V S

; x

if xV S

S V S

; xS; x

( otherwise

4.4 Computation of the C-Solution

The C-Solution concept is defined by induction on the cardinality of the set of relevant coalitions V; in other words we consider first the coalition structure in which each player stands alone, next we define an abstract game where X is the set of payoff configurations corresponding to the coalition structures generated by adding at each step one of the relevant coalitions and considering as payoff vector the solution of the bargaining problem for the relevant coalitions and the stand-alone solution for the singletons and using the above defined domination relation.

Formally, we have:

Initial step |V|=0V=

The C-Solution is ({{1}, {2}, , {n}}, (x1, x2, , xn))

Iterative step |V|=m1

The C-Solution is the dynamic solution of the abstract game (X, dom) where X={(P,x)RN},

with xT

T V T

; yT

N that

assigns a payoff vector as a solution for each bargaining problem for S, and satisfies the following properties:

Feasibility: S(FS, dS) FSIndividual rationality: S(FS, dS)dSPareto optimality: xRSN,x>S(FS,dS)xFS

The three solutions presented in Section 3 are possible choices.

& A payoff configuration is a couple (P, x) P(PFV(P))

where P is a coalition structure, i.e. a partition of the player set N, and FV(P) is the set: {x RN | x V(S),

S P}.& The domination relation between two different payoff configurations (P1, x1), (P2, x2) is:

(P1,x1)dom(P2,x2)RP1|xi1>xi2,iR& The set of relevant coalitions for a game V, V, is the set of coalitions S, |S|2, s.t.: y V(S) | y>xSwhere xS=(xi)iS and xi=sup {t R | tei V(i)}.

for each T P, yT

if TV and jTj2

xi if T i

f g

1 K Th1xhT and dom is the domination defined above.

The point yTrepresents the average payoff of the players in the C-Solution {(P1, x1), , (PK(T), xK(T))} P P FV

T P

of the reduced game V T, that represents the outside opportunities of the players of T in the other coalitions:

Note that V T is originated according to the current V, so by the inductive hypothesis the C-Solution was computed in the previous step; as X is finite, the dynamic solution is always non-empty.

We remark that the C-Solution may be used also for a TU-game, applying it to the associated NTU-game (see Example 1).

5 The problem

We consider a situation in which a set N={1, , n} of TOs operates a set of trains on the same line. For sake of simplicity

118 Eur. Transp. Res. Rev. (2014) 6:113125

we suppose that each TO operates exactly one train, so that we may identify the set of TOs and the set of trains .2

In order to determine a scheduling, we assume that each TO i=1, , n, communicates to the IM a small set of data consisting of the ideal departure time for the train he operates pi, the travel time ti and the associated arrival time ai = pi + ti, the corresponding maximal utility, Ui, and a feasible time window fi = f i; f i

h i

with pi fi, that represents the time interval in which it is still profitable to schedule the departure of the train. At this point the

IM assigns to each train an a priori utility function (see Fig. 1). We may think of a utility function as a map that assigns to every possible leaving instant a real number that represents the income for operating the train according to this departure time. The a priori utility function for each TO i=1, , n is continuous, piecewise linear and assumes the maximum value at its ideal departure time, while is null outside of its feasible time window, as the train is no longer operated:

Fig. 1 The a priori utility function

bu xi

Ui

xif i

pif i

8

>

>

>

>

>

>

>

<

>

>

>

>

>

>

>

:

if xi f i; pi

h i

Ui f ixi f ipi

if xi pi; f i

h i 0 otherwise

Referring to these utility functions, we suppose that the IM defines a scheduling (x1*,,xn*) that maximizes the total utility, iN

bui x , minimizing the losses of each train, Ui -

bui x i ; i 1; ; n . Obviously, if xi*fi the TO

may decide to not operate train i.

We do not go deeper on this aspect and we address to the literature mentioned in Sections 1 and 2 for the possible approaches that may be used for computing the scheduling (x1*,, xn*), but we remark that the proposal of the IM is based on the a priori utility functions bui; i 1; ; n .

The resulting scheduling is communicated to the TOs.

Looking at the proposed timetable, it is possible that a small group of TOs realize that a coordinate behaviour may improve their utilities. So, they decide to cooperate and share among them (possibly with the intervention of a mediator) more details about their utility functions. A larger set of information may lead to a different scheduling that increases the profits of the cooperating TOs, without affecting the timetable of other trains. Let us illustrate it using a simple example: suppose that the TO of train A considers his best choice to leave from a given station ten minutes after the arrival of train B; in this situation the maximum of the utility is defined according to the arrival time of train B. The TO establishes his ideal departure time referring to historical data, that can be no longer valid in the new timetable. When the

IM proposes its timetable, this information is available, so the TOs may work on better data for designing their real utility functions, i.e. a utility function that takes into account more data, those that are made public by the IM and those that all the TOs decide to share with the cooperating agents. We want to stress that the true utility function of an agent is difficult to determine even for him and contains data that are considered private information by each agent. In other words, our setting is not a full information one. In the examples in the following section we suppose that the a priori and the real utility functions of each TO have the same ideal departure time and time window, while the values of the utility could be different. In Examples 2, 3 and 4, the real maximal does not coincide with the one communicated to the IM; this difference may be motivated by the idea that the IM may apply a smaller access fee to the infrastructure. Another interesting point is that, as we said, the scheduling proposed by the IM may influence some elements of the real utility function of a TO, especially the ideal departure time or the extension of the time window. Finally, we want to remark that even if the a priori and the real utility functions of all the TOs coincide not necessarily the solution proposed by the IM is the same of the bargaining process, because some agents may be more able during the negotiation, unless the solution proposed by the IM is Pareto optimal for the agents and side payments are not allowed (see Example 3).

We propose to use game theoretical tools in order to model a cooperative situation in which the agents are interested in improving their own utility; when the TOs decide to cooperate we have a problem of coalition formation. This problem often arises when we want to model a real-world situation; in fact it is very important that the model takes into account the various possibilities of the players, in particular that it is not necessary that all the players form the grand coalition and that each player decides to cooperate with other players not for the worth of the coalition but on the basis of its own payoff (see [27] and [28]). The C-Solution proposed by Gerber [1] seems very suitable both for getting a numerical solution of the problem and because it does not necessarily favour the formation of the grand coalition.

In the following section we present some examples in which we completely develop the approach proposed in this section, referring to simple case-studies.

6 Examples

In this section, we present four examples. In order to make the reasoning simpler, we suppose that the solutions may differ only in the departure time, i.e. we do not allow the possibility of

2 Otherwise, we may assume that when a TO operates more trains it is split in several clones, each one operating one train.

Eur. Transp. Res. Rev. (2014) 6:113125 119

Table 2 Scheduling proposed by the IM and a priori utilities of the TOs (Example 1)

Departure time A priori utility

TO1 9.20

bu1 9:20 30

TO2 9.58

bu2 9:58 30

TO3 10.00

bu3 10:00 30

TO4 10.45

bu4 10:45 15

TO5 11.00

bu5 11:00 30

Table 1 Data communicated by the TOs to the IM (Example 1)

Departure time

Travel time

Arrival time

Time window

Maximal utility

TO1 9.20 25 9.45 [8.50, 9.50] 30 TO2 9.58 32 10.30 [9.28,10.28] 30 TO3 10.00 86 11.26 [9.30,10.30] 30 TO4 10.30 43 11.13 [10.00,11.00] 30

TO5 11.00 40 11.40 [10.30,11.30] 30

modifying the travel time of the trains. Consequently, we consider a line without intermediate stations, as the scheduling of the trains depends only on their departure times. Moreover, we suppose that all the TOs declare to the IM the same maximal utility Ui, i=1, , n.

Example 1 refers to a simple situation with five trains two of which have conflicting requests and the resolution of the conflict may involve also a third train. The solution proposed by the IM may be improved when the three TOs involved take into account their real utility functions. In this first example we suppose that the TOs accept to transfer utility among them, i.e. side payments are permitted, so that the main aim is to maximize the global utility; the proposed methodology allows computing also the monetary compensations that the agents have to pay or receive as a consequence of the new scheduling obtained after the agreement. The limited number of agents enables us to completely develop the steps of the iterative procedure for computing the C-Solution.

Examples 2, 3 and 4 consider a situation in which the agents are not allowed for side payments. In these cases the improvement of the solution is obtained through a bargaining procedure among the agents. In order to have a simple graphical representation of the strategies and of the utilities of the agents, we restrict to two-agent situations, being aware that this excludes intermediate coalitions and consequently, the outside opportunities do not play any role. The data set, i.e. the requirements of the agents are the same in all three examples, but introducing different real utility functions we analyze three possible situations: in Example 2 the agents may improve their utilities with respect to the proposal of the IM and we show three possible alternatives corresponding to the bargaining problem solutions of Nash, Kalai-Smorodinsky and Egalitarian; in Example 3 the agents realize that the proposal of the IM is already Pareto optimal, i.e. it cannot be improved by an agent without a reduction of the utility of the other one; finally, Example 4 shows that under

particular utility functions the agents may face a situation in which the bargaining region is non-convex, in contrast with the classical literature. The situation of Example 4 allows us to propose some non-standard approaches to this kind of problems. In all the examples we assume that the headway time between trains is at least two minutes.

6.1 Example 1 - trains with transferable utilities

We consider a situation with five TOs, whose requirements are in Table 1 and the string diagram is in Fig. 2.

In order to solve the conflict between trains 3 and 4, the IM computes the optimal scheduling using the a priori utility functions of the TOs. The solution of the conflict requires to anticipate the leaving of train 3 or to delay the leaving of train 4 or both. It is easy to observe that according to the a priori utility function each minute of difference with respect to the optimal departure time corresponds to a reduction of one unit of utility for the corresponding TO; on the other hand the anticipation of train 3 requires anticipating also the departure of train 2. This corresponds to a reduction of two units per minute of the global utility of TOs 2 and 3, while a delay of train 4 reduces the utility of TO 4 of one unit per minute.

In Table 2 we report the departure times and the corresponding a priori utilities of the TOs associated to the scheduling that maximizes the global utility; the related string diagram is depicted in Fig. 3.

Clearly, TO 4 does not like the reduction of his utility with respect to his expectation, so he looks for a better solution after an agreement with TOs 2 and 3. Note that trains 1 and 5 do not influence the decisions of TOs 2, 3 and 4 because there is no conflict when departure times are in the time windows. Suppose

Fig. 2 String diagram with conflict among the TOs (Example 1)

120 Eur. Transp. Res. Rev. (2014) 6:113125

Fig. 3 String diagram proposed by the IM (Example 1)

that the three TOs have similar real utility functions, i.e. all of them obtain quite the same utility if the departure time is anticipated (in the time window), while the utility linearly decreases to zero after the ideal departure time (see Fig. 4):

uri xi

30 pixi 30 pif i

8

>

>

>

>

>

>

>

>

>

>

>

<

>

>

>

>

>

>

>

>

>

>

>

:

if xi f i; pi

h i

30 fixi fipi

if xi pi; f i

h i i 2; 3; 4

0 otherwise

This situation is a natural habitat for our purpose: it is possible that the real utility functions induce a better solution for the three players. First of all, note that the utilities of the TOs 2, 3 and 4 according to their real utility functions coincide with their utilities according to the a priori utility functions.

We suppose that computing the C-Solution, in each bargaining problem HS, SN={2, 3, 4} the players in S agree on the scheduling that corresponds to their maximal global utility M(S), so V(S)={x RS | iN xiM(S)}, i.e. the feasible s-tuples of utilities for the members of S. Under this hypothesis the

Nash, Kalai-Smorodinsky and Egalitarian solutions coincide; the corresponding payoffs are obtained with side payments.

For each coalition SN, the characteristic function V(S) is defined on the basis of the solution proposed by the IM and of the real utility functions of the TOs (see Table 3). More precisely, the scheduling of the TOs not belonging to S remain fixed according to the solution proposed by the IM, while the scheduling of the TOs belonging to S are re-optimized referring to their real utility functions uir,iS, maximizing the total utility iSuir(xi).

The set of relevant coalitions is:V={{3,4}, {2,3,4}}

Now, we have all the data for performing the steps of the procedure for computing the C-Solution.

Initial step

|V|=0 V=

There is a unique coalition structure: ({2}, {3}, {4}).

The C-Solution is ({2}, {3}, {4}), (30, 30, 15)), according to the scheduling proposed by the IM.

Iterative step

|V|=1 V={{3,4}}

There are two coalition structures: ({2}, {3}, {4}) and ({2}, {3,4}).

The payoff vector is computed with respect to the coalition {3,4}:

Table 4 Scheduling and real utilities after the agreement of the TOs (Example 1)

Departure time Real utility

TO1 9.20 u1r(9.20)=30 TO2 9.43 u2r(9.43)=29.50 TO3 9.45 u3r(9.45)=30 TO4 10.30 u4r(10.30)=30 TO5 11.00 u5r(11.00)=30

Fig. 4 Real utility functions of TO2, TO3, TO4 (Example 1)

Table 3 Characteristic function V(S) and the maximal global utility M(S) for each coalition SN (Example 1)

S V(S) M(S)

{2} {uR{2}|u2r30} u2r(9.58)=30

{3} {uR{3}|u3r30} u3r(10.00)=30

{4} {uR{4}|u4r15} u4r(10.45)=15

{2,3} {uR{2,3}|u

2

r+u3r60}

u2r(9.58)+u3r(10.00)=30+30

{2,4} {uR{2,4}|u

3

r+u4r45}

u2r(9.58)+u4r(10.45)=30+15

{3,4} {uR{3,4}|u

3

r+u4r57}

u3r(10.02)+u3r(10.00)=28+29

{2,3,4} {uR{2,3,4}|u

2

r+u3r+u4r89} ur2 9:43

ur3 9:45

ur4 10:30

29:50 29:50 30

Eur. Transp. Res. Rev. (2014) 6:113125 121

Fig. 5 String diagram after the agreement of the TOs (Example 1)

T 3; 4

f g yT 0; 30; 15

is feasible

T V T

; yT

0; 36; 21

X={(({2}, {3}, {4}), (30, 30, 15)), (({2}, {3,4}), (30, 36,21))}

The C-Solution is ({2}, {3,4}), (30, 36, 21)), i.e. train 2

leaves at 9.58 (IM solution) with utility 30, train 3 at 10.02 with utility 28 plus a compensation of 8 from the fourth TO and train 4 at 10.00 with utility 29 minus a compensation of 8 to the third TO.

V={{2,3,4}}

There are two coalition structures: ({2}, {3}, {4}) and ({2,3,4}).

The payoff vector is computed with respect to the coalition {2,3,4}:

T 2; 3; 4

f g

yT 30; 30; 15

is feasible

T V T

; yT

34:66; 34:66; 19:66

X={(({2}, {3}, {4}), (30, 30, 15)), (({2,3,4}), (34.66,34.66, 19.66))}

The C-Solution is (({2,3,4}), (34.66, 34.66, 19.66)), i.e. train 2

leaves at 9.43 with utility 29.50 plus a compensation of 5.16 from the fourth TO, train 3 at 9.45 with utility 29.50 plus a compensation of 5.16 from the fourth TO and train 4 at 10.30 with utility30.00 minus a compensation of 10.33 to the other TOs.

V

2

V={{3,4},{2,3,4}}

There are three coalition structures: ({2}, {3}, {4}), ({2}, {3,4}) and ({2,3,4}).

The payoff vectors computed with respect to the coalitions {3,4} and {2,3,4} are:

T 3; 4

f g yT 0; 34:66; 19:66

is feasible

T V T

; yT

0; 36; 21

T 2; 3; 4

f g yT 30; 36; 21

is feasible

T V T

; yT

30:66; 36:66; 21:66

X={(({2}, {3}, {4}), (30, 30, 15)), (({2}, {3,4}), (30, 36,21)), (({2,3,4}), (30.66, 36.66, 21.66))}

The C-Solution is (({2,3,4}), (30.66, 36.66, 21.66)), i.e.

train 2 leaves at 9.43 with utility 29.50 plus a compensation of1.16 from the fourth TO, train 3 at 9.45 with utility 29.50 plus a compensation of 7.16 from the fourth TO and train 4 at10.30 with utility 30 minus a compensation of 8.33 to the other TOs (see Table 4 and Fig. 5). The different compensations of TOs 2 and 3 depend on their different roles played in the coalition formation process. In fact the C-Solution reflects the opportunity that players 3 and 4 have of getting a joint utility of 57 not cooperating with player 2. In other words player 2 cannot obtain the utility of 34.66 that assigns to players 3 and 4 a joint utility of 55.32, because they may exclude player 2 from the coalition, getting a joint utility of 57. However, each player increases his final payoff with respect to the solution proposed by IM.

Remark 1 When TOs exchange information about their real utility functions they realize that each minute of delay for train 4 reduces its utility of one unit, i.e. the same amount of anticipating of 15 min both trains 2 and 3. The possibility of transferring the utility from TO 4 to TOs 2 and 3 induces them to accept the new scheduling.

6.2 Example 2 - trains without transferable utilities

In order to have a better analysis of the bargaining problem we suppose that the players cannot transfer their utilities. Starting

Table 5 Data communicated by the TOs to the IM (Example 2)

Departure time

Travel time

Arrival time

Time window

Maximal utility

TO1 10.00 60 11.00 [9.30,10.30] 15 TO2 10.20 22 10.42 [9.50,10.50] 15

Fig. 6 String diagram with conflict among the TOs (Example 2)

Table 6 Scheduling proposed by the IM and a priori utilities of the TOs (Example 2)

Departure time A priori utility

TO1 9.50

bu1 9:20 10

TO2 10.30 u2 10:30

10

122 Eur. Transp. Res. Rev. (2014) 6:113125

Fig. 7 String diagram proposed by the IM to the TOs (Example 2)

from the strategies of each player, i.e. the possible departure times, we build up the space of strategies. If a situation of conflict shows up it means that some tuples of strategies are infeasible.

We define the bargaining problem using the utility functions of the players in order to define the bargaining region in the space of the utilities; in this case the natural choice for the disagreement point is the solution proposed by the IM, because it has the double role of starting point for the negotiation and of adopted scheduling if the negotiation fails. We analyze the Nash, Kalai-Smorodinsky the Egalitarian solutions. Consider the requirements of TOs as in Table 5 and the string diagram as in Fig. 6.

Using the a priori utility functions, maximizing the total utility and minimizing the loss of each train, the IM solves the conflict between the trains. The departure times and the related a priori utilities of the TOs are given in Table 6; the corresponding string diagram is depicted in Fig. 7.

In Fig. 8, we represent the space of strategies (departure times) of the two players; the horizontal axis represents the departure times in the time window for TO1 and the vertical axis represents the departure times in the time window for TO2; the points A, B, C, D, E, F, G, H, I, J represent the extreme points that will be used to define the bargaining region in the space of utilities of the two players; the point IM represents the solution proposed by the IM that corresponds to the disagreement point in the bargaining problem; the UNFEASIBLE region corresponds to pairs of departure times that produce a conflict among trains.

Now, we introduce the real utility functions of the two TOs, represented in Fig. 9 (note that the real maximal utilities of the two TOs are different from those communicated to the IM) and build the bargaining problem (in the space of utilities) depicted in Fig. 10 (the utilities of the TOs are reported in Table 7).

We compute the solutions of Nash (N), Kalai-Smorodinsky (K) and Egalitarian (E) for the bargaining problem in Fig. 10

Fig. 10 The bargaining problem (Example 2)

Table 7 Utilities of the two players (Example 2)

point A B C D E F G H I J IM

real utility ofTO1

80 50 23 40 40 80 26 23 80 80 0 0 53 13

real utility of

TO2

35 13 50 50 30 30 50 16 23 0 0 50 33 13

Fig. 8 The space of strategies of the two players (Example 2)

Fig. 9 Real utility functions of TO1 (a) and TO2 (b) (Example 2)

Eur. Transp. Res. Rev. (2014) 6:113125 123

Fig. 13 The bargaining problem (Example 3)

Table 9 Utilities of the two players (Example 3)

point A B C D E F G H I J IM

real utility of

TO1

80 21 13 0 0 80 53 13 80 80 40 40 66 23

real utility of

TO2

Fig. 11 The space of strategies of the two players with the three possible solutions (Example 3)

and referring to the space of strategies (see Fig. 11), we compute the corresponding timetables and the related real utilities of the TOs (see Table 8).

6.3 Example 3 - Pareto optimal disagreement point

In this example we suppose that the real utility functions of the two TOs are those represented in Fig. 12.

The new bargaining problem is represented in Fig. 13 and the real utilities are reported in Table 9.

In this case the solution proposed by the IM is already on the Pareto boundary of the bargaining region and it is Pareto optimal (we can improve the utility for one player only with a loss for the other one).

6.4 Example 4 - non-convex bargaining region

Avery interesting problem appears when we consider a slightly different situation in which the real utility functions of the two TOs are those represented in Fig. 14.

The new bargaining problem is represented in Fig. 15 and the real utilities are reported in Table 10.

Here the bargaining region is not convex. If we consider also the area delimited by the segment BG as the usual theory of bargaining suggests a new question arises: what is the meaning of these new points, or more precisely the points of the individually rational Pareto boundary B G ?

Table 8 The scheduling corresponding to the three solutions (seconds are in brackets) and the real utilities of the TOs (Example 2)

Solution TO Departure time Real utility

Nash TO1 10.08(.30) ur1 10:08

68 23

TO2 10.06(.30) u2r(10.06)=41 Kalai-Smorodinsky TO1 10.10(.00) ur1 10:10

66 23

TO2 10.08(.00) u2r(10.08)=42 Egalitarian TO1 10.12(.20) ur1 10:12

63 1425

TO2 10.10(.20) ur2 10:10

43 1425

Fig. 12 Real utility functions of TO1 (a) and TO2 (b) (Example 3)

13 13 50 50 0 0 50 36 23 30 30 50 43 13

124 Eur. Transp. Res. Rev. (2014) 6:113125

Fig. 14 Real utility functions of TO1 (a) and TO2 (b) (Example 4)

In the space of strategies the segment B G corresponds to infeasible strategies. We can consider these points as corresponding to correlated strategies or to lotteries of the two (feasible) events B and G. A correlated strategy is impossible in the present situation because the timetable is fixed for all the season and cannot be varied on the basis of a probabilistic event; on the other hand a lottery requires that the players accept the risk of a result that can be worse of the solution of the IM.

Another possible interpretation corresponds to a side payment between the players, but in this case the two players will try to maximize their joint utility so they choose G and if they agree on side payments we are back to a situation like that in Example 1.

Finally we can restrict to consider only the individually rational Pareto boundary eB

eG, returning to a usual bargaining problem, like that in Example 2.

7 Concluding remarks

The approach proposed in this paper presents how to improve a railway timetable, when a small set of agents decides to cooperate exchanging more data with respect to the dataset communicated to the IM. The C-Solution method shows not only how to produce a better schedule, but also the level of compensation that an agent requires for accepting a worse scheduling, in order to increase the global utility of the cooperating agents. Clearly, under this assumption it is possible to increase the global utility, with positive influence on the quality of service for the users. This approach can be applied whenever the scheduling proposed by the IM relies on less information than that exchanged by the TOs in our model.

This procedure may increase also the utility of the IM who may succeed in allocating a larger number of tracks, via a better use of the infrastructure, or simply asking a higher price to the TOs, after that more profitable scheduling increases their willingness-to-pay. The IM, aiming to increase profit and quality of service, may have an interest in creating an arena for stimulating communication between the TOs. In this way some of them may identify situations of inefficiency that could lead to an agreement that improves the utility and the scheduling.

We know that the main hindrance to the proposed approach is implicit in the railway system, i.e. the operators resistance to cooperate and to reveal even partial information (in view of

Fig. 15 The bargaining problem (Example 4)

Table 10 Utilities of the twoplayers (Example 4) point A B C D E F G H I J IM

real utility of TO1 80 50 23 40 40 80 26 23 80 80 0 0 53 13

point real utility of TO2 13 13 50 50 0 0 50 30 20 20 50 40

point B G

eB eG

real utility of TO1 53 13 65 13 53 13 58 23

real utility of TO2 48 211 40 46 23 40

Eur. Transp. Res. Rev. (2014) 6:113125 125

this, we were not able to make suitable comparisons of our approach with other ones); nevertheless we think that it should be of extreme importance to use research in order to highlight the benefits that could originate from a higher level of cooperation in order to stimulate TOs. Clearly, the maximal improvement of the utility may be obtained in a transferable utility setting, possibly with large exchange of information, as we noticed in the comments to Example 4.

Possible further developments of the present research include a deeper analysis of the situation illustrated in Example 4, via an analysis of the strategic behaviour of the agents. It would be interesting to compare some refinements of our approach with a combinatorial auction using sophisticated strategies. First of all, it is interesting to analyze the possibility that an agent intentionally disable some coalitions in order to reduce the alternatives for himself or for other agents; secondly, the agents may face a combinatorial auction, that allows for different strategies in submitting bids, following the ideas first addressed by Rassenti et al. [29] and reconsidered by Borndrfer et al. [20]. Another point deserving better analysis is the situation shown in the last example. In fact the assumption of convexity for the bargaining region is important from a theoretical point of view, but it may result no longer valid in this and other real-world situations (see [30]).

Acknowledgement The authors gratefully acknowledge the useful suggestions of two anonymous reviewers that allowed improving the paper.

Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution and reproduction in any medium, provided the original author(s) and source are credited.

References

1. Gerber A (2000) Coalition Formation in General NTU-Games. Rev Econ Des 5:149175

2. Hooghiemstra JS, Kroon LG, Odijk MA, Salomon M, Zwaneveld PJ (1998) Decision support systems support the search for Win-Win Solutions in railway network design. Interfaces 29:1532

3. Hollander Y, Prashker JN (2006) The applicability of non-cooperative game theory in transport analysis. Transportation 33:481496

4. Nash JF (1950) The bargaining problem. Econometrica 21:1281405. Odijk MA (1996) A constraint generation algorithm for the construction of periodic railway timetables. Transp Res B Methodol 30:4554646. Kroon L, Dekker R, Vromans M (2007) Cyclic railway timetabling: a stochastic optimization approach. In: Geraets F, Kroon L, Schoebel A, Wagner D, Zaroliagis CD (eds) Algorithmic methods for railway optimization, lecture notes in computer science 4359. Springer, Berlin, pp 4166

7. Fischetti M, Salvagnin D, Zanette A (2009) Fast approaches to improve the robustness of a railway timetable. Transp Sci 43:321 335

8. Ho TK, Tsang CW, Ip KH, Kwan KS (2012) Train service timetabling in railway open markets by particle swarm optimisation. Expert Syst Appl 39:861868

9. Wong SK, Ho TK (2010) Intelligent negotiation behaviour model for an open railway access market. Expert Syst Appl 37:8109 8118

10. Bouwman MR, Greuter JBJ (2001) Rapportage SIMONE studies voor ProRail Capaciteitstoedeling. Incontrol Enterprise Dynamics

11. Nash A, Huerlimann D (2004) Railroad simulation using opentrack. Comput Railways IX:4554

12. Radtke A, Hauptmann D (2004) Automated planning of timetables in large railway networks using a microscopic basis and railway simulation techniques. Comput Railways IX:615625

13. Meijer S (2012) Introducing gaming simulation in the Dutch railways. Procedia Social and Behav Sci 48:4151

14. Abril M, Barber F, Ingolotti L, Salido MA, Tormos P, Lova A (2008) An assessment of railway capacity. Transp Res Part E Logistics Transp Rev 44:774806

15. Hansen IA (2010) Railway network timetabling and dynamic traffic management. Int J Civil Eng 8:1932

16. Brewer PJ, Plott CR (1996) A Binary Conflict Ascending Price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks. Int J Ind Organ 14:857886

17. Nilsson JF (2002) Towards a welfare enhancing process to manage railway infrastructure access. Transp Res A 36:419436

18. Caprara A, Fischetti M, Toth P (2002) Modeling and solving the train timetabling problem. Oper Res 50:851861

19. Caprara A, Monaci M, Toth P, Guida PL (2006) A Lagrangian heuristic algorithm for a real-world train timetabling problem. Discret Appl Math 154:738753

20. Borndrfer R, Grtschel M, Lukac S, Mitusch K, Schechte T, Scultz S, Tanner A (2005) An Auctioning Approach to Railway Slot Allocation. ZIB Report ZR-05-45

21. Lalive R, Schmutzler A (2008) Exploring the effects of competition for railway markets. Int J Ind Organ 26:443458

22. Kuo A, Miller-Hooks E (2012) Developing responsive rail services through collaboration. Transp Res Part B Methodol 46:42443923. Kalai E, Smorodinsky M (1975) Other solutions to Nashs bargaining problem. Econometrica 43:513518

24. Kalai E (1977) Proportional solutions to Nashs bargaining situations: interpersonal utility comparisons. Econometrica 45:16231630

25. Shenoy PP (1980) A dynamic solution concept for abstract games. J Optim Theory Appl 32:151169

26. Bennett E, Zame WR (1988) Bargaining in cooperative games. Int J Game Theory 17:279300

27. Hart S, Kurz M (1983) Endogenous formation of coalitions. Econometrica 51:10471064

28. Greenberg J (1994) Coalition Structures. In: Aumann RJ, Hart S (eds) Handbook of Game Theory Vol. II. North Holland, Amsterdam29. Rassenti SJ, Smith VL, Bulfin RL (1982) A combinatorial auction mechanism for airport time slot allocation. Bell J Econ 13:402417

30. Agnetis A, Fragnelli V (2013) Some Nonstandard Features of Bargaining Problems. International Game Theory Review 15. DOI:http://dx.doi.org/10.1142/S0219198913400070

Web End =10.1142/S0219198913400070