Cette thèse est consacrée à l'étude de deux phases du processus de la livraison e-commerce. La première partie est consacrée aux opérations de préparation des commandes et de leur expédition. Nous proposons un modèle global basé sur la coordination de la préparation et de l'expédition et l'intégration tactique-opérationnelle. La méthode de la résolution proposée repose sur la décomposition du problème en trois phases et il a été démontré qu'elle surpasse significativement le solveur commercial. Ensuite, nous proposons un second modèle basé sur une procédure dynamique à horizon glissant qui prend en compte l'incertitude du nombre des commandes futures. La deuxième partie de la thèse est consacrée à un système de livraison du dernier kilomètre offrant deux familles de services. Nous abordons un problème de tarification des services qui prend en compte le comportement des clients. Les clients sont sensibles au tarif d'un service de livraison, mais aussi à sa qualité. Nous proposons un modèle à deux niveaux où au niveau supérieur, le fournisseur de services contrôle des tarifs. Au niveau inférieur, les clients réagissent en choisissant leur service de livraison selon une fonction d'utilité qui incorpore le tarif du fournisseur et la congestion perçue. Nous modélisons la réaction des clients à l'aide d'un modèle logit imbriqué et calculons l'état de l'équilibre des utilisateurs. Basé sur une recherche locale qui exploite une analyse de sensibilité pour le SUE, un nouvel algorithme heuristique pour le problème de tarification des services à deux niveaux est proposé et comparé à d'autres approches existantes. / All over the world, the growth of e-commerce has led to an increasing importance of the inherent supply chain. This thesis is dedicated to the study of two phases of the e-fulillment process. The first part is dedicated to to the warehouse where picking and shipping operations are conducted at the e-fulfilment process uphill. We propose a global model based on picking and shipping coordination, and tactical-operational integration. The solution method proposed is based on decomposition of the problem in three phases and it was shown to outperform significantly commercial solver. Then we propose, a second model that is based on a dynamic procedure with rolling horizon that takes into account the uncertainty of the future demand. The second part of the thesis is dedicated to last mile delivery system offering two families of services. We address a services pricing problem that takes into account the customers behaviour. Customers are sensitive to the tariff of a delivery service, but also to its quality. We propose a bilevel model where at the upper level, the provider control services tariffs. At the lower level, users react by choosing their delivery service according to a utility function which incorporates the provider tariff and the perceived congestion. We model the customers reaction using a nested logit model and compute the resulting stochastic user equilibrium (SUE). Based on a local search that exploits a sensitivity analysis for the SUE, a new heuristic algorithm for the bilevel services pricing problem is proposed and compared to others existing approaches.

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.

Dans cette thèse nous étudions la problématique d’un fournisseur d’électricité qui souhaite à la fois réguler la demande et créer du revenu dans un environnement potentiellement compétitif (PRMDS). Nous proposons des modèles bi-niveaux pour représenter l’interaction hiérarchique entre le fournisseur d’électricité (le meneur) et ses clients (le suiveur). L’objectif du meneur est de maximiser son revenu en décroissant la valeur de pointe de la demande alors que l’objectif du suiveur est de minimiser la somme des coûts des clients. Nous supposons que les clients résidentiels sont inter-connectés entre eux via un réseau de communication bi-directionnel ce qui permet un pilotage de la demande par rapport aux prix par un agrégateur de réseau intelligent. Dans cette thèse nous avons proposé plusieurs modèles de programmation mathématique à deux niveaux bilinéaire bilinéaire pour le PRMDS. Ces modèles peuvent être reformulés sous forme de problèmes linéaire avec variables mixte (MIP) en utilisant les conditions de KKT. Ces modèles sont résolus de façon exacte sur des instances de taille moyenne via un logiciel commercial. Afin de résoudre des instances de plus grande taille, des heuristiques ont été proposées. Deux d’entre elles ont prouvé leur efficacité en terme de qualité de solution obtenue et de temps de calcul. Finalement nous avons considéré une version robuste du problème de programmation mathématique à deux niveaux. Des propriétés préliminaires ont été prouvées. / This thesis is concerned with revenue optimization of an energy provider. A bilevel programming approach is proposed to model the relationship between the energy provider (leader) and power users (follower). The leader intends to achieve an optimal trade-off between revenue and peak load whereas the follower minimizes total cost of users to achieve system optimality. A smart grid structure that allows two-way communication is assumed to interconnect users and to schedule their demand regarding the prices. Day-ahead real-time prices are read by each customer's smart meter and the response is coordinated. In this thesis, we propose several bilinear bilevel programs that are presented and reformulated as single-level mixed integer problems using the KKT conditions of the follower's problem. These MIPs are solved to optimality for randomly generated instances using a commercial software. Different versions of the models are tested and compared. In order to solve large instances, several heuristics are developed. Two of these methods are shown to be efficient and solve large instances that cannot be solved within a reasonable time interval using exact method. Their outputs are compared to the exact solutions for small instances and their performances are evaluated. Finally, we address the robust bilevel optimization problem, discuss existing approaches, give illustrative examples, and propose avenues for future research.

Nous étudions dans cette thèse un problème de tarification pour le transport longue distance de marchandises à charge pleine. Plus précisément chaque véhicule livre une seule demande à la fois. Dans cet environnement, nous étudions une problématique de tarification et de valorisation de la capacité inutilisée entre 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 en présence d'un processus de décision séquentiel, non coopératif, hiérarchisé que nous modélisons par une approche de programmation bi-niveau : au premier niveau le transport A (le meneur) a pour objectif de maximiser son revenu en fixant des tarifs, et en prenant explicitement en compte la réaction du transporteur B (le suiveur) qui a pour objectif de satisfaire toutes ses demandes à coût minimal. Deux types de modèles ont été proposé : un modèle bi-niveau mono-objectif et un modèle bi-niveau bi-objectif. Plus précisément deux objectifs sont pris simultanément en compte pour le problème de haut niveau : la maximisation du revenu et l'équilibrage de la distance parcourue à vide. Des méthodes exactes ont été proposées, pour résoudre les instances de petites tailles et des heuristiques sont définies pour obtenir de bonnes solutions en des temps raisonnables sur des instances de plus grande taille.

Les conditions de circulation sur un réseau routier subissent souvent de la congestion. Selon ses sources, la congestion routière peut être classée en deux catégories : la congestion récurrente déterminée par les lois de trafic et la congestion non-récurrente due aux incidents, accidents ou autres aléas sur la route. Grâce à l'avancement des technologies, notamment en informatique, communication et techniques de traitement des données, l'exploitant est devenu capable de détecter les perturbations, de mesurer les effets et même d'anticiper l'état du trafic afin de mieux adapter ses actions d'exploitation. L'information dynamique concernant les conditions de trafic permet aux usagers de réduire l'inconfort et d'effectuer leur choix d'itinéraire de manière plus raisonnable. Pour l'exploitant, le service d'information aux usagers peut servir à la gestion du trafic. Nous avons étudié la contribution potentielle de l'information dynamique au profit individuel des usagers et à la performance collective du système en prenant en compte : i) la congestion récurrente et non-récurrente ; ii) des différents comportements de choix d'itinéraire en fonction de l'accessibilité à l'information ; iii) d'autres actions de gestion du trafic menées par l'exploitant. Un modèle théorique avec une application analytique sur un réseau élémentaire de deux routes parallèles, une paire origine-destination et deux classes d'usagers respectivement informée ou non-informée nous a permis de retirer de nombreuses indications : i) la diffusion excessive de l'information avec un contenu " neutre " dégrade à la fois le profit individuel et la performance du système ; ii) l'information dynamique avec certain contenu " coopératif " peut contribuer l'optimisation du système sans causer le problème d'acceptabilité ; iii) l'information dynamique et d'autres mesures de gestion dynamique s'interagissent de manière complémentaire à l'optimisation du trafic

Le management de la chaîne logistique concerne un large éventail d'activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l'incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l'incertitude, l'indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d'incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d'aborder ce problème d'une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l'incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d'incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L'incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision.

Les conditions de circulation sur un réseau routier subissent souvent de la congestion. Selon ses sources, la congestion routière peut être classée en deux catégories : la congestion récurrente déterminée par les lois de trafic et la congestion non-récurrente due aux incidents, accidents ou autres aléas sur la route. Grâce à l'avancement des technologies, notamment en informatique, communication et techniques de traitement des données, l'exploitant est devenu capable de détecter les perturbations, de mesurer les effets et même d'anticiper l'état du trafic afin de mieux adapter ses actions d'exploitation. L'information dynamique concernant les conditions de trafic permet aux usagers de réduire l'inconfort et d'effectuer leur choix d'itinéraire de manière plus raisonnable. Pour l'exploitant, le service d'information aux usagers peut servir à la gestion du trafic. Nous avons étudié la contribution potentielle de l'information dynamique au profit individuel des usagers et à la performance collective du système en prenant en compte : i) la congestion récurrente et non-récurrente ; ii) des différents comportements de choix d'itinéraire en fonction de l'accessibilité à l'information ; iii) d'autres actions de gestion du trafic menées par l'exploitant. Un modèle théorique avec une application analytique sur un réseau élémentaire de deux routes parallèles, une paire origine-destination et deux classes d'usagers respectivement informée ou non-informée nous a permis de retirer de nombreuses indications : i) la diffusion excessive de l'information avec un contenu « neutre » dégrade à la fois le profit individuel et la performance du système ; ii) l'information dynamique avec certain contenu « coopératif » peut contribuer l'optimisation du système sans causer le problème d'acceptabilité ; iii) l'information dynamique et d'autres mesures de gestion dynamique s'interagissent de manière complémentaire à l'optimisation du trafic / Traffic conditions on a road network often suffer from congestion. According to sources, the traffic congestion can be classified into two categories : recurrent congestion determined by the physic laws of traffic and non-recurrent congestion due to incidents, accidents or other hazards on the road. Thanks to the advancement of technologies, including computers, communications and data processing, the traffic operator is now able to detect disturbances, to measure the effects and even to anticipate traffic conditions to better match traffic management activities. Dynamic information on traffic conditions enables users to reduce discomfort and make their route choice decision more reasonable. For the operator, the service user information may be used as a traffic management tool. We investigated the potential contribution of dynamic traffic information for the benefit of individual users and system performance by taking into account : i) recurring congestion and non-recurring ; ii) different route choice behaviours based on accessibility to information service ; iii) other traffic management actions taken by the traffic operator. A theoretical model with an analytical application on a simple two-parallel-road network, an origin-destination pairs and two user classes, respectively-informed or non-informed has given many conclusions : i) an excessive distribution of traffic information with a « neutral » content damages both the individual profit and system performance ; ii) traffic information with some « cooperative » content may help optimize the system performance without causing acceptability problem ; and iii) dynamic information and other traffic management tools interplay in a complementary manner to optimize the traffic

Le système étudié durant cette thèse est un véhicule électrique hybride avec deux sources d’énergies (Pile à combustible et Super-capacité). L’objectif fixé est de minimiser la consommation du carburant tout en satisfaisant la demande instantanée en puissance sous des contraintes de puissance et de capacité et de stockage. Le problème a été modélisé sous la forme d’un problème d’optimisation globale. Nous avons développé de nouvelles méthodes heuristiques pour le résoudre et proposé le calcul d’une borne inférieure de consommation, en apportant de meilleurs résultats que ceux trouvés dans la littérature. En plus, une étude de robustesse a été réalisée afin de minimiser la consommation de pire-cas suite à une perturbation ou du fait d’incertitudes sur les données d’entrée, précisément sur la puissance demandée. Le but de cette étude est de prendre en compte les perturbations dès la construction des solutions afin d’éviter l’infaisabilité des solutions non robustes en situation perturbée. Les heuristiques de résolution du problème robuste modélisé sous la forme d’un problème de Minimax ont fourni des solutions moins sensibles aux perturbations que les solutions classiques. / The system studied in this thesis is a hybrid electrical vehicle with two energy sources (fuel cell system and super-capacitor). The first goal is to minimize the fuel consumption whilst satisfying the requested power for each instant, taking into account constraints on the availability and the state of charge of the storage element. The system was modeled as a global optimization problem. The heuristics developped for obtaining the best power split between the two sources and the lower bound consumption computation proposed provide better results than those found in the literature. The second goal of the thesis is the study of the robustness of the solutions in order to minimize the worst-case consumption when perturbation happens or uncertainty is added to the input data. In this study the uncertainty concerns the power required for traction. The objective is to maintain the feasibility of solutions and limit the worst consumption that can happen due to a demand fluctuation. Dedicated heuristics are proposed for solving the identified robust variant of the problem, modeled as a Minimax problem. The solutions provided are less sensitive to the perturbations than the previous ones.

L’objectif de cette thèse est de développer et étudier des modèles mathématiques d’échanges économiques, basés sur la flexibilité de la demande, entre fournisseurs et consommateurs d’électricité. D’une part, des fournisseurs d’électricité offrent des prix dépendant de l’heure de consommation. D’autre part, des consommateurs adaptent leur usage, minimisant leur facture et le désagrément lié aux changements de consommation induits. La structure de ces problèmes correspond à des problèmes d’optimisation bi-niveau. Trois types de modèles sont étudiés. Tout d’abord, l’interaction entre un fournisseur et un opérateur de smart grid est modélisée par un problème à un seul meneur et un seul suiveur. Pour cette première approche, le niveau de détails du suiveur est particulièrement élevé, et inclut notamment une gestion stochastique de la production distribuée. La meilleure réponse d’un fournisseur dans un modèle à plusieurs meneurs et plusieurs suiveurs fait l’objet de la seconde partie de la thèse. Celle-ci intègre aussi la possibilité d’avoir des agrégateurs comme suiveurs. Deux nouvelles méthodes de résolution reposant sur la sélection d’équilibres de Nash entre suiveurs sont proposées. Enfin, dans une troisième et dernière partie, on se focalise sur la recherche d’équilibres non coopératifs pour ce modèle à plusieurs meneurs et plusieurs suiveurs.Tous les problèmes abordés dans cette thèse le sont non seulement d’un point de vue théorique, mais également d’un point de vue numérique / The objective of this thesis is to develop and study mathematical models of economical exchanges between energy suppliers and consumers, using demand-side management. On one hand, the suppliers offer time-of-use electricity prices. On the other hand, energy consumers decide on their energy demand schedule, minimizing their electricity bill and the inconvenience due to schedule changes. This problem structure gives rise to bilevel optimization problems.Three kinds of models are studied. First, single-leader single-follower problems modeling the interaction between an energy supplier and a smart grid operator. In this first approach, the level of details is very high on the follower’s side, and notably includes a stochastic treatment of distributed generation. Second, a multi-leader multi-follower problem is studied from the point of view of the best response of one of the suppliers. Aggregators are included in the lower level. Two new resolution methods based on a selection of Nash equilibriums at the lower level are proposed. In the third and final part, the focus is on the evaluation of noncooperative equilibriums for this multi-leader multi-follower problem.All the problems have been studied both from a theoretical and numerical point of view.

La programmation bi-niveau désigne une classe de problèmes d'optimisation emboîtés impliquant deux joueurs.Un joueur meneur annonce une décision à un joueur suiveur qui détermine sa réponse parmi l'ensemble des solutions d'un problème d'optimisation dont les données dépendent de la décision du meneur (problème de niveau bas).La décision optimale du meneur est la solution d'un autre problème d'optimisation dont les données dépendent de la réponse du suiveur (problème de niveau haut).Lorsque la réponse du suiveur n'est pas unique, on distingue les problèmes bi-niveaux optimistes et pessimistes,suivant que la réponse du suiveur soit respectivement la meilleure ou la pire possible pour le meneur.Les problèmes bi-niveaux sont souvent utilisés pour modéliser des problèmes de tarification. Dans les applications étudiées ici, le meneur est un vendeur qui fixe un prix, et le suiveur modélise le comportement d'un grand nombre de clients qui déterminent leur consommation en fonction de ce prix. Le problème de niveau bas est donc de grande dimension.Cependant, la plupart des problèmes bi-niveaux sont NP-difficiles, et en pratique, il n'existe pas de méthodes générales pour résoudre efficacement les problèmes bi-niveaux de grande dimension.Nous introduisons ici une nouvelle approche pour aborder la programmation bi-niveau.Nous supposons que le problème de niveau bas est un programme linéaire, en variables continues ou discrètes,dont la fonction de coût est déterminée par la décision du meneur.Ainsi, la réponse du suiveur correspond aux cellules d'un complexe polyédral particulier,associé à une hypersurface tropicale.Cette interprétation est motivée par des applications récentes de la géométrie tropicale à la modélisation du comportement d'agents économiques.Nous utilisons la dualité entre ce complexe polyédral et une subdivision régulière d'un polytope de Newton associé pour introduire une méthode dedécomposition qui résout une série de sous-problèmes associés aux différentes cellules du complexe.En utilisant des résultats portant sur la combinatoire des subdivisions, nous montrons que cette décomposition mène à un algorithme permettant de résoudre une grande classe de problèmes bi-niveaux en temps polynomial en la dimension du problème de niveau bas lorsque la dimension du problème de niveau haut est fixée.Nous identifions ensuite des structures spéciales de problèmes bi-niveaux pour lesquelles la borne de complexité peut être améliorée.C'est en particulier le cas lorsque la fonction coût du meneur ne dépend que de la réponse du suiveur.Ainsi, nous montrons que la version optimiste du problème bi-niveau peut être résolue en temps polynomial, notammentpour des instancesdans lesquelles les données satisfont certaines propriétés de convexité discrète.Nous montrons également que les solutions de tels problèmes sont des limites d'équilibres compétitifs.Dans la seconde partie de la thèse, nous appliquons cette approche à un problème d'incitation tarifaire dans les réseaux mobiles de télécommunication.Les opérateurs de données mobiles souhaitent utiliser des schémas de tarification pour encourager les différents utilisateurs à décaler leur consommation de données mobiles dans le temps, et par conséquent dans l'espace (à cause de leur mobilité), afin de limiter les pics de congestion.Nous modélisons cela par un problème bi-niveau de grande taille.Nous montrons qu'un cas simplifié peut être résolu en temps polynomial en utilisant la décomposition précédente,ainsi que des résultats de convexité discrète et de théorie des graphes.Nous utilisons ces idées pour développer une heuristique s'appliquant au cas général.Nous implémentons et validons cette méthode sur des données réelles fournies par Orange. / Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.