1,721,102 research outputs found
On two sequential problems : the load planning and sequencing problem and the non-normal recurrent neural network
Get PDFThe 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
The berth allocation problem at port terminals : a column generation framework
Get PDFLe problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié.
Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard.
Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation.
Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire.
Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory.
In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes
Data-driven large neighbourhood search for combinatorial optimization problems
Get PDFLes problèmes d'Optimisation Combinatoire (OC) sont omniprésents dans les domaines où une allocation de ressources discrètes est requise. Ces problèmes ont des implications tangibles, car des solutions de haute qualité peuvent considérablement améliorer l'efficacité opérationnelle, réduire les coûts et augmenter la rentabilité des organisations. Typiquement formulés comme des Programmes Mixtes en Nombres Entiers (PMNE), ces problèmes présentent un défi computationnel même pour les solveurs les plus avancés (état de l'art). Cette thèse étudie le développement d'heuristiques efficaces, en particulier pour les instances de grande taille où les méthodes traditionnelles peinent à trouver des solutions de haute qualité dans des délais raisonnables. L'Apprentissage Automatique (AA) représente une voie prometteuse pour améliorer les heuristiques à usage général en apprenant des stratégies à partir des données. Cette thèse contient trois articles qui examinent l'intégration des techniques d'AA dans le cadre de la Recherche à Grand Voisinage (RGV) en mettant l'accent sur l'efficacité computationnelle. Le premier article démontre comment les données collectées tôt dans l'arbre de recherche peuvent aider à prédire des solutions de haute qualité pour les PMNE avec des ensembles ordonnés spéciaux de type 1. Ce type de contrainte est typiquement utilisé pour modéliser des affectations dans les problèmes d'OC. Le deuxième article se concentre sur le problème de conception de réseau multi-produits avec coûts fixes et capacité limitée et sur l'intégration de méthodes d'apprentissage dans l'heuristique qui représente l'état de l'art. Le troisième article combine les connaissances acquises des deux premiers pour développer une RGV améliorée par AA pour des PMNE génériques. En proposant des approches efficientes et accessibles, cette thèse pose les bases pour l'intégration pratique de l'AA en OC. Les méthodes présentées visent à équilibrer l'efficacité computationnelle avec la qualité des solutions, et elles offrent des perspectives pragmatiques sur la façon dont les techniques basées sur les données peuvent améliorer les stratégies d'optimisation traditionnelles. Ce travail contribue à l'effort continu pour résoudre plus efficacement des problèmes d'optimisation complexes et concrets, ce qui peut conduire à des améliorations significatives dans diverses industries et applications.Combinatorial Optimization (CO) problems are ubiquitous in domains where discrete resource allocation is required. These problems have significant real-world implications, as high-quality solutions can substantially enhance operational efficiency, reduce costs, and improve profitability for organizations. Typically formulated as Mixed-Integer Programs (MIPs), these problems remain computationally challenging even for state-of-the-art (SOA) solvers. This thesis studies the development of effective heuristics, particularly for large-scale instances where traditional methods struggle to find high-quality solutions within reasonable time constraints. Machine Learning (ML) presents a promising avenue for enhancing general-purpose heuristics by learning strategies from data. This thesis contains three articles that investigate the integration of ML techniques within the Large Neighbourhood Search (LNS) framework with a focus on computational efficiency. The first article demonstrates how data collected early in the search tree can help predict high-quality solutions for MIPs with special ordered sets of type 1. This type of constraint is typically used to model assignments in CO problems. The second article focuses on the multicommodity capacitated fixed-charge network design problem and the integration of learning methods within the SOA heuristic. The third paper combines the insights learned from the first two papers to develop a ML-enhanced LNS for generic MIPs. By proposing cost-effective and accessible approaches, this thesis lays a foundation for the practical integration of ML in CO. The methods presented aim to balance computational efficiency with solution quality and they offer pragmatic perspectives on how data-driven techniques can augment traditional optimization strategies. This work contributes to the ongoing effort to solve complex, real-world optimization problems more efficiently, which can lead to significant improvements in various industries and applications
Strategic capacity planning and pricing : a choice-based approach
Get PDFCette thèse étudie les problèmes de décision stratégiques abordés par un fournisseur de services logistiques (FSL) souhaitant optimiser ses profits ou ses pertes, lorsque l'information dont il dispose à propos de la demande de ses clients pour de nouveaux services est incomplète. Nous adoptons l'hypothèse que la demande est issue de la maximisation d'utilité par les clients. Puisque la connaissance des préférences des clients par le FSL est incertaine, celles-ci sont décrites au moyen de modèles d'utilité aléatoires. La thèse est constituée de trois articles dans lesquels les problèmes traités par le FSL sont exprimés sous forme de programmes stochastiques bi-niveaux où le FSL est le leader et les clients sont les suiveurs. Les articles proposent des reformulations à un seul niveau fondées sur les propriétés duales des solutions optimales et faisant usage de la méthode d'approximation par moyenne échantillonnale pour le calcul des utilités espérées. Ces reformulations sous-tendent la construction, d'une part, de méthodes de résolution asymptotiquement exactes dont la vitesse est supérieure à celle des méthodes de pointe actuelles et, d'autre part, de méthodes heuristiques dont la vitesse et l'exactitude sont élevées. Cette thèse est basée sur trois articles. Dans le premier article, le FSL offre aux expéditeurs des combinaisons de prix et de niveau de service de sorte à maximiser l'espérance des profits résultant de la fourniture des combinaisons sélectionnées par les expéditeurs, à l'inclusion des coûts associés à l'installation des lieux de service. Le programme du niveau inférieur concerne dans ce cas la sélection des combinaisons de prix et de service par les expéditeurs. Dans le second article, le FSL désire minimiser l'espérance du total de ses coûts de livraison et de fonctionnement en offrant à ses clients de substituer la visite de points de cueillette et livraison à la livraison à domicile. Le programme du niveau inférieur concerne dans ce cas la sélection des points de cueillette et livraison ou de la livraison à domicile par les clients. Le troisième article introduit un procédé d'agrégation des scénarios dans la reformulation développée dans le premier article, permettant ainsi d'accroître la vitesse de calcul de plusieurs ordres de grandeur. En résumé, cette thèse fait avancer l'état de l'art sur les formulations stochastiques bi-niveaux pour les problèmes de localisation et de tarification. Ces problèmes sont difficiles à résoudre en raison des objectifs de maximisation du profit, des structures de coût complexes et des contraintes de capacité. D’un point de vue applicatif, la thèse fournit des perspectives managériales essentielles pour les fournisseurs logistiques.This thesis examines strategic decision-making problems addressed by a profit-maximizing or cost-minimizing logistic provider (LP) faced with the demand of its customers for new services, about which incomplete information is available. The demand is driven by the utility-maximizing customers' preferences and, from the LP's perspective, these preferences are surrounded by uncertainty. They are described with random utility maximizing models. The thesis comprises three articles where the LP's problems are expressed by stochastic bilevel programming formulations in which the LP is the leader and its customers are the followers. The articles propose single-level reformulations leveraging the properties of the dual optimal solutions and utilizing the method of sample average approximation to compute expected utilities. These reformulations yield asymptotically exact and faster than the state-of-the-art computation methods as well as heuristic, high-accuracy, high-speed computation methods. The thesis is based on three articles. In the first article, the LP offers combinations of price and service level to the shippers and aims to maximize the expected profits of supplying the selected combinations, including the costs related to facility installation. The lower level concerns the selection of the combinations of price and service level by the shippers. In the second article, the LP aims to minimize its total expected delivery and operating costs by offering its customers to substitute the use of collection-and-delivery points for home-delivery service. The lower level concerns the selection of service points or home-delivery by the customers. The third article introduces an aggregation procedure in the reformulation of the first article, thereby increasing the speed of computation by several orders of magnitude. To summarize, the thesis advances the literature on stochastic bilevel formulations for facility location and pricing problems. These problems are challenging to solve due to profit-maximizing objectives, complex cost structures, and capacity constraints. From an application perspective, the thesis offers managerial insights valuable to LPs.Ecuadorian Secretaría de Educación Superior, Ciencia, Tecnología e Innovacion (SENESCYT)Escuela Superior Politecnica del Litoral, Ecuado
Méta-enseignement : génération active d’exemples par apprentissage par renforcement
Get PDFLe problème d’intérêt est un problème d’optimisation discrète dont on tente d’approximer les
solutions des instances particulières à l’aide de réseaux de neurones. Un obstacle à résoudre ce
problème par apprentissage automatique réside dans le coût d’étiquettage élevé (et variable)
des différentes instances, rendant coûteuse et difficile la génération d’un ensemble de données
étiquettées. On propose une architecture d’apprentissage actif, qu’on nomme architecture de
méta-enseignement, dans le but de pallier à ce problème. On montre comment on combine
plusieurs modèles afin de résoudre ce problème d’apprentissage actif, formulé comme un
problème de méta-apprentissage, en utilisant un agent d’apprentissage par renforcement
pour la génération active d’exemples. Ainsi, on utilise des concepts de plusieurs domaines
de l’apprentissage automatique dont des notions d’apprentissage supervisé, d’apprentissage
actif, d’apprentissage par renforcement, ainsi que des réseaux récurrents. Dans ce travail
exploratoire, on évalue notre méthodologie sur un problème simple, soit celui de classifier
des mains de poker en 10 classes pré-établies. On teste notre architecture sur ce problème
jouet dans le but de simplifier l’analyse. Malheureusement, l’avantage d’utiliser l’architecture
de génération active n’est pas significatif. On expose ensuite plusieurs pistes de réflexion
sur certaines observations à approfondir dans de futurs travaux, comme la définition de la
fonction de récompense. Dans de futurs projets, il serait également intéressant d’utiliser un
problème plus similaire au problème d’optimisation initial qui comporterait, entre autres,
des coûts d’étiquettage variables.The motivating application behind this architecture is a discrete optimisation problem
whose solution we aim to predict using neural networks. A main challenge of solving this
problem by machine learning lies in the high (and variable) labelling cost associated to
the various instances, which leads to an expensive and difficult dataset generation. We
propose an active learning architecture, called meta-teaching, to address this problem. We
show how we combine several models to solve the active learning problem, formulated as
a metalearning problem, by using a reinforcement learning agent to actively generate new
instances. Therefore, we use concepts from various areas of machine learning, including
supervised learning, active learning, reinforcement learning and recurrent networks. In this
exploratory work, we evaluate our method on a simpler problem, which is to classify poker
hands in 10 predefined classes. We test our architecture on this toy dataset in order to
simplify the analysis. Unfortunately, we do not achieve a significant advantage using our
active generation architecture on this dataset. We outline avenues for further reflections,
including the definition of the reward function. In future projects, using a more similar
problem to our problem of interest having, among others, a variable labelling cost, would
be interesting
Development of new scenario decomposition techniques for linear and nonlinear stochastic programming
Get PDFUne 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
The berth allocation problem at port terminals : a column generation framework
Get PDFLe problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié.
Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard.
Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation.
Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire.
Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory.
In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes
Machine learning accelerated stochastic optimization and applications to railway operations
Get PDFNous proposons des innovations méthodologiques combinant l’apprentissage automatique (AA) et la recherche opérationnelle (RO) où des prédicteurs issus de l’AA supervisé sont entraînés hors-ligne et introduits dans des algorithmes de RO pour accélérer les calculs en-ligne. La synergie entre RO et AA est particulièrement avantageuse pour la programmation stochastique. Nous concentrant sur les problèmes de décision à deux étapes, nous vérifions que des prédictions de la solution de deuxième étape (DE) améliorent considérablement le compromis entre exactitude et vitesse des calculs. Nous éprouvons nos propositions sur des applications réalistes et des problèmes standardisés. La thèse comprend cinq articles: The Load Planning Problem for Double-stack Intermodal Trains traite en contexte réaliste le problème opérationnel déterministe de chargement optimal (PCO) de conteneurs sur des wagons doublement étagés. Il établit en outre les bases des applications de l’AA à la RO examinées dans les deux articles suivants où l’apprentissage se fonde sur des paires entrée-sortie joignant une instance déterministe du PCO à sa solution exacte. Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information emploie l’AA hors-ligne pour accélérer la programmation stochastique à deux étapes lorsque DE est difficile. Les prédictions d’AA de la solution espérée de DE, conditionnelles aux variables de première étape (PE), obvient à la génération de scénarios et au calcul de solutions en DE. Elles produisent des solutions globales avec plus d’exactitude et de vitesse en-ligne que les méthodes alternatives. Une application à une version tactique du PCO est présentée. A Language Processing Algorithm for Predicting Tactical Solutions to an Operational Planning Problem Under Uncertainty démontre l’usage d’un algorithme de traduction neural pour générer des prédictions rapides et fidèles de solutions détaillées d’un problème stochastique de décision. Il décrit comment établir les vocabulaires et les syntaxes, introduire des contraintes portant sur la relation d’entrée-sortie ou sur les sorties. Il définit une mesure de discordance et un prédicteur de référence. Une application au PCO est présentée. Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning présente une matheuristique résolvant un programme stochastique linéaire à deux étapes avec variables mixtes. Il démontre comment la substitution de solutions d’AA au sous-problème de Benders pour le calcul de coupes d’optimalité L-shaped entières et continues permet un compromis avantageux entre exactitude et temps de calcul en-ligne. Les temps sont indépendants du nombre de scénarios et le prédicteur d’AA est valide pour des familles de problèmes paramétrées. Une application à des familles dérivées de problèmes stochastiques standard de localisation de serveurs et de sac-à-dos multiple est présentée. Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems présente des générateurs simulant une large gamme de problèmes de conception de réseau déterministes et stochastiques avec multiples classes d’objets, capacités et coûts fixes. Il vise à faciliter l’évaluation et la comparaison de méthodes de solution exactes et heuristiques, notamment usant de l’AA, et à favoriser la reproductibilité et la comparabilité de résultats publiés.We present methodological innovations at the intersection of machine learning (ML) and operations research (OR) where predictions from generic input-output map approximators originating from supervised ML are trained offline and introduced within OR algorithms to accelerate online computations. We demonstrate that the synergy between OR and ML can be highly advantageous for stochastic programming. Concentrating on two-stage stochastic decision problems, we verify that, by introducing at the first stage (FS) predictions about the expected solution of second stage (SS), the trade-off between accuracy and online computational speed attained by the overall solution process can be considerably improved. We test our ideas upon realistic applications and standardized problems. The thesis comprises five articles: The Load Planning Problem for Double-stack Intermodal Trains addresses in a realistic setting the deterministic operational load planning problem (LPP) of optimally loading intermodal containers onto double-stack railcars. While this has intrinsic interest, it also establishes the foundations of the applications of ML to OR considered in the next two articles. There, ML relies on input-output pairs joining a deterministic LPP instance with its exact solution. Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information employs offline ML to accelerate two-stage stochastic programming when the SS is computationally demanding. ML predictions of the expected solution of the SS problem, conditional on FS variables, avoid online SS generation of scenarios and solution and yield overall solutions with greater accuracy and online speed than otherwise achievable. An extensive application to a tactical version of the LPP is examined. A Language Processing Algorithm for Predicting Tactical Solutions to an Operational Planning Problem Under Uncertainty demonstrates the use of a neural machine translation algorithm for generating fast and accurate predictions of solutions to a complex and detailed stochastic discrete decision problem. It describes how to specify the input and output vocabularies and syntaxes, enforce constraints restricting the input-output map or the output, and define a measure of discrepancy and a baseline. An extensive application to the LPP is presented. Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning presents a matheuristic solving linear two-stage stochastic programs where integers appear in both stages. It demonstrates large reductions in online solution time while incurring small reductions in overall accuracy by substituting ML solutions for the Benders subproblems and calculating approximate integer and continuous L-shaped optimality cuts. Computation times are independent of number of scenarios and the ML predictor is valid for parameterized families of problems. An extensive application to families of problems derived from standard classes of stochastic server location and stochastic multi knapsack problems is presented. Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems fills a gap in the literature on network design, introducing flexible and high-speed generators capable of simulating a wide range of settings for the deterministic and stochastic multi-commodity, capacitated, fixed charge network design problems. We aim to facilitate systematic experimentations, leading to more thorough assessments of performance of exact and heuristic solution methods, and to foster reproducibility and comparability of published research
Route choice and traffic equilibrium modeling in multi-modal and activity-based networks
Get PDFQue ce soit pour aller au travail, faire du magasinage ou participer à des activités sociales, la mobilité fait partie intégrante de la vie quotidienne. Nous bénéficions à cet égard d'un nombre grandissant de moyens de transports, ce qui contribue tant à notre qualité de vie qu'au développement économique. Néanmoins, la demande croissante de mobilité, à laquelle s'ajoutent l'expansion urbaine et l'accroissement du parc automobile, a également des répercussions négatives locales et globales, telles que le trafic, les nuisances sonores, et la dégradation de l'environnement. Afin d'atténuer ces effets néfastes, les autorités cherchent à mettre en oeuvre des politiques de gestion de la demande avec le meilleur résultat possible pour la société. Pour ce faire, ces dernières ont besoin d'évaluer l'impact de différentes mesures. Cette perspective est ce qui motive le problème de l'analyse et la prédiction du comportement des usagers du système de transport, et plus précisément quand, comment et par quel itinéraire les individus décident de se déplacer.
Cette thèse a pour but de développer et d'appliquer des modèles permettant de prédire les flux de personnes et/ou de véhicules dans des réseaux urbains comportant plusieurs modes de transport. Il importe que de tels modèles soient supportés par des données, génèrent des prédictions exactes, et soient applicables à des réseaux réels. Dans la pratique, le problème de prédiction de flux se résout en deux étapes. La première, l'analyse de choix d'itinéraire, a pour but d'identifier le chemin que prendrait un voyageur dans un réseau pour effectuer un trajet entre un point A et un point B. Pour ce faire, on estime à partir de données les paramètres d'une fonction de coût multi-attribut représentant le comportement des usagers du réseau. La seconde étape est celle de l'affectation de trafic, qui distribue la demande totale dans le réseau de façon à obtenir un équilibre, c.-à-d. un état dans lequel aucun utilisateur ne souhaite changer d'itinéraire. La difficulté de cette étape consiste à modéliser la congestion du réseau, qui dépend du choix de route de tous les voyageurs et affecte simultanément la fonction de coût de chacun.
Cette thèse se compose de quatre articles soumis à des journaux internationaux et d'un chapitre additionnel. Dans tous les articles, nous modélisons le choix d'itinéraire d'un individu comme une séquence de choix d'arcs dans le réseau, selon une approche appelée modèle de choix d'itinéraire récursif. Cette méthodologie possède d'avantageuses propriétés, comme un estimateur non biaisé et des procédures d'affectation rapides, en évitant de générer des ensembles de chemins. Néanmoins, l'estimation de tels modèles pose une difficulté additionnelle puisqu'elle nécessite de résoudre un problème de programmation dynamique imbriqué, ce qui explique que cette approche ne soit pas encore largement utilisée dans le domaine de la recherche en transport. Or, l'objectif principal de cette thèse est de répondre des défis liés à l'application de cette méthodologie à des réseaux multi-modaux. La force de cette thèse consiste en des applications à échelle réelle qui soulèvent des défis computationnels, ainsi que des contributions méthodologiques.
Le premier article est un tutoriel sur l'analyse de choix d'itinéraire à travers les modèles récursifs susmentionnés. Les contributions principales sont de familiariser les chercheur.e.s avec cette méthodologie, de donner une certaine intuition sur les propriétés du modèle, d'illustrer ses avantages sur de petits réseaux, et finalement de placer ce problème dans un contexte plus large en tissant des liens avec des travaux dans les domaines de l'optimisation inverse et de l'apprentissage automatique.
Deux articles et un chapitre additionnel appartiennent à la catégorie de travaux appliquant la méthodologie précédemment décrite sur des réseaux réels, de grande taille et multi-modaux. Ces applications vont au-delà des précédentes études dans ce contexte, qui ont été menées sur des réseaux routiers simples. Premièrement, nous estimons des modèles de choix d'itinéraire récursifs pour les trajets de cyclistes, et nous soulignons certains avantages de cette méthodologie dans le cadre de la prédiction. Nous étendons ensuite ce premier travail afin de traiter le cas d'un réseau de transport public comportant plusieurs modes. Enfin, nous considérons un problème de prédiction de demande plus large, où l'on cherche à prédire simultanément l'enchaînement des trajets quotidiens des voyageurs et leur participation aux activités qui motivent ces déplacements.
Finalement, l'article concluant cette thèse concerne la modélisation d'affectation de trafic. Plus précisément, nous nous intéressons au calcul d'un équilibre dans un réseau où chaque arc peut posséder une capacité finie, ce qui est typiquement le cas des réseaux de transport public. Cet article apporte d'importantes contributions méthodologiques. Nous proposons un modèle markovien d'équilibre de trafic dit stratégique, qui permet d'affecter la demande sur les arcs du réseau sans en excéder la capacité, tout en modélisant comment la probabilité qu'un arc atteigne sa capacité modifie le choix de route des usagers.Traveling is an essential part of daily life, whether to attend work, perform social activities, or go shopping among others. We benefit from an increasing range of available transportation services to choose from, which supports economic growth and contributes to our quality of life. Yet the growing demand for travel, combined with urban sprawl and increasing vehicle ownership rates, is also responsible for major local and global externalities, such as degradation of the environment, congestion and noise. In order to mitigate the negative impacts of traveling while weighting benefits to users, transportation planners seek to design policies and improve infrastructure with the best possible outcome for society as a whole. Taking effective actions requires to evaluate the impact of various measures, which necessitates first to understand and predict travel behavior, i.e., how, when and by which route individuals decide to travel.
With this background in mind, this thesis has the objective of developing and applying models to predict flows of persons and/or vehicles in multi-modal transportation networks. It is desirable that such models be data-driven, produce accurate predictions, and be applicable to real networks. In practice, the problem of flow prediction is addressed in two separate steps, and this thesis is concerned with both. The first, route choice analysis, is the problem of identifying the path a traveler would take in a network. This is achieved by estimating from data a parametrized cost function representing travelers' behavior. The second step, namely traffic assignment, aims at distributing all travelers on the network's paths in order to find an equilibrium state, such that no traveler has an interest in changing itinerary. The challenge lies in taking into account the effect of generated congestion, which depends on travelers' route choices while simultaneously impacting their cost of traveling.
This thesis is composed of four articles submitted to international journals and an additional chapter. In all the articles of the thesis, we model an individual's choice of path as a sequence of link choices, using so-called recursive route choice models. This methodology is a state-of-the-art framework which is known to possess the advantage of unbiased parameter estimates and fast assignment procedures, by avoiding to generate choice sets of paths. However, it poses the additional challenge of requiring one to solve embedded dynamic programming problems, and is hence not widely used in the transportation community. This thesis addresses practical and theoretical challenges related to applying this methodological framework to real multi-modal networks. The strength of this thesis consists in large-scale applications which bear computational challenges, as well as some methodological contributions to this modeling framework.
The first article in this thesis is a tutorial on predicting and analyzing path choice behavior using recursive route choice models. The contribution of this article is to familiarize researchers with this methodology, to give intuition on the model properties, to illustrate its advantages through examples, and finally to position this modeling framework within a broader context, by establishing links with recently published work in the inverse optimization and machine learning fields.
Two articles and an additional chapter can be categorized as applications of the methodology to estimate parameters of travel demand models in several large, real, and/or multi-dimensional networks. These applications go beyond previous studies on small physical road networks. First, we estimate recursive models for the route choice of cyclists and we demonstrate some advantages of the recursive models in the context of prediction. We also provide an application to a time-expanded public transportation networks with several modes. Then, we consider a broader travel demand problem, in which decisions regarding daily trips and participation in activities are made jointly. The latter is also modeled with recursive route choice models by considering sequences of activity, destination and mode choices as paths in a so-called supernetwork.
Finally, the subject of the last article in this thesis is traffic assignment. More precisely, we address the problem of computing a traffic equilibrium in networks with strictly limited link capacities, such as public transport networks. This article provides important methodological contributions. We propose a strategic Markovian traffic equilibrium model which assigns flows to networks without exceeding link capacities while realistically modeling how the risk of not being able to access an arc affects route choice behavior
Analyse du comportement hétérogène des usagers dans un réseau
Get PDFLe nombre important de véhicules sur le réseau routier peut entraîner des problèmes d'encombrement et de sécurité. Les usagers des réseaux routiers qui nous intéressent sont les camionneurs qui transportent des marchandises, pouvant rouler avec des véhicules non conformes ou emprunter des routes interdites pour gagner du temps. Le transport de matières dangereuses est réglementé et certains lieux, surtout les ponts et les tunnels, leur sont interdits d'accès. Pour aider à faire appliquer les lois en vigueur, il existe un système de contrôles routiers composé de structures fixes et de patrouilles mobiles. Le déploiement stratégique de ces ressources de contrôle mise sur la connaissance du comportement des camionneurs que nous allons étudier à travers l'analyse de leurs choix de routes.
Un problème de choix de routes peut se modéliser en utilisant la théorie des choix discrets, elle-même fondée sur la théorie de l'utilité aléatoire. Traiter ce type de problème avec cette théorie est complexe. Les modèles que nous utiliserons sont tels, que nous serons amenés à faire face à des problèmes de corrélation, puisque plusieurs routes partagent probablement des arcs. De plus, puisque nous travaillons sur le réseau routier du Québec, le choix de routes peut se faire parmi un ensemble de routes dont le nombre est potentiellement infini si on considère celles ayant des boucles.
Enfin, l'étude des choix faits par un humain n'est pas triviale.
Avec l'aide du modèle de choix de routes retenu, nous pourrons calculer une expression de la probabilité qu'une route soit prise par le camionneur.
Nous avons abordé cette étude du comportement en commençant par un travail de description des données collectées. Le questionnaire utilisé par les contrôleurs permet de collecter des données concernant les camionneurs, leurs véhicules et le lieu du contrôle. La description des données observées est une étape essentielle, car elle permet de présenter clairement à un analyste potentiel ce qui est accessible pour étudier les comportements des camionneurs. Les données observées lors d'un contrôle constitueront ce que nous appellerons une observation. Avec les attributs du réseau, il sera possible de modéliser le réseau routier du Québec. Une sélection de certains attributs permettra de spécifier la fonction d'utilité et par conséquent la fonction permettant de calculer les probabilités de choix de routes par un camionneur. Il devient alors possible d'étudier un comportement en se basant sur des observations. Celles provenant du terrain ne nous donnent pas suffisamment d'information actuellement et même en spécifiant bien un modèle, l'estimation des paramètres n'est pas possible. Cette dernière est basée sur la méthode du maximum de vraisemblance.
Nous avons l'outil, mais il nous manque la matière première que sont les observations, pour continuer l'étude.
L'idée est de poursuivre avec des observations de synthèse. Nous ferons des estimations avec des observations complètes puis, pour se rapprocher des conditions réelles, nous continuerons avec des observations partielles. Ceci constitue d'ailleurs un défi majeur. Nous proposons pour ces dernières, de nous servir des résultats des travaux de (Bierlaire et Frejinger, 2008) en les combinant avec ceux de (Fosgerau, Frejinger et Karlström, 2013).
Bien qu'elles soient de nature synthétiques, les observations que nous utilisons nous mèneront à des résultats tels, que nous serons en mesure de fournir une proposition concrète qui pourrait aider à optimiser les décisions des responsables des contrôles routiers. En effet, nous avons réussi à estimer, sur le réseau réel du Québec, avec un seuil de signification de 0,05 les valeurs des paramètres d'un modèle de choix de routes discrets, même lorsque les observations sont partielles. Ces résultats donneront lieu à des recommandations sur les changements à faire dans le questionnaire permettant de collecter des données.Using transportation roads enables workers to reach their work facilities. Security and traffic jam issues are all the more important given that the number of vehicles is always increasing and we will focus on merchandise transporters in this study. Dangerous items transportation is under strict control as it is for example forbidden for them to be carried through a tunnel or across a bridge. Some transporters may drive a vehicle that has defects or/and they may be ta\-king some forbidden roads so as to reach their destination faster. Transportation of goods is regulated by the law and there exists a control system, whose purpose is to detect frauds and to make sure controlled vehicles are in order. The strategic deployment of control resources can be based on the knowledge of transporters behaviour, which is going to be studied through their route choice analysis. The number of routes can be unbounded especially if we consider loops, which leads to a complex problem to be solved. We can also mention issues closely related to route choice problem using discrete choice models such as correlation between routes sharing links and point out the fact that human decision process is not considered something easy.
A route choice problem can be modelled based on the random utility theory and as a consequence we will focus on the discrete choice models. We are going to use such model on the real road network of Quebec and we will derive an expression of the probability, for a transporter, to pick one route.
We are going to explain the way we did our study. It started first by doing a data description job as we are convinced this is a step that will help other analysts to have a clear view of the data situation. Some data are network related and the corresponding attributes collected will be used to model the road network of Quebec.
We will use some attributes to explain the utility function, which leads to the definition of the function that gives the probability that a user takes a given route. Once this function is fully specified, the behaviour study can be done, except that we have a set of observations that are absolutely incomplete. When observations are a gathering of data collected during a road control, the information they provide us is not enough and thus, the parameters estimation will fail.
We might seem blocked but in fact, we brought the idea of using simulated observations.
We are going to estimate model parameters with firstly complete observations and in order to imitate the real conditions, we then are going to use partial observations. This constitutes a main challenge and we overcome it by using the results presented in (Bierlaire et Frejinger, 2008) combined with those from (Fosgerau, Frejinger et Karlström, 2013). We will demonstrate that even though the observations used are simulated, we will deliver conclusions that can be useful for road network managers. The main results we provide in this work is that estimation can be done with a 0,05 signification level on real road network of Quebec, while the observations are incomplete. Eventually, our results should motivate network managers to improve the set of questions they use to collect data as it would help them to strengthen their knowledge about the merchandise transporters and hopefully, the decision process will lead to optimized resource deployments
- …
