Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

Vérification temporelle des systèmes cycliques et acycliques basée sur l’analyse des contraintes

Nous présentons une nouvelle approche pour formuler et calculer le temps de séparation des événements utilisé dans l’analyse et la vérification de différents systèmes cycliques et acycliques sous des contraintes linéaires-min-max avec des composants ayant des délais finis et infinis. Notre approche consiste à formuler le problème sous la forme d’un programme entier mixte, puis à utiliser le solveur Cplex pour avoir les temps de séparation entre les événements. Afin de démontrer l’utilité en pratique de notre approche, nous l’avons utilisée pour la vérification et l’analyse d’une puce asynchrone d’Intel de calcul d’équations différentielles. Comparée aux travaux précédents, notre approche est basée sur une formulation exacte et elle permet non seulement de calculer le maximum de séparation, mais aussi de trouver un ordonnancement cyclique et de calculer les temps de séparation correspondant aux différentes périodes possibles de cet ordonnancement.

Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Optimization-Based Robotic Manipulation for Safe Interaction with Human Operators

This thesis investigates a method for human-robot interaction (HRI) in order to uphold productivity of industrial robots like minimization of the shortest operation time, while ensuring human safety like collision avoidance. For solving such problems an online motion planning approach for robotic manipulators with HRI has been proposed. The approach is based on model predictive control (MPC) with embedded mixed integer programming. The planning strategies of the robotic manipulators mainly considered in the thesis are directly performed in the workspace for easy obstacle representation. The non-convex optimization problem is approximated by a mixed-integer program (MIP). It is further effectively reformulated such that the number of binary variables and the number of feasible integer solutions are drastically decreased. Safety-relevant regions, which are potentially occupied by the human operators, can be generated online by a proposed method based on hidden Markov models. In contrast to previous approaches, which derive predictions based on probability density functions in the form of single points, such as most likely or expected human positions, the proposed method computes safety-relevant subsets of the workspace as a region which is possibly occupied by the human at future instances of time. The method is further enhanced by combining reachability analysis to increase the prediction accuracy. These safety-relevant regions can subsequently serve as safety constraints when the motion is planned by optimization. This way one arrives at motion plans that are safe, i.e. plans that avoid collision with a probability not less than a predefined threshold. The developed methods have been successfully applied to a developed demonstrator, where an industrial robot works in the same space as a human operator. The task of the industrial robot is to drive its end-effector according to a nominal sequence of grippingmotion-releasing operations while no collision with a human arm occurs.

The role of sky conditions on gross primary production in a mixed deciduous forest

The role of different sky conditions on diffuse PAR fraction (ϕ), air temperature (Ta), vapor pressure deficit (vpd) and GPP in a deciduous forest is investigated using eddy covariance observations of CO2 fluxes and radiometer and ceilometer observations of sky and PAR conditions on hourly and growing season timescales. Maximum GPP response occurred under moderate to high PAR and ϕ and low vpd. Light response models using a rectangular hyperbola showed a positive linear relation between ϕ and effective quantum efficiency (α = 0.023ϕ + 0.012, r2 = 0.994). Since PAR and ϕ are negatively correlated, there is a tradeoff between the greater use efficiency of diffuse light and lower vpd and the associated decrease in total PAR available for photosynthesis. To a lesser extent, light response was also modified by vpd and Ta. The net effect of these and their relation with sky conditions helped enhance light response under sky conditions that produced higher ϕ. Six sky conditions were classified from cloud frequency and ϕ data: optically thick clouds, optically thin clouds, mixed sky (partial clouds within hour), high, medium and low optical aerosol. The frequency and light responses of each sky condition for the growing season were used to predict the role of changing sky conditions on annual GPP. The net effect of increasing frequency of thick clouds is to decrease GPP, changing low aerosol conditions has negligible effect. Increases in the other sky conditions all lead to gains in GPP. Sky conditions that enhance intermediate levels of ϕ, such as thin or scattered clouds or higher aerosol concentrations from volcanic eruptions or anthropogenic emissions, will have a positive outcome on annual GPP, while an increase in cloud cover will have a negative impact. Due to the ϕ/PAR tradeoff and since GPP response to changes in individual sky conditions differ in sign and magnitude, the net response of ecosystem GPP to future sky conditions is non-linear and tends toward moderation of change.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (I the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry`s own practice. (c) 2006 Elsevier Ltd. All rights reserved.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Programação estocástica para fundos de pensão

Nesta dissertação discutiremos modelos e métodos de soluções de programação estocástica para resolver problemas de ALM em fundos de pensão. Apresentaremos o modelo de (Drijver et al.), baseado na programação estocástica multiestágios inteira-mista. Um estudo de caso para um problema de ALM será apresentado usando simulação de cenários.

A Bilevel Approach to Transmission Expansion Planning Within a Market Environment

We present a bilevel model for transmission expansion planning within a market environment, where producers and consumers trade freely electric energy through a pool. The target of the transmission planner, modeled through the upper-level problem, is to minimize network investment cost while facilitating energy trading. This upper-level problem is constrained by a collection of lower-level market clearing problems representing pool trading, and whose individual objective functions correspond to social welfare. Using the duality theory the proposed bilevel model is recast as a mixed-integer linear programming problem, which is solvable using branch-and-cut solvers. Detailed results from an illustrative example and a case study are presented and discussed. Finally, some relevant conclusions are drawn.

Uma abordagem fuzzy para a avaliação técnico-econômica de redes de acesso

O surgimento de novas tecnologias e serviços vem impondo mudanças substanciais ao tradicional sistema de telecomunicações. Múltiplas possibilidades de evolução do sistema fazem da etapa de planejamento um procedimento não só desejável como necessário, principalmente num ambiente de competitividade. A utilização de metodologias abrangentes e flexíveis que possam auxiliar no processo de decisão, fundadas em modelos de otimização, parece um caminho inevitável. Este artigo propõe um modelo de programação linear inteiro misto para ajudar no planejamento estratégico de sistemas de telecomunicações, e em particular da rede de acesso. Os principais componentes de custo e receita são identificados e o modelo é desenvolvido para determinar a configuração da rede (serviços, tecnologias, etc) que maximize a receita esperada pelo operador do sistema. O conceito de números fuzzy é adotado para avaliar o risco técnico-econômico em situações de imprecisão nos dados de demanda. Resultados de experimentos computacionais são apresentados e discutidos.

Um problema de programação da produção numa fundição automatizada

Este trabalho apresenta a modelagem de um problema particular de Programação da Produção numa Fundição Automatizada e sua resolução por um algoritmo de busca heurística, que explora a estrutura do problema.

Transmission-expansion planning using the DC model and nonlinear-programming technique

The paper presents a constructive heuristic algorithm (CHA) for solving directly the long-term transmission-network-expansion-planning (LTTNEP) problem using the DC model. The LTTNEP is a very complex mixed-integer nonlinear-programming problem and presents a combinatorial growth in the search space. The CHA is used to find a solution for the LTTNEP problem of good quality. A sensitivity index is used in each step of the CHA to add circuits to the system. This sensitivity index is obtained by solving the relaxed problem of LTTNEP, i.e. considering the number of circuits to be added as a continuous variable. The relaxed problem is a large and complex nonlinear-programming problem and was solved through the interior-point method (IPM). Tests were performed using Garver's system, the modified IEEE 24-Bus system and the Southern Brazilian reduced system. The results presented show the good performance of IPM inside the CHA.

An implementation of modified scatter search algorithm to transmission expansion planning

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)