#  Planning and optimizing transit lines

Marie Schmidt University Würzburg, Würzburg, Germany
<EMAIL_ADDRESS>
Anita Schöbel, University Kaiserslautern-Landau and
Fraunhofer ITWM, Kaiserslautern, Germany
<EMAIL_ADDRESS>

##### Abstract

For all line-based transit systems like bus, metro and tram, the routes of the
lines and the frequencies at which they are operated are determining for the
operational performance of the system. However, as transit line planning
happens early in the planning process, it is not straightforward to predict
the effects of line planning decisions on relevant performance indicators.
This challenge has in more than 40 years of research on transit line planning
let to many different models. In this chapter, we concentrate on models for
transit line planning including transit line planning under uncertainty. We
pay particular attention to the interplay of passenger routes, frequency and
capacity, and specify three different levels of aggregation at which these can
be modeled.

Transit line planning has been studied in different communities under
different names. The problem can be decomposed into the components _line
generation_ , _line selection_ , and _frequency setting_. We include
publications that regard one of these individual steps as well as publications
that combine two or all of them. We do not restrict to models build with a
certain solution approach in mind, but do have a focus on models expressed in
the language of mathematical programming.

##### Keywords

transit, line planning, public transport, passenger, model, integer
programming

##  1 Introduction

##### What is transit line planning?

Colloquially speaking, transit line planning is to decide which public
transport lines are to be established when the stops or stations and possible
direct connections between them are already known, and demand between these
can be estimated. More precisely, the decisions concern the number of lines to
be established, their routes and the frequencies with which they should be
operated. The result is a line plan together with the frequencies of the
lines. The lines themselves can be depicted on a map, as, e.g., the well-known
map of the London underground. As an example, a map of the line plan of the
city of Berlin (including _U-Bahn_ and _S-Bahn_ lines operational in 2009) is
shown in Figure 1.

Figure 1: A possible visualization of the line plan of the city of Berlin

##### Relevance of transit line planning.

Designing a network of transit lines and deciding upon their frequencies is a
core process in transit planning. The decision on which locations are
connected by direct lines can have a big impact on mobility patterns in the
considered region. In schedule-based transportation, transit line planning
sets the ground for the subsequent steps such as timetabling, vehicle- and
crew scheduling, delay management and others. As such, transit line planning
is considered the basis for the public transport supply and the decisions
taken at this planning stage as fundamental for most performance indicators
(such as efficiency, emissions, costs). In particular in a metropolitan area,
a transit network coordinates different modes such as buses, light rail,
trams, or metros.

Nevertheless, line planning is a relevant problem also for railway
applications. We hence also refer to some papers which are formulated in the
railway context.

##### Different names - clarification.

Transit line planning has mostly been researched in _transport engineering_
and in _operations research_. This explains a hodgepodge of subproblems and
variations with different names and notations. In order to give a systematic
view, we split transit line planning into three subproblems (see Figure 2)
showing the overlap of TNDP and line planning. The three subproblems of
_transit line planning_ are:

Figure 2: Subproblems of transit line planning and their combinations

  1. 1.

_Line generation_ : a set of candidate lines is constructed. The result is the
_line pool_.

  2. 2.

_Line selection_ : From a given line pool, the lines to be established are
selected. The result is the _line plan_.

  3. 3.

_Frequency setting_ : Frequencies are assigned to the selected lines. The
lines together with the frequencies are called _line concept_.

The _transit (route) network design problem (TNDP)_ (also called (TRNDP))
mostly researched in transport engineering, covers the subproblems line
generation and line selection. A line pool as intermediate result is not
needed in the TNDP. Frequency setting is left as separate step after the lines
have been decided. The problem that integrates line generation, line
selection, and frequency setting is known as _transit network design and
frequency setting (TNDFS)_ in the transport engineering community, see, e.g.,
Pternea et al.,  (2015); Jha et al.,  (2019).

The term _line planning_ , mostly used in operations research, integrates the
subproblems line selection and frequency setting. As input, most researchers
assume a line pool as given. There are also publications in which the lines
are constructed from scratch within the line planning problem, e.g.,
Borndörfer et al.,  (2007); Heinrich et al.,  (2022). Such models integrating
line generation, line selection and frequency setting are in operations
research called _line planning with the full pool_ , since _all_ possible
lines can be selected in this setting.

_Line planning with the full pool_ and _transit network design and frequency
setting (TNDFS)_ are hence synonyms for the integration of all three
subproblems. In this paper we use the notation _transit line planning_
whenever line generation, line selection, frequency setting or a combination
of them is involved.

##### Development of transit line planning.

The first paper on transit line planning we are aware of is Patz,  (1925),
published a century ago. Although dealing with the same type of problem, there
has been little overlap between the literature in the transport engineering
and operations research communities in the early years. Nevertheless, both
communities mention only single papers from the 60s, while research on the
topic started in the 70s and evolved to numerous papers in the 90s and in the
first decade of this century. Since then, research on transit line planning
has continued and the overlap between the communities has continuously
increased.

Several surveys exist, most of them from more than a decade ago: The survey
Schöbel,  (2012) is mainly on line planning (line selection and frequency
setting) while the surveys Ceder and Wilson,  (1986); Guihare and Hao,
(2008); Kepaptsoglou and Karlaftis,  (2009); Farahani et al.,  (2013); Cancela
et al.,  (2015) are mainly about the transit network design problem (TNDP).
The recent survey by Durán-Micco and Vansteenwegen,  (2022) concentrates on
developments in TNDP und TNDFS since 2009. In this chapter we concentrate on
modeling aspects of transit line planning including transit line planning
under uncertainty. Moreover, we specify three aggregation levels and classify
approaches with respect to them.

In contrast to vehicle and crew scheduling, algorithms for transit line
planning are still not commonly used in commercial software systems, as
mentioned, e.g., in Durán-Micco and Vansteenwegen,  (2022); Migl et al.,
(2024). This is about to be changed. In the open-source research library
LinTim, see Schiewe et al.,  (2024), many algorithms and data sets for transit
line planning are available and the method of Gatt et al.,  (2022) is
currently further developed for the use in the professional Heurès software of
Lumiplan,  (2023).

##### Embedding of transit line planning in the planning horizon.

The planning process in transit is normally divided into several stages where
the output of a stage serves as input to the subsequent stage, see Figure 3
which can be found in similar form in many papers from the 1980s to now, see,
e.g., Ceder and Wilson,  (1986); Li et al.,  (2023).

Figure 3: The planning process in public transportation.

The first stage within the planning horizon, _infrastructure location
decisions_ , decides about stops and their direct connections. It is followed
by _transit line planning_ , which is the focus of this chapter. In _schedule-
based_ operations, the next planning stages are _timetabling_ specifying the
exact departure and arrival times for the transit lines, and _vehicle
scheduling_ assigning vehicles to trips. In a _line-pure schedule_ , each
vehicle is assigned to one line which it serves back and forth the whole day.
_Crew scheduling_ is the next stage. In _headway-based_ transportation (also
referred to as _schedule-free_ transportation), operations are not meant to
adhere to fixed timetables, but only the headway of a line is known, i.e., the
time between two subsequent departures. Passengers hence go to a stop and wait
there for their bus coming.

Other planning steps include crew rostering Caprara et al.,  (1998) or fare
setting Otto and Boysen,  (2017); Hamacher and Schöbel,  (2004).

##### Solution approaches for transit line planning.

Transit line planning invites a variety of solution approaches, spanning from
_construction heuristics_ , _metaheuristics_ , and _mixed-integer programming_
approaches to _game theoretic_ approaches. Since this chapter is mainly about
_models_ , we recommend Kepaptsoglou and Karlaftis,  (2009) to learn more
about transit line planning _heuristics_ , including early contributions. The
review papers Iliopoulou et al.,  (2019); Durán-Micco and Vansteenwegen,
(2022) give a good overview on transit line planning with metaheuristics. For
a game theoretic approach we refer to Schiewe et al.,  (2019).

There is also a stream of research aiming to derive optimal frequencies for
transit lines analytically by continuum approximation, starting with the
research by Mohring,  (1972) on a single line and later been extended to
spatially diversified demand, compare, e.g., Jara-Díaz and Gschwender, 2003b ;
Fielbaum et al.,  (2016). This class of models with parametric descriptions of
network structure and demand is described in Section 5.4.

##### Remainder of this chapter.

Section 2 describes the basic notation, introduces a first line planning model
and discusses modeling of the fundamental elements: line pool and frequencies.
The section also covers performance indicators for transit line planning.
Passengers play an important role in line planning. Their routes relate the
three key concepts _frequency_ , _capacity_ , and _demand_. This relation, and
the many modeling approaches for routing passengers within transit line
planning are discussed and classified in Section 3. Section 4 describes how
uncertainty can be incorporated by robust and stochastic transit line planning
models. We treat uncertainty of demand, of driving times and link failures.
Extensions and related problems are discussed in Section 5. This includes the
skip-stop problem, seasonal demand, the integration with other planning stages
and parametric transit line planning as well as a sketch of other interesting
related problems. We conclude the chapter in Section 6.

##  2 Basic modeling considerations for transit line planning

In the following we first introduce the basic notation needed and specify the
variables and the general goals of transit line planning in Section 2.1. With
this notation it is already possible to present the basic feasibility
constraints and a first model as a building block for possible extensions in
Section 2.2. Modeling the line pool is treated in Section 2.3 and different
ways of modeling the frequencies are shown in Section 2.4.

###  2.1 Basic notation, variables and general goals

Many different versions of the transit line planning problem have been
formulated in the literature. So there is not a single ’transit line planning
model’, but there are many models for each of the subproblems line generation,
line selection and frequency setting or for their combinations. They differ in
the level of accuracy in which they model important aspects like demand or
cost, but also in the objective function and in their constraints.

To formally define a line, we first need a model for the underlying
infrastructure.

###### Notation 2.1

The _public transportation network (PTN)_ $G=(V,A)$ consists of nodes $V$
which represent stops or stations and of links (also called _arcs_) $A$ which
represent direct (i.e., non-stop) connections between stops. Link labels in
the PTN represent distance which can be measured as physical distance in
meters or as travel time in minutes.

A _line_ corresponds to a path in the public transport network $G$. In the
basic transit line planning models, it is assumed that the line stops at every
node of the path. The line generation problem constructs a _line pool_
$\mathcal{L^{\textup{Pool}}}$ of candidate lines. The goal of the line
selection problem is to select lines to be operated from the line pool
$\mathcal{L^{\textup{Pool}}}$. We refer to the subset of selected lines
$\mathcal{L^{*}}\subset\mathcal{L^{\textup{Pool}}}$ as _line plan_. Sometimes,
binary _indicator variables_ $y_{l}\in\\{0,1\\}$,
$l\in\mathcal{L^{\textup{Pool}}}$ are used to model which lines are selected.

The frequency $f_{l}$ of a line $l$ denotes how often the line is operated per
time period $T$ (often: per hour) and is usually required to be a natural
number. The frequency of a line has a crucial impact on cost (km driven,
number of vehicles needed, number of crew members needed) and service level
(expected waiting time, capacity per hour). For a given line plan
$\mathcal{L^{*}}$, the _frequency setting problem_ determines frequencies to
operate the already selected lines $l\in\mathcal{L^{*}}$. Let
$(f_{l})_{l\in\mathcal{L^{*}}}$ be the vector which contains the frequencies
of all lines $l\in\mathcal{L^{*}}$. A line plan
$(\mathcal{L^{*}},(f_{l})_{l\in\mathcal{L^{*}}})$ together with its vector of
frequencies is called a _line concept_.

The _line planning problem_ (see Figure 2) asks for a line concept, i.e., for
both the lines and their frequencies. These two subproblems can be modeled
integratedly by using the frequency vector
$(f_{l})_{l\in\mathcal{L^{\textup{Pool}}}}$ for _all_ lines
$l\in\mathcal{L^{\textup{Pool}}}$. $f_{l}=0$ means that line
$l\in\mathcal{L^{\textup{Pool}}}$ is not selected, i.e.,

$\mathcal{L^{*}}:=\\{l\in\mathcal{L^{\textup{Pool}}}:f_{l}>0\\}.$

The variables $y_{l}$ may not be needed in this integrated setting, but can be
obtained by using $y_{l}=1$ if and only if $f_{l}>0$.

For evaluating a line concept, performance indicators can be split into two
groups:

  * •

_demand-centered indicators_ can be coverage, travel time, directness, or the
number of connections per hour. Their general tendency is that ’more is
better’, i.e., increasing lines, frequency, or capacity normally has a
positive effect on these indicators.

In order to evaluate demand-related indicators, we assume that for every pair
$(s,t)$ with $s,t\in V$ it is known how many passengers $\textup{OD}_{s,t}$
wish to travel from station $s$ to station $t$. The corresponding matrix
$\textup{OD}=\left(\textup{OD}_{st}\right)_{(s,t)\in V\times V}$ is called
_OD-matrix_. $\mathcal{O}\mathcal{D}=\\{(s,t)\in V\times
V:\textup{OD}_{s,t}>0\\}$ denotes the set of origin-destination (OD) pairs.

  * •

_supply-centered indicators_ include emissions and different types of cost,
e.g., related to distance driven, or vehicles or crew needed. Here, the
heuristic principle ’less is better’ holds, as every additional line or
frequency increases cost and emissions.

For computing supply-centered indicators we assume that costs or emissions can
be estimated. This includes costs/emissions per kilometer traveled, dependent
on the vehicle type used, and costs per hour traveled reflecting, e.g., cost
for the driver or conductor.

All transit line planning models need to find a balance between these two
groups of indicators and integrate them at least in a basic way.

It is important to note that the evaluation of a line plan can only be a
(rough) estimate of the actual realization of cost and quality: As long as
only the line plan and the frequencies of the lines are known, the cost and
the travel times cannot be computed exactly, but only estimated since travel
time depends on the timetable and cost depends on the vehicle- and crew
schedules. This gives room for different performance indicators described in
more detail in Section 2.5.

###  2.2 A basic line planning model

We start with one of the simplest integer linear programming models from the
literature, compare, e.g., Schöbel,  (2012). It solves the line selection and
frequency setting problems integratedly (with a given line pool) and hence
belongs to the class of line planning models.

##### Basic feasibility constraint.

The following basic feasibility constraints are part of most transit line
planning models. Let $\mathcal{L^{\textup{Pool}}}$ be the given line pool. As
decision variables we use the frequencies $f_{l}$ for
$l\in\mathcal{L^{\textup{Pool}}}$. We require them to be non-negative and
integer. A frequency of $f_{l}=0$ means that line $l$ is not operated. The
basic feasibility constraints are

$\displaystyle L_{a}\ \ \leq\sum_{l\in\mathcal{L^{\textup{Pool}}}:l\ni
a}f_{l}\ \ \leq\ \ U_{a}$ $\displaystyle\forall{a}\in A$ (1) $\displaystyle
f_{l}\in\mathbb{N}_{0}\ \ $ $\displaystyle\forall
l\in\mathcal{L^{\textup{Pool}}}.$ (2)

The constraints (1) bound the cumulative frequency of each link $a\in A$ from
above and below. Upper bounds support the supply-centered indicators. Small
upper bounds $U_{a}$ lead typically to less expensive line concepts. The upper
bounds are often also due to the capacity of the underlying infrastructure. In
particular in rail-based systems where safety headways need to be respected,
there is a strict upper bound on the number of trips that can cross the arc
$a\in A$ in one period. But there may also be reasons to constrain the
frequencies in road-based transport, e.g., noise protection, or avoiding road
damage by over usage.

The lower bounds are due to the demand-centered indicators. They impose a
minimum cumulative frequency per link, motivated by service level or by
capacity considerations.

Finding frequencies that fulfill constraints (1) and (2) already is strongly
NP-hard, see Bussieck,  (1998) In the reduction, maximum frequencies of the
constructed instance are set to $1$, thus, the proof implies strong NP-
hardness of the line selection problem as well.

##### Basic cost model.

The basic feasibility constraints can be extended to the following line
planning model which is often used as reference or to show new developments.

Let $\textup{OD}_{s,t}$ specify the number of travelers per period between $s$
and $t$, $s,t\in V$ in the PTN. In the cost model, the lower bounds $L_{a}$
for each link $a$ are determined as follows: Each OD-pair $\textup{OD}_{s,t}$
is routed along a shortest path $P_{s,t}$ in the PTN. For every link $a$,

$d_{a}:=\sum_{(s,t):a\in P_{s,t}}\textup{OD}_{s,t}$ (3)

is the number of travelers (the _traffic load_) on link $a$. Let $C$ be the
(constant) capacity of the vehicles. Then,
$L_{a}:=\lceil\frac{d_{a}}{C}\rceil$ is the minimum number of vehicles needed
per period along link $a$ to ensure that all passengers can travel on a
shortest path $P_{s,t}$.

Let $c_{l}$ be the cost of line $l\in\mathcal{L^{\textup{Pool}}}$. It is often
assumed that it is composed by a constant fixed cost and costs related to the
length of the line and the time needed for a complete round-trip. Then the
_basic cost model_

$\displaystyle\min\textup{cost}((\mathcal{L^{\textup{Pool}}},f))$
$\displaystyle:=$
$\displaystyle\sum_{l\in\mathcal{L^{\textup{Pool}}}}c_{l}\cdot f_{l}$ (4)
$\displaystyle\mbox{s.t. }\ \ L_{a}$ $\displaystyle\leq$
$\displaystyle\sum_{l\in\mathcal{L^{\textup{Pool}}}:l\ni a}f_{l}\ \ \leq\ \
U_{a}\ \ \forall{a}\in A$ $\displaystyle f_{l}$ $\displaystyle\in$
$\displaystyle\mathbb{N}_{0}\ \ \forall l\in\mathcal{L}$

finds a line concept with minimal cost in which all passengers can travel on
their shortest paths in the PTN. The model originally stems from Claessens et
al.,  (1998) and has been used in many other papers, e.g., Torres et al.,
(2008); Schöbel,  (2012); Friedrich et al., 2017b ; Şahin et al.,  (2020);
Schiewe et al.,  (2023).

###  2.3 Line pool generation

The basic cost model (4) is formulated with a given line pool as input.
However, the choice of a suitable line pool to use as input for the line
selection problem is non-trivial. In fact, the choice of a good line pool has
a significant impact on the quality of the line concepts, as shown in
Friedrich et al., 2017a ; Migl et al.,  (2024)

There are, to the extent of our knowledge, only few papers that study line
pool generation in isolation. Gattermann et al.,  (2017) show that the line
generation problem is (strongly) NP-hard if a set with a bounded number of
lines satisfying constraints (1) is searched.

There is a number of publications that study line pool generation together
with the subsequent transit line planning steps, i.e., the (TNDP), in a
sequential manner. In a first step, promising lines are created as paths in a
PTN, in a second step, lines are selected. The result of the first step then
is a line pool. This has been done already in the early papers by Silman et
al.,  (1974); Ceder and Wilson,  (1986), but is still used in more recent
contributions, e.g., Suman and Bolia,  (2019); Vermeir et al.,  (2021); Gioia,
(2023).

In numerous contributions that use metaheuristics for solving the TNDP, one or
several line plans are proposed, evaluated, and subsequently improved in each
iteration, see Iliopoulou et al.,  (2019); Durán-Micco and Vansteenwegen,
(2022) for an overview.

The idea of generating promising lines during the optimization process is also
gaining popularity in the operations research community, for example, by
column generation in Borndörfer et al.,  (2007); Bertsimas et al.,  (2021).
Heinrich et al.,  (2022, 2023) prove complexity results and state exact
algorithms for the TNDP on specific graph structures.

Most problem formulations for line generation work under the assumption that a
public transport system, and in particular the line pool, needs to be
constructed _from scratch_. A notable exception is Suman and Bolia,  (2019),
where preexisting lines can be replaced by new lines with same start and end
terminals under the constraint that line length may not deviate by more than a
given factor from the shortest path from start to end terminal. Having
generated all lines that fulfill these properties, they aim at choosing a
subset of them that maximizes the number of additional direct travelers. This
is modeled as a linear integer program. Friedrich et al.,  (2021) argue that
existing, manually constructed line plans often contain knowledge of transport
planners that should not be discarded lightly, and propose to use this
expertise to construct a line pool, from which lines are selected by
optimization methods. Migl et al.,  (2024) propose to generate line pools by
combining automated steps and steps that include manual choices.

###  2.4 Modeling frequencies

The basic feasibility constraints (1), (2) model frequencies by an integer
variable $f_{l}$ that represents the number of trips (or line runs) per
period.

Friedrich et al., 2018a argue that to improve memorability and practicality of
a line concept, all frequencies should be multiples of a (given) _system
frequency_ $i\geq 2$. This can be modeled by the additional constraints

$\displaystyle f_{l}=i\cdot\alpha_{l}$ $\displaystyle\leavevmode\nobreak\
\forall l\in\mathcal{L^{\textup{Pool}}}$ (5) $\displaystyle\
\alpha_{l}\in\mathbb{N}_{0}$ $\displaystyle\leavevmode\nobreak\ \forall
l\in\mathcal{L^{\textup{Pool}}}.$ (6)

An alternative approach to model frequencies is to use indicator variables
$z_{l}^{\phi}$ that take the value $1$ if line $l$ has frequency $\phi$, see,
e.g., Borndörfer and Karbstein,  (2012); Martínez et al.,  (2014); Van der
Hurk et al.,  (2016); Gatt et al.,  (2022). Let $\Phi$ be the set of all
allowed frequencies. We then can replace $f_{l}$ by
$\sum_{\phi\in\Phi}\phi\cdot z_{l}^{\phi}$. Constraints

$\displaystyle\sum_{\phi\in\Phi}z_{l}^{\phi}\leq 1$ $\displaystyle\forall
l\in\mathcal{L^{\textup{Pool}}}$ (7)

ensure that at most one frequency $\phi\in\Phi$ is assigned to each line $l$.

There are several lines of reasoning behind the choice of the set $\Phi$. When
the line plan to be constructed is supposed to serve as a basis for a regular
timetable, i.e., a timetable in which the headways between two consecutive
trips of the same line are exactly $h_{l}=T/f_{l}$, one can argue (compare,
e.g., Gkiotsalitis et al.,  (2022)) that candidate frequencies should be
divisors of $T$, so that headways and thus scheduled time points are integer.
On the other hand, only lines with frequencies that are powers of the same
base can be scheduled effectively to minimize transfer times while preserving
regularity. E.g., for a planning period of $T=60$ minutes, transfers between
two lines $l$ and $l^{\prime}$ with frequencies $f_{l}=2$ and
$f_{l^{\prime}}=4$, respectively, can be easily scheduled such that short
transfers are possible twice an hour. For line $l$ with $f_{l}=2$ and
$\tilde{l}$ with $f_{\tilde{l}}=3$, on the other hand, we can achieve at most
one short transfer if we want to preserve regularity of the schedule.

Borndörfer et al.,  (2013) propose to strengthen line planning models by
introducing the concept of _frequency configurations_ , i.e., by enumerating
which combinations of line frequencies can be chosen to fulfill constraints
(1). They show that adding such inequalities to transit line planning models
can improve their integer linear formulation and speed up computation times.

###  2.5 Transit line planning performance indicators

A multitude of demand- and supply-centered performance indicators and
combinations thereof are used to evaluate the quality of line concepts and
line plans, and (to a lesser extent) also line pools in the literature. All
indicators can be used as a constraint (both _budget_ and _service level_
constraints are common) or as (part of) the objective function of an
optimization problem.

####  2.5.1 Supply-centered indicators

A simple and common way to consider cost in transit line planning is to
introduce a cost parameter $c_{l}$ that models the operating cost for one trip
of line $l$ and is often assumed to be proportional to the length of line $l$.
Using frequency variables $f_{l}$ for a line pool
$\mathcal{L^{\textup{Pool}}}$, the total cost of a line concept can then be
computed as $\sum_{l\in\mathcal{L^{\textup{Pool}}}}c_{l}f_{l}$, as it is done
in (4). These cost are referred to as _variable_ cost, while
$\textrm{cost}^{v}_{l}$ that are related to the introduction of a new line are
referred to as _fixed_ cost. For modeling fixed cost we need the indicator
variables $y_{l}$ and receive
$\sum_{l\in\mathcal{L^{\textup{Pool}}}}\textrm{cost}^{v}_{l}y_{l}$. When
different types of vehicles are considered, these cost may depend on vehicle
type as well, compare, e.g., Gatt et al.,  (2022).

In models that do not use a given line pool but construct lines as part of the
optimization step, fixed or variable line cost can be modeled by adding up
$\textup{cost}_{a}$ of all PTN arcs $a$ contained in line $l$, i.e.,
$c_{l}:=\sum_{a\in L}\textup{cost}_{a}$ compare, e.g., (Guan et al., , 2006;
Borndörfer et al., , 2007).

Energy cost are for a fixed vehicle type in a non-mountain region proportional
to kilometers driven Sadrani et al.,  (2022). Emissions also play an
increasing role in transit planning, see, e.g, Bel and Holst,  (2018); Cheng
et al.,  (2018); Duran-Micco et al.,  (2020). They also depend on the vehicle
type and on the distance covered and can thus be modeled in the same way as
(energy) costs, compare, e.g., Beltran et al.,  (2009); Pternea et al.,
(2015); Jha et al.,  (2019); Duran et al.,  (2019); Duran-Micco et al.,
(2020). Pternea et al.,  (2015) remark that the use of electric vehicles may
require additional infrastructure such as charging stations and include the
cost of locating these into the objective function.

In absence of more intricate cost models, variable costs are also used to
estimate vehicle acquisition or maintenance cost, since these roughly
correlate with the distance driven. In order to correctly model these cost
types, an estimation of the number of vehicles to operate the line concept is
needed. This is normally done under the assumption of line-pure vehicle
schedules. In this case, the number of vehicles needed can be estimated as
$\sum_{l\in\mathcal{L^{\textup{Pool}}}}\frac{{\rm time}_{l}\cdot f_{l}}{T}$ ,
where ${\rm time}_{l}$ denotes the time needed to complete a trip and $T$ is
the period.

Pätzold et al.,  (2017) argue that the numbers of vehicles needed should
already be considered during the construction of a line pool: If the distance
covered by a line is such that the line needs (slightly less) than a multiple
of a planning period length to complete a trip forth and back, it can
immediately be employed after finalization one trip (in a line-pure vehicle
schedule), leading to higher utilization of the available rolling stock. In
the context of a subline frequency setting problem Gkiotsalitis et al.,
(2022) explicitly determine the number of vehicles for every subline based on
the length of the sublines and their frequencies. The number of vehicles
needed can then be added to the objective function. Also Canca et al.,  (2019)
and De-Los-Santos et al.,  (2017) (in a railway context) compute the cost for
operating the vehicles based on estimated vehicle numbers.

All above-described costs (and emissions) are additive at the line level,
i.e., each line or line-frequency combination is attributed individually with
a cost and/or an emission value. The overall cost (or emissions) of a line
concept are then computed as sum over the cost per line.

####  2.5.2 Demand-centered indicators

Indicators for connectivity and directness from network science can be used to
analyze line plans in transit, compare, e.g., Luo et al.,  (2019); Fielbaum et
al.,  (2020). However, optimization models in transit line planning use more
specific indicators which are described in the following.

Passengers’ _travel time_ is one of the key service quality measures used in
transit line planning, and is also used in order to distribute passengers in
the network (compare Section 3.3). We distinguish between the following
_components of travel time_ :

  * •

_Driving time_ is the time spent in a driving vehicle. Usually it is computed
based on the kilometers driven and on the speed of the vehicle.

  * •

We refer to the time that a passenger spends in a standing vehicle at a stop
where she does not board or alight as _waiting time_.

  * •

_In-vehicle time_ aggregates driving time and waiting time.

  * •

The _transfer time_ is the time between arriving at a station in one vehicle,
and departing from it in a different one. In contrast to driving and waiting
time, the transfer time depends crucially on the timetable.

  * •

_Adaption time_ is the time passing between the moment that a passenger
desires to depart, and the time at which she actually departs. Adaption time
is particularly relevant in transit systems that operate with a high frequency
where passengers do not consult a timetable prior to departure. Including
adaption time into the travel time can, however, also be seen as a means to
penalize infrequent connections between highly demanded OD-pairs, as they lead
to high adaption times Hartleb et al.,  (2023).

  * •

_Access time_ is the time for walking to the first or from the last station.
It can be computed if the demand is given in districts or zones also
considering the choice of the first and last station into the route choice
decisions, compare dell’Olio et al.,  (2006); Shimamoto et al.,  (2012); Szeto
and Jiang,  (2014); Klier and Haase,  (2015). It is often neglected in transit
line planning.

Many line planning papers use travel time or its components as objective
function or as service level constraint. Some models minimize a _weighted sum_
of the components, as it has been shown that the value of different time
components is different in the passengers’ perception, see, e.g., Wardman,
(2004). When the sum over all passenger travel times is used as an objective,
this is normally combined with requiring that all passengers must be
transported, because not transporting a passenger would lead to a reduction in
travel time.

Besides travel time, _coverage_ is a second important demand-related
performance indicator in transit line planning. The definition of coverage
boils down to the question of how many passengers of all OD-pairs are going to
travel by transit.

Many transit line planning models implicitly assume that a _system split_
(see, e.g., Oltrogge,  (1994)) is precomputed. That is, the OD passenger
numbers that are taken as input do not represent the full amount of people
traveling from origin to destination, but the fraction of them that wants to
travel by public transport. Based on such a system split, many line planning
models require full coverage, i.e., that _all_ passengers of all OD-pairs are
transported. When travel time is not considered in the objective function,
such models require that the routes provided for the passengers do not deviate
too much from shortest routes, i.e., a service level constraint with respect
to travel time is introduced to avoid that passengers with large detours, who
would in reality probably not take transit, are counted as covered.

_Direct traveler models_ consider a passenger covered if there is a line that
connects her origin to her destination without a large detour, see, e.g.
Bussieck et al.,  (1996); Bussieck,  (1998); Suman and Bolia,  (2019), while
in Bertsimas et al.,  (2021) passengers may transfer at most once.

In contrast to such approaches, in _coverage by transit_ the existence of
other modes (e.g. the private car) is recognized. Only if the travel option
using transit is good enough compared to the other existing mode, an OD-pair
is counted as covered, see, e.g., Laporte et al.,  (2007); Cadarso et al.,
(2017); Bertsimas et al.,  (2021); Klier and Haase,  (2015); Tirachini et al.,
(2014); Beltran et al.,  (2009); Laporte et al.,  (2005) This is often framed
as integrating _mode choice_ and will be explained in further detail in
Section 3.5.

In some models, instead of coverage the related indicator _revenue_ (as a
function of coverage) is used. E.g., Gkiotsalitis and Cats,  (2022); Hartleb
et al.,  (2023) consider revenue from ticket prices, which are proportional to
the distance between the passengers’ origins and destinations. De-Los-Santos
et al.,  (2017); Canca et al.,  (2019) additionally include a subsidy per
transported passenger into the revenue estimation. An advantage of using
revenue is that it can easily be aggregated with the supply-aggregated
indicator _cost_ to obtain _profit_ as an objective function.

Also _comfort_ -oriented indicators are occasionally used. To ensure passenger
satisfaction, besides a criterion on the travel time, Gatt et al.,  (2022)
require that the buses are not filled beyond a certain level. Cats and Glück,
(2019) include deteriorating comfort in the case of overcrowding into their
simulation-based evaluation of line plans and corresponding passenger routes.

In contrast to most supply-centered indicators that can be attributed to
individual lines, most of the demand-centered indicators can be decomposed per
passenger, but cannot be decomposed per line. Therefore, it is difficult or
impossible to apply them to assess individual lines. A possible approach to
evaluate individual lines from a demand perspective is to consider the
marginal benefit that the addition of a line has on an existing line concept,
compare Vermeir et al.,  (2021).

##  3 Modeling passengers and capacity

In the previous section we have shown how lines and their frequencies are
defined and can be modeled. Looking at the _demand-centered_ performance
indicators, it became clear that the routes for the passengers are crucial for
defining _coverage_ and _travel time_ indicators. Moreover, the routes of the
passengers are important to evaluate if the capacity provided by a line is
sufficient to transport all of them. We first describe three levels of detail
in which passenger routes can be modeled and aggregated: link-based, line-
based and trip-based. We then show for each of these aggregation levels how
the capacity and the passenger routes are connected in Section 3.2 and how
travel time can be estimated in Section 3.3. We finally classify the various
models for determining the passenger routes in Section 3.4 and end with some
remarks on the mode choice.

###  3.1 Modeling passenger routes in three levels of detail

We start by describing three levels of aggregation which are common. For all
of them, let OD be the OD-matrix, $\mathcal{O}\mathcal{D}$ be the set of OD-
pairs with $\textup{OD}_{s,t}>0$ for $s,t\in V$ and let $Q_{l}$ be the
capacity of vehicles operating on line $l\in\mathcal{L^{\textup{Pool}}}$.

##### Passenger routes on link level.

Here, passenger routes $P^{\textrm{PTN}}_{st}$ are determined in the PTN, that
is, a route is a sequence of links in the PTN. The link level is the least
detailed level. It neglects information about the lines the passengers use.

##### Passenger routes on line level.

Here, we determine the routes of the passengers in the PTN together with the
lines to be used. This can be efficiently done in the _Change & Go network_
CGN, originally introduced in Schöbel and Scholl,  (2006). See Figure 4 for a
small public transport network and its corresponding Change & Go network.

###### Notation 3.1

The _change-and-go network_ (CGN) $\textrm{CGN}=(N,E)$ consists of nodes which
represent station-line pairs for each line $l$ and all the stations $v$ it
passes:

$N=\\{(v,l):v\in V,l\in\mathcal{L^{\textup{Pool}}}\mbox{ and }v\in l\\}$

The arcs set consists of _transfer (=change) arcs_ and _driving (=go) arcs_

$E=\\{(a,l):=((v,l),(u,l)):a=(v,u)\in A,v,u\in
l\\}\cup\\{((u,l_{1}),(u,l_{2})):u\in l_{1}\cap l_{2}\\}$

which represent driving activities of $(a,l)$ of line $l$ on arc $a\in A$ and
possible transfer activities for passengers between lines $l_{1},l_{2}$ in
station $u$. For routing an OD-pair $(s,t)$, the CGN is extended by adding
$(s,0)$ and $(t,0)$ as nodes and connecting $(s,0)$ to all nodes $(s,l)\in N$
and $(t,0)$ to all $(t,l)\in N$. The arcs in the CGN are labeled by an
estimate of the travel time for the respective driving or transfer activity
that allows a shortest path computation for determining passenger routes.

Note that the CGN can only be built if a line pool is available.

A _route_ $P^{\textrm{CGN}}_{s,t}$ from $(s,0)$ to $(t,0)$ in the CGN
represents a path which not only contains the sequence of stations but also
the lines to be used. There exist a number of similar network models, compare,
e.g., Nguyen and Pallottino,  (1988); Cancela et al.,  (2015). Some papers use
line-based aggregation levels without the CGN, e.g. Nachtigall and Jerosch,
(2008).

##### Passenger routes on trip level.

A line $l$ with a frequency of let’s say $f_{l}=4$ consists of four _trips_
per period. Let ${\cal T}_{l}$ be the trips belonging to line
$l\in\mathcal{L^{\textup{Pool}}}$. To estimate travel time and capacity even
more accurately than on the line level, we want to specify not only the routes
but also the trips which are used on the passengers’ journeys. This is
possible if line planning is integrated with scheduling decisions. In this
case, passengers can be assigned to the specific _trip_ to be used and not
only to the line. The exact trips a passenger uses can be computed as a route
$P^{\textrm{EAN}}_{s,t}$ in the so-called _event-activity network (EAN)_ which
contains events for each arrival or departure of every trip at every station,
together with their accurate arrival and departure times. Transit line models
including timetabling and passenger routing on trip level exist, e.g., the
single corridor frequency assignment model by Sadrani et al.,  (2022), or the
model integrating line planning, timetabling, and passenger routing by
Schiewe,  (2020); Schiewe and Schöbel,  (2022), but they are computationally
hardly tractable.

###  3.2 Modeling capacity

While line generation models do usually not consider capacity considerations,
providing sufficient capacity is normally considered in line planning and in
frequency setting. The two decisions that impact the overall capacity of line
$l\in\mathcal{L^{\textup{Pool}}}$ per period are the capacity $Q_{l}$ of
vehicles serving the line and its frequency $f_{l}$. In many models, the
vehicle capacity $Q_{l}$ is considered to be given and identical for all
lines. Some models allow to choose among different line types with vehicle
capacity being one distinguishing property of different lines (besides, e.g.,
speed), or different vehicle sizes can be associated to different lines, see,
e.g., dell’Olio et al.,  (2012); Cats and Glück,  (2019); Gatt et al.,
(2022).

The main difference between models for transit line planning comes from the
level of capacity aggregation used, which should be aligned with the level of
detail used for the passenger routes. The joint determination of line
_frequencies_ and vehicle _capacities_ is common in frequency setting, as
both, increasing frequencies and increasing capacities, are means to adjust
line capacity to passenger demand. While in link-based and line-based
approaches, all vehicles of the same line have the same capacity dell’Olio et
al.,  (2012); Cats and Glück,  (2019); Gatt et al.,  (2022) it may make sense
in trip-based models to assign vehicles of different sizes to the same line,
to cater for fluctuations in demand, compare Sadrani et al.,  (2022). In the
following we formulate the relation between frequency, capacity and demand for
the three aggregation levels link-based, line-based and trip-based.

##### Link-based capacity aggregation.

For the link-based aggregation level we use the links of the PTN defined in
Notation 2.1. In this level of detail we can aggregate the frequencies of all
lines for each specific link and require that the capacity on the link is
sufficient for the passengers that use this link, independent of the specific
lines they take. Constraint

$\sum_{l\in\mathcal{L^{\textup{Pool}}}:a\in l}f_{l}\cdot
Q_{l}\geq\sum_{(s,t)\in\mathcal{O}\mathcal{D}:a\in
P^{\textrm{PTN}}_{s,t}}\textup{OD}_{s,t}=d_{a}\mbox{ for all }a\in A$ (8)

makes sure that the demand is covered on every link $a\in A$ of the PTN when
solving the line planning problem. The cost model (4) is an example which uses
the link-based aggregation.

##### Line-based capacity aggregation.

The link-based aggregation neglects which lines passengers use. Even if the
capacity on a link $a\in A$ is large enough to transport the demand $d_{a}$ it
might be possible that not all passengers can use their preferred lines. To
ensure that the capacity _per line_ is sufficient to transport all passengers
we use routes $P^{\textrm{CGN}}_{s,t}$ in the CGN and receive

$f_{l}\cdot Q_{l}\geq\sum_{(s,t)\in\mathcal{O}\mathcal{D}:(a,l)\in
P^{\textrm{CGN}}_{s,t}}\textup{OD}_{s,t}=:d_{a,l}\mbox{ for all }a\in
A,l\in\mathcal{L^{\textup{Pool}}}$ (9)

making sure that the number of passengers using line $l$ on arc $a\in A$ does
not exceed the _line capacity_ $f_{l}\cdot Q_{l}$ on every arc $a\in A$ of the
line, compare, e.g., Guan et al.,  (2006); Schöbel and Scholl,  (2006); Gatt
et al.,  (2021). In other words, it is ensured that over the whole period $T$,
capacity on each line $l$ is sufficient to transport the passengers assigned
to the line. (9) also confirms that no demand can use a line
$l\in\mathcal{L^{\textup{Pool}}}$ which is not selected, i.e.,
$l\not\in\mathcal{L^{*}}$.

##### Trip-based capacity aggregation.

When passenger routes are detailed on trip level, capacity can be modeled on a
trip level as well. That is, for each arc $a\in A$ and each trip operated on
$a$ we count the passengers that are assigned to this trip and bound their
number by the number of places in the vehicle. With ${\cal T}$ being the set
of all trips, we receive

$Q_{l}\geq\sum_{(s,t)\in\mathcal{O}\mathcal{D}:(a,l,\textup{trip})\in
P^{\textrm{EAN}}_{s,t}}\textup{OD}_{s,t}=:d_{a,l,\textup{trip}}\mbox{ for all
}l\in\mathcal{L^{\textup{Pool}}},\textup{trip}\in{\cal T}_{l},a\in A,$ (10)

The following example illustrates why trip-based capacity modeling may be
desirable.

##### Illustration.

Figure 4: The public transport network and the Change & Go network for the
illustration.

We illustrate and compare the three aggregation levels in a small example.
Consider the network with three stations, $s_{1},s_{2},$ and $s_{3}$ and three
lines $\mathcal{L^{*}}=\\{l_{1},l_{2},l_{3}\\}$ depicted in Figure 4. Assume
that 120 persons wish to travel from $s_{1}$ to $s_{3}$. We want to evaluate a
solution in which the lines $l_{1}$ and $l_{3}$ operate with a frequency of
$f_{l_{1}}=f_{l_{3}}=1$ and capacities of $Q_{l_{1}}=Q_{l_{3}}=60$ while line
$l_{2}$ runs with the double frequency of $f_{l_{2}}=2$, but only uses smaller
buses with half of the capacity, i.e., $Q_{l_{2}}=30$.

  * •

In the link-based aggregation level we determine the traffic loads of both
links $a_{1}=(s_{1},s_{2}),a_{2}=(s_{2},s_{3})\in A$ as
$d_{a_{1}}=d_{a_{2}}=120$. We receive

$\displaystyle\sum_{l\in\mathcal{L^{\textup{Pool}}}:a_{1}\in l}f_{l}Q_{l}$
$\displaystyle=$ $\displaystyle 60+60\geq 120=d_{a_{1}},$
$\displaystyle\sum_{l\in\mathcal{L^{\textup{Pool}}}:a_{2}\in l}f_{l}Q_{l}$
$\displaystyle=$ $\displaystyle 60+30+30\geq 120=d_{a_{2}},$

so on a link-based aggregation the solution is feasible with respect to (8)
although we may expect overcrowded buses on line $l_{3}$ since most passengers
would prefer a direct connection over a connection with a transfer.

  * •

The line-based aggregation would either route all passengers along line
$l_{3}$ yielding an infeasible solution since capacity of $l_{3}$ is only
limited to 60 persons. With a capacity-aware routing model, 60 persons would
use the path
$P^{\textrm{CGN}}_{1}=((s_{1},l_{3}),(s_{2},l_{3}),(s_{3},l_{3}))$ and 60
persons would be assigned to path
$P^{\textrm{CGN}}_{2}=((s_{1},l_{1}),(s_{2},l_{1}),(s_{2},l_{2}),(s_{3},l_{2}))$.
With these two paths, the capacity constraints (9) are satisfied, since

$\displaystyle f_{l_{1}}Q_{l_{1}}=60\geq 60=d_{a_{1},l_{1}},$ $\displaystyle
f_{l_{2}}Q_{l_{2}}=60\geq 60=d_{a_{2},l_{2}},$ $\displaystyle
f_{l_{3}}Q_{l_{3}}=60\geq 60=\max\\{d_{a_{1},l_{3}},d_{a_{2},l_{3}}\\}$

and the solution would be classified as feasible. However, the 60 passengers
arriving at station $s_{2}$ will all try to use the same bus of line $l_{2}$
(namely the first one that arrives) leading to an overcrowded bus — while the
next bus of line $l_{2}$ would be not used at all.

  * •

The trip-based model assigning passengers to the individual trips is the only
of these three which reflects capacity correctly in this situation: For the
trips of lines $l_{1}$ and $l_{3}$ we see that their capacities are sufficient
to transport all passengers assigned to them in one trip. However, there are
two trips (let’s say $\textup{trip}_{1}$ and $\textup{trip}_{2}$) belonging to
line $l_{2}$. All 60 passengers arriving at station $s_{2}$ with line $l_{1}$
will board the first of these two trips, say $\textup{trip}_{1}$. Then we have

$Q_{l_{2}}=30<60=d_{a_{2},l_{2},\textup{trip}_{1}},$

i.e., (10) is not satisfied.

###  3.3 Estimating passengers’ travel time

Estimating travel time is key to most demand distribution models (compare
Section 3.4): the travel time of a certain route determines how many
passengers take it, and the amount of passengers on a route in turn determines
whether capacity constraints are satisfied (compare Section 3.2). Travel time
and its components are also relevant performance indicators to evaluate a line
concept, and, as such, have been described in Section 2.5. This section
examines how travel time can be estimated based on the level of detail used.

##### Estimating travel time in case of trip-based aggregation.

An exact estimate of planned travel time can be given in presence of a
timetable. If there are no delays, the departure time of the first boarded
vehicle at the origin and the arrival time of the last vehicle of a route at
the destination can be read from the timetable. Sometimes, even denied
boarding is modeled and accounted for in the transfer and adaption time,
compare Sadrani et al.,  (2022). If the desired departure time of a passenger
was known (normally, this is not the case in line planning), also adaption
time could be computed exactly. Otherwise, it must be estimated, e.g., as in
(11).

##### Estimating travel time in case of line-based aggregation.

When passenger routes are modeled line-based, _driving time_ can be estimated
based on line speed and distance and assigned to the arcs of the CGN. In a few
models for headway-based transportation, road congestion is explicitly
modeled. E.g., Tirachini et al.,  (2014) allow passengers to choose between
different modes, where both, bus and car traffic, contribute to crowded
streets.

Sometimes, _waiting time_ is included in the in-vehicle time as a constant
supplement to the driving times, Szeto and Jiang,  (2014) assume that waiting
time depends linearly on the number of passengers already in the vehicle
(modeled as passengers assigned to the line on that link divided by the
frequency), but usually the vehicles’ stopping times are considered as
marginal and hence not included in the travel time.

In absence of a timetable, transfer times cannot be predicted exactly, but
need to be estimated. To assign transfer time as label to the CGN, the
transfer time can be approximated either by using a fixed penalty term Guan et
al.,  (2006); Schöbel and Scholl,  (2006) or by using the frequency of the
departing line. An approximation for the transfer time in the line-based model
is the average expected transfer time

$\frac{T}{2\cdot f_{l}}.$ (11)

The same formula can be used for the _adaption time_. When using binary
indicator variables, this is equivalent to
$\sum_{\phi\in\Phi}\frac{T}{2\phi}z_{l}^{\phi}$, compare, e.g., Bull et al.,
(2015); Sadrani et al.,  (2022)).

Gatt et al.,  (2022) follow the same approach when the frequency is high (more
than 6 per hour), but argue, that for low frequencies passengers will mind the
timetable to avoid adaption time and transfers will be synchronized.
Therefore, for lower frequencies they assume a transfer and adaption time of
$5$ minutes. Interestingly, a similar result also holds in the absence of
regularity constraints: Gkiotsalitis et al.,  (2022) prove that in the case of
$k$ periodically scheduled but un-synchronized (i.e.: irregular) vehicle
departures the expected adaption/waiting time to board one of them is
$\frac{T}{k+1}$, which even holds for the case of irregular departures.

##### Estimating travel time in case of link-based aggregation.

Routes that are modeled on link-based aggregation level are paths in the PTN
and hence do not encode which lines are taken. Most models (see,
e.g.,Borndörfer et al.,  (2007); Borndörfer and Karbstein,  (2012); Gatt et
al.,  (2021); Bertsimas et al.,  (2021)) assume constant line speed so that
driving times do not depend on the chosen lines and can hence be estimated
without knowing the lines used by the passengers. Transfer times are mostly
neglected in the link-based aggregation, see, e.g., Borndörfer et al.,
(2007). A possibility is to distinguish between direct routes and routes with
at least one transfer and penalize the latter ones Borndörfer and Karbstein,
(2012); Gatt et al.,  (2021); Bertsimas et al.,  (2021). In some direct
traveler models, routes in the PTN are associated with the fastest line (or
just any line) that covers the route, and a passengers’ travel time is given
between the passenger’s origin and destination, compare, e.g., Suman and
Bolia,  (2019)). In link-based aggregation, adaption time is normally not
included.

###  3.4 Modeling passengers’ route choice

To determine travel time or to evaluate the capacity constraints (8), (9), or
(10) in the different aggregation levels, passenger routes need to be
determined. To describe the many route choice models to do this, we use the
structure shown in the decision tree in Figure 5.

Figure 5: Models for passengers’ route choice and their possible aggregation
levels.

We first distinguish between approaches that distribute passengers over the
network _prior_ to the optimization step and models that aim to integrate the
route choice of the passengers into the optimization step.

##### Passenger routing _prior_ to transit line planning (node 1)

In order to distribute OD-demand prior to the construction of a line concept,
shortest-path algorithms or other assignment models, see, e.g., de Dios
Ortúzar and Willumsen,  (2011) on the PTN can be used. The predetermined
passenger distribution can be used to compute _traffic loads_ on each link of
the PTN, see (3). This is a common approach, e.g., used in Bussieck et al.,
(2004); Claessens et al.,  (1998); Goossens et al.,  (2006). Other models use
precomputed PTN-paths for the OD-pairs that need to be enabled in order to
travel, see Bussieck et al.,  (1996).

##### Passenger routing _during_ transit line planning (node 2)

We now turn to models that do not consider the passenger routes as given, but
acknowledge that they depend on the transit line planning decisions to be made
in the optimization. We distinguish between optimization models where
passengers are _assigned_ to routes by a central decision maker (node 2.1) and
models that assume that passengers choose a route by solving their own
optimization problems (e.g., a shortest route with respect to travel time).

##### Route assignment assignment by planner (node 2.1)

We first review models that aim at a _system optimum_ , i.e., the sum of
travel times (or any other performance indicator) is to be minimized by a
central decision maker who makes both decisions, on the supply (lines and
frequencies) and on the demand (passengers routes). The decision maker
optimizes _her_ objective function which is not necessarily fully aligned with
the passengers individual objective functions. I.e., such models do not forbid
to assign individual passengers to routes that are suboptimal from the
perspective of the individual passenger, if this benefits the overall
objective function. Since in this case, transit line planning reduces to a
single level problem, it can be often approached by integer-programming.

Other publications explicitly choose passenger routes during the optimization
process and will be reviewed below. For doing so, some rely on a precomputed
_candidate set_ of routes for each OD-pair, while others use _flow
constraints_.

##### Flow-based passenger modeling (node 2.1.1)

_Flow-based_ models describe the passenger routes as multi-commodity flows
between origins and destinations. This approach can be applied on all
aggregation levels for passenger routes (compare Section 3.1). That is, in the
description that follows, the term _network_ can refer to the PTN (e.g., in
Friedrich et al., 2017b ; Laporte et al.,  (2007); Cadarso et al.,  (2017)),
CGN (see, e.g., Nachtigall and Jerosch,  (2008); Schöbel and Scholl,  (2006))
or EAN (see, e.g., Schiewe and Schöbel,  (2022); Li et al.,  (2023)).

Such models use flow variables $x_{a}^{(v^{\textrm{org}},v^{\textrm{dest}})}$
that indicate how many passengers of an OD-pair
$(v^{\textrm{org}},v^{\textrm{dest}})$ travel on an arc $a$ of the network.
Flow constraints are modeled as

$\displaystyle\theta
x^{(v^{\textrm{org}},v^{\textrm{dest}})}=q^{(v^{\textrm{org}},v^{\textrm{dest}})}\
\ \forall(v^{\textrm{org}},v^{\textrm{dest}})\in\mathcal{O}\mathcal{D}$ (12)

where $\theta$ represents the node-arc incidence matrix of the network and
$q^{(v^{\textrm{org}},v^{\textrm{dest}})}$ is the number of passengers on OD-
pair $(v^{\textrm{org}},v^{\textrm{dest}})$. Models that use passenger routing
with flow constraints therefore minimize total (or, equivalently, average)
travel time. Note that passengers may be assigned to routes with long travel
time if this benefits the objective function of the model. In order to avoid
this, one can impose bounds on the maximal travel time for each OD-pair,
depending on the geographical distance of origin and destination or on the
length of a shortest route, see, e.g., Friedrich et al., 2017b .

##### Path-based passenger modeling (node 2.1.2)

As alternative to flow-based models, some models _precompute choice sets_ of
routes on link or line level for each OD-pair
$(v^{\textrm{org}},v^{\textrm{dest}})$, and assign the passengers of
$(v^{\textrm{org}},v^{\textrm{dest}})$ to one or several of these routes
during the optimization step. In most models, only routes of a certain
quality, e.g., that do not exceed the length of a shortest path by too much,
are included in the choice set. From a modeling perspective, this approach has
the advantage that passengers cannot be assigned to ’bad’ routes for the sake
of the social optimum, even if the objective function minimizes not travel
time, but, e.g., costs. On the other hand, route choice is more constrained in
these models, in particular if the choice set is small. To overcome this
problem, Borndörfer et al.,  (2007) use a column generation approach to
iteratively _generate_ suitable OD-paths in the PTN.

A challenge is that in particular in dense line pools, the number of routes
with good travel time for an OD-pair $(v^{\textrm{org}},v^{\textrm{dest}})$
can be very big. In the CGN this may happen even if there is only one path
from $v^{\textrm{org}}$ to $v^{\textrm{dest}}$ in the PTN. Therefore,
preprocessing the choice set is a promising approach. E.g., Hartleb et al.,
(2023) restrict to routes with only one transfer and set tight bounds on the
travel time.

On the contrary, Klier and Haase,  (2015) consider an even bigger choice set
where each CGN path corresponds to multiple elements - one for each possible
frequency combination for the lines used on the CGN path. This allows to
precompute travel time including frequency-dependent adaption and transfer
times.

##### Passenger route _choice_ (node 2.2)

We now review approaches that explicitly model route _choice_ of passengers.
Such models are often represented as bilevel optimization models with transit
line planning decisions (route generation, selection, and frequency setting)
on the upper level and passenger routing on the lower level.

_Solution approaches_ for these kind of models can be roughly categorized as
follows: The first class of approaches computes transit line planning
decisions and routing simultaneously, e.g., by solving a mixed-integer program
that encodes both transit network design decisions and decisions on passenger
routes in variables of the same problem. The other class of approaches follows
the hierarchy suggested by the bilevel representation and takes transit line
planning decisions first, and routing decisions second. In many heuristics and
metaheuristics this process is iterated, interpreting the computation of a
routing for a given line concept as an evaluation mechanism and using it to
guide the solution process. The first approach has the advantage that (if the
resulting models can be solved to optimality) a global optimum is found, while
the second approach can get stuck in local optima. On the other hand, the
routing models of the first approach need to be simple enough to be used
within a mixed-integer linear program, while the stepwise treatment of line
planning decisions and routing in the second approach has the advantage, that
line planning decisions are already fixed when a routing is computed, thus
more sophisticated routing models can be used.

We distinguish further by the type of problem considered on the lower level.

#####  _Independent_ route choice (node 2.2.1)

We first turn our attention to models where the routing problem of each
passenger can be formulated as an optimization problem based on the upper
level decisions, but independent of the choices of other passengers. Here, we
distinguish between models where the solutions to the lower level of
optimization problems for an individual OD-pair are _routes_ , and models
where lower level solutions are _strategies_.

##### Passengers choose _single paths_ (node 2.2.1.1)

These models are motivated by the consideration that, as soon as the decisions
on line routes and frequencies (and possibly a timetable) are taken, transfer
times and adaption times can be computed as described in Section 3.3, and
finding a travel-time minimal line-based (trip-based) route from an origin to
a destination corresponds to solving a shortest path problem in the CGN (or
the EAN).

If no capacity constraints are considered, and if the upper level objective is
the sum of the individual OD-pair objective functions of the lower level
optimization problems, in a social optimum all passengers are assigned to
individually optimal paths, and thus, the bilevel problem can be transformed
to a single level problem with route assignment by planner as described in
node 2.1, see Schmidt,  (2014). However, in general this does not hold.
Schmidt,  (2014); Goerigk and Schmidt,  (2017) remark that in the presence of
capacity constraints, the passenger routes estimated by flow constraints may
not follow shortest paths. They argue that this may lead to capacity
violations in reality, when passengers do behave rational and choose shortest
routes instead of following the routes predicted by the model. Therefore, they
propose to model transit line planning as a bilevel program, where the
operator’s objective constitutes the upper level and passengers’ route choice
(using line-based aggregation) constitute the lower level. By introducing
additional _shortest-route-indicator_ variables, or by dualizing the lower
level problem, the bilevel problem can be transferred to a mixed integer
program, which is, however, hard to solve is followed in the route-selection
based frequency setting model by Gatt et al.,  (2022) where the authors use an
optimal value function to assign passengers to the shortest path that is
enabled by the line concept.

##### Passengers choose _hyperpaths (strategies)_ (node 2.2.1.2)

The above-described passenger routing models have in common that they use
(adaption and) transfer time estimates (either frequency-based, fixed
penalties, or no transfer time) in order to compute travel-time minimal routes
and then assign passengers to these routes. Unfortunately, the travel time of
a route may deviate considerably from the estimates made.

For this reason, some authors argue that assignment of OD-pairs to routes is
not the best way to estimate passenger routes choice in line planning. The
approach that they propose is motivated by a routing paradigm for headway-
based transportation, described first as the _common lines problem_ by Chriqui
and Robillard,  (1975): When several lines could be boarded to go from origin
to destination (possibly with transfers), in absence of a timetable a
passenger would not decide prior to departure which line to take, but make her
decision depend on, e.g., which line arrives first. That is, instead of
choosing a route prior to departure, passengers choose a _strategy_ based on
the line plan, i.e., a set of rules that the user will apply in an online
fashion to travel through the system, see Spiess and Florian,  (1989).

This strategy can be represented as an acyclic directed graph or hyperpath in
a suitably chosen network (compare, e.g., Constantin and Florian,  (1995);
Shimamoto et al.,  (2012); Cancela et al.,  (2015)), where each node with more
than one outgoing arc represents a decision on how a passenger will continue
her route. Based on line frequencies, probabilities for each OD-path in the
network can be determined which allow to compute the expected travel time of a
strategy by solving a linear program, see Spiess and Florian,  (1989). This
route choice approach has been integrated as lower level problem in a bilevel
frequency setting approach Constantin and Florian,  (1995), which has been
transformed into a mixed-integer program in Martínez et al.,  (2014).

Shimamoto et al.,  (2012) use the computation of optimal strategies for the
passengers as fitness function in a metaheuristic for the TNDFS.

##### Interdependent route choice (node 2.2.2)

Lastly, there are models where the route choice of individual passengers does
not only depend on the line plan, but is also impacted by the route choice of
other passengers.

Cancela et al.,  (2015) use a bilevel model where on the lower level they
optimize all the passenger routes based on strategies simultaneously. There is
also a number of publications that formulate transit line planning with
equilibrium constraints on the lower level. To give two examples, dell’Olio et
al.,  (2012) formulate a joint frequency and bus size assignment problem as
bilevel optimization problem. They apply a metaheuristic where, on the lower
level, they use a transit assignment model proposed by De Cea and Fernández,
(1993), which leads to _equilibrium constraints_ for passenger flow modeling.
A similar model is employed in dell’Olio et al.,  (2006) for joint stop
location and frequency setting. Within a genetic algorithm, Beltran et al.,
(2009) use an equilibrium model where passengers can choose among three ways
of traveling; by car, by public transport in conventional vehicles.

Schiewe et al.,  (2019) propose a model for transit line planning with the
full pool where passengers choose their (line-based) routes based on a
weighted sum of travel time and _distributed operational cost_ , i.e., when a
passenger chooses a previously unused line or frequencies are increased, this
is more costly than choosing a route that uses already established lines and
their frequencies. They sequentially apply this routing strategy in a best-
response approach to find a line concept. A similar approach is applied in
Gioia,  (2023) for line generation.

Cats and Glück,  (2019) use _agent-based simulation_ to model lower-level
route choice in a frequency assignment problem.

###  3.5 Mode choice

While many line planning models assume that the _system split_ is precomputed
and that passenger demand is inelastic in the sense that the OD-matrix is
given and fixed and represents all passengers who travel by transit, there are
models that recognize that passengers are sensitive to the quality of transit
and aim to include _mode choice_ in transit line planning.

Some papers propose an all-or-nothing assignment: If and only if the offered
connection from origin to destination is better than an alternative mode,
passengers choose it. This includes the models which maximize coverage by
transit as performance indicator: Here, a passenger uses transit if the travel
time is smaller than a (maybe fictive) travel time in an alternative mode,
e.g., the private car, see, Laporte et al.,  (2007, 2010); Cadarso and Marin,
(2012, 2016); Cadarso et al.,  (2017). A link-wise all-or-nothing assignment
is used in Gkiotsalitis and Cats,  (2022) studying frequency assignment under
pandemic-imposed distancing measures. They allow to split passenger flows into
passengers traveling on the line segment, and passengers bridging the distance
covered by the line segment by other means.

In order to estimate the number of passengers using public transit, also
_logit models_ based on travel time have been used. De-Los-Santos et al.,
(2017) use a piecewise linearization of the logit function. Also Canca et al.,
(2019) use a piecewise linearization of the logit function for route choice
within a very detailed modeled transit line planning problem. Tirachini et
al.,  (2014) formulate mode choice for three alternative modes (bus, car, and
walking) using the logit model, for a frequency setting that integrates not
only decision on bus capacity, but also on fare, congestion toll, fare
collection system, and bus boarding policy on a linear network. They do not
linearize their formulation but solve it directly using sequential quadratic
programming. Beltran et al.,  (2009) consider three options to provide
transport along a link: public transport with regular vehicles, public
transport with green vehicles and transport by car, and employ an equilibrium
model for route and mode choice. Laporte et al.,  (2005) use a logit model for
locating a single line and solve it with a greedy approach.

Others argue that besides travel time, the number of connections per period
plays a relevant role in attracting passengers to travel by public transit.
Hartleb et al.,  (2023) argue that, in a reasonable line plan, in-vehicle time
and transfer time on routes between OD-pairs is negligible, and thus, the
utility of using public transit depends only on the number of _reasonable_
routes offered between origin and destination per hour. Also, in their direct
traveler model, Bertsimas et al.,  (2021) assume that the percentage of
passengers of an OD-pair choosing public transit depends on the frequency of
the connecting line offered. Assuming that public transit demand depends only
on the quality of the best available _route bundle_ , Klier and Haase,  (2015)
are able to _precompute_ the OD-demand.

##  4 Transit line planning under uncertainty

The goal of uncertain optimization in transit line planning is to find a line
concept which is still good under variation of input parameters. We discuss
the following sources of uncertainty.

  * •

Uncertainty of the demand, i.e., how many passengers wish to travel (see
Section 4.1),

  * •

unforeseen link failures in the PTN (see Section 4.2), or

  * •

uncertainty of the driving times which may vary due to congestion, weather
conditions, or unforeseen delays (see Section 4.3).

Each realization of an uncertain parameter is called a _scenario_ and the set
of all scenarios is called the _uncertainty set_ ${\cal U}$. Sometimes, a
probability distribution on ${\cal U}$ is known. Further aspects of
uncertainty can be considered, e.g., Kontogiannis and Zaroliagis,  (2008);
Bessas et al.,  (2009) model competition between railway operators which do
not reveal their real incentives.

##### Optimality concepts.

Uncertain optimization can be treated by robust and stochastic optimization
(see Ben-Tal et al.,  (2009); Birge and Louveaux,  (1997); Kouvelis and Yu,
(1997)). They differ in the optimality concepts they follow.

_One-stage robust optimization_ (e.g., Ben-Tal et al.,  (2009)) hedges against
the worst case. It hence aims for a solution which is feasible for every
scenario in the uncertainty set and performs best in the worst case over all
scenarios. The concept is also called _strict robustness_.

_Two-stage robust optimization_ splits decisions into _here-and-now decisions_
of the first stage which have to be made without knowing the scenario and
_wait-and-see decisions_ in a second stage. The latter can be taken after the
scenario is revealed. The goal is to find here-and-now decisions that can be
recovered to a good solution even in the worst case over all scenarios. These
optimality concepts include adjustable robustness (e.g., Ben-Tal et al.,
(2003)) and recovery robustness (e.g., Liebchen et al.,  (2009)).

_One-stage stochastic optimization_ Birge and Louveaux,  (1997) assume that a
probability distribution on the scenario set is known. This allows to minimize
the expected value of the objective function.

_Two-stage stochastic optimization_ Birge and Louveaux,  (1997) considers a
second stage in which recourse variables reflecting wait-and-see decisions can
be chosen after the scenario has been revealed. Several goals may be
considered, among them the minimization of the expected value.

##### Uncertainty sets.

We introduce uncertainty sets which have been used in transit network design.
For illustration, consider a problem in which two parameters, $(l_{1},l_{2})$
are uncertain. These may represent uncertain driving times on two links
$a_{1},a_{2}$.

  * •

In the _deterministic case_ the values of $l_{1}$ and $l_{2}$ are known and
the uncertainty set contains only one point, e.g., ${\cal U}=\\{(8,15)\\}$.

  * •

A _discrete uncertainty set_ consists of a finite set of scenarios. These
could be driving times under three different traffic situations, e.g., ${\cal
U}=\\{(10,20),(9,17),(8,15)\\}$. Probabilities may be assigned to each of the
scenarios.

  * •

If parameter ranges can be specified independently for each parameter, we
obtain _box-wise uncertainty_. If the driving time $l_{1}$ on link $a_{1}$ is
in $[8,10]$ and $l_{2}\in[15,20]$ we receive ${\cal U}:=[8,10]\times[15,20]$.
A typical distribution on ${\cal U}$ (reflecting measurement errors) may be
the multi-normal distribution.

  * •

_$\Gamma$ -uncertainty_ introduced by Bertsimas and Sim,  (2004) takes into
account that in the case of box-uncertainty it may be unlikely that all
uncertain parameters take their extreme values simultaneously. In the example,
it might be unlikely, that both driving times take their worst case at the
same time. This is reflected by a budget constraint with budget $\Gamma$,
leading, e.g., to ${\cal U}=\\{(l_{1},l_{2}):8\leq l_{1}\leq 10,15\leq
l_{2}\leq 20,\mbox{ and }l_{1}+l_{2}\leq 25=:\Gamma\\}$.

Uncertain optimization generates challenging optimization problems, and many
of them may be practically relevant. Nevertheless, research on transit line
planning under uncertainties is still scarce. In the following we sketch how
some of the introduced optimality concepts have been applied to transit line
planning.

###  4.1 Transit line planning under demand uncertainty

Most publications assume that transit demand, as given in the OD-matrix, is
given and fixed, or that its dependence on the supply provided is
deterministic (compare Section 3.5). However, since exact predictions about
future demand are hard to make, the OD-matrix should be considered as an
uncertain parameter. In the papers sketched below, the goal is to design a
line concept which still can transport all passengers even if demand
increases. Box-wise uncertainty ${\cal
U}_{box}=\\{\textup{OD}:l_{s,t}\leq\textup{OD}_{s,t}\leq u_{s,t}\
\forall(s,t)\in\mathcal{O}\mathcal{D}\\}$ for given lower and upper bounds
$l_{s,t},u_{s,t}$ for all OD-pairs $(s,t)$ and $\Gamma$-based uncertainty
${\cal U}_{\Gamma}=\\{\textup{OD}\in{\cal
U}_{box}:\sum_{(s,t)\in\mathcal{O}\mathcal{D}}\textup{OD}_{s,t}\leq\Gamma\\}$
have been used.

One-stage robust optimization. Lee and Nair,  (2021) consider a strictly
robust approach to transit line planning in which they assume
$\Gamma$-uncertainty. They search a line concept and passenger routes that
minimize the travel time of the passengers including a penalty for overcrowded
lines in the worst case of all OD-matrices in ${\cal U}_{\Gamma}$. They use a
line-based aggregation and model both, route assignment by the planner and
route choice by the passengers.

One-stage stochastic optimization. Gkiotsalitis et al.,  (2022) study a
single-stage stochastic version of the _subline frequency setting problem_ ,
i.e., the problem to select lines and frequencies to run on a corridor. In a
deterministic version of the problem, frequencies have to be chosen high
enough to allow all passengers to board the next-arriving vehicle towards
their destination, however, in the stochastic case this constraint may be
violated and capacity violations lead to a penalty. They solve the problem by
scenario sampling from a known distribution of the demand.

Two-stage robust optimization. Box-uncertainty has been considered in An and
Lo,  (2016) and in Pu and Zhan,  (2021). Both groups of authors minimize a sum
of costs and travel time in the worst-case over all possible scenarios in the
line-based aggregation level. They use two-stage models where lines and
frequencies are determined in the first stage before knowing the scenario,
while passenger routes are adjusted to the realized scenario in the second
stage.

In An and Lo,  (2016) two models are discussed. In the first one, passenger
routes are assigned by a planner under hard capacity limits of the lines. In
the second model, line capacity violations are allowed, but lead to discomfort
for the passengers who choose their routes interdependently according to an
equilibrium model. In Pu and Zhan,  (2021), passenger routes are assigned by
the planner. Here, additionally to the adjustment of the passenger routes, the
authors allow to also adjust the routes of the lines on a limited number of
links. Their objective function also includes the travel time and costs in the
first stage.

In both papers, the problems where passenger routes are assigned by the
planner can be solved by using the worst case in which all OD-pairs take their
maximum values. For the model with equilibrium routing presented in An and Lo,
(2016), the authors observe a paradox: it may happen that maximum demand does
not constitute the worst-case scenario.

Two-stage stochastic optimization. An and Lo,  (2016) propose two-level
stochastic optimization models to transit line planning with uncertain demand
with box uncertainty. They minimize the expected cost and travel times
assuming a known probability distribution of the passengers’ demand which is
made tractable by sampling approaches. As in their robust optimization
approaches described above, the first stage concerns the decisions on lines
and their frequencies and the second stage allows to adjust the passenger
routes within a line-based level of detail when the scenario is known. They
analyze the situation where passengers are assigned to routes by the planner
as well as routing passengers interdependently with equilibrium flows assuming
capacity violation penalties. Additionally, the second stage does not only
adjust the routing variables but also allows to add flexible service (such as
dial-a-ride) on higher costs for passengers that cannot be transported by the
transit lines.

###  4.2 Transit line planning under the risk of link failure

If a link in the PTN fails, some passengers might not be able to travel any
more or they might suffer detours. The goal in transit line planning is to
find a line concept which keeps the number of badly affected passengers low
even if links fail. The uncertainty set ${\cal U}$ is discrete in this setting
since there is only a finite number of links to fail. If only the failure of
single links is considered we have ${\cal U}=A$.

We first discuss how the consequences of link failures can be evaluated. Link
failures are a typical disruption in classic network design problems and have
also been investigated in transit line planning. While many papers evaluate
networks from a pure topology point of view (e.g., Derrible and Kennedy,
(2010)), De-Los-Santos et al.,  (2012) were one of the first who included the
demand in a line-based evaluation. For the failure of a link $a$ they propose
two models: one in which passengers need to avoid the link, i.e., they compute
new (shortest) paths with an increased travel time. The second model assumes
bridging the failed link by a bus service which also increases the travel
times. A full-scan of all edges is performed and the maximum of them is used
as robustness index. Also Cats,  (2016) suggests a full-scan of all links, but
on a link-based level. In case of a failure, they distinguish between
passengers without any path, passengers which need a detour and undisturbed
passengers.

One-stage robust or stochastic optimization. If passenger routes cannot be
adjusted, failure of a link will destroy some passenger paths (unless the link
would not be used at all). The worst case would be attained at the link with
the highest traffic load. However, in real life passengers would adjust their
routes which makes one-stage optimization concepts for link failures useless
from a practical point of view and might be the reason that they have not been
considered for link failures in transit line planning.

Two-stage robust optimization. In a two-stage approach, the lines and their
frequencies are set in the first stage while the routes of the passengers can
be adjusted in the second stage when it is known which link has failed. This
concept has been followed in Marín et al.,  (2009), who minimize the
passengers’ traveling times under link failure in the worst case. The authors
analyze travel time in the link-based aggregation level assigning passengers
to routes by the planner. The same setting is used in Laporte et al.,  (2010)
but with coverage by transit in presence of an alternative mode as performance
indicator, i.e., they aim to find a line concept that maximizes the coverage
of passengers in the worst case. Since the uncertainty set with ${\cal U}:=A$
is small, the authors can formulate an integer linear program which contains
paths for all OD-pairs and all scenarios. They show that it is equivalent to a
two-player non-cooperative zero-sum game in which the first player is the
transit line planner which can choose from different line concepts in his
strategy set while the second player is an evil adversary who selects a link
to fail. The authors prove that a saddle point of the game (if it exists)
corresponds to a (strictly) robust solution of the two-stage robust transit
line planning problem.

Two-stage stochastic optimization. Given that probabilities for the link
failures are available, Laporte et al.,  (2010) maximize the expected coverage
of the line concept. Passenger routes are determined (by the planner) in the
second stage in the link-based aggregation level, and may be adjusted to the
link which has failed. Analogous to their approach for minimizing the worst
case, and due to the rather small scenario set ${\cal U}=A$ the resulting
problem can be formulated as linear integer program.

###  4.3 Transit line planning under driving time uncertainty

Uncertainty in the driving times may, e.g., be due to varying traffic, or due
to unforeseen delays. Hedging against travel time uncertainty has been
considered in timetabling in numerous papers, see Lusby et al.,  (2018) for a
survey. Transit lines have an impact on the timetable and hence on its
robustness. In order to _evaluate_ a line concept with respect to the
traveling times of the passengers in schedule-based transit, a simulation
approach can be used that considers not only the transit lines but also the
timetable and the vehicle schedules as follows:

  1. 1.

Based on the line concept, design a timetable and a vehicle schedule (as in
Figure 3).

  2. 2.

Generate a set ${\cal U}$ of (typical) driving times, including unforeseen
delays.

  3. 3.

Route the passengers in the trip-based aggregation level for every scenario in
${\cal U}$.

  4. 4.

Aggregate their traveling times to, e.g., the expected or the worst case
traveling time.

LinTim (see Schiewe et al.,  (2024)) is a tool that can be used for such an
evaluation as done in Goerigk et al.,  (2013). A systematic evaluation of a
large set of possible disruptions has been suggested in Friedrich et al.,
2017c ; Friedrich et al., 2018b . For Step 2, the authors generate delays on
each single train run, a travel time increase on each link, and a temporary
blocking of each station. For each of these scenarios the additional delay
encountered by the passengers is computed and summarized in a robustness
value. The evaluation has been used within a machine learning approach for
improving the robustness of timetables in Müller-Hannemann et al.,  (2022);
Müller-Hannemann et al.,  (2021).

In the following we turn to _analytical_ models for dealing with travel time
uncertainty.

Two-stage robust optimization Cadarso and Marin,  (2012, 2016) use a model for
the TNDP where passengers are assigned to routes by the planner in the link-
based level of detail and optimize a weighted sum of coverage by transit,
costs and passengers’ traveling times. As uncertainty, a finite set of
disruptions caused, e.g., by maintenance work is considered in a two-stage
program. Transit lines are constructed in the first stage while the passenger
routes are adjusted in the second stage (in the paper this is called _recovery
action_). The aim is to find the best set of transit lines in the worst case.

Two-stage stochastic optimization Sadrani et al.,  (2022) assume a log-normal
distribution of driving times between stops. They sample their values from the
scenario set within the optimization. The goal is to minimize the expected
travel time of the passengers. Their routes are determined by the planner on
trip-level together with a scenario-based schedule and under consideration of
crowding in the second stage. The mean and the standard deviation needed are
assumed to be given, but analyzed within a sensitivity analysis.

Cadarso et al.,  (2017) modify the deterministic model of Cadarso and Marin,
(2012, 2016) by making the driving times stochastic. They use a finite
scenario set ${\cal U}$. The aim is to minimize the expected value of coverage
by transit as performance indicator, where the lines are determined in the
first stage and the routes of the passenger are adjusted by the planner in the
second stage within the link-based aggregation level. Due to the finiteness of
the uncertainty set the problem can be formulated as a linear integer program.
The results are compared with the Expected Value model and two different
Value-at-Risk formulations.

There are also other approaches to increase robustness of line plans under
travel time uncertainty. Some authors argue that an equal distribution of
passengers through the network may decrease the probability for delays since
crowded arcs tend to be more sensible to delays and since a disruption will
affect less passengers in the worst case if there are no overcrowded arcs.
This has been done in Cadarso and Marin,  (2012); Laporte et al.,  (2011)
where constraints on the passenger routes make sure that demand is forced to
disperse on the whole network. Instead of distributing the passenger routes,
Schöbel and Schwarze,  (2013) aim at dispersing the lines more equally on the
network within a game-theoretic model: here, each line is interpreted as a
player, and the players compete for the limited infrastructure when choosing
their frequencies. Both approaches work on the link-based aggregation level.

Yao et al.,  (2014) add buffer times to the travel times in the transit line
planning model to account for potential delays In Yan et al.,  (2013), a
transit travel time reliability constraint is introduced within a stochastic
model requiring that the probability that the travel time for an OD-pair is
larger than a certain threshold is small.

##  5 Extensions and related problems

###  5.1 The skip-stop problem

So far, lines have been defined as paths in the public transportation network
PTN, usually by their sequence of links. This determines also the stops of a
line. In the _skip-stop problem_ the lines are given and fixed. The decision
to be made is to determine their stops. More precisely, for every line the
skip-stop problem decides, which of the stops along its path should be visited
by the line and which of them can be skipped.

Formally, assume that a line $l$ passes links $e_{1}=(u,v)$ and $e_{2}=(v,w)$,
i.e., the path for $l$ includes the sequence

$l=(\ldots,(u,v),(v,w),\ldots).$

If the stop $v$ is _skipped_ , the two consecutive links $(u,v)$ and $(v,w)$
are merged into one link $(u,w)$ and we receive

$l^{\prime}=(\ldots,(u,w),\ldots)$

instead. Note that the PTN needs to be transitive when merging edges which is
a realistic assumption since the bus/train can just pass a stop/station
without stopping there.

For the model, assume a line $l$ which is operated every $p$ minutes. The idea
is to split the line into two lines which are operated alternately, let’s say
into a red line and into a green line. The red line serves only red stations
$V^{\textup{red}}\subseteq V$ and the green line serves only green stations
$V^{\textup{green}}\subseteq V$. The set of green stations and the set of red
stations does not need to be disjoint. It is required that every station is
served by at least one of the two lines, i.e., that

$V^{\textup{red}}\cup V^{\textup{green}}=V.$

For every station that is not visited by both lines, driving time is saved
because the line does not need to stop. The saved time can be used to increase
frequency such that more passengers can be transported. This is a reason to
skip as many stops as possible since capacity is a crucial issue in crowded
metropolitan areas. Skip stop problems in this context have been developed,
e.g., in Asia Cao et al.,  (2014); Cacchiani et al.,  (2020); Rajabighamchi et
al.,  (2019); Park et al.,  (2013) or in South America Freyssa et al.,
(2013). The saved time can also be used as buffer to increase robustness
Cacchiani et al.,  (2020).

For passengers traveling between red stations or between green stations, the
travel time decreases, too. However, passengers who wish to travel between a
red and a green station need an additional transfer. Hence, skipping too many
stations makes it inconvenient for the passengers that now do not have direct
connections any more and might even need to travel a short piece into the
wrong direction.

In the literature, the term skip-stop is used and analyzed from many different
perspectives and there exist several approaches of solving the skip-stop
problem considering various objective functions that have to be minimized.
Vuchic,  (1976) analyzes the differences between the skip-stop operation and
the standard operation with respect to the passengers time savings. Within a
parametric approach Freyssa et al.,  (2013) considers a continuum
approximation approach focusing on the density of the stations visited by both
lines. Evenly distributed demands and identical stopping-times are assumed for
analyzing the influence of different parameters of the model, especially the
length of the lines. A multicriteria-optimization model considering waiting
times, travel times and driving times of the trains is developed by Cao et
al.,  (2014). In a suburban area, Xu et al.,  (2021) aim at a solution with
one local line visiting all stations and one express line skipping some of the
stations. In addition to minimizing the total passenger traveling time and the
riding times of the vehicles, the total number of used trains (for a given
number of passengers) is taken into account.

Combining the choice of a stopping pattern with the computation of the
concrete timetable has been investigated in Yue et al.,  (2016); Jiang et al.,
(2017), and robust models hedging against demand uncertainty for the
integrated problem are developed in Yin et al.,  (2016); Cacchiani et al.,
(2020); Jiang et al.,  (2017). These papers use rail operations as examples.
Demand uncertainty has also been investigated for skip-stop bus operations.
Here, Mou et al.,  (2020) minimizes the costs taking into account the
uncertain boarding times of the passengers, while Liu et al.,  (2013); Lee et
al.,  (2014); Rajabighamchi et al.,  (2019) develop robust strategies for
skipping stops if a bus is behind schedule in the deadheading problem. A quite
different application for skip-stop models is presented by Limsawasd et al.,
(2022) who propose a skip-stop model that includes social distancing
constraints and enables to plan better schedules while capacities of the
vehicles are drastically reduced (due to the COVID-19 pandemic).

###  5.2 Transit network design with seasonal demand

Which line concept is to be considered optimal highly depends on the demand.
Transit line planning for _uncertain_ demand has already been addressed in
Section 4.1. However, demand changes are typical in public transport: at
night, there is less demand than during the day, in peak-hours we have high-
demand periods. We call these different demand periods _seasonal demand_. Let
us assume that we have $K$ different demand seasons, each of them
characterized by an OD-matrix $\textup{OD}_{j}$, $j=1,\ldots,K$. When
designing transit lines, the two extremes for dealing with seasonal demand are
the following:

  * •

One might find an optimal line concept
$(\mathcal{L^{*}}^{j},(f_{l})_{l\in\mathcal{L^{*}}^{j}})$ for each of the OD-
matrices $j=1,\ldots,K$. This would serve each of the demand seasons best, but
the resulting line concepts might be very different from each other.

  * •

The other extreme is to find only _one_ line concept
$(\mathcal{L^{*}},(f_{l})_{l\in\mathcal{L^{*}}})$ which should suit all
different demand seasons. This is easy to memorize but most likely too
expensive or too crowded.

Let us denote $f^{j}:=(f_{l})_{l\in\mathcal{L^{*}}^{j}}$ the vector containing
the frequencies of line concept $\mathcal{L^{*}}^{j}$.

Seasonal demand and the above two options have already been mentioned in in
Amiripour et al.,  (2014). The authors suggest to find one line concept
$(\mathcal{L^{*}}^{r},f^{r})$ minimizing the expected travel time over all
seasons. They call it _robust_ since they additionally require that it should
on average over all seasons be better than any of the optimal line concepts
$(\mathcal{L^{*}}^{j},f^{j})$. With $F_{j}(\mathcal{L^{*}},f)$ being the
travel time of $(\mathcal{L^{*}},f)$ evaluated for $\textup{OD}_{j}$ they
require for all seasons $i$ that

$\sum_{j=1}^{k}\alpha_{j}F_{j}(\mathcal{L^{*}}^{r},f^{r})\leq\sum_{j=1}^{k}\alpha_{j}F_{j}(\mathcal{L^{*}}^{i},f^{i})$

where $\alpha_{j}$ is the length of the season with OD-matrix
$\textup{OD}_{j}$.

Based on the observations that demand of the metrobüs in Istanbul is extremely
unsteady (see Borndörfer et al.,  (2018)) Şahin et al.,  (2020) are the first
to define a multi-period transit line planning problem: they search for a line
concept for each of the periods and couple them by resource constraints which
make sure that the resources flow from one period to the next. The model is
stated in general form starting from the cost model (4) as basis.

In Zhu et al.,  (2022); Duran-Micco et al.,  (2022), the authors take a
passenger-oriented point of view and evaluate line concepts under various OD
matrices within a case study. They suggest to find a line concept for the
morning peak hour (since this is the busiest demand season) and for other
seasons to update the frequencies while keeping the same line plan. The model
in Schiewe et al.,  (2023) goes a step further. Here, a line concept
$(\mathcal{L^{*}}^{j},f^{j})$ is determined for each of the demand seasons,
where coupling constraints ensure sufficient similarity of the different line
concepts:

$\textup{diff}\left((\mathcal{L^{*}}^{j},f^{j}),(\mathcal{L^{*}}^{k},f^{k})\right)\leq\alpha\
\ \forall k,l=1,\ldots,K$

Different (dis)similarity measures are discussed and tested on the basic cost
model (4): Similarity of line concepts can be evaluated by looking at the
differences of the frequency vectors (defined on
$\mathcal{L^{\textup{Pool}}}$), i.e.,
$\textup{diff}\left(\mathcal{L^{*}}^{j},f^{j}),(\mathcal{L^{*}}^{k},f^{k})\right):=\|f^{j}-f^{k}\|$
which is interesting also for the case in which only the frequencies change
and the lines stay the same for all seasons. A simple measure is to
investigate only the number of lines that are added or that change. The most
promising approach starts by defining a dissimilarity $d(l_{1},l_{2})$ between
each pair of lines $l_{1},l_{2}$ first and then use these numbers within a
transportation problem (similar to the Wasserstein-distance) to compute the
similarity of the line _concept_ , see Mauttone and Urquharta,  (2009); Zhu et
al.,  (2022); Schiewe et al.,  (2023).

###  5.3 Integrating transit line planning with other planning stages

The main stages for public transport planning are the design of the
infrastructure, followed by transit line planning, timetabling, vehicle- and
crew scheduling as depicted in Figure 3. Most papers concentrate on one of
these stages. Proceeding through the stages sequentially, one after another,
we receive a solution which consists of lines, frequencies, a timetable, and
vehicle- and crew schedules. It can be evaluated using similar performance
indicators as described in Section 2.5, but the decisions made in later
planning stages allow to make more precise estimates, e.g., travel times can
be evaluated trip-based instead of line based and costs for vehicle and crew
can be evaluated based on actual schedules. However, proceeding sequentially
stage after stage is just a greedy approach and does in general not find the
best possible solution. This has been recognized by many authors. Solving the
planning stages integratedly would yield an optimal solution but is
computationally out of scope. An integer linear program integrating transit
line planning, timetabling, and vehicle scheduling is presented in Schiewe,
(2020); Schiewe and Schöbel,  (2022) but it can only be solved for tiny
networks. In the following we sketch some work which considers line planning
together with other planning stages.

Line planning and timetabling. Most work on integrating transit line planning
with another planning stage concerns the integration of line planning and
timetabling. There are a few exact models (given as mixed-integer programs),
e.g., in Blanco et al.,  (2020) who model the line selection, frequency
setting and timetabling problem respecting capacities and passenger flows, or
in Irnich and Steiner,  (2018) who choose lines and schedules simultaneously
for a line corridor in the context of intercity bus lines. Since such models
are hard to solve, different types of heuristic approaches have been proposed.

  * •

Iterative approaches switch between transit line planning and timetabling
iteratively trying to improve the line concept and/or the timetable in every
step. Depending on the submodels used for transit line planning or
timetabling, different improvement strategies exist. In Schöbel,  (2017) lines
can be broken at stations and re-arranged within a matching problem in order
to reduce the number of transfers (but still respecting the timetable). In
Burggraeve et al.,  (2017) the lengths of the lines are changed in each
iteration allowing a more flexible and hence more robust timetable. Within a
railway context Yan and Goverde,  (2019) adapt the maximal frequencies in each
iteration to deal with infrastructural limitations while Zhang et al.,  (2022)
(also in a railway context) adds a coupling constraint whose level of
satisfaction is used within a feedback loop in the iterative process.

  * •

A look-ahead strategy is followed by Fuchs et al.,  (2022) who aims at finding
a line plan that admits a feasible timetable. Within an iterative approach a
small set of incompatible services is identified and modified until a feasible
timetable exists.

  * •

An evolutionary approach for integrating transit line planning and timetabling
is suggested in Kaspi and Raviv,  (2013).

Line planning, timetabling, and vehicle scheduling. Exact formulations for an
integration of these three planning stages are given in Schiewe,  (2020);
Schiewe and Schöbel,  (2022) as linear integer programming models using trip-
based aggregation and routing passengers by the planner. Since it is
computationally hard to solve these models, several other models and
approaches have been developed.

  * •

Liebchen and Möhring,  (2007) deal mainly with timetabling integrating vehicle
scheduling and allowing slight rearrangements of lines within their approach.

  * •

Schöbel,  (2017) proposes to re-optimize all three stages step by step within
an iterative approach. As framework, the so-called eigenmodel Schöbel,  (2017)
is developed. Its nodes represent subproblems and the edges indicate which of
these problems can be solved after another. In Jäger and Schöbel,  (2020) it
is shown that the approach always converges to a local optimum in a finite
number of improvement steps for public transit planning. Pätzold et al.,
(2017) use this idea by changing the order of the subproblems in a sequential
approach: they start with vehicle scheduling followed by timetabling and line
planning instead of processing in the classic way indicated in Figure 3.

  * •

A look-ahead approach is followed by Li et al.,  (2023) who develop a line
plan together with a timetable integratedly and in such a way that it is a
feasible input for the vehicle scheduling problem. This is modeled as a large
nonlinear integer optimization problem which is solved by decomposition
approaches.

Integrating transit line planning with other stages. The integration of
transit line planning and vehicle scheduling (without looking at a timetable,
but just forming the vehicles’ routes) has been treated in Michaelis and
Schöbel,  (2009); Pternea et al.,  (2015); Schiewe and Stinzendörfer,  (2022).
Also the integration of transit line planning with tariff planning has been
considered, see Zhou et al.,  (2023) or Tirachini et al.,  (2014) who combine
frequency setting and the determination of the bus sizes with the optimization
of fares and congestion tolls.

###  5.4 Parametric transit line planning

There is a stream of literature that regards line planning and frequency
setting from a _continuum approximation_ perspective. Rather than designing a
line concept and/or frequencies for a specific city, represented by a PTN and
OD-pairs on the PTN, the aim is to make general statements about optimal
design of line concepts, frequencies, and capacities. An early contribution in
this area is Mohring,  (1972), who, coming from a microeconomics perspective,
analytically studied the problem of determining optimal frequencies and the
number of bus stops for a so-called _steady-state route_ , where passengers’
origins and destinations are uniformly distributed along the route and bus
stops are to be spaced evenly along the route. An optimal frequency is
obtained by balancing operator cost (which increase with frequency) and
passenger waiting times (which decrease with frequency). This leads to the
famous _square root formula_ which states that the frequency should be
proportional to the square root of the number of passengers. This line of
research has been developed further in, e.g., Jansson,  (1980); Jara-Díaz and
Gschwender, 2003a ; Jara-Díaz and Gschwender,  (2009). Jara-Díaz and
Gschwender, 2003b are able to generalize the square root result to lines on
networks.

Based on these results there is also a stream of publications that consider
transit network design on _parametric networks_ , i.e., networks whose
topology and demand structure are fully determined by a few input parameters.
The goal of most of these publications is to determine optimal design
parameters for stylized line concepts (_feeder trunk_ , _hub and spoke_ etc.)
and to specify _optimal_ line concepts based on the input parameters with
respect to a weighted sum of costs and travel time.

Fielbaum et al.,  (2016) represent the area for which the line plan is to be
designed as a network consisting of a central business district node (CBD)
connected to several subcenter nodes which are in turn connected to
neighboring subcenters and to periphery nodes. Distances between CBD and
subcenters and between subcenters and periphery nodes, as well as the demand
structure between the different types of nodes are controlled parameters. They
analyze the performance of four general network structures (_direct lines_ ,
_feeder trunk_ , _hub and spoke_ , and _exclusive_) under some common transit
network design assumptions. For each of the proposed structures, they
determine optimal frequencies and capacities for the lines with respect to an
objective function composed of operational costs (depending on the total
number of vehicles needed and the vehicle capacity, but notably not on the
distance driven) and total passenger travel time (composed of in-vehicle time,
adaption time, and transfer penalties). Due to the regular network structure,
they are able to express the different cost components as functions of the
parameters and to compute optimal frequencies and capacities numerically when
parameter values are given. Fielbaum et al.,  (2021) enrich the model from
Fielbaum et al.,  (2016) by _line spacing_. Fielbaum et al.,  (2018) compare
the performance of the general line network structures proposed in Fielbaum et
al.,  (2016) with line plans found by approaches developed for transit line
planning problems with specific (non-parametrically given) PTN and demand.
Masing et al.,  (2022) propose a mixed-integer linear program to compute
(symmetric) line concepts on parametric cities and discuss the price of
symmetry.

Analyses similar to Fielbaum et al.,  (2016) have been done also for other
underlying network structures like grid networks Daganzo,  (2010); Chen et
al.,  (2015) and radial networks Badia et al.,  (2014); Chen et al.,  (2015).

###  5.5 Further related problems

During disruptions or construction work at rail infrastructure, the
corresponding connections are often bridged by buses, leading to ad-hoc route
generation, route selection and frequency assignment problems. The _bus
bridging_ problem has been studied in, e.g., Kepaptsoglou et al.,  (2010); Van
der Hurk et al.,  (2016); Gu et al.,  (2018); Deng et al.,  (2018), for
further references see also the corresponding section in the recent survey on
urban rail disruption management by Wang et al.,  (2024).

_On-demand transportation_ does often not operate on fixed routes, but is
planned flexibly based on passengers origins and destinations. This transport
mode has been used for a long time to transport people with reduced mobility
access where requests are normally known in advance. Recently, it has sparked
new interest, also in its online version, with the advent of autonomous
vehicles on the horizon. See, e.g., Cordeau,  (2006); Ropke and Cordeau,
(2009); Gaul et al.,  (2021). A recent survey is given in Vansteenwegen et
al.,  (2022).

Hoogervorst et al.,  (2022) study the _edge (link) investment problem_ : which
segments of a bus line should be upgraded to be used by bus rapid transport,
assuming that there are multiple parties responsible for the investments.

To avoid _bus bunching_ , different control strategies are possible, such as
waiting, stop-skipping, short-turning. See, e.g., Daganzo,  (2009); Tian et
al.,  (2022) and references therein. Gkiotsalitis et al.,  (2023) investigate
the problem for rail-based transport. A survey is given in Rezazada et al.,
(2022).

There is also a stream of research dealing with the question how to _visualize
line plans_ according to criteria like preservation of network topology and
relative position of stations, uniform link lengths between stations, few
bends along individual metro lines, or limited number of link orientations. A
mixed integer linear programming approach to the problem has been described in
Nöllenburg and Wolff,  (2011). This approach has been used to generate the
line plan in Figure 1. For more on line plan visualization, see Wolff,
(2007); Wu et al.,  (2020).

##  6 Outlook and further research

We hope that this article made a small contribution to the following two goals
which we consider as important for a further development of the field of
transit planning. The first is to bring researchers from different communities
even closer together. We believe that cooperations will help to improve
research on optimization of public transport significantly. The second
challenge is to use more results of transit line planning for optimizing real-
life applications, in particular in view of climate changes, and eventually
make transit line planning procedures available in practice whenever they are
needed.

## Acknowledgments

The authors thank Martin Nöllenburg und Alexander Wolff for providing Figure1.

## References

  * Amiripour et al., (2014) Amiripour, S. M., Ceder, A. A., and Mohaymany, A. S. (2014).  Designing large-scale bus network with seasonal variations of demand.  Transportation Research Part C: Emerging Technologies, 48:322–338.
  * An and Lo, (2016) An, K. and Lo, H. (2016).  Two-phase stochastic program for transit network design under demand uncertainty.  Transportation Research B, 84:157–181.
  * Badia et al., (2014) Badia, H., Estrada, M., and Robusté, F. (2014).  Competitive transit network design in cities with radial street patterns.  Transportation Research Part B: Methodological, 59:161–181.
  * Bel and Holst, (2018) Bel, G. and Holst, M. (2018).  Evaluation of the impact of bus rapid transit on air pollution in mexico city.  Transport Policy, 63:209–220.
  * Beltran et al., (2009) Beltran, B., Carrese, S., Cipriani, E., and Petrelli, M. (2009).  Transit network design with allocation of green vehicles: A genetic algorithm approach.  Transportation Research Part C: Emerging Technologies, 17(5):475–483.
  * Ben-Tal et al., (2009) Ben-Tal, A., Ghaoui, L. E., and Nemirovski, A. (2009).  Robust Optimization.  Princeton University Press, Princeton and Oxford.
  * Ben-Tal et al., (2003) Ben-Tal, A., Goryashko, A., Guslitzer, E., and Nemirovski, A. (2003).  Adjustable robust solutions of uncertain linear programs.  Math. Programming A, 99:351–376.
  * Bertsimas et al., (2021) Bertsimas, D., Ng, Y. S., and Yan, J. (2021).  Data-driven transit network design at scale.  Operations Research, 69(4):1118–1133.
  * Bertsimas and Sim, (2004) Bertsimas, D. and Sim, M. (2004).  The price of robustness.  Operations Research, 52(1):35–53.
  * Bessas et al., (2009) Bessas, A., Kontogiannis, S., and Zaroliagis, C. (2009).  Incentive-compatible robust line planning.  In Ahuja, R. K., Möhring, R., and Zaroliagis, C., editors, Robust and online large-scale optimization, volume 5868 of Lecture Note on Computer Science, pages 85–118. Springer.
  * Birge and Louveaux, (1997) Birge, J. and Louveaux, F. (1997).  Introduction to Stochastic Programming.  Springer Verlag, New York.
  * Blanco et al., (2020) Blanco, V., Conde, E., Hinojosa, Y., and Puerto, J. (2020).  An optimization model for line planning and timetabling in automated urban metro subway networks. a case study.  Omega, 92:102165.
  * Borndörfer et al., (2018) Borndörfer, R., Arslan, O., Elijazyfer, Z., Güler, H., Renken, M., Şahin, G., and Schlechte, T. (2018).  Line planning on path networks with application to the istanbul metrobüs.  In Operations Research Proceedings 2016: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Helmut Schmidt University Hamburg, Germany, August 30-September 2, 2016, pages 235–241. Springer.
  * Borndörfer et al., (2007) Borndörfer, R., Grötschel, M., and Pfetsch, M. E. (2007).  A column generation approach to line planning in public transport.  Transportation Science, 41:123–132.
  * Borndörfer and Karbstein, (2012) Borndörfer, R. and Karbstein, M. (2012).  A direct connection approach to integrated line planning and passenger routing.  In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, volume 25 of OpenAccess Series in Informatics (OASIcs), pages 47–57. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Borndörfer et al., (2013) Borndörfer, R., Hoppmann, H., and Karbstein, M. (2013).  A configuration model for the line planning problem.  In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), volume 33 of OpenAccess Series in Informatics (OASIcs), pages 68–79. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Bull et al., (2015) Bull, S. H., Lusby, R. M., and Larsen, J. (2015).  An optimization based method for line planning to minimize travel time.  In 13th Conference on Advanced Systems in Public Transport. Erasmus University.
  * Burggraeve et al., (2017) Burggraeve, S., Bull, S., Vansteenwegen, P., and Lusby, R. (2017).  Integrating robust timetabling in line plan optimization for railway systems.  Transportation Research C, 77:134–160.
  * Bussieck, (1998) Bussieck, M. (1998).  Optimal lines in public transport.  PhD thesis, Technische Universität Braunschweig.
  * Bussieck et al., (1996) Bussieck, M., Kreuzer, P., and Zimmermann, U. (1996).  Optimal lines for railway systems.  European Journal of Operational Research, 96(1):54–63.
  * Bussieck et al., (2004) Bussieck, M., Lindner, T., and Lübbecke, M. (2004).  A fast algorithm for near cost optimal line plans.  Mathematical Methods of Operational Research, 59(3):205–220.
  * Cacchiani et al., (2020) Cacchiani, V., Qi, J., and Yang, L. (2020).  Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty.  Transportation Research Part B: Methodological, 136:1–29.
  * Cadarso et al., (2017) Cadarso, L., Codina, E., Escudero, L., and Marin, A. (2017).  Rapid transit network design: considering recovery robustness and risk aversion measures.  Transportation Research Procedia, 22:255–264.
  * Cadarso and Marin, (2012) Cadarso, L. and Marin, A. (2012).  Recoverable robustness in rapid transit network design.  Procedia - Social and Behavioral Sciences, 54:1288–1297.
  * Cadarso and Marin, (2016) Cadarso, L. and Marin, A. (2016).  Rapid transit network design considering risk aversion.  Electronic Notes in Discrete Mathematics, 52:29–36.
  * Canca et al., (2019) Canca, D., De-Los-Santos, A., Laporte, G., and Mesa, J. A. (2019).  Integrated railway rapid transit network design and line planning problem with maximum profit.  Transportation Research Part E: Logistics and Transportation Review, 127:1–30.
  * Cancela et al., (2015) Cancela, H., Mauttone, A., and Urquhart, M. E. (2015).  Mathematical programming formulations for transit network design.  Transportation Research B, 77:17–37.
  * Cao et al., (2014) Cao, Z., Yuan, Z., and Li, D. (2014).  Estimation method for a skip-stop operation strategy for urban rail transit in china.  Journal of Modern Transport, 3:174–182.
  * Caprara et al., (1998) Caprara, A., Toth, P., Vigo, D., and Fischetti, M. (1998).  Modeling and solving the crew rostering problem.  Operations Research, 46(6):820–830.
  * Cats, (2016) Cats, O. (2016).  The robustness value of public transportation development plans.  Journal of Transport Geography, pages 236–246.
  * Cats and Glück, (2019) Cats, O. and Glück, S. (2019).  Frequency and vehicle capacity determination using a dynamic transit assignment model.  Transportation Research Record, 2673(3):574–585.
  * Ceder and Wilson, (1986) Ceder, A. and Wilson, N. (1986).  Bus network design.  Transportation Research B, 20(4):331–344.
  * Chen et al., (2015) Chen, H., Gu, W., Cassidy, M. J., and Daganzo, C. F. (2015).  Optimal transit service atop ring-radial and grid street networks: A continuum approximation design method and comparisons.  Transportation Research Part B: Methodological, 81:755–774.
  * Cheng et al., (2018) Cheng, H., Mao, C., Madanat, S., and Horvath, A. (2018).  Minimizing the total costs of urban transit systems can reduce greenhouse gas emissions: The case of san francisco.  Transport Policy, 66:40–48.
  * Chriqui and Robillard, (1975) Chriqui, C. and Robillard, P. (1975).  Common bus lines.  Transportation science, 9(2):115–121.
  * Claessens et al., (1998) Claessens, M., van Dijk, N., and Zwaneveld, P. (1998).  Cost optimal allocation of rail passenger lines.  European Journal on Operational Research, 110:474–489.
  * Constantin and Florian, (1995) Constantin, I. and Florian, M. (1995).  Optimizing frequencies in a transit network: a nonlinear bi-level programming approach.  International Transactions in Operational Research, 2(2):149–164.
  * Cordeau, (2006) Cordeau, J.-F. (2006).  A branch-and-cut algorithm for the dial-a-ride problem.  Operations research, 54(3):573–586.
  * Daganzo, (2009) Daganzo, C. F. (2009).  A headway-based approach to eliminate bus bunching: Systematic analysis and comparisons.  Transportation Research Part B: Methodological, 43(10):913–921.
  * Daganzo, (2010) Daganzo, C. F. (2010).  Structure of competitive transit networks.  Transportation Research Part B: Methodological, 44(4):434–446.
  * De Cea and Fernández, (1993) De Cea, J. and Fernández, E. (1993).  Transit assignment for congested public transport systems: an equilibrium model.  Transportation science, 27(2):133–147.
  * de Dios Ortúzar and Willumsen, (2011) de Dios Ortúzar, J. and Willumsen, L. (2011).  Modelling transport.  John Wiley & Sons.
  * De-Los-Santos et al., (2012) De-Los-Santos, A., Laporte, G., Mesa, J., and Perea, F. (2012).  Evaluating passenger robustness in rail transit networks.  Transportation Research C, 20(1):34–46.
  * De-Los-Santos et al., (2017) De-Los-Santos, A., Laporte, G., Mesa, J. A., and Perea, F. (2017).  The railway line frequency and size setting problem.  Public Transport, 9:33–53.
  * dell’Olio et al., (2006) dell’Olio, L., Moura, J. L., and Ibeas, A. (2006).  Bi-level mathematical programming model for locating bus stops and optimizing frequencies.  Transportation research record, 1971(1):23–31.
  * dell’Olio et al., (2012) dell’Olio, L., Ibeas, A., and Ruisánchez, F. (2012).  Optimizing bus-size and headway in transit networks.  Transportation, 39:449–464.
  * Deng et al., (2018) Deng, Y., Ru, X., Dou, Z., and Liang, G. (2018).  Design of bus bridging routes in response to disruption of urban rail transit.  Sustainability, 10(12):4427.
  * Derrible and Kennedy, (2010) Derrible, S. and Kennedy, C. (2010).  Characterizing metro networks: state, form, and structure.  Transportation, 37:275–297.
  * Duran et al., (2019) Duran, J., Pradenas, L., and Parada, V. (2019).  Transit network design with pollution minimization.  Public Transport, 11:189–210.
  * Duran-Micco et al., (2022) Duran-Micco, J., van Kooten Niekerk, M., and Vansteenwegen, P. (2022).  Designing bus line plans for realistic cases — the utrecht case study.  Expert Systems with Applications, 187:115918.
  * Durán-Micco and Vansteenwegen, (2022) Durán-Micco, J. and Vansteenwegen, P. (2022).  A survey on the transit network design and frequency setting problem.  Public Transport, 14(1):155–190.
  * Duran-Micco et al., (2020) Duran-Micco, J., Vermeir, E., and Vansteenwegen, P. (2020).  Considering emissions in the transit network design and frequency setting problem with a heterogeneous fleet.  European Journal of Operational Research, 282(2):580–592.
  * Farahani et al., (2013) Farahani, R., Miandoabchi, E., Szeto, W., and Rashidi, H. (2013).  A review of urban transportation network design problems.  European Journal of Operational Research, 229(2):281–302.
  * Fielbaum et al., (2016) Fielbaum, A., Jara-Diaz, S., and Gschwender, A. (2016).  Optimal public transport networks for a general urban structure.  Transportation Research Part B: Methodological, 94:298–313.
  * Fielbaum et al., (2020) Fielbaum, A., Jara-Diaz, S., and Gschwender, A. (2020).  Beyond the mohring effect: Scale economies induced by transit lines structures design.  Economics of Transportation, 22:100163.
  * Fielbaum et al., (2021) Fielbaum, A., Jara-Diaz, S., and Gschwender, A. (2021).  Lines spacing and scale economies in the strategic design of transit systems in a parametric city.  Research in Transportation Economics, 90:100991.
  * Fielbaum et al., (2018) Fielbaum, A., Jara-Díaz, S., and Gschwender, A. (2018).  Transit line structures in a general parametric city: The role of heuristics.  Transportation Science, 52(5):1092–1105.
  * Freyssa et al., (2013) Freyssa, M., Giesena, R., and Muñoz, J. C. (2013).  Continuous approximation for skip-stop operation in rail transit.  Procedia- Social and Behavioral Sciences,, 80:186–210.
  * (59) Friedrich, M., Hartl, M., Schiewe, A., and Schöbel, A. (2017a).  Angebotsplanung im öffentlichen Verkehr - planerische und algorithmische Lösungen.  In Heureka’17.
  * (60) Friedrich, M., Hartl, M., Schiewe, A., and Schöbel, A. (2017b).  Integrating Passengers’ Assignment in Cost-Optimal Line Planning.  In D’Angelo, G. and Dollevoet, T., editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 1–16, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * (61) Friedrich, M., Hartl, M., Schiewe, A., and Schöbel, A. (2018a).  System Headways in Line Planning.  In Proceedings of CASPT 2018, Preprint-Reihe, Institut für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen, no. 2018-11, http://num.math.uni-goettingen.de/preprints/files/2018-11.pdf.
  * Friedrich et al., (2021) Friedrich, M., Hartl, M., Schilling, M., Schiewe, A., and Schöbel, A. (2021).  Kombination von linienkonstruktions-und linienauswahlverfahren für die liniennetzplanung.  In HEUREKA’21: Optimierung in Verkehr und Transport.
  * (63) Friedrich, M., Müller-Hannemann, M., Rückert, R., Schiewe, A., and Schöbel, A. (2017c).  Robustness Tests for Public Transport Planning.  In D’Angelo, G. and Dollevoet, T., editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 1–16, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * (64) Friedrich, M., Müller-Hannemann, M., Rückert, R., Schiewe, A., and Schöbel, A. (2018b).  Robustness as a third dimension for evaluating public transport plans.  In Borndörfer, R. and Storandt, S., editors, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs), pages 4:1–4:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Fuchs et al., (2022) Fuchs, F., Trivella, A., and Corman, F. (2022).  Enhancing the interacton of railway timetabling and line planning with infrastructure awareness.  Transportation Research, Part C, 142:103805.
  * Gatt et al., (2022) Gatt, H., Freche, J.-M., Laurent, A., and Lehuédé, F. (2022).  A Bilevel Model for the Frequency Setting Problem.  In D’Emidio, M. and Lindner, N., editors, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), volume 106 of Open Access Series in Informatics (OASIcs), pages 5:1–5:8, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * Gatt et al., (2021) Gatt, H., Freche, J.-M., Lehuédé, F., and Yeung, T. G. (2021).  A column generation-based heuristic for the line planning problem with service levels (short paper).  In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Gattermann et al., (2017) Gattermann, P., Harbering, J., and Schöbel, A. (2017).  Line pool generation.  Public Transport, 9(1-2):7–32.
  * Gaul et al., (2021) Gaul, D., Klamroth, K., and Stiglmayr, M. (2021).  Solving the dynamic dial-a-ride problem using a rolling-horizon event-based graph.  In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Schloss-Dagstuhl-Leibniz Zentrum für Informatik.
  * Gioia, (2023) Gioia, S. (2023).  Line edge graphs: a methodology to model and determine generic lines, line plans and line type services in public transport planning.  In RailBelgrade 2023: 10th International Conference on Railway Operations Modelling and Analysis.
  * Gkiotsalitis and Cats, (2022) Gkiotsalitis, K. and Cats, O. (2022).  Optimal frequency setting of metro services in the age of covid-19 distancing measures.  Transportmetrica A: Transport Science, 18(3):807–827.
  * Gkiotsalitis et al., (2023) Gkiotsalitis, K., Cats, O., Liu, T., and Bult, J. (2023).  An exact optimization method for coordinating the arrival times of urban rail lines at a common corridor.  Transportation Research Part E: Logistics and Transportation Review, 178:103265.
  * Gkiotsalitis et al., (2022) Gkiotsalitis, K., Schmidt, M., and van der Hurk, E. (2022).  Subline frequency setting for autonomous minibusses under demand uncertainty.  Transportation Research Part C: Emerging Technologies, 135:103492.
  * Goerigk et al., (2013) Goerigk, M., Schachtebeck, M., and Schöbel, A. (2013).  Evaluating line concepts using travel times and robustness: Simulations with the lintim toolbox.  Public Transport, 5(3).
  * Goerigk and Schmidt, (2017) Goerigk, M. and Schmidt, M. (2017).  Line planning with user-optimal route choice.  European Journal of Operational Research, 259(2):424–436.
  * Goossens et al., (2006) Goossens, J., van Hoesel, C., and Kroon, L. (2006).  On solving multi-type railway line planning problems.  European Journal of Operational Research, 168(2):403–424.
  * Gu et al., (2018) Gu, W., Yu, J., Ji, Y., Zheng, Y., and Zhang, H. M. (2018).  Plan-based flexible bus bridging operation strategy.  Transportation Research Part C: Emerging Technologies, 91:209–229.
  * Guan et al., (2006) Guan, J., Yang, H., and Wirasinghe, S. (2006).  Simultaneous optimization of transit line configuration and passenger line assignment.  Transportation Research Part B: Methodological, 40(10):885–902.
  * Guihare and Hao, (2008) Guihare, V. and Hao, J.-K. (2008).  Transit network design and scheduling: a global review.  Transportation Research, Part A, 42(10):1251–1273.
  * Hamacher and Schöbel, (2004) Hamacher, H. and Schöbel, A. (2004).  Design of zone tariff systems in public transportation.  OR, 52(6):897–908.
  * Hartleb et al., (2023) Hartleb, J., Schmidt, M., Huisman, D., and Friedrich, M. (2023).  Modeling and solving line planning with mode choice.  Transportation Science, 57(2):336–350.
  * Heinrich et al., (2022) Heinrich, I., Schiewe, P., and Seebach, C. (2022).  Algorithms and hardness for non-pool-based line planning.  In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems.
  * Heinrich et al., (2023) Heinrich, I., Schiewe, P., and Seebach, C. (2023).  Non-Pool-Based Line Planning on Graphs of Bounded Treewidth.  In Frigioni, D. and Schiewe, P., editors, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), volume 115 of Open Access Series in Informatics (OASIcs), pages 4:1–4:19, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * Hoogervorst et al., (2022) Hoogervorst, R., van der Hurk, E., Schiewe, P., Schöbel, A., and Urban, R. (2022).  The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties.  In D’Emidio, M. and Lindner, N., editors, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), volume 106 of Open Access Series in Informatics (OASIcs), pages 9:1–9:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * Iliopoulou et al., (2019) Iliopoulou, C., Kepaptsoglou, K., and Vlahogianni, E. (2019).  Metaheuristics for the transit route network design problem: a review and comparative analysis.  Public Transport, 11:487–521.