@misc{BorndoerferElijazyferSchwartz2019, author = {Bornd{\"o}rfer, Ralf and Elijazyfer, Ziena and Schwartz, Stephan}, title = {Approximating Balanced Graph Partitions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73675}, year = {2019}, abstract = {We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a \$\Delta\$-approximation where \$\Delta\$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.}, language = {en} } @misc{Elijazyfer2018, type = {Master Thesis}, author = {Elijazyfer, Ziena}, title = {L{\"a}ngenbeschr{\"a}nkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung}, year = {2018}, language = {de} } @misc{Schreck2018, type = {Master Thesis}, author = {Schreck, Vanessa}, title = {Algorithmic Analysis of the Graph Segmentation Problem}, year = {2018}, language = {en} } @article{Schwartz2022, author = {Schwartz, Stephan}, title = {An overview of graph covering and partitioning}, volume = {345}, journal = {Discrete Mathematics}, number = {8}, doi = {https://doi.org/10.1016/j.disc.2022.112884}, year = {2022}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.}, language = {en} } @misc{SchwartzBalestrieriBorndoerfer2018, author = {Schwartz, Stephan and Balestrieri, Leonardo and Bornd{\"o}rfer, Ralf}, title = {On Finding Subpaths With High Demand}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69280}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{SchwartzBorndoerferBalestrieri2018, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Balestrieri, Leonardo}, title = {On Finding Subpaths With High Demand}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, pages = {355 -- 360}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{BorndoerferSchwartzBartz2018, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Bartz, Gerald}, title = {The Graph Segmentation Problem}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, pages = {35 -- 44}, year = {2018}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @article{GrimmHoogervorstBorndoerfer2025, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Two Models for Rolling Stock Scheduling}, volume = {59}, journal = {Transportation Science}, number = {5}, arxiv = {http://arxiv.org/abs/2312.09697}, doi = {10.1287/trsc.2024.0505}, year = {2025}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.}, language = {en} } @misc{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84427}, year = {2021}, language = {en} } @inproceedings{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Finding Minimum Balanced Separators - an Exact Approach}, booktitle = {Operations Research Proceedings 2021}, issn = {1438-0064}, doi = {https://doi.org/10.1007/978-3-031-08623-6_24}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83138}, pages = {154 -- 159}, year = {2021}, abstract = {Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.}, language = {en} } @misc{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82616}, year = {2021}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.}, language = {en} } @inproceedings{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in optimal experimental design and second order cone programming}, volume = {51}, booktitle = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, doi = {10.2478/v10127-012-0016-x}, pages = {161 -- 171}, year = {2012}, abstract = {In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results.}, language = {en} } @misc{Schwartz2013, type = {Master Thesis}, author = {Schwartz, Stephan}, title = {Bilevel Programming to Optimize the Use of Traffic Control Gantries for Toll Enforcement}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54180}, year = {2013}, language = {en} } @misc{BorndoerferBuwayaSagnoletal.2014, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks}, issn = {1438-0064}, doi = {10.1002/net.21596}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-47139}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{SchwartzSchlechteSwarat2017, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_30}, pages = {217 -- 223}, year = {2017}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{SchwartzSchlechteSwarat2016, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61123}, year = {2016}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in Optimal Experimental Design and Second Order Cone Programming}, volume = {51}, number = {51}, issn = {1438-0064}, doi = {10.2478/v10127-012-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14942}, pages = {161 -- 171}, year = {2012}, abstract = {In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results.}, language = {en} } @misc{BorndoerferBuwayaSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, issn = {1438-0064}, doi = {/10.1016/j.endm.2013.05.100}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17401}, year = {2012}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} } @misc{BorndoerferSagnolSwarat2011, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_51}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14299}, number = {11-42}, year = {2011}, abstract = {This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.}, language = {en} } @misc{SagnolBorndoerferSchlechteetal.2014, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {The Price of Spite in Spot-checking games}, issn = {1438-0064}, doi = {10.1007/978-3-662-44803-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52775}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{BorndoerferSagnolSchwartz2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, volume = {52}, booktitle = {INOC 2015 - 7th International Network Optimization Conference}, doi = {10.1016/j.endm.2016.03.040}, pages = {301 -- 308}, year = {2016}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @misc{BorndoerferReutherSchlechteetal.2015, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56070}, year = {2015}, abstract = {Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.}, language = {en} } @misc{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, issn = {1438-0064}, doi = {10.4230/OASIcs.SCOR.2012.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15498}, year = {2012}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, volume = {22}, booktitle = {3rd Student Conference on Operational Research}, doi = {10.4230/OASIcs.SCOR.2012.1}, pages = {1 -- 10}, year = {2012}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @article{BorndoerferSagnolSchlechteetal.2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal duty rostering for toll enforcement inspectors}, volume = {252(2)}, journal = {Annals of Operations Research}, edition = {252}, publisher = {Springer US}, doi = {10.1007/s10479-016-2152-1}, pages = {383 -- 406}, year = {2016}, abstract = {We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, we developed a personalized crew rostering model, to schedule the crews of the tours. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, booktitle = {Operations Research Proceedings 2011}, doi = {10.1007/978-3-642-29210-1_51}, pages = {317 -- 322}, year = {2012}, abstract = {This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.}, language = {en} } @inproceedings{BorndoerferBuwayaSagnoletal.2013, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, volume = {41}, booktitle = {Proceedings of INOC'2013}, doi = {http://dx.doi.org//10.1016/j.endm.2013.05.100}, pages = {253 -- 260}, year = {2013}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} } @inproceedings{BorndoerferOmontSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, volume = {105}, booktitle = {Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012)}, doi = {http://dx.doi.org/10.1007/978-3-642-35582-0_17}, pages = {224 -- 235}, year = {2012}, abstract = {We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of \$N\$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways.}, language = {en} } @misc{BorndoerferOmontSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, issn = {1438-0064}, doi = {10.1007/978-3-642-35582-0_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14995}, year = {2012}, abstract = {We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of \$N\$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways.}, language = {en} } @misc{BorndoerferSagnolSchwartz2015, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, issn = {1438-0064}, doi = {10.1016/j.endm.2016.03.040}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55405}, year = {2015}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @article{BorndoerferBuwayaSagnoletal.2015, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Network spot-checking games: Theory and application to toll enforcing in transportation networks}, volume = {65}, journal = {Networks}, publisher = {Wiley Periodicals, Inc.}, doi = {10.1002/net.21596}, pages = {312 -- 328}, year = {2015}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.}, language = {en} } @inproceedings{SagnolBorndoerferSchlechteetal.2014, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {The Price of Spite in Spot-checking games}, volume = {8768}, booktitle = {7th International Symposium on Algorithmic Game Theory (SAGT'2014)}, editor = {Lavi, Ron}, publisher = {Springer}, isbn = {978-3-662-44802-1}, doi = {10.1007/978-3-662-44803-8}, pages = {293}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{BorndoerferReutherSchlechteetal.2015, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.}, language = {en} } @misc{Gamrath2016, type = {Master Thesis}, author = {Gamrath, Gerwin}, title = {A Coarse-to-Fine Approach for the Workforce Scheduling of Teams}, pages = {72}, year = {2016}, abstract = {We present a coarse-to-fine column generation approach for the workforce scheduling of teams. In addition we present a price-and-branch approach and a new hypergraph formulation for a specific workforce team problem, called the Toll Enforcement Problem.}, language = {en} } @misc{BorndoerferSagnolSchlechteetal.2013, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering}, issn = {1438-0064}, doi = {10.1007/s10479-016-2152-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-45107}, year = {2013}, abstract = {We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.}, language = {en} } @inproceedings{GrimmBorndoerferBushe2023, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Bushe, Julian}, title = {Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2023.13}, pages = {13:1 -- 13:15}, year = {2023}, abstract = {The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation's feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Bornd{\"o}rfer et al., 2016] on a test set of real world instances.}, language = {en} } @inproceedings{BorndoerferCaselIssacetal.2021, author = {Bornd{\"o}rfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, title = {Connected k-partition of k-connected graphs and c-claw-free graphs}, volume = {207}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.27}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-147200}, pages = {27:1 -- 27:14}, year = {2021}, abstract = {A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c -1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w_1, ..., w_k. In the 1970s Győri and Lov{\´a}sz showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T_1, ..., T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least w_i/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least w_i/3 and at most max({r, 3})w_i, where r ≥1 is the ratio between the largest and smallest value in w_1, ..., w_k. In particular for the balanced version, i.e. w_1 = w_2 = ... = w_k, this gives a partition with 1/3 w_i ≤ w(T_i) ≤ 3w_i.}, language = {en} } @article{BorndoerferSchwartzSurau2023, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, volume = {81}, journal = {Networks}, number = {2}, doi = {10.1002/net.22130}, pages = {253 -- 277}, year = {2023}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph'svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature}, language = {en} } @inproceedings{BorndoerferSchwartzSurau2022, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, booktitle = {Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7-10, 2022}, doi = {10.48786/inoc.2022.12}, pages = {63 -- 68}, year = {2022}, abstract = {Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.}, language = {en} } @misc{Schwartz2020, author = {Schwartz, Stephan}, title = {An Overview of Graph Covering and Partitioning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79431}, year = {2020}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, our review extends to the corresponding partioning problems.}, language = {en} } @inproceedings{GamrathReutherSchlechteetal.2021, author = {Gamrath, Gerwin and Reuther, Markus and Schlechte, Thomas and Swarat, Elmar}, title = {An LP-based heuristic for Inspector Scheduling}, volume = {1}, booktitle = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I}, pages = {77 -- 86}, year = {2021}, abstract = {We present a heuristic based on linear programming (LP) for the integrated tour and crew roster planning of toll enforcement inspectors. Their task is to enforce the proper paying of a distance-based toll on German motorways. This leads to an integrated tour planning and duty rostering problem; it is called Toll Enforcement Problem (TEP). We tackle the TEP by a standard multi-commodity flow model with some extensions in order to incorporate the control tours. The heuristic consists of two variants. The first, called Price \& Branch, is a column generation approach to solve the model's LP relaxation by pricing tour and roster arc variables. Then, we compute an integer feasible solution by restricting to all variables that were priced. The second is a coarse-to-fine approach. Its basic idea is projecting variables to an aggregated variable space, which is much smaller. The aim is to spend as much algorithmic effort in this coarse model as possible. For both heuristic procedures we will show that feasible solutions of high quality can be computed even for large scale industrial instances.}, language = {en} }