We consider a single-part, two-echelon supply chain problem for spare parts. The network consists of a single manufacturing plant, a set of service centers (SCs) and a set of customers. Both echelons keep spare parts using the base-stock replenishment policy. The plant behaves as an M/M/1 queueing system and has limited production and storage capacity. Demand faced by each SC follows an independent Poisson process. The problem is to determine optimal location-allocation and optimal base-stock levels at both echelons while satisfying the target service levels and customer preferences of SCs. We develop a mixed integer non-linear programming model and use cutting-plane method to optimize the inventory-location decisions. We present an exact solution procedure for the inventory stocking problem and demonstrate the limitations of using traditional inventory models like METRIC-like and Approximate in case of high utilization rates. We show the effectiveness of our proposed cutting-plane algorithm and provide important managerial insights for spare parts management.

We consider a single-part, two-echelon supply chain problem for spare parts. The network consists of a single manufacturing plant, a set of service centers (SCs) and a set of customers. Both echelons keep spare parts using the base-stock replenishment policy. The plant behaves as an M/M/1 queueing system and has limited production and storage capacity. Demand faced by each SC follows an independent Poisson process. The problem is to determine optimal location-allocation and optimal base-stock levels at both echelons while satisfying the target service levels and customer preferences of SCs. We develop a mixed integer non-linear programming model and use cutting-plane method to optimize the inventory-location decisions. We present an exact solution procedure for the inventory stocking problem and demonstrate the limitations of using traditional inventory models like METRIC-like and Approximate in case of high utilization rates. We show the effectiveness of our proposed cutting-plane algorithm and provide important managerial insights for spare parts management.

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

No description available.

Les travaux présentés dans cette thèse relèvent de l'étude des méthodes de classification linéaires, c'est à dire l'étude de méthodes ayant pour but la catégorisation de données en différents groupes à partir d'un jeu d'exemples, préalablement étiquetés, disponible en amont et appelés ensemble d'apprentissage. En pratique, l'acquisition d'un tel ensemble d'apprentissage peut être difficile et/ou couteux, la catégorisation d'un exemple étant de fait plus ardu que l'obtention de dudit exemple. Cette disparité entre la disponibilité des données et notre capacité à constituer un ensemble d'apprentissage étiqueté a été un des problèmes centraux de l'apprentissage automatique et ce manuscrit s’intéresse à deux solutions usuellement considérées pour contourner ce problème : l'apprentissage en présence de données bruitées et l'apprentissage actif. / The works presented in this thesis fall within the general framework of linear classification, that is the problem of categorizing data into two or more classes based on on a training set of labelled data. In practice though acquiring labeled examples might prove challenging and/or costly as data are inherently easier to obtain than to label. Dealing with label scarceness have been a motivational goal in the machine learning literature and this work discuss two settings related to this problem: learning in the presence of noise and active learning.

Les réseaux optiques sont aujourd’hui l’élément de base des systèmes de communica- tions modernes, en particulier l’Internet. Grâce au multiplexage en longueurs d’onde et au groupage du tra?c, la bande passante disponible sur une ?bre optique est supérieure à plusieurs térabits par seconde. Cependant les équipements opto-électroniques qui permettent d’opérer ces réseaux sont très coûteux car il doivent fonctionner à un débit très important. Le problème de groupage et du routage d’un ensemble de requêtes couplé avec l’affectation des longueurs d’onde (GRWA) est donc un problème stratégique de première importance. L’objectif est de minimiser le coût du réseau, évalué comme le nombre de ports optiques installés aux nœuds. Il peut être modélisé sous la forme d’un problème d’allocation de ressources dans un réseau à capacité multi-niveaux avec multi-?ots non bifurqués. Cette catégorie de problème est connue pour être très dif?cile compte tenu de la faiblesse de la relaxation linéaire des formulations associées. Les travaux réalisés durant cette thèse ont consisté en le développement de méthodes de résolution pour ce problème à partir de multiples techniques de recherche opéra- tionnelle : méta-heuristique de type recherche avec tabous, décomposition de Dantzig- Wolfe, décomposition de Benders, reformulation en variables binaires, méthode de plans coupants, heuristique d’arrondi. Les méthodes résultantes, dont certaines sont hybrides, permettent d’avoir un aperçu des méthodes ef?caces pour ce type de problème. En partic- ulier, les méthodes basées sur la décomposition de Benders, qui donnent lieu à des procédures d’optimisation hiérarchique dans lesquelles l’affectation de longueurs d’onde est placée au dernier niveau, sont les méthodes les plus ef?caces car elles permettent de séparer le routage optique du routage physique. En?n, nous utilisons la meilleure méthode de résolution pour observer l’impact des contraintes de délais sur la qualité des solutions. / Optical networks are the core element of modern communication systems and in particu- lar Internet. With wavelength multiplexing and grooming capability, terabits per second bandwidth can be reached. However, opto-electronic equipment used to operate these networks are very expensive as their bit rate must be very large. The grooming, routing and wavelength assignment (GRWA) problem, which consists in minimizing the net- work cost, evaluated by the number of required optical ports, while guaranteeing that each request is granted, is of great interest. The GRWA problem can be modeled as a multi-layer capacitated network design problem with non-bifurcated multi-?ows. This type of problem is known to be hard to solve as their linear relaxation is weak. The objective of this work was to develop solution methods based on multiple oper- ations research techniques : Tabu search based meta-heuristic, Dantzig-Wolfe decompo- sition, Benders decomposition, 0 1 reformulation, cutting-planes, rounding heuristic. The resulting solution tools, some of them hybrid, give a perspective on the effective solution approaches for this type of problem. From the experiments, it turns out that the methods based on Benders’ decomposition, which lead to hierarchical optimization procedures, are the most ef?cient as they allow to separate the optical routing from the physical routing with the wavelength assignment decisions taken in the lower stage sub- problem. In addition to the approach comparison, we use the most effective method to evaluate the impact of the delay constraints on the solution quality.