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.

Reproductive and developmental toxicity study using Sprague-Dawley rats exposed under various calendars to the weedkiller Glyphosate and commercial formulations Glyphosate-based

Glyphosate-based herbicides (GBHs) are the most globally used herbicides raising the risk of environmental exposition. Carcinogenic effects are only one component of the multiple adverse health effects of Glyphosate and GBHs that have been reported. Questions related to hazards and corresponding risks identified in relation to endocrine disrupting effects are rising. The present study investigated the possible reproductive/developmental toxicity of GBHs administered to male and female Sprague-Dawley rats under various calendar of treatment. Assessments included maternal and reproductive outcome of F0 and F1 dams exposed to GBHs throughout pregnancy and lactation and developmental landmarks and sexual characteristics of offspring. The study was designed in two stages. In the first stage Glyphosate, or its commercial formulation Roundup Bioflow, was administered to rats at the dose of 1.75 mg/kg bw/day (Glyphosate US Acceptable Daily Intake) from the prenatal period until adulthood. In the second stage, multiple toxicological parameters were simultaneously assessed, including multigeneration reproductive/developmental toxicity of Glyphosate and two GBHs (Roundup Bioflow and Ranger Pro). Man-equivalent doses, beginning from 0.5 mg/kg bw/day (ADI Europe) up to 50 mg/kg bw/day (NOAEL Glyphosate), were administered to male and female rats, covering specific windows of biological susceptibility. The results of stage 1 and preliminary data from stage 2 experiments characterize GBHs as probable endocrine disruptors as suggested by: 1) androgen-like effects of Roundup Bioflow, including a significant increase of anogenital distances in both males and females, delay of first estrous and increased testosterone in females; 2) slight puberty onset anticipation in the high dose of Ranger Pro group, observed in the F1 generation treated from in utero life until adulthood; 3) a delayed balano-preputial separation achievement in the high dose of Ranger Pro-treated males exposed only during the peri-pubertal period, indicating a direct and specific effect of GBHs depending on the timing of exposure.

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.