This post is a description of a graph structure for a transit network, used for static, link-based, frequency-based assignment. Our focus is the classic algorithm "Optimal strategies" by Spiess & Florian [1]. This assignment algorithm has been implemented in AequilibraE package, a comprehensive Python package for transportation modeling that offers a wide array functionalities and features.

Let's start by giving a few definitions:

system of transport for passengers by group travel systems available for use by the general public unlike private transport, typically managed on a schedule, operated on established routes, and that charge a posted fee for each trip.

  • transit network: a set of transit lines and stops, where passengers can board, alight or change vehicles.

  • assignment: distribution of the passengers [demand] on the network [suppl], knowing that transit users attempt to minimize total travel time, time or distance walking, time waiting, number of transfers, fares, etc...

  • static assignment : assignment without time evolution. Dynamic properties of the flows, such as congestion, are not well described, unlike with dynamic assignment models.

  • frequency-based [or headway-based] as opposed to schedule-based : schedules are averaged in order to get line frequencies. In the schedule-based approach, distinct vehicle trips are represented by distinct links. We can see the associated network as a time-expanded network, where the third dimension would be time.

  • link-based: the assignment algorithm is not evaluating paths, or any aggregated information besides attributes stored by nodes and links. In the present case, each link has an associated travel time c [s] and frequency f [1/s].

We are going at first to describe the input transit network, which is mostly composed of stops, lines and zones.

Elements of a transit network

Transit stops and stations

Transit stops are points where passenger can board, alight or change vehicles. Also, they can be part of larger stations:

208088240-38e72a88-569e-4b12-a3df-9bc1fb1a4e62

In the illustration above, two distinct stops, A and B, are highlighted, both affiliated with the same station [depicted in red].

Transit lines

A transit line is a set of services that may use different routes, decomposed into segments.

Transit routes

A routes is described by a sequence of stop nodes. We assume here the routes to be directed. For example, we can take a simple case with 3 stops:

208088742-2c51a9f5-298c-4a1a-af10-edcde6437d0c

In this case, the L1 line is made of two distinct routes:

  • ABC
  • CBA.

Various configurations are possible, such as:

  • a partial route at a given moment of the day: AB,
  • a route with an additional stop : ABDC
  • a route that does not stop at a given stop: AC

208088800-5f65028f-8040-49bb-89d7-ad81b013538b

Lines can be decomposed into multiple sub-lines, each representing distinct routes. For the given example, we may have several sub-lines under the same commercial line [L1]:

line idcommercial namestop sequenceheadway (s)
L1_a1L1ABC600
L1_a2L1ABDC3600
L1_a3L1AB3600
L1_a4L1AC3600
L1_b1L1CBA600

Headway, associated with each sub-line, corresponds to the mean time range between consecutive vehicles—the inverse of the line frequency used as a link attribute in the assignment algorithm.

Line segments

A line segment represents a portion of a transit line between two consecutive stops. Using the example line L1_a1, we derive two distinct line segments:

line idsegment indexorigin stopdestination stoptravel_time (s)
L1_a11AB300
L1_a12BC600

Note that a travel time is included for each line segment, serving as another link attribute used by the assignment algorithm.

Transit assignment zones and connectors

To effectively assign passengers on the network, expressing demand between regions is crucial. This is achieved by first decomposing the network area into a partition of transit assignment zones, as illustrated below with 4 non-overlapping zones:

208088960-bd088858-ef7b-43e5-86bc-341eb8f6e7b0

The demand is then expressed as a number of trips from each zone to every other zone, forming a 4 by 4 Origin/Destination [OD] matrix in this case.

Additionally, each zone centroid is connected to specific network nodes to facilitate the connection between supply and demand. These connection points are referred to as connectors.

208089058-a735d969-5f13-4ab4-b983-2c637e865aa4

With these components, we now have all the elements required to describe the assignment graph.

The Assignment graph

Link and node types

The transit network is used to generate a graph with specific nodes and links used to model the transit process. Various link types and node categories play crucial roles in this representation.

Link types:

  • on-board
  • boarding
  • alighting
  • dwell
  • transfer
  • connector
  • walking

Nodes types:

  • stop
  • boarding
  • alighting
  • od
  • walking

To illustrate, consider the anatomy of a simple stop:

208089118-72766743-ce62-4f25-8296-026a8f9657b5

Waiting links encompass boarding and transfer links. Each line segment is associated with a boarding, an on-board and an alighting link.

Transfer links enable to compute the passenger flow count between line couples at the same stop:

208089209-885dd6ac-f3e6-43e0-b8ff-f548a375aec9

These links can be extended between all lines of a station if an increase in the number of links is viable.

walking links connect stop nodes within a station, while connector links connect the zone centroids [od nodes] to stop nodes:

208089273-6ab4c267-7591-4f77-a1c1-88d072927061

Connectors that connect od to stop nodes allow passengers to access the network, while connectors in the opposite direction allow them to egress. Walking nodes/links may also be used to connect stops from distant stations.

Link attributes

The table below summarizes link characteristics and attributes based on link types:

link typefrom node typeto node typecostfrequency
on-boardboardingalightingtrav. time$\infty$
boardingstopboardingconst.line freq.
alightingalightingstopconst.$\infty$
dwellalightingboardingconst.$\infty$
transferalightingboardingconst. + trav. timedest. line freq.
connector od or stop od or stoptrav. time$\infty$
walking stop or walking stop or walkingtrav. time$\infty$

The travel time is specific to each line segment or walking time. For example, there can be 10 minutes connection between stops in a large transit station. Constant boarding and alighting times are applied uniformly across the network, and dwell links have constant cost equal to the sum of the alighting and boarding constants.

Additional attributes can be introduced for specific link types, such as:

  • line_id: for on-board, boarding, alighting and dwell links.
  • line_seg_idx: the line segment index for boarding, on-board and alighting links.
  • stop_id: for alighting, dwell and boarding links. This can also apply to transfer links for inner stop transfers.
  • o_line_id: origin line id for transfer links
  • d_line_id: destination line id for transfer links

In the next section, we will explore a small classic transit network example featuring four stops and four lines.

A Small example : Spiess and Florian

This illustrative example is taken from Spiess and Florian [1]:

208089367-5e636a8e-c133-425d-bc7c-0c9b4af7a038

Travel time are indicated on the figure. We have the following four distinct line characteristics:

line idrouteheadway (min)frequency (1/s)
L1AB120.001388889
L2AXY120.001388889
L3XYB300.000555556
L4YB60.002777778

Passengers aim to travel from A to B, prompting the division of the network area into two distinct zones: TAZ 1 and TAZ 2. The assignment graph associated with this network encompasses 26 links:

208089460-913526d1-fd40-4ed8-b1a3-65cf264de336

Here is a table listing all links :

link idlink typeline idcostfrequency
1connector0$\infty$
2boardingL100.001388889
3boardingL200.001388889
4on-boardL11500$\infty$
5on-boardL2420$\infty$
6alightingL20$\infty$
7dwellL20$\infty$
8transfer00.000555556
9boardingL200.001388889
10boardingL300.000555556
11on-boardL2360$\infty$
12on-boardL3240$\infty$
13alightingL30$\infty$
14alightingL20$\infty$
15transferL300.000555556
16transfer00.002777778
17dwellL30$\infty$
18transfer00.002777778
19boardingL300.000555556
20boardingL400.002777778
21on-boardL3240$\infty$
22on-boardL4600$\infty$
23alightingL40$\infty$
24alightingL30$\infty$
25alightingL10$\infty$
26connector0$\infty$

Transit graph specificities in AequilibraE

The graph creation process in AequilibraE incorporates several edge types to capture the nuances of transit networks. Notable distinctions include:

Connectors :

  • access connectors directed from od nodes to the network
  • egress connectors directed from the network to the od nodes

Transfer edges :

  • inner transfer: Connect lines within the same stop
  • outer transfer: Connect lines between distinct stops within the same station

Origin and Destination Nodes :

  • origin nodes: represent the starting point of passenger trips
  • destination nodes: represent the end point of passenger trips

Users can customize these features using boolean parameters:

  • with_walking_edges: create walking edges between the stops of a station
  • with_inner_stop_transfers: create transfer edges between lines of a stop
  • with_outer_stop_transfers: create transfer edges between lines of different stops of a station
  • blocking_centroid_flow: duplicate OD nodes into unconnected origin and destination nodes in order to block centroid flows. Flows starts from an origin node and ends at a destination node. It is not possible to use an egress connector followed by an access connector in the middle of a trip.

Note that during the assignment, if passengers have the choice between a transfer edge or a walking edge for a line change, they will always be assigned to the transfer edge.

This leads to these possible edge types:

  • on-board
  • boarding
  • alighting
  • dwell
  • access_connector
  • egress_connector
  • inner_transfer
  • outer_transfer
  • walking

Here is a simple example of a station with two stops, with two lines each:

  • walking edges only:

with_walking_only

  • inner transfer edges, but no outer transfer ones:

with_inner_transfer

  • both inner and outer transfer edges:

with_inner_and_outer_transfer

As an illustrative example, if we build the graph for the city of Lyon France [GTFS files from 2022] on a given day, we get 20196 vertices and 91107 edges, with with_walking_edges=True, with_inner_stop_transfers=True, with_outer_stop_transfers=True and blocking_centroid_flow=False. Here is the distribution of edge types:

Edge typeCount
outer_transfer27287
inner_transfer10721
walking9140
on-board7590
boarding7590
alighting7590
dwell7231
access_connector6979
egress_connector6979

and vertex types:

Vertex typeCount
alighting7590
boarding7590
stop4499
od517

References

[1] Heinz Spiess, Michael Florian, Optimal strategies: A new assignment model for transit networks, Transportation Research Part B: Methodological, Volume 23, Issue 2, 1989, Pages 83-102, ISSN 0191-2615, https://doi.org/10.1016/0191-2615(89)90034-9.