[pt] O processo decisório na logística humanitária compreende diversos tipos de prioridades que por vezes estão relacionados com situações de vida ou morte. Neste grau de importância, os objetivos a serem perseguidos pelos tomadores de decisão na situação de um desastre e as restrições do problema devem ser estabelecidos para se alinhar com os anseios das vítimas e com as limitações existentes. Este estudo visa analisar de que maneiras as prioridades conflitantes num problema repleto de incertezas como em um desastre podem impactar o resultado do atendimento humanitário no que tange à sua eficiência, efetividade e equidade (3E). A dissertação apresenta o papel de alguns objetivos e restrições conflitantes (trade-offs) na tomada de decisão durante a fase de preparação para um desastre. Para tal, modelos de otimização estocástica são propostos utilizando-se dos conceitos de desempenho via 3E e sensibilidade ao risco, através da medida CVaR. Os resultados sugerem que a inclusão da aversão ao risco pode levar a um sistema mais efetivo em média. Outro ponto importante é que o modelo de minimização de custos incluindo o custo da falta forneceu uma resposta com melhor desempenho do que na maximização de equidade ou de cobertura de forma independente. Além disso, a restrição de orçamento (eficiência) quando mal dimensionada pode tornar um problema de maximização de cobertura (efetividade) desnecessariamente ineficiente. Conclui-se que a priorização da maximização conjunta da eficiência e da efetividade com restrição de inequidade e sensibilidade ao risco torna o modelo mais preciso quanto ao atendimento das vítimas do desastre. / [en] The decision-making process in humanitarian logistics comprises several types of priorities that are sometimes related to life or death situations. In this degree of importance, the objectives to be pursued by decision-makers in the event of a disaster as well as the constraints of the problem must be established to align both with the needs of the victims and with the existing limitations. This study aims at analyzing how conflicting priorities in an uncertainty-filled problem such as a disaster can impact the performance of the solution with respect to its efficiency, effectiveness and equity (3E). The dissertation presents the role of some decision-making trade-offs within disaster preparedness phase. For this, stochastic optimization models are proposed using the concept of 3E-performance and risk sensitivity, through the measure CVaR. Results indicate that the inclusion of risk aversion may lead to a more effective system on average. Another important point is that the cost minimization model including the shortage penalty provided a better performing response than in equity or coverage maximization independently. In addition, budget constraint (efficiency) when poorly dimensioned can make a problem of maximizing coverage (effectiveness) unnecessarily inefficient. It is concluded that the prioritization of the joint maximization of efficiency and effectiveness with restriction of inequity and risk sensitivity makes a model more precise as regards the care of the disaster victims.

Avec plus de 345 millions de tonnes de déchets produits en France en 2012, la performance de la chaîne logistique de collecte, transport et traitement de ces produits et matériaux est devenue un enjeu économique et écologique majeur dans notre société. Dans cette thèse, nous nous intéressons à l’optimisation de la chaîne de collecte et transport des déchets sur le plan tactique et opérationnel. Nous modélisons dans un premier temps un nouveau problème tactique d’optimisation de flux de déchets avec sites de transfert et de traitement sur un horizon mono-périodique puis multi-périodique, afin d’exploiter un réseau logistique existant de manière optimale. Nous résolvons différentes variantes de ce problème linéaire mixte à l’aide d’un solveur. Nous étudions dans un second temps la planification opérationnelle de la collecte de conteneurs d’apport volontaire et des tournées de véhicules associées en résolvant un problème riche de tournées avec gestion de stocks et plateformes de vidage intermédiaires. Nous proposons un modèle d’optimisation de ce nouveau problème et le résolvons par un algorithme à voisinages larges (ALNS) dans un cadre déterministe puis stochastique, dans lequel le remplissage des conteneurs est aléatoire et plus conforme à la réalité. Nous obtenons des résultats compétitifs en évaluant notre approche sur des instances de la littérature proches de notre problème riche. En réalisant un logiciel d’optimisation à destination d’une entreprise de collecte et transport de déchets, nous améliorons également de manière significative les tournées de véhicules en application réelle. / With more than 345 million tons produced in France in2012, waste supply chain management is an important economical and ecological issue for our society. In this thesis, we focus on optimizing waste supply chain on both the tactical and operational decision levels. In order to optimize an existing waste logistic network in medium term, we first solve a multimodal flow problem where products are transferred and transformed in sites of various size, in a mono-periodic then multi-periodic horizon. At an operational level, we study the planning and routing of vehicles used for voluntary drop-off waste container collection by solving a complex inventory routing problem with intermediate facilities. We use a large neighborhoods search metaheuristic to solve both the deterministic and stochastic approaches, where waste supply quantity is also subject to uncertainty. We obtain competitive results on instances coming from the literature on classical routing problems close to our rich case. We also develop an optimization software used by a French waste management company and significantly improve routes in a real application.

Cette thèse étudie l’évolution des marchés du gaz naturel en Europe jusqu’en 2035 en utilisant les outils de la modélisation. Le modèle proposé, intitulé GaMMES, repose sur une description oligopolistique des marchés et ses principaux avantages sont les suivants : un niveau de détail important de la structure économique de la chaîne gazière et une prise en compte endogène des contrats de long-terme en amont ainsi que de la substitution avec les produits pétroliers et le charbon, au niveau de la demande. Dans un premier temps, nous étudions la question de la sécurité d’approvisionnement en gaz en Europe et les conditions favorables à la régulation des marchés vulnérables au risque de rupture d’approvisionnement, notamment de la part de la Russie. Trois études de cas sont proposées selon le degré de dépendance et la nature de régulation en place : le marché allemand des années 1980 et les marchés actuels de la Bulgarie et de l’Espagne. Nous étudions en particulier l’évolution des caractéristiques des marchés en fonction du risque de rupture et le type de régulation à mettre en place afin d’assurer l’optimalité du bien-être social. Ensuite, nous proposons un modèle de type systèmes dynamiques afin de prendre en compte la substitution énergétique entre le charbon, le pétrole et le gaz naturel. Notre approche permet d’estimer une nouvelle forme fonctionnelle de la fonction de demande pour le gaz naturel, qui englobe à la fois la substitution énergétique et les inerties de consommation dues aux investissements des usagers finaux. Dans un troisième temps, nous utilisons cette fonction de demande dans un modèle d’équilibre partiel des marchés du gaz naturel en Europe. Le modèle GaMMES, écrit sous forme de problème de complémentarité, représente les principaux acteurs de l’industrie du gaz naturel en considérant leurs interactions stratégiques et les pouvoirs de marchés. Il a été appliqué au marché du gaz naturel en Europe du nord-est afin d’étudier l’évolution, jusqu’en 2035, de la consommation, des prix spot, des prix et volumes long-terme, de la production et de la dépendance par rapport aux imports étrangers. Finalement, nous proposons une extension stochastique du modèle GaMMES afin d’analyser l’impact de la forte fluctuation du prix du Brent sur les marchés gaziers. Une étude économétrique a été menée afin de calculer la loi de probabilité du prix du pétrole, lorsqu’il est modélisé en tant que variable aléatoire, dans le but de construire et pondérer l’arbre des scénarii. Les résultats permettent de comprendre comment l’aléa modifie les comportements stratégiques des acteurs, notamment au niveau des contrats de long-terme. Enfin, la valeur de la solution stochastique est calculée afin de quantifier l’importance de la prise en compte des fluctuations du prix du pétrole pour chaque acteur de la chaîne. / This thesis studies the evolution of the natural gas markets in Europe, until 2035, using optimization theory tools. The model we develop, named GaMMES, is based on an oligopolistic description of the markets. Its main advantages are the following: we consider an important level of detail in the economic structure of the gas chain and we endogenously take into account long-term contracts in the upstream as well as energy substitution between gas, oil, and coal in the demand. In the first part of this thesis, we study the issue of security of supply in Europe and the conditions under which it is necessary to regulate the gas markets that are strongly dependent on foreign imports. Three case studies are then presented, regarding the level of dependence and the markets' specificities: the German gas trade of the 1980s and the current Spanish and Bulgarian markets. We study in particular the evolution of the markets' outcome as a function of the supply disruption probability and the kind of regulation to implement in order to maximize the social welfare. In the second part, we develop a system dynamics model in order to capture fuel substitution between oil, coal, and natural gas. Our approach allows one to calculate a new functional form of the demand function for natural gas that contains energy substitution and consumption inertia effects due to end-users' investments. In the third part, we take advantage of our demand function and use it in a partial equilibrium model of natural gas markets in Europe. The GaMMES model, when written as a complementarity problem, describes the principal gas chain actors as well as their strategic interactions and market power. It was applied to the northwestern European gas trade to analyze the evolution of consumption, spot and long-term contract prices and volumes, production, and natural gas dependence, until 2035. In the last part, we present a stochastic extension of the GaMMES model in order to study the impact of the strong Brent price fluctuation on the gas markets. An econometric analysis allowed us to calculate the probability law of the oil price, when taken as a random variable, in order to construct the scenario tree and estimate its weights. Our results show how uncertainty changes the strategic behavior, in particular for the long-term contracting activity. Finally, the value of the stochastic solution is calculated to quantify the importance of taking into account randomness in the optimization programs of the gas chain actors.

Title: Multivariate stochastic dominance and its application in portfolio optimization Problems Author: Barbora Petrová Department: Department of Probability and Mathematical Statistics Supervisor: doc. RNDr. Ing. Miloš Kopa, Ph.D., Department of Probability and Mathematical Statistics Abstract: This thesis discusses the concept of multivariate stochastic dominance, which serves as a tool for ordering random vectors, and its possible usage in dynamic portfolio optimization problems. We strictly focus on different types of the first-order multivariate stochastic dominance for which we describe their generators in the sense of von Neumann-Morgenstern utility functions. The first one, called strong multivariate stochastic dominance, is generated by all nondecreasing multivariate utility functions. The second one, called weak multivariate stochastic dominance, is defined by relation between survival functions, and the last one, called the first-order linear multivariate stochastic dominance, applies the first-order univariate stochastic dominance notion to linear combinations of marginals. We focus on the main characteristics of these types of stochastic dominance, their relationships as well as their relation to the cumulative and marginal distribution functions of considered random vectors. Formulated...

La distillation est une opération unitaire de séparation qui est largement utilisée. Toutefois, lorsque les volatilités des corps à séparer sont proches, le besoin en énergie de la colonne augmente, et l’efficacité énergétique du procédé de séparation diminue. Ainsi, la faiblesse de la distillation est son efficacité énergétique (au maximum 10 %). La réduction de la consommation énergétique des colonnes à distiller est donc un enjeu majeur dans le contexte énergétique actuel. Une des voies prometteuses est les colonnes à distiller dites HIDiC (Heat Integrated Distillation Column). Dans ce type de configuration, la colonne est scindée en deux colonnes : une colonne d’appauvrissement et une colonne d’enrichissement. La colonne d’appauvrissement opère à un niveau de pression plus faible que la colonne d’enrichissement. Un compresseur ainsi qu’une vanne de détente sont installés pour ajuster les niveaux de pression respectifs dans les deux parties. La différence de pression ainsi établie permet d’imposer une différence de températures qui offre la possibilité de transférer de l’énergie entre les deux colonnes par l’intermédiaire d’une technologie de transfert de chaleur. Dans un premier temps, l’objet de cette étude est de valider une nouvelle technologie de transfert thermique pour les colonnes concentriques HIDiC. Cette technologie innovante, Mousse métallique à cellules ouvertes, est caractérisée et validée en comparant avec un garnissage classique. Pour cela, un pilote expérimental de colonne concentrique contenant le garnissage structuré a été mis en oeuvre au laboratoire. Les résultats des mousses métalliques ont montré une performance thermique plus importante que le garnissage classique avec un gain moyen de 102 %. La conductance thermique des mousses métallique à cellules ouvertes obtenue expérimentalement est de 1285 W.K-1. Ces résultats confirment l’intérêt de l’utilisation du garnissage innovant dans les colonnes de distillation HIDiC en tant que technologie de transfert de chaleur. Dans un deuxième temps, un outil de simulation des colonnes HIDiC est développé dans le logiciel commercial ProSim Plus™®. Par rapport aux colonnes de distillation conventionnelles, les colonnes HIDiC possèdent des paramètres spécifiques tels que le rapport de pression et le profil d’échange de chaleur entre les deux sections de la colonne. Une procédure d’optimisation est élaborée afin d’obtenir une colonne HIDiC avec un coût total annuel « TAC » minimal et une distribution énergétique optimale. La méthode stochastique est adoptée avec un algorithme génétique « AG » ou l’initialisation des variables d’action n’est pas nécessaire. Deux études de cas sont effectuées. L’une est un système largement étudié dans la littérature, le mélange (Benzène/Toluène). La procédure de conception et d’optimisation est évaluée. Une réduction du TAC de 7,4 % et 13,9 % est obtenue par rapport aux précédents travaux de la littérature. L’autre étude de cas est un mélange binaire (Cyclohexane/n-Heptane). Les résultats de la simulation concernant les quantités d’énergie échangées de la colonne d’enrichissement vers la colonne d’appauvrissement sont validés en vérifiant la faisabilité du transfert thermique par la conductance thermique de la technologie innovante obtenue expérimentalement UA (W.K-1). / Distillation is the most applied separation technology. Its major drawback is the low thermodynamic efficiency (typically around 10 %). In response to environmental issues that concern energy consumption of distillation column, HIDiC (heat integrated distillation column) which combines advantages of vapor recompression and diabatic operation is expected to have a large impact on energy saving. The mixtures with close boiling point are confirmed to be the best candidates for HIDiC. In fact, in this configuration the rectifying section and the stripping section are separated. Heat is transferred inside the distillation column from the rectifying to the stripping section, because the operating pressure (and thus the temperature) of the rectifying section is increased by means of the compressor. First, a novel technology of heat and mass transfer between rectifying column and stripping column is characterized and validated on an experimental pilot. A concentric HIDiC which contains metal foam packing is designed. Compared to the Raschig Super-Ring results, the heat transfer in this structured packing is more efficient, with a gain up to 102 %. The obtained thermal conductance UA (W.K-1) of the innovative column packing is 1285 W.K-1. This confirms the purpose of open cell metal foams use in HIDiC as a heat transfer technology. Secondly, the aim of this study is to optimize the HIDiC sensitive parameters so as to minimize the Total Annual Cost (TAC). For this, a HIDiC simulation model is developed by using commercial software ProSim Plus™®. GA (Genetic Algorithm) is used to find the optimal HIDiC configuration where variables are optimized without initialization. Binary (Benzene/Toluene) separation case is examined for the evaluation of the proposed method. As a result, 7.4 % and 13.9 % TAC reductions are realized in comparison with the reported solutions in previous works. Binary (Cyclohexane/n-Heptane) is studied to evaluate the physical feasibility of heat transfer between rectifying and stripping column by the experimental thermal conductance (UA experimental [W.K-1]) of the innovative column packing.

Le travail présenté dans ce mémoire de thèse concerne la gestion de la consommation et de la production d'énergie électrique dans les bâtiments. Le problème de gestion d'énergie est modélisé sous forme de programme linéaire mixte. Le travail présenté dans ce mémoire propose des outils qui permettent de prendre en compte les incertitudes dans l'optimisation des flux d'énergie dans l'habitat. Dans un premier temps les incertitudes à prendre en compte sont étudiées. Nous distinguons 2 types d'incertitudes : les incertitudes paramétriques qui concernent le caractère imprécis des coefficients du modèle (prévisions météorologiques, paramètres des modèles, demande prévisionnelle d'énergie…) et les incertitudes d'occurrence qui sont liées aux actions directes de l'usager sur sa consommation d'énergie. Une approche d'optimisation robuste s'appuyant sur une formulation présentée par Bertsimas et Sim pour la programmation linéaire robuste est proposée pour prendre en compte les incertitudes paramétriques. Une procédure d'optimisation en deux étapes, basée sur la programmation stochastique, est proposée pour anticiper les possibilités de démarrage des services pilotés par l'usager. Cette procédure apporte une réponse aux incertitudes d'occurrence en permettant de prendre en compte les consommations d'énergie qui ne sont pas pilotées par le système d'optimisation. Différents exemples d'appartements sont utilisés pour illustrer la validité des méthodes proposées. Différents scénarios de tarification de l'énergie sont également étudiés. / This PhD dissertation concerns the power management in buildings. The problem of power management is modeled as a mixed linear program. The work presented in this thesis aims to take into account the uncertainties in the optimization of energy flow in the buildings. The uncertainties are analyzed and two types of uncertainty are identified: parametric uncertainties concerning the vagueness of the parameters (weather forecasts, energy demand forecast ...) and the occurrence uncertainties that are related to uncontrollable actions of the user. A robust optimization approach based on a formulation presented by Bertsimas and Sim for robust linear programming is proposed to take into account the parametric uncertainties. An optimization procedure in two stages, based on stochastic programming, is proposed to answer the occurrence uncertainties. This procedure allows to take into account the energy consumption that is not driven by the management system. The proposed methods have been illustrated on various examples of dwellings. Different energy pricing are addressed.

Cette thèse propose une nouvelle méthode pour modéliser les fonctions non linéaires de modulations d’amplitude et de fréquence de signaux multicomposantes non stationnaires de durée longue. La méthode repose sur une décomposition du signal en segments courts pour une modélisation locale sur les segments. Pour initialiser la modélisation, nous avons conçu une première étape qui peut être considérée comme un estimateur indépendant et non paramétrique des fonctions de modulations. L’originalité de l’approche réside dans la définition d’une matrice de convergence totale intégrant simultanément les valeurs d’amplitude et de fréquence et utilisé pour l’association d’un pic à une composante selon un critère d’acceptation stochastique. Suite à cette initialisation, la méthode estime les fonctions de modulations par l'enchaînement des étapes de segmentation, modélisation et fusion. Les fonctions de modulations estimées localement par maximum de vraisemblance sont connectées dans l'étape de fusion, qui supprime les discontinuités, et produit l’estimation globale sur la durée totale du signal. Les étapes sont conçues afin de pouvoir modéliser des signaux multicomposantes avec des morts et naissances, ce qui en fait une de ses originalités par rapport aux techniques existantes. Les résultats sur des signaux réels et simulés ont illustré les bonnes performances et l’adaptabilité de la méthode proposée. / In this thesis, a novel method is proposed for modeling the non-linear amplitude and frequency modulations of non-stationary multi-component signals of long duration. The method relies on the decomposition of the signal into short time segments to carry out local modelings on these segments. In order to initialize the modeling, a first step is designed which can be considered as an independent estimator of the modulations over the entire duration of the signal. The originality of this approach lies in the definition of the total divergence matrix integrating simultaneously the amplitude and frequency values, which are employed for the association of a peak to a component according to a stochastic acceptation criteria. Following the initialization, the proposed method estimates the modulations by the step sequence of segmentation, modeling and fusion. The locally obtained modulation functions estimated by maximum likelihood are finally connected in the fusion step which suppresses their discontinuity and yields the global estimation over the entire signal duration. All these steps are defined in order to be able to model multicomponent signals with births and deaths, making one of its original features compared to existing techniques. The results on real and simulated signals have shown the good performance and adaptability of the proposed method.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Com o aumento do número de desastres e consequente incremento no número de pessoas vitimadas, a preparação para esses eventos é uma necessidade das sociedades modernas. Neste sentido, o planejamento das operações logísticas para atendimento as situações de emergências é uma atividade recente e pouco explorada na produção acadêmica. O objetivo deste trabalho é estabelecer uma metodologia para definir locais para o pré-posicionamento de materiais utilizados no socorro a populações afetadas por desastres através de um modelo de otimização estocástica de dois estágios e análise de decisão multicritério e que considerem parâmetros quantitativos e qualitativos. Com base nos custos de transporte e do não atendimento a demanda, e utilizando informações como mapeamentos de riscos; custos de transporte; histórico de ocorrências de desastres; cobertura geográfica; compras de materiais; capacidades de depósitos e de transporte, um modelo estocástico de programação linear minimiza os custos operacionais para abastecimento às vítimas. Uma análise detalhada sobre como atribuir penalidades para demanda não atendida também é apresentada. Devido à incerteza quanto a severidade de um desastre e a influência da mídia nas fases pós-desastres estes parâmetros são representados na forma de cenários. O resultado do modelo estocástico mostra a quantidade de locais e quais localidades minimizam o custo operacional. Após a obtenção desse resultado, uma nova etapa é utilizada para decisão de escolha do local, com a aplicação de modelo de decisão multicritério que considere, além dos valores obtidos pela modelagem, critérios subjetivos característicos a operações humanitárias. Os resultados finais mostram que modelos estocásticos promovem resultados mais confiáveis que os determinísticos, especialmente, em situações nas quais materiais disponíveis não podem atender toda a demanda e que a consideração de critérios qualitativos e quantitativos proporciona uma decisão mais robusta em operações humanitárias. / The increase in disasters and the consequent increase in the number of victims make it highly necessary to prepare for these events in modern societies. Logistics operations planning to meet emergencies is a recent activity and little explored in academic production. Our aim is to establish a method to locate pre-positioned materials used in disaster relief through a two-stage stochastic optimization model and a multi-criteria decision analysis that consider quantitative and qualitative parameters. Based on transportation and unattended demand costs, and using information such as risk mapping, transportation costs, historical occurrences of disasters, coverage, materials purchase, warehouses and transport capacities, a stochastic linear programming model minimizes the operating costs to supply the victims. A detailed analysis on how to assign penalties for unmet demand is also presented. Due to the uncertainty of the disasters severity and the influence of the media in phases after disasters, these parameters are represented as scenarios. The result of the stochastic model shows the quantity and the locations that minimize the operational cost. After this result, a new phase is applied for site selection, with the application of multi-criteria decision analysis that consider the values provided by the model and subjective criteria characteristic of humanitarian operations. The final results show that stochastic models promote more reliable results than deterministic ones, especially in situations in which the materials available cannot meet all the demand and that the consideration of qualitative and quantitative criteria provides better decisions in humanitarian operations.

In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.<p><p>Optimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.<p><p>In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics: <p>(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;<p>(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;<p>(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances. <p><p>We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.<p>The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.<p><p>Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished