A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Frequency-domain receiver design for doubly-selective channels

This work is devoted to the broadband wireless transmission techniques, which are serious candidates to be implemented in future broadband wireless and cellular systems, aiming at providing high and reliable data transmission and concomitantly high mobility. In order to cope with doubly-selective channels, receiver structures based on OFDM and SC-FDE block transmission techniques, are proposed, which allow cost-effective implementations, using FFT-based signal processing. The first subject to be addressed is the impact of the number of multipath components, and the diversity order, on the asymptotic performance of OFDM and SC-FDE, in uncoded and for different channel coding schemes. The obtained results show that the number of relevant separable multipath components is a key element that influences the performance of OFDM and SC-FDE schemes. Then, the improved estimation and detection performance of OFDM-based broadcasting systems, is introduced employing SFN (Single Frequency Network) operation. An initial coarse channel is obtained with resort to low-power training sequences estimation, and an iterative receiver with joint detection and channel estimation is presented. The achieved results have shown very good performance, close to that with perfect channel estimation. The next topic is related to SFN systems, devoting special attention to time-distortion effects inherent to these networks. Typically, the SFN broadcast wireless systems employ OFDM schemes to cope with severely time-dispersive channels. However, frequency errors, due to CFO, compromises the orthogonality between subcarriers. As an alternative approach, the possibility of using SC-FDE schemes (characterized by reduced envelope fluctuations and higher robustness to carrier frequency errors) is evaluated, and a technique, employing joint CFO estimation and compensation over the severe time-distortion effects, is proposed. Finally, broadband mobile wireless systems, in which the relative motion between the transmitter and receiver induces Doppler shift which is different or each propagation path, is considered, depending on the angle of incidence of that path in relation to the direction of travel. This represents a severe impairment in wireless digital communications systems, since that multipath propagation combined with the Doppler effects, lead to drastic and unpredictable fluctuations of the envelope of the received signal, severely affecting the detection performance. The channel variations due this effect are very difficult to estimate and compensate. In this work we propose a set of SC-FDE iterative receivers implementing efficient estimation and tracking techniques. The performance results show that the proposed receivers have very good performance, even in the presence of significant Doppler spread between the different groups of multipath components.

Cálculo dos níveis ótimos de rentabilidade para o desempenho energético de habitações residenciais unifamiliares objeto de reabilitação

Dissertação de mestrado em Construção e Reabilitação Sustentáveis

Otimização com restrições de complementaridade: algoritmos e aplicações

Tese de Doutoramento em Engenharia Industrial e de Sistemas (PDEIS)

Modelos de apoio às decisão na conceção e planeamento de um armazém

Programa Doutoral em Engenharia Industrial e de Sistemas.

Anderson localization of light in disordered superlattices containing graphene layers

We theoretically investigate light propagation and Anderson localization in one-dimensional disordered superlattices composed of dielectric stacks with graphene sheets in between. Disorder is introduced either on graphene material parameters ({\it e.g.} Fermi energy) or on the widths of the dielectric stacks. We derive an analytic expression for the localization length $\xi$, and compare it to numerical simulations using transfer matrix technique; a very good agreement is found. We demonstrate that the presence of graphene may strongly attenuate the anomalously delocalised Breswter modes, and is at the origin of a periodic dependence of $\xi$ on frequency, in contrast to the usual asymptotic decay, $\xi \propto \omega^{-2}$. By unveiling the effects of graphene on Anderson localization of light, we pave the way for new applications of graphene-based, disordered photonic devices in the THz spectral range.

Solving large 0–1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm

The artificial fish swarm algorithm has recently been emerged in continuous global optimization. It uses points of a population in space to identify the position of fish in the school. Many real-world optimization problems are described by 0-1 multidimensional knapsack problems that are NP-hard. In the last decades several exact as well as heuristic methods have been proposed for solving these problems. In this paper, a new simpli ed binary version of the artificial fish swarm algorithm is presented, where a point/ fish is represented by a binary string of 0/1 bits. Trial points are created by using crossover and mutation in the different fi sh behavior that are randomly selected by using two user de ned probability values. In order to make the points feasible the presented algorithm uses a random heuristic drop item procedure followed by an add item procedure aiming to increase the profit throughout the adding of more items in the knapsack. A cyclic reinitialization of 50% of the population, and a simple local search that allows the progress of a small percentage of points towards optimality and after that refines the best point in the population greatly improve the quality of the solutions. The presented method is tested on a set of benchmark instances and a comparison with other methods available in literature is shown. The comparison shows that the proposed method can be an alternative method for solving these problems.

Surface phenomena and hydrodynamic effects on the deposition of Pseudomonas fluorescens

Biofilm adhesion to metals (copper, aluminium and brass) was studied at two different velocities and pH values of 7 and 9. Both bacteria and metals showed negative surface charges at those values of pH, which tends to slow down adhesion. Film densities increased with the fluid velocity and were also affected by the pH and by the growth rate of the bacteria. Long duration tests based on heat transfer measurements were run at five different fluid velocities and at pH = 7, showing in general an asymptotic behaviour and a control of deposition by adhesion and growth phenomena.

Age, growth and population dynamics of lemon sole Microstomus kitt (Walbaum 1792) sampled off the West Coast of Ireland

The age, growth, maturity and population dynamics of lemon sole (Microstomus kitt), captured off the west coast of Ireland (ICES division Vllb), were determined for the period November 2000 to February 2002. The maximum age recorded was 14 years. Males of the population were dominated by 4 year olds, while females were dominated by 5 year olds. Females dominated the sex ratio in the overall sample, each month sampled, at each age and from 22cm in total length onwards (when N > 20). Possible reasons for the dominance of females in the sex ratio are discussed. Three models were used to obtain the parameters of the von Bertalanfly growth equation. These were the Ford-Walford plot (Beverton and Holt 1957), the Gulland and Holt plot (1959) and the Rafail (1973) method. Results of the fitted von Bertalanffy growth curves showed that female lemon sole o f f the west coast of Ireland grew faster than males and attained a greater size. Male and female lemon sole mature from 2 years of age onwards. There is evidence in the population o f a smaller asymptotic length (L«, = 34.47cm), faster growth rate (K = 0.1955) and younger age at first maturity, all of which are indicative o f a decrease in population size, when present results are compared to data collected in the same area 22 years earlier. Results of the yield per recruit curve indicate that lemon sole are currently being over-fished o f f the west coast of Ireland. Problems of selectivity within the sampling method, particularly at the discarding stage, may have influenced the outcome of results of the models used in the assessment of this stock. Therefore, additional/future work on this species should include catch data which incorporates discards and not landings data alone.

Failure rates modelling for heterogenous populations

Mixture of distributions, decreasing failure rate, increasing failure rate, proportional hazards model, accelerated life model, asymptotic behavior of mixture failure rate

Non-classical error bounds in the central limit theorem

The classical central limit theorem states the uniform convergence of the distribution functions of the standardized sums of independent and identically distributed square integrable real-valued random variables to the standard normal distribution function. While first versions of the central limit theorem are already due to Moivre (1730) and Laplace (1812), a systematic study of this topic started at the beginning of the last century with the fundamental work of Lyapunov (1900, 1901). Meanwhile, extensions of the central limit theorem are available for a multitude of settings. This includes, e.g., Banach space valued random variables as well as substantial relaxations of the assumptions of independence and identical distributions. Furthermore, explicit error bounds are established and asymptotic expansions are employed to obtain better approximations. Classical error estimates like the famous bound of Berry and Esseen are stated in terms of absolute moments of the random summands and therefore do not reflect a potential closeness of the distributions of the single random summands to a normal distribution. Non-classical approaches take this issue into account by providing error estimates based on, e.g., pseudomoments. The latter field of investigation was initiated by work of Zolotarev in the 1960's and is still in its infancy compared to the development of the classical theory. For example, non-classical error bounds for asymptotic expansions seem not to be available up to now ...

Aging and growth parameter from the Piaractus mesopotamicus (pacu) from the Cuiabá river, Mato Grosso, Brazil

This study has aims to determine the age and to estimate the growth parameters using scales of the species. Individuals of Piaractus mesopotamicus (Holmberg, 1887) used in this study were captured in the commercial fishery conducted in the region, along the year 2006. The model selected to express the growth of the species was the von Bertalanffy Sl= Sl∞*[1-exp-k(t-to)]. To determine if scales are suitable for studying the growth of pacu, we analyzed the relation between standard length (Sl) and the radius of the scales through linear regression. The period of annuli formation was determined analyzing the variations in the marginal increment and evaluating the consistency of the readings through the analysis of the coefficient of variations (CVs) for the average standard lengths of each age (number of rings) observed in the scales. The relationship between Ls of the fish and the radius of the scales showed that scales can be used to study the age and growth of P. mesopotamicus (R= 0.79). CVs were always below 20%, demonstrating the consistency of the readings. Annuli formation occurred in February, probably related to trophic migration that occurs in this month in the region. Equations that represents the growth in length obtained for P. mesopotamicus are Sl=50.00*[1-exp-0.18(t-(-3.00)] for males and Sl=59.23*[1-exp-0.14(t-(-3.36)] for females. The growth parameters obtained in this study were lower compared to other studies previously conducted for the same species and can related to overexploitation that species is submitted by fishing in the region. These values show also that females of pacu attain greater asymptotic length than males that growth faster.

Semidiscretization and long-time asymptotics of nonlinear diffusion equations

We review several results concerning the long time asymptotics of nonlinear diffusion models based on entropy and mass transport methods. Semidiscretization of these nonlinear diffusion models are proposed and their numerical properties analysed. We demonstrate the long time asymptotic results by numerical simulation and we discuss several open problems based on these numerical results. We show that for general nonlinear diffusion equations the long-time asymptotics can be characterized in terms of fixed points of certain maps which are contractions for the euclidean Wasserstein distance. In fact, we propose a new scaling for which we can prove that this family of fixed points converges to the Barenblatt solution for perturbations of homogeneous nonlinearities for values close to zero.

A note on the separability principle in economies with single-peaked

We consider the problem of allocating an infinitely divisible commodity among a group of agents with single-peaked preferences. A rule that has played a central role in the analysis of the problem is the so-called uniform rule. Chun (2001) proves that the uniform rule is the only rule satisfying Pareto optimality, no-envy, separability, and continuity (with respect to the social endowment). We obtain an alternative characterization by using a weak replication-invariance condition, called duplication-invariance, instead of continuity. Furthermore, we prove that Pareto optimality, equal division lower bound, and separability imply no-envy. Using this result, we strengthen one of Chun's (2001) characterizations of the uniform rule by showing that the uniform rule is the only rule satisfying Pareto optimality, equal división lower bound, separability, and either continuity or duplication-invariance.

Human capital in a global and knowledge-based economy. Part 2. Asssessment at the EU country level.

This report is an extension and partial update of de la Fuente and Ciccone (2002). It constructs estimates of the private and social rates of return on schooling for fourteen EU countries using microeconometric estimates of Mincerian wage equations, the results of cross-country growth regressions and OECD data on educational expenditures, tax rates and social benefits. The results are used to draw some tentative conclusions regarding the optimality of observed investment patterns and educational subsidy levels.