# A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels

Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, Thomas G. Yeung

► To cite this version:

Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, Thomas G. Yeung. A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels. ATMOS 2021: International Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Sep 2021, Lisbon, Portugal. 10.4230/OASIcs.ATMOS.2021.19. [hal-03356433]

HAL Id: hal-03356433

https://hal.science/hal-03356433

Submitted on 28 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels

Hector Gatt

<figure><img src="image_2.png" /></figure>

IMT Atlantique, LS2N, Nantes France

Lumiplan, Saint-Herblain, France

Jean-Marie Freche

<figure><img src="image_3.png" /></figure>

Lumiplan, Saint-Herblain, France

Fabien Lehuédé

<figure><img src="image_4.png" /></figure>

IMT Atlantique, LS2N, Nantes, France

Thomas G. Yeung

<figure><img src="image_5.png" /></figure>

IMT Atlantique, LS2N, Nantes, France

## Abstract

This paper addresses the line planning problem by the combination of existing models reinforced with realistic characteristics like lines frequencies intervals or maximum number of lines, useful for public transportation companies. The problem is solved by an innovative, easily implementable, heuristic combining column generation and elementary column enumeration methods. In this paper, the operator's exploitation costs are minimized while respecting new quality of service parameters addressed to passengers. Furthermore, a case study based on a real network is performed and described in this paper to prove the efficiency of our method.

**2012 ACM Subject Classification** Networks → Network design and planning algorithms

**Keywords and phrases** Line Planning, Network Design, Column Generation, Service Performance

**Digital Object Identifier** 10.4230/OASICS.ATMOS.2021.19

**Category** Short Paper

## 1 Introduction

Offering a high-quality bus network at a reasonable cost is the main objective of many public transportation companies. Known as the *Line Planning Problem*, this problem is included at a strategic level in a global planning process of a public transportation system first introduced by Ceder and Wilson in 1986 [6]. It consists of designing a set of lines and frequencies such that a given demand can be transported. The two major challenges of this problem are cost and quality of service. While the capital and operating expense of the network is the main challenge of the operator, the passenger seeks a fast, reliable, and convenient network. Hence, the existent line planning models can be classified in two types: with cost-oriented or with passenger oriented objective functions. For each of these two objectives, many mathematical approaches have been developed, see Schöbel [8] for an overview.

According to Schöbel [8] and Karbstein [7], there are two approaches to consider passengers choices in the line planning problem: the fixed passenger routing approach or the integrated passenger routing approach. The former assumes that the number of passengers traveling along each path is known, while the second approach assumes the passengers' path choice depends on the lines proposed. The first approach is nowadays somewhat abandoned in favor of the second one. A change & go graph, as proposed by Schöbel and Scholl in 2005 [9] can be a method to deal with the integrated passenger routing approach for solving the Line Planning problem. This method consists of duplicating each node each time a transfer from one line to another on this node is done, and to connect them with a new edge. The

<figure><img src="image_6.png" /></figure>

© Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, and Thomas G. Yeung;

licensed under Creative Commons License CC-BY 4.0

21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021).

Editors: Matthias Müller-Hannemann and Federico Perea; Article No. 19; pp. 19:1–19:6

<figure><img src="image_7.png" /></figure>

OpenAccess Series in Informatics
OASICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
19:2 A Column Generation-Based Heuristic for the LPP-SL

advantage of this method is that it models transfers with great accuracy. However, the size
of the graph grows exponentially with the size of the network, which prevents the approach
from being used on real-world cases. Another method to deal with the integrated passenger
routing approach can be to use a bi-level method. This method separates the problem into
two levels, the upper one to determine the lines and their frequencies and the lower one to
define the passengers choices on the network. Szeto and Jiang [12] propose a mixed-integer,
non-linear, bi-level formulation for the Line Planning problem. Their upper level aims to
define a line set minimizing the number of transfers with respect to constraints on fleet size or
lines frequencies, and their lower level aims to solve an assignment model with respect to bus
capacity. In this paper, we focus on the cost-oriented problem associated with the integrated
passenger routing approach to better match the motivating companies expectations. In our
case, these are to offer a network with a guaranteed service level at minimum cost. Inspired
by the direct connection approach formulated by Borndörfer and Karbstein [5], we focus on
network creation with novel service level constraints and solved by an innovative heuristic
combining column generation and elementary column enumeration methods.

2 The Line Planning Problem with Service Levels

**2.1 Problem Description**

The Line Planning Problem (LPP) seeks to define a system of lines with associated operation
frequencies satisfying passengers demands. In our case, we decide to focus on the cost oriented
Line Planning Problem in order to minimize the operation costs. Operation costs can be
characterised as the sum of the products between the total lines lengths and a kilometric
cost c. The total length of a line $l \in \mathcal{L}$ ($\mathcal{L}$ being a set of bus lines) is defined by the product
of its outward and return length $d_l$ and its frequency $f_l$ (number of bus passages on the line
$l$ during the time period considered). Therefore, we can define the cost of a line plan ($\mathcal{L}, f$)
as $c(\mathcal{L}, f) = \sum_{l \in \mathcal{L}} d_l \times f_l \times c$.

We consider a public transportation network composed of main stations linked together
by edges that have travel times, distances, and maximum capacities. The maximum capacity
of an edge refers to the maximum number of buses allowed to circulate on it. It is used
to avoid the saturation of the network on an edge. The public transportation network is
represented as an undirected graph $G = (V, E)$ where $V$ are the main stations and $E$ the
edges. Infrastructure parameters (number of buses available, bus capacity, kilometric cost)
and user-specified parameters such as the lines authorized frequency, minimum and maximum
lengths, maximum total number are also taken into account. Finally, passengers demands are
considered, represented as an origin-destination (OD) matrix where each $(i-j)$ coefficient
represents the number of passengers desiring to go from point $i$ to $j$ during a given time
period.

Our problem being an extension of the Line Planning Problem that incorporates service
levels, we decide to name it the Line Planing Problem with Service Levels (LPP-SL).

**2.2 Passenger Service Levels**

In 1995, Baaj et al. [1] introduced the notion of a time deviation threshold for passengers
compared to their shortest path. More recently, in 2018, Suman et al. [11] analyze the
perception of potential users about existing bus services in Delhi, India, and conclude most of
people avoid using buses due to overloading, excessive travel time compared with a personal
vehicle, the need to make a transfer, and lack of punctuality. Suman reuses his study to propose with Bolia [10] in 2019 a model maximizing the directness of their network, defined as total passenger kilometers without transfers.

Borndörfer et al. [4] (2007) offer a method to generate bus lines and passenger paths. However, they do not differentiate direct and non-direct paths. Borndörfer and Karbstein [5] (2012) introduce the direct connection approach, that distinguishes passenger paths without transfers and passenger paths with one or more transfers. This method loses accuracy compared to the change-and-go method [9] by not determining the exact number of transfers, but conversely this method can be used on large graphs and thus exploited on real size networks. With this approach, Borndörfer and Karbstein propose a method to generate direct and non-direct passenger paths. However they do not generate bus lines, only selecting them from a pre-defined pool. Finally, Bertsimas et al. [3] (2021) offer a method to model direct and non-direct passenger paths, while generating bus lines. However, they only constrain exploitation costs to a maximum threshold and choose to maximize the demand that is served by the lines chosen instead. Furthermore, as passengers transfers are modeled by analyzing the exact transfer node and line used on each part of the path, they chose to limit the passenger paths to a maximum of one transfer to avoid the saturation of their model.

Inspired by these articles, we propose two conditions to model the quality of service of a network: (1) A passenger must have a path allowing him to go from his origin to his destination by not deviating by a pre-defined threshold from its shortest path time (2) A minimum percentage of passengers must be able to go from their origin to final destination without making a transfer. These two conditions named *maximum SPT deviation* and *minimum direct percentage* are respectively defined by the two quality of service parameters $\alpha$ and $\beta$, $\alpha \ge 1$ and $\beta \in [0, 1]$. The first condition can thus be defined as $t_p \le \alpha \times SPT_{st} \quad \forall p \in P_{st}$; where $p \in P_{st}$ symbolizes the paths to go from $s$ to $t$, $t_p$ the time of the path $p$, and $SPT_{st}$ the shortest time to go from $s$ to $t$ based on the arcs in the current network.

# 3 Column Generation-based Heuristic

## 3.1 Modeling Approach

To integrate a maximum SPT deviation constraint, we adopt a path-based formulation to model passenger flows. Furthermore, to integrate a minimum direct percentage in a realistic size bus network, we extend the approach of Borndörfer and Karbstein [5] by dividing traveler paths in two pools, one for direct and one for non-direct, and using a column generation approach for the design of bus lines. Our Line Planning Problem is thus composed of four decision variables: a binary variable $z_l$ that represents the opening of a bus line, a positive integer variable $f_l$ that represents the bus line frequency, and two continuous variables, $y_p^{0+}$ and $y_p^{1}$, that track the number of passengers respectively traveling on direct path $p$ and non-direct path $p'$. Hence, the integration of a minimum direct percentage leads to a more realistic network than Borndörfer et al. [4] where an uncontrolled number of passengers can be linked with non-direct paths.

## 3.2 The Heuristic

The number of potentially attractive bus lines and passenger paths increase at an exponential rate as the network size increases. Complete enumeration is not possible for large instances and commercial solvers also become quickly overwhelmed. Hence, using a column generation method can be a good choice to solve this problem by selecting the pool of best bus lines and passenger paths prior to using a commercial solver to solve the integer problem.
19:4 A Column Generation-Based Heuristic for the LPP-SL

We propose a heuristic which consists of a column generation step, followed by a column
enumeration method based on [2]. The general process of this heuristic is presented in
Figure 1.

<figure><img src="image_8.png" /><figcaption>■ **Figure 1** General overview of column generation heuristic for the considered Line Planning Problem.</figcaption></figure>

By deciding to generate direct paths, non-direct paths and lines during the column
generation process and not only direct and non-direct paths, we avoid needing to compute
a line pool beforehand as Borndörfer and Karbstein do [5]. This yields a final line pool of
smaller size and thus a smaller resolution time of the Line Planning Problem.

In the first step, some initial sets of bus lines and passenger paths are generated while the LPP-SL has no solution. This gives rise to a restricted formulation of the LPP-SL (denoted rLPP-SL). The rLPP-SL is linearized using the variable substitution of [4] to model the use of a line and its frequency as a single variable. This forms the column generation master problem. Bus lines, direct paths and non-direct paths are then generated in the column generation step with two dedicated labelling algorithms, in which every label dominated by another label during the labeling algorithms execution is detected and removed, leading to time savings. This process terminates when the optimum of the Master problem has been found, providing a lower bound to the LPP-SL. All generated columns are then used in the rLPP-SL to solve the MIP with a commercial solver, thus providing an upper bound to the problem.

In this column generation heuristic, columns leading to an optimal solution of the LPP-SL
may not be generated because column generation is not used at each node of the branch-and-
bound algorithm that solves the MIP. To consolidate the sets of traveler paths and bus lines,
we add an elementary column enumeration step as introduced by Baldacci et al. [2] for the
VRP. For a given upper bound zIP and a lower bound zMP of the problem, this technique
consists of enumerating all possible lines and paths with reduced cost c_l and c_p such that
<span style="text-decoration: overline;">c</span><sub>l</sub> &le; z<sub>IP</sub> &minus; z<sub>MP</sub> and <span style="text-decoration: overline;">c</span><sub>p</sub> &le; z<sub>IP</sub> &minus; z<sub>MP</sub>. All these line and path variables are then added to
the rLPP-SL, which is solved with the MIP solver, using the previous upper bound as an
initial solution. This yields the final line plan composed of lines and frequencies.
## 4 Numerical Results

A case study has been chosen on the city of Poitiers, France with over 200 000 residents. Data is obtained from the collaboration between the local public transport operator and Lumiplan, a private company that offers services to optimize public transportation networks. To carry out this study, a graph composed of 78 nodes and 106 edges has been defined, based on the existing network. The network and the graph are presented in Figure 2.

<figure><img src="image_9.png" /><figcaption>Figure 2 Poitiers Bus Network – Graph Model.</figcaption></figure>

This case study is separated in two experiments, the first aims to redesign the network by minimizing cost with the same quality of services parameters for users. The second experiment analyzes the sensitivity of various parameters such as the service level, the maximum number of lines, or the line interval frequency on the cost of the network. The following table presents objective values details on the Poitiers instance for the first experiment. After both the Column-Generation and Column-Enumeration steps, the LPP-SL is solved using CPLEX with a computation time limit of 10 hours.

<table><caption>Table 1 Characteristics of current and redesigned line plans for Poitiers. The columns list objective value and service level parameters (maximum SPT deviation and minimum direct percentage).</caption><thead><tr><td>Network</td><td>Objective Value</td><td>Max. SPT Dev.</td><td>Min. Dir. Perc.</td></tr></thead><tbody><tr><td>Poitiers - Current Network</td><td>18 300</td><td rowspan="2">1.75</td><td rowspan="2">0.7</td></tr><tr><td>Poitiers - Redesigned Network</td><td>13 971</td></tr></tbody></table>

We calculated the maximum SPT deviation and minimum direct percentage values (1) for the current network and we used the same values as constraints for optimizing the redesign, which our approach was able to reduce the objective value by more than 23%. Concerning the second experiment, we were able to make some observations on the results obtained. For the same service level, the redesigned network with 22 lines had an objective function
19:6 A Column Generation-Based Heuristic for the LPP-SL

value 2% lower than one with only 21 lines. Furthermore, it was noticed that the number of non-direct paths generated with our heuristic increases as the Maximum Time Deviation parameter increases. Indeed, an increase of this parameter of 0.25 units lead to an increase of the generated non-direct paths of 100%. On the contrary, the number of generated lines decreased as this parameter increased.

5 Conclusion

We propose a heuristic for solving the line planning problem. In this formulation, we set the operator cost as a minimization objective while specifying quality of service parameters for the passengers. This heuristic, composed of column generation and column enumeration methods aims thus to minimize operator exploitation costs, depending on the lines defined and their associated frequencies. The quality of service has been defined according to two parameters, the first referring to the travel times and the second one referring to the number of direct passengers. Computational results for an instance based on a real city were obtained and showed the relevance of our heuristic for public transport companies to define a high quality network at a reasonable cost. Work will be pursued in the coming months on existing instances to evaluate the efficiency of our method on optimal known solution. Furthermore, a line typology study will be integrated into our heuristic to evaluate the conformity of the generated lines.

We are currently continuing this work at a more tactical level to define the line frequencies at different, smaller time periods. To this aim, a transit assignment model will need to be defined to determine which lines are attractive for every passenger, followed by a frequency setting model to adjust the line frequencies at a minimized cost while respecting quality of service parameters.

References

1 M. H. Baaj and H. S. Mahmassani. Hybrid route generation heuristic algorithm for the design of transit networks. *Transportation Research Part C: Emerging Technologies*, 1995.

2 R. Baldacci, N. Christofides, and A. Mingozi. An exact algorithm for the vrp based on the set partitioning formulation with additional cuts. *Mathematical Programming*, 2008.

3 D. Bertsimas, Y. S. Ng, and J. Yan. Data-Driven Transit Network Design at Scale. *Operations Research*, 2021.

4 R. Borndörfer, M. Grötschel, and M. E. Pfetsch. A Column-Generation Approach to Line Planning in Public Transport. *Transportation Science*, 2007.

5 R. Borndörfer and M. Karbstein. A Direct Connection Approach to Integrated Line Planning and Passenger Routing. *Discrete Optimization*, 2012.

6 A. Ceder and N. H. M. Wilson. Bus network design. *Transportation Research Part B: Methodological*, 1986.

7 M. Karbstein. *Line Planning and Connectivity*. PhD thesis, Mathematik und Naturwissenschaften der Technischen Universität Berlin, 2013.

8 A. Schöbel. Line planning in public transportation: models and methods. Springer, 2012.

9 A. Schöbel and S. Scholl. Line planning with minimal traveling time. *ATMOS*, 2005.

10 H. K. Suman and N. B. Bolia. Improvement in direct bus services through route planning. *Transport Policy*, 2019.

11 H. K. Suman, N. B. Bolia, and G. Tiwari. Perception of potential bus users and impact of feasible interventions to improve quality of bus services in Delhi. *Case Studies on Transport Policy*, 2018.

12 W.Y. Szeto and Y. Jiang. Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach. *Transportation Research Part B*, 2014.