2 resultados para Degenerate bifurcation
em AMS Tesi di Dottorato - Alm@DL - Università di Bologna
Resumo:
In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.
Resumo:
Bioremediation implies the use of living organisms, primarily microorganisms, to convert environmental contaminants into less toxic forms. The impact of the consequences of hydrocarbon release in the environment maintain a high research interest in the study of microbial metabolisms associated with the biodegradation of aromatic and aliphatic hydrocarbons but also in the analysis of microbial enzymes that can convert petroleum substrates to value-added products. The studies described in this Thesis fall within the research field that directs the efforts into identifying gene/proteins involved in the catabolism of n-alkanes and into studying the regulatory mechanisms leading to their oxidation. In particular the studies were aimed at investigating the molecular aspects of the ability of Rhodococcus sp. BCP1 to grow on aliphatic hydrocarbons as sole carbon and energy sources. We studied the ability of Rhodococcus sp. BCP1 to grow on gaseous (C2-C4), liquid (C5-C16) and solid (C17-C28) n-alkanes that resulted to be biochemically correlated with the activity of one or more monooxygenases. In order to identify the alkane monooxygenase that is involved in the n-alkanes degradation pathway in Rhodococcus sp. BCP1, PCR-based methodology was applied by using degenerate primers targeting AlkB monooxygenase family members. As result, a chromosomal region, including the alkB gene cluster, was cloned from Rhodococcus sp. BCP1 genome. We characterized the products of this alkB gene cluster and the products of the orfs included in the flanking regions by comparative analysis with the homologues in the database. alkB gene expression studies were carried out by RT-PCR and by the construction of a promoter probe vector containing the lacZ gene downstream of the alkB promoter. B-galactosidase assays revealed the alkB promoter activity induced by n-alkanes and by n-alkanes metabolic products. Furthermore, the transcriptional start of alkB gene was determined by primer extension procedure. A proteomic approach was subsequently applied to compare the protein patterns expressed by BCP1 growing on n-butane, n-hexane, n-hexadecane or n-eicosane with the protein pattern expressed by BCP1 growing on succinate. The accumulation of enzymes specifically induced on n-alkanes was determined. These enzymes were identified by tandem mass spectrometry (LC/MS/MS). Finally, a prm gene, homologue to the gene family coding for soluble di-iron monooxygenases (SDIMOs), has been isolated from Rhodococcus sp. BCP1 genome. This gene product could be involved in the degradation of gaseous n-alkanes in this Rhodococcus strain. The versatility in utilizing hydrocarbons and the discovery of new remarkable metabolic activities outline the potential applications of this microorganism in environmental and industrial biotechnologies.