Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network
No full textConsolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems
Inside Front Cover: Numerical Investigation of a Coupled Micropillar - Waveguide System for Integrated Quantum Photonic Circuits (Adv. Quantum Technol. 12/2024)
No full text
Logic-Constrained Shortest Paths for Flight Planning
No full textThe Logic-Constrained Shortest Path Problem (LCSP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSP. We analyze its theoretical impact on the B&B algorithm. In the second part of the paper, we show how to model the Flight Planning Problem with TFRs as an LCSP and solve it using the branch and bound algorithm. We demonstrate the algorithm’s efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice
Computational Study of the Reactions of CH2 with HCNO and HNCO
No full textWe present a computational approach for screening reaction mechanisms with machine learning estimates of energy barriers. A comprehensive screening of thousands of reactions identified the CH2 reactions with HCNO and HNCO as possible sources of relatively complex organic molecules in space. We report detailed reaction mechanisms, including TS, intermediate, and product energies, calculated with density functional theory and coupled cluster theory. Singlet CH2, located 9 kcal/mol above the triplet ground state, reacts with HCNO or HNCO without a barrier, producing four prod11 ucts: CH2NCHO, N-methyleneformamide, the thermodynamically favored product; NHCHCHO, imine acetaldehyde; NHCHOCH; and (CH2OC)NH, oxiran-2-ylazanide. The lowest energy pathway for CH2 + HCNO, involving a triplet-to-singlet crossing,
has a barrier of 8 kcal/mol and leads to N -methyleneformamide, imine acetaldehyde, and NHCHOCH. The reaction of triplet CH2 with HNCO has a lowest energy pathway with a barrier of 11 kcal/mol, yielding CH2(CO)NH
Forecasting and modeling the dynamics of large-scale energy networks under the supply and demand balance constraint
No full textWith the emergence of ”Big Data” the analysis of large data sets of high-dimensional energy time series in network structures have become feasible. However, building large-scale data-driven and computationally efficient models to accurately capture the underlying spatial and temporal dynamics and forecast the multivariate time series data remains a great challenge. Additional constraints make the problem more challenging to solve with conventional methods. For example, to ensure the security of supply, energy networks require the demand and supply to be balanced.
This paper introduces a novel large-scale Hierarchical Network Regression model with Relaxed Balance constraint (HNR-RB) to investigate the network dynamics and predict multistep-ahead flows in the natural gas transmission network, where the total in- and out-flows of the network have to be balanced over a period of time. We concurrently address three main challenges: high dimensionality of networks with more than 100 nodes, unknown network dynamics, and constraint of balanced supply and demand in the network. The effectiveness of the proposed model is demonstrated through a real-world case study of forecasting demand and supply in a large-scale natural gas transmission network. The results demonstrate that HNR-RB outperforms alternative models for short- and mid-term horizons
Which algorithm to select in sports timetabling?
No full textAny sports competition needs a timetable, specifying when and where teams meet each other. The recent International Timetabling Competition (ITC2021) on sports timetabling showed that, although it is possible to develop general algorithms, the performance of each algorithm varies considerably over the problem instances. This paper provides a problem type analysis for sports timetabling, resulting in powerful insights into the strengths and weaknesses of eight state-of-the-art algorithms. Based on machine learning techniques, we propose an algorithm selection system that predicts which algorithm is likely to perform best based on the type of competition and constraints being used (i.e., the problem type) in a given sports timetabling problem instance. Furthermore, we visualize how the problem type relates to algorithm performance, providing insights and possibilities to further enhance several algorithms. Finally, we assess the empirical hardness of the instances. Our results are based on large computational experiments involving about 50 years of CPU time on more than 500 newly generated problem instances
On Geodesics in the Spaces of Constrained Curves
No full textIn this work, we study the geodesics of the space of certain geometrically and physically motivated subspaces of the space of immersed curves endowed with a first order Sobolev metric. This includes elastic curves and also an extension of some results on planar concentric circles to surfaces. The work focuses on intrinsic and constructive approaches
Approximating rolling stock rotations with integrated predictive maintenance
No full textWe 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