Während in vielen Städten ÖV Tarife unabhängig von der Route sind, ist dies in einigen Städten nicht der Fall. In solchen Fällen wird vom Fahrgast ein Grundtarif und zudem ein distanz-basierter Zuschlag verlangt. Der marginale Zuschlag pro km verringert sich dabei meist mit gefahrener Strecke. Solche Tarifsysteme stellen eine Herausforderung für lininenfeine Umlegungsverfahren da, in denen hyperpaths unter Berücksichtigung von „strategischer Routenwahl“ berechnet werden. In diesem Beitrag diskutieren wir Modellierungsverfahren und stellen einen Lösungsansatz vor. Dieser hat zur Grundlage, dass der hyperpath spezifische Tarif unter Berücksichtigung der bereits gefahrenen Kanten des Netzwerkes berechnet wird. Dieser Ansatz wird dann in einem Umlegungsverfahren mit „effective frequencies“ verwendet und in einer Beispielstudie mit dem Londoner U-Bahnnetz angewendet. Die Ergebnisse verdeutlichen, dass distanz-basierte Tarife eine Möglichkeit sein können Kapazitätsengpässe zu verringern.

Whereas in many cases public transport fares are route-independent in other cities they vary according to the chosen route. In such cases passengers have to pay a base fare plus a distance-depending surcharge. The marginal increase per km is thereby in most cases decreasing. Such fare structures constitute a problem for frequency-based assignment where shortest hyperpaths are obtained according to “optimal strategies”. In this paper we discuss previous solutions and present a solution where the hyperpath specific expected link fare is calculated according to the number of links that have already been traversed. We implement the approach in a transit assignment model that considers effective frequencies and apply it to the London metro network. Results illustrate how distance-based fares can potentially reduce congestion in a network.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Introduction

There are a large range of different fare structures among public transport operators. In some cities integrated fares are achieved so that customers have to pay only once for a trip independent of modes and routes whereas in other cities only partial integration or no integration is implemented. Partial integration could mean that customers obtain reductions in fares in case they transfer. As discussed in Constantin and Florian (2015) with examples from Latin America, the fare to be paid for an express service can depend as to whether the user has used a non-express service on his journey before or not. Besides operator and route integration furthermore the spatial fare structures remain an important topic among operators.

Though zonal fare structures are common in many cities, other cities do not want to abandon flat fare systems, or, on the contrary, believe that distance-based fare structures are fair as customers are charged according to how much they use the services. Furthermore, through new technology such as mobile phone based ticketing complex fare structures become more common.

Schmöcker et al (2016) discuss that there are contradicting trends especially among European metropolitan cities partly triggered through new charging technologies. On the one hand cities/regions such as East Austria`s public transport organization aim to fully utilize such technologies and introduce very detailed fare structures. On the other hand cities such as Stockholm or Oslo consider that introducing such complexities does not lead to significant revenue increases and that the disadvantage of a difficult to understand fare structure outweighs potential advantages.

One argument that is also part of this discussion is the difficulty to plan revenues and route choices in case of complex price differentiation. The objective of this paper is to contribute overcoming these problems. We consider a pricing structure where passengers are charged according to distance travelled in the network, where distance is approximated by link numbers. Such pricing is common in, for example, Japanese bus networks. We are aware that such pricing structures have become less common in urban rail or metro networks with the introduction of electronic ticketing where passengers tap-in and tap-out and prices become independent of the route chosen. We suggest though that for (future) charging based on GPStracking such pricing structures (for public transport as well as for car journeys) are likely to return. Furthermore, we aim to develop an approach that is applicable for large scale networks and at the planning stage. Therefore we consider a frequency-based assignment model in which we aim to integrate a solution approach capable of dealing with such fares. The remainder of the paper is organized as follows. The next section will describe existing approaches to reflect non-linear fares as well as the unsolved challenges. Section 3 then sets out our solution approach which is an extension of a working paper by the authors of this paper. Whereas in that work we only discuss how to obtain the optimal hyperpaths in this paper we extend this work in Section 4 by discussing its implementation to a transit network and a transit assignment approach considering congestion. Section 5 then applies the approach to a London example. The example is not meant to reflect necessarily the exact network flows but rather to illustrate the effect of non-additive fares on route choice and link flows. Section 6 concludes the paper.

2 Existing solution approaches and unsolved problems

The main “base” approach for frequency-based transit assignment remains the optimal strategy approach proposed by Spiess and Florian (1989). The main idea of their paper is the consideration of “hyperpaths” to explain passengers` route choices. That is, passengers can minimize their travel time if they take “which service arrives first” at a stop from a predetermined set of attractive lines. The approach has been improved and extended in several ways, notably considering the availability of real-time information and consideration of congestion and capacity constraints. For a summary we refer to Gentile and Nökel (2016). The attractiveness of the Spiess and Florian search for a shortest hyperpath is that the problem can be reduced to a linear programming problem and solved fast. The approach is based on backward search for the optimal hyperpath tree from a given destination to all origins in the network.

Fares can be introduced in the solution approach by adding link penalties. In a multi-modal flat fare network where one wants to model mode choice one can add fares to the entry links of the public transport network. Zonal fare systems can be partially reflected if one adds penalties at links that cross the zones. What such fares can though not reflect is the case of non-additive zonal fares as discussed in detail in PTV (2013). That is, if the fare of a particular zone depends on how many previous zones have been traversed. For example, take a city with three radial zones. If the fare for travelling in the outermost Zone 3 differs depending on whether Zone 1 or Zones 1 and 2 have been traversed before then zone crossing penalties do not work. In particular note that these are not possible to be considered in the above mentioned backward oriented frequency-based assignment approach.

To overcome such difficulties the aforementioned paper by Florian and Constantin (2015) discusses the idea of a “state-augmented” network originally proposed in Lo et al (2003). The idea of the approach is that the network is expanded to the different states a traveler can be in, such as “has already used a local bus”. This information, implemented as parallel networks, is then considered in the backward oriented hyperpath search. Constantin and Florian illustrate this approach with an application to a multi-modal network where one obtains discounts for transfers depending on previously used modes.

The approach works well in case of a limited number of fare stages. We suggest though the approach becomes impractical in case there are a large number of fares or if the fare depends on specific paths that a traveler has taken. One might summarize the currently employed approaches as in Table 1. We note that Constantin and Florian only discuss the application of the SAM network to transfer fares though we suggest the idea might also be worth exploring further to model non-additive zonal fares.

Table 1. Methods for hyperpath-based assignment with common fare structures

3 Optimal hyperpaths for non-additive “distance-depending” fares

3.1 Detailed problem description

We consider still a case where there a limited number of “fare stages”. In our case these do not depend though on specific transfers but generally on the distance travelled. To simplify the problem we discretize fares and assume that links are fairly equal distance. (If there are some exceptionally long links in the network, one can always divide these into several links.) This allows us to introduce a fare vector F where the first entry denotes the fare for entering the network. The second entry the fare for traversing the first link, the third the fare for traversing the 2nd link and so on. The last vector entry describes the fare for traversing link n-1 as well as all subsequent links. E.g. F=(10,5,3,2) denotes a fare system where the traveller has to pay a base fare of 10 units, a fare of 5 units for the first link, a fare of 3 units for the second link and a fare of 2 units for all subsequent links. We also note that link number depending fares are not unusual in that in some public transport networks passengers are charged directly in terms of stop numbers (for example take the Berlin case as a simple fare structure where there are “Kurzstreckentickets” for up to three 3 stops.)

Our solution approach utilizes the idea that for this fare structure types three types of hyperpaths can be distinguished as shown in Table 2. In the first case, we obtain the same hyperpath in the network with considering minimum fares and hyperpath specific fares. In the second case, the hyperpath changes after assigning fares but the Bellman principle still holds. In other words, the strategy of taking detours for the sake of saving fares further downstream never pays off and hence the optimal (hyper-)path from an origin O to a node A is the optimal hyperpath independent as to whether node A itself is the destination or if a node B is the destination for which the optimal hyperpath includes traversing A. This property might though not always hold so that there are potentially different optimal hyperpaths to an intermediate node depending on what the final destination is.

The following example on a four link network where ta denotes the fixed link cost and da the headway illustrates the three cases. O is the origin and B and C the two destinations. Table 2 shows that for the fare structure F = (0,5,3,2) we will find the same hyperpaths for both destinations compared to the case without fare, so that this fare structure and OD pairs can be classified as Type 1. In case of F= (0,20,12,10) instead the hyperpath changes compared to the without fare case. It is important though that the hyperpath changes for both (all) destinations so that the Bellman principle still holds.

This is not the case for F= (0,50,30,2) so that this fare has to be classified as Type 3. The optimal hyperpath to B consists of the link (O,B) only, whereas the optimal hyperpath to C includes both paths to B. In words, the detour via A pays off for travellers to C as it reduces the costs from B to C more than the additional costs for possibly travelling via A. The larger the marginal differences between fares on the n-1^th and nth link, the more likely the fare structure is of Type 3.

The key point for transit assignment is now that for Type 1 OD pairs the standard optimal strategy approach will still give the optimal solution whereas in other cases this is not guaranteed. We therefore develop a solution algorithm that distinguishes the three types. If we find an OD pair to be of Type 1 no further consideration is needed.

Figure 1. Four link network example

Table 3 Illustration of different optimal hyperpath types

3.2 Summary of Solution Algorithm

The solution algorithm is split into two stages. Stage 1 identifies for which type of OD pairs the fare does not influence route choice. This is done as follows: Firstly a hyperpath is obtained considering minimum fare for all links. Then the fare for those links that are part of the optimal hyperpath are increased but all other fares kept at their minimum. By comparing the new and old resulting optimal hyperpath we can obtain a conservative estimate of which links are of Type 1. All other OD pairs enter Stage 2.

For obtaining expected link costs we define a “history vector” φ_j^rh that defines the expected number of links a traveller from origin r has traversed on hyperpath h for reaching node j. With (1) we obtain the expected fare stage of the traveller considering the fare stage of the upstream nodes weighted by the probability of traversing those. In (1) pa defines the link choice probability of a link a with tail node i and head node j ad π_i is probability of passing the tail node of link a. This probability is then multiplied with the shift operator as in (2) which “shifts” the fare one stage further considering that the traveler will have completed traveling link a when reaching node j. The expected link costs can then be obtained by (3).

Formel (1) siehe PDF.

Formel (2) siehe PDF.

Formel (3) siehe PDF.

Stage 1: Backward search and extracting ODs with fare depending ODs

Step 1-1: Obtain hyperpaths by backward search considering for all links their lower fare limit.

Step 1-2: Obtain link costs c_a^rh FT(φ_a^rh) for links part of the optimal hyperpath but keep all other fares at their lowest feasible value.

Step 1-3: Obtain optimal hyperpath considering link costs c^rh,

Step 1-4: Classify OD pairs into Type 1 if hyperpaths found in 1-1 and 1-3 are the same, collect all other OD pairs for further consideration.

To avoid computational complex (NP-hard) enumeration as much as possible for the remaining node pairs we distinguish nodes as to whether they are “fixed”, “passive critical” or “active critical”. Fixed nodes are those where there is no uncertainty as to the expected link cost. For example if an origin has a single outgoing link, one can be certain it will be charged by the second element in our fare vector F. Similar for links far from the origin one can be certain that the traveler will pay always the lowest fare. Critical nodes are hence nodes for which the above defined φ^rh vector has multiple non-zero entries. For a number of these nodes we know though already the optimal shortest hyperpath as from origin r to this node it is of Type 1. We refer to these as passive critical nodes. It is the remaining active critical nodes that are the main issue and for which we require a heuristic selective hyperpath generation.

In Stage 2 firstly the expected φ^r are obtained by moving forward from the origins with OD pairs not in Type 1. As noted, critical nodes can be distinguished from fixed nodes by considering their φ^rh vector. Considering then the results of Stage 1 as well we can further distinguish passive and active critical nodes. Only for active critical nodes, i.e. critical nodes that are not of Type 1 for a given origin, we need to employ a selected hyperpath generation. This consists of generating all hyperpaths that are not significantly longer than the shortest hyperpath found so far. As a threshold we consider two additional links compared to the shortest hyperpath.

Once these “gaps” of optimal hyperpaths for origins to all critical nodes has been filled a normal backward search for the shortest hyperpath can be employed where one “jumps” from critical nodes to origins by the previously found hyperpath. For further details we refer to Maadi and Schmöcker (2017).

Stage 2: Selective hyperpath generation and backward search for Type 2 and 3 ODs Step 2-1: Obtain φ^r by moving forward from all origins with OD pairs in Type 2 or 3.

Step 2-2: Classify nodes into fixed, passive and active critical based on φ^r as well as results of optimal hyperpaths obtained in Stage 1.

Step 2-3: see PDF

Step 2-4: see PDF

Step 2-5: see PDF

4 Implementation into transit assignment

4.1 Network representation

In Figure 2 we illustrate a transit network consisting of three stations where Stations 1 and 3 have one platform and Station 2 two. We require two node and four link types to represent the idea of travelers using “optimal strategies”. The stop nodes represent platforms of stations where the traveler waits for the service. The passengers who want to board or alight do so by traversing the line specific alighting-boarding nodes. Therefore the hyperpath split occurs at the stop nodes where we assume that passengers split to lines according to the line frequencies of those links that are in their optimal hyperpath.

There are four types of links connecting these two node types. The boarding (alighting) links are used by travelers boarding (alighting) at the current station, on-board links by those who continue their trip or start their trip at this station. The walking links connect the different platforms of one station. Fares are applied to the on-board links according to the hyperpath of the traveler whereas walking links are not charged. As will explained in the following congestion is considered in the form of modified frequencies associated with the boarding links.

Figure 2. Network representation of 3 stations with 4 platforms and 2 transit lines

4.2 Notation

IT:      Set of nodes in the transit network, S U AB = IT

AT:     Set of links in the transit network, bo U al U w U ob = AT

S:       Set of stop nodes in the transit network

AB:    Set of alighting and boarding nodes in the transit network

bo:     Set of boarding links in the transit network

al:      Set of alighting links in the transit network

w:      Set of walking links in the transit network

ob:    Set of on-board links in the transit network

4.3 Modification of the non-additive hyperpath approach for transit networks

The approach discussed in Section 3 requires a few modifications to be applicable for the above introduced network notation. Firstly φ needs to be only updated according to line frequencies for boarding links. For on-board links all elements of φ can be shifted and for alighting and walking links φ of the head node takes the same value as for the tail node since no fares are charged. This is expressed in Eq. (4). Further since fares only apply to on-board links this also has to be considered as in (5).

Formel (4) siehe PDF.

Formel (5) siehe PDF.

Further to obtain critical nodes required in Stage 2 of the algorithm for OD pairs not of Type 1 link types do not have to be distinguished as passengers are only charged for movement between stations. Therefore the network can be collapsed into a simpler form with one node representing a station and links connecting stations if there is a transit line connecting these.

4.4 Congested transit assignment

To consider congestion effects and to illustrate the effect of non-additive fares in such networks, we implement the “effective frequency” approach as proposed in De Cea and Fernandez (1993). Depending on link flows the frequencies of boarding links are thereby updated. The higher the boarding demand compared to available spaces the lower the frequency of a line at a node. The rationale is that the more flow there is on a link, the higher the chance of potentially missing a connection and therefore the waiting time increases. For more details, including stability properties we refer the reader to the original paper or the chapter on congested transit assignment in Gentile and Nökel (2016).

To obtain a user equilibrium assignment the approach is embedded in the Method of Successive Averages (MSA) where the effective frequencies vary in each iteration and hence also the optimal hyperpaths might change.

5 London Case Study

The proposed algorithm has been applied to the congested center zone of London network in order to show the applicability of our approach for large scale networks where passengers have various choices for getting to their destinations. In addition to run time issues, selecting the central area only appears sufficient for the purposes in this paper as in the outer zones there are less route choices and further long trips on a line will not be affected by the fare structures discussed in this paper. The network shown in Figure 3 is hence used. It consists of 56 stations (75 stop nodes by considering platforms) and 11 transit lines. Stations at the boarder of the network such as e.g. “Piccadily North” are created in order to accumulate all demand coming into the central area from the northern part of London. For further discussion we refer to Schmöcker (2006) who used the same network. OD demand data are obtained from the Rolling Origin and Destination Survey (RODS) by London Underground Limited (2005).

Figure 3. The center of London network used for the case study

We consider four fare structures and run at least five MSA iterations for each fare structure scenario. The flow for a selected number of links with the highest load of each line are shown in Table 3.

In the first fare scenario, travel costs are set to zero. We then introduce marginal fares in the other three scenarios. In scenarios 2 and 3 there are no big jumps in the fare depending on links traversed. We observe some changes in link flows though no large jumps. This is different in Scenario 4 where we define a scenario where only the first links are charged significantly and subsequent links are heavily discounted. This means that in effect, especially compared to fare Scenario 3 where all links are charged at least ten units, longer trips are encouraged as the fare charged on the later links of a journey are low. We observe that the flow on the Warren St to Oxford St link reduces significantly as passengers trade off longer routes with congestion effects.

Table 3. Links flows for selected links with different non-additive fare structures

6 Conclusions

In this paper we discussed the problem of non-additive distance based fares for transit assignment. We illustrated the problem and discussed the difficulty of transit assignment models dealing with such fare structures. We noted that these fare structures are only common in some cities but suggest that in future, with fares based on passenger tracking, such fare structures might further increase. We then discuss a solution approach where expected fares of hyperpaths are calculated considering these non-additivities. Key to the approach is the idea to firstly determine for which OD pairs the hyperpaths change if one consider the marginal fare effects. We aim to minimize this group as for only these OD pairs a “Stage 2” approach is required which partly utilizes selective enumeration techniques between origins and what we refer to as “critical nodes”. The encouraging news is that we find that for transit networks such as London the number of OD pairs which need to enter Stage 2 is only around 1 to 2% of all OD pairs.

We implement the approach into a congested transit assignment model and illustrate how fare structures can influence route flows and be a potential demand management tool. In further work we will extend our case study as well as aim to derive more conclusions for which types of networks non-additive fares are useful. We further aim to expand the approach presented here in a number of directions. For one, we aim to replace the “global fare structure” with one that can consider that fares can vary between lines as is the case in Japan or that there zones with non-additive fares. We further aim to replace the fact that fares depend on link numbers traversed with a more directly distance-based fare. The main challenge for this is that then the “history vector φ” should then not be a vector but a continuous function.

References

[1]  Constantin, I. and D. Florian. 2015. Integrated fare modelling with strategy-based transit assignment, 13th Conference on Advanced Systems in Public Transport, CASPT2015, Rotterdam, Netherlands.

[2]  Gentile, G. and Nökel, K. 2016. (Editors). Modelling Public Transport Passenger Flows in the Era of Intelligent Transport Systems. Final Report of COST Action TU1004 (TransITS). Springer.

[3]  Lo, H. K., Yip, C. W. and K. H. Wan. 2003. Modeling transfer and non-linear fare structure in multi-modal network, Transportation Research Part B, 37(2), 149–170.

[4]  Maadi, S. and Schmöcker, J.-D. 2017. Optimal Hyperpaths With Non-Additive Link Costs. Working Paper.

[5]  PTV (2013). Using Fares in Headway-Based Public Transport Assignment. Memo to VISUM users. Unpublished.

[6]  Spiess, H. and M. Florian. 1989. Optimal strategies: a new assignment model for transit networks, Transportation Research Part B, 23(2), 83-102.

[7]  De Cea, J. and Fernández, E. 1993. Transit assignment for congested public transport system: An equilibrium model. Transportation Science, 27(2), 133-147.

[8]  Schmöcker, J.-D. 2006, Dynamic Capacity Constrained Transit Assignment, PhD thesis, Centre for Transport Studies, Department for Civil and Environmental Engineering, Imperial College London, London, UK

[9]  London Underground Limited 2005. Research Brief London Underground Rolling Origin and Destination Survey (RODS). London Underground Limited, Unpublished Report.