Cette thèse porte sur la modélisation du trafic dans les réseaux routiers et comment celle-ci est intégrée dans des modèles d'optimisation. Ces deux sujets ont évolué de manière plutôt disjointe: le trafic est prédit par des modèles mathématiques de plus en plus complexes, mais ce progrès n'a pas été incorporé dans les modèles de design de réseau dans lesquels les usagers de la route jouent un rôle crucial. Le but de cet ouvrage est d'intégrer des modèles d'utilités aléatoires calibrés avec de vraies données dans certains modèles biniveaux d'optimisation et ce, par une décomposition de Benders efficace. Cette décomposition particulière s'avère être généralisable par rapport à une grande classe de problèmes communs dans la litérature et permet d'en résoudre des exemples de grande taille. Le premier article présente une méthodologie générale pour utiliser des données GPS d'une flotte de véhicules afin d'estimer les paramètres d'un modèle de demande dit recursive logit. Les traces GPS sont d'abord associées aux liens d'un réseau à l'aide d'un algorithme tenant compte de plusieurs facteurs. Les chemins formés par ces suites de liens et leurs caractéristiques sont utilisés afin d'estimer les paramètres d'un modèle de choix. Ces paramètres représentent la perception qu'ont les usagers de chacune de ces caractéristiques par rapport au choix de leur chemin. Les données utilisées dans cet article proviennent des véhicules appartenant à plusieurs compagnies de transport opérant principalement dans la région de Montréal. Le deuxième article aborde l'intégration d'un modèle de choix de chemin avec utilités aléatoires dans une nouvelle formulation biniveau pour le problème de capture de flot de trafic. Le modèle proposé permet de représenter différents comportements des usagers par rapport à leur choix de chemin en définissant les utilités d'arcs appropriées. Ces utilités sont stochastiques ce qui contribue d'autant plus à capturer un comportement réaliste des usagers. Le modèle biniveau est rendu linéaire à travers l'ajout d'un terme lagrangien basé sur la dualité forte et ceci mène à une décomposition de Benders particulièrement efficace. Les expériences numériques sont principalement menés sur un réseau représentant la ville de Winnipeg ce qui démontre la possibilité de résoudre des problèmes de taille relativement grande. Le troisième article démontre que l'approche du second article peut s'appliquer à une forme particulière de modèles biniveaux qui comprennent plusieurs problèmes différents. La décomposition est d'abord présentée dans un cadre général, puis dans un contexte où le second niveau du modèle biniveau est un problème de plus courts chemins. Afin d'établir que ce contexte inclut plusieurs applications, deux applications distinctes sont adaptées à la forme requise: le transport de matières dangeureuses et la capture de flot de trafic déterministe. Une troisième application, la conception et l'établissement de prix de réseau simultanés, est aussi présentée de manière similaire à l'Annexe B de cette thèse. / The subject of this thesis is the modeling of traffic in road networks and its integration in optimization models. In the literature, these two topics have to a large extent evolved independently: traffic is predicted more accurately by increasingly complex mathematical models, but this progress has not been incorporated in network design models where road users play a crucial role. The goal of this work is to integrate random utility models calibrated with real data into bilevel optimization models through an efficient Benders decomposition. This particular decomposition generalizes to a wide class of problems commonly found in the literature and can be used to solved large-scale instances. The first article presents a general methodology to use GPS data gathered from a fleet of vehicles to estimate the parameters of a recursive logit demand model. The GPS traces are first matched to the arcs of a network through an algorithm taking into account various factors. The paths resulting from these sequences of arcs, along with their characteristics, are used to estimate parameters of a choice model. The parameters represent users' perception of each of these characteristics in regards to their path choice behaviour. The data used in this article comes from trucks used by a number of transportation companies operating mainly in the Montreal region. The second article addresses the integration of a random utility maximization model in a new bilevel formulation for the general flow capture problem. The proposed model allows for a representation of different user behaviors in regards to their path choice by defining appropriate arc utilities. These arc utilities are stochastic which further contributes in capturing real user behavior. This bilevel model is linearized through the inclusion of a Lagrangian term based on strong duality which paves the way for a particularly efficient Benders decomposition. The numerical experiments are mostly conducted on a network representing the city of Winnipeg which demonstrates the ability to solve problems of a relatively large size. The third article illustrates how the approach used in the second article can be generalized to a particular form of bilevel models which encompasses many different problems. The decomposition is first presented in a general setting and subsequently in a context where the lower level of the bilevel model is a shortest path problem. In order to demonstrate that this form is general, two distinct applications are adapted to fit the required form: hazmat transportation network design and general flow capture. A third application, joint network design and pricing, is also similarly explored in Appendix B of this thesis.

This dissertation focuses on selected issues in regard to the mathematical modeling of electricity markets. In a first step the interrelations of electric power market modeling are highlighted a crossroad between operations research, applied economics, and engineering. In a second step the development of a large-scale continental European economic engineering model named ELMOD is described and the model is applied to the issue of wind integration. It is concluded that enabling the integration of low-carbon technologies appears feasible for wind energy. In a third step algorithmic work is carried out regarding a game theoretic model. Two approaches in order to solve a discretely-constrained mathematical program with equilibrium constraints using disjunctive constraints are presented. The first one reformulates the problem as a mixed-integer linear program and the second one applies the Benders decomposition technique. Selected numerical results are reported.

In today's competitive environment, the importance of continuous production, quality improvement, and fast delivery has forced production and delivery processes to become highly reliable. Keeping equipment in good condition through maintenance activities can ensure a more reliable system. However, maintenance leads to temporary reduction in capacity that could otherwise be utilized for production. Therefore, the coordination of maintenance and production is important to guarantee good system performance. The central thesis of this dissertation is that integrating maintenance and production decisions increases efficiency by ensuring high quality production, effective resource utilization, and on-time deliveries. Firstly, we study the problem of integrated maintenance and production planning where machines are preventively maintained in the context of a periodic review production system with uncertain yield. Our goal is to provide insight into the optimal maintenance policy, increasing the number of finished products. Specifically, we prove the conditions that guarantee the optimal maintenance policy has a threshold type. Secondly, we address the problem of integrated maintenance planning and production scheduling where machines are correctively maintained in the context of a dynamic aircraft repair shop. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter periods. Our results show that the approach that uses logic-based Benders decomposition to solve the static sub-problems, schedules over longer horizon, and quickly adjusts the schedule increases the utilization of aircraft in the long term. Finally, we tackle the problem of integrated maintenance planning and production scheduling where machines are preventively maintained in the context of a multi-machine production system. Depending on the deterioration process of machines, we design decomposed techniques that deal with the stochastic and combinatorial challenges in different, coupled stages. Our results demonstrate that the integrated approaches decrease the total maintenance and lost production cost, maximizing the on-time deliveries. We also prove sufficient conditions that guarantee the monotonicity of the optimal maintenance policy in both machine state and the number of customer orders. Within these three contexts, this dissertation demonstrates that the integrated maintenance and production decision-making increases the process efficiency to produce high quality products in a timely manner.

Le problème d’ordre linéaire (LOP) a reçu beaucoup d’attention dans différents domaines d’application, allant de l’archéologie à l’ordonnancement en passant par l’économie et même de la psychologie mathématique. Ce problème est aussi connu pour être parmi les problèmes NP-difficiles. Nous considérons dans cette thèse une variante de (LOP) sous contrainte de cardinalité. Nous cherchons donc un ordre linéaire d’un sous-ensemble de sommets du graphe de préférences de cardinalité fixée et de poids maximum. Ce problème, appelé (FCLOP) pour ’fixed-cardinality linear ordering problem’, n’a pas été étudié en tant que tel dans la littérature scientifique même si plusieurs applications dans les domaines de macro-économie, de classification dominante ou de transport maritime existent concrètement. On retrouve en fait ses caractéristiques dans les modèles étendus de sous-graphes acycliques. Le problème d’ordre linéaire est déjà connu comme un problème NP-difficile et il a donné lieu à de nombreuses études, tant théoriques sur la structure polyédrale de l’ensemble des solutions réalisables en variables 0-1 que numériques grâce à des techniques de relaxation et de séparation progressive. Cependant on voit qu’il existe de nombreux cas dans la littérature, dans lesquelles des solveurs de Programmation Linéaire en nombres entiers comme CPLEX peuvent en résoudre certaines instances en moins de 10 secondes, mais une fois que la cardinalité est limitée, ces mêmes instances deviennent très difficiles à résoudre. Sur les aspects polyédraux, nous avons étudié le polytope de FCLOP, défini plusieurs classes d’inégalités valides et identifié la dimension ainsi que certaines inégalités qui définissent des facettes pour le polytope de FCLOP. Nous avons introduit un algorithme Relax-and-Cut basé sur ces résultats pour résoudre les instances du problème. Dans cette étude, nous nous sommes également concentrés sur la relaxation Lagrangienne pour résoudre ces cas difficiles. Nous avons étudié différentes stratégies de relaxation et nous avons comparé les bornes duales par rapport à la consolidation obtenue à partir de chaque stratégie de relâcher les contraintes afin de détecter le sous-ensemble des contraintes le plus approprié. Les résultats numériques montrent que nous pouvons trouver des bornes duales de très haute qualité. Nous avons également mis en place une méthode de décomposition Lagrangienne. Dans ce but, nous avons décomposé le modèle de FCLOP en trois sous-problèmes (au lieu de seulement deux) associés aux contraintes de ’tournoi’, de ’graphes sans circuits’ et de ’cardinalité’. Les résultats numériques montrent une amélioration significative de la qualité des bornes duales pour plusieurs cas. Nous avons aussi mis en oeuvre une méthode de plans sécants (cutting plane algorithm) basée sur la relaxation pure des contraintes de circuits. Dans cette méthode, on a relâché une partie des contraintes et on les a ajoutées au modèle au cas où il y a des de/des violations. Les résultats numériques montrent des performances prometteuses quant à la réduction du temps de calcul et à la résolution d’instances difficiles hors d’atteinte des solveurs classiques en PLNE. / Linear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from transportation and scheduling to economics and even archeology and mathematical psychology. It is classified as a NP-hard problem. Assume a complete weighted directed graph on V n , |V n |= n. A permutation of the elements of this finite set of vertices is a linear order. Now let p be a given fixed integer number, 0 ≤ p ≤ n. The p-Fixed Cardinality Linear Ordering Problem (FCLOP) is looking for a subset of vertices containing p nodes and a linear order on the nodes in S. Graphically, there exists exactly one directed arc between every pair of vertices in an LOP feasible solution, which is also a complete cycle-free digraph and the objective is to maximize the sum of the weights of all the arcs in a feasible solution. In the FCLOP, we are looking for a subset S ⊆ V n such that |S|= p and an LOP on these S nodes. Hence the objective is to find the best subset of the nodes and an LOP over these p nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution of the FCLOP is a complete cycle-free digraph on S plus a set of n − p vertices that are not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of the linear ordering problem as well as various exact and heuristic solution methods. The fixed cardinality linear ordering problem is presented for the first time in this PhD study, so as far as we know, there is no other study in the literature that has studied this problem. The linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature that can be solved by CPLEX in less than 10 seconds (when p = n), but once the cardinality number is limited to p (p < n), the instance is not anymore solvable due to the memory issue. We have studied the polytope corresponding to the FCLOP for different cardinality values. We have identified dimension of the polytope, proposed several classes of valid inequalities and showed that among these sets of valid inequalities, some of them are defining facets for the FCLOP polytope for different cardinality values. We have then introduced a Relax-and-Cut algorithm based on these results to solve instances of the FCLOP. To solve the instances of the problem, in the beginning, we have applied the Lagrangian relaxation algorithm. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable subproblem. Numerical results show that some of the relaxation strategies result better dual bound and some other contribute more in reducing the computational time and provide a relatively good dual bound in a shorter time. We have also implemented a Lagrangian decomposition algorithm, decom-6 posing the FCLOP model to three subproblems (instead of only two subproblems). The interest of decomposing the FCLOP model to three subproblems comes mostly from the nature of the three subproblems, which are relatively quite easier to solve compared to the initial FCLOP model. Numerical results show a significant improvement in the quality of dual bounds for several instances. We could also obtain relatively quite better dual bounds in a shorter time comparing to the other relaxation strategies. We have proposed a cutting plane algorithm based on the pure relaxation strategy. In this algorithm, we firstly relax a subset of constraints that due to the problem structure, a very few number of them are active. Then in the course of the branch-and-bound tree we verify if there exist any violated constraint among the relaxed constraints or. Then the characterized violated constraints will be globally added to the model. (...)