Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <p><br><p>To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <p><br><p>To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.<p><br><p>Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <p><br><p>In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: <p>1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; <p>2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

No description available.

Au cours des dernières années, la technologie GNSS a attiré beaucoup d’attention autour du monde et elle a été largement appliquée dans de nombreux domaines. D'autre part, le système d'exploitation ferroviaire avancé a été largement utilisé pour assurer la sécurité, la sûreté et l'efficacité du réseau ferroviaire. L'efficacité de ce système se fonde sur la disponibilité du positionnement fiable du train. L’application de cette technologie au positionnement du train est un domaine de recherche très prometteur. Dans cette thèse, plusieurs algorithmes sont proposés pour le positionnement du train en utilisant des signaux GNSS et un modèle géométrique de voie stocké dans la base de données à bord du train. Premièrement, la distance, vitesse du train sont estimées en utilisant des signaux GNSS et un modèle géométrique ‘idéal’ qui est composé de lignes droites, de courbes de transition et d'arcs de cercle. L’impact du rayon de courbure de la voie sur ces estimations est étudié. Deuxièmement, la distance, vitesse du train sont estimées en utilisant des signaux GNSS et un modèle géométrique ‘non-idéal’ qui est approché par une ligne polygonale avec un certain niveau d'incertitude. L’impact de l’incertitude de la voie sur ces estimations est étudié. Finalement, la distance, vitesse du train sont estimées à l’aide d’intégration des mesures GNSS et une base de données bruitée. L’impact des erreurs de GNSS et de la base de données sur ces estimations est étudié / Over these years, GNSS technology has attracted many attentions around world and it has been widely applied in navigation for airplanes, ground vehicles and boats. On the other hand, advanced railway operating systems have been widely used to guarantee the safety and efficiency of the railway network. The efficiency of these systems is based on the availability of reliable train positioning. Hence, applying GNSS technology to the train positioning is a very promising research area, since it has such important benefits as lower initial costs and lower maintenance. In this thesis, several algorithms are proposed for train positioning by using GNSS signals and the railway centerline stored in the onboard computer database. At first, the train travelled distance, speed are estimated by using GNSS signals and an ''ideal'' railway centerline which is composed of straight line segments, transition curves and arcs of circles. The impact of the railroad curvature on these estimations is studied. Secondly, the train travelled distance, speed are estimated by using GNSS signals and a ''non-ideal'' railway centerline which is defined by a polygonal line with some level of uncertainty. The impact of the track geometric model imprecision on these estimations is studied. Finally, the train travelled distance, speed are estimated by integrating the GNSS measurements with a track database. The impact of the GNSS measurements and the track database errors on these estimations is studied

Thesis (Ph.D. (Statistics)) -- University of Limpopo, 2019 / This study presents the application of Direct and Indirect methods of Small AreaEstimation(SAE)techniques. Thestudyisaimedatestimatingthetrends and the proportions of households accessing water, sanitation, and electricity for lighting at small areas of the Limpopo Province, South Africa. The study modified Statistics South Africa’s General Household Survey series 2009-2015 and Census 2011 data. The option categories of three variables: Water, Sanitation and Electricity for lighting, were re-coded. Empirical Bayes and Hierarchical Bayes models known as Markov Chain Monte Carlo (MCMC) methods were used to refine estimates in SAS. The Census 2011 data aggregated in ‘Supercross’ was used to validate the results obtained from the models. The SAE methods were applied to account for the census undercoverage counts and rates. It was found that the electricity services were more prioritised than water and sanitation in the Capricorn District of the Limpopo Province. The greatest challenge, however, lies with the poor provision of sanitation services in the country, particularly in the small rural areas. The key point is to suggestpolicyconsiderationstotheSouthAfricangovernmentforfutureequitable provisioning of water, sanitation and electricity services across the country.

Threaded fasteners tend to break and loosen when exposed to cyclic loads or potent temperature variations. Additionally, if the joint is held tightly to the structure, distortion will occur under thermal expansion issues. These complications can be prevented by identifying and regulating the clamping force to an appropriate degree – adapted to the properties of the joint. Torque-controlled tightening is a way of monitoring the clamping force, but it assumes constant friction and therefore has low accuracy, with an error of around 17% - 43%.This thesis investigates if the friction and clamping force can be estimated using the Extended and Unscented Kalman filters to increase the precision of the torque-controlled methodology. Before the investigation, data were collected for two widely used tightening strategies. The first tightening strategy is called Continuous Drive, where the angular velocity is kept at a constant speed while torque is increased. The second strategy is TurboTight, where the angular velocity starts at a very high speed and decreases with increased torque. The collected data were noisy and had to be filtered. A hybrid between a Butterworth lowpass filter and a Sliding Window was developed and exploited for noise cancellation.The investigations revealed that it was possible to use both the Extended and Unscented Kalman filers to estimate friction and clamping force in threaded fasteners. In Continuous Drive tightening, both the EKF and UKF performed well - with an averagequality factor of 81.87% and 88.38%, and with an average error (at max torque) of 3.54% and 4.09%, respectively. However, the TurboTight strategy was much more complex and had a higher order of statistical moments to account for. Thus, the UKF outperformed the EKF with an average quality factor of 93.02% relative to 24.49%, and with an average error (at max torque) of 3.50% compared to 4.19%

The enhancement of the reliability, security, and resiliency of electric power systems depends on the availability of fast, accurate, and robust dynamic state estimators. These estimators should be robust to gross errors on the measurements and the model parameter values while providing good state estimates even in the presence of large dynamical system model uncertainties and non-Gaussian thick-tailed process and observation noises. It turns out that the current Kalman filter-based dynamic state estimators given in the literature suffer from several important shortcomings, precluding them from being adopted by power utilities for practical applications. To be specific, they cannot handle (i) dynamic model uncertainty and parameter errors; (ii) non-Gaussian process and observation noise of the system nonlinear dynamic models; (iii) three types of outliers; and (iv) all types of cyber attacks. The three types of outliers, including observation, innovation, and structural outliers are caused by either an unreliable dynamical model or real-time synchrophasor measurements with data quality issues, which are commonly seen in the power system. To address these challenges, we have pioneered a general theoretical framework that advances both robust statistics and robust control theory for robust dynamic state and parameter estimation of a cyber-physical system. Specifically, the generalized maximum-likelihood-type (GM)-estimator, the unscented Kalman filter (UKF), and the H-infinity filter are integrated into a unified framework to yield various centralized and decentralized robust dynamic state estimators. These new estimators include the GM-iterated extended Kalman filter (GM-IEKF), the GM-UKF, the H-infinity UKF and the robust H-infinity UKF. The GM-IEKF is able to handle observation and innovation outliers but its statistical efficiency is low in the presence of non-Gaussian system process and measurement noise. The GM-UKF addresses this issue and achieves a high statistical efficiency under a broad range of non-Gaussian process and observation noise while maintaining the robustness to observation and innovation outliers. A reformulation of the GM-UKF with multiple hypothesis testing further enables it to handle structural outliers. However, the GM-UKF may yield biased state estimates in presence of large system uncertainties. To this end, the H-infinity UKF that relies on robust control theory is proposed. It is shown that H-infinity is able to bound the system uncertainties but lacks of robustness to outliers and non-Gaussian noise. Finally, the robust H-infinity filter framework is proposed that leverages the H-infinity criterion to bound system uncertainties while relying on the robustness of GM-estimator to filter out non-Gaussian noise and suppress outliers. Furthermore, these new robust estimators are applied for system bus frequency monitoring and control and synchronous generator model parameter calibration. Case studies of several different IEEE standard systems show the efficiency and robustness of the proposed estimators. / Ph. D. / The enhancement of the reliability, security, and resiliency of electric power systems depends on the availability of fast, accurate, and robust dynamic state estimators. These estimators should be robust to gross errors on the measurements and the model parameter values while providing good state estimates even in the presence of large dynamical system model uncertainties and non-Gaussian thick-tailed process and observation noises. There are three types of gross errors or outliers, namely, observation, innovation, and structural outliers. They can be caused by either an unreliable dynamical model or real-time synchrophasor measurements with data quality issues, which are commonly seen in the power system. The system uncertainties can be induced in several ways, including i) unknowable system inputs, such as noise, parameter variations and actuator failures, to name a few; ii) unavailable inputs, such as unmeasured mechanical power, field voltage of the exciter, unknown fault location; and iii) inaccuracies of the model parameter values of the synchronous generators, the loads, the lines, and the transformers, to name a few. It turns out that the current Kalman filter-based dynamic state estimators suffer from several important shortcomings, precluding them from being adopted by power utilities for practical applications. To address these challenges, this dissertation has proposed a general theoretical framework that advances both robust statistics and robust control theory for robust dynamic state and parameter estimation. Specifically, the robust generalized maximum-likelihood-type (GM)- estimator, the nonlinear filter, i.e., unscented Kalman filter (UKF), and the H-infinity filter are integrated into a unified framework to produce various robust dynamic state estimators. These new estimators include the robust GM-IEKF, the robust GM-UKF, the H-infinity UKF and the robust H-infinity UKF. Specifically, the GM-IEKF deals with the observation and innovation outliers but achieving relatively low statistical efficiency in the presence of non-Gaussian system process and measurement noise. To address that, the robust GM-UKF is proposed that is able to achieve a high statistical efficiency under a broad range of non-Gaussian noise while maintaining the robustness to observation and innovation outliers. A reformulation of the GM-UKF with multiple hypothesis testing further enables it to handle three types of outliers. However, the GM-UKF may yield biased state estimates in presence of large system uncertainties. To this end, the H-infinity UKF that depends on robust control theory is proposed. It is able to bound the system uncertainties but lacks of robustness to outliers and non-Gaussian noise. Finally, the robust H-infinity filter framework is proposed that relies on the H-infinity criterion to bound system uncertainties while leveraging the robustness of GM-UKF to filter out non-Gaussian noise and suppress outliers. These new robust estimators are applied for system bus frequency monitoring and control and synchronous generator model parameter calibration. Case studies of several different IEEE standard systems show the efficiency and robustness of the proposed estimators.

Thesis (PhD (Statistics and Actuarial Sciences))--Stellenbosch University, 2008. / We consider the problem of model assessment by risk estimation. Various approaches to risk estimation are considered in a uni ed framework. This a discussion of various complexity dimensions and approaches to obtaining bounds on covering numbers is also presented. The second type of training sample interval estimator discussed in the thesis is Rademacher bounds. These bounds use advanced concentration inequalities, so a chapter discussing such inequalities is provided. Our discussion of Rademacher bounds leads to the presentation of an alternative, slightly stronger, form of the core result used for deriving local Rademacher bounds, by avoiding a few unnecessary relaxations. Next, we turn to a discussion of PAC-Bayesian bounds. Using an approach developed by Olivier Catoni, we develop new PAC-Bayesian bounds based on results underlying Hoe ding's inequality. By utilizing Catoni's concept of \exchangeable priors", these results allowed the extension of a covering number-based result to averaging classi ers, as well as its corresponding algorithm- and data-dependent result. The last contribution of the thesis is the development of a more exible shell decomposition bound: by using Hoe ding's tail inequality rather than Hoe ding's relative entropy inequality, we extended the bound to general loss functions, allowed the use of an arbitrary number of bins, and introduced between-bin and within-bin \priors". Finally, to illustrate the calculation of these bounds, we applied some of them to the UCI spam classi cation problem, using decision trees and boosted stumps. framework is an extension of a decision-theoretic framework proposed by David Haussler. Point and interval estimation based on test samples and training samples is discussed, with interval estimators being classi ed based on the measure of deviation they attempt to bound. The main contribution of this thesis is in the realm of training sample interval estimators, particularly covering number-based and PAC-Bayesian interval estimators. The thesis discusses a number of approaches to obtaining such estimators. The rst type of training sample interval estimator to receive attention is estimators based on classical covering number arguments. A number of these estimators were generalized in various directions. Typical generalizations included: extension of results from misclassi cation loss to other loss functions; extending results to allow arbitrary ghost sample size; extending results to allow arbitrary scale in the relevant covering numbers; and extending results to allow arbitrary choice of in the use of symmetrization lemmas. These extensions were applied to covering number-based estimators for various measures of deviation, as well as for the special cases of misclassi - cation loss estimators, realizable case estimators, and margin bounds. Extended results were also provided for strati cation by (algorithm- and datadependent) complexity of the decision class. In order to facilitate application of these covering number-based bounds,

Cette thèse porte sur l'analyse des performances en traitement du signal et se compose de deux parties: Premièrement, nous étudions les bornes inférieures dans la caractérisation et la prédiction des performances en termes d'erreur quadratique moyenne (EQM). Les bornes inférieures de l'EQM donne la variance minimale qu'un estimateur peut atteindre et peuvent être divisées en deux catégories: les bornes déterministes pour le modèle où les paramètres sont supposés déterministes (mais inconnus), et les bornes Bayésiennes pour le modèle où les paramètres sont supposés aléatoires. En particulier, nous dérivons les expressions analytiques de ces bornes pour deux applications différentes: (i) La première est la localisation des sources en utilisant un radar multiple-input multiple-output (MIMO). Nous considérons les bornes inférieures dans deux contextes c'est-à-dire avec ou sans erreurs de modèle. (ii) La deuxième est l'estimation de phase d'impulsion de pulsars à rayon X qui est une solution potentielle pour la navigation autonome dans l'espace. Pour cette application, nous avons calculé plusieurs bornes inférieures de l'EQM dans le contexte de données modélisées par une loi de Poisson (complétant ainsi les travaux disponibles dans la littérature où les données sont modélisées par une loi gaussienne). Deuxièmement, nous étudions le seuil statistique de résolution limite (SRL), qui est la distance minimale en termes des paramètres d'intérêts entre les deux signaux permettant de séparer / estimer correctement les paramètres d'intérêt. Plus précisément, nous dérivons le SRL dans deux contextes: le traitement d'antenne et le radar MIMO en utilisant deux approches basées sur la théorie de l'estimation et sur la théorie de l'information. Finalement, nous proposons des expressions compactes du SRL dans le cas d'erreurs de modèle. / This manuscript concerns the performance analysis in signal processing and consists into two parts : First, we study the lower bounds in characterizing and predicting the estimation performance in terms of mean square error (MSE). The lower bounds on the MSE give the minimum variance that an estimator can expect to achieve and it can be divided into two categories depending on the parameter assumption: the so-called deterministic bounds dealing with the deterministic unknown parameters, and the so-called Bayesian bounds dealing with the random unknown parameter. Particularly, we derive the closed-form expressions of the lower bounds for two applications in two different fields: (i) The first one is the target localization using the multiple-input multiple-output (MIMO) radar in which we derive the lower bounds in the contexts with and without modeling errors, respectively. (ii) The other one is the pulse phase estimation of X-ray pulsars which is a potential solution for autonomous deep space navigation. In this application, we show the potential universality of lower bounds to tackle problems with parameterized probability density function (pdf) different from classical Gaussian pdf since in X-ray pulse phase estimation, observations are modeled with a Poisson distribution. Second, we study the statistical resolution limit (SRL) which is the minimal distance in terms of the parameter of interest between two signals allowing to correctly separate/estimate the parameters of interest. More precisely, we derive the SRL in two contexts: array processing and MIMO radar by using two approaches based on the estimation theory and information theory. We also present in this thesis the usefulness of SRL in optimizing the array system.

This dissertation studies several aspects of the interface between information theory and signal processing. Several new and existing results in information theory are researched from the perspective of signal processing. Similarly, some fundamental results in signal processing and statistics are studied from the information theoretic viewpoint. The first part of this dissertation focuses on illustrating the equivalence between Stein's identity and De Bruijn's identity, and providing two extensions of De Bruijn's identity. First, it is shown that Stein's identity is equivalent to De Bruijn's identity in additive noise channels with specific conditions. Second, for arbitrary but fixed input and noise distributions, and an additive noise channel model, the first derivative of the differential entropy is expressed as a function of the posterior mean, and the second derivative of the differential entropy is expressed in terms of a function of Fisher information. Several applications over a number of fields, such as statistical estimation theory, signal processing and information theory, are presented to support the usefulness of the results developed in Section 2. The second part of this dissertation focuses on three contributions. First, a connection between the result, proposed by Stoica and Babu, and the recent information theoretic results, the worst additive noise lemma and the isoperimetric inequality for entropies, is illustrated. Second, information theoretic and estimation theoretic justifications for the fact that the Gaussian assumption leads to the largest Cramer-Rao lower bound (CRLB) is presented. Third, a slight extension of this result to the more general framework of correlated observations is shown. The third part of this dissertation concentrates on deriving an alternative proof for an extremal entropy inequality (EEI), originally proposed by Liu and Viswanath. Compared with the proofs, presented by Liu and Viswanath, the proposed alternative proof is simpler, more direct, and more information-theoretic. An additional application for the extremal inequality is also provided. Moreover, this section illustrates not only the usefulness of the EEI but also a novel method to approach applications such as the capacity of the vector Gaussian broadcast channel, the lower bound of the achievable rate for distributed source coding with a single quadratic distortion constraint, and the secrecy capacity of the Gaussian wire-tap channel. Finally, a unifying variational and novel approach for proving fundamental information theoretic inequalities is proposed. Fundamental information theory results such as the maximization of differential entropy, minimization of Fisher information (Cramer-Rao inequality), worst additive noise lemma, entropy power inequality (EPI), and EEI are interpreted as functional problems and proved within the framework of calculus of variations. Several extensions and applications of the proposed results are briefly mentioned.

Power system generators are interconnected in a distributed network to allow sharing of power. If one of the generators cannot meet the power demand, spare power is diverted from neighbouring generators. However, this approach also allows for propagation of electric disturbances. An oscillation arising from a disturbance at a given generator site will affect the normal operation of neighbouring generators and might cause them to fail. Hours of production time will be lost in the time it takes to restart the power plant. If the disturbance is detected early, appropriate control measures can be applied to ensure system stability. The aim of this study is to improve existing algorithms that estimate the oscillation parameters from acquired generator data to detect potentially dangerous power system disturbances. When disturbances occur in power systems (due to load changes or faults), damped oscillations (or &quotmodes") are created. Modes which are heavily damped die out quickly and pose no threat to system stability. Lightly damped modes, by contrast, die out slowly and are more problematic. Of more concern still are &quotnegatively damped" modes which grow exponentially with time and can ultimately cause the power system to fail. Widespread blackouts are then possible. To avert power system failures it is necessary to monitor the damping of the oscillating modes. This thesis proposes a number of damping estimation algorithms for this task. If the damping is found to be very small or even negative, then additional damping needs to be introduced via appropriate control strategies. This thesis presents a number of new algorithms for estimating the damping of modal oscillations in power systems. The first of these algorithms uses multiple orthogonal sliding windows along with least-squares techniques to estimate the modal damping. This algorithm produces results which are superior to those of earlier sliding window algorithms (that use only one pair of sliding windows to estimate the damping). The second algorithm uses a different modification of the standard sliding window damping estimation algorithm - the algorithm exploits the fact that the Signal to Noise Ratio (SNR) within the Fourier transform of practical power system signals is typically constant across a wide frequency range. Accordingly, damping estimates are obtained at a range of frequencies and then averaged. The third algorithm applied to power system analysis is based on optimal estimation theory. It is computationally efficient and gives optimal accuracy, at least for modes which are well separated in frequency.