Nous abordons dans cette thèse une approche à deux niveaux pour un problème de transport longue distance à charge pleine. Dans cette approche, la problématique étant que le produit chargé dans un entrepôt est immédiatement et intégralement livré au client, laissant le véhicule vide pour passage à l’entrepôt du client suivant. Dans cet environnement, nous étudions la situation de deux transporteurs. Le premier, le transporteur B, possède une clientèle qu’il ne peut satisfaire en totalité, et devra se résoudre à sous-traiter une partie à la concurrence. Le deuxième transporteur, le transporteur A, concurrent mais partenaire privilégié du premier, propose des tarifs pour combler les demandes insatisfaites du transporteur B. Nous sommes donc en présence d’un problème séquentiel non coopératif que nous modélisons par une approche de programmation bi-niveau : au premier niveau le transport A représente le meneur, qui a pour objectif de maximiser son revenu en fixant des tarifs attractifs à B. Au second niveau, le transporteur B représente le suiveur qui a pour objectif de satisfaire toutes ses demandes à coût minimal. Le modèle proposé formulé en programme mathématique à deux niveaux en variables mixtes est NP difficile à résoudre en raison de sa complexité intrinsèque. Deux versions du problème sont étudiées : le modèle simplifié mono-objectif et le modèle complet bi- objectif. Nous développons des méthodes exactes pour résoudre les instances de petites tailles et des heuristiques afin d’obtenir de bonnes solutions en des temps raisonnables pour les instances de plus grande taille. / In this thesis, we discuss a bilevel approach for a full-load long-haul problem. In this type of issue, the product, loaded from a warehouse, is immediately and fully delivered to client, leaving the vehicle empty to visit the warehouse of the next customer. In this environnement, we consider the situation for two carriers. The first one, called carrier B, has a customer base that they cannot totally satisfy and they will be compelled to partial outsourcing to competitors. The second one, called carrier A, competitor but also key partner of the first carrier, offers rates to respond to requests unsatisfied by carrier B. We are dealing here with a non-cooperative sequential problem that we model with a bilevel programming approach : at the first level, carrier A is the leader, whose aim is to maximize their incomes by setting attractive prices to B. In the second level, carrier B is the follower whose aim is to respond to all demands at minimal cost. The proposed model is formulated as mathematical program with two levels and mixed variables. It is NP-hard to solve due to inherent complexity. Two versions of the problem are considered : the mono-objective simplified model and the multi-objective complete model. We develop exact method to solve small-scale instances and heuristics to obtain goog solutions within a reasonable amount of time for larger-scale instances.

Nous considèrerons ici les modèles linéaires de multiflots, en mettant l'accent sur leurs multiples applications, notamment dans les domaines de l'ordonnancement et de la gestion de production. Il est bien connu que ces problèmes, présentés sous forme de programmes linéaires, sont difficiles à résoudre, contrairement à leurs homologues en flot simple. Les méthodes de résolution classiques proposent, déjà dans le cas continu, des solutions approchées. On distingue: les méthodes de décomposition par les prix, par les ressources, ainsi que les techniques de partitionnement. Si l'on rajoute la contrainte d'intégralité sur les flots, ces problèmes deviennent extrêmement difficiles. Nous nous sommes intéressés à un cas particulier des problèmes de multiflots, à savoir: le biflot entier de coût minimum. Nous avons développé une approche de résolution heuristique basée sur un principe de décomposition mixte, opérant itérativement, à la fois par une allocation de ressources et par un ajustement des coûts. L'implémentation de cette approche met en évidence des résultats prometteurs, obtenus sur des problèmes de biflot purs, générés aléatoirement. Nous avons donc envisagé une deuxième application sur des problèmes de biflot plus structurés. Ces problèmes de biflot ont été proposés pour la modélisation du problème de voyageur de commerce. Cette application débouche d'une part, sur l'utilisation d'un algorithme de recherche d'un circuit hamiltonien dans un graphe, et d'autre part, sur le développement de techniques heuristiques pour la construction de tournées intéressantes

Cette thèse s’inscrit dans le cadre de la conception, l’analyse et la mise en œuvre d’algorithmes efficaces et fiables pour la résolution de problèmes d’optimisation non linéaire avec contraintes. Nous présentons trois nouveaux algorithmes fortement primaux-duaux pour résoudre ces problèmes. La première caractéristique de ces algorithmes est que le contrôle des itérés s’effectue dans l’espace primal-dual tout au long du processus de la minimisation, d’où l’appellation “fortement primaux-duaux”. En particulier, la globalisation est effectuée par une méthode de recherche linéaire qui utilise une fonction de mérite primale-duale. La deuxième caractéristique est l’introduction d’une régularisation naturelle du système linéaire qui est résolu à chaque itération pour calculer une direction de descente. Ceci permet à nos algorithmes de bien se comporter pour résoudre les problèmes dégénérés pour lesquels la jacobienne des contraintes n’est pas de plein rang. La troisième caractéristique est que le paramètre de pénalisation est autorisé à augmenter au cours des itérations internes, alors qu’il est généralement maintenu constant. Cela permet de réduire le nombre d’itérations internes. Une étude théorique détaillée incluant l’analyse de convergence globale des itérations internes et externes, ainsi qu’une analyse asymptotique a été présentée pour chaque algorithme. En particulier, nous montrons qu’ils jouissent d’un taux de convergence rapide, superlinéaire ou quadratique. Ces algorithmes sont implémentés dans un nouveau solveur d’optimisation non linéaire qui est appelé SPDOPT. Les bonnes performances de ce solveur ont été montrées en effectuant des comparaisons avec les codes de références IPOPT, ALGENCAN et LANCELOT sur une large collection de problèmes. / This thesis focuses on the design, analysis, and implementation of efficient and reliable algorithms for solving nonlinearly constrained optimization problems. We present three new strongly primal-dual algorithms to solve such problems. The first feature of these algorithms is that the control of the iterates is done in both primal and dual spaces during the whole minimization process, hence the name “strongly primal-dual”. In particular, the globalization is performed by applying a backtracking line search algorithm based on a primal-dual merit function. The second feature is the introduction of a natural regularization of the linear system solved at each iteration to compute a descent direction. This allows our algorithms to perform well when solving degenerate problems for which the Jacobian of constraints is rank deficient. The third feature is that the penalty parameter is allowed to increase along the inner iterations, while it is usually kept constant. This allows to reduce the number of inner iterations. A detailed theoretical study including the global convergence analysis of both inner and outer iterations, as well as an asymptotic convergence analysis is presented for each algorithm. In particular, we prove that these methods have a high rate of convergence : superlinear or quadratic. These algorithms have been implemented in a new solver for nonlinear optimization which is called SPDOPT. The good practical performances of this solver have been demonstrated by comparing it to the reference codes IPOPT, ALGENCAN and LANCELOT on a large collection of test problems.