Spelling suggestions: "subject:"programmation een nombre entier"" "subject:"programmation enn nombre entier""
1 |
Vehicle Routing Problem for the Collection of Information in Wireless Network / Un problème de tournées de véhicules pour la collecte des informations dans un réseau sans filFlores Luyo, Luis Ernesto 15 February 2018 (has links)
Les progrès dans l'architecture de réseau informatique ajoutent continuellement de nouvelles fonctionnalités aux problèmes de routage des véhicules. Dans cette thèse, le problème de tournée des véhicules avec la collecte de donnée sans fil (WT-VRP) est étudié. Il recherche un itinéraire pour le véhicule chargé de collecter des informations auprès des stations ainsi qu'un planning efficace de collecte d'informations. La nouvelle fonctionnalité ajoutée ici est la possibilité de récupérer des informations via une transmission sans fil, sans visiter physiquement les stations du réseau. Le WT-VRP a des applications dans la surveillance sous-marine et la surveillance environnementale. Nous discutons les critères pour mesurer l'efficacité d'une solution et proposons des formulations de programmation linéaire en nombre entier mixte pour résoudre le problème. Des expériences computationnelles ont été réalisées pour accéder à la complexité numérique du problème et pour comparer les solutions selon les critères proposés. Ensuite, nous avons renforcé certains modèles ainsi que considéré différentes suppositions pour le réseaux sans fils. Finalement, pour être capable de résoudre le problème dans des réseaux de grande échelle, nous avons développés des méthodes heuristiques pour le WT-VRP. / The vehicle routing problem is one of the most studied problems in Operations Research.Different variants have been treated in the past 50 years and with technologicaladvances, new challenges appear. In this thesis, we introduce a new variation of theVRP appearing in wireless networks. The new characteristic added to this well-knowproblem is the possibility of pick-up information via wireless transmissions. In the contextconsidered here, a unique base station is connected with the outside and a vehicleis responsible for collecting information via wireless connection to the vehicle when it islocated in another sufficiently close station. Simultaneous transmissions are permitted.Time of transmission depends on the distance between stations, the amount of informationtransmitted, and other physical factors (e.g obstacles along the way, installedequipment). Information to be sent outside of the network is continuously generatedin each station at a constant rate. The first contribution of this thesis is the introductionof a mixed ILP formulation for a variation in which it is only possible to send all theinformation or nothing during a wireless transmission. For this model three differentstrategies are investigated: maximizing total amount of information extracted an theend of the time horizon; maximizing the average of the information in the vehicle ateach time point; and maximizing the satisfaction of each station at the end of the timehorizon. Each strategy is translated as a different objective function for the mixed ILPformulation. The problem is then reformulated by accepting the option of sending onlypart of the information during a wireless transmission and considering only the firststrategy,(i.e. maximizing the amount of information extracted at the end of the horizontime). For this new version, we present three mixed ILP formulations, each one withadvantages and disadvantages. These mixed ILP models are compared according to theCPU time, amount of information collected, gap of unresolved instances, etc. Becausein real life we need to solve problems with a large number of stations, in this thesis,we also propose heuristics methods for the second version of the problem introduced.We build some heuristics that do not depend on the mixed ILP model (as for exampleGreedy heuristics) and also matheuristcs. In our matheuristics our best model (a vehicleevent model) is used as a base for the development of construction of Heuristics aswell as local search heuristics.
|
2 |
Optimisation d'un portfolio GNL, par l'approche de programmation stochastiqueCen, Zhihao 22 November 2011 (has links) (PDF)
Le travail présenté dans cette thèse est motivé par le problème de gestion de transport de gaz naturel liquéfié (GNL) par cargo proposé par Total. Le gestion de portefeuille doit satisfaire toute les contraintes et faire arbitrage entre les différents marchés. Donc, il traduit mathématiquement un problème d'optimisation stochastique, dynamique et en nombre entiers. Cette thèse se compose de quatre parties: 1 Nous introduisons une méthode numérique pour résoudre le problème de relaxation continue. Nous nous appuyons sur la méthode de quantification pour discrétiser le processus et nous utilisons l'algorithme de programmation dynamique duale stochastique. Nous montrons la convergence de cette méthode numérique et donnons une analyse d'erreur sur la discrétisation par quantification. Des tests numériques sur le marché énergie sont fournis. 2 Nous étudions l'optimisation sous risque inverse en utilisant la "conditional value at risk (CVaR)" dans le critère. Nous montrons que notre algorithme est bien adapté pour cette formulation. De plus, nous utilisons la technique de changement de probabilité dans la programmation stochastique pour améliorer la simulation d'évènements rares. Des tests numériques similaire dans le cas risque neutre sont donnés en guise comparaison. 3 Nous étudions la sensibilité de la valeur de portefeuille par rapport aux divers paramètres dans le modèle de prix sur le marché. Nous proposons une méthode numérique pour calculer les valeurs de sensibilité qui est basée sur le théorème de Danskin. On fournit la convergence de valeur de sensibilité du problème discrétisé vers celui de problème continu. On donne également des tests de comparaison avec d'autres méthodes. 4 Enfin, nous nous concentrons sur le problème stochastique en nombre entier. La méthode de coupe intégralité est utilisée pour le problème en nombre entier. Nous montrons qu'il n'est possible de converger vers la solution entière à cause de non convexité et discontinuité de la fonction valeur. Nous appliquons une méthode heuristique et proposons des améliorations basées sur la méthode de coupe précédent. Des tests numérique sont donnés.
|
Page generated in 0.1137 seconds