# A Tree-Based Model for Setting Optimal Train Fare Zones

Authors: J. Alberto Conejero; Cristina Jordán; Esther Sanabria-Codesal
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Given a railway line withn stops and the number of travelers between each pair of stops, we show how to split these stops into k different fare zones in order to maximize the benefit obtained from the sale of tickets to the travelers. We present a method to obtain this solution that is based on finding the longest path in a weighted root tree. This method improves in terms of efficiency the combinatorial method, where all the possible distributions have to be considered for deciding which is the optimal one.


---

## Body

## 1. Introduction

In regional or local transportation networks a fare system where the stops are grouped into different zones is usually applied. This is the case for subway, bus, and regional railway transportation networks. The price of a ticket between two stops depends on the number of zones that a passenger must traverse during the travel. The stops and the number of zones are determined by the company. The assignment of the stops to certain zones usually depends on their distance to the center of the network. This is usually an arbitrary decision and it could attend to different reasons. The maximization of benefits can be addressed either to social welfare or to profit. In this last case, an analysis of the flow of travelers between every single pair of stops is required. One may wonder whether a change of fares in order to increase the income would result in a decrease of the demand; however this depends on several factors such as the type of area, the trip purposes, the distance of the journey, and the ticket types, among others. Moreover, one also has to distinguish between short, medium, and long-term elasticities [1]. In our work, we will consider that the number of travelers between each pair of stops is constant and independent of the change of the fare prices.


### 1.1. Related Work

In 1980 Webster and Bly published a collaborative report on [2] identifying many factors which influence demand of travelers. This has been of great value to public transport operators and transport planners. This has been recently updated in [1]. This same year Cervello analyzed the effect of flat rates versus differentiated ones [3]. In particular, he studied the impact of the variability of fares depending on the distance and time-of-day. Moreover, the differentiated fares can be further subdivided into zonal fares, distance-based fares, sectional fares, and time-based fares [4, 5]. Zonal-based fares are the most common fare systems in regional railway and underground transportation networks in Spain.Several studies have been conducted in the last thirty years in order to study fare optimization; see, for instance, [6–9]. The objective functions in the above studies were to maximize either total profit and/or social welfare. In some of the cases elasticities in the demand of the transportation service were included. The solution of these problems was given by the maximization of certain profit function subject to certain restrictions. Sometimes, the maximization can be split into two levels using a bilevel model approach, with the operator model at the upper level and the user at the lower one; see [10, 11]. For further information we refer the reader to [12, Section 2.2].The problem of fare zone design for local public transportation networks using a graph theoretical approach was considered by Hamacher and Schöbel in [13]; see also [14, 15]. In these works, the design is obtained in order to minimize either the maximal or average deviation between the fare zone system and the distance tariff for all the pairs of stops. Some heuristics algorithms were provided in this line in [15].In this work we present an algorithm to find the optimal fare zone system for a line of transport, where the stops are located one after the other. Our model is based on finding the longest path between the root and one of the leaves on a certain weighted directed tree with root. Weighted graphs often appear in the modeling of problems of logistics [16], scheduling and transport routing [17], and management in the air industry [18, 19] and of car-rental companies [20]; see also [21].Apart from this problem, the use of discrete mathematics in railway transportation problems is not new and has been considered for different problems [22–24]. This is done, for instance, in therolling stock planning phase [25, 26] and in its integration with thetimetabling phase [27–29], or in the assignment tracks to the trains [30, 31]. In particular, graph models have been used for choosing a fare planning model that maximizes the revenue [32, 33].


### 1.2. Preliminaries on Weighted Graphs and Trees

We recall that a directed weighted graph is a3-tuple G=(V,E,w) where V is the set ofnodes, E is the set ofarcs (ordered pairs of nodes), and w:E→N0 assigns to every arc (u,v)∈E, with u,v∈V, a positive integer amount (or zero) denoted by w(u,v), or just as wu,v. Apath on a graph is defined as an alternate sequence of nonrepeated nodes and arcs of the form u1,(u1,u2),u2,(u2,u3),u3,…,un-1,(un-1,un),un for some nodes u1,u2,…,un∈V and (u1,u2),(u2,u3),…,(un-1,un)∈E. A directed tree is a directed graph which would be a tree if the directions on the arcs were ignored and all the arcs are directed away from a particular node, which is called the root of the tree. A nondirected graph is a tree if it is connected (every pair of nodes are joined by a path) and it verifies that |E|=|V|-1.The solution of the longest path problem on a graphG=(V,E,w) consists of finding the path between a certain pair of nodes u,v∈V whose sum of the weights of the arcs is maximized. Despite the fact that this is in general an NP-hard problem, its solution can be computed in a linear time on directed acyclic graphs. For further information on graphs and trees, we refer the reader to [21, 34–36].


### 1.3. Organization of the Paper

The paper is organized as follows: in Section2 we introduce the notation and we calculate the total number of admissible solutions to the problem using a combinatorial approach. Section 3 is devoted to the complete analysis of the case of 2 zones. A general algorithm for the construction of a directed rooted tree for an arbitrary number of stops and zones is provided in Section 4. Then the solution to our problem is reduced to find the longest path from the root to one of the leaves in this tree. In Section 5 we give details about the size of the tree constructed in Section 4 and how to label their nodes. This will help us to study the computational cost of this problem that is shown in Section 6. We conclude this section with an example of application.


## 1.1. Related Work

In 1980 Webster and Bly published a collaborative report on [2] identifying many factors which influence demand of travelers. This has been of great value to public transport operators and transport planners. This has been recently updated in [1]. This same year Cervello analyzed the effect of flat rates versus differentiated ones [3]. In particular, he studied the impact of the variability of fares depending on the distance and time-of-day. Moreover, the differentiated fares can be further subdivided into zonal fares, distance-based fares, sectional fares, and time-based fares [4, 5]. Zonal-based fares are the most common fare systems in regional railway and underground transportation networks in Spain.Several studies have been conducted in the last thirty years in order to study fare optimization; see, for instance, [6–9]. The objective functions in the above studies were to maximize either total profit and/or social welfare. In some of the cases elasticities in the demand of the transportation service were included. The solution of these problems was given by the maximization of certain profit function subject to certain restrictions. Sometimes, the maximization can be split into two levels using a bilevel model approach, with the operator model at the upper level and the user at the lower one; see [10, 11]. For further information we refer the reader to [12, Section 2.2].The problem of fare zone design for local public transportation networks using a graph theoretical approach was considered by Hamacher and Schöbel in [13]; see also [14, 15]. In these works, the design is obtained in order to minimize either the maximal or average deviation between the fare zone system and the distance tariff for all the pairs of stops. Some heuristics algorithms were provided in this line in [15].In this work we present an algorithm to find the optimal fare zone system for a line of transport, where the stops are located one after the other. Our model is based on finding the longest path between the root and one of the leaves on a certain weighted directed tree with root. Weighted graphs often appear in the modeling of problems of logistics [16], scheduling and transport routing [17], and management in the air industry [18, 19] and of car-rental companies [20]; see also [21].Apart from this problem, the use of discrete mathematics in railway transportation problems is not new and has been considered for different problems [22–24]. This is done, for instance, in therolling stock planning phase [25, 26] and in its integration with thetimetabling phase [27–29], or in the assignment tracks to the trains [30, 31]. In particular, graph models have been used for choosing a fare planning model that maximizes the revenue [32, 33].


## 1.2. Preliminaries on Weighted Graphs and Trees

We recall that a directed weighted graph is a3-tuple G=(V,E,w) where V is the set ofnodes, E is the set ofarcs (ordered pairs of nodes), and w:E→N0 assigns to every arc (u,v)∈E, with u,v∈V, a positive integer amount (or zero) denoted by w(u,v), or just as wu,v. Apath on a graph is defined as an alternate sequence of nonrepeated nodes and arcs of the form u1,(u1,u2),u2,(u2,u3),u3,…,un-1,(un-1,un),un for some nodes u1,u2,…,un∈V and (u1,u2),(u2,u3),…,(un-1,un)∈E. A directed tree is a directed graph which would be a tree if the directions on the arcs were ignored and all the arcs are directed away from a particular node, which is called the root of the tree. A nondirected graph is a tree if it is connected (every pair of nodes are joined by a path) and it verifies that |E|=|V|-1.The solution of the longest path problem on a graphG=(V,E,w) consists of finding the path between a certain pair of nodes u,v∈V whose sum of the weights of the arcs is maximized. Despite the fact that this is in general an NP-hard problem, its solution can be computed in a linear time on directed acyclic graphs. For further information on graphs and trees, we refer the reader to [21, 34–36].


## 1.3. Organization of the Paper

The paper is organized as follows: in Section2 we introduce the notation and we calculate the total number of admissible solutions to the problem using a combinatorial approach. Section 3 is devoted to the complete analysis of the case of 2 zones. A general algorithm for the construction of a directed rooted tree for an arbitrary number of stops and zones is provided in Section 4. Then the solution to our problem is reduced to find the longest path from the root to one of the leaves in this tree. In Section 5 we give details about the size of the tree constructed in Section 4 and how to label their nodes. This will help us to study the computational cost of this problem that is shown in Section 6. We conclude this section with an example of application.


## 2. Notation

Our algorithm for finding the optimal solution considers partial admissible solutions of the problem and compares among themselves in order to choose the optimal one. For dealing with this partial distributions and with all the admissible solutions to the problem, we introduce a special notation for referring to them. Besides, as we want to get the optimal revenue for the company that supplies the service, then the number of passengers between every pair of stops must be taken into account.Firstly, let us consider a railway line where we know the location ofn stops. For determining a fare system of k zones, we assume that there is at least one stop at every zone; therefore n≥k. The case n=k has a trivial solution since we have a unique stop at every zone so that the cases of interest will be the ones with n>k.Secondly, let us considern stops, namely, {s1,s2,…,sn}. These stops are assumed to be ordered in the railway line; namely, s1≺s2≺s3,…,≺sn, with s1 being the first one and sn the last one. We will also assume that every single stop si is located at only one of the k zones, and we denote by zi its zone, with 1≤i≤n and 1≤zi≤k.We assume the following statements about the distribution of stops into zones. The first one indicates that two consecutive stops in the line must be in the same zone or in contiguous zones.(A1)
For every1≤i≤n-1, either zi+1=zi or zi+1=zi+1.Among all possible distributions generated under assumption (A1), only some of them will be admissible distributions of stops into zones. They will be the ones verifying assumptions (A2) and (A3).(A2)
Considerz1=1 and zn=k; that is, the first and the last city of the line are located at the first and at the last zone, respectively.(A3)
For every1<i<k there exists some 1<j<n such that zj=i; that is, we have at least one stop at every zone.We introduce a notation for referring to particular distributions ofn stops into k zones. We also consider partial distributions that deal with n′<n stops distributed into k zones.Definition 1.
We define a partial distribution ofn′ stops into k zones as a k-tuple of the form [y1,y2,…,yk] where y1+y2+⋯+yk≤n with yi≥0 for all 1≤i≤k, and such that if there exists yi0=0, then yi=0 for i≥i0.
Thek-tuple [y1,y2,…,yk] indicates that stops s1,…,sy1 are in zone 1, stops sy1+1,…,sy1+y2 are in zone 2, and so on, until we have that stops sy1+⋯+yk-1+1,…,sy1+⋯+yk are located in zone k.If we distribute all then stops we refer to this distribution as an admissible one.Definition 2.
We define an admissible distribution ofn stops into k zones as a k-tuple of the form [y1,y2,…,yk] where y1+y2+⋯+yk=n and yi≥1 for all 1≤i≤k.The total number of admissible distributions can be computed using a combinatorial approach.Proposition 3.
Letn be the number of stops to be distributed into k zones. The total number of admissible distributions of this n stops into k zones is (n-1)!/(n-k)!(k-1)!.Proof.
By assumption (A2),z1=1 and zn=k. The other n-2 stops must be distributed into the k zones. By assumption (A3) we have to assign at least one stop of these n-2 to each zone i for 2≤i≤k-1. Let us count how many admissible distributions can we find rearranging the others n-2 stops.
Let us consider two types of symbols,S and C, where S stands for a stop and C for a change of zone. A string of n symbols S and k-1 symbols C represents an admissible distribution of n stops into k zones whenever there is at least (i)
oneS before the first C,(ii)
oneS after the last C,(iii)
oneS between every pair of symbols C.
If we assume the necessity of having at least one symbolS at every zone, then we can rephrase the problem to calculate how many strings can be constructed with n-k symbols S and k-1 symbols C. For instance, a string of the form
(1)SS⋯S︸i1CSS⋯S︸i2C⋯CSS⋯S︸ik,
with i1,…,ik≥0 and i1+i2+⋯+ik=n-k, corresponds to an admissible distribution [i1+1,i2+1,…,ik+1]. The total number of strings constructed with two different elements S and C, with S appearing n-k times and C appearing k-1 times, is given by
(2)Pn-1n-k,k-1=(n-1)!(n-k)!(k-1)!,
which is the number of permutations with repetition of n-1 elements with n-k of one type and k-1 of the other type. For n much more greater than k, this is of order O(nk-1).Given an admissible distribution[y1,y2,…,yk] we can compute the benefit obtained from the passengers tickets. For every pair of stops si,sj with 1≤i,j≤n, i≠j, we denote by pi,j the number of passengers that depart from si and arrive at sj on a certain period of time. A passenger with a return ticket between two stops is counted twice, one on each sense. We assume that these passengers pay two times the price of a single ticket and no discount is granted to them.Once we have an estimation of the number of passengers between every single pair of stops, we can compute which will be the benefit obtained by the sale of tickets after applying a certain assignment of stops to the zones. As we have indicated in the Introduction, we are assuming that a change of the location of the stops in the zones does not modify the number of travelers between every pair of stops.We consider a fare system for the sale of tickets based on the number of zones. The price of a ticket depends on how many zones a passenger crosses in his/her trip, that is, a counting zone tariff system. If a passenger remains at the same zone, then the fare ish0. If it is required to visit 2 zones, that is, the initial and final stops are at contiguous zones, then the price would be h0+h1. When a passenger visits 3 zones, then the cost of the ticket would be h0+h2, and so on. For simplicity, when we compute the benefit coming from a certain distribution of stops into zones we omit the fixed value h0 since it is applied to all the tickets. For maximizing the benefit, the idea is to find a distribution that globally forces the passengers to traverse the highest number of zones, taking into account the aforementioned restrictions set on the distribution of stops into zones. This is the underlying idea on which the following algorithms are based.


## 3. The Case of 2 Zones

The simplest case of just a single zone is not a problem for any numbern of stops. In this section we solve the problem of findig a distribution of n stops into 2 zones in order that the revenue obtained from the passengers tickets is maximized. First, we introduce the trees that model this problem in terms of n∈N. Later, we will show how to compute the optimal solution using the structure of this tree.Some figures will help us to show the construction of the trees used to model different statements of the problem. A dashed line will be used for separating admissible distributions (nodes) with the last stop in different zones. Besides, a node with a thick line around it will be used to indicate the admissible distributions at every step, that is, the ones verifying assumptions (A1), (A2), and (A3).


### 3.1. Definition of the Tree forn Stops and 2 Zones, n≥3

We start at the first stops1 that must be located at zone 1. This is represented by the partial admissible distribution [1,0]. Then we can add one more stop, s2. By assumption (A1), s2 can be assigned either to zone 1 or to zone 2. The first case corresponds to the partial distribution [2,0] and the second one to the unique admissible distribution [1,1]. A pair of arcs departing from [1,0] and arriving at [2,0] and [1,1] shows that these distributions are generated from [1,0]; see Figure 1.Figure 1
Tree for 2 zones and 2 stops.A third stop,s3 can be added. Taking into account (A1) we have two options. On the one hand, the distribution [2,0] lets us generate two new distributions: [3,0], if we add the third stop to zone 1, and [2,1], if we add it to zone 2. On the other hand, from distribution [1,1] we can only add s3 to the second zone since there is no third zone in this case. This enables us to consider the distribution [1,2], too. However, the unique admissible distributions with 3 stops will be [2,1] and [1,2], and not [3,0]. In Figure 2 we have represented this case.Figure 2
Tree for 2 zones and 3 stops.We can proceed by induction using (A1) to construct a tree for each numbern of stops. Suppose that we have done the construction up to n-1 stops. We will see how to get the partial distributions for n stops. There are two kinds of nodes representing a distribution of n-1 stops attending to its form as follows:(i)
[n-1,0],(ii)
the nodes of the form[i,j] with 1≤i,j≤n and i+j=n-1.On the one hand, from[n-1,0] we can construct two new distributions [n,0] and [n-1,1]. On the other hand, from a node [i,j] of the second form we can only generate one more distribution, [i,j+1]; see Figure 3.Figure 3
Tree for2 zones and n stops.With this procedure we construct a tree with a root at[1,0]; see Figure 3. Fixing a value n∈N, the nodes [i,j] with i+j=n will be the leaves of the tree. In particular, every leaf, except [n,0], corresponds to one of the admissible distributions of n stops into 2 zones, bijectively.We point out that in our representations of the trees generated under this procedure, all nodes with the same value fori+j are displayed horizontally as we can also see in Figure 3. Moreover, the nodes of the form [i,j] with j=0 are set to the left of the dashed line, since they correspond to partial distributions that uniquely have stops in zone 1. The rest of the nodes are set to the right of the dashed line since they have at least one stop in zone 2.


### 3.2. Optimal Solution forn Stops and 2 Zones

For finding the optimal arrangement ofn stops into 2 zones, we assign weights to all arcs in order that if we take an admissible distribution [i,j] with i+j=n and j≠0, then the sum of the weights of the arcs in the path that connects [1,0] with [i,j] will represent the total benefit obtained from the passengers that have to change of zone during their travel.Theorem 4.
LetT be a tree constructed under assumptions (A1), (A2), and (A3), for representing the admissible distributions of n stops into 2 zones. Let us assume that the number of passengers between every pair of stops (pi,j)1≤i,j≤n is given.
Then there is an assignment of weights to the edges in order that the sum of the weights of the longest path from the root to[1,0] to a leaf of the form [i,j] with 1≤i,j≤n and i+j=n returns the maximal benefit for distributing n stops into 2 zones.Proof.
Take a treeT constructed under assumptions (A1), (A2), and (A3), for representing the admissible distributions of n stops into 2 zones. Fix i,j with i+j<n; then an arc connecting a node representing the partial distribution [i,j] with a node [i+1,j] or [i,j+1] represents that we added one stop to the partial admissible distribution [i,j], namely, si+j+1.
The weight that we assign to this arc will represent the increment of benefit due to the changes of zone of the passengers that travel between each one of the stops{s1,…,si} and si+j+1. The following formula gives the value of the weights for all the arcs in the tree:
(3)w(u,v)={0foru=[i,0],v=[i+1,0],with1≤i≤n-1,h1∑l=1i‍pl,i+1+pi+1,lforu=[i,0],v=[i,1],with1≤i≤n-1,h1∑l=1i‍pl,i+j+1+pi+j+1,lforu=[i,j],v=[i,j+1]with1≤i,j≤n-1,2≤i+j≤n-1.
In this way, the optimal solution is given by the weight of the longest path among all the paths from the root[1,0] to any vertex [i,j] with i+j=n. By properties of trees, once determining [i,j] such a path is unique.


## 3.1. Definition of the Tree forn Stops and 2 Zones, n≥3

We start at the first stops1 that must be located at zone 1. This is represented by the partial admissible distribution [1,0]. Then we can add one more stop, s2. By assumption (A1), s2 can be assigned either to zone 1 or to zone 2. The first case corresponds to the partial distribution [2,0] and the second one to the unique admissible distribution [1,1]. A pair of arcs departing from [1,0] and arriving at [2,0] and [1,1] shows that these distributions are generated from [1,0]; see Figure 1.Figure 1
Tree for 2 zones and 2 stops.A third stop,s3 can be added. Taking into account (A1) we have two options. On the one hand, the distribution [2,0] lets us generate two new distributions: [3,0], if we add the third stop to zone 1, and [2,1], if we add it to zone 2. On the other hand, from distribution [1,1] we can only add s3 to the second zone since there is no third zone in this case. This enables us to consider the distribution [1,2], too. However, the unique admissible distributions with 3 stops will be [2,1] and [1,2], and not [3,0]. In Figure 2 we have represented this case.Figure 2
Tree for 2 zones and 3 stops.We can proceed by induction using (A1) to construct a tree for each numbern of stops. Suppose that we have done the construction up to n-1 stops. We will see how to get the partial distributions for n stops. There are two kinds of nodes representing a distribution of n-1 stops attending to its form as follows:(i)
[n-1,0],(ii)
the nodes of the form[i,j] with 1≤i,j≤n and i+j=n-1.On the one hand, from[n-1,0] we can construct two new distributions [n,0] and [n-1,1]. On the other hand, from a node [i,j] of the second form we can only generate one more distribution, [i,j+1]; see Figure 3.Figure 3
Tree for2 zones and n stops.With this procedure we construct a tree with a root at[1,0]; see Figure 3. Fixing a value n∈N, the nodes [i,j] with i+j=n will be the leaves of the tree. In particular, every leaf, except [n,0], corresponds to one of the admissible distributions of n stops into 2 zones, bijectively.We point out that in our representations of the trees generated under this procedure, all nodes with the same value fori+j are displayed horizontally as we can also see in Figure 3. Moreover, the nodes of the form [i,j] with j=0 are set to the left of the dashed line, since they correspond to partial distributions that uniquely have stops in zone 1. The rest of the nodes are set to the right of the dashed line since they have at least one stop in zone 2.


## 3.2. Optimal Solution forn Stops and 2 Zones

For finding the optimal arrangement ofn stops into 2 zones, we assign weights to all arcs in order that if we take an admissible distribution [i,j] with i+j=n and j≠0, then the sum of the weights of the arcs in the path that connects [1,0] with [i,j] will represent the total benefit obtained from the passengers that have to change of zone during their travel.Theorem 4.
LetT be a tree constructed under assumptions (A1), (A2), and (A3), for representing the admissible distributions of n stops into 2 zones. Let us assume that the number of passengers between every pair of stops (pi,j)1≤i,j≤n is given.
Then there is an assignment of weights to the edges in order that the sum of the weights of the longest path from the root to[1,0] to a leaf of the form [i,j] with 1≤i,j≤n and i+j=n returns the maximal benefit for distributing n stops into 2 zones.Proof.
Take a treeT constructed under assumptions (A1), (A2), and (A3), for representing the admissible distributions of n stops into 2 zones. Fix i,j with i+j<n; then an arc connecting a node representing the partial distribution [i,j] with a node [i+1,j] or [i,j+1] represents that we added one stop to the partial admissible distribution [i,j], namely, si+j+1.
The weight that we assign to this arc will represent the increment of benefit due to the changes of zone of the passengers that travel between each one of the stops{s1,…,si} and si+j+1. The following formula gives the value of the weights for all the arcs in the tree:
(3)w(u,v)={0foru=[i,0],v=[i+1,0],with1≤i≤n-1,h1∑l=1i‍pl,i+1+pi+1,lforu=[i,0],v=[i,1],with1≤i≤n-1,h1∑l=1i‍pl,i+j+1+pi+j+1,lforu=[i,j],v=[i,j+1]with1≤i,j≤n-1,2≤i+j≤n-1.
In this way, the optimal solution is given by the weight of the longest path among all the paths from the root[1,0] to any vertex [i,j] with i+j=n. By properties of trees, once determining [i,j] such a path is unique.


## 4. The General Case ofk Zones

In this section we will see how to construct a tree for the case ofn stops and k zones, with k≥2 and n≥3. The algorithm is mainly based on assumption (A1), which permits inductively defining the nodes and the arcs as we have seen in Section 3.From Step 1 up to Stepk-1, at the substeps q.1 and q.2 for 1≤q≤k-1, we define two new nodes from a node [i1,i2,…,iq,0,…], which are [i1,i2,…,iq+1,…] and [i1,i2,…,iq,1,…]. We also define two arcs connecting node [i1,i2,…,iq,…] with each of them and assign its weight using formulas (4), (5), (6), (7), and (8). When a node is of the form [i1,i2,…,ik] with ik≠0, then we connect this node with a single node [i1,i2,…,ik+1] and assign a weight to this arc using formula (9).An example of a tree for 5 stops and 3 zones is represented in Figure4.Figure 4
Tree for3 zones and 5 stops.


### 4.1. Definition of the Tree forn Stops and k Zones with n>k≥2

Step
0
.Consider the following.(0.1)
Definei0=0. (*This index will be used from Step 3 onwards)*.(0.2)
Start a tree with a unique node[1,0,0,…,0]︸k. This will be its root.(0.3)
Define a listL. We initialize the list with the node [1,0,0,…,0].Step
1. We take the first node in the list L, namely, [i1,i2,i3,…,ik].Ifij=0 for 2≤j≤k then consider the following.(1.1)
Ifi1≤n-k+1 then
(i)
define two new nodes[i1+1,0,0,…,0] and [i1,1,0,0,…,0] that are added to L;(ii)
define the arcs([i1,0,0,…,0],[i1+1,0,0,…,0]) with weight 0 and ([i1,0,0,…,0],  [i1,1,0,…,0]) with weight
(4)h1(∑l=1i1‍pl,i1+1+pi1+1,l);(iii)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.(1.2)
Else ifn-k+1<i1≤n-1 then
(i)
define two new nodes[i1+1,0,0,…,0] and [i1,1,0,0,…,0] that are added to L;(ii)
define the arcs([i1,0,0,…,0],[i1+1,0,0,…,0]) and ([i1,0,0,…,0],[i1,1,0,…,0]) with weight 0;(iii)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.(1.3)
Else ifi1=n then
(i)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.Step
2. If i2≠0 but ij=0 for j=3,…,k then consider the following.(2.1)
Ifi1+i2≤n-k+2 then
(i)
define two new nodes[i1,i2+1,0,…,0] and [i1,i2,1,0,…,0] that are added to L;(ii)
define the arc([i1,i2,0,…,0],[i1,i2+1,0,…,0]), with weight
(5)h1(∑l=1i1‍pl,i1+i2+1+pi1+i2+1,l),and the arc([i1,i2,0,…,0],[i1,i2,1,0,…,0]) with weight
(6)h2(∑l=1i1‍pl,i1+i2+1+pi1+i2+1,l)+h1(∑l=i1+1i1+i2‍pl,i1+i2+1+pi1+i2+1,l);(iii)
remove[i1,i2,0,…,0] from the list L and return to Step 1.(2.2)
Ifn-k+2<i1+i2≤n-1 then
(i)
define two new nodes[i1,i2+1,0,0,…,0] and [i1,i2,1,…,0] that are added to L;(ii)
define the arcs([i1,i2,0,…,0],[i1,i2+1,0,…,0]) and ([i1,i2,0,…,0],[i1,i2,1,…,0]), both of them with weight 0;(iii)
remove[i1,i2,0,…,0] from the list L and return to Step 2.(2.3)
Ifi1+i2=n then
(i)
remove[i1,i2,0,…,0] from the list L and return to Step 2.(*For q=3,…,k-1 the steps are defined following the next pattern:)*Step
q. If iq≠0 and ij=0 for j=q+1,…,k then consider the following.(q.1)
Ifi1+i2+⋯+iq≤n-k+q then
(i)
define two new nodes[i1,i2,…,iq+1,0,…,0], [i1,i2,…,iq,1,…,0] that are added to L;(ii)
define the arc([i1,i2,…,iq,0,…,0],[i1,i2,…,iq+1,0,…,0]), with weight
(7)∑r=1q-1‍hq-r(∑l=i0+i1+⋯+ir-1+1i0+i1+⋯+ir‍pl,i1+i2+⋯+iq+1+pi1+i2+⋯+iq+1,l),and the arc([i1,i2,…,iq,0,…,0],[i1,i2,…,iq,1,0,…,0]) with weight
(8)∑r=1q‍hq-r+1(∑l=i0+⋯+ir-1+1i0+⋯+ir‍pl,i1+i2+⋯+iq+1+pi1+i2+⋯+iq+1,l);(iii)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.(q.2)
Ifn-k+q<i1+i2+⋯+ij≤n-1 then
(i)
define two new nodes[i1,i2,…,iq+1,0,…,0] and [i1,i2,…,iq,1,…,0] that are added to L;(ii)
define the arcs([i1,i2,…,iq,0,…,0],[i1,i2,…,iq+1,0,…,0]) and ([i1,i2,…,iq,…,0],  [i1,i2,…,iq+1,0,…,0]), both of them with weight 0;(iii)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.(q.3)
Ifi1+i2+⋯+iq=n then
(i)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.Step
k. Since ik≠0 then consider the following.(k.1)
Ifi1+i2+⋯+ik≤n-1 then
(i)
define a new node[i1,i2,…,ik-1,ik+1] and add it to L;(ii)
define the arc([i1,i2,…,ik-1,ik],[i1,i2,…,ik-1,ik+1]) with weight
(9)∑r=1k-1‍hk-r(∑l=i0+⋯+ir-1+1i0+⋯+ir‍pl,i1+i2+⋯+ik+1+pi1+i2+⋯+ik+1,l);(iii)
remove[i1,i2,…,ik-1,ik] from the list L and return to Step 1.(k.2)
Ifi1+i2+⋯+ik=n then
(i)
remove[i1,i2,…,ik-1,ik] from the list L and we are done.


### 4.2. Optimal Solution forn Stops and k Zones

With a similar argument as in the proof of Theorem4, we can get the optimal solution for k zones.Theorem 5.
Let us considern stops to be distributed into k zones and assume that the number of passengers between every pair of stops (pi,j)1≤i,j≤n is given. Let T be a weighted tree constructed under assumptions (A1), (A2), and (A3) as it is indicated in Section 4.1.
Then the longest path from the root to[1,0,…,0] to a leaf of the form [i1,…,ik] with 1≤i1,…,ik≤n and i1+⋯+ik=n returns the maximal benefit for distributing n stops into k zones.Remark 6.
We point out that in substeps1.2,…,k-1.2 some nodes defined are useless for finding the solution, since they do not belong to any path from the root [1,0,0,…,0] to any admissible distribution. However, their definition will simplify the enumeration of the nodes as we will see in the next section.


## 4.1. Definition of the Tree forn Stops and k Zones with n>k≥2

Step
0
.Consider the following.(0.1)
Definei0=0. (*This index will be used from Step 3 onwards)*.(0.2)
Start a tree with a unique node[1,0,0,…,0]︸k. This will be its root.(0.3)
Define a listL. We initialize the list with the node [1,0,0,…,0].Step
1. We take the first node in the list L, namely, [i1,i2,i3,…,ik].Ifij=0 for 2≤j≤k then consider the following.(1.1)
Ifi1≤n-k+1 then
(i)
define two new nodes[i1+1,0,0,…,0] and [i1,1,0,0,…,0] that are added to L;(ii)
define the arcs([i1,0,0,…,0],[i1+1,0,0,…,0]) with weight 0 and ([i1,0,0,…,0],  [i1,1,0,…,0]) with weight
(4)h1(∑l=1i1‍pl,i1+1+pi1+1,l);(iii)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.(1.2)
Else ifn-k+1<i1≤n-1 then
(i)
define two new nodes[i1+1,0,0,…,0] and [i1,1,0,0,…,0] that are added to L;(ii)
define the arcs([i1,0,0,…,0],[i1+1,0,0,…,0]) and ([i1,0,0,…,0],[i1,1,0,…,0]) with weight 0;(iii)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.(1.3)
Else ifi1=n then
(i)
remove[i1,0,0,…,0] from the list L and return to the beginning of this step.Step
2. If i2≠0 but ij=0 for j=3,…,k then consider the following.(2.1)
Ifi1+i2≤n-k+2 then
(i)
define two new nodes[i1,i2+1,0,…,0] and [i1,i2,1,0,…,0] that are added to L;(ii)
define the arc([i1,i2,0,…,0],[i1,i2+1,0,…,0]), with weight
(5)h1(∑l=1i1‍pl,i1+i2+1+pi1+i2+1,l),and the arc([i1,i2,0,…,0],[i1,i2,1,0,…,0]) with weight
(6)h2(∑l=1i1‍pl,i1+i2+1+pi1+i2+1,l)+h1(∑l=i1+1i1+i2‍pl,i1+i2+1+pi1+i2+1,l);(iii)
remove[i1,i2,0,…,0] from the list L and return to Step 1.(2.2)
Ifn-k+2<i1+i2≤n-1 then
(i)
define two new nodes[i1,i2+1,0,0,…,0] and [i1,i2,1,…,0] that are added to L;(ii)
define the arcs([i1,i2,0,…,0],[i1,i2+1,0,…,0]) and ([i1,i2,0,…,0],[i1,i2,1,…,0]), both of them with weight 0;(iii)
remove[i1,i2,0,…,0] from the list L and return to Step 2.(2.3)
Ifi1+i2=n then
(i)
remove[i1,i2,0,…,0] from the list L and return to Step 2.(*For q=3,…,k-1 the steps are defined following the next pattern:)*Step
q. If iq≠0 and ij=0 for j=q+1,…,k then consider the following.(q.1)
Ifi1+i2+⋯+iq≤n-k+q then
(i)
define two new nodes[i1,i2,…,iq+1,0,…,0], [i1,i2,…,iq,1,…,0] that are added to L;(ii)
define the arc([i1,i2,…,iq,0,…,0],[i1,i2,…,iq+1,0,…,0]), with weight
(7)∑r=1q-1‍hq-r(∑l=i0+i1+⋯+ir-1+1i0+i1+⋯+ir‍pl,i1+i2+⋯+iq+1+pi1+i2+⋯+iq+1,l),and the arc([i1,i2,…,iq,0,…,0],[i1,i2,…,iq,1,0,…,0]) with weight
(8)∑r=1q‍hq-r+1(∑l=i0+⋯+ir-1+1i0+⋯+ir‍pl,i1+i2+⋯+iq+1+pi1+i2+⋯+iq+1,l);(iii)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.(q.2)
Ifn-k+q<i1+i2+⋯+ij≤n-1 then
(i)
define two new nodes[i1,i2,…,iq+1,0,…,0] and [i1,i2,…,iq,1,…,0] that are added to L;(ii)
define the arcs([i1,i2,…,iq,0,…,0],[i1,i2,…,iq+1,0,…,0]) and ([i1,i2,…,iq,…,0],  [i1,i2,…,iq+1,0,…,0]), both of them with weight 0;(iii)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.(q.3)
Ifi1+i2+⋯+iq=n then
(i)
remove[i1,i2,…,iq,0,…,0] from the list L and return to Step 1.Step
k. Since ik≠0 then consider the following.(k.1)
Ifi1+i2+⋯+ik≤n-1 then
(i)
define a new node[i1,i2,…,ik-1,ik+1] and add it to L;(ii)
define the arc([i1,i2,…,ik-1,ik],[i1,i2,…,ik-1,ik+1]) with weight
(9)∑r=1k-1‍hk-r(∑l=i0+⋯+ir-1+1i0+⋯+ir‍pl,i1+i2+⋯+ik+1+pi1+i2+⋯+ik+1,l);(iii)
remove[i1,i2,…,ik-1,ik] from the list L and return to Step 1.(k.2)
Ifi1+i2+⋯+ik=n then
(i)
remove[i1,i2,…,ik-1,ik] from the list L and we are done.


## 4.2. Optimal Solution forn Stops and k Zones

With a similar argument as in the proof of Theorem4, we can get the optimal solution for k zones.Theorem 5.
Let us considern stops to be distributed into k zones and assume that the number of passengers between every pair of stops (pi,j)1≤i,j≤n is given. Let T be a weighted tree constructed under assumptions (A1), (A2), and (A3) as it is indicated in Section 4.1.
Then the longest path from the root to[1,0,…,0] to a leaf of the form [i1,…,ik] with 1≤i1,…,ik≤n and i1+⋯+ik=n returns the maximal benefit for distributing n stops into k zones.Remark 6.
We point out that in substeps1.2,…,k-1.2 some nodes defined are useless for finding the solution, since they do not belong to any path from the root [1,0,0,…,0] to any admissible distribution. However, their definition will simplify the enumeration of the nodes as we will see in the next section.


## 5. Some Considerations regarding the Nodes

The algorithm in Section4 lets us construct a tree that models our problem. As we have seen in the previous section, the construction of the nodes and the arcs joining them can be done inductively. However, it could be of interest to find an explicit formula for calculating the total number of nodes in each tree; see, for instance, the case of 3 zones and 5 stops in Figure 5 and the case of 4 zones and 6 stops in the figure in the Supplementary Material available online at http://dx.doi.org/10.1155/2014/384321.Figure 5
Tree for3 zones and 5 stops with labels at the nodes.Suppose that we haven stops and k zones, with n>k≥2. At the qth step of the construction of the tree, q=1,…,n, we have all admissible distributions of q stops distributed in a row. More precisely we have all distributions of the form [i1,…,ik] with ∑l=0k‍il=q and if il=0, then the next indexes are null; that is, il+1=⋯=ik=0.We recall that for everyq<n, every node labelled in the step q as [i1,…,ik] is split into one or two nodes at step q+1. More precisely, a node [i1,…,ij,0,…,0], with i1,…,ij≠0 and j<k, gives birth to [i1,…,ij+1,0,…,0] and [i1,…,ij,1,…,0]. A node at zone k in the step q of the form [i1,…,ik], with ik≠0, is only connected with the node [i1,…,ik+1] at the zone k in the step q+1. All these nodes can be enumerated using properties of Pascal’s triangle; see, for instance, [37].Theorem 7.
Let us denote byzq,j the number of nodes at zone j at Step q of the construction of the tree that models the problem for n stops into k zones. Then
(10)zq,j=(q-1j-1)=∏l=1j-1‍(q-l)(j-1)!for1≤q≤n,1≤j≤k.Proof.
Let us denote byzq,j the number of nodes at zone j at Step q of the construction of the tree, which is defined for all pairs (q,j) with 1≤q≤n and 1≤j≤min⁡{k,q}. The sequence {zq,j}j,q can be inductively defined as
(11){zq,1=1∀1≤q≤n,zq,q=1∀1≤q≤k,zq,j=zq-1,j-1+zq-1,jif1<q≤n,q<j≤k.
This recurrence is similar to the one used for generating the combinatorial numbers in Pascal’s triangle [37]. Therefore, we can identify the numbers zq,j with the combinatorial numbers expressed in (10).As the number of nodes in a row is represented by combinatorial numbers, in order to assign labels to the nodes, we can use an existing connection with the partial sums by rows of Pascal’s triangle. Furthermore, explicit formulas for these numbers can be provided using generating functions [38].Proposition 8 (see [38]).
Let us consider the functions(12)Gj(x)∶=1xj-1(∑i=0j-1‍xi(1-x)i+1-(2x)j-1-12x-1)for1≤j≤k.
If we denote byGj,i the ith coefficient of the Taylor expansion of Gj at x=0, then the following relation holds:
(13)∑l=1j‍zq,l=∑l=1j‍(q-1l-1)=Gj,q-jforj≤q.Example 9.
Let us analyze with more details the basic cases of2 and 3 zones with n stops. For 2 zones, the total number of nodes of the tree generated for distributing n stops is
(14)∑q=1n‍(q-10)+∑q=2n‍(q-11)=n2+n2.
Similarly, for3 zones and n stops the number of nodes needed to define the tree is
(15)∑q=1n‍(q-10)+∑q=2n‍(q-11)+∑q=3n‍(q-12)=n3+5n6,
and for 4 zones and n stops we have a tree with the following number of nodes:
(16)∑q=1n‍(q-10)+∑q=2n‍(q-11)+∑q=3n‍(q-12)+∑q=4n‍(q-13)=n4-2n3+11n2+14n24.Remark 10.
The formulas in Proposition8 and in Example 9 can be obtained taking into account that the sum of combinatorial numbers along a diagonal of Pascal’s triangle can be expressed as an arithmetic sequence of higher order [39]. The general formula for the number of nodes in the problem of k zones and n stops is given by
(17)∑j=1k‍∑q=1n‍(q-1j-1)
that can be also rewritten as
(18)n+12!∏l=01‍(n-l)+13!∏l=02‍(n-l)+⋯+1(k-1)!∏l=0k-2‍(n-l)+1k!∏l=0k-1‍(n-l).
Therefore, using properties of arithmetic sequence of higher order [39] and if n is much more greater than k, we affirm that the number of nodes of the tree for the problem of k zones and n stops is of order O(nk).We can also enumerate all admissible distributions of a tree using a sequential order. As we have already seen, this can be done recursively. Here we provide explicit formulas for the cases of2 and 3 zones.Example 11.
The number corresponding to a node representing the admissible distribution corresponding to the case of2 zones and n stops [i1,i2], with i1+i2≤n, can be easily defined from the sequence {aj}j≥1 with aj=(j2+j)/2:(19){1+ai1-1fori1≠0,i2=0,1+ai1+i2-1+i2fori1,i2≠0.
For the case of3 zones and n stops, the number assigned to a (partial) admissible distribution [i1,i2,i3], with i1+i2+i3≤n, can be easily defined from the sequence {aj}j≥1 with aj=(j3+5j)/6. The label of [i1,i2,i3] is
(20){1+ai1-1fori1≠0,i2,i3=0,1+ai1+i2-1+i2fori1,i2≠0,i3=0,1+ai1+i2+i3-1+i2+∑l=1i3‍(i1+i2+i3-l)fori1,i2,i3≠0.Remark 12.
We point out that in the algorithm of Section4, at some steps of the form (*.2), we were introducing additional nodes for simplifying the notation as it is indicated at the beginning of this section; see also Remark 6, despite the fact that they are not considered for finding the optimal solution. Since no admissible distribution is accessible from one of these nodes, then we can remove them and reduce the number of nodes that we are considering in our model. Nevertheless, we have preserved them for the clarity of the enumeration.


## 6. Discussion and Results

As we have already mentioned in Section2, for n stops to be distributed into k zones, we have to evaluate a number of (n-1k-1) possible solutions. The cost of generating all these solutions is of order O(nk), since k nested loops from 1 to n are required. For each one of these possible solutions one has to consider the n(n-1) arrangements of two different stops and to compute the income received from the passengers between every pair of stops (in both directions). Then the cost is of order O(nk+2).If we think in terms of the tree constructed in Section4.1 for modeling the problem, each possible solution to the problem of the optimal assignment of stops into zones is associated with a leaf of that tree, or in other words to a node in the zone k at step n. This is consistent with the definition of zn,k, which is in fact (n-1k-1). So as to get the benefit from a certain distribution [i1,…,ik], of n stops into k zones, we have to compute the length (in terms of weight) of the unique path that connects the root [1,0,…,0] with the node associated with [i1,…,ik]. Each path from the root to a leaf consists of n-1 edges. The tree structure used for representing the distributions of stops into zones lets us obtain the weight of each of them by computing once the weight of each arc in order to get the optimal solution to our problem. This improves the computational cost of the solution with respect to the combinatorial approach. Let us see in detail the benefits of using the tree-based approach.Firstly, as we have indicated in the previous section, the number of nodes is of orderO(nk). This also holds for the number of arcs, since the number of arcs in a tree is equal to the number of nodes minus 1.Secondly, the computational cost of the calculations for assigning a weight to a single arc is of orderO(n): for every arc with an end node of the form [i1,i2,…,ij,0,…,0] we need at most 2(i1+i2+⋯+ij-1) sums plus at most j-1 products in order to determine the benefit from the passengers between the first i1+⋯+ij-1 and the last one; see (7), (8), and (9). These computations are of order O(n). The same estimation of the computational cost is obtained if the end node is of the form [i1,i2,…,ik] with ik≠0. Therefore, the cost of assigning weights to all arcs of the tree is of order O(nk+1).Finally, for finding the longest path from the root to a leaf we needO(nk) operations because we only need to consider each arc only once as we can see right now. Consider the zn,k leaves of the tree, which are located at level n. Each one is connected to a different node in the level n-1. But some of the nodes at level n-1 share their adjacent node at level n-2. For instance, a pair of nodes of the form [i1,…,ik-1,1], [i1,…,ik-1+1,0] at level n-1, share its adjacent node at level n-2, which is [i1,…,ik-1,0]. This also holds for nodes of the form [i1,…,ij,1,0,…,0], [i1,…,ij+1,0,0,…,0] for j=2,…,k-2.Our strategy will be to start with the leaves and find their adjacent nodes at leveln-1. Then we find the adjacent nodes to them at level n-2. For every node at level n-2, we choose between the two only possibilities we have and record which is the path to a leaf that provides a longer path. Inductively, we repeat the process with nodes at an upper level until we arrive at the root. Therefore, once the tree is defined, for finding the distribution with highest revenue, we have to perform a number of computations of order O(nk), similar to the order of the number of arcs in the tree.All this together gives that we needO(nk+1) computations to find the solution using the tree-based approach for finding the solution to our problem, which is smaller than the computational cost of the combinatorial approach, O(nk+2).For illustrating these results we have considered the problem of splitting 10 stops into 2, 3, 4, 5, and 6 zones. In particular we have considered an estimation of the number of the passengers of the railway line Valencia-Castellón over the month of August 2013. The number of passengers between each pair of stops is given in Table1.Table 1
A
B
C
D
E
F
G
H
I
J
A
—
9260
5616
13692
3254
13804
1468
4564
19586
29611
B
5689
—
48
2402
397
1526
678
83
3545
3378
C
1334
28
—
788
53
388
410
230
558
573
D
3485
1354
524
—
225
479
580
294
2193
2922
E
507
17
3
402
—
94
16
393
361
1125
F
3463
934
306
629
806
—
1052
2753
3706
6300
G
576
236
240
390
340
510
—
1048
1802
1799
H
1301
344
54
495
509
1353
257
—
4014
6741
I
13065
4124
1334
3566
931
4669
1778
5249
—
867
J
33181
9914
4395
9494
3752
26694
5931
17326
1824
—We present in the table the most efficient distributions of the 10 stops into different number of zones. For3 zones the optimal distribution is [7,1,2] and for 4 zones [6,1,1,2]. Besides, for 5 and 6 zones the results are the ones shown in Figures 6 and 7.Figure 6
Optimal distribution for the 10 stops of Table1 into 5 zones. This corresponds with [5,1,1,1,2].Figure 7
Optimal distribution for the 10 stops of Table1 into 6 zones. This corresponds with [3,2,1,1,1,2].



---

*Source: 384321-2014-09-11.xml*