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.

Oxidation and pyrolysis of methane and methyl formate in a plug flow reactor: computational and experimenal studies

Biodiesel represents a possible substitute to the fossil fuels; for this reason a good comprehension of the kinetics involved is important. Due to the complexity of the biodiesel mixture a common practice is the use of surrogate molecules to study its reactivity. In this work are presented the experimental and computational results obtained for the oxidation and pyrolysis of methane and methyl formate conducted in a plug flow reactor. The work was divided into two parts: the first one was the setup assembly whilst, in the second one, was realized a comparison between the experimental and model results; these last was obtained using models available in literature. It was started studying the methane since, a validate model was available, in this way was possible to verify the reliability of the experimental results. After this first study the attention was focused on the methyl formate investigation. All the analysis were conducted at different temperatures, pressures and, for the oxidation, at different equivalence ratios. The results shown that, a good comprehension of the kinetics is reach but efforts are necessary to better evaluate kinetics parameters such as activation energy. The results even point out that the realized setup is adapt to study the oxidation and pyrolysis and, for this reason, it will be employed to study a longer chain esters with the aim to better understand the kinetic of the molecules that are part of the biodiesel mixture.

Experimental results on gravity driven fully condensing flows in vertical tubes, their agreement with theory, and their differences with shear driven flows' boundary-condition sensitivities

This doctoral thesis presents the experimental results along with a suitable synthesis with computational/theoretical results towards development of a reliable heat transfer correlation for a specific annular condensation flow regime inside a vertical tube. For fully condensing flows of pure vapor (FC-72) inside a vertical cylindrical tube of 6.6 mm diameter and 0.7 m length, the experimental measurements are shown to yield values of average heat transfer co-efficient, and approximate length of full condensation. The experimental conditions cover: mass flux G over a range of 2.9 kg/m2-s ≤ G ≤ 87.7 kg/m2-s, temperature difference ∆T (saturation temperature at the inlet pressure minus the mean condensing surface temperature) of 5 ºC to 45 ºC, and cases for which the length of full condensation xFC is in the range of 0 < xFC < 0.7 m. The range of flow conditions over which there is good agreement (within 15%) with the theory and its modeling assumptions has been identified. Additionally, the ranges of flow conditions for which there are significant discrepancies (between 15 -30% and greater than 30%) with theory have also been identified. The paper also refers to a brief set of key experimental results with regard to sensitivity of the flow to time-varying or quasi-steady (i.e. steady in the mean) impositions of pressure at both the inlet and the outlet. The experimental results support the updated theoretical/computational results that gravity dominated condensing flows do not allow such elliptic impositions.

A study of computational methods to analyze gene expression data

The recent advent of new technologies has led to huge amounts of genomic data. With these data come new opportunities to understand biological cellular processes underlying hidden regulation mechanisms and to identify disease related biomarkers for informative diagnostics. However, extracting biological insights from the immense amounts of genomic data is a challenging task. Therefore, effective and efficient computational techniques are needed to analyze and interpret genomic data. In this thesis, novel computational methods are proposed to address such challenges: a Bayesian mixture model, an extended Bayesian mixture model, and an Eigen-brain approach. The Bayesian mixture framework involves integration of the Bayesian network and the Gaussian mixture model. Based on the proposed framework and its conjunction with K-means clustering and principal component analysis (PCA), biological insights are derived such as context specific/dependent relationships and nested structures within microarray where biological replicates are encapsulated. The Bayesian mixture framework is then extended to explore posterior distributions of network space by incorporating a Markov chain Monte Carlo (MCMC) model. The extended Bayesian mixture model summarizes the sampled network structures by extracting biologically meaningful features. Finally, an Eigen-brain approach is proposed to analyze in situ hybridization data for the identification of the cell-type specific genes, which can be useful for informative blood diagnostics. Computational results with region-based clustering reveals the critical evidence for the consistency with brain anatomical structure.

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37: 695-705, 1990); Bertolissi (J Mater Process Technol 107: 459-465, 2000), Aldowaisan and Allahverdi (Omega 32: 345-352, 2004) and the Chins heuristic by Fink and Voa (Eur J Operat Res 151: 400-414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.

Numerical Study of Hypersonic Leeward Flow over a Blunt Nosed Delta Wing

A kinetic theory based Navier-Stokes solver has been implemented on a parallel supercomputer (Intel iPSC Touchstone Delta) to study the leeward flowfield of a blunt nosed delta wing at 30-deg incidence at hypersonic speeds (similar to the proposed HERMES aerospace plane). Computational results are presented for a series of grids for both inviscid and laminar viscous flows at Reynolds numbers of 225,000 and 2.25 million. In addition, comparisons are made between the present and two independent calculations of the some flows (by L. LeToullec and P. Guillen, and S. Menne) which were presented at the Workshop on Hypersonic Flows for Re-entry Problems, Antibes, France, 1991.

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature. (C) 2009 Elsevier Ltd. All rights reserved.

Transport in bidisperse adsorbents: Significance of the macroscopic adsorbate flux

Transport in bidisperse adsorbents is investigated here, while incorporating a two-dimensional model for adsorbate diffusion in the microparticles. The latter treatment permits consideration of the macropore concentration variation around the microparticle surface, and thereby predicts an adsorbate through-flux on the macroscopic coordinate. Such a through-flux has earlier been postulated in the literature, but with unrealistic mechanistic justification. The new model therefore resolves the existing ambiguity in this regard, and covers the entire spectrum of behaviour between microparticle and macropore diffusion control. Computational results show that if the macroscopic adsorbate flux, ignored in the conventional analysis, has a significant contribution to the total flux under macropore control conditions then it is always important even when the microparticle diffusion resistance is not negligible. The effect of various parameters such as relative microparticle size and isotherm heterogeneity on the uptake is also studied and discussed. (C) 1997 Elsevier Science Ltd.

Computation of the linear elastic properties of random porous materials with a wide variety of microstructure

A finite-element method is used to study the elastic properties of random three-dimensional porous materials with highly interconnected pores. We show that Young's modulus, E, is practically independent of Poisson's ratio of the solid phase, nu(s), over the entire solid fraction range, and Poisson's ratio, nu, becomes independent of nu(s) as the percolation threshold is approached. We represent this behaviour of nu in a flow diagram. This interesting but approximate behaviour is very similar to the exactly known behaviour in two-dimensional porous materials. In addition, the behaviour of nu versus nu(s) appears to imply that information in the dilute porosity limit can affect behaviour in the percolation threshold limit. We summarize the finite-element results in terms of simple structure-property relations, instead of tables of data, to make it easier to apply the computational results. Without using accurate numerical computations, one is limited to various effective medium theories and rigorous approximations like bounds and expansions. The accuracy of these equations is unknown for general porous media. To verify a particular theory it is important to check that it predicts both isotropic elastic moduli, i.e. prediction of Young's modulus alone is necessary but not sufficient. The subtleties of Poisson's ratio behaviour actually provide a very effective method for showing differences between the theories and demonstrating their ranges of validity. We find that for moderate- to high-porosity materials, none of the analytical theories is accurate and, at present, numerical techniques must be relied upon.

Tide-induced water table fluctuations in coastal aquifers bounded by rhythmic shorelines

Previous studies on tidal water table dynamics in unconfined coastal aquifers have focused on the inland propagation of oceanic tides in the cross-shore direction based on the assumption of a straight coastline. Here, two-dimensional analytical solutions are derived to study the effects of rhythmic coastlines on tidal water table fluctuations. The computational results demonstrate that the alongshore variations of the coastline can affect the water table behavior significantly, especially in areas near the centers of the headland and embayment. With the coastline shape effects ignored, traditional analytical solutions may lead to large errors in predicting coastal water table fluctuations or in estimating the aquifer's properties based on these signals. The conditions under which the coastline shape needs to be considered are derived from the new analytical solution.

Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A*

Utilizar robôs autônomos capazes de planejar o seu caminho é um desafio que atrai vários pesquisadores na área de navegação de robôs. Neste contexto, este trabalho tem como objetivo implementar um algoritmo PSO híbrido para o planejamento de caminhos em ambientes estáticos para veículos holonômicos e não holonômicos. O algoritmo proposto possui duas fases: a primeira utiliza o algoritmo A* para encontrar uma trajetória inicial viável que o algoritmo PSO otimiza na segunda fase. Por fim, uma fase de pós planejamento pode ser aplicada no caminho a fim de adaptá-lo às restrições cinemáticas do veículo não holonômico. O modelo Ackerman foi considerado para os experimentos. O ambiente de simulação de robótica CARMEN (Carnegie Mellon Robot Navigation Toolkit) foi utilizado para realização de todos os experimentos computacionais considerando cinco instâncias de mapas geradas artificialmente com obstáculos. O desempenho do algoritmo desenvolvido, A*PSO, foi comparado com os algoritmos A*, PSO convencional e A* Estado Híbrido. A análise dos resultados indicou que o algoritmo A*PSO híbrido desenvolvido superou em qualidade de solução o PSO convencional. Apesar de ter encontrado melhores soluções em 40% das instâncias quando comparado com o A*, o A*PSO apresentou trajetórias com menos pontos de guinada. Investigando os resultados obtidos para o modelo não holonômico, o A*PSO obteve caminhos maiores entretanto mais suaves e seguros.

Error bounds for low-rank approximations of the first exponential integral kernel

A hierarchical matrix is an efficient data-sparse representation of a matrix, especially useful for large dimensional problems. It consists of low-rank subblocks leading to low memory requirements as well as inexpensive computational costs. In this work, we discuss the use of the hierarchical matrix technique in the numerical solution of a large scale eigenvalue problem arising from a finite rank discretization of an integral operator. The operator is of convolution type, it is defined through the first exponential-integral function and, hence, it is weakly singular. We develop analytical expressions for the approximate degenerate kernels and deduce error upper bounds for these approximations. Some computational results illustrating the efficiency and robustness of the approach are presented.

Electromagnetic transients analysis of lightning overvoltages on wind power plants

As wind power generation undergoes rapid growth, lightning and overvoltage incidents involving wind power plants have come to be regarded as a serious problem. Firstly, lightning location systems are discussed, as well as important parameters regarding lightning protection. Also, this paper presents a case study, based on a wind turbine with an interconnecting transformer, for the study of adequate lightning and overvoltage protection measures. The electromagnetic transients circuit under study is described, and computational results are presented.

Avaliação da dose absorvida na tiróide, em cintigrafias com 123I e Na99mTcO4 utilizando modelos biocinéticos e métodos de Monte Carlo

Mestrado em Radiações Aplicadas às Tecnologias da Saúde. Área de especialização: Protecção contra Radiações