Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif. / In the literature of optimization problems under uncertainty a common approach of dealing with two- and multi-stage problems is to use scenario analysis. To do so, the uncertainty of some data in the problem is modeled by stage specific random vectors with finite supports. Each realization is called a scenario. By using scenarios, it is possible to study smaller versions (subproblems) of the underlying problem. As a scenario decomposition technique, the progressive hedging algorithm is one of the most popular methods in multi-stage stochastic programming problems. In spite of full decomposition over scenarios, progressive hedging efficiency is greatly sensitive to some practical aspects, such as the choice of the penalty parameter and handling the quadratic term in the augmented Lagrangian objective function. For the choice of the penalty parameter, we review some of the popular methods, and design a novel adaptive strategy that aims to better follow the algorithm process. Numerical experiments on linear multistage stochastic test problems suggest that most of the existing techniques may exhibit premature convergence to a sub-optimal solution or converge to the optimal solution, but at a very slow rate. In contrast, the new strategy appears to be robust and efficient, converging to optimality in all our experiments and being the fastest in most of them. For the question of handling the quadratic term, we review some existing techniques and we suggest to replace the quadratic term with a linear one. Although this method has yet to be tested, we have the intuition that it will reduce some numerical and theoretical difficulties of progressive hedging in linear problems.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. 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. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

No description available.

The work in this thesis is separated into two parts. The first part deals with the load planning and sequencing problem for double-stack intermodal railcars, an operational problem found at many rail container terminals. In this problem, containers must be assigned to a platform on which the container will be loaded, and the loading order must be determined. These decisions are made with the objective of minimizing the costs associated with handling the containers, as well as minimizing the cost of containers left behind. The deterministic version of the problem can be cast as a shortest path problem on an ordered graph. This problem is challenging to solve because of the large size of the graph. We propose a two-stage heuristic based on the Iterative Deepening A* algorithm to compute solutions to the load planning and sequencing problem within a five-minute time budget. Next, we also illustrate how a Deep Q-learning algorithm can be used to heuristically solve the same problem.The second part of this thesis considers sequential models in deep learning. A recent strategy to circumvent the exploding and vanishing gradient problem in recurrent neural networks (RNNs) is to enforce recurrent weight matrices to be orthogonal or unitary. While this ensures stable dynamics during training, it comes at the cost of reduced expressivity due to the limited variety of orthogonal transformations. We propose a parameterization of RNNs, based on the Schur decomposition, that mitigates the exploding and vanishing gradient problem, while allowing for non-orthogonal recurrent weight matrices in the model. / Le travail de cette thèse est divisé en deux parties. La première partie traite du problème de planification et de séquencement des chargements de conteneurs sur des wagons, un problème opérationnel rencontré dans de nombreux terminaux ferroviaires intermodaux. Dans ce problème, les conteneurs doivent être affectés à une plate-forme sur laquelle un ou deux conteneurs seront chargés et l'ordre de chargement doit être déterminé. Ces décisions sont prises dans le but de minimiser les coûts associés à la manutention des conteneurs, ainsi que de minimiser le coût des conteneurs non chargés. La version déterministe du problème peut être formulé comme un problème de plus court chemin sur un graphe ordonné. Ce problème est difficile à résoudre en raison de la grande taille du graphe. Nous proposons une heuristique en deux étapes basée sur l'algorithme Iterative Deepening A* pour calculer des solutions au problème de planification et de séquencement de la charge dans un budget de cinq minutes. Ensuite, nous illustrons également comment un algorithme d'apprentissage Deep Q peut être utilisé pour résoudre heuristiquement le même problème. La deuxième partie de cette thèse examine les modèles séquentiels en apprentissage profond. Une stratégie récente pour contourner le problème de gradient qui explose et disparaît dans les réseaux de neurones récurrents (RNN) consiste à imposer des matrices de poids récurrentes orthogonales ou unitaires. Bien que cela assure une dynamique stable pendant l'entraînement, cela se fait au prix d'une expressivité réduite en raison de la variété limitée des transformations orthogonales. Nous proposons une paramétrisation des RNN, basée sur la décomposition de Schur, qui atténue les problèmes de gradient, tout en permettant des matrices de poids récurrentes non orthogonales dans le modèle.

Cette thèse porte sur la modélisation du trafic dans les réseaux routiers et comment celle-ci est intégrée dans des modèles d'optimisation. Ces deux sujets ont évolué de manière plutôt disjointe: le trafic est prédit par des modèles mathématiques de plus en plus complexes, mais ce progrès n'a pas été incorporé dans les modèles de design de réseau dans lesquels les usagers de la route jouent un rôle crucial. Le but de cet ouvrage est d'intégrer des modèles d'utilités aléatoires calibrés avec de vraies données dans certains modèles biniveaux d'optimisation et ce, par une décomposition de Benders efficace. Cette décomposition particulière s'avère être généralisable par rapport à une grande classe de problèmes communs dans la litérature et permet d'en résoudre des exemples de grande taille. Le premier article présente une méthodologie générale pour utiliser des données GPS d'une flotte de véhicules afin d'estimer les paramètres d'un modèle de demande dit recursive logit. Les traces GPS sont d'abord associées aux liens d'un réseau à l'aide d'un algorithme tenant compte de plusieurs facteurs. Les chemins formés par ces suites de liens et leurs caractéristiques sont utilisés afin d'estimer les paramètres d'un modèle de choix. Ces paramètres représentent la perception qu'ont les usagers de chacune de ces caractéristiques par rapport au choix de leur chemin. Les données utilisées dans cet article proviennent des véhicules appartenant à plusieurs compagnies de transport opérant principalement dans la région de Montréal. Le deuxième article aborde l'intégration d'un modèle de choix de chemin avec utilités aléatoires dans une nouvelle formulation biniveau pour le problème de capture de flot de trafic. Le modèle proposé permet de représenter différents comportements des usagers par rapport à leur choix de chemin en définissant les utilités d'arcs appropriées. Ces utilités sont stochastiques ce qui contribue d'autant plus à capturer un comportement réaliste des usagers. Le modèle biniveau est rendu linéaire à travers l'ajout d'un terme lagrangien basé sur la dualité forte et ceci mène à une décomposition de Benders particulièrement efficace. Les expériences numériques sont principalement menés sur un réseau représentant la ville de Winnipeg ce qui démontre la possibilité de résoudre des problèmes de taille relativement grande. Le troisième article démontre que l'approche du second article peut s'appliquer à une forme particulière de modèles biniveaux qui comprennent plusieurs problèmes différents. La décomposition est d'abord présentée dans un cadre général, puis dans un contexte où le second niveau du modèle biniveau est un problème de plus courts chemins. Afin d'établir que ce contexte inclut plusieurs applications, deux applications distinctes sont adaptées à la forme requise: le transport de matières dangeureuses et la capture de flot de trafic déterministe. Une troisième application, la conception et l'établissement de prix de réseau simultanés, est aussi présentée de manière similaire à l'Annexe B de cette thèse. / The subject of this thesis is the modeling of traffic in road networks and its integration in optimization models. In the literature, these two topics have to a large extent evolved independently: traffic is predicted more accurately by increasingly complex mathematical models, but this progress has not been incorporated in network design models where road users play a crucial role. The goal of this work is to integrate random utility models calibrated with real data into bilevel optimization models through an efficient Benders decomposition. This particular decomposition generalizes to a wide class of problems commonly found in the literature and can be used to solved large-scale instances. The first article presents a general methodology to use GPS data gathered from a fleet of vehicles to estimate the parameters of a recursive logit demand model. The GPS traces are first matched to the arcs of a network through an algorithm taking into account various factors. The paths resulting from these sequences of arcs, along with their characteristics, are used to estimate parameters of a choice model. The parameters represent users' perception of each of these characteristics in regards to their path choice behaviour. The data used in this article comes from trucks used by a number of transportation companies operating mainly in the Montreal region. The second article addresses the integration of a random utility maximization model in a new bilevel formulation for the general flow capture problem. The proposed model allows for a representation of different user behaviors in regards to their path choice by defining appropriate arc utilities. These arc utilities are stochastic which further contributes in capturing real user behavior. This bilevel model is linearized through the inclusion of a Lagrangian term based on strong duality which paves the way for a particularly efficient Benders decomposition. The numerical experiments are mostly conducted on a network representing the city of Winnipeg which demonstrates the ability to solve problems of a relatively large size. The third article illustrates how the approach used in the second article can be generalized to a particular form of bilevel models which encompasses many different problems. The decomposition is first presented in a general setting and subsequently in a context where the lower level of the bilevel model is a shortest path problem. In order to demonstrate that this form is general, two distinct applications are adapted to fit the required form: hazmat transportation network design and general flow capture. A third application, joint network design and pricing, is also similarly explored in Appendix B of this thesis.

No description available.