TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances. Y1 - 2024 ER - TY - CHAP A1 - Prause, Felix T1 - A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance T2 - Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024 N2 - We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables. Y1 - 2024 U6 - https://doi.org/10.48786/inoc.2024.11 SP - 58 EP - 63 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating rolling stock rotations with integrated predictive maintenance JF - Journal of Rail Transport Planning & Management N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. Y1 - 2024 U6 - https://doi.org/10.1016/j.jrtpm.2024.100434 VL - 30 SP - 100434 ER - TY - JOUR A1 - Sahin, Guvenc A1 - Digehsara, Amin Ahmadi A1 - Borndörfer, Ralf T1 - Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation JF - Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) N2 - In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation. Y1 - 2021 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2021.17 VL - 96 SP - 17:1 EP - 17:6 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Free Flight Planning JF - Algorithms N2 - We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach. KW - shortest path KW - flight planning KW - free flight KW - discrete-continuous algorithm KW - optimal control KW - discrete optimization Y1 - 2020 U6 - https://doi.org/10.3390/a14010004 SN - 1438-0064 VL - 14 IS - 1 SP - 4 PB - MDPI ER - TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM. T3 - ZIB-Report - 23-20 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Test Library Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91734 SN - 1438-0064 ER - TY - GEN A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems N2 - The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve. T3 - ZIB-Report - 23-24 KW - Electric Vehicle Scheduling KW - Non-Linear Charging Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92441 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eßer, Thomas A1 - Frankenberger, Patrick A1 - Huck, Andreas A1 - Jobmann, Christoph A1 - Krostitz, Boris A1 - Kuchenbecker, Karsten A1 - Moorhagen, Kai A1 - Nagl, Philipp A1 - Peterson, Michael A1 - Reuther, Markus A1 - Schang, Thilo A1 - Schoch, Michael A1 - Schülldorf, Hanno A1 - Schütz, Peter A1 - Therolf, Tobias A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization JF - Informs Journal on Applied Analytics N2 - Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB’s fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO’s impact within DB’s planning departments has been revolutionary. DB has used it to support the company’s procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s plan-ning departments appreciate FEO’s high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO. Y1 - 2021 U6 - https://doi.org/10.1287/inte.2020.1069 VL - 51 IS - 1 SP - 42 EP - 62 ER - TY - JOUR A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-period line planning with resource transfers JF - Transportation Research Part C: Emerging Technologies N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. Y1 - 2020 U6 - https://doi.org/10.1016/j.trc.2020.102726 VL - 119 SP - 102726 ER - TY - CHAP A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-187765 VL - 115 SP - 15:1 EP - 15:6 ER - TY - THES A1 - Löbel, Fabian T1 - Implementing the Network Simplex for Hypergraphs N2 - The well-known network simplex algorithm is a powerful tool to solve flow problems on graphs. Based on a recent dissertation by Isabel Beckenbach, we develop the necessary theory to extend the network simplex to capacitated flow problems on hypergraphs and implement this new variant. We then attempt to solve instances arising from real-life vehicle rotation planning problems. Y1 - 2020 ER - TY - JOUR A1 - Euler, Ricardo A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Price optimal routing in public transportation JF - EURO Journal on Transportation and Logistics KW - Management Science and Operations Research KW - Transportation KW - Modeling and Simulation Y1 - 2024 U6 - https://doi.org/10.1016/j.ejtl.2024.100128 SN - 2192-4376 VL - 13 SP - 1 EP - 15 PB - Elsevier BV ER - TY - CHAP A1 - Klug, Torsten A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - Timetabling is a classical and complex task for public transport operators as well as for railway undertakings. The general question is: Which vehicle is taking which route through the transportation network in which order? In this paper, we consider the special setting to find optimal timetables for railway systems under a moving block regime. We directly set up on our work of [8 ], i.e., we consider the same model formulation and real-world instances of a moving block headway system. In this paper, we present a repair heuristic and a lazy-constraint approach utilizing the callback features of Gurobi, see [3]. We provide an experimental study of the different algorithmic approaches for a railway network with 100 and up to 300 train requests. The computational results show that the lazy-constraint approach together with the repair heuristic significantly improves our previous approaches. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.11 VL - 106 SP - 11:1 EP - 11:8 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - An Improved Multiobjective Shortest Path Algorithm JF - Computers & Operations Research N2 - We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra’s algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm Multiobjective Dijkstra Algorithm (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins, which we improved using new data structures and pruning techniques. On average, the MDA is 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude. Y1 - 2021 U6 - https://doi.org/10.1016/j.cor.2021.105424 VL - 135 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel T1 - Restricted Adaptivity in Stochastic Scheduling JF - 29th Annual European Symposium on Algorithms (ESA 2021) N2 - We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω(logm/loglogm). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an O(loglogm)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy. Y1 - 2021 U6 - https://doi.org/10.4230/LIPIcs.ESA.2021.79 VL - 204 SP - 79:1 EP - 79:14 ER - TY - JOUR A1 - Pronzato, Luc A1 - Sagnol, Guillaume T1 - Removing inessential points in c- and A-optimal design JF - Journal of Statistical Planning and Inference N2 - A design point is inessential when it does not contribute to an optimal design, and can therefore be safely discarded from the design space. We derive three inequalities for the detection of such inessential points in c-optimal design: the first two are direct consequences of the equivalence theorem for c-optimality; the third one is derived from a second-order cone programming formulation of c-optimal design. Elimination rules for A-optimal design are obtained as a byproduct. When implemented within an optimization algorithm, each inequality gives a screening test that may provide a substantial acceleration by reducing the size of the problem online. Several examples are presented with a multiplicative algorithm to illustrate the effectiveness of the approach. Y1 - 2021 UR - https://hal.archives-ouvertes.fr/hal-02868664 U6 - https://doi.org/10.1016/j.jspi.2020.11.011 VL - 213 SP - 233 EP - 252 ER - TY - GEN A1 - Löbel, Andreas T1 - Solving Large-Scale Multiple-Depot Vehicle Scheduling Problems N2 - This paper presents an integer linear programming approach with delayed column generation for the {\em NP} Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail all basic ingredients of our approach that are indispensable to solve truly large-scale real-world instances to optimality, and we report on computational investigations that are based on real-world instances from the city of Berlin, the city of Hamburg, and the region around Hamburg. These real-world instances have up to 25 thousand timetabled trips and 70 million dead-head trips. Computational tests using the data of the Hamburger Hochbahn AG indicate savings of several vehicles and a cost reduction of about 10\% compared with the solution provided by HOT II, the vehicle scheduling tool of the HanseCom GmbH, Hamburg. Parts of our algorithms are already integrated in the BERTA system of the Berliner Verkehrsbetriebe (BVG) and will soon be integrated in the MICROBUS system of the Gesellschaft für Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin. T3 - ZIB-Report - SC-97-17 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2866 ER - TY - THES A1 - Schultz, Rüdiger T1 - Structure and Stability in Two-Stage Stochastic Programming N2 - {\begin{footnotesize} This thesis is concerned with structural properties and the stability behaviour of two-stage stochastic programs. Chapter~1 gives an introduction into stochastic programming and a summary of the main results of the thesis. In Chapter~2 we present easily verifiable sufficient conditions for the strong convexity of the expected-recourse function in a stochastic program with linear complete recourse. Different levels of randomness in the data are considered. We start with models where only the right-hand side of the constraints is random and extend these results to the situation where also the technology matrix contains random entries. The statements on strong convexity imply new stability estimates for sets of optimal solutions when perturbing the underlying probability measure. We work out Hölder estimates (in terms of the $\mbox{L}_1$-Wasserstein distance) for optimal solution sets to linear recourse models with random technology matrix. In Chapter~3 ({\it joint work with Werner Römisch, Berlin}) we are aiming at the Lipschitz stability of optimal solution sets to linear recourse models with random right-hand side. To this end , we first adapt the distance notion for the underlying probability measures to the structure of the model and derive a Lipschitz estimate for optimal solutions based on that distance. Here, the strong convexity established in Chapter~2 turns out as an essential assumption. For applications, however, a Lipschitz estimate with respect to a more accesssible probability distance is desirable. Structural properties of the expected-recourse function finally permit such an estimate in terms of the Kolmogorov-Smirnov distance of linear transforms of the underlying measures. The general analysis is specified to estimation via empirical measures. We obtain a law of iterated logarithm, a large deviation estimate and an estimate for the asymptotic distribution of optimal solution sets. Chapters~4 and~5 deal with two-stage linear stochastic programs where integrality constraints occur in the second stage. In Chapter~4 we study basic continuity properties of the expected-recourse function for models with random right-hand side and random technology matrix. The joint continuity with respect to the decision variable and the underlying probability measure leads to qualitative statements on the stability of local optimal values and local optimal solutions. In Chapter~5 we demonstrate that a variational distance of probability measures based on a suitable Vapnik-\v{C}ervonenkis class of Borel sets leads to convergence rates of the Hölder type for the expected recourse as a function of the underlying probability measure. The rates carry over to the convergence of local optimal values. As an application we again consider estimation via empirical measures. Beside qualitative asymptotic results for optimal values and optimal solutions we obtain a law of iterated logarithm for optimal values. \end{footnotesize}} T3 - ZIB-Report - SC-95-15 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1819 ER - TY - THES A1 - Koch, Thorsten T1 - Jack-III Ein Branch & Cut-Verfahren zur Lösung des gewichteten Steinerbaumproblems in Graphen N2 - In der vorliegenden Arbeit werden die grundlegenden Gedanken und die Implementierung eines Branch & Cut-Algorithmus zur Lösung des gewichteten Steinerbaumproblems in Graphen beschrieben. Der Algorithmus basiert auf der linearen Relaxierung einer bidirektionalen ganzzahligen Formulierung des Problems. Wir werden das Problem einführen, drei ganzzahlige Modellierungen vorstellen, auf Reduktionsverfahren und Heuristiken eingehen sowie das Verfahren und seine Implementierung darstellen. Am Ende werden wir die Implementierung an 191 bekannten Probleminstanzen testen und auch optimale Lösungen f� ur zwei nach Wissen des Autors bis zu diesem Zeitpunkt ungelöste Instanzen liefern. Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9946 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - Decomposing Matrices into Blocks N2 - In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs. T3 - ZIB-Report - SC-97-15 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2849 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints N2 - In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time. T3 - ZIB-Report - SC-97-70 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3391 ER -