Equilibrium Assignments in Competitive and Cooperative Traffic Flow Routing

Part 18: Optimization in Collaborative Networks

Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

Strategic Optimization Techniques For FRTU Deployment and Chip Physical Design

Combinatorial optimization is a complex engineering subject. Although formulation often depends on the nature of problems that differs from their setup, design, constraints, and implications, establishing a unifying framework is essential. This dissertation investigates the unique features of three important optimization problems that can span from small-scale design automation to large-scale power system planning: (1) Feeder remote terminal unit (FRTU) planning strategy by considering the cybersecurity of secondary distribution network in electrical distribution grid, (2) physical-level synthesis for microfluidic lab-on-a-chip, and (3) discrete gate sizing in very-large-scale integration (VLSI) circuit. First, an optimization technique by cross entropy is proposed to handle FRTU deployment in primary network considering cybersecurity of secondary distribution network. While it is constrained by monetary budget on the number of deployed FRTUs, the proposed algorithm identi?es pivotal locations of a distribution feeder to install the FRTUs in different time horizons. Then, multi-scale optimization techniques are proposed for digital micro?uidic lab-on-a-chip physical level synthesis. The proposed techniques handle the variation-aware lab-on-a-chip placement and routing co-design while satisfying all constraints, and considering contamination and defect. Last, the first fully polynomial time approximation scheme (FPTAS) is proposed for the delay driven discrete gate sizing problem, which explores the theoretical view since the existing works are heuristics with no performance guarantee. The intellectual contribution of the proposed methods establishes a novel paradigm bridging the gaps between professional communities.

Mathematical models for cellular aggregation: the chemotactic instability and clustering formation

In this thesis we present a mathematical formulation of the interaction between microorganisms such as bacteria or amoebae and chemicals, often produced by the organisms themselves. This interaction is called chemotaxis and leads to cellular aggregation. We derive some models to describe chemotaxis. The first is the pioneristic Keller-Segel parabolic-parabolic model and it is derived by two different frameworks: a macroscopic perspective and a microscopic perspective, in which we start with a stochastic differential equation and we perform a mean-field approximation. This parabolic model may be generalized by the introduction of a degenerate diffusion parameter, which depends on the density itself via a power law. Then we derive a model for chemotaxis based on Cattaneo's law of heat propagation with finite speed, which is a hyperbolic model. The last model proposed here is a hydrodynamic model, which takes into account the inertia of the system by a friction force. In the limit of strong friction, the model reduces to the parabolic model, whereas in the limit of weak friction, we recover a hyperbolic model. Finally, we analyze the instability condition, which is the condition that leads to aggregation, and we describe the different kinds of aggregates we may obtain: the parabolic models lead to clusters or peaks whereas the hyperbolic models lead to the formation of network patterns or filaments. Moreover, we discuss the analogy between bacterial colonies and self gravitating systems by comparing the chemotactic collapse and the gravitational collapse (Jeans instability).

Leakage Temperature Dependency Aware Real-Time Scheduling for Power and Thermal Optimization

Catering to society’s demand for high performance computing, billions of transistors are now integrated on IC chips to deliver unprecedented performances. With increasing transistor density, the power consumption/density is growing exponentially. The increasing power consumption directly translates to the high chip temperature, which not only raises the packaging/cooling costs, but also degrades the performance/reliability and life span of the computing systems. Moreover, high chip temperature also greatly increases the leakage power consumption, which is becoming more and more significant with the continuous scaling of the transistor size. As the semiconductor industry continues to evolve, power and thermal challenges have become the most critical challenges in the design of new generations of computing systems. In this dissertation, we addressed the power/thermal issues from the system-level perspective. Specifically, we sought to employ real-time scheduling methods to optimize the power/thermal efficiency of the real-time computing systems, with leakage/ temperature dependency taken into consideration. In our research, we first explored the fundamental principles on how to employ dynamic voltage scaling (DVS) techniques to reduce the peak operating temperature when running a real-time application on a single core platform. We further proposed a novel real-time scheduling method, “M-Oscillations” to reduce the peak temperature when scheduling a hard real-time periodic task set. We also developed three checking methods to guarantee the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research from single core platform to multi-core platform. We investigated the energy estimation problem on the multi-core platforms and developed a light weight and accurate method to calculate the energy consumption for a given voltage schedule on a multi-core platform. Finally, we concluded the dissertation with elaborated discussions of future extensions of our research.

Wavelet analysis and hierarchical clustering of ofm phenotypic population's variations originated from southern america and europe and attempts of a first relation to molecular divergence.

In this work we compare Grapholita molesta Busck (Lepidoptera: Tortricidae) populations originated from Brazil, Chile, Spain, Italy and Greece using power spectral density and phylogenetic analysis to detect any similarities between the population macro- and the molecular micro-level. Log-transformed population data were normalized and AR(p) models were developed to generate for each case population time series of equal lengths. The time-frequency/scale properties of the population data were further analyzed using wavelet analysis to detect any population dynamics frequency changes and cluster the populations. Based on the power spectral of each population time series and the hierarchical clustering schemes, populations originated from Southern America (Brazil and Chile) exhibit similar rhythmic properties and are both closer related with populations originated from Greece. Populations from Spain and especially Italy, have higher distance by terms of periodic changes on their population dynamics. Moreover, the members within the same cluster share similar spectral information, therefore they are supposed to participate in the same temporally regulated population process. On the contrary, the phylogenetic approach revealed a less structured pattern that bears indications of panmixia, as the two clusters contain individuals from both Europe and South America. This preliminary outcome will be further assessed by incorporating more individuals and likely employed a second molecular marker.

Edge-aware Graph Attention Networks: Joint Reasoning On Text and Knowledge Graphs for Biomedical Question Answering

Much of the real-world dataset, including textual data, can be represented using graph structures. The use of graphs to represent textual data has many advantages, mainly related to maintaining a more significant amount of information, such as the relationships between words and their types. In recent years, many neural network architectures have been proposed to deal with tasks on graphs. Many of them consider only node features, ignoring or not giving the proper relevance to relationships between them. However, in many node classification tasks, they play a fundamental role. This thesis aims to analyze the main GNNs, evaluate their advantages and disadvantages, propose an innovative solution considered as an extension of GAT, and apply them to a case study in the biomedical field. We propose the reference GNNs, implemented with methodologies later analyzed, and then applied to a question answering system in the biomedical field as a replacement for the pre-existing GNN. We attempt to obtain better results by using models that can accept as input both node and edge features. As shown later, our proposed models can beat the original solution and define the state-of-the-art for the task under analysis.

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

Ssr-based Genetic Diversity And Structure Of Garlic Accessions From Brazil.

Garlic is a spice and a medicinal plant; hence, there is an increasing interest in 'developing' new varieties with different culinary properties or with high content of nutraceutical compounds. Phenotypic traits and dominant molecular markers are predominantly used to evaluate the genetic diversity of garlic clones. However, 24 SSR markers (codominant) specific for garlic are available in the literature, fostering germplasm researches. In this study, we genotyped 130 garlic accessions from Brazil and abroad using 17 polymorphic SSR markers to assess the genetic diversity and structure. This is the first attempt to evaluate a large set of accessions maintained by Brazilian institutions. A high level of redundancy was detected in the collection (50 % of the accessions represented eight haplotypes). However, non-redundant accessions presented high genetic diversity. We detected on average five alleles per locus, Shannon index of 1.2, HO of 0.5, and HE of 0.6. A core collection was set with 17 accessions, covering 100 % of the alleles with minimum redundancy. Overall FST and D values indicate a strong genetic structure within accessions. Two major groups identified by both model-based (Bayesian approach) and hierarchical clustering (UPGMA dendrogram) techniques were coherent with the classification of accessions according to maturity time (growth cycle): early-late and midseason accessions. Assessing genetic diversity and structure of garlic collections is the first step towards an efficient management and conservation of accessions in genebanks, as well as to advance future genetic studies and improvement of garlic worldwide.

Spectrophotometric Evaluation Of Dental Bleaching Under Orthodontic Bracket In Enamel And Dentin.

Aware of the diffusion capacity of bleaching in the dental tissues, many orthodontists are subjecting their patients to dental bleaching during orthodontic treatment for esthetic purposes or to anticipate the exchange of esthetic restorations after the orthodontic treatment. For this purpose specific products have been developed in pre-loaded whitening trays designed to fit over and around brackets and wires, with clinical efficacy proven. The objective of this study was to evaluate, through spectrophotometric reflectance, the effectiveness of dental bleaching under orthodontic bracket. Thirty-two bovine incisors crown blocks of 8 mm x 8 mm height lengths were used. Staining of tooth blocks with black tea was performed for six days. They were distributed randomly into 4 groups (1-home bleaching with bracket, 2- home bleaching without bracket, 3- office bleaching with bracket, 4 office bleaching without bracket). The color evaluation was performed (CIE L * a * b *) using color reflectance spectrophotometer. Metal brackets were bonded in groups 1 and 3. The groups 1 and 2 samples were subjected to the carbamide peroxide at 15%, 4 hours daily for 21 days. Groups 3 and 4 were subjected to 3 in-office bleaching treatment sessions, hydrogen peroxide 38%. After removal of the brackets, the second color evaluation was performed in tooth block, difference between the area under the bracket and around it, and after 7 days to verified color stability. Data analysis was performed using the paired t-test and two-way variance analysis and Tukey's. The home bleaching technique proved to be more effective compared to the office bleaching. There was a significant difference between the margin and center color values of the specimens that were subjected to bracket bonding. The bracket bond presence affected the effectiveness of both the home and office bleaching treatments. Key words:Tooth bleaching, spectrophotometry, orthodontics.

Altered Urinary Sodium Excretion Response After Central Cholinergic And Adrenergic Stimulation Of Adult Spontaneously Hypertensive Rats.

In this study, we hypothesized that blunting of the natriuresis response to intracerebroventricularly (i.c.v.) microinjected cholinergic and adrenergic agonists is involved in the development of hypertension in spontaneously hypertensive rats (SHR). We evaluated the effect of i.c.v. injection of cholinergic and noradrenergic agonists, at increasing concentrations, and of muscarinic cholinergic and α1 and α2-adrenoceptor antagonists on blood pressure and urinary sodium handling in SHR, compared with age-matched Wistar Kyoto rats (WR). We confirmed that CCh and NE microinjected into the lateral ventricle (LV) of conscious rats leads to enhanced natriuresis. This response was associated with increased proximal and post-proximal sodium excretion accompanied by an unchanged rate of glomerular filtration. We showed that cholinergic-induced natriuresis in WR and SHR was attenuated by previous i.c.v. administration of atropine and was significantly lower in the hypertensive strain than in WR. In both groups the natriuretic effect of injection of noradrenaline into the LV was abolished by previous local injection of an α1-adrenoceptor antagonist (prazosin). Conversely, LV α2-adrenoceptor antagonist (yohimbine) administration potentiated the action of noradrenaline. The LV yohimbine pretreatment normalized urinary sodium excretion in SHR compared with age-matched WR. In conclusion, these are, as far as we are aware, the first results showing the importance of interaction of central cholinergic and/or noradrenergic receptors in the pathogenesis of spontaneous hypertension. These experiments also provide good evidence of the existence of a central adrenergic mechanism consisting of α1 and α2-adrenoceptors which works antagonistically on regulation of renal sodium excretion.

The Role Of Edaphic Environment And Climate In Structuring Phylogenetic Pattern In Seasonally Dry Tropical Plant Communities.

Seasonally dry tropical plant formations (SDTF) are likely to exhibit phylogenetic clustering owing to niche conservatism driven by a strong environmental filter (water stress), but heterogeneous edaphic environments and life histories may result in heterogeneity in degree of phylogenetic clustering. We investigated phylogenetic patterns across ecological gradients related to water availability (edaphic environment and climate) in the Caatinga, a SDTF in Brazil. Caatinga is characterized by semiarid climate and three distinct edaphic environments - sedimentary, crystalline, and inselberg -representing a decreasing gradient in soil water availability. We used two measures of phylogenetic diversity: Net Relatedness Index based on the entire phylogeny among species present in a site, reflecting long-term diversification; and Nearest Taxon Index based on the tips of the phylogeny, reflecting more recent diversification. We also evaluated woody species in contrast to herbaceous species. The main climatic variable influencing phylogenetic pattern was precipitation in the driest quarter, particularly for herbaceous species, suggesting that environmental filtering related to minimal periods of precipitation is an important driver of Caatinga biodiversity, as one might expect for a SDTF. Woody species tended to show phylogenetic clustering whereas herbaceous species tended towards phylogenetic overdispersion. We also found phylogenetic clustering in two edaphic environments (sedimentary and crystalline) in contrast to phylogenetic overdispersion in the third (inselberg). We conclude that while niche conservatism is evident in phylogenetic clustering in the Caatinga, this is not a universal pattern likely due to heterogeneity in the degree of realized environmental filtering across edaphic environments. Thus, SDTF, in spite of a strong shared environmental filter, are potentially heterogeneous in phylogenetic structuring. Our results support the need for scientifically informed conservation strategies in the Caatinga and other SDTF regions that have not previously been prioritized for conservation in order to take into account this heterogeneity.

Breastfeeding and non-nutritive sucking patterns related to the prevalence of anterior open bite in primary dentition

OBJECTIVE: Nutritional, immunological and psychological benefts of exclusive breastfeeding for the frst 6 months of life are unequivocally recognized. However, mothers should also be aware of the importance of breastfeeding for promoting adequate oral development. This study evaluated the association between breastfeeding and non-nutritive sucking patterns and the prevalence of anterior open bite in primary dentition. MATERIAL AND METHODS: Infant feeding and non-nutritive sucking were investigated in a 3-6 year-old sample of 1,377 children, from São Paulo city, Brazil. Children were grouped according to breastfeeding duration: G1 - non-breastfed, G2 - shorter than 6 months, G3 - interruption between 6 and 12 months, and G4 - longer than 12 months. Three calibrated dentists performed clinical examinations and classifed overbite into 3 categories: normal, anterior open bite and deep bite. Chi-square tests (p<0.05) with odds ratio (OR) calculation were used for intergroup comparisons. The impact of breastfeeding and non-nutritive sucking on the prevalence of anterior open bite was analyzed using binary logistic regression. RESULTS: The prevalence estimates of anterior open bite were: 31.9% (G1), 26.1% (G2), 22.1% (G3), and 6.2% (G4). G1 would have signifcantly more chances of having anterior open bite compared with G4; in the total sample (OR=7.1) and in the subgroup without history of non-nutritive sucking (OR=9.3). Prolonging breastfeeding for 12 months was associated with a 3.7 times lower chance of having anterior open bite. In each year of persistence with non-nutritive sucking habits, the chance of developing this malocclusion increased in 2.38 times. CONCLUSIONS: Breastfeeding and non-nutritive sucking durations demonstrated opposite effects on the prediction of anterior open bite. Non-breastfed children presented signifcantly greater chances of having anterior open bite compared with those who were breastfed for periods longer than 12 months, demonstrating the benefcial infuence of breastfeeding on dental occlusion.

Serological survey of Rickettsia sp. in horses and dogs in an non-endemic area in Brazil

Brazilian Spotted Fever (BSF) is a lethal rickettsiosis in humans caused by the bacteria Rickettsia rickettsii, and is endemic in some areas of Brazil. Horses and dogs are part of the disease's life cycle and they may also serve as sentinel animals in epidemiological studies. The first human BSF case in the State of Paraná was reported in 2005. The present study was conducted in the municipality of Almirante Tamandaré, where no previous case of BSF was reported. Serum samples were collected from 71 horses and 20 dogs from nine properties in the area. Ticks were also collected from these animals. All farmers completed a questionnaire about their knowledge of BSF and animal health management. Serum samples were analyzed by indirect immunofluorescent-antibody assay (IFA) using R. rickettsii and R. parkeri as antigens. Ticks were analyzed by PCR for Rickettsia sp., and all of them were PCR-negative. Six horses (8.45%) and 4 dogs (20%) were identified as seropositive. Farmers were not aware of the correlation between the presence of ticks and risk of BSF. Although a non-endemic area, Almirante Tamandaré is a vulnerable environment for BSF and effective tick control measures are required.

Elevated Risk for HIV-1 Infection in Adolescents and Young Adults in São Paulo, Brazil

Background. Recent studies have sought to describe HIV infection and transmission characteristics around the world. Identification of early HIV-1 infection is essential to proper surveillance and description of regional transmission trends. In this study we compare people recently infected (RI) with HIV-1, as defined by Serologic Testing Algorithm for Recent HIV Seroconversion (STARHS), to those with chronic infection. Methodology/Principal Findings Subjects were identified from 2002-2004 at four testing sites in São Paulo. Of 485 HIV-1-positive subjects, 57 (12%) were defined as RI. Of the participants, 165 (34.0%) were aware of their serostatus at the time of HIV-1 testing. This proportion was statistically larger (p<0.001) among the individuals without recent infection (n = 158, 95.8%) compared to 7 individuals (4.2%) with recently acquired HIV-1 infection. In the univariate analysis, RI was more frequent in <25 and >59 years-old age strata (p<0.001). The majority of study participants were male (78.4%), 25 to 45 years-old (65.8%), white (63.2%), single (61.7%), with family income of four or more times the minimum wage (41.0%), but with an equally distributed educational level. Of those individuals infected with HIV-1, the predominant route of infection was sexual contact (89.4%), with both hetero (47.5%) and homosexual (34.5%) exposure. Regarding sexual activity in these individuals, 43.9% reported possible HIV-1 exposure through a seropositive partner, and 49.4% reported multiple partners, with 47% having 2 to 10 partners and 37.4% 11 or more; 53.4% of infected individuals reported condom use sometimes; 34.2% reported non-injecting, recreational drug use and 23.6% were reactive for syphilis by VDRL. Subjects younger than 25 years of age were most vulnerable according to the multivariate analysis. ) Conclusions/Significance In this study, we evaluated RI individuals and discovered that HIV-1 has been spreading among younger individuals in São Paulo and preventive approaches should, therefore, target this age stratum