Multipath policy routing in packet switched networks

Dissertação apresentada para obtenção do Grau de Mestre em Engenharia Electrotécnica e de Computadores, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia

A clustering approach for vehicle routing problems with hard time windows

Dissertação para obtenção do Grau de Mestre em Logica Computicional

Planning and verification of multipath routing protocols

Conventionally the problem of the best path in a network refers to the shortest path problem. However, for the vast majority of networks present nowadays this solution has some limitations which directly affect their proper functioning, as well as an inefficient use of their potentialities. Problems at the level of large networks where graphs of high complexity are commonly present as well as the appearing of new services and their respective requirements, are intrinsically related to the inability of this solution. In order to overcome the needs present in these networks, a new approach to the problem of the best path must be explored. One solution that has aroused more interest in the scientific community considers the use of multiple paths between two network nodes, where they can all now be considered as the best path between those nodes. Therefore, the routing will be discontinued only by minimizing one metric, where only one path between nodes is chosen, and shall be made by the selection of one of many paths, thereby allowing the use of a greater diversity of the present paths (obviously, if the network consents). The establishment of multi-path routing in a given network has several advantages for its operation. Its use may well improve the distribution of network traffic, improve recovery time to failure, or it can still offer a greater control of the network by its administrator. These factors still have greater relevance when networks have large dimensions, as well as when their constitution is of high complexity, such as the Internet, where multiple networks managed by different entities are interconnected. A large part of the growing need to use multipath protocols is associated to the routing made based on policies. Therefore, paths with different characteristics can be considered with equal level of preference, and thus be part of the solution for the best way problem. To perform multi-path routing using protocols based only on the destination address has some limitations but it is possible. Concepts of graph theory of algebraic structures can be used to describe how the routes are calculated and classified, enabling to model the routing problem. This thesis studies and analyzes multi-path routing protocols from the known literature and derives a new algebraic condition which allows the correct operation of these protocols without any network restriction. It also develops a range of software tools that allows the planning and the respective verification/validation of new protocols models according to the study made.

Locating emergency services with priority rules: The priority queuing covering location problem

One of the assumptions of the Capacitated Facility Location Problem (CFLP) is thatdemand is known and fixed. Most often, this is not the case when managers take somestrategic decisions such as locating facilities and assigning demand points to thosefacilities. In this paper we consider demand as stochastic and we model each of thefacilities as an independent queue. Stochastic models of manufacturing systems anddeterministic location models are put together in order to obtain a formula for thebacklogging probability at a potential facility location.Several solution techniques have been proposed to solve the CFLP. One of the mostrecently proposed heuristics, a Reactive Greedy Adaptive Search Procedure, isimplemented in order to solve the model formulated. We present some computationalexperiments in order to evaluate the heuristics performance and to illustrate the use ofthis new formulation for the CFLP. The paper finishes with a simple simulationexercise.

A multi-objective model for a multi-period distribution management problem

The problems arising in commercial distribution are complex and involve several players and decision levels. One important decision is relatedwith the design of the routes to distribute the products, in an efficient and inexpensive way.This article deals with a complex vehicle routing problem that can beseen as a new extension of the basic vehicle routing problem. The proposed model is a multi-objective combinatorial optimization problemthat considers three objectives and multiple periods, which models in a closer way the real distribution problems. The first objective is costminimization, the second is balancing work levels and the third is amarketing objective. An application of the model on a small example, with5 clients and 3 days, is presented. The results of the model show the complexity of solving multi-objective combinatorial optimization problems and the contradiction between the several distribution management objective.

Strategies for an integrated distribution problem

The problems arising in the logistics of commercial distribution are complexand involve several players and decision levels. One important decision isrelated with the design of the routes to distribute the products, in anefficient and inexpensive way.This article explores three different distribution strategies: the firststrategy corresponds to the classical vehicle routing problem; the second isa master route strategy with daily adaptations and the third is a strategythat takes into account the cross-functional planning through amulti-objective model with two objectives. All strategies are analyzed ina multi-period scenario. A metaheuristic based on the Iteratetd Local Search,is used to solve the models related with each strategy. A computationalexperiment is performed to evaluate the three strategies with respect to thetwo objectives. The cross functional planning strategy leads to solutions thatput in practice the coordination between functional areas and better meetbusiness objectives.

Heuristic solution methods for multi-attribute vehicle routing problems

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

Problèmes de tournées de véhicules avec contraintes de chargement

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.

A modified Primal-Dual Logarithmic-Barrier Method for solving the Optimal Power Flow problem with discrete and continuous control variables

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

A Strategy to Solve the Multistage Transmission Expansion Planning Problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A column generation approach to capacitated p-median problems

The Capacitated p-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from Sao Jose dos Campos' city.