Search results for "optimization"
showing 10 items of 2824 documents
A Branch-and-Cut method for the Capacitated Location-Routing Problem
2011
International audience; Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots. The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles. The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities. The computational evaluation on three sets of instances (34 instances in total), with 5–10 potential depots and 20–88 …
Mode-superposition correction method for deterministic and stochastic analysis of structural systems
2001
The role played by the modal analysis in the framework of structural dynamics is fundamental from both deterministic and stochastic point of view. However the accuracy obtained by means of the classical modal analysis is not always satisfactory. Therefore it is clear the importance of methods able to correct the modal response in such a way to obtain the required accuracy. Many methods have been proposed in the last years but they are meaningful only when the forcing function is expressed by an analytical function. Moreover in stochastic analysis they fail for white noise excitation. In the paper a method able to give a very accurate response for both deterministic and stochastic input is p…
Longest Common Subsequence from Fragments via Sparse Dynamic Programming
1998
Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…
A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
2002
In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, t…
In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
2015
Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…
The Capacitated Arc Routing Problem: Lower bounds
1992
In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds…
Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem
2015
A dynamic time window relates to two operations that must be executed within a given time meaning that the difference between the points in time when the two operations are performed is bounded from above. The most prevalent context of dynamic time windows is when precedence is given for the two operations so that it is a priori specified that one operation must take place before the other. A prominent vehicle routing problem with dynamic time windows and precedence is the dial-a-ride problem (DARP), where user-specified transportation requests from origin to destination points must be serviced. The paper presents a new branch-and-cut-and-price solution approach for the DARP, the prototypi…
Reflections on the Hohmann Transfer
2004
Walter Hohmann was a civil engineer who studied orbital maneuvers in his spare time. In 1925, he published an important book (Ref. 1) containing his main result, namely, that the most economical transfer from a circular orbit to another circular orbit is achieved via an elliptical trajectory bitangent to the terminal orbits. With the advent of the space program some three decades later, the Hohmann transfer maneuver became the most fundamental maneuver in space. In this work, we present a complete study of the Hohmann transfer maneuver. After revisiting its known properties, we present a number of supplementary properties which are essential to the qualitative understanding of the maneuver.…
Local Green Power Supply Plants Based on Alcohol Regenerative Gas Turbines: Economic and Environmental Aspects
2020
Growing economies need green and renewable energy. Their financial development can reduce energy consumption (through energy-efficient technologies) and replace fossil fuels with renewable ones. Gas turbine engines are widely used in transport and industry. To improve their economic attractiveness and to reduce harmful emissions, including greenhouse gases, alternative fuels and waste heat recovery technologies can be used. A promising direction is the use of alcohol and thermo-chemical recuperation. The purpose of this study is to estimate the economic efficiency and carbon dioxide emissions of an alcohol-fueled regenerative gas turbine engine with thermo-chemical recuperation. The carbon …
Sensitivity analysis and process optimization of a natural gas dehydration unit using triethylene glycol
2019
Abstract Dehydration of natural gas by absorption using triethylene glycol (TEG) is a common industrial offshore procedure to ensure the compliance with the required water dew point specifications for midstream transportation. Two thermodynamic models, the UMR-PRU and the TST/NRTL, are applied for the process simulation while a preliminary economic evaluation has been conducted revealing that both yield overall similar results as for the fixed capital cost which is found to be in good agreement with reported literature values. Moreover, sensitivity analysis of several operational parameters of the process has been performed and optimized values are suggested aiming to reduce its energy requ…