Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Planification de tournées de véhicules pour le problème de livraison à domicile

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.

Mechanisms underlying activation of neural stem cells in the adult central nervous system

À la fin du 19e siècle, Dr. Ramón y Cajal, un pionnier scientifique, a découvert les éléments cellulaires individuels, appelés neurones, composant le système nerveux. Il a également remarqué la complexité de ce système et a mentionné l’impossibilité de ces nouveaux neurones à être intégrés dans le système nerveux adulte. Une de ses citations reconnues : “Dans les centres adultes, les chemins nerveux sont fixes, terminés, immuables. Tout doit mourir, rien ne peut être régénérer” est représentative du dogme de l’époque (Ramón y Cajal 1928). D’importantes études effectuées dans les années 1960-1970 suggèrent un point de vue différent. Il a été démontré que les nouveaux neurones peuvent être générés à l’âge adulte, mais cette découverte a créé un scepticisme omniprésent au sein de la communauté scientifique. Il a fallu 30 ans pour que le concept de neurogenèse adulte soit largement accepté. Cette découverte, en plus de nombreuses avancées techniques, a ouvert la porte à de nouvelles cibles thérapeutiques potentielles pour les maladies neurodégénératives. Les cellules souches neurales (CSNs) adultes résident principalement dans deux niches du cerveau : la zone sous-ventriculaire des ventricules latéraux et le gyrus dentelé de l’hippocampe. En condition physiologique, le niveau de neurogenèse est relativement élevé dans la zone sous-ventriculaire contrairement à l’hippocampe où certaines étapes sont limitantes. En revanche, la moelle épinière est plutôt définie comme un environnement en quiescence. Une des principales questions qui a été soulevée suite à ces découvertes est : comment peut-on activer les CSNs adultes afin d’augmenter les niveaux de neurogenèse ? Dans l’hippocampe, la capacité de l’environnement enrichi (incluant la stimulation cognitive, l’exercice et les interactions sociales) à promouvoir la neurogenèse hippocampale a déjà été démontrée. La plasticité de cette région est importante, car elle peut jouer un rôle clé dans la récupération de déficits au niveau de la mémoire et l’apprentissage. Dans la moelle épinière, des études effectuées in vitro ont démontré que les cellules épendymaires situées autour du canal central ont des capacités d’auto-renouvellement et de multipotence (neurones, astrocytes, oligodendrocytes). Il est intéressant de noter qu’in vivo, suite à une lésion de la moelle épinière, les cellules épendymaires sont activées, peuvent s’auto-renouveller, mais peuvent seulement ii donner naissance à des cellules de type gliale (astrocytes et oligodendrocytes). Cette nouvelle fonction post-lésion démontre que la plasticité est encore possible dans un environnement en quiescence et peut être exploité afin de développer des stratégies de réparation endogènes dans la moelle épinière. Les CSNs adultes jouent un rôle important dans le maintien des fonctions physiologiques du cerveau sain et dans la réparation neuronale suite à une lésion. Cependant, il y a peu de données sur les mécanismes qui permettent l'activation des CSNs en quiescence permettant de maintenir ces fonctions. L'objectif général est d'élucider les mécanismes sous-jacents à l'activation des CSNs dans le système nerveux central adulte. Pour répondre à cet objectif, nous avons mis en place deux approches complémentaires chez les souris adultes : 1) L'activation des CSNs hippocampales par l'environnement enrichi (EE) et 2) l'activation des CSNs de la moelle épinière par la neuroinflammation suite à une lésion. De plus, 3) afin d’obtenir plus d’information sur les mécanismes moléculaires de ces modèles, nous utiliserons des approches transcriptomiques afin d’ouvrir de nouvelles perspectives. Le premier projet consiste à établir de nouveaux mécanismes cellulaires et moléculaires à travers lesquels l’environnement enrichi module la plasticité du cerveau adulte. Nous avons tout d’abord évalué la contribution de chacune des composantes de l’environnement enrichi à la neurogenèse hippocampale (Chapitre II). L’exercice volontaire promeut la neurogenèse, tandis que le contexte social augmente l’activation neuronale. Par la suite, nous avons déterminé l’effet de ces composantes sur les performances comportementales et sur le transcriptome à l’aide d’un labyrinthe radial à huit bras afin d’évaluer la mémoire spatiale et un test de reconnaissante d’objets nouveaux ainsi qu’un RNA-Seq, respectivement (Chapitre III). Les coureurs ont démontré une mémoire spatiale de rappel à court-terme plus forte, tandis que les souris exposées aux interactions sociales ont eu une plus grande flexibilité cognitive à abandonner leurs anciens souvenirs. Étonnamment, l’analyse du RNA-Seq a permis d’identifier des différences claires dans l’expression des transcripts entre les coureurs de courte et longue distance, en plus des souris sociales (dans l’environnement complexe). iii Le second projet consiste à découvrir comment les cellules épendymaires acquièrent les propriétés des CSNs in vitro ou la multipotence suite aux lésions in vivo (Chapitre IV). Une analyse du RNA-Seq a révélé que le transforming growth factor-β1 (TGF-β1) agit comme un régulateur, en amont des changements significatifs suite à une lésion de la moelle épinière. Nous avons alors confirmé la présence de cette cytokine suite à la lésion et caractérisé son rôle sur la prolifération, différentiation, et survie des cellules initiatrices de neurosphères de la moelle épinière. Nos résultats suggèrent que TGF-β1 régule l’acquisition et l’expression des propriétés de cellules souches sur les cellules épendymaires provenant de la moelle épinière.