Energy-optimal Public Transport
M. Burgera , A. Schiewea∗ and A. Schöbela,ba Fraunhofer Institute for Industrial Mathematics ITWM, Kaiserslautern, Germany

michael.burger@itwm.fraunhofer.de,alexander.schiewe@itwm.fraunhofer.deanita.schoebel@itwm.fraunhofer.deb Technische Universität Kaiserslautern, Kaiserslautern, Germany∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: Public Transport Planning, Sustainability, Energy Consumption, Line Planning, Vehicle Scheduling

1INTRODUCTION

There are several possible objective functions for public transport planning. While passenger convenience and operational costs are the most common objectives in the well researched sequential
solution process, other objectives such as the robustness of the obtained public transport system
are considered in the literature as well, see e.g. Friedrich et al. (2017).
In this work we investigate the objective to minimize the energy needed to serve the public
transport system while still considering the passenger convenience. Note that we are not only
considering the special case of electric vehicles, see e.g. Perumal et al. (2021) but want to find ageneral public transport system that consumes a lower amount of energy than a system obtainedby the algorithms in literature. This may as well be a system operated by traditional fuel-driven
buses where we hence want to find a solution consuming less fuel.
To introduce energy in the public transport optimization process, we first need to define theelements used in public transport planning. We assume that a public transport network (PTN)
is given, consisting of stops V and direct connections E between them. Lines are then defined
as simple paths on the PTN that should be served regularly in a planning period. We assume
that a set of possible lines, the line pool L, is given as well. Then line planning is the problemof finding a set of lines with frequencies such that all given passengers can be transported. For
an overview on line planning, we refer to Schöbel (2012). For a given line plan, we can assign(periodic) arrival and departure times for each line at its respective stations. This process iscalled timetabling, for an overview see Lusby et al. (2011). Afterwards, the periodic timetable
can be rolled out to cover a given planning period (e.g. extend a periodic timetable for one hour
to a day), where each line serving defines a trip that needs to be covered by a vehicle. Vehicle
scheduling describes the process of finding an assignment of vehicles to trips, where each vehicle
serves a list of trips, with potential empty trips connecting the end of one line to the start of
the next line. We refer to Bunte & Kliewer (2009) for more details and an overview on differentmodels to solve this problem.
TRISTAN XI Symposium

Original abstract submittal

M. Burger, A. Schiewe and A. Schöbel

22DIFFERENT ABSTRACTIONS FOR ENERGY-BASEDOPTIMIZATION

There are different problem stages and levels of detail to consider when we want to allow theoptimization process to respect the energy needed to operate the created public transport system.
We discuss possible models based on the data available. For this, we adapt models for line
planning and vehicle scheduling. Since the model for computing the energy consumption of avehicle in detail is computationally difficult (and non-linear), see e.g. Speckert et al. (2014), weuse abstractions that allow us to approximate the energy needed using linear integer optimization
models.

2.1

Planning based on altitude data

Information that is easy to obtain for a given infrastructure network is altitude data for the edgese ∈ E. To approximate the energy needed to traverse an edge e = (v, w), we use the upward
altitude difference, i.e., the positive altitude difference that needs to be traversed when travelingfrom v to w along e. We call this u(e). As a baseline cost function we choose the cost function
cost(l) for each line l ∈ L from Gattermann et al. (2017), i.e.,cost(l) = cl

Xlen(e) + ce |{e ∈ l}| + cf ,(1)e∈lwhere cl , ce and cf are given weight factors and len(e) is the (given) length of an edge e ∈ E.
We now extend this formulation by adding the upward altitude difference as well:costa (l) = ca

Xu(e) + cl

Xlen(e) + ce |{e ∈ l}| + cf .

(2)e∈le∈lThis now allows us to use known line planning algorithms such as cost-based models or weighted
sum methods containing the line costs to optimize w.r.t. the upward altitude difference used by
the lines, resulting in less energy needed for the computed public transport system. Additionally,
we may adapt the weighting factors ca , ce , cf and cl to change the focus between operational costs
and energy consumption.
We can extend this approach to the vehicle scheduling stage as well. Again, the baseline costfunction that we use to compute the costs of a vehicle schedule is a weighted sum, i.e.,cost(t) = cd dur(t) + cs len(t),(3)

where cd and cs are weight factors, dur(t) is the duration of the trip t (based on the currenttimetable) and len(t) is the length of t. Note that the length can be computed based on thelength len(e), e ∈ E of all edges contained in the trip, i.e., e ∈ t. This is based on the line (forservice trips) or on the edges used in the empty trip. Again, we can extend this formulation tocosta (t) = ca

Xu(e) + cd dur(t) + cs len(t).

(4)

e∈t

Note that for the overall costs of a vehicle schedule, we consider the number of vehicles needed
as well but this term is not dependent on a single trip and therefore not present in (4).
With this, we are now able to use models from the literature to do energy-aware cost optimization in both line planning and vehicle scheduling. For a computational evaluation of thismodelling propositions, see Section 3.
TRISTAN XI Symposium

Original abstract submittal

M. Burger, A. Schiewe and A. Schöbel

3

Perceived travel time [min]39.0ca = 0ca = 1ca = 1038.5

38.0

37.5

37.0

2000

2250

2500

2750

3000

3250

3500

3750

Consumed energy [kWh]Figure 1 – Comparing different solutions for their energy-efficiency using the approach of Section 2.1 on the bus system in Göttingen. Solutions marked with a cross are computed using a
cost-oriented line planning algorithm and solutions marked with a diamond are computed using
a weighted sum approach of costs and direct travellers. Direct travellers are passengers that cantravel from their origin to their destination without transferring between lines.

2.2

Planning based on simulation data

Instead of using the altitude approximation described in Section 2.1 we can use more detailed
information as well. For this, we assume that we have a black-box tool to simulate the energy
needed for a given path in the infrastructure network. This could e.g. be the simulation moduleof the tool “Geo-referenced Analysis and Virtual Measurement Campaign (VMC)”, see Speckert et al. (2014), which is used for this work. Again, we discuss possibilities to include such
simulation results in line planning as well as in vehicle scheduling.
For line planning, using the simulation allows us to approximate the energy needed to serve
every single line very accurately. We call this en(l). We can therefore replace the altitude termin (2) and obtain
Xl(e) + ce |{e ∈ l}| + cf .
(5)costen (l) = cen en(l) + cle∈l

For vehicle scheduling, the exact energy consumption of service trips is important to determine the overall energy consumption but since all service trips need to be covered and are fixed,
we do not need these values for the optimization process. Instead, we use the simulation toapproximate the energy used for empty trips in more detail. We need to find energy-efficient
shortest paths between all end and start stations of lines. To do so, we use a linear objectivefunction, namelyw(e) = wa u(e) + wl l(e),(6)to approximate the energy needed for each edge e ∈ E of the PTN using the altitude datafrom Section 2.1. Since (6) is linear and non-negative, we can now use known shortest paths
algorithms from literature to obtain all possible empty trips t ∈ T . Afterwards, every t ∈ T canbe simulated to obtain en(t) and we adapt (4):costen (t) = cen en(t) + cd dur(t) + cs l(t).

3(7)

FIRST COMPUTATIONAL RESULTS

We used the open-source software framework LinTim, see Schiewe et al. (2021, n.d.), to test
our adaptions in algorithms from the literature and the bus system in Göttingen, and VMC,
see Speckert et al. (2014), for simulating the energy consumption of lines and vehicle schedules.
TRISTAN XI Symposium

Original abstract submittal

M. Burger, A. Schiewe and A. Schöbel

4Using the adaptions proposed in Section 2.1, we obtain the results presented in Figure 1.
For this, we preprocessed the infrastructure in VMC to obtain altitude data. Note that this canbe done very efficiently since no simulation is needed. Afterwards, we used a cost-oriented anda weighted-sum (cost and direct travelers) integer programming approach to compute two line
plans for three different weight scenarios. Then a periodic timetable, a vehicle schedule and thecost function (4) were computed. We can observe that for the cost-oriented approach all threeweight factors perform very well with regard to their consumed energy but still the solutions
with higher altitude weight are able to outperform solutions with lower altitude weight, with amaximal effect of around 6%. But this effect is even stronger for the weighted-sum line plans,
allowing to reduce the energy needed to perform the resulting public transport system by around30%. Of course, this energy saving is not for free, the corresponding perceived passenger travel
time is increased by around 4%. Note that the perceived passenger travel time is a weighted
sum of the travel time and the number of transfers needed and the passengers are routed usinga shortest path approach w.r.t. their perceived travel time.
Similar effects can be seen when using the adaptions from Section 2.2, since the energy
consumption can be approximated even better. But this also increases the computation times,
since we need to compute more simulations using VMC, which is time consuming.

4CONCLUSION

In this work, we presented different approaches to incorporating energy consumption into public
transport planning and showed their effectiveness with first computational results. An important next step is to incorporate the timetabling process as well. Here, we adapted the stages
line planning and vehicle scheduling but the timetable plays an important role in the energy
consumption of a public transport system as well, since the energy consumption depends on thespeed of driving. Another aspect would be a further coupling to the simulation software, i.e.,allowing the optimization direct access to the simulation itself or important parts of it insteadof only using the output to improve the linear objective functions.

References
Bunte, S., & Kliewer, N. 2009. An overview on vehicle scheduling models. Public Transport, 1(4), 299–317.
Friedrich, Markus, Müller-Hannemann, Matthias, Rückert, Ralf, Schiewe, Alexander, & Schöbel, Anita.
2017. Robustness Tests for Public Transport Planning. Pages 6:1–6:16 of: D’Angelo, Gianlorenzo,& Dollevoet, Twan (eds), 17th Workshop on Algorithmic Approaches for Transportation Modelling,Optimization, and Systems (ATMOS 2017). OpenAccess Series in Informatics (OASIcs), vol. 59.
Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
Gattermann, P., Harbering, J., & Schöbel, A. 2017. Line pool generation. Public Transport, 9(1-2), 7–32.
Lusby, R., Larsen, J., Ehrgott, M., & Ryan, D. 2011. Railway track allocation: models and methods. ORspectrum, 33(4), 843–883.
Perumal, Shyam S.G., Dollevoet, Twan, Huisman, Dennis, Lusby, Richard M., Larsen, Jesper, & Riis,Morten. 2021. Solution approaches for integrated vehicle and crew scheduling with electric buses.
Computers & Operations Research, 132, 105268.
Schiewe, A., Albert, S., Grafe, V., Schiewe, P., Schöbel, A., & Spühler, F. LinTim - Integrated Optimization in Public Transportation. Homepage. https://www.lintim.net/. open source.
Schiewe, A., Albert, S., Grafe, V., Schiewe, P., Schöbel, A., & Spühler, F. 2021. LinTim: An integrated
environment for mathematical public transport optimization. Documentation for version 2021.12. Tech.
rept. Fraunhofer-Institut für Techno- und Wirtschaftsmathematik.
Schöbel, A. 2012. Line planning in public transportation: models and methods. OR spectrum, 34(3),491–510.
Speckert, M, Dreßler, K, Ruf, N, Halfmann, T, & Polanski, S. 2014. The Virtual Measurement CampaignVMC concept-a methodology for georeferenced description and evaluation of environmental conditions
for vehicle loads and energy efficiency. Pages 88–98 of: Proceedings of the 3rd Commercial Vehicle
Technology Symposium (CVT 2014). CVT.

TRISTAN XI Symposium

Original abstract submittal