Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

Metaheuristics for Search Problems in Genomics - New Algorithms and Applications

In this thesis we made the first steps towards the systematic application of a methodology for automatically building formal models of complex biological systems. Such a methodology could be useful also to design artificial systems possessing desirable properties such as robustness and evolvability. The approach we follow in this thesis is to manipulate formal models by means of adaptive search methods called metaheuristics. In the first part of the thesis we develop state-of-the-art hybrid metaheuristic algorithms to tackle two important problems in genomics, namely, the Haplotype Inference by parsimony and the Founder Sequence Reconstruction Problem. We compare our algorithms with other effective techniques in the literature, we show strength and limitations of our approaches to various problem formulations and, finally, we propose further enhancements that could possibly improve the performance of our algorithms and widen their applicability. In the second part, we concentrate on Boolean network (BN) models of gene regulatory networks (GRNs). We detail our automatic design methodology and apply it to four use cases which correspond to different design criteria and address some limitations of GRN modeling by BNs. Finally, we tackle the Density Classification Problem with the aim of showing the learning capabilities of BNs. Experimental evaluation of this methodology shows its efficacy in producing network that meet our design criteria. Our results, coherently to what has been found in other works, also suggest that networks manipulated by a search process exhibit a mixture of characteristics typical of different dynamical regimes.

Formulations and Metaheuristics for combinatorial optimization problems

Combinatorial optimization problems have been strongly addressed throughout history. Their study involves highly applied problems that must be solved in reasonable times. This doctoral Thesis addresses three Operations Research problems: the first deals with the Traveling Salesman Problem with Pickups and Delivery with Handling cost, which was approached with two metaheuristics based on Iterated Local Search; the results show that the proposed methods are faster and obtain good results respect to the metaheuristics from the literature. The second problem corresponds to the Quadratic Multiple Knapsack Problem, and polynomial formulations and relaxations are presented for new instances of the problem; in addition, a metaheuristic and a matheuristic are proposed that are competitive with state of the art algorithms. Finally, an Open-Pit Mining problem is approached. This problem is solved with a parallel genetic algorithm that allows excavations using truncated cones. Each of these problems was computationally tested with difficult instances from the literature, obtaining good quality results in reasonable computational times, and making significant contributions to the state of the art techniques of Operations Research.

New biomaterials for packaging: a green approach to biopolymers and biocomposites

The impellent global environmental issues related to plastic materials can be addressed by following two different approaches: i) the development of synthetic strategies towards novel bio-based polymers, deriving from biomasses and thus identifiable as CO2-neutral materials, and ii) the development of new plastic materials, such as biocomposites, which are bio-based and biodegradable and therefore able to counteract the accumulation of plastic waste. In this framework, this dissertation presents extensive research efforts have been devoted to the synthesis and characterization of polyesters based on various bio-based monomers, including ω-pentadecalactone, vanillic acid, 2,5-furan dicarboxylic acid, and 5-hydroxymethylfurfural. With the aim of achieving high molecular weight polyesters, different synthetic strategies have been used as melt polycondensation, enzymatic polymerization, ring-opening polymerization and chain extension reaction. In particular, poly(ethylene vanillate) (PEV), poly(ω-pentadecalactone) (PPDL), poly(ethylene vanillate-co-pentadecalactone) (P(EV-co-PDL)), poly(2-hydroxymethyl 5-furancarboxylate) (PHMF), poly(ethylene 2,5-furandicarboxylate) (PEF) with different amount of diethylene glycol (DEG) unit amount, poly(propylene 2,5-furandicarboxylate) (PPF), poly(hexamethylene 2,5-furandicarboxylate), (PHF) have been prepared and extensively characterized. To improve the lacks of poly(hydroxybutyrate-co-valerate) (PHBV), its minimal formulations with natural additives and its blending with medium chain length PHAs (mcl-PHAs) have been tested. Additionally, this dissertation presents new biocomposites based on polylactic acid (PLA), poly(butylene succinate) (PBS), and PHBV, which are polymers both bio-based and biodegradable. To maintain their biodegradability only bio-fillers have been taken into account as reinforcing agents. Moreover, the commitment to sustainability has further limited the selection and led to the exclusive use of agricultural waste as fillers. Detailly, biocomposites have been obtained and discussed by using the following materials: PLA and agro-wastes like tree pruning, potato peels, and hay leftovers; PBS and exhausted non-compliant coffee green beans; PHBV and industrial starch extraction residues.