An Extended Formulation for the Line Planning Problem
In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on a
- PDF / 122,837 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 190 Views
Abstract In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.
1 Introduction Line planning is an important strategic planning problem in public transport. The task is to find a set of lines and frequencies such that a given demand can be transported. There are usually two main objectives: minimizing the travel times of the passengers and minimizing the line operating costs. Since the late 90s, the line planning literature has developed a variety of integer programming approaches that capture different aspects, for an overview see Schöbel [10]. Bussieck, Kreuzer, and Zimmermann [5] propose an integer programming model to maximize the number of direct travelers. Operating costs are discussed for instance in the article of Goossens, van Hoesel, and Kroon [7]. Schöbel and Scholl [11] and Borndörfer and Karbstein [1] focus on the number of transfers and the number of direct travelers, respectively, and further integrate line planning and passenger routing in their models. Borndörfer, Grötschel, and Pfetsch [2] also propose an integrated line planning and passenger routing model that allows a dynamic generation of lines. Supported by the Research Center Matheon “Mathematics for key technologies”. H. Hoppmann (B) Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany e-mail: [email protected] © Springer International Publishing Switzerland 2017 K.F. Dœrner et al. (eds.), Operations Research Proceedings 2015, Operations Research Proceedings, DOI 10.1007/978-3-319-42902-1_2
11
12
H. Hoppmann
All these models employ some type of capacity or frequency demand constraints in order to cover a given demand. In this paper we propose a concept to strengthen such constraints by means of a novel extended formulation. The idea is to enumerate the set of possible configurations of line frequencies for each capacity constraint. We show that such an extended formulation implies general facet defining inequalities for the standard model. We consider the following basic line planning problem: We are given an undirected graph G = (V, E) representing the transportation network; a line is a simple path in G and we denote by L = {1 , . . . , n }, n ∈ N, the given set of lines. We denote by L(e) := { ∈ L : e ∈ } the set of lines on edge e ∈ E. Furthermore, we are given an ordered set of frequencies F = {f1 , . . . , fk } ⊆ N, k ∈ N, such that 0 < f1 < · · · < fk , and we
Data Loading...
