# Revenue management for rail container transportation

Ioana Bilegan, Luce Brotcorne, Dominique Feillet, Yezekael Hayel

► To cite this version:

Ioana Bilegan, Luce Brotcorne, Dominique Feillet, Yezekael Hayel. Revenue management for rail container transportation. EURO Journal on Transportation and Logistics, 2015, 4 (2), pp.261-283. 10.1007/s13676-014-0051-7. emse-01092226

HAL Id: emse-01092226

https://hal-emse.ccsd.cnrs.fr/emse-01092226

Submitted on 29 Apr 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

# Revenue management for rail container transportation

Ioana C. Bilegan · Luce Brotcorne ·
Dominique Feillet · Yezekael Hayel

Received: 26 March 2013 / Accepted: 1 April 2014 / Published online: 15 April 2014

© Springer-Verlag Berlin Heidelberg and EURO - The Association of European Operational Research Societies 2014

**Abstract** In this paper, we consider the revenue maximization problem of a rail freight transportation company or an intermodal marketing company selling freight transportation services. We propose a revenue management (RM) policy to dynamically accept transportation requests or reject them in favor of some future forecasted transportation demands with higher potential profit. In the proposed load acceptance system, we explicitly take the network structure into account. We analyze solutions obtained from numerical simulations and conclude on the promising results shown by the RM system.

**Keywords** Revenue management · Rail transportation · Multi-commodity flow problem

<figure><img src="image_4.png" /></figure>

<footnote>I. C. Bilegan
LAMIH UMR CNRS 8201, Université de Valenciennes et du Hainaut-Cambrésis,
59313 Valenciennes, France
e-mail: ioana.bilegan@univ-valenciennes.fr</footnote>

<footnote>L. Brotcorne
INRIA Lille-Nord Europe, 59650 Villeneuve d'Ascq, France
e-mail: luce.brotcorne@inria.fr</footnote>

<footnote>D. Feillet (✉)
Ecole des Mines de Saint-Etienne, CMP Georges Charpak, 13541 Gardanne, France
e-mail: feillet@emse.fr</footnote>

<footnote>Y. Hayel
LIA, Université d'Avignon et des Pays de Vaucluse, 84911 Avignon, France
e-mail: yezekael.hayel@univ-avignon.fr</footnote>
# 1 Introduction

Rail freight transportation companies are facing the consequences of deregulation and high competition over the same physical infrastructure. In order to best serve their clients, while maximizing the utilization of their available capacities, an optimal management of their costly assets has to be found (Crainic 2009). Revenue Management (RM) offers a set of tools to make decisions, at the operational level, to maximize the benefits of a firm by dynamically adjusting the offer to the forecasted future demand.

In this paper, we use RM strategies to “sell the right product to the right customer at the right price at the right time” (AMR Annual Report 1987). More precisely, we consider the problem of a rail freight transportation company or an intermodal marketing company selling freight transportation services. We consider a full-asset-utilization operation policy corresponding to operating regular and cyclically scheduled services with fixed composition (Crainic et al. 2006). This means that each service is scheduled once during a given period, the planned schedule being repeated cyclically over the time horizon. Demand for shipments varies greatly across locations and time, partially due to new management practices favoring just-in-time production strategies. Managing such a complex system requires the use of a reservation system. Traditionally, the transportation requests are accepted on a first-come first-served basis, as long as free capacity exists, and the prices are usually based on handling costs and distances. In such a system with scarce resources during some periods, high-value demands may be unsatisfied due to infeasibility. However, the customers do not all have identical time delivery constraints and/or quality of service requirements. For example, some companies are willing to pay less for longer deliveries or to pay higher rates for quicker deliveries. In this context, it may be advantageous to hold some capacity in reserve if there is a reasonable expectation that high revenue, service sensitive customers will arrive later. The load acceptance management system we design in this paper aims to dynamically accept transportation demands or reject them in favor of some future forecasted transportations demands with higher potential profit. As we will see later the rail freight load acceptance problem, we consider few similarities and differences with the airline inventory control problems in RM systems. The principle that transportation demands can be rejected and the mathematical modeling assumptions made in this paper are not necessarily acceptable in all contexts. National rail industry organization differs greatly between countries. For example, in the US, large railroads are subject to “common carrier laws” that force them to accept any demand that is placed to them. The approach developed in this paper concerns rail transportation companies with regulations or practices similar to that of France and other EU countries.

Revenue management systems are classically separated in four subproblems: demand forecasting, inventory control, pricing decision and oversales (Belobaba 1987; Capiez 2003; Chiang et al. 2007; Talluri and van Ryzin 2004). Commonly used in passenger airline transportation or in other service industries such as car rentals or hotels, applications in rail transportation of freight are not largely reported in the scientific literature. Yet, many of the characteristics required for efficiently
applying RM to this mode of transportation are present: the demand varies with time and is uncertain, the transportation service is perishable (scheduled trains have to depart on time, even if their transportation capacity is not full; thus, the unused space on the transportation service is not generating monetary benefits, although the fixed costs of the service have to be payed), and different client profiles and market segments are easily identifiable. In a recent perspective (Kuehn 2011), Kuehn states that yield management is an answer to US freight rail carriers' capacity problems. Although there are challenges in applying conventional yield management techniques to the rail industry, the author describes possible alternative approaches that could help railroads to manage traffic and allocate service network capacity more efficiently. Several presentations at INFORMS annual conferences also emphasized the high potential of RM systems designed for dealing with container (or, more generally, freight) transportation by railway (Gao and Gorman 2008; Lieberman 2005).

A recent survey on railway RM problems is presented in (Armstrong and Meissner 2010). The authors provide an overview of the published literature for both passenger and freight railway RM. While for passengers, the relationships with airline RM are shown to be rather strong [see, e.g., (Bharill and Rangaraj 2008) or (You 2008)], the authors highlight additional difficulties associated with freight rail transportation. These include the fact that the effective capacity in rail transportation is heterogeneous and not known in advance (Gorman 2005). Furthermore, the capacity management problem is highly combinatorial, since solution (the capacity allocation) depends on the routes followed by the merchandise on the service network (Cordeau et al. 1998).

The way revenue and traffic flow management that can be integrated has not been investigated much in the literature. Seminal studies on this issue were provided by Kraft, in his Ph.D thesis (Kraft 1998) and his papers (Kraft 2002; Kraft et al. 2000). This type of study was recently extended in (Crevier et al. 2012). In these different papers, several RM or pricing strategies have been proposed on different types of networks and under diverse assumptions. In this paper, we follow the same line of investigation. However, a major difference is that we explicitly take into account the network structure and interactions in the decision process. More precisely, a lower priority shipment may be displaced even at an intermediate terminal in favor of a newly arrived high revenue load if sufficient slack time exists in the schedule. We assume that a differential pricing policy with different fare classes is proposed to the clients. We focus on the load acceptance process faced by rail freight transportation or by an intermodal company to maximize revenues taking into account future demand forecasting.

The contribution of this paper is a new decision-making process based on a booking and RM system for rail container transportation planning at the operational level. The proposed approach is based on a probabilistic mixed integer programming model formulated on a space-time network representation of the transportation services. A discrimination policy (accept/reject) for each new incoming demand is applied, and the decision process explicitly takes into account the flow interactions between present and future potential demands, to maximize expected revenues. The routing of the demand in the space-time network is evaluated in a
predictive manner, by taking into account the potential influence of future high
revenue demands, for which capacity should be reserved on the network. We solve
the expected revenue maximization problem using an off-the-shelf solver and
validate by numerical simulation the decision support system on test instances
inspired by French/EU rail transportation companies. We perform sensitivity
analysis on fare classes price ratios and demand estimation accuracy criteria to show
the robustness of the proposed approach.

The paper is organized as follows. We give a general description of the booking
system in Sect. 2. We describe the transportation scheme and introduce a
mathematical model for the optimization of container flows in Sect. 3. We present
the RM policy and the way new booking requests are accepted in Sect. 4. We finally
provide simulation results evaluating this policy in Sect. 5. Concluding remarks and
perspectives are given in Sect. 6.

## 2 General description of the booking system

Freight rail transportation companies have a complex organization. When dealing
with very dense rail infrastructures such as the French or European rail network, the
main difficulty is that many different types of users share the same physical
network: competitors (freight transporters), passenger transporters, etc. [see, e.g.,
(Cacchiani et al. 2010) or (Godwin et al. 2007)]. A very tight planning is thus
needed to ensure traffic safety. Companies have to make very early bookings, often
more than 1 year in advance, for the needed utilization of the network, with
precisely defined time-schedules.

The main purpose of the booking system developed here is to answer the
following question: for each new booking demand, what is the right decision, to
accept or to reject it? Each new booking demand arriving in the system is
characterized by its origin and destination on the carrier's service network, the
containers' availability date at the origin, their maximum delivery time, their total
volume (in standard volume units, TEU—*twenty equivalent units*) etc. The time
characteristics such as the booking anticipation and the latest delivery time
constitute the criteria used to match a specific booking request to its corresponding
fare class. Its associated fare is thus known a priori, and no fare negotiation process
is to be proposed to the client. Accepting the booking request is decided based on
the comparison between the expected future revenue computed with and without
that demand in the booking system. This discrimination policy is inspired by
classical mechanisms of bid-price controls for network RM, which are based on
accepting a booking request only if its price exceeds the opportunity cost of the
reduction in resource capacities required to satisfy that request (Talluri and van
Ryzin 2004).

In order to estimate these expected revenues, we introduce a space-time network
flow problem. We consider two scenarios, both of them accounting for flows
corresponding to the already accepted demands, the future potential demands (given
in terms of probability distribution of their volumes) and, in turn, including the
current demand (Scenario 1) or excluding it (Scenario 2). The accepted demands are
thus optimally routed on the service network of the rail carrier. Two problems, corresponding to the two scenarios, have to be solved: the first including the current demand, the second excluding it. The expected revenues, thus, obtained are compared to make the decision of accepting or rejecting the current request.

In the model, we consider two kinds of flow:

* The accepted requests, that have to be routed through the network; this first type of flow corresponds to the already accepted demands that have to be satisfied, including or not the current demand being addressed at the time of the decision making;

* The future potential reservations, which are not to be physically routed, but are used to compute the total expected demand that might be accepted, given the remaining available capacity; in this way, the potential revenue associated with the future demand is estimated.

The system is, thus, able to accept or reject new demands to save capacity for potentially more profitable future demands. Figure 1 depicts the decision support system.

# 3 The container transportation system

We describe in this section, the service offer of the railway company as well as the way the services are operated. This model is inspired by the flow model defined in (Crainic et al. 2006). To keep the model tractable, we focus our study on a relatively small subset of the railway network, and on a relatively short period of time. The empty railcars rebalancing policy is therefore not addressed here. We also consider that the capacity of rail stations, in terms of available railcars and power engines, is large enough to serve the planned services.

## 3.1 Description

Let us consider a rail company working on a full-asset utilization basis to satisfy regular and irregular freight transportation demands for its clients. Let the oriented

<figure><img src="image_5.png" /><figcaption>Fig. 1 Decision making for the booking system</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 2 Physical network</figcaption></figure>

graph $G_N = (N, A_N)$ represent the physical network of the carrier. The set $N$ represents the rail stations. Each different arc $(i,j)$ connecting two different stations $i, j \in N$ belongs to the set $A_N$ if and only if the physical network allows a direct train to reach $j$ starting in $i$ without traversing any other intermediate station. A discretized time horizon $T$ is considered, the time unit being one or several hours, depending on the length of the horizon and the data granularity.

We illustrate the graph representation of the physical network in Fig. 2, where a linear network linking five cities is depicted.

In order to organize traffic flows, the company organizes transportation activities as scheduled services that are planned cyclically, with a certain frequency within the planning horizon and with a given itinerary on the physical network. Time dimension is introduced in the model via a space-time representation of the service network. On this network, a service is defined by its origin station and its departure time, its destination station and its arrival time, its itinerary within a fixed schedule and lower and upper bounds in terms of transportation capacity. Let $S$ denote the set of services.

Any transportation request may be served by one ore more services, from the origin station to the destination station of the demand.

Let $K$ be the set of demands, and let us consider for the time being that all the demands are known in advance and accepted by the booking system. We place ourselves in the static case, where the only decision to be made is the freight optimal routing on the network. The dynamic case, where a decision to accept or reject the current demand has to be made, will be treated in the Sect. 4.

When using the term *service*, the terms *leg* and *block* must be introduced as well. A *leg* is one arc in the set $A_N$, connecting two consecutive stations, in the physical network. Let $R(s)$ be the route of service $s$, in other words, the set of legs used by the service $s$. A *block* is a set of railcars traveling together within a given service, using
<figure><img src="image_7.png" /><figcaption>Fig. 3 Legs of a service</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 4 Blocks of a service</figcaption></figure>

one or more legs. Note that the origin and the destination of a block may be different from the origin and destination of the containers being transported on that block. Let $B(s)$ be the set of blocks associated with a service $s$ and let $B = \cup_{s \in S} B(s)$ be the set of all the blocks of the services offered by the rail company on a given network. Services and blocks are defined by the block plan of the transporter, on the long or medium term. The routing of the freight volume corresponding to one transportation demand will be given by the set of all blocks, belonging to one or several services, to which the demand will be assigned, if accepted.

We give an example of a service and its four legs in Fig. 3, and an example of the blocks defined for this service in Fig. 4. Figure 5 illustrates these blocks, represented on a space-time network.

In terms of mathematical notation, a given service $s \in S$ is characterized by:

* $o(s) \in N$: service origin on the physical network;

* $d(s) \in N$: service destination on the physical network;

* $R(s)$: the route used by the service;

* $t(s) \in T$: service departure time [from $o(s)$];

* $\theta(s) \in \mathbb{N}$: service duration [arrival at destination $d(s)$ takes place at $t(s) + \theta(s)$];

* $B(r, s) \subset B$ ($r \in R(s)$): set of blocks of service $s$ using leg $r$;

* $l(s)$: lower bound for service capacity, in TEUs; gives the minimum volume that is required for the service to operate;

* $u(s)$: upper bound for service capacity, in TEUs; gives the maximum volume the service is able to transport.
<figure><img src="image_9.png" /><figcaption>Fig. 5 Structure of the space-time network, in terms of blocks</figcaption></figure>

A block $b \in B$ is characterized by:

* $o(b) \in N$: block origin on the physical network;

* $d(b) \in N$: block destination on the physical network;

* $s(b) \in S$: service to which the block belongs;

* $t(b)$: departure time of the block from its origin $o(b)$;

* $\theta(b)$: block duration [arrival at destination $d(b)$ takes place at $t(b) + \theta(b)$];

* $l(b)$: lower bound for block capacity, in TEUs; gives the minimum volume that is required for the block to exist;

* $u(b)$: upper bound for block capacity, in TEUs; gives the maximum volume that can be transported by a block.

A transportation demand $k \in K$ is characterized by:

* $o(k) \in N$: demand origin on the physical network;

* $d(k) \in N$: demand destination on the physical network;

* vol(k): freight volume to be transported, in TEUs;

* $t_{\text{avl}}(k)$: freight availability time at the origin;

* $t_{\text{max}}(k)$: freight latest delivery time to the destination;

* $B(k) \subset B$: set of blocks that could be used to satisfy the demand; the characteristics of the demand [$t_{\text{avl}}(k)$, $t_{\text{max}}(k)$...] as well as other possible specific requirements and incompatibilities are considered when defining this set of blocks.

We also introduce the following additional notation, for the sake of simplicity, to denote the set of demands $k \in K$ that use the same block $b \in B(k)$: $B^{-1}(b) \subset K$ ($b \in B$).

We denote by $K_{fr} \subset K$ the set of demands belonging to the regular traffic on the network. Since these regular flows correspond to large volume demands, of regular clients, received and accepted long before the “current day”, the corresponding block assignment is decided on the long term and fixed in advance.

Freight containers are traveling on the network under two types of capacity constraints:
* Services capacities: the power engine in charge with a service $s \in S$ cannot pull more than a predefined freight volume $u(s)$; it cannot pull less than a predefined freight volume $l(s)$ either, otherwise the service is not profitable;

* Blocks capacities: a block $b$ cannot contain more than a predefined freight volume $u(b)$, nor can it contain less than a predefined freight volume $l(b)$, for practical operational reasons.

We make the assumption that the minimum load for blocks and services is ensured by the regular flows; moreover, in our model we consider the remaining capacity only after the subtraction of the regular traffic flows already allocated on the network. In other words, the remaining capacity is taken into account for the capacity constraints in the model: this capacity is thus between zero (when no capacity is left available for irregular demands) and an upper bound. For this reason, the lower bounds for block and service capacities are not to be used in the model we present; the remaining available capacities that are used by the irregular transportation demands are thus given by the values of the upper bounds of those capacities.

In the following section, we propose a mathematical model for the freight transportation problem on the space-time network. This model is defined in the context of a rail company functioning under the rules as described previously. Nevertheless, the proposed approach is robust enough to cope with different ways of working for other types of transportation companies, as long as the transportation network can be represented in terms of block plans on a space-time network.

## 3.2 Mathematical models

In this section, we introduce a mathematical formulation for the network flow optimization problem. The model is based on a space-time network $G = (V, A)$, constructed as follows.

The set of nodes $V$ is composed of three subsets: $V = V_{NT} \cup V_O \cup V_D$.

$V_{NT} = \{v_{i,t} | (i,t) \in N \times T\}$ is the backbone of the space-time network. Each physical location is replicated for all time periods 1, ..., $T$, thus forming the space-time pairs of the set $V_{NT}$. $V_O = \{u_k | k \in K\}$ and $V_D = \{w_k | k \in K\}$ represent the sets of origins and destinations of all requests (irrespective of time), respectively.

The set of all the arcs of the network, $A$, is made of five subsets: $A = A_B \cup A_{wtt} \cup A_O \cup A_D \cup A_R$.

$A_B$ stands for the set of blocks in the space-time network. To each block $b \in B$ is assigned an arc, coined $a(b)$, which connects its origin $[v_{o(b),t(b)}]$ and destination $[v_{d(b),t(b)+\theta(b)}]$ on the space-time network: $A_B = \{a(b) | b \in B\}$.

$A_{wtt}$ represents waiting times in stations: $A_{wtt} = \{(v_{i,t}, v_{i,t+1}) | (i,t) \in N \times T \setminus \{t_{max}\}\}$, where $t_{max}$ is the last time step of time horizon $T$.

The three other arc sets connect source and destination “dummy” nodes to the remaining of the graph. $A_O$ is composed of one arc per request $k \in K$, which connects the source $u_k$ to the node $(i,t)$ in $V_{NT}$ with $i = o(k)$ and $t = t_{avl}(k)$: $A_O = \{(u_k, v_{o(k),t_{avl}(k)}) | k \in K\}$. Equivalently, $A_D$ is the set of arcs connecting the last nodes of $V_{NT}$ allowing the completion of the transportation requests $k$ to their
<figure><img src="image_10.png" /><figcaption>Fig. 6 Space-time network including waiting arcs and dummy arcs.</figcaption></figure>

destinations $w_k \in V_D: A_D = \{(v_{d(k)}, t_{max}(k), w_k)|k \in K\}$ (this is equivalent to considering that even if some containers arrive at their destination before $t_{max}$, they wait at the destination yard until the maximum delivery time is reached, so that we have a single arc per request in $A_D$; otherwise, there could be several arcs at destination of $k$, for times $t \le t_{max}(k)$). Finally, $A_R$ contains a single arc $(w_k, u_k)$ per request $k \in K$, coined $a(k): A_R = \{a(k)|k \in K\}$. This latter set aims at ensuring flow balance throughout the graph $G$ and is solely introduced for the sake of simplifying the subsequent mathematical modeling.

Figure 6 exhibits a part of the graph $G$ obtained in the case of the example given in the previous section, considering a request for transportation of containers from Lille to Marseille within a maximum delivery time of 6 time units (TU).

We introduce the following decision variables. The variable $v(k, a)$ represents the volume of the request $k \in K$ delivered via the arc $a \in A$. Depending on the subset of $A$ to which arc $a$ belongs, the value of $v(k, a)$ can easily be interpreted. For example, in the case where $a \in A_B$, $v(k, a)$ indicates the quantity of merchandise to be loaded in the corresponding block; if $a \in A_{wtt}$, $v(k, a)$ is the quantity of merchandise that is going to wait in the corresponding station during the time interval represented by arc $a$; etc. Note that variables $v(k, a)$ are only defined when the use of arc $a$ for satisfying request $k$ is compatible with the time characteristics of the request. This set of arcs is then denoted $A_k$. Also, the set of ending nodes of arcs in $A_k$ is denoted $V_k$, so that flow issued from request $k$ will traverse the network through the subgraph $(V_k, A_k)$.

For the sake of simplicity, we also introduce additional variables $v(b)$, with the meaning that $v(b)$ is the cumulated load of block $b \in B$.

We denote $v$ as the vector defined by variables $v(k, a)$ and $v(b)$. The problem of delivering goods in the railway network can then be described as follows:
$$ \text{maximize } \phi(v) \qquad (1) $$

subject to

$$ v(b) = \sum_{k \in B^{-1}(b)} v(k, a(b)) \quad (b \in B), \qquad (2) $$

$$ v(b) \le u(b) \quad (b \in B), \qquad (3) $$

$$ \sum_{b \in B(r,s)} v(b) \le u(s) \quad (s \in S, r \in R(s)), \qquad (4) $$

$$ \sum_{a \in \delta^{+}(i) \cap A_k} v(k, a) - \sum_{a \in \delta^{-}(i) \cap A_k} v(k, a) = 0 \quad (k \in K, i \in V_k), \qquad (5) $$

$$ v(k, a(k)) = \text{vol}(k) \quad (k \in K), \qquad (6) $$

$$ v(k, a) \text{ fixed} \quad (k \in K_{fr}, a \in A_k), \qquad (7) $$

$$ v(k, a) \ge 0 \quad (k \in K, a \in A_k), \qquad (8) $$

$$ v(b) \ge 0 \quad (b \in B). \qquad (9) $$

The definition of the objective function $\phi$ depends on the objective pursued. Its definition in the context of the arrival of new requests will be discussed in Sect. 4. Constraints (2) define the load of a block as the sum of the quantities of goods assigned to this block. Inequalities (3) and (4) ensure block and service capacity constraints, respectively. Regarding services, this capacity is enforced for each leg (segment) composing the service. Constraints (5) stand for flow balance, for each request $k \in K$, where notations $\delta^{-}(i)$ and $\delta^{+}(i)$ denote ingoing and outgoing arcs of node $i$, respectively. Constraints (6) ensure that every request $k \in K$ is satisfied by imposing a flow $\text{vol}(k)$, equal to the volume of the demand, on the dummy arc $a(k) = (w_k, u_k)$ (that links backwards the sink to the source node). Finally, constraints (7) define the volumes associated with the regular flows in the network.

## 4 The booking and revenue management system

In this section, we present a booking and RM system devoted to the arrival of new requests. We describe the behavior of the system faced with the arrival of a new request $\tilde{k}$ at time $t_{\text{res}}(\tilde{k})$. Time $t_{\text{res}}(\tilde{k})$ is the time the client calls in to make a booking for a certain transportation demand $\tilde{k}$. This time is called the reservation time of the request.

The discretization of the time horizon involves relatively large periods between the time steps (e.g., the time period may be equal to six hours, twelve hours, etc.). Therefore, we assume that several booking requests may arrive simultaneously at each time step, although we assume that these requests are treated sequentially, in the order of their arrival (i.e., requests following request $\tilde{k}$ at time $t_{\text{res}}(\tilde{k})$ are not known while request $\tilde{k}$ is treated).
At time $t_{\text{res}}(\tilde{k})$, the booking system has to decide whether or not request $\tilde{k}$ should be accepted. Let us recall that in addition to its booking time, request $\tilde{k}$ is defined by its origin $o(\tilde{k})$, its destination $d(\tilde{k})$, a volume vol($\tilde{k}$), times $t_{\text{avl}}(\tilde{k})$ and $t_{\text{max}}(\tilde{k})$ (see Sect. 3). In view of its characteristics $o(\tilde{k})$, $d(\tilde{k})$, $t_{\text{res}}(\tilde{k})$, $t_{\text{avl}}(\tilde{k})$ and $t_{\text{max}}(\tilde{k})$, the request is assigned to a fare class, with a known unit price denoted $f(\tilde{k})$. Thus, the revenue obtained in case request $\tilde{k}$ is accepted is vol($\tilde{k}$) × $f(\tilde{k})$. No request can be partially accepted. Also, the booking system is designed for requests of limited amount, and unit prices are assumed to be independent of the total amount of goods involved in the request.

A new request is accepted under two conditions:

* A feasibility condition, imposing that a solution exists including the new request plus the formerly accepted requests and regular flows.

* An economic condition, implying that the expected revenue if the request accepted is at least equal to the expected revenue in case of rejection; note that the computation of these expected revenues requires that some forecasts of the future demands should be available in the system.

When the request is rejected, we assume that the customer leaves the system. In particular, we do not treat the case where the same customer reformulates his/her request to fit in another fare class.

To compute the expected revenue for a booking request $\tilde{k}$, we have to look at the possible flow interactions between this request and potential future requests that might use the same services and blocks of the transportation network. Let us define $\mathcal{L}(\tilde{k})$ as the set of all possible future booking request configurations with direct interactions with the request $\tilde{k}$. Each potential request configuration $l \in \mathcal{L}(\tilde{k})$ is characterized by an origin-destination pair $(o(l), d(l))$, an availability time $t_{\text{avl}}(l)$, a latest delivery time $t_{\text{max}}(l)$ and a booking time $t_{\text{res}}(l)$. By direct interactions, we mean that the time intervals on which future demands and the new booking demand $\tilde{k}$ are routed on the space-time network overlap. Mathematically, we define the set of future requests $\mathcal{L}(\tilde{k})$ as made up of requests of type $l$ satisfying simultaneously the two time conditions:

* $t_{\text{res}}(l) > t_{\text{res}}(\tilde{k})$,

* $[t_{\text{avl}}(l), t_{\text{max}}(l)] \cap [t_{\text{avl}}(\tilde{k}), t_{\text{max}}(\tilde{k})] \neq \emptyset$.

The unit price corresponding to the fare class to which a request configuration $l$ belongs is denoted $f(l)$. Note that $\mathcal{L}(\tilde{k})$ is possibly a very large set as it enumerates all the feasible combinations of the parameters that define a request. However, not all of these requests will become realizations. Each request type $l \in \mathcal{L}(\tilde{k})$ has a probability distribution associated with it. This is given in terms of possible values of the volume of that request. These values are integer and bounded, as they are given in terms of number of twenty feet containers (TEUs). Therefore, we use a discrete probability distribution function, denoted $P_l(x)$, to characterize the random integer variable corresponding to the volume $x$ of the potential request type $l$. A volume $x=0$ indicates that the request will not appear.
Let us finally introduce decision variables vol(l), l ∈ L(˜k), aimed at “booking” some capacity (delivery routes) in the network for potential future requests. More precisely, vol(l) is a decision variable that gives the maximum volume available to serve a request of type l, compatible with the capacity constraints on blocks and services of the network.

Then, given a vector v [including variables vol(l)], the expected revenue for future requests can be computed as:

$$
\phi(v) = \sum_{l \in \mathcal{L}(\tilde{k})} f(l) \sum_{x=0}^{\text{vol}(l)} x P_l(x). \quad (10)
$$

Note that when the volume x exceeds vol(l) no revenue is obtained as requests
cannot be partially accepted.

We denote by K(˜k) the set of all requests accepted before request ˜k, including the regular flows.

Model REJECT(˜k) described below allows to evaluate the expected maximum
revenue at time t<sub>res</sub>(˜k), if request ˜k is rejected:

$$
\text{maximize} \quad \phi(v) \tag{11}
$$

subject to

$$
v(b) = \sum_{k \in B^{-1}(b)} v(k, a(b)) + \sum_{l \in B_{\mathcal{L}(\tilde{k})}^{-1}(b)} v(l, a(b)) \quad (b \in B), \quad (12)
$$

$$
v(b) \le u(b) \quad (b \in B), \tag{13}
$$

$$
\sum_{b \in B(r,s)} v(b) \le u(s) \quad (s \in S, r \in R(s)), \qquad (14)
$$

$$
\sum_{a \in \delta^{+}(i) \cap A_k} v(k, a) - \sum_{a \in \delta^{-}(i) \cap A_k} v(k, a) = 0 \quad (k \in K(\tilde{k}), i \in V_k), \quad (15)
$$

$$
\sum_{a \in \delta^{+}(i) \cap A_l} v(l, a) - \sum_{a \in \delta^{-}(i) \cap A_l} v(l, a) = 0 \quad (l \in \mathcal{L}(\tilde{k}), i \in V_l), \qquad (16)
$$

$$
v(k, a(k)) = \mathrm{vol}(k) \quad (k \in K(\tilde{k})), \tag{17}
$$

$$
v(l, a(l)) = \mathrm{vol}(l) \quad (l \in \mathcal{L}(\tilde{k})), \tag{18}
$$

$$
v(k, a) \text{ fixed} \quad (k \in K(\tilde{k}), a \in A_k), \tag{19}
$$

$$
v(l, a) \ge 0 \quad (l \in \mathcal{L}(\tilde{k}), a \in A_l), \tag{20}
$$

$$
\mathrm{vol}(l) \ge 0 \quad (l \in \mathcal{L}(\tilde{k})), \qquad (21)
$$

$$
v(b) \ge 0 \quad (b \in B). \tag{22}
$$
where $B_{\mathcal{L}(\|\|)}^{-1}(b)$ is the set of requests of $\mathcal{L}(\tilde{k})$ that are authorized to use block $b$ and $(V_l, A_l)$ is the subgraph within which the request of type $l$ can be delivered (sub-graph containing all the blocks that request $l$ is authorized to use).

Variables $v(l, a(b))$ indicate the volume “booked” on block $b$ for a potential request of type $l$. Each variable $v(l, a(l))$ associated with a request of type $l$ gives the total volume vol($l$) of this request that has to be transported on the network, on the dummy arc $a(l)$, to ensure demand satisfaction [constraints (18)]. Other constraints replicate and adapt constraints of model (1–9). In particular, constraints (12) include the volumes associated with potential requests $l$ when computing arc flows; they are thus considered in the capacity constraints (13) and (14).

Let us call $v_{REJECT}$ an optimal solution of model REJECT($\tilde{k}$).

Model ACCEPT($\tilde{k}$), maximizing the expected revenue at time $t_{res}(\tilde{k})$ under the assumption that request $\tilde{k}$ will be accepted, can be stated:

$$ \text{maximize} \quad \phi(v) \qquad (23) $$

subject to constraints (13, 14), (16), (18–22) as before, and the following ones:

$$ v(b) = \sum_{k \in B^{-1}(b)} v(k, a(b)) + \sum_{l \in B_{\mathcal{L}(\|\|)}^{-1}(b)} v(l, a(b)) \quad (b \in B \setminus B_{\tilde{k}}), \qquad (24) $$

$$ v(b) = \sum_{k \in B^{-1}(b) \cup \{\tilde{k}\}} v(k, a(b)) + \sum_{l \in B_{\mathcal{L}(\|\|)}^{-1}(b)} v(l, a(b)) \quad (b \in B_{\tilde{k}}), \qquad (25) $$

$$ \sum_{a \in \delta^{+}(i) \cap A_k} v(k, a) - \sum_{a \in \delta^{-}(i) \cap A_k} v(k, a) = 0 \quad (k \in K(\tilde{k}) \cup \{\tilde{k}\}, i \in V_k), \qquad (26) $$

$$ v(k, a(k)) = vol(k) \quad (k \in K(\tilde{k}) \cup \{\tilde{k}\}), \qquad (27) $$

$$ v(\tilde{k}, a) \ge 0 \quad (a \in A_k). \qquad (28) $$

Compared with model REJECT($\tilde{k}$), the sole modification is that the delivery of an amount vol($\tilde{k}$) of goods for request $\tilde{k}$ is imposed, which is equivalent to including request $\tilde{k}$ in $K$. Let us call $v_{ACCEPT}$ an optimal solution of this model.

Demand $\tilde{k}$ is then finally accepted if:

$$ \phi(v_{ACCEPT}) + vol(\tilde{k}) \times f(\tilde{k}) \ge \phi(v_{REJECT}) \qquad (29) $$

In order to efficiently solve the REJECT and ACCEPT optimization problems, we propose a linearization of the objective function, as follows. We introduce, for each request $l$, additional binary decision variables $y_{lj}$, where $j$ are integer values such that $1 \le j \le VMAX(l)$ and $VMAX(l)$ is the smallest integer such that $P_l(j) = 0$ for $j \ge VMAX(l) + 1$. Variable $y_{lj}$ is then equal to 1 if a volume $j$ is booked for request $l$, 0 otherwise.

The decision variables vol($l$) are given by:

$$ \text{vol}(l) = \sum_{1 \le j \le VMAX(l)} j y_{lj} \quad (l \in \mathcal{L}(\tilde{k})), \qquad (30) $$
$$ \sum_{1 \le j \le \text{VMAX}(l)} y_{lj} \le 1 \quad (l \in \mathcal{L}(\tilde{k})), \qquad (31) $$

$$ y_{lj} \in \{0, 1\} \quad (l \in \mathcal{L}(\tilde{k}), 1 \le j \le \text{VMAX}(l)). \qquad (32) $$

Constraints (31) ensure that only one variable $y_{lj}$ is fixed to 1. The expected revenue $\phi(v)$ is then given by:

$$ \phi(v) = \sum_{l \in \mathcal{L}(\tilde{k})} f(l) \sum_{x=0}^{\text{vol}(l)} x P_l(x) = \sum_{l \in \mathcal{L}(\tilde{k})} f(l) \sum_{1 \le j \le \text{VMAX}(l)} \sum_{x=0}^{j} (x P_l(x)) y_{lj} \qquad (33) $$

or

$$ \phi(v) = \sum_{l \in \mathcal{L}(\tilde{k})} \sum_{1 \le j \le \text{VMAX}(l)} \left( f(l) \sum_{x=0}^{j} x P_l(x) \right) y_{lj}. \qquad (34) $$

Due to this linearization (or to the initially non-linear objective function), none of the two problems to be solved to accept/reject a new request is a pure flow problem. Binary variables $y_{lj}$ complicate the solution method and prevent from solving large instances in reasonable computing times. Ad hoc or heuristic algorithms could be proposed to tackle this difficulty, by partitioning the network and exactly solving each subproblem separately, or by stopping the exploration of the search tree when a satisfactory solution is found, for example.

## 5 Simulation and numerical results

We validate the proposed RM models through numerical simulations performed using CPLEX 11.2 solver on a computer running under Linux 64-bit and with an Intel Xeon 5160 CPU, 3GHz, 16GB. We use two types of networks (linear and star) and different scenarios for the demand profile. We keep the networks and time horizons relatively small to allow acceptable computing time for solutions of the mathematical models (<1 min). Again, we leave more sophisticated solution methods for future research. The purpose in these experiments is to give some insights on the benefits that could be obtained with the proposed booking and RM system.

We design the linear and star networks as follows:

**Linear network.** We introduce four consecutive cities, A, B, C, D. We define two cyclic services $s_1$ and $s_2$, connecting A to C and C to D, respectively. We introduce four blocks. Service $s_1$ is composed of three blocks: $b_1$, linking A to B, $b_2$, linking B to C and $b_3$, linking A to C; Service $s_2$ is composed of a single block: $b_4$, linking C to D. In this network, we limit requests to three origin-destination pairs: AC, AD and BD.

**Star network.** The star network links four cities, A, B, C, D through a single hub, H; no direct link exists between the four cities; for example, to go from A to B, the two legs AH and HB are consecutively used. We introduce three services and
four blocks in this network. Service $s_1$ connects A to B and is composed of two blocks, $b_1$ (from A to H) and $b_2$ (from H to B). Service $s_2$ connects H to C, with one block $b_3$ (from H to C). Service $s_3$ connects H to D, with one block $b_4$ (from H to D). In this network, we limit requests to three origin-destination pairs: AB, AC and AD.

Services and blocks are chosen with respect to the interactions between different flows on the space-time network. We generate bottlenecks in the test instances to study the effects of the RM models on congested parts of the network. The limited size of the physical/service network is consistent with the fact that, in practice these congested parts can be easily identified and should be relatively small.

Note that in all scenarios the residual capacity is scarce with respect to the volume of irregular demands arriving in the system, thus some of the demands have to be rejected.

Fare classes constitute a critical set of parameters for the simulator. We define four different fare classes as a combination of two possible categories (short or long) for the booking anticipation time $w$ and two possible categories (short or long) for the maximum delivery time $\Delta$ (see Fig. 7). The highest fare class corresponds to short booking anticipation and short delivery time, the second highest is the one with long booking anticipation and short delivery time, short booking anticipation and long delivery time comes on the third position and finally the lowest fare class corresponds to long booking anticipation and long delivery time. Each demand is associated with its corresponding fare class based on these two time characteristics. Relative values (price ratios) are used in the test instances to illustrate the price differences between the four fare classes.

We design and simulate the decision-making process as follows. The requests arrive to the booking and RM system and are treated sequentially, in the order of their arrival. The simulation horizon is discrete and made up of 100 time units (TUs). A single booking request $\tilde{k}$ is generated at each time unit of the simulation horizon; the booking time is thus fixed [$t_{res}(\tilde{k})$]. The origin-destination pair characterizing the request is uniformly generated using the possible values defined. Uniform distributions are also used to generate the value (in TUs) of the booking anticipation (either short or long) and the value (in TUs) for the delivery time (either short or long). This implies that the four fare classes resulting from the combination

<figure><img src="image_11.png" /><figcaption>**Fig. 7** Anticipation $w$ and delivery time $\Delta$ used to compute the fare class of a demand</figcaption></figure>
of the values of these two parameters are equally likely (the parameters are uniformly generated, one out of two possible values each).

Demand $X$ is represented as a discrete random variable varying between 0 and a maximum volume size $VMAX = 5$ (in TEUs). Size zero is an indication that the demand does not come. The discrete probability distribution of a request configuration type $l$ is defined as follows: $P_l(X = 0) = 0.5$ and $P_l(X = x) = 0.1$ for $x \in \{1, 2, ..., 5\}$.

For each arriving booking request $\tilde{k}$, an accept/reject decision has to be made. As explained in Sect. 4, this decision relies on the estimation of the expected revenue computed based on the future possible requests appearing between $t_{\text{res}}(\tilde{k})$ and $t_{\text{max}}(\tilde{k})$. On this time interval, we apply the same process as for the arriving requests $\tilde{k}$, using the same values of parameters, at each time unit, to generate potential future request configurations. The characteristics origin-destination pair $(o(l), d(l))$, availability time $t_{\text{avl}}(l)$, latest delivery time $t_{\text{max}}(l)$ of such a future request configuration are then checked against the conditions that direct interactions with $\tilde{k}$ are generated on the space-time network. Finally, the expected revenue is computed as indicated by $\phi(v)$ in Eq. (34), using the same volume probability distributions as when generating the new requests. For all other configuration types $l$ we define the volume probability distribution given for a single value, equal to zero: $P_l(X = 0) = 1$. By doing so we limit the size of the optimization problems that are solved. Furthermore, we anticipate the fact that in practice $\mathcal{L}$ could be very large and it might be necessary to only consider a limited subset of configurations.

In the experiments we test the application of the RM policy (RM2), described in Sect. 4. We also present and analyze results of a less powerful policy, when only the optimization model ACCEPT($\tilde{k}$) is applied (RM1). RM1 policy applies the acceptation rule based on the feasibility of the demand only; nevertheless, the routing of the demand (in case of acceptation) is done in a predictive manner, by taking into account the potential influence of future high-revenue demands, for which capacity should be reserved on the network.

We test these two RM policies against a traditional FCFS policy. FCFS refers here to a decision policy that simply treats the demands $\tilde{k}$, one by one, in the order of their arrival time [$t_{\text{res}}(\tilde{k})$]. A demand is accepted (irrespective of its profitability) if it is feasible. It is rejected otherwise. The feasibility is computed in terms of available capacity of the different blocks of the itinerary, and time delivery constraints, considering the remaining capacity on the network, at the moment when the booking request arrives in the system. Mathematically, a feasible solution is found by applying model ACCEPT($\tilde{k}$) with $\mathcal{L}(\tilde{k})$ set to $\emptyset$.

We also compare the results of applying the RM policies with a deterministic optimal solution policy (DET), i.e., assuming perfect information. It consists in considering future demand information completely known in advance, thus the accept/reject decisions are made in a pure optimal way (no uncertainty exists with respect to the future). This policy constitutes an upper bound for the performances of the policies tested (FCFS, RM1 and RM2).
As the demands' characteristics are randomly generated, we perform 20 replications for each proposed scenario and compute the average values of the performance indicators. Tables 1, 2, 3 and 4 summarize these numerical results.

We perform sensitivity analysis with respect to (1) Fare classes prices and (2) Demand estimation accuracy.

1. Fare classes price ratios. Tables 1 and 3: the reference scenario is based on 1:2:4:6 price ratios. This notation means that the highest fare class is characterized by a price six times the price of the lowest fare class (6:1). The subsequent fare class has a price four times the lowest price (4:1). The following (the third class) is associated with a price only twice the lowest one (2:1).

2. Demand estimation accuracy. Tables 2 and 4: the reference scenario is based on a parameter, called demand coefficient, equal to one; the meaning of this parameter is the ratio between the average interarrival time of booking demands $\bar{k}$ and the average interarrival time of future demand configurations $l$; when equal to one, demand estimation accuracy is considered perfect, since the arrival rate for the two processes is the same. When the parameter has values <1 (demand coefficient <1) the future demand is underestimated. Indeed, if the average interarrival time of demands $\bar{k}$ is less than the one of future demands, we have, on average, more booking demands than what was expected (we simulate a demand underestimation situation). On the contrary, when the parameter is greater than one (demand coefficient > 1) we simulate a demand overestimation situation, based on the same reasoning: the interarrival time of demands $\bar{k}$ is now greater than the one of future demand configurations $l$, so we have, on average, less demands $\bar{k}$ than what was expected.

Corresponding results are presented for both the linear network (Tables 1,2) and star network (Tables 3, 4).

In each table, the column heading "Policy" refers to the type of allocation policy performed, "Tot rejected" denotes the total number of rejected demands (in percents), "RM rejected" gives the number of demands rejected due to the revenue maximization criterion (29), "Income/Dem" denotes the average revenue per accepted demand (in monetary unit). The last column, "Gain/FCFS" refers to the total revenue improvement of the allocation policy with respect to FCFS.

As a general rule, the RM2 policy significantly increases the total revenue when compared to the FCFS. The revenue increase obtained by the RM1 policy is not as pronounced. As we have also compared our results to the DET policy, we conclude that the results obtained are relatively good. The gap between the RM2 improvement and the deterministic (best) solution is, for instance, of the order of 55% for a scenario dealing with only two different fare classes and with a high price ratio between them (1:6:6:6).

The number of rejected demands in the deterministic case is relatively high, which shows that in all scenarios the residual capacity is scarce with respect to the transportation demand the system has to cope with.
<table><caption>**Table 1** Instances with different price ratios—linear network</caption><thead><tr><th>Price ratio</th><th>Policy</th><th>Tot rejected</th><th>RM rejected</th><th>Income/demand</th><th>Gain/FCFS</th></tr></thead><tbody><tr><td rowspan="4">1:2:4:6</td><td>FCFS</td><td>38.5</td><td>0</td><td>7.06</td><td>1.00</td></tr><tr><td>RM1</td><td>38.2</td><td>0</td><td>7.26</td><td>1.03</td></tr><tr><td>RM2</td><td>42.9</td><td>10.7</td><td>8.45</td><td>1.11</td></tr><tr><td>DET</td><td>34.1</td><td>0</td><td>11.30</td><td>1.71</td></tr><tr><td rowspan="4">1:2:2:6</td><td>FCFS</td><td>38.0</td><td>0</td><td>5.57</td><td>1.00</td></tr><tr><td>RM1</td><td>38.8</td><td>0</td><td>5.68</td><td>1.01</td></tr><tr><td>RM2</td><td>41.3</td><td>4.7</td><td>5.92</td><td>1.01</td></tr><tr><td>DET</td><td>33.9</td><td>0</td><td>8.85</td><td>1.69</td></tr><tr><td rowspan="4">1:3:3:6</td><td>FCFS</td><td>38.5</td><td>0</td><td>6.69</td><td>1.00</td></tr><tr><td>RM1</td><td>38.0</td><td>0</td><td>6.70</td><td>1.01</td></tr><tr><td>RM2</td><td>41.0</td><td>4.9</td><td>7.33</td><td>1.05</td></tr><tr><td>DET</td><td>35.0</td><td>0</td><td>10.80</td><td>1.70</td></tr><tr><td rowspan="4">1:4:4:6</td><td>FCFS</td><td>38.5</td><td>0</td><td>8.04</td><td>1.00</td></tr><tr><td>RM1</td><td>37.7</td><td>0</td><td>8.01</td><td>1.01</td></tr><tr><td>RM2</td><td>42.3</td><td>10.5</td><td>9.56</td><td>1.12</td></tr><tr><td>DET</td><td>35.1</td><td>0</td><td>12.42</td><td>1.63</td></tr><tr><td rowspan="4">1:5:5:6</td><td>FCFS</td><td>38.0</td><td>0</td><td>9.64</td><td>1.00</td></tr><tr><td>RM1</td><td>38.0</td><td>0</td><td>9.73</td><td>1.01</td></tr><tr><td>RM2</td><td>40.8</td><td>12.0</td><td>11.85</td><td>1.17</td></tr><tr><td>DET</td><td>34.6</td><td>0</td><td>13.91</td><td>1.52</td></tr><tr><td rowspan="4">1:6:6:6</td><td>FCFS</td><td>38.0</td><td>0</td><td>10.99</td><td>1.00</td></tr><tr><td>RM1</td><td>37.1</td><td>0</td><td>11.10</td><td>1.02</td></tr><tr><td>RM2</td><td>40.3</td><td>12.8</td><td>13.55</td><td>1.19</td></tr><tr><td>DET</td><td>35.0</td><td>0</td><td>15.71</td><td>1.50</td></tr><tr><td rowspan="4">1:2:4:8</td><td>FCFS</td><td>38.5</td><td>0</td><td>7.62</td><td>1.00</td></tr><tr><td>RM1</td><td>37.9</td><td>0</td><td>7.72</td><td>1.02</td></tr><tr><td>RM2</td><td>44.2</td><td>14.4</td><td>9.89</td><td>1.18</td></tr><tr><td>DET</td><td>33.9</td><td>0</td><td>13.15</td><td>1.86</td></tr><tr><td rowspan="4">1:2:4:10</td><td>FCFS</td><td>39.9</td><td>0</td><td>7.94</td><td>1.00</td></tr><tr><td>RM1</td><td>39.7</td><td>0</td><td>8.62</td><td>1.09</td></tr><tr><td>RM2</td><td>46.1</td><td>17.1</td><td>10.97</td><td>1.24</td></tr><tr><td>DET</td><td>34.8</td><td>0</td><td>14.25</td><td>1.95</td></tr></tbody></table>

For the price-based scenarios, we have varied the number of different fares, as well as the ratio between the different fares two by two. The revenue improvement obtained is, as expected, higher as the ratio between the fare classes grows. For the linear network this gain may go up to 24 % and the for the star network, up to 30 %.

For the demand based scenarios, we note that in case of overestimation the net gain obtained by applying RM policies is limited (not more than 10 % of revenue improvement). On the opposite, the underestimation situation is clearly well suited for taking advantage from applying RM strategies. The improvement obtained is up
<table><caption>**Table 2** Instances with under and over estimation of the demand—linear network</caption><thead><tr><th>Demand coeff</th><th>Policy</th><th>Tot rejected</th><th>RM rejected</th><th>Income/demand</th><th>Gain/FCFS</th></tr></thead><tbody><tr><td rowspan="4">0.25</td><td>FCFS</td><td>70.9</td><td>0</td><td>5.63</td><td>1.00</td></tr><tr><td>RM1</td><td>71.0</td><td>0</td><td>5.89</td><td>1.04</td></tr><tr><td>RM2</td><td>72.5</td><td>8.3</td><td>7.14</td><td>1.20</td></tr><tr><td>DET</td><td>72.2</td><td>0</td><td>13.15</td><td>2.23</td></tr><tr><td rowspan="4">0.50</td><td>FCFS</td><td>58.8</td><td>0</td><td>5.76</td><td>1.00</td></tr><tr><td>RM1</td><td>58.4</td><td>0</td><td>5.99</td><td>1.05</td></tr><tr><td>RM2</td><td>60.4</td><td>10.4</td><td>7.41</td><td>1.24</td></tr><tr><td>DET</td><td>59.5</td><td>0</td><td>12.92</td><td>2.21</td></tr><tr><td rowspan="4">1.00</td><td>FCFS</td><td>38.5</td><td>0</td><td>7.06</td><td>1.00</td></tr><tr><td>RM1</td><td>38.2</td><td>0</td><td>7.26</td><td>1.03</td></tr><tr><td>RM2</td><td>42.9</td><td>10.7</td><td>8.45</td><td>1.11</td></tr><tr><td>DET</td><td>34.1</td><td>0</td><td>11.30</td><td>1.71</td></tr><tr><td rowspan="4">1.50</td><td>FCFS</td><td>23.2</td><td>0</td><td>7.80</td><td>1.00</td></tr><tr><td>RM1</td><td>23.8</td><td>0</td><td>8.03</td><td>1.02</td></tr><tr><td>RM2</td><td>30.2</td><td>11.7</td><td>9.01</td><td>1.05</td></tr><tr><td>DET</td><td>12.0</td><td>0</td><td>9.90</td><td>1.46</td></tr><tr><td rowspan="4">1.75</td><td>FCFS</td><td>24.5</td><td>0</td><td>7.87</td><td>1.00</td></tr><tr><td>RM1</td><td>22.9</td><td>0</td><td>8.08</td><td>1.05</td></tr><tr><td>RM2</td><td>32.4</td><td>13.0</td><td>9.27</td><td>1.06</td></tr><tr><td>DET</td><td>13.6</td><td>0</td><td>9.39</td><td>1.36</td></tr></tbody></table>

to 24 % for the linear network and up to 33 % for the star network, which is a very significant gain at the level of the annual turn-over of the transportation company.

The results obtained by applying RM1 give a good indication about the potential benefits of using a “predictive routing” policy instead of a FCFS traditional approach. The relative revenue increase is of the order of 2 or 3 %. Even if they seem low, these values are not negligible when talking about transportation companies making benefits of the order of several million dollars or euros. Moreover, when considering the average revenue per demand, we notice a consistent increase of the values compared with the ones of the FCFS strategy. This confirms that the discrimination policies proposed are effective and allow a better utilization of resources on the network. Numerical results obtained so far validate the proposed RM approach. The decision-making process, with dynamic booking and capacity allocation, in the light of future demand forecasts, yields high performances of the transportation system.

## 6 Concluding remarks and further work

In this paper, we propose a new approach, inspired by bid-price capacity control mechanisms, for optimizing expected revenue on a rail transportation service
<table><caption>**Table 3** Instances with different price ratios—star network</caption><thead><tr><th>Price ratio</th><th>Policy</th><th>Tot rejected</th><th>RM rejected</th><th>Income/demand</th><th>Gain/FCFS</th></tr></thead><tbody><tr><td rowspan="4">1:2:4:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>6.85</td><td>1.00</td></tr><tr><td>RM1</td><td>46.2</td><td>0</td><td>6.98</td><td>1.03</td></tr><tr><td>RM2</td><td>50.8</td><td>14.2</td><td>8.98</td><td>1.21</td></tr><tr><td>DET</td><td>42.7</td><td>0</td><td>12.02</td><td>1.88</td></tr><tr><td rowspan="4">1:2:2:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>4.68</td><td>1.00</td></tr><tr><td>RM1</td><td>47.0</td><td>0</td><td>4.91</td><td>1.04</td></tr><tr><td>RM2</td><td>47.1</td><td>0.3</td><td>4.92</td><td>1.04</td></tr><tr><td>DET</td><td>42.3</td><td>0</td><td>9.44</td><td>2.17</td></tr><tr><td rowspan="4">1:3:3:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>5.99</td><td>1.00</td></tr><tr><td>RM1</td><td>47.2</td><td>0</td><td>6.08</td><td>1.01</td></tr><tr><td>RM2</td><td>50.8</td><td>7.2</td><td>6.98</td><td>1.07</td></tr><tr><td>DET</td><td>42.3</td><td>0</td><td>10.99</td><td>1.98</td></tr><tr><td rowspan="4">1:4:4:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>7.30</td><td>1.00</td></tr><tr><td>RM1</td><td>46.4</td><td>0</td><td>7.47</td><td>1.03</td></tr><tr><td>RM2</td><td>50.0</td><td>14.2</td><td>9.79</td><td>1.26</td></tr><tr><td>DET</td><td>42.5</td><td>0</td><td>12.58</td><td>1.86</td></tr><tr><td rowspan="4">1:5:5:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>8.60</td><td>1.00</td></tr><tr><td>RM1</td><td>46.8</td><td>0</td><td>8.66</td><td>1.01</td></tr><tr><td>RM2</td><td>52.1</td><td>15.4</td><td>11.81</td><td>1.23</td></tr><tr><td>DET</td><td>42.5</td><td>0</td><td>14.15</td><td>1.77</td></tr><tr><td rowspan="4">1:6:6:6</td><td>FCFS</td><td>46.6</td><td>0</td><td>9.91</td><td>1.00</td></tr><tr><td>RM1</td><td>45.8</td><td>0</td><td>10.01</td><td>1.02</td></tr><tr><td>RM2</td><td>50.9</td><td>16.1</td><td>13.99</td><td>1.30</td></tr><tr><td>DET</td><td>41.9</td><td>0</td><td>15.55</td><td>1.71</td></tr><tr><td rowspan="4">1:2:4:8</td><td>FCFS</td><td>46.6</td><td>0</td><td>7.12</td><td>1.00</td></tr><tr><td>RM1</td><td>47.1</td><td>0</td><td>7.33</td><td>1.02</td></tr><tr><td>RM2</td><td>51.2</td><td>14.7</td><td>9.40</td><td>1.21</td></tr><tr><td>DET</td><td>42.7</td><td>0</td><td>14.08</td><td>2.12</td></tr><tr><td rowspan="4">1:2:4:10</td><td>FCFS</td><td>46.6</td><td>0</td><td>7.40</td><td>1.00</td></tr><tr><td>RM1</td><td>46.5</td><td>0</td><td>7.60</td><td>1.03</td></tr><tr><td>RM2</td><td>51.7</td><td>13.9</td><td>9.98</td><td>1.22</td></tr><tr><td>DET</td><td>42.6</td><td>0</td><td>16.11</td><td>2.34</td></tr></tbody></table>

network. RM has already been used as an important mechanism for transportation companies (mainly airlines) to best serve their clients while optimally assigning the available capacities to the demand. Nevertheless, this type of mechanism has been much less studied for solving rail container transportation problems. Indeed, in rail transportation, many exogenous constraints appear, whereas it is not the case with airline transportation. In this research work, we propose a load acceptance management system to dynamically accept or reject transportation demands in favor
<table><caption>**Table 4** Instances with under and over estimation of the demand—star network</caption><thead><tr><th>Demand coeff</th><th>Policy</th><th>Tot rejected</th><th>RM rejected</th><th>Income/demand</th><th>Gain/FCFS</th></tr></thead><tbody><tr><td rowspan="4">0.25</td><td>FCFS</td><td>70.8</td><td>0</td><td>5.42</td><td>1.00</td></tr><tr><td>RM1</td><td>70.5</td><td>0</td><td>5.56</td><td>1.04</td></tr><tr><td>RM2</td><td>72.2</td><td>12.7</td><td>7.24</td><td>1.27</td></tr><tr><td>DET</td><td>73.7</td><td>0</td><td>13.00</td><td>2.16</td></tr><tr><td rowspan="4">0.50</td><td>FCFS</td><td>62.0</td><td>0</td><td>5.42</td><td>1.00</td></tr><tr><td>RM1</td><td>61.7</td><td>0</td><td>5.56</td><td>1.04</td></tr><tr><td>RM2</td><td>64.8</td><td>14.6</td><td>7.24</td><td>1.33</td></tr><tr><td>DET</td><td>63.6</td><td>0</td><td>13.00</td><td>2.25</td></tr><tr><td rowspan="4">1.00</td><td>FCFS</td><td>46.6</td><td>0</td><td>6.85</td><td>1.00</td></tr><tr><td>RM1</td><td>46.2</td><td>0</td><td>6.98</td><td>1.03</td></tr><tr><td>RM2</td><td>50.8</td><td>14.2</td><td>8.98</td><td>1.21</td></tr><tr><td>DET</td><td>42.7</td><td>0</td><td>12.02</td><td>1.88</td></tr><tr><td rowspan="4">1.50</td><td>FCFS</td><td>34.5</td><td>0</td><td>7.66</td><td>1.00</td></tr><tr><td>RM1</td><td>34.5</td><td>0</td><td>7.81</td><td>1.02</td></tr><tr><td>RM2</td><td>40.0</td><td>13.5</td><td>9.17</td><td>1.10</td></tr><tr><td>DET</td><td>23.2</td><td>0</td><td>10.62</td><td>1.63</td></tr><tr><td rowspan="4">1.75</td><td>FCFS</td><td>34.6</td><td>0</td><td>7.62</td><td>1.00</td></tr><tr><td>RM1</td><td>36.1</td><td>0</td><td>7.50</td><td>0.96</td></tr><tr><td>RM2</td><td>42.0</td><td>13.8</td><td>9.09</td><td>1.06</td></tr><tr><td>DET</td><td>17.6</td><td>0</td><td>9.25</td><td>1.53</td></tr></tbody></table>

of some future forecasted transportation requests with higher potential profit. The objective function to be maximized is given by the expected revenue of the company. We give a probabilistic mathematical model taking into account network interactions. The proposed decision support system is validated through numerical simulations. We present results showing that significantly improved revenues may be obtained by applying the proposed RM mechanisms and policies.

In future work, we plan to study some other variants of the acceptance conditions. We could, for instance, introduce some flexibility in the offered services, by considering penalties to be applied to the provider in case of delivery delays. Unexpected modifications in the regular flows could also be a source of uncertainty to be integrated in the model.

Finally, RM has been proposed initially as a mechanism for airline companies to adapt their services to a competitive market. It would be also interesting to study the impacts of applying RM techniques in a rail container transportation competitive market, with several companies operating simultaneously on the same physical network.

**Acknowledgments** The present research work was partly financed by the GDR RO of the CNRS. The authors gratefully acknowledge the support of this institution. The authors also thank the reviewers for their accurate observations and suggestions that helped improving the quality of this paper.
References

Armstrong A, Meissner J (2010) Railway revenue management: overview and models. Working paper (available at http://www.meiss.com), Lancaster University Management School, 2010

Belobaba P (1987) Airline yield management: an overview of seat inventory control. Transp Sci 21(2):63–73

Bharill R, Rangaraj N (2008) Revenue management in railway operations: a study of the rajdhani express. Indian Railw Transp Res Part A 42(9):1195–1207

Cacchiani V, Caprara A, Toth P (2010) Scheduling extra freight trains on railways networks. Transp Res Part B 44B(2):215–231

Capiez A (2003) Yield management. Hermes Science, Paris

Chiang WC, Chen JCH, Xu X (2007) An overview of research on revenue management: current issues and future research. Int J Revenue Manag 1(1):97–128

Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp Sci 32(4):380–404

Crainic TG (2009) Service design models for rail intermodal transportation. Innov Distrib Logist Lect Notes Econ Math Syst 619:53–67

Crainic TG, Bilegan IC, Gendreau M (2006) Fleet management for advanced intermodal services—final report, report for Transport Canada, Publication CRT-2006-13. Centre de recherche sur les transports, Université de Montréal, 2006

Crevier B, Cordeau J-F, Savard G (2012) Integrated operations planning and revenue management for rail freight transportation. Transp Res Part B 46(1):100–119

Gao et L, Gorman M (2008) Yield management in freight transportation. Informs Annual Meeting, Washington DC

Godwin T, Gopalan R, Narendran TT (2007) Freight train routing and scheduling in a passenger rail network: computational complexity and the stepwise dispatching heuristic. Asia-Pacific J Oper Res 24(04):499–533

Gorman MF (2005) Reservations, forecasting, yield management and railroads. Informs Annual Meeting, San Francisco

Kuehn J (2011) Yield management ~ the next advance in rail profitability. Oliver Wyman perspective

Kraft ER (1998) A reservations-based railway network operations management system. Ph.D. dissertation, Department of Systems Engineering, University of Pennsylvania

Kraft ER (2002) Scheduling railway freight delivery appointments using a bid price approach. Transp Res Part A 36(2):145–165

Kraft ER, Srikar RL, Phillips RL (2000) Revenue management in railroad applications. J Transp Res Forum 39(1):157–176

Lieberman W (2005) Revenue management for the rail industry. Informs Annual Meeting, San Francisco

Talluri KT, van Ryzin GJ (2004) The theory and practice of revenue management. Kluwer Academic Publishers, Norwell

You P-S (2008) An efficient computational approach for railway booking problems. Eur J Oper Res 185(2):811–824