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.

Reduced models of chemical reaction in chaotic flows

We describe and evaluate two reduced models for nonlinear chemical reactions in a chaotic laminar flow. Each model involves two separate steps to compute the chemical composition at a given location and time. The “manifold tracking model” first tracks backwards in time a segment of the stable manifold of the requisite point. This then provides a sample of the initial conditions appropriate for the second step, which requires solving one-dimensional problems for the reaction in Lagrangian coordinates. By contrast, the first step of the “branching trajectories model” simulates both the advection and diffusion of fluid particles that terminate at the appropriate point; the chemical reaction equations are then solved along each of the branched trajectories in a second step. Results from each model are compared with full numerical simulations of the reaction processes in a chaotic laminar flow.

Multiple solutions and numerical analysis to the dynamic and stationary models coupling a delayed energy balance model involving latent heat and discontinuous albedo with a deep ocean

We study a climatologically important interaction of two of the main components of the geophysical system by adding an energy balance model for the averaged atmospheric temperature as dynamic boundary condition to a diagnostic ocean model having an additional spatial dimension. In this work, we give deeper insight than previous papers in the literature, mainly with respect to the 1990 pioneering model by Watts and Morantine. We are taking into consideration the latent heat for the two phase ocean as well as a possible delayed term. Non-uniqueness for the initial boundary value problem, uniqueness under a non-degeneracy condition and the existence of multiple stationary solutions are proved here. These multiplicity results suggest that an S-shaped bifurcation diagram should be expected to occur in this class of models generalizing previous energy balance models. The numerical method applied to the model is based on a finite volume scheme with nonlinear weighted essentially non-oscillatory reconstruction and Runge–Kutta total variation diminishing for time integration.

Nonlinear evolution of harmonically forced perturbations on a wingtip vortex

Wingtip vortices are created by flying airplanes due to lift generation. The vortex interaction with the trailing aircraft has sparked researchers’ interest to develop an efficient technique to destroy these vortices. Different models have been used to describe the vortex dynamics and they all show that, under real flight conditions, the most unstable modes produce a very weak amplification. Another linear instability mechanism that can produce high energy gains in short times is due to the non-normality of the system. Recently, it has been shown that these non-normal perturbations also produce this energy growth when they are excited with harmonic forcing functions. In this study, we analyze numerically the nonlinear evolution of a spatially, pointwise and temporally forced perturbation, generated by a synthetic jet at a given radial distance from the vortex core. This type of perturbation is able to produce high energy gains in the perturbed base flow (10^3), and is also a suitable candidate for use in engineering applications. The flow field is solved for using fully nonlinear three-dimensional direct numerical simulation with a spectral multidomain penalty method model. Our novel results show that the nonlinear effects are able to produce locally small bursts of instability that reduce the intensity of the primary vortex.

Calculation of mutual information for nonlinear communication channel at large signal-to-noise ratio

Using the path-integral technique we examine the mutual information for the communication channel modeled by the nonlinear Schrödinger equation with additive Gaussian noise. The nonlinear Schrödinger equation is one of the fundamental models in nonlinear physics, and it has a broad range of applications, including fiber optical communications - the backbone of the internet. At large signal-to-noise ratio we present the mutual information through the path-integral, which is convenient for the perturbative expansion in nonlinearity. In the limit of small noise and small nonlinearity we derive analytically the first nonzero nonlinear correction to the mutual information for the channel.

Discrete Velocity Models for Mixtures Without Nonphysical Collision Invariants

An important aspect of constructing discrete velocity models (DVMs) for the Boltzmann equation is to obtain the right number of collision invariants. It is a well-known fact that DVMs can also have extra collision invariants, so called spurious collision invariants, in plus to the physical ones. A DVM with only physical collision invariants, and so without spurious ones, is called normal. For binary mixtures also the concept of supernormal DVMs was introduced, meaning that in addition to the DVM being normal, the restriction of the DVM to any single species also is normal. Here we introduce generalizations of this concept to DVMs for multicomponent mixtures. We also present some general algorithms for constructing such models and give some concrete examples of such constructions. One of our main results is that for any given number of species, and any given rational mass ratios we can construct a supernormal DVM. The DVMs are constructed in such a way that for half-space problems, as the Milne and Kramers problems, but also nonlinear ones, we obtain similar structures as for the classical discrete Boltzmann equation for one species, and therefore we can apply obtained results for the classical Boltzmann equation.